lib/freetype/src/cache/ftlru.c

   1 /***************************************************************************/
   2 /*                                                                         */
   3 /*  ftlru.c                                                                */
   4 /*                                                                         */
   5 /*    Simple LRU list-cache (body).                                        */
   6 /*                                                                         */
   7 /*  Copyright 2000-2001, 2002 by                                           */
   8 /*  David Turner, Robert Wilhelm, and Werner Lemberg.                      */
   9 /*                                                                         */
  10 /*  This file is part of the FreeType project, and may only be used,       */
  11 /*  modified, and distributed under the terms of the FreeType project      */
  12 /*  license, LICENSE.TXT.  By continuing to use, modify, or distribute     */
  13 /*  this file you indicate that you have read the license and              */
  14 /*  understand and accept it fully.                                        */
  15 /*                                                                         */
  16 /***************************************************************************/
  17
  18
  19 #include <ft2build.h>
  20 #include FT_CACHE_H
  21 #include FT_CACHE_INTERNAL_LRU_H
  22 #include FT_LIST_H
  23 #include FT_INTERNAL_OBJECTS_H
  24 #include FT_INTERNAL_DEBUG_H
  25
  26 #include "ftcerror.h"
  27
  28
  29   FT_EXPORT_DEF( FT_Error )
  30   FT_LruList_New( FT_LruList_Class  clazz,
  31                   FT_UInt           max_nodes,
  32                   FT_Pointer        user_data,
  33                   FT_Memory         memory,
  34                   FT_LruList       *alist )
  35   {
  36     FT_Error    error;
  37     FT_LruList  list;
  38
  39
  40     if ( !alist || !clazz )
  41       return FTC_Err_Invalid_Argument;
  42
  43     *alist = NULL;
  44     if ( !FT_ALLOC( list, clazz->list_size ) )
  45     {
  46       /* initialize common fields */
  47       list->clazz      = clazz;
  48       list->memory     = memory;
  49       list->max_nodes  = max_nodes;
  50       list->data       = user_data;
  51
  52       if ( clazz->list_init )
  53       {
  54         error = clazz->list_init( list );
  55         if ( error )
  56         {
  57           if ( clazz->list_done )
  58             clazz->list_done( list );
  59
  60           FT_FREE( list );
  61         }
  62       }
  63
  64       *alist = list;
  65     }
  66
  67     return error;
  68   }
  69
  70
  71   FT_EXPORT_DEF( void )
  72   FT_LruList_Destroy( FT_LruList  list )
  73   {
  74     FT_Memory         memory;
  75     FT_LruList_Class  clazz;
  76
  77
  78     if ( !list )
  79       return;
  80
  81     memory = list->memory;
  82     clazz  = list->clazz;
  83
  84     FT_LruList_Reset( list );
  85
  86     if ( clazz->list_done )
  87       clazz->list_done( list );
  88
  89     FT_FREE( list );
  90   }
  91
  92
  93   FT_EXPORT_DEF( void )
  94   FT_LruList_Reset( FT_LruList  list )
  95   {
  96     FT_LruNode        node;
  97     FT_LruList_Class  clazz;
  98     FT_Memory         memory;
  99
 100
 101     if ( !list )
 102       return;
 103
 104     node   = list->nodes;
 105     clazz  = list->clazz;
 106     memory = list->memory;
 107
 108     while ( node )
 109     {
 110       FT_LruNode  next = node->next;
 111
 112
 113       if ( clazz->node_done )
 114         clazz->node_done( node, list->data );
 115
 116       FT_FREE( node );
 117       node = next;
 118     }
 119
 120     list->nodes     = NULL;
 121     list->num_nodes = 0;
 122   }
 123
 124
 125   FT_EXPORT_DEF( FT_Error )
 126   FT_LruList_Lookup( FT_LruList   list,
 127                      FT_LruKey    key,
 128                      FT_LruNode  *anode )
 129   {
 130     FT_Error          error = 0;
 131     FT_LruNode        node, *pnode;
 132     FT_LruList_Class  clazz;
 133     FT_LruNode*       plast;
 134     FT_LruNode        result = NULL;
 135     FT_Memory         memory;
 136
 137
 138     if ( !list || !key || !anode )
 139       return FTC_Err_Invalid_Argument;
 140
 141     pnode  = &list->nodes;
 142     plast  = pnode;
 143     node   = NULL;
 144     clazz  = list->clazz;
 145     memory = list->memory;
 146
 147     if ( clazz->node_compare )
 148     {
 149       for (;;)
 150       {
 151         node = *pnode;
 152         if ( node == NULL )
 153           break;
 154
 155         if ( clazz->node_compare( node, key, list->data ) )
 156           break;
 157
 158         plast = pnode;
 159         pnode = &(*pnode)->next;
 160       }
 161     }
 162     else
 163     {
 164       for (;;)
 165       {
 166         node = *pnode;
 167         if ( node == NULL )
 168           break;
 169
 170         if ( node->key == key )
 171           break;
 172
 173         plast = pnode;
 174         pnode = &(*pnode)->next;
 175       }
 176     }
 177
 178     if ( node )
 179     {
 180       /* move element to top of list */
 181       if ( list->nodes != node )
 182       {
 183         *pnode      = node->next;
 184         node->next  = list->nodes;
 185         list->nodes = node;
 186       }
 187       result = node;
 188       goto Exit;
 189     }
 190
 191    /* since we haven't found the relevant element in our LRU list,
 192     * we're going to "create" a new one.
 193     *
 194     * the following code is a bit special, because it tries to handle
 195     * out-of-memory conditions (OOM) in an intelligent way.
 196     *
 197     * more precisely, if not enough memory is available to create a
 198     * new node or "flush" an old one, we need to remove the oldest
 199     * elements from our list, and try again. since several tries may
 200     * be necessary, a loop is needed
 201     *
 202     * this loop will only exit when:
 203     *
 204     *   - a new node was succesfully created, or an old node flushed
 205     *   - an error other than FT_Err_Out_Of_Memory is detected
 206     *   - the list of nodes is empty, and it isn't possible to create
 207     *     new nodes
 208     *
 209     * on each unsucesful attempt, one node will be removed from the list
 210     *
 211     */
 212
 213     {
 214       FT_Int   drop_last = ( list->max_nodes > 0 &&
 215                              list->num_nodes >= list->max_nodes );
 216
 217       for (;;)
 218       {
 219         node = NULL;
 220
 221        /* when "drop_last" is true, we should free the last node in
 222         * the list to make room for a new one. note that we re-use
 223         * its memory block to save allocation calls.
 224         */
 225         if ( drop_last )
 226         {
 227          /* find the last node in the list
 228           */
 229           pnode = &list->nodes;
 230           node  = *pnode;
 231
 232           if ( node == NULL )
 233           {
 234             FT_ASSERT( list->nodes == 0 );
 235             error = FT_Err_Out_Of_Memory;
 236             goto Exit;
 237           }
 238
 239           FT_ASSERT( list->num_nodes > 0 );
 240
 241           while ( node->next )
 242           {
 243             pnode = &node->next;
 244             node  = *pnode;
 245           }
 246
 247          /* remove it from the list, and try to "flush" it. doing this will
 248           * save a significant number of dynamic allocations compared to
 249           * a classic destroy/create cycle
 250           */
 251           *pnode = NULL;
 252           list->num_nodes -= 1;
 253
 254           if ( clazz->node_flush )
 255           {
 256             error = clazz->node_flush( node, key, list->data );
 257             if ( !error )
 258               goto Success;
 259
 260            /* note that if an error occured during the flush, we need to
 261             * finalize it since it is potentially in incomplete state.
 262             */
 263           }
 264
 265          /* we finalize, but do not destroy the last node, we
 266           * simply re-use its memory block !
 267           */
 268           if ( clazz->node_done )
 269             clazz->node_done( node, list->data );
 270
 271           FT_MEM_ZERO( node, clazz->node_size );
 272         }
 273         else
 274         {
 275          /* try to allocate a new node when "drop_last" is not TRUE
 276           * this usually happens on the first pass, when the LRU list
 277           * is not already full.
 278           */
 279           if ( FT_ALLOC( node, clazz->node_size ) )
 280             goto Fail;
 281         }
 282
 283         FT_ASSERT( node != NULL );
 284
 285         node->key = key;
 286         error = clazz->node_init( node, key, list->data );
 287         if ( error )
 288         {
 289           if ( clazz->node_done )
 290             clazz->node_done( node, list->data );
 291
 292           FT_FREE( node );
 293           goto Fail;
 294         }
 295
 296       Success:
 297         result = node;
 298
 299         node->next  = list->nodes;
 300         list->nodes = node;
 301         list->num_nodes++;
 302         goto Exit;
 303
 304       Fail:
 305         if ( error != FT_Err_Out_Of_Memory )
 306           goto Exit;
 307
 308         drop_last = 1;
 309         continue;
 310       }
 311     }
 312
 313   Exit:
 314     *anode = result;
 315     return error;
 316   }
 317
 318
 319
 320   FT_EXPORT_DEF( void )
 321   FT_LruList_Remove( FT_LruList  list,
 322                      FT_LruNode  node )
 323   {
 324     FT_LruNode  *pnode;
 325
 326
 327     if ( !list || !node )
 328       return;
 329
 330     pnode = &list->nodes;
 331     for (;;)
 332     {
 333       if ( *pnode == node )
 334       {
 335         FT_Memory         memory = list->memory;
 336         FT_LruList_Class  clazz  = list->clazz;
 337
 338
 339         *pnode     = node->next;
 340         node->next = NULL;
 341
 342         if ( clazz->node_done )
 343           clazz->node_done( node, list->data );
 344
 345         FT_FREE( node );
 346         list->num_nodes--;
 347         break;
 348       }
 349
 350       pnode = &(*pnode)->next;
 351     }
 352   }
 353
 354
 355   FT_EXPORT_DEF( void )
 356   FT_LruList_Remove_Selection( FT_LruList             list,
 357                                FT_LruNode_SelectFunc  select_func,
 358                                FT_Pointer             select_data )
 359   {
 360     FT_LruNode       *pnode, node;
 361     FT_LruList_Class  clazz;
 362     FT_Memory         memory;
 363
 364
 365     if ( !list || !select_func )
 366       return;
 367
 368     memory = list->memory;
 369     clazz  = list->clazz;
 370     pnode  = &list->nodes;
 371
 372     for (;;)
 373     {
 374       node = *pnode;
 375       if ( node == NULL )
 376         break;
 377
 378       if ( select_func( node, select_data, list->data ) )
 379       {
 380         *pnode     = node->next;
 381         node->next = NULL;
 382
 383         if ( clazz->node_done )
 384           clazz->node_done( node, list );
 385
 386         FT_FREE( node );
 387       }
 388       else
 389         pnode = &(*pnode)->next;
 390     }
 391   }
 392
 393
 394 /* END */