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