[freetype2] ftc_resize af7a92d03: [cache] Revise the dynamic hash table accounting.

[Werner Lemberg]

branch: ftc_resize
commit af7a92d03ba1daf16ec50d5bff78af2fc738da68
Author: Alexei Podtelezhnikov <apodtele@gmail.com>
Commit: Alexei Podtelezhnikov <apodtele@gmail.com>

    [cache] Revise the dynamic hash table accounting.
    
    Instead of counting entries relative to the middle of the hash table,
    this switches to the absolute counter with the full index range mask.
    As a result, some calculations become a bit simpler.
    
    * src/cache/ftccache.h (FTC_NODE_TOP_FOR_HASH): Revised.
    * src/cache/ftccache.c (ftc_get_top_node_for_hash): Ditto.
    (ftc_cache_resize): Simplify the flow.
    (ftc_cache_init): Stop over-allocating initially.
    (FTC_Cache_Clear, FTC_Cache_RemoveFaceID): Updated accordingly.
---
 src/cache/ftccache.c | 76 ++++++++++++++++++++++++----------------------------
 src/cache/ftccache.h | 12 ++++-----
 2 files changed, 41 insertions(+), 47 deletions(-)

diff --git a/src/cache/ftccache.c b/src/cache/ftccache.c
index ef7369d0a..e77c1468f 100644
--- a/src/cache/ftccache.c
+++ b/src/cache/ftccache.c
@@ -94,8 +94,8 @@
 
 
     idx = hash & cache->mask;
-    if ( idx < cache->p )
-      idx = hash & ( 2 * cache->mask + 1 );
+    if ( idx >= cache->p )
+      idx = hash & ( cache->mask >> 1 );
 
     return cache->buckets + idx;
   }
@@ -113,9 +113,9 @@
     for (;;)
     {
       FTC_Node  node, *pnode;
-      FT_UFast  p     = cache->p;
-      FT_UFast  mask  = cache->mask;
-      FT_UFast  count = mask + p + 1;    /* number of buckets */
+      FT_UFast  p    = cache->p;
+      FT_UFast  size = cache->mask + 1;  /* available size */
+      FT_UFast  half = size >> 1;
 
 
       /* do we need to expand the buckets array? */
@@ -127,20 +127,22 @@
         /* try to expand the buckets array _before_ splitting
          * the bucket lists
          */
-        if ( p >= mask )
+        if ( p == size )
         {
           FT_Memory  memory = cache->memory;
           FT_Error   error;
 
 
           /* if we can't expand the array, leave immediately */
-          if ( FT_RENEW_ARRAY( cache->buckets,
-                               ( mask + 1 ) * 2, ( mask + 1 ) * 4 ) )
+          if ( FT_QRENEW_ARRAY( cache->buckets, size, size * 2 ) )
             break;
+
+          cache->mask = 2 * size - 1;
+          half        = size;
         }
 
-        /* split a single bucket */
-        pnode = cache->buckets + p;
+        /* the bucket to split */
+        pnode = cache->buckets + p - half;
 
         for (;;)
         {
@@ -148,7 +150,7 @@
           if ( !node )
             break;
 
-          if ( node->hash & ( mask + 1 ) )
+          if ( node->hash & half )
           {
             *pnode     = node->link;
             node->link = new_list;
@@ -158,56 +160,50 @@
             pnode = &node->link;
         }
 
-        cache->buckets[p + mask + 1] = new_list;
+        cache->buckets[p] = new_list;
 
         cache->slack += FTC_HASH_MAX_LOAD;
+        cache->p      = p + 1;
 
-        if ( p >= mask )
-        {
-          cache->mask = 2 * mask + 1;
-          cache->p    = 0;
-        }
-        else
-          cache->p = p + 1;
+        FT_TRACE2(( "ftc_cache_resize: cache %u increased to %u hashes\n",
+                    cache->index, cache->p ));
       }
 
       /* do we need to shrink the buckets array? */
-      else if ( cache->slack > (FT_Long)count * FTC_HASH_SUB_LOAD )
+      else if ( cache->slack > (FT_Long)p * FTC_HASH_SUB_LOAD )
       {
-        FT_UFast   old_index = p + mask;
-        FTC_Node*  pold;
+        FTC_Node  old_list = cache->buckets[--p];
 
 
-        if ( old_index + 1 <= FTC_HASH_INITIAL_SIZE )
+        if ( p < FTC_HASH_INITIAL_SIZE )
           break;
 
-        if ( p == 0 )
+        if ( p == half )
         {
           FT_Memory  memory = cache->memory;
           FT_Error   error;
 
 
           /* if we can't shrink the array, leave immediately */
-          if ( FT_QRENEW_ARRAY( cache->buckets,
-                               ( mask + 1 ) * 2, mask + 1 ) )
+          if ( FT_QRENEW_ARRAY( cache->buckets, size, half ) )
             break;
 
-          cache->mask >>= 1;
-          p             = cache->mask;
+          cache->mask = half - 1;
         }
-        else
-          p--;
 
-        pnode = cache->buckets + p;
+        /* the bucket to merge */
+        pnode = cache->buckets + p - half;
+
         while ( *pnode )
           pnode = &(*pnode)->link;
 
-        pold   = cache->buckets + old_index;
-        *pnode = *pold;
-        *pold  = NULL;
+        *pnode = old_list;
 
         cache->slack -= FTC_HASH_MAX_LOAD;
         cache->p      = p;
+
+        FT_TRACE2(( "ftc_cache_resize: cache %u decreased to %u hashes\n",
+                    cache->index, cache->p ));
       }
 
       /* otherwise, the hash table is balanced */
@@ -336,11 +332,11 @@
     FT_Error   error;
 
 
-    cache->p     = 0;
+    cache->p     = FTC_HASH_INITIAL_SIZE;
     cache->mask  = FTC_HASH_INITIAL_SIZE - 1;
     cache->slack = FTC_HASH_INITIAL_SIZE * FTC_HASH_MAX_LOAD;
 
-    FT_MEM_NEW_ARRAY( cache->buckets, FTC_HASH_INITIAL_SIZE * 2 );
+    FT_MEM_NEW_ARRAY( cache->buckets, FTC_HASH_INITIAL_SIZE );
     return error;
   }
 
