ref: a3c378024bfb412f021223bc7eca3d5030423060
dir: /src/cache/ftlru.c/
/***************************************************************************/
/* */
/* ftlru.c */
/* */
/* Simple LRU list-cache (body). */
/* */
/* Copyright 2000-2001, 2002 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"
FT_EXPORT_DEF( FT_Error )
FT_LruList_New( FT_LruList_Class clazz,
FT_UInt max_nodes,
FT_Pointer user_data,
FT_Memory memory,
FT_LruList *alist )
{
FT_Error error;
FT_LruList list;
if ( !alist || !clazz )
return FTC_Err_Invalid_Argument;
*alist = NULL;
if ( !FT_ALLOC( list, clazz->list_size ) )
{
/* initialize common fields */
list->clazz = clazz;
list->memory = memory;
list->max_nodes = max_nodes;
list->data = user_data;
if ( clazz->list_init )
{
error = clazz->list_init( list );
if ( error )
{
if ( clazz->list_done )
clazz->list_done( list );
FT_FREE( list );
}
}
*alist = list;
}
return error;
}
FT_EXPORT_DEF( void )
FT_LruList_Destroy( FT_LruList list )
{
FT_Memory memory;
FT_LruList_Class clazz;
if ( !list )
return;
memory = list->memory;
clazz = list->clazz;
FT_LruList_Reset( list );
if ( clazz->list_done )
clazz->list_done( list );
FT_FREE( list );
}
FT_EXPORT_DEF( void )
FT_LruList_Reset( FT_LruList list )
{
FT_LruNode node;
FT_LruList_Class clazz;
FT_Memory memory;
if ( !list )
return;
node = list->nodes;
clazz = list->clazz;
memory = list->memory;
while ( node )
{
FT_LruNode next = node->next;
if ( clazz->node_done )
clazz->node_done( node, list->data );
FT_FREE( node );
node = next;
}
list->nodes = NULL;
list->num_nodes = 0;
}
FT_EXPORT_DEF( FT_Error )
FT_LruList_Lookup( FT_LruList list,
FT_LruKey key,
FT_LruNode *anode )
{
FT_Error error = 0;
FT_LruNode node, *pnode;
FT_LruList_Class clazz;
FT_LruNode* plast;
FT_LruNode result = NULL;
FT_Memory memory;
if ( !list || !key || !anode )
return FTC_Err_Invalid_Argument;
pnode = &list->nodes;
plast = pnode;
node = NULL;
clazz = list->clazz;
memory = list->memory;
if ( clazz->node_compare )
{
for (;;)
{
node = *pnode;
if ( node == NULL )
break;
if ( clazz->node_compare( node, key, list->data ) )
break;
plast = pnode;
pnode = &(*pnode)->next;
}
}
else
{
for (;;)
{
node = *pnode;
if ( node == NULL )
break;
if ( node->key == key )
break;
plast = pnode;
pnode = &(*pnode)->next;
}
}
if ( node )
{
/* move element to top of list */
if ( list->nodes != node )
{
*pnode = node->next;
node->next = list->nodes;
list->nodes = node;
}
result = node;
goto Exit;
}
/* we haven't found the relevant element. We will now try */
/* to create a new one. */
/* */
/* first, check if our list if full, when appropriate */
if ( list->max_nodes > 0 && list->num_nodes >= list->max_nodes )
{
/* this list list is full; we will now flush */
/* the oldest node, if there's one! */
FT_LruNode last = *plast;
if ( last )
{
if ( clazz->node_flush )
{
error = clazz->node_flush( last, key, list->data );
}
else
{
if ( clazz->node_done )
clazz->node_done( last, list->data );
last->key = key;
error = clazz->node_init( last, key, list->data );
}
if ( !error )
{
/* move it to the top of the list */
*plast = NULL;
last->next = list->nodes;
list->nodes = last;
result = last;
goto Exit;
}
/* in case of error during the flush or done/init cycle, */
/* we need to discard the node */
if ( clazz->node_done )
clazz->node_done( last, list->data );
*plast = NULL;
list->num_nodes--;
FT_FREE( last );
goto Exit;
}
}
/* otherwise, simply allocate a new node */
if ( FT_ALLOC( node, clazz->node_size ) )
goto Exit;
node->key = key;
error = clazz->node_init( node, key, list->data );
if ( error )
{
FT_FREE( node );
goto Exit;
}
result = node;
node->next = list->nodes;
list->nodes = node;
list->num_nodes++;
Exit:
*anode = result;
return error;
}
FT_EXPORT_DEF( void )
FT_LruList_Remove( FT_LruList list,
FT_LruNode node )
{
FT_LruNode *pnode;
if ( !list || !node )
return;
pnode = &list->nodes;
for (;;)
{
if ( *pnode == node )
{
FT_Memory memory = list->memory;
FT_LruList_Class clazz = list->clazz;
*pnode = node->next;
node->next = NULL;
if ( clazz->node_done )
clazz->node_done( node, list->data );
FT_FREE( node );
list->num_nodes--;
break;
}
pnode = &(*pnode)->next;
}
}
FT_EXPORT_DEF( void )
FT_LruList_Remove_Selection( FT_LruList list,
FT_LruNode_SelectFunc select_func,
FT_Pointer select_data )
{
FT_LruNode *pnode, node;
FT_LruList_Class clazz;
FT_Memory memory;
if ( !list || !select_func )
return;
memory = list->memory;
clazz = list->clazz;
pnode = &list->nodes;
for (;;)
{
node = *pnode;
if ( node == NULL )
break;
if ( select_func( node, select_data, list->data ) )
{
*pnode = node->next;
node->next = NULL;
if ( clazz->node_done )
clazz->node_done( node, list );
FT_FREE( node );
}
else
pnode = &(*pnode)->next;
}
}
/* END */