Update zix

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);