summaryrefslogtreecommitdiffstats
path: root/src/zix
diff options
context:
space:
mode:
Diffstat (limited to 'src/zix')
-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
4 files changed, 247 insertions, 72 deletions
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" */
generated by cgit v1.2.1 (git 2.18.0) at 2024-09-07 14:13:00 +0000