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, 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" */