diff options
Diffstat (limited to 'src/hash.c')
| -rw-r--r-- | src/hash.c | 226 |
1 files changed, 0 insertions, 226 deletions
diff --git a/src/hash.c b/src/hash.c deleted file mode 100644 index f654e91..0000000 --- a/src/hash.c +++ /dev/null @@ -1,226 +0,0 @@ -/* - Copyright 2011 David Robillard <http://drobilla.net> - - Permission to use, copy, modify, and/or distribute this software for any - purpose with or without fee is hereby granted, provided that the above - copyright notice and this permission notice appear in all copies. - - THIS SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL WARRANTIES - WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF - MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR - ANY SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES - WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN - ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF - OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE. -*/ - -#include <assert.h> -#include <stdlib.h> -#include <string.h> - -#include "zix/hash.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 _Entry { - const void* key; ///< Hash key - void* data; ///< Value - struct _Entry* next; ///< Next entry in bucket - unsigned hash; ///< Non-modulo hash value (for cheap rehash) -} Entry; - -struct ZixHashImpl { - ZixHashFunc hash_func; - ZixEqualFunc key_equal_func; - Entry** buckets; - const unsigned* n_buckets; - unsigned count; -}; - -ZixHash* -zix_hash_new(ZixHashFunc hash_func, - ZixEqualFunc key_equal_func) - -{ - ZixHash* hash = (ZixHash*)malloc(sizeof(ZixHash)); - hash->hash_func = hash_func; - hash->key_equal_func = key_equal_func; - hash->count = 0; - hash->n_buckets = &sizes[0]; - hash->buckets = (Entry**)malloc(*hash->n_buckets * sizeof(Entry*)); - memset(hash->buckets, 0, *hash->n_buckets * sizeof(Entry*)); - - return hash; -} - -void -zix_hash_free(ZixHash* hash) -{ - for (unsigned b = 0; b < *hash->n_buckets; ++b) { - Entry* bucket = hash->buckets[b]; - for (Entry* e = bucket; e;) { - Entry* next = e->next; - free(e); - e = next; - } - } - - free(hash->buckets); - free(hash); -} - -unsigned -zix_string_hash(const void* key) -{ - // Trusty old DJB hash - const char* str = (const char*)key; - unsigned h = 5381; - for (const char* s = str; *s != '\0'; ++s) { - h = (h << 5) + h + *s; // h = h * 33 + c - } - return h; -} - -bool -zix_string_equal(const void* a, const void* b) -{ - return !strcmp((const char*)a, (const char*)b); -} - -static void -insert_entry(Entry** bucket, - Entry* entry) -{ - entry->next = *bucket; - *bucket = entry; -} - -static ZixStatus -rehash(ZixHash* hash, unsigned new_n_buckets) -{ - Entry** new_buckets = (Entry**)malloc(new_n_buckets * sizeof(Entry*)); - if (!new_buckets) { - return ZIX_STATUS_NO_MEM; - } - - memset(new_buckets, 0, new_n_buckets * sizeof(Entry*)); - - for (unsigned b = 0; b < *hash->n_buckets; ++b) { - for (Entry* e = hash->buckets[b]; e;) { - Entry* 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 Entry* -find_entry(const ZixHash* hash, - const void* key, - unsigned h) -{ - for (Entry* e = hash->buckets[h]; e; e = e->next) { - if (hash->key_equal_func(e->key, key)) { - return e; - } - } - - return NULL; -} - -void* -zix_hash_find(const ZixHash* hash, const void* key) -{ - const unsigned h = hash->hash_func(key) % *hash->n_buckets; - Entry* const entry = find_entry(hash, key, h); - return entry ? entry->data : 0; -} - -ZixStatus -zix_hash_insert(ZixHash* hash, const void* key, void* data) -{ - unsigned h_nomod = hash->hash_func(key); - unsigned h = h_nomod % *hash->n_buckets; - - Entry* elem = find_entry(hash, key, h); - if (elem) { - assert(elem->hash == h_nomod); - return ZIX_STATUS_EXISTS; - } - - elem = (Entry*)malloc(sizeof(Entry)); - if (!elem) { - return ZIX_STATUS_NO_MEM; - } - elem->key = key; - elem->data = data; - elem->next = NULL; - elem->hash = h_nomod; - 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; - return ZIX_STATUS_SUCCESS; -} - -ZixStatus -zix_hash_remove(ZixHash* hash, const void* key) -{ - unsigned h = hash->hash_func(key) % *hash->n_buckets; - - Entry** next_ptr = &hash->buckets[h]; - for (Entry* e = hash->buckets[h]; e; e = e->next) { - if (hash->key_equal_func(e->key, key)) { - *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; -} - -ZIX_API -void -zix_hash_foreach(const ZixHash* hash, - void (*f)(const void* key, void* value, void* user_data), - void* user_data) -{ - for (unsigned b = 0; b < *hash->n_buckets; ++b) { - Entry* bucket = hash->buckets[b]; - for (Entry* e = bucket; e; e = e->next) { - f(e->key, e->data, user_data); - } - } -} - |