1 /***************************************************************************/
2 /*                                                                         */
3 /*  ftcmru.c                                                               */
4 /*                                                                         */
5 /*    FreeType MRU support (body).                                         */
6 /*                                                                         */
7 /*  Copyright 2003-2018 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 );
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 );
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 )
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 || 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