summaryrefslogtreecommitdiffstats
path: root/src/zix/hash.c
diff options
context:
space:
mode:
Diffstat (limited to 'src/zix/hash.c')
-rw-r--r--src/zix/hash.c117
1 files changed, 62 insertions, 55 deletions
diff --git a/src/zix/hash.c b/src/zix/hash.c
index aacf993..b24ee78 100644
--- a/src/zix/hash.c
+++ b/src/zix/hash.c
@@ -15,6 +15,7 @@
*/
#include <assert.h>
+#include <stdint.h>
#include <stdlib.h>
#include <string.h>
@@ -31,31 +32,39 @@ static const unsigned sizes[] = {
};
typedef struct ZixHashEntry {
- const void* key; ///< Hash key
- void* data; ///< Value
struct ZixHashEntry* next; ///< Next entry in bucket
- unsigned hash; ///< Non-modulo hash value (for cheap rehash)
+ uint32_t hash; ///< Non-modulo hash value
+ // Value follows here (access with zix_hash_value)
} ZixHashEntry;
struct ZixHashImpl {
ZixHashFunc hash_func;
- ZixEqualFunc key_equal_func;
+ ZixEqualFunc equal_func;
ZixHashEntry** buckets;
const unsigned* n_buckets;
+ size_t value_size;
unsigned count;
};
+static inline const void*
+zix_hash_value(const ZixHashEntry* entry)
+{
+ return entry + 1;
+}
+
ZIX_API ZixHash*
zix_hash_new(ZixHashFunc hash_func,
- ZixEqualFunc key_equal_func)
+ ZixEqualFunc equal_func,
+ size_t value_size)
{
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 = (ZixHashEntry**)calloc(*hash->n_buckets,
- sizeof(ZixHashEntry*));
+ hash->hash_func = hash_func;
+ hash->equal_func = equal_func;
+ hash->n_buckets = &sizes[0];
+ hash->value_size = value_size;
+ hash->count = 0;
+ hash->buckets = (ZixHashEntry**)calloc(*hash->n_buckets,
+ sizeof(ZixHashEntry*));
return hash;
}
@@ -75,41 +84,30 @@ zix_hash_free(ZixHash* hash)
free(hash);
}
-ZIX_API 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;
-}
-
-ZIX_API bool
-zix_string_equal(const void* a, const void* b)
+ZIX_API size_t
+zix_hash_size(const ZixHash* hash)
{
- return !strcmp((const char*)a, (const char*)b);
+ return hash->count;
}
-ZIX_PRIVATE void
-insert_entry(ZixHashEntry** bucket, ZixHashEntry* entry)
+static inline void
+insert_entry(ZixHashEntry** bucket, ZixHashEntry* entry)
{
entry->next = *bucket;
*bucket = entry;
}
-ZIX_PRIVATE ZixStatus
+static inline ZixStatus
rehash(ZixHash* hash, unsigned new_n_buckets)
{
- ZixHashEntry** new_buckets = (ZixHashEntry**)calloc(new_n_buckets,
- sizeof(ZixHashEntry*));
+ ZixHashEntry** new_buckets = (ZixHashEntry**)calloc(
+ new_n_buckets, sizeof(ZixHashEntry*));
if (!new_buckets) {
return ZIX_STATUS_NO_MEM;
}
- for (unsigned b = 0; b < *hash->n_buckets; ++b) {
+ 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;
@@ -124,48 +122,52 @@ rehash(ZixHash* hash, unsigned new_n_buckets)
return ZIX_STATUS_SUCCESS;
}
-ZIX_PRIVATE ZixHashEntry*
+static inline ZixHashEntry*
find_entry(const ZixHash* hash,
const void* key,
- unsigned h)
+ const unsigned h,
+ const unsigned h_nomod)
{
for (ZixHashEntry* e = hash->buckets[h]; e; e = e->next) {
- if (hash->key_equal_func(e->key, key)) {
+ if (e->hash == h_nomod && hash->equal_func(zix_hash_value(e), key)) {
return e;
}
}
-
return NULL;
}
-ZIX_API void*
-zix_hash_find(const ZixHash* hash, const void* key)
+ZIX_API const void*
+zix_hash_find(const ZixHash* hash, const void* value)
{
- const unsigned h = hash->hash_func(key) % *hash->n_buckets;
- ZixHashEntry* const entry = find_entry(hash, key, h);
- return entry ? entry->data : 0;
+ 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;
}
ZIX_API ZixStatus
-zix_hash_insert(ZixHash* hash, const void* key, void* data)
+zix_hash_insert(ZixHash* hash, const void* value, const void** inserted)
{
- unsigned h_nomod = hash->hash_func(key);
+ unsigned h_nomod = hash->hash_func(value);
unsigned h = h_nomod % *hash->n_buckets;
- ZixHashEntry* elem = find_entry(hash, key, h);
+ 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));
+ elem = (ZixHashEntry*)malloc(sizeof(ZixHashEntry) + hash->value_size);
if (!elem) {
return ZIX_STATUS_NO_MEM;
}
- elem->key = key;
- elem->data = data;
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)) {
@@ -175,17 +177,22 @@ zix_hash_insert(ZixHash* hash, const void* key, void* data)
insert_entry(&hash->buckets[h], elem);
++hash->count;
+ if (inserted) {
+ *inserted = zix_hash_value(elem);
+ }
return ZIX_STATUS_SUCCESS;
}
ZIX_API ZixStatus
-zix_hash_remove(ZixHash* hash, const void* key)
+zix_hash_remove(ZixHash* hash, const void* value)
{
- unsigned h = hash->hash_func(key) % *hash->n_buckets;
+ 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 (hash->key_equal_func(e->key, key)) {
+ if (h_nomod == e->hash &&
+ hash->equal_func(zix_hash_value(e), value)) {
*next_ptr = e->next;
free(e);
return ZIX_STATUS_SUCCESS;
@@ -207,14 +214,14 @@ zix_hash_remove(ZixHash* hash, const void* key)
}
ZIX_API void
-zix_hash_foreach(const ZixHash* hash,
- void (*f)(const void* key, void* value, void* user_data),
- void* user_data)
+zix_hash_foreach(const 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(e->key, e->data, user_data);
+ for (const ZixHashEntry* e = bucket; e; e = e->next) {
+ f(zix_hash_value(e), user_data);
}
}
}
generated by cgit v1.2.1 (git 2.18.0) at 2024-11-16 07:41:31 +0000