diff options
Diffstat (limited to 'src/zix/hash.c')
| -rw-r--r-- | src/zix/hash.c | 217 |
1 files changed, 0 insertions, 217 deletions
diff --git a/src/zix/hash.c b/src/zix/hash.c deleted file mode 100644 index 5952574..0000000 --- a/src/zix/hash.c +++ /dev/null @@ -1,217 +0,0 @@ -// Copyright 2011-2020 David Robillard <d@drobilla.net> -// SPDX-License-Identifier: ISC - -#include "zix/hash.h" - -#include <assert.h> -#include <stdlib.h> -#include <string.h> - -/** - Primes, each slightly less than twice its predecessor, and as far away - from powers of two as possible. -*/ -static const unsigned sizes[] = { - 53, 97, 193, 389, 769, 1543, 3079, - 6151, 12289, 24593, 49157, 98317, 196613, 393241, - 786433, 1572869, 3145739, 6291469, 12582917, 25165843, 50331653, - 100663319, 201326611, 402653189, 805306457, 1610612741, 0}; - -typedef struct ZixHashEntry { - struct ZixHashEntry* next; ///< Next entry in bucket - uint32_t hash; ///< Non-modulo hash value - // Value follows here (access with zix_hash_value) -} ZixHashEntry; - -struct ZixHashImpl { - ZixHashFunc hash_func; - ZixEqualFunc equal_func; - ZixHashEntry** buckets; - const unsigned* n_buckets; - size_t value_size; - unsigned count; -}; - -static inline void* -zix_hash_value(ZixHashEntry* entry) -{ - return entry + 1; -} - -ZixHash* -zix_hash_new(ZixHashFunc hash_func, ZixEqualFunc equal_func, size_t value_size) -{ - ZixHash* hash = (ZixHash*)malloc(sizeof(ZixHash)); - if (hash) { - hash->hash_func = hash_func; - hash->equal_func = equal_func; - hash->n_buckets = &sizes[0]; - hash->value_size = value_size; - hash->count = 0; - if (!(hash->buckets = - (ZixHashEntry**)calloc(*hash->n_buckets, sizeof(ZixHashEntry*)))) { - free(hash); - return NULL; - } - } - return hash; -} - -void -zix_hash_free(ZixHash* hash) -{ - if (!hash) { - return; - } - - for (unsigned b = 0; b < *hash->n_buckets; ++b) { - ZixHashEntry* bucket = hash->buckets[b]; - for (ZixHashEntry* e = bucket; e;) { - ZixHashEntry* next = e->next; - free(e); - e = next; - } - } - - free(hash->buckets); - free(hash); -} - -size_t -zix_hash_size(const ZixHash* hash) -{ - return hash->count; -} - -static inline void -insert_entry(ZixHashEntry** bucket, ZixHashEntry* entry) -{ - entry->next = *bucket; - *bucket = entry; -} - -static inline ZixStatus -rehash(ZixHash* hash, unsigned new_n_buckets) -{ - ZixHashEntry** new_buckets = - (ZixHashEntry**)calloc(new_n_buckets, sizeof(ZixHashEntry*)); - if (!new_buckets) { - return ZIX_STATUS_NO_MEM; - } - - const unsigned old_n_buckets = *hash->n_buckets; - for (unsigned b = 0; b < old_n_buckets; ++b) { - for (ZixHashEntry* e = hash->buckets[b]; e;) { - ZixHashEntry* const next = e->next; - const unsigned h = e->hash % new_n_buckets; - insert_entry(&new_buckets[h], e); - e = next; - } - } - - free(hash->buckets); - hash->buckets = new_buckets; - - return ZIX_STATUS_SUCCESS; -} - -static inline ZixHashEntry* -find_entry(const ZixHash* hash, - const void* key, - const unsigned h, - const unsigned h_nomod) -{ - for (ZixHashEntry* e = hash->buckets[h]; e; e = e->next) { - if (e->hash == h_nomod && hash->equal_func(zix_hash_value(e), key)) { - return e; - } - } - return NULL; -} - -void* -zix_hash_find(const ZixHash* hash, const void* value) -{ - const unsigned h_nomod = hash->hash_func(value); - const unsigned h = h_nomod % *hash->n_buckets; - ZixHashEntry* const entry = find_entry(hash, value, h, h_nomod); - return entry ? zix_hash_value(entry) : 0; -} - -ZixStatus -zix_hash_insert(ZixHash* hash, const void* value, void** inserted) -{ - unsigned h_nomod = hash->hash_func(value); - unsigned h = h_nomod % *hash->n_buckets; - - ZixHashEntry* elem = find_entry(hash, value, h, h_nomod); - if (elem) { - assert(elem->hash == h_nomod); - if (inserted) { - *inserted = zix_hash_value(elem); - } - return ZIX_STATUS_EXISTS; - } - - elem = (ZixHashEntry*)malloc(sizeof(ZixHashEntry) + hash->value_size); - if (!elem) { - return ZIX_STATUS_NO_MEM; - } - elem->next = NULL; - elem->hash = h_nomod; - memcpy(elem + 1, value, hash->value_size); - - const unsigned next_n_buckets = *(hash->n_buckets + 1); - if (next_n_buckets != 0 && (hash->count + 1) >= next_n_buckets) { - if (!rehash(hash, next_n_buckets)) { - h = h_nomod % *(++hash->n_buckets); - } - } - - insert_entry(&hash->buckets[h], elem); - ++hash->count; - if (inserted) { - *inserted = zix_hash_value(elem); - } - return ZIX_STATUS_SUCCESS; -} - -ZixStatus -zix_hash_remove(ZixHash* hash, const void* value) -{ - const unsigned h_nomod = hash->hash_func(value); - const unsigned h = h_nomod % *hash->n_buckets; - - ZixHashEntry** next_ptr = &hash->buckets[h]; - for (ZixHashEntry* e = hash->buckets[h]; e; e = e->next) { - if (h_nomod == e->hash && hash->equal_func(zix_hash_value(e), value)) { - *next_ptr = e->next; - free(e); - return ZIX_STATUS_SUCCESS; - } - next_ptr = &e->next; - } - - if (hash->n_buckets != sizes) { - const unsigned prev_n_buckets = *(hash->n_buckets - 1); - if (hash->count - 1 <= prev_n_buckets) { - if (!rehash(hash, prev_n_buckets)) { - --hash->n_buckets; - } - } - } - - --hash->count; - return ZIX_STATUS_NOT_FOUND; -} - -void -zix_hash_foreach(ZixHash* hash, ZixHashVisitFunc f, void* user_data) -{ - for (unsigned b = 0; b < *hash->n_buckets; ++b) { - ZixHashEntry* bucket = hash->buckets[b]; - for (ZixHashEntry* e = bucket; e; e = e->next) { - f(zix_hash_value(e), user_data); - } - } -} |