misc/libfreetype/src/cache/ftccache.c
changeset 9372 915436ff64ab
parent 9371 f3840de881bd
child 9373 b769a8e38cbd
equal deleted inserted replaced
9371:f3840de881bd 9372:915436ff64ab
     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 */