summaryrefslogtreecommitdiffstats
path: root/src/zix
diff options
context:
space:
mode:
Diffstat (limited to 'src/zix')
-rw-r--r--src/zix/btree.c17
-rw-r--r--src/zix/common.h17
-rw-r--r--src/zix/digest.c90
-rw-r--r--src/zix/digest.h26
-rw-r--r--src/zix/hash.c15
-rw-r--r--src/zix/hash.h12
6 files changed, 143 insertions, 34 deletions
diff --git a/src/zix/btree.c b/src/zix/btree.c
index bc07f51..0a8010f 100644
--- a/src/zix/btree.c
+++ b/src/zix/btree.c
@@ -594,8 +594,10 @@ zix_btree_remove(ZixBTree* const t,
n->children[1]->n_vals};
n = zix_btree_merge(t, n, 0);
- ti->stack[ti->level].node = n;
- ti->stack[ti->level].index = counts[i];
+ if (ti) {
+ ti->stack[ti->level].node = n;
+ ti->stack[ti->level].index = counts[i];
+ }
} else {
// Both child's siblings are minimal, merge them
if (i < n->n_vals) {
@@ -659,6 +661,9 @@ zix_btree_lower_bound(const ZixBTree* const t,
if (!t) {
*ti = NULL;
return ZIX_STATUS_BAD_ARG;
+ } else if (!t->root) {
+ *ti = NULL;
+ return ZIX_STATUS_SUCCESS;
}
ZixBTreeNode* n = t->root;
@@ -760,7 +765,7 @@ zix_btree_iter_copy(const ZixBTreeIter* const i)
ZIX_API bool
zix_btree_iter_is_end(const ZixBTreeIter* const i)
{
- return !i || (i->level == 0 && i->stack[0].node == NULL);
+ return !i || i->stack[0].node == NULL;
}
ZIX_API bool
@@ -768,14 +773,16 @@ zix_btree_iter_equals(const ZixBTreeIter* const lhs, const ZixBTreeIter* const r
{
if (zix_btree_iter_is_end(lhs) && zix_btree_iter_is_end(rhs)) {
return true;
- } else if (!lhs || !rhs || lhs->n_levels != rhs->n_levels) {
+ } else if (zix_btree_iter_is_end(lhs) || zix_btree_iter_is_end(rhs)) {
+ return false;
+ } else if (!lhs || !rhs || lhs->level != rhs->level) {
return false;
}
return !memcmp(lhs,
rhs,
sizeof(ZixBTreeIter) +
- lhs->n_levels * sizeof(ZixBTreeIterFrame));
+ (lhs->level + 1) * sizeof(ZixBTreeIterFrame));
}
ZIX_API void
diff --git a/src/zix/common.h b/src/zix/common.h
index a59c033..3271858 100644
--- a/src/zix/common.h
+++ b/src/zix/common.h
@@ -17,6 +17,8 @@
#ifndef ZIX_COMMON_H
#define ZIX_COMMON_H
+#include <stdbool.h>
+
/**
@addtogroup zix
@{
@@ -48,14 +50,21 @@
#ifdef __cplusplus
extern "C" {
-#else
-# include <stdbool.h>
#endif
#ifdef __GNUC__
-#define ZIX_UNUSED __attribute__((__unused__))
+#define ZIX_LOG_FUNC(fmt, arg1) __attribute__((format(printf, fmt, arg1)))
+#else
+#define ZIX_LOG_FUNC(fmt, arg1)
+#endif
+
+// Unused parameter macro to suppresses warnings and make it impossible to use
+#if defined(__cplusplus)
+# define ZIX_UNUSED(name)
+#elif defined(__GNUC__)
+# define ZIX_UNUSED(name) name##_unused __attribute__((__unused__))
#else
-#define ZIX_UNUSED
+# define ZIX_UNUSED(name) name
#endif
typedef enum {
diff --git a/src/zix/digest.c b/src/zix/digest.c
index 7d9c035..889cfde 100644
--- a/src/zix/digest.c
+++ b/src/zix/digest.c
@@ -1,5 +1,5 @@
/*
- Copyright 2012-2014 David Robillard <http://drobilla.net>
+ Copyright 2012-2020 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
@@ -20,23 +20,29 @@
# include <smmintrin.h>
#endif
+#include <assert.h>
+#include <stdint.h>
+
+#ifdef __SSE4_2__
+
+// SSE 4.2 CRC32
+
ZIX_API uint32_t
zix_digest_start(void)
{
-#ifdef __SSE4_2__
- return 1; // CRC32 initial value
-#else
- return 5381; // DJB hash initial value
-#endif
+ return 1;
}
ZIX_API uint32_t
zix_digest_add(uint32_t hash, const void* const buf, const size_t len)
{
const uint8_t* str = (const uint8_t*)buf;
-#ifdef __SSE4_2__
- // SSE 4.2 CRC32
- for (size_t i = 0; i < (len / sizeof(uint32_t)); ++i) {
+
+ for (size_t i = 0; i < (len / sizeof(uint64_t)); ++i) {
+ hash = (uint32_t)_mm_crc32_u64(hash, *(const uint64_t*)str);
+ str += sizeof(uint64_t);
+ }
+ if (len & sizeof(uint32_t)) {
hash = _mm_crc32_u32(hash, *(const uint32_t*)str);
str += sizeof(uint32_t);
}
@@ -47,11 +53,71 @@ zix_digest_add(uint32_t hash, const void* const buf, const size_t len)
if (len & sizeof(uint8_t)) {
hash = _mm_crc32_u8(hash, *(const uint8_t*)str);
}
+
+ return hash;
+}
+
+ZIX_API uint32_t
+zix_digest_add_64(uint32_t hash, const void* const buf, const size_t len)
+{
+ assert((uintptr_t)buf % sizeof(uint64_t) == 0);
+ assert(len % sizeof(uint64_t) == 0);
+
+ const uint64_t* ptr = (const uint64_t*)buf;
+
+ for (size_t i = 0; i < (len / sizeof(uint64_t)); ++i) {
+ hash = (uint32_t)_mm_crc32_u64(hash, *ptr);
+ ++ptr;
+ }
+
+ return hash;
+}
+
+ZIX_API uint32_t
+zix_digest_add_ptr(const uint32_t hash, const void* const ptr)
+{
+#if UINTPTR_MAX == UINT64_MAX
+ return (uint32_t)_mm_crc32_u64(hash, (uintptr_t)ptr);
+#else
+ return _mm_crc32_u32(hash, (uintptr_t)ptr);
+#endif
+}
+
#else
- // Classic DJB hash
+
+// Classic DJB hash
+
+ZIX_API uint32_t
+zix_digest_start(void)
+{
+ return 5381;
+}
+
+ZIX_API uint32_t
+zix_digest_add(uint32_t hash, const void* const buf, const size_t len)
+{
+ const uint8_t* str = (const uint8_t*)buf;
+
for (size_t i = 0; i < len; ++i) {
- hash = (hash << 5) + hash + str[i];
+ hash = (hash << 5u) + hash + str[i];
}
-#endif
+
return hash;
}
+
+ZIX_API uint32_t
+zix_digest_add_64(uint32_t hash, const void* const buf, const size_t len)
+{
+ assert((uintptr_t)buf % sizeof(uint64_t) == 0);
+ assert(len % sizeof(uint64_t) == 0);
+
+ return zix_digest_add(hash, buf, len);
+}
+
+ZIX_API uint32_t
+zix_digest_add_ptr(const uint32_t hash, const void* const ptr)
+{
+ return zix_digest_add(hash, &ptr, sizeof(ptr));
+}
+
+#endif
diff --git a/src/zix/digest.h b/src/zix/digest.h
index 264c918..16ba9b9 100644
--- a/src/zix/digest.h
+++ b/src/zix/digest.h
@@ -1,5 +1,5 @@
/*
- Copyright 2012 David Robillard <http://drobilla.net>
+ Copyright 2012-2020 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
@@ -26,12 +26,36 @@
extern "C" {
#endif
+/**
+ Return an initial empty digest value.
+*/
ZIX_API uint32_t
zix_digest_start(void);
+/**
+ Update `hash` to include `buf`, a buffer of `len` bytes.
+
+ This can be used for any size or alignment.
+*/
ZIX_API uint32_t
zix_digest_add(uint32_t hash, const void* buf, size_t len);
+/**
+ Update `hash` to include `buf`, a 64-bit aligned buffer of `len` bytes.
+
+ Both `buf` and `len` must be evenly divisible by 8 (64 bits).
+*/
+ZIX_API uint32_t
+zix_digest_add_64(uint32_t hash, const void* buf, size_t len);
+
+/**
+ Update `hash` to include `ptr`.
+
+ This hashes the value of the pointer itself, and does not dereference `ptr`.
+*/
+ZIX_API uint32_t
+zix_digest_add_ptr(uint32_t hash, const void* ptr);
+
#ifdef __cplusplus
} /* extern "C" */
#endif
diff --git a/src/zix/hash.c b/src/zix/hash.c
index f633e16..c4a2dba 100644
--- a/src/zix/hash.c
+++ b/src/zix/hash.c
@@ -1,5 +1,5 @@
/*
- Copyright 2011-2014 David Robillard <http://drobilla.net>
+ Copyright 2011-2018 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
@@ -14,13 +14,12 @@
OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE.
*/
+#include "zix/hash.h"
+
#include <assert.h>
-#include <stdint.h>
#include <stdlib.h>
#include <string.h>
-#include "zix/hash.h"
-
/**
Primes, each slightly less than twice its predecessor, and as far away
from powers of two as possible.
@@ -76,6 +75,10 @@ zix_hash_new(ZixHashFunc hash_func,
ZIX_API void
zix_hash_free(ZixHash* hash)
{
+ if (!hash) {
+ return;
+ }
+
for (unsigned b = 0; b < *hash->n_buckets; ++b) {
ZixHashEntry* bucket = hash->buckets[b];
for (ZixHashEntry* e = bucket; e;) {
@@ -141,7 +144,7 @@ find_entry(const ZixHash* hash,
return NULL;
}
-ZIX_API const void*
+ZIX_API void*
zix_hash_find(const ZixHash* hash, const void* value)
{
const unsigned h_nomod = hash->hash_func(value);
@@ -151,7 +154,7 @@ zix_hash_find(const ZixHash* hash, const void* value)
}
ZIX_API ZixStatus
-zix_hash_insert(ZixHash* hash, const void* value, const void** inserted)
+zix_hash_insert(ZixHash* hash, const void* value, void** inserted)
{
unsigned h_nomod = hash->hash_func(value);
unsigned h = h_nomod % *hash->n_buckets;
diff --git a/src/zix/hash.h b/src/zix/hash.h
index db24c45..9546a64 100644
--- a/src/zix/hash.h
+++ b/src/zix/hash.h
@@ -17,11 +17,11 @@
#ifndef ZIX_HASH_H
#define ZIX_HASH_H
+#include "zix/common.h"
+
#include <stddef.h>
#include <stdint.h>
-#include "zix/common.h"
-
#ifdef __cplusplus
extern "C" {
#endif
@@ -91,9 +91,9 @@ zix_hash_size(const ZixHash* hash);
@return ZIX_STATUS_SUCCESS, ZIX_STATUS_EXISTS, or ZIX_STATUS_NO_MEM.
*/
ZIX_API ZixStatus
-zix_hash_insert(ZixHash* hash,
- const void* value,
- const void** inserted);
+zix_hash_insert(ZixHash* hash,
+ const void* value,
+ void** inserted);
/**
Remove an item from `hash`.
@@ -112,7 +112,7 @@ zix_hash_remove(ZixHash* hash,
@param hash The hash table.
@param value The value to search for.
*/
-ZIX_API const void*
+ZIX_API void*
zix_hash_find(const ZixHash* hash,
const void* value);
generated by cgit v1.2.1 (git 2.18.0) at 2024-11-09 09:53:39 +0000