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