+++ /dev/null
-/***************************************************************************/
-/* */
-/* ftlru.c */
-/* */
-/* Simple LRU list-cache (body). */
-/* */
-/* Copyright 2000-2001 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 <ft2build.h>
-#include FT_CACHE_H
-#include FT_CACHE_INTERNAL_LRU_H
-#include FT_LIST_H
-#include FT_INTERNAL_OBJECTS_H
-
-#include "ftcerror.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 FTC_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->nodes );
- 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 FTC_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 )
- {
- /* move element to top of list */
- FT_List_Up( &lru->elements, node );
- }
- else
- {
- /* 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 FTC_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 */
projects / rrdtool.git / blobdiff