Use a single node hash for all types of nodes.

Inline nodes in hash table nodes and eliminate key+value pointer overhead.
Use SSE 4.2 accelerated node and string hashing when available.


git-svn-id: http://svn.drobilla.net/sord/trunk@250 3d64ff67-21c5-427c-a301-fe4f08042e5a

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);
 		}
 	}
 }