1 /***************************************************************************/
5 /* Simple LRU list-cache (body). */
7 /* Copyright 2000-2001 by */
8 /* David Turner, Robert Wilhelm, and Werner Lemberg. */
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. */
16 /***************************************************************************/
21 #include FT_CACHE_INTERNAL_LRU_H
23 #include FT_INTERNAL_OBJECTS_H
29 lru_build_free_list( FT_LruNode nodes,
33 FT_LruNode node = nodes;
34 FT_LruNode limit = node + count;
37 free_list->head = free_list->tail = 0;
38 for ( ; node < limit; node++ )
39 FT_List_Add( free_list, (FT_ListNode)node );
43 FT_EXPORT_DEF( FT_Error )
44 FT_Lru_New( const FT_Lru_Class* clazz,
56 return FTC_Err_Invalid_Argument;
59 if ( !ALLOC( lru, sizeof ( *lru ) ) )
63 /* allocate static array of lru list nodes */
64 if ( ALLOC_ARRAY( lru->nodes, max_elements, FT_LruNodeRec ) )
70 /* build the `free_nodes' list from the array */
71 lru_build_free_list( lru->nodes, max_elements, &lru->free_nodes );
74 /* initialize common fields */
75 lru->clazz = (FT_Lru_Class*)clazz;
76 lru->max_elements = max_elements;
78 lru->user_data = user_data;
89 FT_Lru_Reset( FT_Lru lru )
99 node = lru->elements.head;
101 memory = lru->memory;
105 FT_ListNode next = node->next;
108 clazz->done_element( lru, (FT_LruNode)node );
115 /* rebuild free list if necessary */
117 lru_build_free_list( lru->nodes, lru->max_elements, &lru->free_nodes );
119 lru->elements.head = lru->elements.tail = 0;
120 lru->num_elements = 0;
124 FT_EXPORT_DEF( void )
125 FT_Lru_Done( FT_Lru lru )
133 memory = lru->memory;
142 FT_EXPORT_DEF( FT_Error )
143 FT_Lru_Lookup_Node( FT_Lru lru,
150 FT_LruNode found = 0;
154 if ( !lru || !key || !anode )
155 return FTC_Err_Invalid_Argument;
157 node = lru->elements.head;
159 memory = lru->memory;
161 if ( clazz->compare_element )
163 for ( ; node; node = node->next )
164 if ( clazz->compare_element( (FT_LruNode)node, key ) )
166 found = (FT_LruNode)node;
172 for ( ; node; node = node->next )
173 if ( ((FT_LruNode)node)->key == key )
175 found = (FT_LruNode)node;
182 /* move element to top of list */
183 FT_List_Up( &lru->elements, node );
187 /* we haven't found the relevant element. We will now try */
188 /* to create a new one. */
189 if ( lru->num_elements >= lru->max_elements )
191 /* this lru list is full; we will now flush */
192 /* the oldest node */
196 node = lru->elements.tail;
197 lru_node = (FT_LruNode)node;
200 if ( clazz->flush_element )
201 error = clazz->flush_element( lru, lru_node, key );
204 clazz->done_element( lru, lru_node );
207 error = clazz->init_element( lru, lru_node );
212 /* now, move element to top of list */
213 FT_List_Up( &lru->elements, node );
217 /* in case of error, the node must be discarded */
218 FT_List_Remove( &lru->elements, node );
222 FT_List_Insert( &lru->free_nodes, node );
234 /* create a new lru list node, then the element for it */
237 node = lru->free_nodes.head;
238 lru_node = (FT_LruNode)node;
241 error = clazz->init_element( lru, lru_node );
245 FT_List_Remove( &lru->free_nodes, node );
249 if ( ALLOC( lru_node, sizeof ( *lru_node ) ) )
253 error = clazz->init_element( lru, lru_node );
262 node = (FT_ListNode)lru_node;
263 FT_List_Insert( &lru->elements, node );
274 FT_EXPORT_DEF( FT_Error )
275 FT_Lru_Lookup( FT_Lru lru,
277 FT_Pointer *anobject )
283 /* check for valid `lru' and `key' delayed to FT_Lru_Lookup_Node() */
286 return FTC_Err_Invalid_Argument;
289 error = FT_Lru_Lookup_Node( lru, key, &node );
291 *anobject = node->root.data;
297 FT_EXPORT_DEF( void )
298 FT_Lru_Remove_Node( FT_Lru lru,
304 if ( lru->num_elements > 0 )
306 FT_List_Remove( &lru->elements, (FT_ListNode)node );
307 lru->clazz->done_element( lru, node );
310 FT_List_Insert( &lru->free_nodes, (FT_ListNode)node );
313 FT_Memory memory = lru->memory;
324 FT_EXPORT_DEF( void )
325 FT_Lru_Remove_Selection( FT_Lru lru,
326 FT_Lru_Selector selector,
329 if ( !lru || !selector )
332 if ( lru->num_elements > 0 )
334 FT_ListNode node = lru->elements.head;
341 if ( selector( lru, (FT_LruNode)node, data ) )
343 /* remove this element from the list, and destroy it */
344 FT_Lru_Remove_Node( lru, (FT_LruNode)node );