From 0e3ef580b5d265ee59d50d35053e989b8c4277c2 Mon Sep 17 00:00:00 2001 From: David Robillard Date: Wed, 28 Sep 2011 17:41:06 +0000 Subject: Add ZixHash git-svn-id: http://svn.drobilla.net/zix/trunk@39 df6676b4-ccc9-40e5-b5d6-7c4628a128e3 --- src/hash.c | 226 +++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++ 1 file changed, 226 insertions(+) create mode 100644 src/hash.c (limited to 'src') diff --git a/src/hash.c b/src/hash.c new file mode 100644 index 0000000..c267757 --- /dev/null +++ b/src/hash.c @@ -0,0 +1,226 @@ +/* + Copyright 2011 David Robillard + + 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 +#include +#include + +#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 = 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); + } + } +} + -- cgit v1.2.1