source/modules/lilv/sord-0.16.0/src/zix/hash.c

   1 /*
   2   Copyright 2011-2014 David Robillard <http://drobilla.net>
   3
   4   Permission to use, copy, modify, and/or distribute this software for any
   5   purpose with or without fee is hereby granted, provided that the above
   6   copyright notice and this permission notice appear in all copies.
   7
   8   THIS SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL WARRANTIES
   9   WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF
  10   MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR
  11   ANY SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES
  12   WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN
  13   ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF
  14   OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE.
  15 */
  16
  17 #include <assert.h>
  18 #include <stdint.h>
  19 #include <stdlib.h>
  20 #include <string.h>
  21
  22 #include "zix/hash.h"
  23
  24 /**
  25    Primes, each slightly less than twice its predecessor, and as far away
  26    from powers of two as possible.
  27 */
  28 static const unsigned sizes[] = {
  29         53, 97, 193, 389, 769, 1543, 3079, 6151, 12289, 24593, 49157, 98317,
  30         196613, 393241, 786433, 1572869, 3145739, 6291469, 12582917, 25165843,
  31         50331653, 100663319, 201326611, 402653189, 805306457, 1610612741, 0
  32 };
  33
  34 typedef struct ZixHashEntry {
  35         struct ZixHashEntry* next;  ///< Next entry in bucket
  36         uint32_t             hash;  ///< Non-modulo hash value
  37         // Value follows here (access with zix_hash_value)
  38 } ZixHashEntry;
  39
  40 struct ZixHashImpl {
  41         ZixHashFunc     hash_func;
  42         ZixEqualFunc    equal_func;
  43         ZixHashEntry**  buckets;
  44         const unsigned* n_buckets;
  45         size_t          value_size;
  46         unsigned        count;
  47 };
  48
  49 static inline void*
  50 zix_hash_value(ZixHashEntry* entry)
  51 {
  52         return entry + 1;
  53 }
  54
  55 ZIX_API ZixHash*
  56 zix_hash_new(ZixHashFunc  hash_func,
  57              ZixEqualFunc equal_func,
  58              size_t       value_size)
  59 {
  60         ZixHash* hash = (ZixHash*)malloc(sizeof(ZixHash));
  61         if (hash) {
  62                 hash->hash_func  = hash_func;
  63                 hash->equal_func = equal_func;
  64                 hash->n_buckets  = &sizes[0];
  65                 hash->value_size = value_size;
  66                 hash->count      = 0;
  67                 if (!(hash->buckets = (ZixHashEntry**)calloc(*hash->n_buckets,
  68                                                              sizeof(ZixHashEntry*)))) {
  69                         free(hash);
  70                         return NULL;
  71                 }
  72         }
  73         return hash;
  74 }
  75
  76 ZIX_API void
  77 zix_hash_free(ZixHash* hash)
  78 {
  79         for (unsigned b = 0; b < *hash->n_buckets; ++b) {
  80                 ZixHashEntry* bucket = hash->buckets[b];
  81                 for (ZixHashEntry* e = bucket; e;) {
  82                         ZixHashEntry* next = e->next;
  83                         free(e);
  84                         e = next;
  85                 }
  86         }
  87
  88         free(hash->buckets);
  89         free(hash);
  90 }
  91
  92 ZIX_API size_t
  93 zix_hash_size(const ZixHash* hash)
  94 {
  95         return hash->count;
  96 }
  97
  98 static inline void
  99 insert_entry(ZixHashEntry** bucket, ZixHashEntry* entry)
 100 {
 101         entry->next = *bucket;
 102         *bucket     = entry;
 103 }
 104
 105 static inline ZixStatus
 106 rehash(ZixHash* hash, unsigned new_n_buckets)
 107 {
 108         ZixHashEntry** new_buckets = (ZixHashEntry**)calloc(
 109                 new_n_buckets, sizeof(ZixHashEntry*));
 110         if (!new_buckets) {
 111                 return ZIX_STATUS_NO_MEM;
 112         }
 113
 114         const unsigned old_n_buckets = *hash->n_buckets;
 115         for (unsigned b = 0; b < old_n_buckets; ++b) {
 116                 for (ZixHashEntry* e = hash->buckets[b]; e;) {
 117                         ZixHashEntry* const next = e->next;
 118                         const unsigned      h    = e->hash % new_n_buckets;
 119                         insert_entry(&new_buckets[h], e);
 120                         e = next;
 121                 }
 122         }
 123
 124         free(hash->buckets);
 125         hash->buckets = new_buckets;
 126
 127         return ZIX_STATUS_SUCCESS;
 128 }
 129
 130 static inline ZixHashEntry*
 131 find_entry(const ZixHash* hash,
 132            const void*    key,
 133            const unsigned h,
 134            const unsigned h_nomod)
 135 {
 136         for (ZixHashEntry* e = hash->buckets[h]; e; e = e->next) {
 137                 if (e->hash == h_nomod && hash->equal_func(zix_hash_value(e), key)) {
 138                         return e;
 139                 }
 140         }
 141         return NULL;
 142 }
 143
 144 ZIX_API const void*
 145 zix_hash_find(const ZixHash* hash, const void* value)
 146 {
 147         const unsigned h_nomod = hash->hash_func(value);
 148         const unsigned h       = h_nomod % *hash->n_buckets;
 149         ZixHashEntry* const entry = find_entry(hash, value, h, h_nomod);
 150         return entry ? zix_hash_value(entry) : 0;
 151 }
 152
 153 ZIX_API ZixStatus
 154 zix_hash_insert(ZixHash* hash, const void* value, const void** inserted)
 155 {
 156         unsigned h_nomod = hash->hash_func(value);
 157         unsigned h       = h_nomod % *hash->n_buckets;
 158
 159         ZixHashEntry* elem = find_entry(hash, value, h, h_nomod);
 160         if (elem) {
 161                 assert(elem->hash == h_nomod);
 162                 if (inserted) {
 163                         *inserted = zix_hash_value(elem);
 164                 }
 165                 return ZIX_STATUS_EXISTS;
 166         }
 167
 168         elem = (ZixHashEntry*)malloc(sizeof(ZixHashEntry) + hash->value_size);
 169         if (!elem) {
 170                 return ZIX_STATUS_NO_MEM;
 171         }
 172         elem->next = NULL;
 173         elem->hash = h_nomod;
 174         memcpy(elem + 1, value, hash->value_size);
 175
 176         const unsigned next_n_buckets = *(hash->n_buckets + 1);
 177         if (next_n_buckets != 0 && (hash->count + 1) >= next_n_buckets) {
 178                 if (!rehash(hash, next_n_buckets)) {
 179                         h = h_nomod % *(++hash->n_buckets);
 180                 }
 181         }
 182
 183         insert_entry(&hash->buckets[h], elem);
 184         ++hash->count;
 185         if (inserted) {
 186                 *inserted = zix_hash_value(elem);
 187         }
 188         return ZIX_STATUS_SUCCESS;
 189 }
 190
 191 ZIX_API ZixStatus
 192 zix_hash_remove(ZixHash* hash, const void* value)
 193 {
 194         const unsigned h_nomod = hash->hash_func(value);
 195         const unsigned h       = h_nomod % *hash->n_buckets;
 196
 197         ZixHashEntry** next_ptr = &hash->buckets[h];
 198         for (ZixHashEntry* e = hash->buckets[h]; e; e = e->next) {
 199                 if (h_nomod == e->hash &&
 200                         hash->equal_func(zix_hash_value(e), value)) {
 201                         *next_ptr = e->next;
 202                         free(e);
 203                         return ZIX_STATUS_SUCCESS;
 204                 }
 205                 next_ptr = &e->next;
 206         }
 207
 208         if (hash->n_buckets != sizes) {
 209                 const unsigned prev_n_buckets = *(hash->n_buckets - 1);
 210                 if (hash->count - 1 <= prev_n_buckets) {
 211                         if (!rehash(hash, prev_n_buckets)) {
 212                                 --hash->n_buckets;
 213                         }
 214                 }
 215         }
 216
 217         --hash->count;
 218         return ZIX_STATUS_NOT_FOUND;
 219 }
 220
 221 ZIX_API void
 222 zix_hash_foreach(ZixHash*         hash,
 223                  ZixHashVisitFunc f,
 224                  void*            user_data)
 225 {
 226         for (unsigned b = 0; b < *hash->n_buckets; ++b) {
 227                 ZixHashEntry* bucket = hash->buckets[b];
 228                 for (ZixHashEntry* e = bucket; e; e = e->next) {
 229                         f(zix_hash_value(e), user_data);
 230                 }
 231         }
 232 }