/***************************************************************************/
/* */
/* ftlru.c */
/* */
/* Simple LRU list-cache (body). */
/* */
/* Copyright 2000-2001, 2002, 2003 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 FT_INTERNAL_DEBUG_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;
}
/* Since we haven't found the relevant element in our LRU list,
* we're going to "create" a new one.
*
* The following code is a bit special, because it tries to handle
* out-of-memory conditions (OOM) in an intelligent way.
*
* More precisely, if not enough memory is available to create a
* new node or "flush" an old one, we need to remove the oldest
* elements from our list, and try again. Since several tries may
* be necessary, a loop is needed.
*
* This loop will only exit when:
*
* - a new node was successfully created, or an old node flushed
* - an error other than FT_Err_Out_Of_Memory is detected
* - the list of nodes is empty, and it isn't possible to create
* new nodes
*
* On each unsuccessful attempt, one node will be removed from the list.
*
*/
{
FT_Int drop_last = ( list->max_nodes > 0 &&
list->num_nodes >= list->max_nodes );
for (;;)
{
node = NULL;
/* If "drop_last" is true, we should free the last node in
* the list to make room for a new one. Note that we reuse
* its memory block to save allocation calls.
*/
if ( drop_last )
{
/* find the last node in the list
*/
pnode = &list->nodes;
node = *pnode;
if ( node == NULL )
{
FT_ASSERT( list->nodes == 0 );
error = FT_Err_Out_Of_Memory;
goto Exit;
}
FT_ASSERT( list->num_nodes > 0 );
while ( node->next )
{
pnode = &node->next;
node = *pnode;
}
/* Remove it from the list, and try to "flush" it. Doing this will
* save a significant number of dynamic allocations compared to
* a classic destroy/create cycle.
*/
*pnode = NULL;
list->num_nodes -= 1;
if ( clazz->node_flush )
{
error = clazz->node_flush( node, key, list->data );
if ( !error )
goto Success;
/* Note that if an error occured during the flush, we need to
* finalize it since it is potentially in incomplete state.
*/
}
/* We finalize, but do not destroy the last node, we
* simply reuse its memory block!
*/
if ( clazz->node_done )
clazz->node_done( node, list->data );
FT_MEM_ZERO( node, clazz->node_size );
}
else
{
/* Try to allocate a new node when "drop_last" is not TRUE.
* This usually happens on the first pass, when the LRU list
* is not already full.
*/
if ( FT_ALLOC( node, clazz->node_size ) )
goto Fail;
}
FT_ASSERT( node != NULL );
node->key = key;
error = clazz->node_init( node, key, list->data );
if ( error )
{
if ( clazz->node_done )
clazz->node_done( node, list->data );
FT_FREE( node );
goto Fail;
}
Success:
result = node;
node->next = list->nodes;
list->nodes = node;
list->num_nodes++;
goto Exit;
Fail:
if ( error != FT_Err_Out_Of_Memory )
goto Exit;
drop_last = 1;
continue;
}
}
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 */
