nostrdb

hash_table_impl_rh.h (11973B)

---

 /*
  * The MIT License (MIT)
  *
  * Copyright (c) 2015 Mikkel F. Jørgensen, dvide.com
  *
  * 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 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.
  */
 
 /* We use the same define for all implementations */
 #ifdef HASH_TABLE_IMPL
 #error "cannot have multiple implementations in same compilation unit"
 #endif
 #define HASH_TABLE_IMPL
 /* Robin Hood (with offset table) */
 #define HT_RH
 
 #if defined(_MSC_VER)
 #pragma warning(disable: 4127) /* conditional expression is constant */
 #endif
 
 #include <stdlib.h>
 #include <assert.h>
 
 /*
  * A variation of Robin Hashing:
  * We do not calcute distance from buckets, nor do we cache
  * hash keys. Instead we maintain a 7-bit offset that points
  * to where the first entry of a bucket is stored. In Robin Hood hashing
  * all entries conceptually chained to the same bucket are stored
  * immediately after each other in order of insertion. The offset of
  * the next bucket is naturally the end of the previous bucket, off by
  * one. This breaks down when the bucket offset is 0 and the bucket is
  * empty because it suggests there is an element. We cannot distinguish
  * between a single used and unused entry, except by looking at the
  * content or otherwise tag the information on. This is not a problem,
  * just a special case to deal with.
  *
  * The offsets are stored separately which might lead to more cache line
  * traffic, but the alternative is not very elegant - either wasting
  * space or trying to pack offsets on a per cache line basis. We only
  * need 8 bits for offsets. If the offset overflows, bit 7 will be set
  * which we can easily detect. During insertion, offsets are increated
  * on all affected buckets, and likewise decrement on remove. In
  * principle we can use bit parallel increments to update most offsets
  * in a single operation, but it is hardly worthwhile due to setup
  * cost. The approach bears some resemblance to hopscotch hashing which
  * uses local offsets for chaining, but we prefer the simpler Robin
  * Hood approach.
  *
  * If the offset overflows, the table is resized. We expect the packed
  * chains to behave like a special case of a hopscotch layout and
  * consequently have the same bounds, meaning we are unlikely to have
  * neither long offsets nor long chains if we resize below very full
  * so resizing on an offset of 128 should be ok.
  *
  * Our main motivation for this hashing is actually to get rid of
  * tombstones in quadruatic and linear probing. Avoiding tombstones
  * is much simpler when sorting chains Robin Hood style, and we avoid
  * checking for tombstones. We loose this benefit by having to inspect
  * offsets, but then also avoid checking keys before the chain, and
  * after because we can zero in on exactly the entries belonging to
  * bucket.
  *
  * Unlike traditional Robin Hood, we can find a missing key very quickly
  * without any heuristics: we only need to inspect exactly the number
  * of entries in the bucket (or at most 1 if the bucket is empty).
  *
  * Find operations start exactly at an entry with a matching hash key
  * unlike normal Robin Hood which must scan past a few earlier entries
  * on average, or guestimate where to start and seek both ways.
  *
  * We can also very quickly insert a key that is known to be unique
  * because we can add it directly to the end (but possibly requiring
  * a shift of later entries Robin Hood style).
  *
  * Whether these benefits outweighs the cost of a separate offset
  * lookup is unclear, but the reduced memory consumption certainly
  * allows for a lower load factor, which also helps a lot.
  *
  * Traditional Robin Hood Hashing actually permits a chain to become
  * very long. We do not permit this, in line with hopscotch hashing.
  * This is a drawback from a security perspective because worst case
  * this can trigger resizing ad infinitum iff the hash function can
  * be hacked or massive duplicate key insertion can be triggered. By
  * used the provided hash functions and seeding them randomly at
  * startup, and avoiding the multi key feature, it is very unlikely to
  * be a problem with what is known about hash table attacks so far.
  *
  * Values and keys are not stored, only item pointers. Custom macroes
  * or inline functions provide access to key data from the item. We
  * could add a separate value array and treat the item strictly as a
  * key, but we can have a smaller load factor instead, and can more
  * easily avoid copying complex key structures, such as start end
  * pointers to token data for parser.
  *
  * A typical hash table has: key pointer or key value, value pointer
  * or value, a cached hash key or bitmap (for Robin Hood or Hopscotch)
  * which on 64 bit platforms easily amounts to 20 bytes or more per
  * bucket. We use 9 bytes on 64 bit platforms and 5 bytes on 32 bit.
  * This gets us down to a max load of 0.5 and on average about 0.37.
  * This should make it very likely that the first bucket inspected is
  * a direct hit negating the benefit of caching hash keys. In addition,
  * when it is not a direct hit, we get pointers loaded in a cache line
  * to inspect, all known to have the same hash key.
  */
 
 int ht_init(hash_table_t *ht, size_t count)
 {
     size_t buckets = 4;
 
     if ((HT_LOAD_FACTOR_FRAC) > 256 || (HT_LOAD_FACTOR_FRAC) < 1) {
         /*
          * 101% will never terminate insertion.
          * 0% will never terminate resize.
          */
         HT_PANIC("robin hood hash table failed with impossible load factor");
         return -1;
     }
     while (count > buckets * (HT_LOAD_FACTOR_FRAC) / 256) {
         buckets *= 2;
     }
     ht->table = calloc(buckets, sizeof(ht_item_t));
     if (ht->table == 0) {
         return -1;
     }
     ht->offsets = calloc(buckets, sizeof(char));
     if (ht->offsets == 0) {
         free(ht->table);
         ht->table = 0;
         return -1;
     }
     ht->buckets = buckets;
     ht->count = 0;
     return 0;
 }
 
 int ht_resize(hash_table_t *ht, size_t count)
 {
     size_t i;
     hash_table_t ht2;
     ht_item_t *T = ht->table;
     ht_item_t item;
 
     if (count < ht->count) {
         count = ht->count;
     }
     if (ht_init(&ht2, count)) {
         return -1;
     }
     for (i = 0; i < ht->buckets; ++i) {
         item = T[i];
         if (item > (ht_item_t)1) {
             ht_insert(&ht2, ht_key(item), ht_key_len(item), item, ht_multi);
         }
     }
     ht_clear(ht);
     memcpy(ht, &ht2, sizeof(*ht));
     return 0;
 }
 
 ht_item_t ht_insert(hash_table_t *ht,
         const void *key, size_t len, ht_item_t item, int mode)
 {
     ht_item_t *T;
     size_t N, n, j, k, offset;
     ht_item_t new_item;
     char overflow = 0;
 
     new_item = item;
     if (ht->count >= ht->buckets * (HT_LOAD_FACTOR_FRAC) / 256) {
         if (ht_resize(ht, ht->count * 2)) {
             HT_PANIC("robin hood hash table failed to allocate memory during resize");
             return HT_NOMEM;
         }
     }
     T = ht->table;
     N = ht->buckets - 1;
     k = HT_HASH_FUNCTION(key, len) & N;
     offset = ht->offsets[k];
     j = (k + offset) & N;
     /*
      * T[j] == 0 is a special case because we cannot count
      * zero probe length, and because we should not increment
      * the offset at insertion point in this case.
      *
      * T[j] == 0 implies offset == 0, but this way we avoid
      * hitting memory that we don't need.
      */
     if (offset == 0 && T[j] == 0) {
         ++ht->count;
         T[j] = new_item;
         return 0;
     }
     n = ht->offsets[(k + 1) & N] - offset + 1;
     if (mode == ht_multi) {
         /* Don't search for match before inserting. */
         j = (j + n) & N;
         n = 0;
     }
     while (n--) {
         item = T[j];
         if (ht_match(key, len, item)) {
             if (mode == ht_replace) {
                 T[j] = new_item;
             }
             return item;
         }
         j = (j + 1) & N;
     }
     ++ht->count;
     while (k != j) {
         /* Only increment buckets after own bucket. */
         k = (k + 1) & N;
         overflow |= ++ht->offsets[k];
     }
     while ((item = T[j])) {
         T[j] = new_item;
         new_item = item;
         j = (j + 1) & N;
         overflow |= ++ht->offsets[j];
     }
     T[j] = new_item;
 
     if (overflow < 0) {
         /*
          * At least one offset overflowed, so we need to
          * resize the table.
          */
         if (ht->count * 10 < ht->buckets) {
             HT_PANIC("FATAL: hash table resize on low utilization would explode\n"\
                    "  possible collision DoS or bad hash function");
             return HT_NOMEM;
         }
         if (ht_resize(ht, ht->count * 2)) {
             HT_PANIC("FATAL: hash table resize failed and left hash table inconsistent");\
             /*
              * This renders the hash table in a bad state
              * because we have updated to an inconsistent
              * state.
              */
             return HT_NOMEM;
         }
     }
     return item;
 }
 
 ht_item_t ht_find(hash_table_t *ht, const void *key, size_t len)
 {
     ht_item_t *T = ht->table;
     size_t N, n, j, k, offset;
     ht_item_t item;
 
     if (T == 0) {
         return 0;
     }
     N = ht->buckets - 1;
     k = HT_HASH_FUNCTION(key, len) & N;
     offset = ht->offsets[k];
     j = (k + offset) & N;
     if (offset == 0 && T[j] == 0) {
         /* Special case because we cannot count zero probe length. */
         return 0;
     }
     n = ht->offsets[(k + 1) & N] - offset + 1;
     while (n--) {
         item = T[j];
         if (ht_match(key, len, item)) {
             return item;
         }
         j = (j + 1) & N;
     }
     return 0;
 }
 
 ht_item_t ht_remove(hash_table_t *ht, const void *key, size_t len)
 {
     ht_item_t *T = ht->table;
     size_t N, n, j, k, offset;
     ht_item_t item, *next_item;
 
     if (T == 0) {
         return 0;
     }
     N = ht->buckets - 1;
     k = HT_HASH_FUNCTION(key, len) & N;
     offset = ht->offsets[k];
     j = (k + offset) & N;
     if (offset == 0 && T[j] == 0) {
         return 0;
     }
     n = ht->offsets[(k + 1) & N] - offset + 1;
     while (n) {
         item = T[j];
         if (ht_match(key, len, item)) {
             break;
         }
         j = (j + 1) & N;
         --n;
     }
     if (n == 0) {
         return 0;
     }
     --ht->count;
     while (k != j) {
         /* Do not update the offset of the bucket that we own. */
         k = (k + 1) & N;
         --ht->offsets[k];
     }
     for (;;) {
         j = (j + 1) & N;
         if (ht->offsets[j] == 0) {
             T[k] = 0;
             return item;
         }
         --ht->offsets[j];
         T[k] = T[j];
         k = j;
     }
 }
 
 void ht_visit(hash_table_t *ht, ht_visitor_f *visitor, void *context)
 {
     size_t i;
     ht_item_t *T = ht->table;
     ht_item_t item;
 
     for (i = 0; i < ht->buckets; ++i) {
         item = T[i];
         if (item > (ht_item_t)1) {
             visitor(context, item);
         }
     }
 }
 
 void ht_clear(hash_table_t *ht)
 {
     if (ht->table) {
         free(ht->table);
     }
     if (ht->offsets) {
         free(ht->offsets);
     }
     memset(ht, 0, sizeof(*ht));
 }