freetype-commit
[Top][All Lists]
Advanced
[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]

[Git][freetype/freetype][ftc_resize] [cache] Revise the hash table accou

From: Alexei Podtelezhnikov (@apodtele)
Subject: [Git][freetype/freetype][ftc_resize] [cache] Revise the hash table accounting.
Date: Tue, 09 May 2023 04:27:34 +0000

Alexei Podtelezhnikov pushed to branch ftc_resize at FreeType / FreeType

Commits:

  • 69b2ec5e
    by Alexei Podtelezhnikov at 2023-05-09T00:11:19-04:00 
    [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.

2 changed files:

Changes:

  • src/cache/ftccache.c
    ... ... @@ -94,8 +94,8 @@
    94 94
    95 95
    96 96 
         idx = hash & cache->mask;
    97 
    -    if ( idx < cache->p )
    98 
    -      idx = hash & ( 2 * cache->mask + 1 );
    97 
    +    if ( idx >= cache->p )
    98 
    +      idx = hash & ( cache->mask >> 1 );
    99 99
    100 100 
         return cache->buckets + idx;
    101 101 
       }
    ... ... @@ -113,9 +113,9 @@
    113 113 
         for (;;)
    114 114 
         {
    115 115 
           FTC_Node  node, *pnode;
    116 
    -      FT_UFast  p     = cache->p;
    117 
    -      FT_UFast  mask  = cache->mask;
    118 
    -      FT_UFast  count = mask + p + 1;    /* number of buckets */
    116 
    +      FT_UFast  p    = cache->p;
    117 
    +      FT_UFast  size = cache->mask + 1;  /* available size */
    118 
    +      FT_UFast  half = size >> 1;
    119 119
    120 120
    121 121 
           /* do we need to expand the buckets array? */
    ... ... @@ -124,23 +124,24 @@
    124 124 
             FTC_Node  new_list = NULL;
    125 125
    126 126
    127 
    +        /* a single bucket to split */
    128 
    +        pnode = cache->buckets + p - half;
    129 
    +
    127 130 
             /* try to expand the buckets array _before_ splitting
    128 131 
              * the bucket lists
    129 132 
              */
    130 
    -        if ( p >= mask )
    133 
    +        if ( ++p >= size )
    131 134 
             {
    132 135 
               FT_Memory  memory = cache->memory;
    133 136 
               FT_Error   error;
    134 137
    135 138
    136 139 
               /* if we can't expand the array, leave immediately */
    137 
    -          if ( FT_RENEW_ARRAY( cache->buckets,
    138 
    -                               ( mask + 1 ) * 2, ( mask + 1 ) * 4 ) )
    140 
    +          if ( FT_RENEW_ARRAY( cache->buckets, size, size * 2 ) )
    139 141 
                 break;
    140 
    -        }
    141 142
    142 
    -        /* split a single bucket */
    143 
    -        pnode = cache->buckets + p;
    143 
    +          cache->mask = 2 * size - 1;
    144 
    +        }
    144 145
    145 146 
             for (;;)
    146 147 
             {
    ... ... @@ -148,7 +149,7 @@
    148 149 
               if ( !node )
    149 150 
                 break;
    150 151
    151 
    -          if ( node->hash & ( mask + 1 ) )
    152 
    +          if ( node->hash & half )
    152 153 
               {
    153 154 
                 *pnode     = node->link;
    154 155 
                 node->link = new_list;
    ... ... @@ -158,53 +159,38 @@
    158 159 
                 pnode = &node->link;
    159 160 
             }
    160 161
    161 
    -        cache->buckets[p + mask + 1] = new_list;
    162 
    +        cache->buckets[p - 1] = new_list;
    162 163
    163 164 
             cache->slack += FTC_HASH_MAX_LOAD;
    164 
    -
    165 
    -        if ( p >= mask )
    166 
    -        {
    167 
    -          cache->mask = 2 * mask + 1;
    168 
    -          cache->p    = 0;
    169 
    -        }
    170 
    -        else
    171 
    -          cache->p = p + 1;
    165 
    +        cache->p      = p;
    172 166 
           }
    173 167
    174 168 
           /* do we need to shrink the buckets array? */
    175 
    -      else if ( cache->slack > (FT_Long)count * FTC_HASH_SUB_LOAD )
    169 
    +      else if ( cache->slack > (FT_Long)p * FTC_HASH_SUB_LOAD )
    176 170 
           {
    177 
    -        FT_UFast   old_index = p + mask;
    178 
    -        FTC_Node*  pold;
    179 
    -
    180 
    -
    181 
    -        if ( old_index + 1 <= FTC_HASH_INITIAL_SIZE )
    171 
    +        if ( p <= FTC_HASH_INITIAL_SIZE )
    182 172 
               break;
    183 173
    184 
    -        if ( p == 0 )
    174 
    +        if ( p-- <= half )
    185 175 
             {
    186 176 
               FT_Memory  memory = cache->memory;
    187 177 
               FT_Error   error;
    188 178
    189 179
    190 180 
               /* if we can't shrink the array, leave immediately */
    191 
    -          if ( FT_QRENEW_ARRAY( cache->buckets,
    192 
    -                               ( mask + 1 ) * 2, mask + 1 ) )
    181 
    +          if ( FT_QRENEW_ARRAY( cache->buckets, size, half ) )
    193 182 
                 break;
    194 183
    195 
    -          cache->mask >>= 1;
    196 
    -          p             = cache->mask;
    184 
    +          cache->mask = half - 1;
    185 
    +          half      >>= 1;
    197 186 
             }
    198 
    -        else
    199 
    -          p--;
    200 187
    201 
    -        pnode = cache->buckets + p;
    188 
    +        pnode = cache->buckets + p - half;
    202 189 
             while ( *pnode )
    203 190 
               pnode = &(*pnode)->link;
    204 191
    205 
    -        pold   = cache->buckets + old_index;
    206 
    -        *pnode = *pold;
    207 
    -        *pold  = NULL;
    192 
    +        *pnode = cache->buckets[p];
    193 
    +        cache->buckets[p] = NULL;
    208 194
    209 195 
             cache->slack -= FTC_HASH_MAX_LOAD;
    210 196 
             cache->p      = p;
    ... ... @@ -336,8 +322,8 @@
    336 322 
         FT_Error   error;
    337 323
    338 324
    339 
    -    cache->p     = 0;
    340 
    -    cache->mask  = FTC_HASH_INITIAL_SIZE - 1;
    325 
    +    cache->p     = FTC_HASH_INITIAL_SIZE;
    326 
    +    cache->mask  = 2 * FTC_HASH_INITIAL_SIZE - 1;
    341 327 
         cache->slack = FTC_HASH_INITIAL_SIZE * FTC_HASH_MAX_LOAD;
    342 328
    343 329 
         FT_MEM_NEW_ARRAY( cache->buckets, FTC_HASH_INITIAL_SIZE * 2 );
    ... ... @@ -351,11 +337,9 @@
    351 337 
         if ( cache && cache->buckets )
    352 338 
         {
    353 339 
           FTC_Manager  manager = cache->manager;
    340 
    +      FT_UFast     count = cache->p;
    354 341 
           FT_UFast     i;
    355 
    -      FT_UFast     count;
    356 
    -
    357 342
    358 
    -      count = cache->p + cache->mask + 1;
    359 343
    360 344 
           for ( i = 0; i < count; i++ )
    361 345 
           {
    ... ... @@ -562,12 +546,12 @@
    562 546 
       FTC_Cache_RemoveFaceID( FTC_Cache   cache,
    563 547 
                               FTC_FaceID  face_id )
    564 548 
       {
    565 
    -    FT_UFast     i, count;
    566 549 
         FTC_Manager  manager = cache->manager;
    567 550 
         FTC_Node     frees   = NULL;
    551 
    +    FT_UFast     count   = cache->p;
    552 
    +    FT_UFast     i;
    568 553
    569 554
    570 
    -    count = cache->p + cache->mask + 1;
    571 555 
         for ( i = 0; i < count; i++ )
    572 556 
         {
    573 557 
           FTC_Node*  pnode = cache->buckets + i;

  • src/cache/ftccache.h
    ... ... @@ -73,10 +73,10 @@ FT_BEGIN_HEADER
    73 73 
     #define FTC_NODE_PREV( x )  FTC_NODE( (x)->mru.prev )
    74 74
    75 75 
     #ifdef FTC_INLINE
    76 
    -#define FTC_NODE_TOP_FOR_HASH( cache, hash )                      \
    77 
    -        ( ( cache )->buckets +                                    \
    78 
    -            ( ( ( ( hash ) &   ( cache )->mask ) < ( cache )->p ) \
    79 
    -              ? ( ( hash ) & ( ( cache )->mask * 2 + 1 ) )        \
    76 
    +#define FTC_NODE_TOP_FOR_HASH( cache, hash )                       \
    77 
    +        ( ( cache )->buckets +                                     \
    78 
    +            ( ( ( ( hash ) &   ( cache )->mask ) >= ( cache )->p ) \
    79 
    +              ? ( ( hash ) & ( ( cache )->mask >> 1 ) )            \
    80 80 
                   : ( ( hash ) &   ( cache )->mask ) ) )
    81 81 
     #else
    82 82 
       FT_LOCAL( FTC_Node* )
    ... ... @@ -142,8 +142,8 @@ FT_BEGIN_HEADER
    142 142 
       /* each cache really implements a dynamic hash table to manage its nodes */
    143 143 
       typedef struct  FTC_CacheRec_
    144 144 
       {
    145 
    -    FT_UFast           p;
    146 
    -    FT_UFast           mask;
    145 
    +    FT_UFast           p;           /* hash table counter     */
    146 
    +    FT_UFast           mask;        /* hash table index range */
    147 147 
         FT_Long            slack;
    148 148 
         FTC_Node*          buckets;
    149 149

    • —
    View it on GitLab.
    You're receiving this email because of your account on gitlab.freedesktop.org. Manage all notifications · Help

    reply via email to
    [Prev in Thread] Current Thread [Next in Thread]