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

6 files changed, 332 insertions, 219 deletions

diff --git a/src/sord.c b/src/sord.c
index afca5c9..819aab1 100644
--- a/src/sord.c
+++ b/src/sord.c
@@ -23,10 +23,9 @@
 #include <string.h>
 
 #define ZIX_INLINE
+#include "zix/digest.c"
 #include "zix/hash.c"
-#include "zix/hash.h"
 #include "zix/tree.c"
-#include "zix/tree.h"
 
 #include "sord_config.h"
 #include "sord_internal.h"
@@ -105,9 +104,7 @@ static const int orderings[NUM_ORDERS][TUP_LEN] = {
 
 /** World */
 struct SordWorldImpl {
-	ZixHash*      names;  ///< URI or blank node identifier string => ID
-	ZixHash*      literals;  ///< Literal => ID
-	size_t        n_nodes;  ///< Number of nodes
+	ZixHash*      nodes;
 	SerdErrorSink error_sink;
 	void*         error_handle;
 };
@@ -145,24 +142,31 @@ struct SordIterImpl {
 	bool             skip_graphs;        ///< Iteration should ignore graphs
 };
 
-static unsigned
-sord_literal_hash(const void* n)
+static uint32_t
+sord_node_hash(const void* n)
 {
 	const SordNode* node = (const SordNode*)n;
-	return zix_string_hash(node->node.buf)
-		+ (node->lang ? zix_string_hash(node->lang) : 0);
+	uint32_t        hash = zix_digest_start();
+	hash = zix_digest_add(hash, node->node.buf, node->node.n_bytes);
+	hash = zix_digest_add(hash, node->lang, sizeof(node->lang));
+	hash = zix_digest_add(hash, &node->node.type, sizeof(node->node.type));
+	if (node->datatype) {
+		hash = zix_digest_add(
+			hash, node->datatype->node.buf, node->datatype->node.n_bytes);
+	}
+	return hash;
 }
 
 static bool
-sord_literal_equal(const void* a, const void* b)
+sord_node_hash_equal(const void* a, const void* b)
 {
 	const SordNode* a_node = (const SordNode*)a;
 	const SordNode* b_node = (const SordNode*)b;
 	return (a_node == b_node)
-		|| (zix_string_equal(sord_node_get_string(a_node),
-		                     sord_node_get_string(b_node))
-		    && !strncmp(a_node->lang, b_node->lang, sizeof(a_node->lang))
-		    && (a_node->datatype == b_node->datatype));
+		|| ((a_node->node.type == b_node->node.type) &&
+		    (a_node->datatype == b_node->datatype) &&
+		    serd_node_equals(&a_node->node, &b_node->node) &&
+		    !strncmp(a_node->lang, b_node->lang, sizeof(a_node->lang)));
 }
 
 static void
@@ -184,32 +188,28 @@ SordWorld*
 sord_world_new(void)
 {
 	SordWorld* world = (SordWorld*)malloc(sizeof(SordWorld));
-	world->names        = zix_hash_new(zix_string_hash, zix_string_equal);
-	world->literals     = zix_hash_new(sord_literal_hash, sord_literal_equal);
-	world->n_nodes      = 0;
 	world->error_sink   = NULL;
 	world->error_handle = NULL;
+
+	world->nodes = zix_hash_new(
+		sord_node_hash, sord_node_hash_equal, sizeof(SordNode));
+
 	return world;
 }
 
 static void
-free_node_entry(const void* key, void* value, void* user_data)
+free_node_entry(const void* value, void* user_data)
 {
-	SordNode* node = (SordNode*)value;
-	if (node->node.type == SERD_LITERAL) {
-		sord_node_free((SordWorld*)user_data, node->datatype);
-	}
+	const SordNode* node = (const SordNode*)value;
+	sord_node_free((SordWorld*)user_data, node->datatype);
 	free((uint8_t*)node->node.buf);
-	free(node);
 }
 
 void
 sord_world_free(SordWorld* world)
 {
-	zix_hash_foreach(world->literals, free_node_entry, world);
-	zix_hash_foreach(world->names, free_node_entry, world);
-	zix_hash_free(world->names);
-	zix_hash_free(world->literals);
+	zix_hash_foreach(world->nodes, free_node_entry, world);
+	zix_hash_free(world->nodes);
 	free(world);
 }
 
@@ -658,22 +658,19 @@ static void
 sord_node_free_internal(SordWorld* world, SordNode* node)
 {
 	assert(node->refs == 0);
-	if (node->node.type == SERD_LITERAL) {
-		if (zix_hash_remove(world->literals, node)) {
-			error(world, SERD_ERR_INTERNAL,
-			      "failed to remove literal from hash\n");
-			return;
-		}
-		sord_node_free(world, node->datatype);
-	} else {
-		if (zix_hash_remove(world->names, node->node.buf)) {
-			error(world, SERD_ERR_INTERNAL,
-			      "failed to remove resource from hash\n");
-			return;
-		}
+
+	// Cache members to free since removing from hash will free the node
+	SordNode* const      datatype = node->datatype;
+	const uint8_t* const buf      = node->node.buf;
+
+	// Remove node from hash (which frees the node)
+	if (zix_hash_remove(world->nodes, node)) {
+		error(world, SERD_ERR_INTERNAL, "failed to remove node from hash\n");
 	}
-	free((uint8_t*)node->node.buf);
-	free(node);
+
+	// Free members
+	sord_node_free(world, datatype);
+	free((uint8_t*)buf);
 }
 
 static void
@@ -752,7 +749,7 @@ sord_num_quads(const SordModel* sord)
 size_t
 sord_num_nodes(const SordWorld* world)
 {
-	return world->n_nodes;
+	return zix_hash_size(world->nodes);
 }
 
 SordIter*
@@ -882,75 +879,14 @@ sord_contains(SordModel* sord, const SordQuad pat)
 	return ret;
 }
 
-static SordNode*
-sord_lookup_name(SordWorld* world, const uint8_t* str)
-{
-	return (SordNode*)zix_hash_find(world->names, str);
-}
-
-static char*
-sord_strndup(const char* str, size_t len)
+static uint8_t*
+sord_strndup(const uint8_t* str, size_t len)
 {
-	char* dup = (char*)malloc(len + 1);
+	uint8_t* dup = (uint8_t*)malloc(len + 1);
 	memcpy(dup, str, len + 1);
 	return dup;
 }
 
-static SordNode*
-sord_new_node(SordWorld* world, SerdType type, const uint8_t* data,
-              size_t n_bytes, size_t n_chars, SerdNodeFlags flags,
-              SordNode* datatype, const char* lang, bool copy)
-{
-	if (lang && strlen(lang) > sizeof(datatype->lang) - 1) {
-		error(world, SERD_ERR_BAD_ARG,
-		      "language tag is longer than %u\n", sizeof(datatype->lang));
-		return NULL;
-	}
-		
-	SordNode* node = (SordNode*)malloc(sizeof(SordNode));
-	node->datatype     = datatype;
-	node->refs         = 1;
-	node->refs_as_obj  = 0;
-	node->node.buf     = data;
-	node->node.n_bytes = n_bytes;
-	node->node.n_chars = n_chars;
-	node->node.flags   = flags;
-	node->node.type    = type;
-
-	memset(node->lang, 0, sizeof(node->lang));
-	if (lang) {
-		strncpy(node->lang, lang, sizeof(node->lang));
-	}
-
-	if (copy) {
-		node->node.buf = (uint8_t*)sord_strndup((const char*)data, n_bytes);
-	}
-	return node;
-}
-
-static SordNode*
-sord_lookup_literal(SordWorld* world, SordNode* type,
-                    const uint8_t* str, size_t n_bytes, size_t n_chars,
-                    const char*    lang)
-{
-	struct SordNodeImpl key;
-	key.datatype     = type;
-	key.refs         = 1;
-	key.refs_as_obj  = 1;
-	key.node.buf     = str;
-	key.node.n_bytes = n_bytes;
-	key.node.n_chars = n_chars;
-	key.node.flags   = 0;
-	key.node.type    = SERD_LITERAL;
-
-	memset(key.lang, 0, sizeof(key.lang));
-	if (lang) {
-		strncpy(key.lang, lang, sizeof(key.lang));
-	}
-
-	return (SordNode*)zix_hash_find(world->literals, &key);
-}
-
 SordNodeType
 sord_node_get_type(const SordNode* node)
 {
@@ -1004,10 +940,34 @@ sord_node_is_inline_object(const SordNode* node)
 	return (node->node.type == SERD_BLANK) && (node->refs_as_obj == 1);
 }
 
-static void
-sord_add_node(SordWorld* world, SordNode* node)
+static SordNode*
+sord_insert_node(SordWorld* world, const SordNode* key, bool copy)
 {
-	++world->n_nodes;
+	SordNode* node = NULL;
+	ZixStatus st   = zix_hash_insert(world->nodes, key, (const void**)&node);
+	switch (st) {
+	case ZIX_STATUS_EXISTS:
+		++node->refs;
+		break;
+	case ZIX_STATUS_SUCCESS:
+		assert(node->refs == 1);
+		if (copy) {
+			node->node.buf = sord_strndup(node->node.buf, node->node.n_bytes);
+		}
+		node->datatype = sord_node_copy(node->datatype);
+		return node;
+	default:
+		assert(!node);
+		error(world, SERD_ERR_INTERNAL,
+		      "error inserting node `%s'\n", key->node.buf);
+	}
+
+	if (!copy) {
+		// Free the buffer we would have copied if a new node was created
+		free((uint8_t*)key->node.buf);
+	}
+
+	return node;
 }
 
 static SordNode*
@@ -1020,20 +980,11 @@ sord_new_uri_counted(SordWorld* world, const uint8_t* str,
 		return NULL;  // Can't intern relative URIs
 	}
 
-	SordNode* node = sord_lookup_name(world, str);
-	if (node) {
-		if (!copy) {
-			free((uint8_t*)str);
-		}
-		++node->refs;
-		return node;
-	}
+	const SordNode key = {
+		NULL, 1, 0, "", { str, n_bytes, n_chars, 0, SERD_URI }
+	};
 
-	node = sord_new_node(world, SERD_URI, str, n_bytes, n_chars, 0, 0, 0, copy);
-	assert(!zix_hash_find(world->names, node->node.buf));
-	zix_hash_insert(world->names, node->node.buf, node);
-	sord_add_node(world, node);
-	return node;
+	return sord_insert_node(world, &key, copy);
 }
 
 SordNode*
