quickjs-tart

ares_htable.c (13140B)

---

 /* MIT License
  *
  * Copyright (c) 2023 Brad House
  *
  * Permission is hereby granted, free of charge, to any person obtaining a copy
  * of this software and associated documentation files (the "Software"), to deal
  * in the Software without restriction, including without limitation the rights
  * to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
  * copies of the Software, and to permit persons to whom the Software is
  * furnished to do so, subject to the following conditions:
  *
  * The above copyright notice and this permission notice (including the next
  * paragraph) shall be included in all copies or substantial portions of the
  * Software.
  *
  * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
  * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
  * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
  * AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
  * LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
  * OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE
  * SOFTWARE.
  *
  * SPDX-License-Identifier: MIT
  */
 #include "ares_private.h"
 #include "ares_llist.h"
 #include "ares_htable.h"
 
 #define ARES__HTABLE_MAX_BUCKETS    (1U << 24)
 #define ARES__HTABLE_MIN_BUCKETS    (1U << 4)
 #define ARES__HTABLE_EXPAND_PERCENT 75
 
 struct ares_htable {
   ares_htable_hashfunc_t    hash;
   ares_htable_bucket_key_t  bucket_key;
   ares_htable_bucket_free_t bucket_free;
   ares_htable_key_eq_t      key_eq;
   unsigned int              seed;
   unsigned int              size;
   size_t                    num_keys;
   size_t                    num_collisions;
   /* NOTE: if we converted buckets into ares_slist_t we could guarantee on
    *       hash collisions we would have O(log n) worst case insert and search
    *       performance.  (We'd also need to make key_eq into a key_cmp to
    *       support sort).  That said, risk with a random hash seed is near zero,
    *       and ares_slist_t is heavier weight, so I think using ares_llist_t
    *       is an overall win. */
   ares_llist_t            **buckets;
 };
 
 static unsigned int ares_htable_generate_seed(ares_htable_t *htable)
 {
 #ifdef FUZZING_BUILD_MODE_UNSAFE_FOR_PRODUCTION
   /* Seed needs to be static for fuzzing */
   return 0;
 #else
   unsigned int seed = 0;
   time_t       t    = time(NULL);
 
   /* Mix stack address, heap address, and time to generate a random seed, it
    * doesn't have to be super secure, just quick.  Likelihood of a hash
    * collision attack is very low with a small amount of effort */
   seed |= (unsigned int)((size_t)htable & 0xFFFFFFFF);
   seed |= (unsigned int)((size_t)&seed & 0xFFFFFFFF);
   seed |= (unsigned int)(((ares_uint64_t)t) & 0xFFFFFFFF);
   return seed;
 #endif
 }
 
 static void ares_htable_buckets_destroy(ares_llist_t **buckets,
                                         unsigned int   size,
                                         ares_bool_t    destroy_vals)
 {
   unsigned int i;
 
   if (buckets == NULL) {
     return;
   }
 
   for (i = 0; i < size; i++) {
     if (buckets[i] == NULL) {
       continue;
     }
 
     if (!destroy_vals) {
       ares_llist_replace_destructor(buckets[i], NULL);
     }
 
     ares_llist_destroy(buckets[i]);
   }
 
   ares_free(buckets);
 }
 
 void ares_htable_destroy(ares_htable_t *htable)
 {
   if (htable == NULL) {
     return;
   }
   ares_htable_buckets_destroy(htable->buckets, htable->size, ARES_TRUE);
   ares_free(htable);
 }
 
 ares_htable_t *ares_htable_create(ares_htable_hashfunc_t    hash_func,
                                   ares_htable_bucket_key_t  bucket_key,
                                   ares_htable_bucket_free_t bucket_free,
                                   ares_htable_key_eq_t      key_eq)
 {
   ares_htable_t *htable = NULL;
 
   if (hash_func == NULL || bucket_key == NULL || bucket_free == NULL ||
       key_eq == NULL) {
     goto fail;
   }
 
   htable = ares_malloc_zero(sizeof(*htable));
   if (htable == NULL) {
     goto fail;
   }
 
   htable->hash        = hash_func;
   htable->bucket_key  = bucket_key;
   htable->bucket_free = bucket_free;
   htable->key_eq      = key_eq;
   htable->seed        = ares_htable_generate_seed(htable);
   htable->size        = ARES__HTABLE_MIN_BUCKETS;
   htable->buckets = ares_malloc_zero(sizeof(*htable->buckets) * htable->size);
 
   if (htable->buckets == NULL) {
     goto fail;
   }
 
   return htable;
 
 fail:
   ares_htable_destroy(htable);
   return NULL;
 }
 
 const void **ares_htable_all_buckets(const ares_htable_t *htable, size_t *num)
 {
   const void **out = NULL;
   size_t       cnt = 0;
   size_t       i;
 
   if (htable == NULL || num == NULL) {
     return NULL; /* LCOV_EXCL_LINE */
   }
 
   *num = 0;
 
   out = ares_malloc_zero(sizeof(*out) * htable->num_keys);
   if (out == NULL) {
     return NULL; /* LCOV_EXCL_LINE */
   }
 
   for (i = 0; i < htable->size; i++) {
     ares_llist_node_t *node;
     for (node = ares_llist_node_first(htable->buckets[i]); node != NULL;
          node = ares_llist_node_next(node)) {
       out[cnt++] = ares_llist_node_val(node);
     }
   }
 
   *num = cnt;
   return out;
 }
 
 /*! Grabs the Hashtable index from the key and length.  The h index is
  *  the hash of the function reduced to the size of the bucket list.
  *  We are doing "hash & (size - 1)" since we are guaranteeing a power of
  *  2 for size. This is equivalent to "hash % size", but should be more
  * efficient */
 #define HASH_IDX(h, key) h->hash(key, h->seed) & (h->size - 1)
 
 static ares_llist_node_t *ares_htable_find(const ares_htable_t *htable,
                                            unsigned int idx, const void *key)
 {
   ares_llist_node_t *node = NULL;
 
   for (node = ares_llist_node_first(htable->buckets[idx]); node != NULL;
        node = ares_llist_node_next(node)) {
     if (htable->key_eq(key, htable->bucket_key(ares_llist_node_val(node)))) {
       break;
     }
   }
 
   return node;
 }
 
 static ares_bool_t ares_htable_expand(ares_htable_t *htable)
 {
   ares_llist_t **buckets  = NULL;
   unsigned int   old_size = htable->size;
   size_t         i;
   ares_llist_t **prealloc_llist     = NULL;
   size_t         prealloc_llist_len = 0;
   ares_bool_t    rv                 = ARES_FALSE;
 
   /* Not a failure, just won't expand */
   if (old_size == ARES__HTABLE_MAX_BUCKETS) {
     return ARES_TRUE; /* LCOV_EXCL_LINE */
   }
 
   htable->size <<= 1;
 
   /* We must pre-allocate all memory we'll need before moving entries to the
    * new hash array.  Otherwise if there's a memory allocation failure in the
    * middle, we wouldn't be able to recover. */
   buckets = ares_malloc_zero(sizeof(*buckets) * htable->size);
   if (buckets == NULL) {
     goto done; /* LCOV_EXCL_LINE */
   }
 
   /* The maximum number of new llists we'll need is the number of collisions
    * that were recorded */
   prealloc_llist_len = htable->num_collisions;
   if (prealloc_llist_len) {
     prealloc_llist =
       ares_malloc_zero(sizeof(*prealloc_llist) * prealloc_llist_len);
     if (prealloc_llist == NULL) {
       goto done; /* LCOV_EXCL_LINE */
     }
   }
   for (i = 0; i < prealloc_llist_len; i++) {
     prealloc_llist[i] = ares_llist_create(htable->bucket_free);
     if (prealloc_llist[i] == NULL) {
       goto done;
     }
   }
 
   /* Iterate across all buckets and move the entries to the new buckets */
   htable->num_collisions = 0;
   for (i = 0; i < old_size; i++) {
     ares_llist_node_t *node;
 
     /* Nothing in this bucket */
     if (htable->buckets[i] == NULL) {
       continue;
     }
 
     /* Fast path optimization (most likely case), there is likely only a single
      * entry in both the source and destination, check for this to confirm and
      * if so, just move the bucket over */
     if (ares_llist_len(htable->buckets[i]) == 1) {
       const void *val = ares_llist_first_val(htable->buckets[i]);
       size_t      idx = HASH_IDX(htable, htable->bucket_key(val));
 
       if (buckets[idx] == NULL) {
         /* Swap! */
         buckets[idx]       = htable->buckets[i];
         htable->buckets[i] = NULL;
         continue;
       }
     }
 
     /* Slow path, collisions */
     while ((node = ares_llist_node_first(htable->buckets[i])) != NULL) {
       const void *val = ares_llist_node_val(node);
       size_t      idx = HASH_IDX(htable, htable->bucket_key(val));
 
       /* Try fast path again as maybe we popped one collision off and the
        * next we can reuse the llist parent */
       if (buckets[idx] == NULL && ares_llist_len(htable->buckets[i]) == 1) {
         /* Swap! */
         buckets[idx]       = htable->buckets[i];
         htable->buckets[i] = NULL;
         break;
       }
 
       /* Grab one off our preallocated list */
       if (buckets[idx] == NULL) {
         /* Silence static analysis, this isn't possible but it doesn't know */
         if (prealloc_llist == NULL || prealloc_llist_len == 0) {
           goto done; /* LCOV_EXCL_LINE */
         }
         buckets[idx] = prealloc_llist[prealloc_llist_len - 1];
         prealloc_llist_len--;
       } else {
         /* Collision occurred since the bucket wasn't empty */
         htable->num_collisions++;
       }
 
       ares_llist_node_mvparent_first(node, buckets[idx]);
     }
 
     /* Abandoned bucket, destroy */
     if (htable->buckets[i] != NULL) {
       ares_llist_destroy(htable->buckets[i]);
       htable->buckets[i] = NULL;
     }
   }
 
   /* We have guaranteed all the buckets have either been moved or destroyed,
    * so we just call ares_free() on the array and swap out the pointer */
   ares_free(htable->buckets);
   htable->buckets = buckets;
   buckets         = NULL;
   rv              = ARES_TRUE;
 
 done:
   ares_free(buckets);
   /* destroy any unused preallocated buckets */
   ares_htable_buckets_destroy(prealloc_llist, (unsigned int)prealloc_llist_len,
                               ARES_FALSE);
 
   /* On failure, we need to restore the htable size */
   if (rv != ARES_TRUE) {
     htable->size = old_size; /* LCOV_EXCL_LINE */
   }
 
   return rv;
 }
 
 ares_bool_t ares_htable_insert(ares_htable_t *htable, void *bucket)
 {
   unsigned int       idx  = 0;
   ares_llist_node_t *node = NULL;
   const void        *key  = NULL;
 
   if (htable == NULL || bucket == NULL) {
     return ARES_FALSE;
   }
 
 
   key = htable->bucket_key(bucket);
   idx = HASH_IDX(htable, key);
 
   /* See if we have a matching bucket already, if so, replace it */
   node = ares_htable_find(htable, idx, key);
   if (node != NULL) {
     ares_llist_node_replace(node, bucket);
     return ARES_TRUE;
   }
 
   /* Check to see if we should rehash because likelihood of collisions has
    * increased beyond our threshold */
   if (htable->num_keys + 1 >
       (htable->size * ARES__HTABLE_EXPAND_PERCENT) / 100) {
     if (!ares_htable_expand(htable)) {
       return ARES_FALSE; /* LCOV_EXCL_LINE */
     }
     /* If we expanded, need to calculate a new index */
     idx = HASH_IDX(htable, key);
   }
 
   /* We lazily allocate the linked list */
   if (htable->buckets[idx] == NULL) {
     htable->buckets[idx] = ares_llist_create(htable->bucket_free);
     if (htable->buckets[idx] == NULL) {
       return ARES_FALSE;
     }
   }
 
   node = ares_llist_insert_first(htable->buckets[idx], bucket);
   if (node == NULL) {
     return ARES_FALSE;
   }
 
   /* Track collisions for rehash stability */
   if (ares_llist_len(htable->buckets[idx]) > 1) {
     htable->num_collisions++;
   }
 
   htable->num_keys++;
 
   return ARES_TRUE;
 }
 
 void *ares_htable_get(const ares_htable_t *htable, const void *key)
 {
   unsigned int idx;
 
   if (htable == NULL || key == NULL) {
     return NULL;
   }
 
   idx = HASH_IDX(htable, key);
 
   return ares_llist_node_val(ares_htable_find(htable, idx, key));
 }
 
 ares_bool_t ares_htable_remove(ares_htable_t *htable, const void *key)
 {
   ares_llist_node_t *node;
   unsigned int       idx;
 
   if (htable == NULL || key == NULL) {
     return ARES_FALSE;
   }
 
   idx  = HASH_IDX(htable, key);
   node = ares_htable_find(htable, idx, key);
   if (node == NULL) {
     return ARES_FALSE;
   }
 
   htable->num_keys--;
 
   /* Reduce collisions */
   if (ares_llist_len(ares_llist_node_parent(node)) > 1) {
     htable->num_collisions--;
   }
 
   ares_llist_node_destroy(node);
   return ARES_TRUE;
 }
 
 size_t ares_htable_num_keys(const ares_htable_t *htable)
 {
   if (htable == NULL) {
     return 0;
   }
   return htable->num_keys;
 }
 
 unsigned int ares_htable_hash_FNV1a(const unsigned char *key, size_t key_len,
                                     unsigned int seed)
 {
   unsigned int hv = seed ^ 2166136261U;
   size_t       i;
 
   for (i = 0; i < key_len; i++) {
     hv ^= (unsigned int)key[i];
     /* hv *= 16777619 (0x01000193) */
     hv += (hv << 1) + (hv << 4) + (hv << 7) + (hv << 8) + (hv << 24);
   }
 
   return hv;
 }
 
 /* Case insensitive version, meant for ASCII strings */
 unsigned int ares_htable_hash_FNV1a_casecmp(const unsigned char *key,
                                             size_t key_len, unsigned int seed)
 {
   unsigned int hv = seed ^ 2166136261U;
   size_t       i;
 
   for (i = 0; i < key_len; i++) {
     hv ^= (unsigned int)ares_tolower(key[i]);
     /* hv *= 16777619 (0x01000193) */
     hv += (hv << 1) + (hv << 4) + (hv << 7) + (hv << 8) + (hv << 24);
   }
 
   return hv;
 }