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

[Werner Lemberg]

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

    [cache] Revise the 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, ftc_cache_init, FTC_Cache_Clear,
    FTC_Cache_RemoveFaceID): Updated accordingly.
---
 src/cache/ftccache.c | 74 ++++++++++++++++++++--------------------------------
 src/cache/ftccache.h | 12 ++++-----
 2 files changed, 35 insertions(+), 51 deletions(-)

diff --git a/src/cache/ftccache.c b/src/cache/ftccache.c
index ef7369d0a..7257d5529 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? */
@@ -124,23 +124,24 @@
         FTC_Node  new_list = NULL;
 
 
+        /* a single bucket to split */
+        pnode = cache->buckets + p - half;
+
         /* 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_RENEW_ARRAY( cache->buckets, size, size * 2 ) )
             break;
-        }
 
-        /* split a single bucket */
-        pnode = cache->buckets + p;
+          cache->mask = 2 * size - 1;
+        }
 
         for (;;)
         {
@@ -148,7 +149,7 @@
           if ( !node )
             break;
 
-          if ( node->hash & ( mask + 1 ) )
+          if ( node->hash & half )
           {
             *pnode     = node->link;
             node->link = new_list;
@@ -158,53 +159,38 @@
             pnode = &node->link;
         }
 
-        cache->buckets[p + mask + 1] = new_list;
+        cache->buckets[p - 1] = new_list;
 
         cache->slack += FTC_HASH_MAX_LOAD;
-
-        if ( p >= mask )
-        {
-          cache->mask = 2 * mask + 1;
-          cache->p    = 0;
-        }
-        else
-          cache->p = p + 1;
+        cache->p      = 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;
-
-
-        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;
+          half      >>= 1;
         }
-        else
-          p--;
 
-        pnode = cache->buckets + p;
+        pnode = cache->buckets + p - half;
         while ( *pnode )
           pnode = &(*pnode)->link;
 
-        pold   = cache->buckets + old_index;
-        *pnode = *pold;
-        *pold  = NULL;
+        *pnode = cache->buckets[p];
+        cache->buckets[p] = NULL;
 
         cache->slack -= FTC_HASH_MAX_LOAD;
         cache->p      = p;
@@ -336,8 +322,8 @@
     FT_Error   error;
 
 
-    cache->p     = 0;
-    cache->mask  = FTC_HASH_INITIAL_SIZE - 1;
+    cache->p     = FTC_HASH_INITIAL_SIZE;
+    cache->mask  = 2 * 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 );
@@ -351,11 +337,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 +546,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;