@@ -1066,16 +1017,11 @@ static SordNode*
 sord_new_blank_counted(SordWorld* world, const uint8_t* str,
                        size_t n_bytes, size_t n_chars)
 {
-	SordNode* node = sord_lookup_name(world, str);
-	if (node) {
-		++node->refs;
-		return node;
-	}
+	const SordNode key = {
+		NULL, 1, 0, "", { str, n_bytes, n_chars, 0, SERD_BLANK }
+	};
 
-	node = sord_new_node(world, SERD_BLANK, str, n_bytes, n_chars, 0, 0, 0, true);
-	zix_hash_insert(world->names, node->node.buf, node);
-	sord_add_node(world, node);
-	return node;
+	return sord_insert_node(world, &key, true);
 }
 
 SordNode*
@@ -1094,20 +1040,15 @@ sord_new_literal_counted(SordWorld*     world,
                          SerdNodeFlags  flags,
                          const char*    lang)
 {
-	SordNode* node = sord_lookup_literal(
-		world, datatype, str, n_bytes, n_chars, lang);
-	if (node) {
-		++node->refs;
-		return node;
+	SordNode key = {
+		datatype, 1, 0, "", { str, n_bytes, n_chars, flags, SERD_LITERAL }
+	};
+	memset(key.lang, 0, sizeof(key.lang));
+	if (lang) {
+		strncpy(key.lang, lang, sizeof(key.lang));
 	}
 
-	node = sord_new_node(world, SERD_LITERAL,
-	                     str, n_bytes, n_chars, flags,
-	                     sord_node_copy(datatype), lang, true);
-	zix_hash_insert(world->literals, node, node);  // FIXME: correct?
-	sord_add_node(world, node);
-	assert(node->refs == 1);
-	return node;
+	return sord_insert_node(world, &key, true);
 }
 
 SordNode*
diff --git a/src/sord_internal.h b/src/sord_internal.h
index 2fd245d..03050db 100644
--- a/src/sord_internal.h
+++ b/src/sord_internal.h
@@ -31,7 +31,4 @@ struct SordNodeImpl {
 	SerdNode  node;         ///< Serd node
 };
 
-const char*
-sord_intern_lang(SordWorld* world, const char* lang);
-
 #endif /* SORD_SORD_INTERNAL_H */
diff --git a/src/zix/digest.c b/src/zix/digest.c
new file mode 100644
index 0000000..4e8e974
--- /dev/null
+++ b/src/zix/digest.c
@@ -0,0 +1,56 @@
+/*
+  Copyright 2012 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 "zix/digest.h"
+
+#ifdef __SSE4_2__
+#    include <smmintrin.h>
+#endif
+
+ZIX_API uint32_t
+zix_digest_start(void)
+{
+#ifdef __SSE4_2__
+	return 1;  // CRC32 initial value
+#else
+	return 5381;  // DJB hash initial value
+#endif
+}
+
+ZIX_API uint32_t
+zix_digest_add(uint32_t hash, const void* buf, const size_t len)
+{
+#ifdef __SSE4_2__
+	// SSE 4.2 CRC32
+	for (size_t i = 0; i < (len / sizeof(uint32_t)); ++i) {
+		hash = _mm_crc32_u32(hash, *(uint32_t*)buf);
+		buf += sizeof(uint32_t);
+	}
+	if (len & sizeof(uint16_t)) {
+		hash = _mm_crc32_u16(hash, *(uint16_t*)buf);
+		buf += sizeof(uint16_t);
+	}
+	if (len & sizeof(uint8_t)) {
+		hash = _mm_crc32_u8(hash, *(uint8_t*)buf);
+	}
+#else
+	// Classic DJB hash
+	for (size_t i = 0; i < len; ++i) {
+		hash = (hash << 5) + hash + ((const uint8_t*)buf)[i];
+	}
+#endif
+	return hash;
+}
diff --git a/src/zix/digest.h b/src/zix/digest.h
new file mode 100644
index 0000000..34ab376
--- /dev/null
+++ b/src/zix/digest.h
@@ -0,0 +1,39 @@
+/*
+  Copyright 2012 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.
+*/
+
+#ifndef ZIX_DIGEST_H
+#define ZIX_DIGEST_H
+
+#include <stddef.h>
+#include <stdint.h>
+
+#include "zix/common.h"
+
+#ifdef __cplusplus
+extern "C" {
+#endif
+
+ZIX_API uint32_t
+zix_digest_start(void);
+
+ZIX_API uint32_t
+zix_digest_add(uint32_t hash, const void* buf, const size_t len);
+
+#ifdef __cplusplus
+}  /* extern "C" */
+#endif
+
+#endif  /* ZIX_DIGEST_H */
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);
 		}
 	}
 }
