summaryrefslogtreecommitdiffstats
diff options
context:
space:
mode:
-rw-r--r--NEWS1
-rw-r--r--src/sord.c229
-rw-r--r--src/sord_internal.h3
-rw-r--r--src/zix/digest.c56
-rw-r--r--src/zix/digest.h39
-rw-r--r--src/zix/hash.c117
-rw-r--r--src/zix/hash.h107
7 files changed, 333 insertions, 219 deletions
diff --git a/NEWS b/NEWS
index a5b475d..12562e1 100644
--- a/NEWS
+++ b/NEWS
@@ -1,6 +1,7 @@
sord (9999) unstable;
* Add error callback to world for custom error reporting
+ * Performance and space (per node) improvements
* sordmm.hpp: Add indices and graphs parameters to Model constructor
* sordmm.hpp: Remove overzealous URI scheme assertion
* sordmm.hpp: Correctly handle Sord::Node self-assignment
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" */