| /***************************************************************************/ |
| /* */ |
| /* 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 */ |