summaryrefslogtreecommitdiffstats
path: root/src/zix/hash.h
diff options
context:
space:
mode:
authorDavid Robillard <d@drobilla.net>2012-08-10 02:10:46 +0000
committerDavid Robillard <d@drobilla.net>2012-08-10 02:10:46 +0000
commitbe0379f60c704cc737ac0063c341121c7de7b2fb (patch)
tree9f8094b6e86e8dc7289231bc9639eccbd0205a0b /src/zix/hash.h
parentbf538b543610873de9b0e4641139b331c600ab17 (diff)
downloadsord-be0379f60c704cc737ac0063c341121c7de7b2fb.tar.gz
sord-be0379f60c704cc737ac0063c341121c7de7b2fb.tar.bz2
sord-be0379f60c704cc737ac0063c341121c7de7b2fb.zip
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
Diffstat (limited to 'src/zix/hash.h')
-rw-r--r--src/zix/hash.h107
1 files changed, 90 insertions, 17 deletions
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" */