1/***************************************************************************/
2/*                                                                         */
3/*  ftcmru.c                                                               */
4/*                                                                         */
5/*    FreeType MRU support (body).                                         */
6/*                                                                         */
7/*  Copyright 2003, 2004, 2006, 2009 by                                    */
8/*  David Turner, Robert Wilhelm, and Werner Lemberg.                      */
9/*                                                                         */
10/*  This file is part of the FreeType project, and may only be used,       */
11/*  modified, and distributed under the terms of the FreeType project      */
12/*  license, LICENSE.TXT.  By continuing to use, modify, or distribute     */
13/*  this file you indicate that you have read the license and              */
14/*  understand and accept it fully.                                        */
15/*                                                                         */
16/***************************************************************************/
17
18
19#include <ft2build.h>
20#include FT_CACHE_H
21#include "ftcmru.h"
22#include FT_INTERNAL_OBJECTS_H
23#include FT_INTERNAL_DEBUG_H
24
25#include "ftcerror.h"
26
27
28  FT_LOCAL_DEF( void )
29  FTC_MruNode_Prepend( FTC_MruNode  *plist,
30                       FTC_MruNode   node )
31  {
32    FTC_MruNode  first = *plist;
33
34
35    if ( first )
36    {
37      FTC_MruNode  last = first->prev;
38
39
40#ifdef FT_DEBUG_ERROR
41      {
42        FTC_MruNode  cnode = first;
43
44
45        do
46        {
47          if ( cnode == node )
48          {
49            fprintf( stderr, "FTC_MruNode_Prepend: invalid action\n" );
50            exit( 2 );
51          }
52          cnode = cnode->next;
53
54        } while ( cnode != first );
55      }
56#endif
57
58      first->prev = node;
59      last->next  = node;
60      node->next  = first;
61      node->prev  = last;
62    }
63    else
64    {
65      node->next = node;
66      node->prev = node;
67    }
68    *plist = node;
69  }
70
71
72  FT_LOCAL_DEF( void )
73  FTC_MruNode_Up( FTC_MruNode  *plist,
74                  FTC_MruNode   node )
75  {
76    FTC_MruNode  first = *plist;
77
78
79    FT_ASSERT( first != NULL );
80
81    if ( first != node )
82    {
83      FTC_MruNode  prev, next, last;
84
85
86#ifdef FT_DEBUG_ERROR
87      {
88        FTC_MruNode  cnode = first;
89        do
90        {
91          if ( cnode == node )
92            goto Ok;
93          cnode = cnode->next;
94
95        } while ( cnode != first );
96
97        fprintf( stderr, "FTC_MruNode_Up: invalid action\n" );
98        exit( 2 );
99      Ok:
100      }
101#endif
102      prev = node->prev;
103      next = node->next;
104
105      prev->next = next;
106      next->prev = prev;
107
108      last = first->prev;
109
110      last->next  = node;
111      first->prev = node;
112
113      node->next = first;
114      node->prev = last;
115
116      *plist = node;
117    }
118  }
119
120
121  FT_LOCAL_DEF( void )
122  FTC_MruNode_Remove( FTC_MruNode  *plist,
123                      FTC_MruNode   node )
124  {
125    FTC_MruNode  first = *plist;
126    FTC_MruNode  prev, next;
127
128
129    FT_ASSERT( first != NULL );
130
131#ifdef FT_DEBUG_ERROR
132      {
133        FTC_MruNode  cnode = first;
134
135
136        do
137        {
138          if ( cnode == node )
139            goto Ok;
140          cnode = cnode->next;
141
142        } while ( cnode != first );
143
144        fprintf( stderr, "FTC_MruNode_Remove: invalid action\n" );
145        exit( 2 );
146      Ok:
147      }
148#endif
149
150    prev = node->prev;
151    next = node->next;
152
153    prev->next = next;
154    next->prev = prev;
155
156    if ( node == next )
157    {
158      FT_ASSERT( first == node );
159      FT_ASSERT( prev  == node );
160
161      *plist = NULL;
162    }
163    else if ( node == first )
164      *plist = next;
165  }
166
167
168  FT_LOCAL_DEF( void )
169  FTC_MruList_Init( FTC_MruList       list,
170                    FTC_MruListClass  clazz,
171                    FT_UInt           max_nodes,
172                    FT_Pointer        data,
173                    FT_Memory         memory )
174  {
175    list->num_nodes = 0;
176    list->max_nodes = max_nodes;
177    list->nodes     = NULL;
178    list->clazz     = *clazz;
179    list->data      = data;
180    list->memory    = memory;
181  }
182
183
184  FT_LOCAL_DEF( void )
185  FTC_MruList_Reset( FTC_MruList  list )
186  {
187    while ( list->nodes )
188      FTC_MruList_Remove( list, list->nodes );
189
190    FT_ASSERT( list->num_nodes == 0 );
191  }
192
193
194  FT_LOCAL_DEF( void )
195  FTC_MruList_Done( FTC_MruList  list )
196  {
197    FTC_MruList_Reset( list );
198  }
199
200
201#ifndef FTC_INLINE
202  FT_LOCAL_DEF( FTC_MruNode )
203  FTC_MruList_Find( FTC_MruList  list,
204                    FT_Pointer   key )
205  {
206    FTC_MruNode_CompareFunc  compare = list->clazz.node_compare;
207    FTC_MruNode              first, node;
208
209
210    first = list->nodes;
211    node  = NULL;
212
213    if ( first )
214    {
215      node = first;
216      do
217      {
218        if ( compare( node, key ) )
219        {
220          if ( node != first )
221            FTC_MruNode_Up( &list->nodes, node );
222
223          return node;
224        }
225
226        node = node->next;
227
228      } while ( node != first);
229    }
230
231    return NULL;
232  }
233#endif
234
235  FT_LOCAL_DEF( FT_Error )
236  FTC_MruList_New( FTC_MruList   list,
237                   FT_Pointer    key,
238                   FTC_MruNode  *anode )
239  {
240    FT_Error     error;
241    FTC_MruNode  node = NULL;
242    FT_Memory    memory = list->memory;
243
244
245    if ( list->num_nodes >= list->max_nodes && list->max_nodes > 0 )
246    {
247      node = list->nodes->prev;
248
249      FT_ASSERT( node );
250
251      if ( list->clazz.node_reset )
252      {
253        FTC_MruNode_Up( &list->nodes, node );
254
255        error = list->clazz.node_reset( node, key, list->data );
256        if ( !error )
257          goto Exit;
258      }
259
260      FTC_MruNode_Remove( &list->nodes, node );
261      list->num_nodes--;
262
263      if ( list->clazz.node_done )
264        list->clazz.node_done( node, list->data );
265    }
266    else if ( FT_ALLOC( node, list->clazz.node_size ) )
267      goto Exit;
268
269    error = list->clazz.node_init( node, key, list->data );
270    if ( error )
271      goto Fail;
272
273    FTC_MruNode_Prepend( &list->nodes, node );
274    list->num_nodes++;
275
276  Exit:
277    *anode = node;
278    return error;
279
280  Fail:
281    if ( list->clazz.node_done )
282      list->clazz.node_done( node, list->data );
283
284    FT_FREE( node );
285    goto Exit;
286  }
287
288
289#ifndef FTC_INLINE
290  FT_LOCAL_DEF( FT_Error )
291  FTC_MruList_Lookup( FTC_MruList   list,
292                      FT_Pointer    key,
293                      FTC_MruNode  *anode )
294  {
295    FTC_MruNode  node;
296
297
298    node = FTC_MruList_Find( list, key );
299    if ( node == NULL )
300      return FTC_MruList_New( list, key, anode );
301
302    *anode = node;
303    return 0;
304  }
305#endif /* FTC_INLINE */
306
307  FT_LOCAL_DEF( void )
308  FTC_MruList_Remove( FTC_MruList  list,
309                      FTC_MruNode  node )
310  {
311    FTC_MruNode_Remove( &list->nodes, node );
312    list->num_nodes--;
313
314    {
315      FT_Memory  memory = list->memory;
316
317
318      if ( list->clazz.node_done )
319        list->clazz.node_done( node, list->data );
320
321      FT_FREE( node );
322    }
323  }
324
325
326  FT_LOCAL_DEF( void )
327  FTC_MruList_RemoveSelection( FTC_MruList              list,
328                               FTC_MruNode_CompareFunc  selection,
329                               FT_Pointer               key )
330  {
331    FTC_MruNode  first, node, next;
332
333
334    first = list->nodes;
335    while ( first && ( selection == NULL || selection( first, key ) ) )
336    {
337      FTC_MruList_Remove( list, first );
338      first = list->nodes;
339    }
340
341    if ( first )
342    {
343      node = first->next;
344      while ( node != first )
345      {
346        next = node->next;
347
348        if ( selection( node, key ) )
349          FTC_MruList_Remove( list, node );
350
351        node = next;
352      }
353    }
354  }
355
356
357/* END */
358