src/cache/ftcmru.c

   1 /***************************************************************************/
   2 /*                                                                         */
   3 /*  ftcmru.c                                                               */
   4 /*                                                                         */
   5 /*    FreeType MRU support (body).                                         */
   6 /*                                                                         */
   7 /*  Copyright 2003, 2004, 2006, 2009 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 "ftcmru.h"
  22 #include FT_INTERNAL_OBJECTS_H
  23 #include FT_INTERNAL_DEBUG_H
  24
  25 #include "ftcerror.h"
  26
  27
  28   FT_LOCAL_DEF( void )
  29   FTC_MruNode_Prepend( FTC_MruNode  *plist,
  30                        FTC_MruNode   node )
  31   {
  32     FTC_MruNode  first = *plist;
  33
  34
  35     if ( first )
  36     {
  37       FTC_MruNode  last = first->prev;
  38
  39
  40 #ifdef FT_DEBUG_ERROR
  41       {
  42         FTC_MruNode  cnode = first;
  43
  44
  45         do
  46         {
  47           if ( cnode == node )
  48           {
  49             fprintf( stderr, "FTC_MruNode_Prepend: invalid action\n" );
  50             exit( 2 );
  51           }
  52           cnode = cnode->next;
  53
  54         } while ( cnode != first );
  55       }
  56 #endif
  57
  58       first->prev = node;
  59       last->next  = node;
  60       node->next  = first;
  61       node->prev  = last;
  62     }
  63     else
  64     {
  65       node->next = node;
  66       node->prev = node;
  67     }
  68     *plist = node;
  69   }
  70
  71
  72   FT_LOCAL_DEF( void )
  73   FTC_MruNode_Up( FTC_MruNode  *plist,
  74                   FTC_MruNode   node )
  75   {
  76     FTC_MruNode  first = *plist;
  77
  78
  79     FT_ASSERT( first != NULL );
  80
  81     if ( first != node )
  82     {
  83       FTC_MruNode  prev, next, last;
  84
  85
  86 #ifdef FT_DEBUG_ERROR
  87       {
  88         FTC_MruNode  cnode = first;
  89         do
  90         {
  91           if ( cnode == node )
  92             goto Ok;
  93           cnode = cnode->next;
  94
  95         } while ( cnode != first );
  96
  97         fprintf( stderr, "FTC_MruNode_Up: invalid action\n" );
  98         exit( 2 );
  99       Ok:
 100       }
 101 #endif
 102       prev = node->prev;
 103       next = node->next;
 104
 105       prev->next = next;
 106       next->prev = prev;
 107
 108       last = first->prev;
 109
 110       last->next  = node;
 111       first->prev = node;
 112
 113       node->next = first;
 114       node->prev = last;
 115
 116       *plist = node;
 117     }
 118   }
 119
 120
 121   FT_LOCAL_DEF( void )
 122   FTC_MruNode_Remove( FTC_MruNode  *plist,
 123                       FTC_MruNode   node )
 124   {
 125     FTC_MruNode  first = *plist;
 126     FTC_MruNode  prev, next;
 127
 128
 129     FT_ASSERT( first != NULL );
 130
 131 #ifdef FT_DEBUG_ERROR
 132       {
 133         FTC_MruNode  cnode = first;
 134
 135
 136         do
 137         {
 138           if ( cnode == node )
 139             goto Ok;
 140           cnode = cnode->next;
 141
 142         } while ( cnode != first );
 143
 144         fprintf( stderr, "FTC_MruNode_Remove: invalid action\n" );
 145         exit( 2 );
 146       Ok:
 147       }
 148 #endif
 149
 150     prev = node->prev;
 151     next = node->next;
 152
 153     prev->next = next;
 154     next->prev = prev;
 155
 156     if ( node == next )
 157     {
 158       FT_ASSERT( first == node );
 159       FT_ASSERT( prev  == node );
 160
 161       *plist = NULL;
 162     }
 163     else if ( node == first )
 164       *plist = next;
 165   }
 166
 167
 168   FT_LOCAL_DEF( void )
 169   FTC_MruList_Init( FTC_MruList       list,
 170                     FTC_MruListClass  clazz,
 171                     FT_UInt           max_nodes,
 172                     FT_Pointer        data,
 173                     FT_Memory         memory )
 174   {
 175     list->num_nodes = 0;
 176     list->max_nodes = max_nodes;
 177     list->nodes     = NULL;
 178     list->clazz     = *clazz;
 179     list->data      = data;
 180     list->memory    = memory;
 181   }
 182
 183
 184   FT_LOCAL_DEF( void )
 185   FTC_MruList_Reset( FTC_MruList  list )
 186   {
 187     while ( list->nodes )
 188       FTC_MruList_Remove( list, list->nodes );
 189
 190     FT_ASSERT( list->num_nodes == 0 );
 191   }
 192
 193
 194   FT_LOCAL_DEF( void )
 195   FTC_MruList_Done( FTC_MruList  list )
 196   {
 197     FTC_MruList_Reset( list );
 198   }
 199
 200
 201 #ifndef FTC_INLINE
 202   FT_LOCAL_DEF( FTC_MruNode )
 203   FTC_MruList_Find( FTC_MruList  list,
 204                     FT_Pointer   key )
 205   {
 206     FTC_MruNode_CompareFunc  compare = list->clazz.node_compare;
 207     FTC_MruNode              first, node;
 208
 209
 210     first = list->nodes;
 211     node  = NULL;
 212
 213     if ( first )
 214     {
 215       node = first;
 216       do
 217       {
 218         if ( compare( node, key ) )
 219         {
 220           if ( node != first )
 221             FTC_MruNode_Up( &list->nodes, node );
 222
 223           return node;
 224         }
 225
 226         node = node->next;
 227
 228       } while ( node != first);
 229     }
 230
 231     return NULL;
 232   }
 233 #endif
 234
 235   FT_LOCAL_DEF( FT_Error )
 236   FTC_MruList_New( FTC_MruList   list,
 237                    FT_Pointer    key,
 238                    FTC_MruNode  *anode )
 239   {
 240     FT_Error     error;
 241     FTC_MruNode  node = NULL;
 242     FT_Memory    memory = list->memory;
 243
 244
 245     if ( list->num_nodes >= list->max_nodes && list->max_nodes > 0 )
 246     {
 247       node = list->nodes->prev;
 248
 249       FT_ASSERT( node );
 250
 251       if ( list->clazz.node_reset )
 252       {
 253         FTC_MruNode_Up( &list->nodes, node );
 254
 255         error = list->clazz.node_reset( node, key, list->data );
 256         if ( !error )
 257           goto Exit;
 258       }
 259
 260       FTC_MruNode_Remove( &list->nodes, node );
 261       list->num_nodes--;
 262
 263       if ( list->clazz.node_done )
 264         list->clazz.node_done( node, list->data );
 265     }
 266     else if ( FT_ALLOC( node, list->clazz.node_size ) )
 267       goto Exit;
 268
 269     error = list->clazz.node_init( node, key, list->data );
 270     if ( error )
 271       goto Fail;
 272
 273     FTC_MruNode_Prepend( &list->nodes, node );
 274     list->num_nodes++;
 275
 276   Exit:
 277     *anode = node;
 278     return error;
 279
 280   Fail:
 281     if ( list->clazz.node_done )
 282       list->clazz.node_done( node, list->data );
 283
 284     FT_FREE( node );
 285     goto Exit;
 286   }
 287
 288
 289 #ifndef FTC_INLINE
 290   FT_LOCAL_DEF( FT_Error )
 291   FTC_MruList_Lookup( FTC_MruList   list,
 292                       FT_Pointer    key,
 293                       FTC_MruNode  *anode )
 294   {
 295     FTC_MruNode  node;
 296
 297
 298     node = FTC_MruList_Find( list, key );
 299     if ( node == NULL )
 300       return FTC_MruList_New( list, key, anode );
 301
 302     *anode = node;
 303     return 0;
 304   }
 305 #endif /* FTC_INLINE */
 306
 307   FT_LOCAL_DEF( void )
 308   FTC_MruList_Remove( FTC_MruList  list,
 309                       FTC_MruNode  node )
 310   {
 311     FTC_MruNode_Remove( &list->nodes, node );
 312     list->num_nodes--;
 313
 314     {
 315       FT_Memory  memory = list->memory;
 316
 317
 318       if ( list->clazz.node_done )
 319         list->clazz.node_done( node, list->data );
 320
 321       FT_FREE( node );
 322     }
 323   }
 324
 325
 326   FT_LOCAL_DEF( void )
 327   FTC_MruList_RemoveSelection( FTC_MruList              list,
 328                                FTC_MruNode_CompareFunc  selection,
 329                                FT_Pointer               key )
 330   {
 331     FTC_MruNode  first, node, next;
 332
 333
 334     first = list->nodes;
 335     while ( first && ( selection == NULL || selection( first, key ) ) )
 336     {
 337       FTC_MruList_Remove( list, first );
 338       first = list->nodes;
 339     }
 340
 341     if ( first )
 342     {
 343       node = first->next;
 344       while ( node != first )
 345       {
 346         next = node->next;
 347
 348         if ( selection( node, key ) )
 349           FTC_MruList_Remove( list, node );
 350
 351         node = next;
 352       }
 353     }
 354   }
 355
 356
 357 /* END */