@@ -351,11 +347,9 @@
     if ( cache && cache->buckets )
     {
       FTC_Manager  manager = cache->manager;
+      FT_UFast     count   = cache->p;
       FT_UFast     i;
-      FT_UFast     count;
-
 
-      count = cache->p + cache->mask + 1;
 
       for ( i = 0; i < count; i++ )
       {
@@ -562,12 +556,12 @@
   FTC_Cache_RemoveFaceID( FTC_Cache   cache,
                           FTC_FaceID  face_id )
   {
-    FT_UFast     i, count;
     FTC_Manager  manager = cache->manager;
     FTC_Node     frees   = NULL;
+    FT_UFast     count   = cache->p;
+    FT_UFast     i;
 
 
-    count = cache->p + cache->mask + 1;
     for ( i = 0; i < count; i++ )
     {
       FTC_Node*  pnode = cache->buckets + i;
diff --git a/src/cache/ftccache.h b/src/cache/ftccache.h
index 23bcb6585..976d63e86 100644
--- a/src/cache/ftccache.h
+++ b/src/cache/ftccache.h
@@ -73,10 +73,10 @@ FT_BEGIN_HEADER
 #define FTC_NODE_PREV( x )  FTC_NODE( (x)->mru.prev )
 
 #ifdef FTC_INLINE
-#define FTC_NODE_TOP_FOR_HASH( cache, hash )                      \
-        ( ( cache )->buckets +                                    \
-            ( ( ( ( hash ) &   ( cache )->mask ) < ( cache )->p ) \
-              ? ( ( hash ) & ( ( cache )->mask * 2 + 1 ) )        \
+#define FTC_NODE_TOP_FOR_HASH( cache, hash )                       \
+        ( ( cache )->buckets +                                     \
+            ( ( ( ( hash ) &   ( cache )->mask ) >= ( cache )->p ) \
+              ? ( ( hash ) & ( ( cache )->mask >> 1 ) )            \
               : ( ( hash ) &   ( cache )->mask ) ) )
 #else
   FT_LOCAL( FTC_Node* )
@@ -142,8 +142,8 @@ FT_BEGIN_HEADER
   /* each cache really implements a dynamic hash table to manage its nodes */
   typedef struct  FTC_CacheRec_
   {
-    FT_UFast           p;
-    FT_UFast           mask;
+    FT_UFast           p;           /* hash table counter     */
+    FT_UFast           mask;        /* hash table index range */
     FT_Long            slack;
     FTC_Node*          buckets;