src/cache/ftccache.c

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