From eb5b6261df49e8dea67e875f161a13eacc635863 Mon Sep 17 00:00:00 2001 From: Alexei Podtelezhnikov Date: Tue, 9 May 2023 06:49:37 -0400 Subject: [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; -- cgit v1.2.1