diff --git a/src/zix/hash.h b/src/zix/hash.h
index 4d93eaa..c992117 100644
--- a/src/zix/hash.h
+++ b/src/zix/hash.h
@@ -1,5 +1,5 @@
 /*
-  Copyright 2011 David Robillard <http://drobilla.net>
+  Copyright 2011-2012 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
@@ -17,48 +17,121 @@
 #ifndef ZIX_HASH_H
 #define ZIX_HASH_H
 
+#include <stddef.h>
+#include <stdint.h>
+
 #include "zix/common.h"
 
 #ifdef __cplusplus
 extern "C" {
 #endif
 
+/**
+   @addtogroup zix
+   @{
+   @name Hash
+   @{
+*/
+
 typedef struct ZixHashImpl ZixHash;
 
 /**
    Function for computing the hash of an element.
 */
-typedef unsigned (*ZixHashFunc)(const void* key);
+typedef uint32_t (*ZixHashFunc)(const void* value);
 
+/**
+   Function to visit a hash element.
+*/
+typedef void (*ZixHashVisitFunc)(const void* value,
+                                 void*       user_data);
+
+/**
+   Create a new hash table.
+
+   To minimize space overhead, unlike many hash tables this stores a single
+   value, not a key and a value.  Any size of value can be stored, but all the
+   values in the hash table must be the same size, and the values must be safe
+   to copy with memcpy.  To get key:value behaviour, simply insert a struct
+   with a key and value into the hash.
+
+   @param hash_func The hashing function.
+   @param equal_func A function to test value equality.
+   @param value_size The size of the values to be stored.
+*/
 ZIX_API ZixHash*
 zix_hash_new(ZixHashFunc  hash_func,
-             ZixEqualFunc key_equal_func);
+             ZixEqualFunc equal_func,
+             size_t       value_size);
 
