src/cache/ftccache.c

   1 /***************************************************************************/
   2 /*                                                                         */
   3 /*  ftccache.c                                                             */
   4 /*                                                                         */
   5 /*    The FreeType internal cache interface (body).                        */
   6 /*                                                                         */
   7 /*  Copyright 2000-2001, 2002, 2003, 2004, 2005, 2006, 2007, 2009, 2010 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 "ftcmanag.h"
  21 #include FT_INTERNAL_OBJECTS_H
  22 #include FT_INTERNAL_DEBUG_H
  23
  24 #include "ftccback.h"
  25 #include "ftcerror.h"
  26
  27 #undef  FT_COMPONENT
  28 #define FT_COMPONENT  trace_cache
  29
  30
  31 #define FTC_HASH_MAX_LOAD  2
  32 #define FTC_HASH_MIN_LOAD  1
  33 #define FTC_HASH_SUB_LOAD  ( FTC_HASH_MAX_LOAD - FTC_HASH_MIN_LOAD )
  34
  35 /* this one _must_ be a power of 2! */
  36 #define FTC_HASH_INITIAL_SIZE  8
  37
  38
  39   /*************************************************************************/
  40   /*************************************************************************/
  41   /*****                                                               *****/
  42   /*****                   CACHE NODE DEFINITIONS                      *****/
  43   /*****                                                               *****/
  44   /*************************************************************************/
  45   /*************************************************************************/
  46
  47   /* add a new node to the head of the manager's circular MRU list */
  48   static void
  49   ftc_node_mru_link( FTC_Node     node,
  50                      FTC_Manager  manager )
  51   {
  52     void  *nl = &manager->nodes_list;
  53
  54
  55     FTC_MruNode_Prepend( (FTC_MruNode*)nl,
  56                          (FTC_MruNode)node );
  57     manager->num_nodes++;
  58   }
  59
  60
  61   /* remove a node from the manager's MRU list */
  62   static void
  63   ftc_node_mru_unlink( FTC_Node     node,
  64                        FTC_Manager  manager )
  65   {
  66     void  *nl = &manager->nodes_list;
  67
  68
  69     FTC_MruNode_Remove( (FTC_MruNode*)nl,
  70                         (FTC_MruNode)node );
  71     manager->num_nodes--;
  72   }
  73
  74
  75 #ifndef FTC_INLINE
  76
  77   /* move a node to the head of the manager's MRU list */
  78   static void
  79   ftc_node_mru_up( FTC_Node     node,
  80                    FTC_Manager  manager )
  81   {
  82     FTC_MruNode_Up( (FTC_MruNode*)&manager->nodes_list,
  83                     (FTC_MruNode)node );
  84   }
  85
  86 #endif /* !FTC_INLINE */
  87
  88
  89   /* Note that this function cannot fail.  If we cannot re-size the
  90    * buckets array appropriately, we simply degrade the hash table's
  91    * performance!
  92    */
  93   static void
  94   ftc_cache_resize( FTC_Cache  cache )
  95   {
  96     for (;;)
  97     {
  98       FTC_Node  node, *pnode;
  99       FT_UFast  p      = cache->p;
 100       FT_UFast  mask   = cache->mask;
 101       FT_UFast  count  = mask + p + 1;    /* number of buckets */
 102
 103
 104       /* do we need to shrink the buckets array? */
 105       if ( cache->slack < 0 )
 106       {
 107         FTC_Node  new_list = NULL;
 108
 109
 110         /* try to expand the buckets array _before_ splitting
 111          * the bucket lists
 112          */
 113         if ( p >= mask )
 114         {
 115           FT_Memory  memory = cache->memory;
 116           FT_Error   error;
 117
 118
 119           /* if we can't expand the array, leave immediately */
 120           if ( FT_RENEW_ARRAY( cache->buckets, (mask+1)*2, (mask+1)*4 ) )
 121             break;
 122         }
 123
 124         /* split a single bucket */
 125         pnode = cache->buckets + p;
 126
 127         for (;;)
 128         {
 129           node = *pnode;
 130           if ( node == NULL )
 131             break;
 132
 133           if ( node->hash & ( mask + 1 ) )
 134           {
 135             *pnode     = node->link;
 136             node->link = new_list;
 137             new_list   = node;
 138           }
 139           else
 140             pnode = &node->link;
 141         }
 142
 143         cache->buckets[p + mask + 1] = new_list;
 144
 145         cache->slack += FTC_HASH_MAX_LOAD;
 146
 147         if ( p >= mask )
 148         {
 149           cache->mask = 2 * mask + 1;
 150           cache->p    = 0;
 151         }
 152         else
 153           cache->p = p + 1;
 154       }
 155
 156       /* do we need to expand the buckets array? */
 157       else if ( cache->slack > (FT_Long)count * FTC_HASH_SUB_LOAD )
 158       {
 159         FT_UFast   old_index = p + mask;
 160         FTC_Node*  pold;
 161
 162
 163         if ( old_index + 1 <= FTC_HASH_INITIAL_SIZE )
 164           break;
 165
 166         if ( p == 0 )
 167         {
 168           FT_Memory  memory = cache->memory;
 169           FT_Error   error;
 170
 171
 172           /* if we can't shrink the array, leave immediately */
 173           if ( FT_RENEW_ARRAY( cache->buckets,
 174                                ( mask + 1 ) * 2, mask + 1 ) )
 175             break;
 176
 177           cache->mask >>= 1;
 178           p             = cache->mask;
 179         }
 180         else
 181           p--;
 182
 183         pnode = cache->buckets + p;
 184         while ( *pnode )
 185           pnode = &(*pnode)->link;
 186
 187         pold   = cache->buckets + old_index;
 188         *pnode = *pold;
 189         *pold  = NULL;
 190
 191         cache->slack -= FTC_HASH_MAX_LOAD;
 192         cache->p      = p;
 193       }
 194       else /* the hash table is balanced */
 195         break;
 196     }
 197   }
 198
 199
 200   /* remove a node from its cache's hash table */
 201   static void
 202   ftc_node_hash_unlink( FTC_Node   node0,
 203                         FTC_Cache  cache )
 204   {
 205     FTC_Node  *pnode;
 206     FT_UInt    idx;
 207
 208
 209     idx = (FT_UInt)( node0->hash & cache->mask );
 210     if ( idx < cache->p )
 211       idx = (FT_UInt)( node0->hash & ( 2 * cache->mask + 1 ) );
 212
 213     pnode = cache->buckets + idx;
 214
 215     for (;;)
 216     {
 217       FTC_Node  node = *pnode;
 218
 219
 220       if ( node == NULL )
 221       {
 222         FT_TRACE0(( "ftc_node_hash_unlink: unknown node\n" ));
 223         return;
 224       }
 225
 226       if ( node == node0 )
 227         break;
 228
 229       pnode = &(*pnode)->link;
 230     }
 231
 232     *pnode      = node0->link;
 233     node0->link = NULL;
 234
 235     cache->slack++;
 236     ftc_cache_resize( cache );
 237   }
 238
 239
 240   /* add a node to the `top' of its cache's hash table */
 241   static void
 242   ftc_node_hash_link( FTC_Node   node,
 243                       FTC_Cache  cache )
 244   {
 245     FTC_Node  *pnode;
 246     FT_UInt    idx;
 247
 248
 249     idx = (FT_UInt)( node->hash & cache->mask );
 250     if ( idx < cache->p )
 251       idx = (FT_UInt)( node->hash & (2 * cache->mask + 1 ) );
 252
 253     pnode = cache->buckets + idx;
 254
 255     node->link = *pnode;
 256     *pnode     = node;
 257
 258     cache->slack--;
 259     ftc_cache_resize( cache );
 260   }
 261
 262
 263   /* remove a node from the cache manager */
 264 #ifdef FT_CONFIG_OPTION_OLD_INTERNALS
 265   FT_BASE_DEF( void )
 266 #else
 267   FT_LOCAL_DEF( void )
 268 #endif
 269   ftc_node_destroy( FTC_Node     node,
 270                     FTC_Manager  manager )
 271   {
 272     FTC_Cache  cache;
 273
 274
 275 #ifdef FT_DEBUG_ERROR
 276     /* find node's cache */
 277     if ( node->cache_index >= manager->num_caches )
 278     {
 279       FT_TRACE0(( "ftc_node_destroy: invalid node handle\n" ));
 280       return;
 281     }
 282 #endif
 283
 284     cache = manager->caches[node->cache_index];
 285
 286 #ifdef FT_DEBUG_ERROR
 287     if ( cache == NULL )
 288     {
 289       FT_TRACE0(( "ftc_node_destroy: invalid node handle\n" ));
 290       return;
 291     }
 292 #endif
 293
 294     manager->cur_weight -= cache->clazz.node_weight( node, cache );
 295
 296     /* remove node from mru list */
 297     ftc_node_mru_unlink( node, manager );
 298
 299     /* remove node from cache's hash table */
 300     ftc_node_hash_unlink( node, cache );
 301
 302     /* now finalize it */
 303     cache->clazz.node_free( node, cache );
 304
 305 #if 0
 306     /* check, just in case of general corruption :-) */
 307     if ( manager->num_nodes == 0 )
 308       FT_TRACE0(( "ftc_node_destroy: invalid cache node count (%d)\n",
 309                   manager->num_nodes ));
 310 #endif
 311   }
 312
 313
 314   /*************************************************************************/
 315   /*************************************************************************/
 316   /*****                                                               *****/
 317   /*****                    ABSTRACT CACHE CLASS                       *****/
 318   /*****                                                               *****/
 319   /*************************************************************************/
 320   /*************************************************************************/
 321
 322
 323   FT_LOCAL_DEF( FT_Error )
 324   FTC_Cache_Init( FTC_Cache  cache )
 325   {
 326     return ftc_cache_init( cache );
 327   }
 328
 329
 330   FT_LOCAL_DEF( FT_Error )
 331   ftc_cache_init( FTC_Cache  cache )
 332   {
 333     FT_Memory  memory = cache->memory;
 334     FT_Error   error;
 335
 336
 337     cache->p     = 0;
 338     cache->mask  = FTC_HASH_INITIAL_SIZE - 1;
 339     cache->slack = FTC_HASH_INITIAL_SIZE * FTC_HASH_MAX_LOAD;
 340
 341     (void)FT_NEW_ARRAY( cache->buckets, FTC_HASH_INITIAL_SIZE * 2 );
 342     return error;
 343   }
 344
 345
 346   static void
 347   FTC_Cache_Clear( FTC_Cache  cache )
 348   {
 349     if ( cache && cache->buckets )
 350     {
 351       FTC_Manager  manager = cache->manager;
 352       FT_UFast     i;
 353       FT_UFast     count;
 354
 355
 356       count = cache->p + cache->mask + 1;
 357
 358       for ( i = 0; i < count; i++ )
 359       {
 360         FTC_Node  *pnode = cache->buckets + i, next, node = *pnode;
 361
 362
 363         while ( node )
 364         {
 365           next        = node->link;
 366           node->link  = NULL;
 367
 368           /* remove node from mru list */
 369           ftc_node_mru_unlink( node, manager );
 370
 371           /* now finalize it */
 372           manager->cur_weight -= cache->clazz.node_weight( node, cache );
 373
 374           cache->clazz.node_free( node, cache );
 375           node = next;
 376         }
 377         cache->buckets[i] = NULL;
 378       }
 379       ftc_cache_resize( cache );
 380     }
 381   }
 382
 383
 384   FT_LOCAL_DEF( void )
 385   ftc_cache_done( FTC_Cache  cache )
 386   {
 387     if ( cache->memory )
 388     {
 389       FT_Memory  memory = cache->memory;
 390
 391
 392       FTC_Cache_Clear( cache );
 393
 394       FT_FREE( cache->buckets );
 395       cache->mask  = 0;
 396       cache->p     = 0;
 397       cache->slack = 0;
 398
 399       cache->memory = NULL;
 400     }
 401   }
 402
 403
 404   FT_LOCAL_DEF( void )
 405   FTC_Cache_Done( FTC_Cache  cache )
 406   {
 407     ftc_cache_done( cache );
 408   }
 409
 410
 411   static void
 412   ftc_cache_add( FTC_Cache  cache,
 413                  FT_UInt32  hash,
 414                  FTC_Node   node )
 415   {
 416     node->hash = hash;
 417     node->cache_index = (FT_UInt16) cache->index;
 418     node->ref_count   = 0;
 419
 420     ftc_node_hash_link( node, cache );
 421     ftc_node_mru_link( node, cache->manager );
 422
 423     {
 424       FTC_Manager  manager = cache->manager;
 425
 426
 427       manager->cur_weight += cache->clazz.node_weight( node, cache );
 428
 429       if ( manager->cur_weight >= manager->max_weight )
 430       {
 431         node->ref_count++;
 432         FTC_Manager_Compress( manager );
 433         node->ref_count--;
 434       }
 435     }
 436   }
 437
 438
 439   FT_LOCAL_DEF( FT_Error )
 440   FTC_Cache_NewNode( FTC_Cache   cache,
 441                      FT_UInt32   hash,
 442                      FT_Pointer  query,
 443                      FTC_Node   *anode )
 444   {
 445     FT_Error  error;
 446     FTC_Node  node;
 447
 448
 449     /*
 450      * We use the FTC_CACHE_TRYLOOP macros to support out-of-memory
 451      * errors (OOM) correctly, i.e., by flushing the cache progressively
 452      * in order to make more room.
 453      */
 454
 455     FTC_CACHE_TRYLOOP( cache )
 456     {
 457       error = cache->clazz.node_new( &node, query, cache );
 458     }
 459     FTC_CACHE_TRYLOOP_END();
 460
 461     if ( error )
 462       node = NULL;
 463     else
 464     {
 465      /* don't assume that the cache has the same number of buckets, since
 466       * our allocation request might have triggered global cache flushing
 467       */
 468       ftc_cache_add( cache, hash, node );
 469     }
 470
 471     *anode = node;
 472     return error;
 473   }
 474
 475
 476 #ifndef FTC_INLINE
 477
 478   FT_LOCAL_DEF( FT_Error )
 479   FTC_Cache_Lookup( FTC_Cache   cache,
 480                     FT_UInt32   hash,
 481                     FT_Pointer  query,
 482                     FTC_Node   *anode )
 483   {
 484     FT_UFast   idx;
 485     FTC_Node*  bucket;
 486     FTC_Node*  pnode;
 487     FTC_Node   node;
 488     FT_Error   error = FTC_Err_Ok;
 489
 490     FTC_Node_CompareFunc  compare = cache->clazz.node_compare;
 491
 492
 493     if ( cache == NULL || anode == NULL )
 494       return FTC_Err_Invalid_Argument;
 495
 496     idx = hash & cache->mask;
 497     if ( idx < cache->p )
 498       idx = hash & ( cache->mask * 2 + 1 );
 499
 500     bucket = cache->buckets + idx;
 501     pnode  = bucket;
 502     for (;;)
 503     {
 504       node = *pnode;
 505       if ( node == NULL )
 506         goto NewNode;
 507
 508       if ( node->hash == hash && compare( node, query, cache ) )
 509         break;
 510
 511       pnode = &node->link;
 512     }
 513
 514     if ( node != *bucket )
 515     {
 516       *pnode     = node->link;
 517       node->link = *bucket;
 518       *bucket    = node;
 519     }
 520
 521     /* move to head of MRU list */
 522     {
 523       FTC_Manager  manager = cache->manager;
 524
 525
 526       if ( node != manager->nodes_list )
 527         ftc_node_mru_up( node, manager );
 528     }
 529     *anode = node;
 530     return error;
 531
 532   NewNode:
 533     return FTC_Cache_NewNode( cache, hash, query, anode );
 534   }
 535
 536 #endif /* !FTC_INLINE */
 537
 538
 539   FT_LOCAL_DEF( void )
 540   FTC_Cache_RemoveFaceID( FTC_Cache   cache,
 541                           FTC_FaceID  face_id )
 542   {
 543     FT_UFast     i, count;
 544     FTC_Manager  manager = cache->manager;
 545     FTC_Node     frees   = NULL;
 546
 547
 548     count = cache->p + cache->mask;
 549     for ( i = 0; i < count; i++ )
 550     {
 551       FTC_Node*  bucket = cache->buckets + i;
 552       FTC_Node*  pnode  = bucket;
 553
 554
 555       for ( ;; )
 556       {
 557         FTC_Node  node = *pnode;
 558
 559
 560         if ( node == NULL )
 561           break;
 562
 563         if ( cache->clazz.node_remove_faceid( node, face_id, cache ) )
 564         {
 565           *pnode     = node->link;
 566           node->link = frees;
 567           frees      = node;
 568         }
 569         else
 570           pnode = &node->link;
 571       }
 572     }
 573
 574     /* remove all nodes in the free list */
 575     while ( frees )
 576     {
 577       FTC_Node  node;
 578
 579
 580       node  = frees;
 581       frees = node->link;
 582
 583       manager->cur_weight -= cache->clazz.node_weight( node, cache );
 584       ftc_node_mru_unlink( node, manager );
 585
 586       cache->clazz.node_free( node, cache );
 587
 588       cache->slack++;
 589     }
 590
 591     ftc_cache_resize( cache );
 592   }
 593
 594
 595 /* END */