libraries/freetype-2.0.5/ftlru.c

   1 /***************************************************************************/
   2 /*                                                                         */
   3 /*  ftlru.c                                                                */
   4 /*                                                                         */
   5 /*    Simple LRU list-cache (body).                                        */
   6 /*                                                                         */
   7 /*  Copyright 2000-2001 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
  25 #include "ftcerror.h"
  26
  27
  28   static void
  29   lru_build_free_list( FT_LruNode  nodes,
  30                        FT_UInt     count,
  31                        FT_List     free_list )
  32   {
  33     FT_LruNode  node  = nodes;
  34     FT_LruNode  limit = node + count;
  35
  36
  37     free_list->head = free_list->tail = 0;
  38     for ( ; node < limit; node++ )
  39       FT_List_Add( free_list, (FT_ListNode)node );
  40   }
  41
  42
  43   FT_EXPORT_DEF( FT_Error )
  44   FT_Lru_New( const FT_Lru_Class*  clazz,
  45               FT_UInt              max_elements,
  46               FT_Pointer           user_data,
  47               FT_Memory            memory,
  48               FT_Bool              pre_alloc,
  49               FT_Lru              *anlru )
  50   {
  51     FT_Error  error;
  52     FT_Lru    lru;
  53
  54
  55     if ( !anlru )
  56       return FTC_Err_Invalid_Argument;
  57
  58     *anlru = 0;
  59     if ( !ALLOC( lru, sizeof ( *lru ) ) )
  60     {
  61       if ( pre_alloc )
  62       {
  63         /* allocate static array of lru list nodes */
  64         if ( ALLOC_ARRAY( lru->nodes, max_elements, FT_LruNodeRec ) )
  65         {
  66           FREE( lru );
  67           goto Exit;
  68         }
  69
  70         /* build the `free_nodes' list from the array */
  71         lru_build_free_list( lru->nodes, max_elements, &lru->free_nodes );
  72       }
  73
  74       /* initialize common fields */
  75       lru->clazz        = (FT_Lru_Class*)clazz;
  76       lru->max_elements = max_elements;
  77       lru->memory       = memory;
  78       lru->user_data    = user_data;
  79
  80       *anlru = lru;
  81     }
  82
  83   Exit:
  84     return error;
  85   }
  86
  87
  88   FT_EXPORT_DEF( void )
  89   FT_Lru_Reset( FT_Lru  lru )
  90   {
  91     FT_ListNode    node;
  92     FT_Lru_Class*  clazz;
  93     FT_Memory      memory;
  94
  95
  96     if ( !lru )
  97       return;
  98
  99     node   = lru->elements.head;
 100     clazz  = lru->clazz;
 101     memory = lru->memory;
 102
 103     while ( node )
 104     {
 105       FT_ListNode  next = node->next;
 106
 107
 108       clazz->done_element( lru, (FT_LruNode)node );
 109       if ( !lru->nodes )
 110         FREE( node );
 111
 112       node = next;
 113     }
 114
 115     /* rebuild free list if necessary */
 116     if ( lru->nodes )
 117       lru_build_free_list( lru->nodes, lru->max_elements, &lru->free_nodes );
 118
 119     lru->elements.head = lru->elements.tail = 0;
 120     lru->num_elements  = 0;
 121   }
 122
 123
 124   FT_EXPORT_DEF( void )
 125   FT_Lru_Done( FT_Lru  lru )
 126   {
 127     FT_Memory  memory;
 128
 129
 130     if ( !lru )
 131       return;
 132
 133     memory = lru->memory;
 134
 135     FT_Lru_Reset( lru );
 136
 137     FREE( lru->nodes );
 138     FREE( lru );
 139   }
 140
 141
 142   FT_EXPORT_DEF( FT_Error )
 143   FT_Lru_Lookup_Node( FT_Lru       lru,
 144                       FT_LruKey    key,
 145                       FT_LruNode  *anode )
 146   {
 147     FT_Error       error = 0;
 148     FT_ListNode    node;
 149     FT_Lru_Class*  clazz;
 150     FT_LruNode     found = 0;
 151     FT_Memory      memory;
 152
 153
 154     if ( !lru || !key || !anode )
 155       return FTC_Err_Invalid_Argument;
 156
 157     node   = lru->elements.head;
 158     clazz  = lru->clazz;
 159     memory = lru->memory;
 160
 161     if ( clazz->compare_element )
 162     {
 163       for ( ; node; node = node->next )
 164         if ( clazz->compare_element( (FT_LruNode)node, key ) )
 165         {
 166           found = (FT_LruNode)node;
 167           break;
 168         }
 169     }
 170     else
 171     {
 172       for ( ; node; node = node->next )
 173         if ( ((FT_LruNode)node)->key == key )
 174         {
 175           found = (FT_LruNode)node;
 176           break;
 177         }
 178     }
 179
 180     if ( found )
 181     {
 182       /* move element to top of list */
 183       FT_List_Up( &lru->elements, node );
 184     }
 185     else
 186     {
 187       /* we haven't found the relevant element.  We will now try */
 188       /* to create a new one.                                    */
 189       if ( lru->num_elements >= lru->max_elements )
 190       {
 191         /* this lru list is full; we will now flush */
 192         /* the oldest node                          */
 193         FT_LruNode  lru_node;
 194
 195
 196         node     = lru->elements.tail;
 197         lru_node = (FT_LruNode)node;
 198         found    = lru_node;
 199
 200         if ( clazz->flush_element )
 201           error = clazz->flush_element( lru, lru_node, key );
 202         else
 203         {
 204           clazz->done_element( lru, lru_node );
 205           lru_node->key = key;
 206           node->data    = 0;
 207           error = clazz->init_element( lru, lru_node );
 208         }
 209
 210         if ( !error )
 211         {
 212           /* now, move element to top of list */
 213           FT_List_Up( &lru->elements, node );
 214         }
 215         else
 216         {
 217           /* in case of error, the node must be discarded */
 218           FT_List_Remove( &lru->elements, node );
 219           lru->num_elements--;
 220
 221           if ( lru->nodes )
 222             FT_List_Insert( &lru->free_nodes, node );
 223           else
 224             FREE( lru_node );
 225
 226           found = 0;
 227         }
 228       }
 229       else
 230       {
 231         FT_LruNode  lru_node;
 232
 233
 234         /* create a new lru list node, then the element for it */
 235         if ( lru->nodes )
 236         {
 237           node          = lru->free_nodes.head;
 238           lru_node      = (FT_LruNode)node;
 239           lru_node->key = key;
 240
 241           error = clazz->init_element( lru, lru_node );
 242           if ( error )
 243             goto Exit;
 244
 245           FT_List_Remove( &lru->free_nodes, node );
 246         }
 247         else
 248         {
 249           if ( ALLOC( lru_node, sizeof ( *lru_node ) ) )
 250             goto Exit;
 251
 252           lru_node->key = key;
 253           error = clazz->init_element( lru, lru_node );
 254           if ( error )
 255           {
 256             FREE( lru_node );
 257             goto Exit;
 258           }
 259         }
 260
 261         found = lru_node;
 262         node  = (FT_ListNode)lru_node;
 263         FT_List_Insert( &lru->elements, node );
 264         lru->num_elements++;
 265       }
 266     }
 267
 268   Exit:
 269     *anode = found;
 270     return error;
 271   }
 272
 273
 274   FT_EXPORT_DEF( FT_Error )
 275   FT_Lru_Lookup( FT_Lru       lru,
 276                  FT_LruKey    key,
 277                  FT_Pointer  *anobject )
 278   {
 279     FT_Error    error;
 280     FT_LruNode  node;
 281
 282
 283     /* check for valid `lru' and `key' delayed to FT_Lru_Lookup_Node() */
 284
 285     if ( !anobject )
 286       return FTC_Err_Invalid_Argument;
 287
 288     *anobject = 0;
 289     error = FT_Lru_Lookup_Node( lru, key, &node );
 290     if ( !error )
 291       *anobject = node->root.data;
 292
 293     return error;
 294   }
 295
 296
 297   FT_EXPORT_DEF( void )
 298   FT_Lru_Remove_Node( FT_Lru      lru,
 299                       FT_LruNode  node )
 300   {
 301     if ( !lru || !node )
 302       return;
 303
 304     if ( lru->num_elements > 0 )
 305     {
 306       FT_List_Remove( &lru->elements, (FT_ListNode)node );
 307       lru->clazz->done_element( lru, node );
 308
 309       if ( lru->nodes )
 310         FT_List_Insert( &lru->free_nodes, (FT_ListNode)node );
 311       else
 312       {
 313         FT_Memory  memory = lru->memory;
 314
 315
 316         FREE( node );
 317       }
 318
 319       lru->num_elements--;
 320     }
 321   }
 322
 323
 324   FT_EXPORT_DEF( void )
 325   FT_Lru_Remove_Selection( FT_Lru           lru,
 326                            FT_Lru_Selector  selector,
 327                            FT_Pointer       data )
 328   {
 329     if ( !lru || !selector )
 330       return;
 331
 332     if ( lru->num_elements > 0 )
 333     {
 334       FT_ListNode  node = lru->elements.head;
 335       FT_ListNode  next;
 336
 337
 338       while ( node )
 339       {
 340         next = node->next;
 341         if ( selector( lru, (FT_LruNode)node, data ) )
 342         {
 343           /* remove this element from the list, and destroy it */
 344           FT_Lru_Remove_Node( lru, (FT_LruNode)node );
 345         }
 346         node = next;
 347       }
 348     }
 349   }
 350
 351
 352 /* END */