ref: d5d28f89b918b303a36e59e9602669d4f718c54e
dir: /src/cache/ftlru.c/
/***************************************************************************/ /* */ /* ftlru.c */ /* */ /* Simple LRU list-cache (body). */ /* */ /* Copyright 2000 by */ /* David Turner, Robert Wilhelm, and Werner Lemberg. */ /* */ /* This file is part of the FreeType project, and may only be used, */ /* modified, and distributed under the terms of the FreeType project */ /* license, LICENSE.TXT. By continuing to use, modify, or distribute */ /* this file you indicate that you have read the license and */ /* understand and accept it fully. */ /* */ /***************************************************************************/ #include <freetype/cache/ftlru.h> #include <freetype/ftlist.h> #include <freetype/internal/ftobjs.h> static void lru_build_free_list( FT_LruNode nodes, FT_UInt count, FT_List free_list ) { FT_LruNode node = nodes; FT_LruNode limit = node + count; free_list->head = free_list->tail = 0; for ( ; node < limit; node++ ) FT_List_Add( free_list, (FT_ListNode)node ); } FT_EXPORT_DEF( FT_Error ) FT_Lru_New( const FT_Lru_Class* clazz, FT_UInt max_elements, FT_Pointer user_data, FT_Memory memory, FT_Bool pre_alloc, FT_Lru *anlru ) { FT_Error error; FT_Lru lru; if ( !anlru ) return FT_Err_Invalid_Argument; *anlru = 0; if ( !ALLOC( lru, sizeof ( *lru ) ) ) { if ( pre_alloc ) { /* allocate static array of lru list nodes */ if ( ALLOC_ARRAY( lru->nodes, max_elements, FT_LruNodeRec ) ) { FREE( lru ); goto Exit; } /* build the `free_nodes' list from the array */ lru_build_free_list( lru->nodes, max_elements, &lru->free_nodes ); } /* initialize common fields */ lru->clazz = (FT_Lru_Class*)clazz; lru->max_elements = max_elements; lru->memory = memory; lru->user_data = user_data; *anlru = lru; } Exit: return error; } FT_EXPORT_DEF( void ) FT_Lru_Reset( FT_Lru lru ) { FT_ListNode node; FT_Lru_Class* clazz; FT_Memory memory; if ( !lru ) return; node = lru->elements.head; clazz = lru->clazz; memory = lru->memory; while ( node ) { FT_ListNode next = node->next; clazz->done_element( lru, (FT_LruNode)node ); if ( !lru->nodes ) FREE( node ); node = next; } /* rebuild free list if necessary */ if ( lru->nodes ) lru_build_free_list( lru->nodes, lru->max_elements, &lru->free_nodes ); lru->elements.head = lru->elements.tail = 0; lru->num_elements = 0; } FT_EXPORT_DEF( void ) FT_Lru_Done( FT_Lru lru ) { FT_Memory memory; if ( !lru ) return; memory = lru->memory; FT_Lru_Reset( lru ); FREE( lru ); } FT_EXPORT_DEF( FT_Error ) FT_Lru_Lookup_Node( FT_Lru lru, FT_LruKey key, FT_LruNode *anode ) { FT_Error error = 0; FT_ListNode node; FT_Lru_Class* clazz; FT_LruNode found = 0; FT_Memory memory; if ( !lru || !key || !anode ) return FT_Err_Invalid_Argument; node = lru->elements.head; clazz = lru->clazz; memory = lru->memory; if ( clazz->compare_element ) { for ( ; node; node = node->next ) if ( clazz->compare_element( (FT_LruNode)node, key ) ) { found = (FT_LruNode)node; break; } } else { for ( ; node; node = node->next ) if ( ((FT_LruNode)node)->key == key ) { found = (FT_LruNode)node; break; } } if ( !found ) { /* we haven't found the relevant element. We will now try */ /* to create a new one. */ if ( lru->num_elements >= lru->max_elements ) { /* this lru list is full; we will now flush */ /* the oldest node */ FT_LruNode lru_node; node = lru->elements.tail; lru_node = (FT_LruNode)node; found = lru_node; if ( clazz->flush_element ) error = clazz->flush_element( lru, lru_node, key ); else { clazz->done_element( lru, lru_node ); lru_node->key = key; node->data = 0; error = clazz->init_element( lru, lru_node ); } if ( !error ) { /* now, move element to top of list */ FT_List_Up( &lru->elements, node ); } else { /* in case of error, the node must be discarded */ FT_List_Remove( &lru->elements, node ); lru->num_elements--; if ( lru->nodes ) FT_List_Insert( &lru->free_nodes, node ); else FREE( lru_node ); found = 0; } } else { FT_LruNode lru_node; /* create a new lru list node, then the element for it */ if ( lru->nodes ) { node = lru->free_nodes.head; lru_node = (FT_LruNode)node; lru_node->key = key; error = clazz->init_element( lru, lru_node ); if ( error ) goto Exit; FT_List_Remove( &lru->free_nodes, node ); } else { if ( ALLOC( lru_node, sizeof ( *lru_node ) ) ) goto Exit; lru_node->key = key; error = clazz->init_element( lru, lru_node ); if ( error ) { FREE( lru_node ); goto Exit; } } found = lru_node; node = (FT_ListNode)lru_node; FT_List_Insert( &lru->elements, node ); lru->num_elements++; } } Exit: *anode = found; return error; } FT_EXPORT_DEF( FT_Error ) FT_Lru_Lookup( FT_Lru lru, FT_LruKey key, FT_Pointer *anobject ) { FT_Error error; FT_LruNode node; /* check for valid `lru' and `key' delayed to FT_Lru_Lookup_Node() */ if ( !anobject ) return FT_Err_Invalid_Argument; *anobject = 0; error = FT_Lru_Lookup_Node( lru, key, &node ); if ( !error ) *anobject = node->root.data; return error; } FT_EXPORT_DEF( void ) FT_Lru_Remove_Node( FT_Lru lru, FT_LruNode node ) { if ( !lru || !node ) return; if ( lru->num_elements > 0 ) { FT_List_Remove( &lru->elements, (FT_ListNode)node ); lru->clazz->done_element( lru, node ); if ( lru->nodes ) FT_List_Insert( &lru->free_nodes, (FT_ListNode)node ); else { FT_Memory memory = lru->memory; FREE( node ); } lru->num_elements--; } } FT_EXPORT_DEF( void ) FT_Lru_Remove_Selection( FT_Lru lru, FT_Lru_Selector selector, FT_Pointer data ) { if ( !lru || !selector ) return; if ( lru->num_elements > 0 ) { FT_ListNode node = lru->elements.head; FT_ListNode next; while ( node ) { next = node->next; if ( selector( lru, (FT_LruNode)node, data ) ) { /* remove this element from the list, and destroy it */ FT_Lru_Remove_Node( lru, (FT_LruNode)node ); } node = next; } } } /* END */