diff options
| -rw-r--r-- | NEWS | 1 | ||||
| -rw-r--r-- | src/sord.c | 229 | ||||
| -rw-r--r-- | src/sord_internal.h | 3 | ||||
| -rw-r--r-- | src/zix/digest.c | 56 | ||||
| -rw-r--r-- | src/zix/digest.h | 39 | ||||
| -rw-r--r-- | src/zix/hash.c | 117 | ||||
| -rw-r--r-- | src/zix/hash.h | 107 |
7 files changed, 333 insertions, 219 deletions
@@ -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 @@ -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" */ |