+/**
+   Free @p hash.
+*/
 ZIX_API void
 zix_hash_free(ZixHash* hash);
 
-ZIX_API unsigned
-zix_string_hash(const void* key);
-
-ZIX_API bool
-zix_string_equal(const void* a, const void* b);
+/**
+   Return the number of elements in @p hash.
+*/
+ZIX_API size_t
+zix_hash_size(const ZixHash* hash);
 
+/**
+   Insert an item into @p hash.
+
+   If no matching value is found, ZIX_STATUS_SUCCESS will be returned, and @p
+   inserted will be pointed to the copy of @p value made in the new hash node.
+   
+   If a matching value already exists, ZIX_STATUS_EXISTS will be returned, and
+   @p inserted will be pointed to the existing value.
+
+   @param hash The hash table.
+   @param value The value to be inserted.
+   @param inserted The copy of @p value in the hash table.
+   @return ZIX_STATUS_SUCCESS, ZIX_STATUS_EXISTS, or ZIX_STATUS_NO_MEM.
+*/
 ZIX_API ZixStatus
-zix_hash_insert(ZixHash*    hash,
-                const void* key,
-                void*       data);
+zix_hash_insert(ZixHash*     hash,
+                const void*  value,
+                const void** inserted);
+
+/**
+   Remove an item from @p hash.
 
+   @param hash The hash table.
+   @param value The value to remove.
+   @return ZIX_STATUS_SUCCES or ZIX_STATUS_NOT_FOUND.
+*/
 ZIX_API ZixStatus
-zix_hash_remove(ZixHash* hash, const void* key);
+zix_hash_remove(ZixHash*    hash,
+                const void* value);
+
+/**
+   Search for an item in @p hash.
 
-ZIX_API void*
+   @param hash The hash table.
+   @param value The value to search for.
+*/
+ZIX_API const void*
 zix_hash_find(const ZixHash* hash,
-              const void*    key);
+              const void*    value);
+
+/**
+   Call @p f on each value in @p hash.
 
+   @param hash The hash table.
+   @param f The function to call on each value.
+   @param user_data The user_data parameter passed to @p f.
+*/
 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);
+
+/**
+   @}
+   @}
+*/
 
 #ifdef __cplusplus
 }  /* extern "C" */