summaryrefslogtreecommitdiffstats
path: root/src
diff options
context:
space:
mode:
Diffstat (limited to 'src')
-rw-r--r--src/bitset.c124
-rw-r--r--src/btree.c957
-rw-r--r--src/chunk.c33
-rw-r--r--src/digest.c141
-rw-r--r--src/hash.c230
-rw-r--r--src/ring.c222
-rw-r--r--src/sorted_array.c193
-rw-r--r--src/strindex.c261
-rw-r--r--src/tree.c735
-rw-r--r--src/tree_debug.h175
10 files changed, 3071 insertions, 0 deletions
diff --git a/src/bitset.c b/src/bitset.c
new file mode 100644
index 0000000..cf82ad0
--- /dev/null
+++ b/src/bitset.c
@@ -0,0 +1,124 @@
+/*
+ Copyright 2014-2016 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/bitset.h"
+
+#ifdef _MSC_VER
+# include <intrin.h>
+#endif
+
+#include <string.h>
+
+/** Number of bits per ZixBitset element (ala CHAR_BIT). */
+#define ZIX_BITSET_ELEM_BIT (CHAR_BIT * sizeof(ZixBitset))
+
+static inline size_t
+zix_bitset_popcount(const ZixBitset value)
+{
+#ifdef _MSC_VER
+ return (size_t)__popcnt(value);
+#else
+ return (size_t)__builtin_popcountl(value);
+#endif
+}
+
+void
+zix_bitset_clear(ZixBitset* b, ZixBitsetTally* t, size_t n_bits)
+{
+ memset(b, 0, ZIX_BITSET_ELEMS(n_bits) * sizeof(ZixBitset));
+ memset(t, 0, ZIX_BITSET_ELEMS(n_bits) * sizeof(ZixBitsetTally));
+}
+
+void
+zix_bitset_set(ZixBitset* b, ZixBitsetTally* t, size_t i)
+{
+ const size_t e = i / ZIX_BITSET_ELEM_BIT;
+ const size_t ebit = i & (ZIX_BITSET_ELEM_BIT - 1); // i % ELEM_BIT
+ const ZixBitset mask = (ZixBitset)1 << ebit;
+
+ if (!(b[e] & mask)) {
+ ++t[e];
+ }
+
+ b[e] |= mask;
+}
+
+void
+zix_bitset_reset(ZixBitset* b, ZixBitsetTally* t, size_t i)
+{
+ const size_t e = i / ZIX_BITSET_ELEM_BIT;
+ const size_t ebit = i & (ZIX_BITSET_ELEM_BIT - 1); // i % ELEM_BIT
+ const ZixBitset mask = (ZixBitset)1 << ebit;
+
+ if (b[e] & mask) {
+ --t[e];
+ }
+
+ b[e] &= ~mask;
+}
+
+bool
+zix_bitset_get(const ZixBitset* b, size_t i)
+{
+ const size_t e = i / ZIX_BITSET_ELEM_BIT;
+ const size_t ebit = i & (ZIX_BITSET_ELEM_BIT - 1); // i % ELEM_BIT
+ const ZixBitset mask = (ZixBitset)1 << ebit;
+
+ return b[e] & mask;
+}
+
+size_t
+zix_bitset_count_up_to(const ZixBitset* b, const ZixBitsetTally* t, size_t i)
+{
+ const size_t full_elems = i / ZIX_BITSET_ELEM_BIT;
+ const size_t extra = i & (ZIX_BITSET_ELEM_BIT - 1); // i % ELEM_BIT
+
+ size_t count = 0;
+ for (size_t e = 0; e < full_elems; ++e) {
+ count += t[e];
+ }
+
+ if (extra) {
+ const ZixBitset mask = ~(~(ZixBitset)0 << extra);
+ count += zix_bitset_popcount(b[full_elems] & mask);
+ }
+
+ return count;
+}
+
+size_t
+zix_bitset_count_up_to_if(const ZixBitset* b, const ZixBitsetTally* t, size_t i)
+{
+ const size_t full_elems = i / ZIX_BITSET_ELEM_BIT;
+ const size_t extra = i & (ZIX_BITSET_ELEM_BIT - 1); // i % ELEM_BIT
+
+ const ZixBitset get_mask = (ZixBitset)1 << extra;
+ if (!(b[full_elems] & get_mask)) {
+ return (size_t)-1;
+ }
+
+ size_t count = 0;
+ for (size_t e = 0; e < full_elems; ++e) {
+ count += t[e];
+ }
+
+ if (extra) {
+ const ZixBitset mask = ~(~(ZixBitset)0 << extra);
+ count += zix_bitset_popcount(b[full_elems] & mask);
+ }
+
+ return count;
+}
diff --git a/src/btree.c b/src/btree.c
new file mode 100644
index 0000000..7435445
--- /dev/null
+++ b/src/btree.c
@@ -0,0 +1,957 @@
+/*
+ Copyright 2011-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
+ 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/btree.h"
+
+#include <assert.h>
+#include <stdint.h>
+#include <stdlib.h>
+#include <string.h>
+
+// #define ZIX_BTREE_DEBUG 1
+// #define ZIX_BTREE_SORTED_CHECK 1
+
+#ifndef ZIX_BTREE_PAGE_SIZE
+# define ZIX_BTREE_PAGE_SIZE 4096
+#endif
+
+#define ZIX_BTREE_NODE_SPACE (ZIX_BTREE_PAGE_SIZE - 2 * sizeof(uint16_t))
+#define ZIX_BTREE_LEAF_VALS ((ZIX_BTREE_NODE_SPACE / sizeof(void*)) - 1)
+#define ZIX_BTREE_INODE_VALS (ZIX_BTREE_LEAF_VALS / 2)
+
+struct ZixBTreeImpl {
+ ZixBTreeNode* root;
+ ZixDestroyFunc destroy;
+ ZixComparator cmp;
+ const void* cmp_data;
+ size_t size;
+ unsigned height; ///< Number of levels, i.e. root only has height 1
+};
+
+struct ZixBTreeNodeImpl {
+ uint16_t is_leaf;
+ uint16_t n_vals;
+ // On 64-bit we rely on some padding here to get page-sized nodes
+ union {
+ struct {
+ void* vals[ZIX_BTREE_LEAF_VALS];
+ } leaf;
+
+ struct {
+ void* vals[ZIX_BTREE_INODE_VALS];
+ ZixBTreeNode* children[ZIX_BTREE_INODE_VALS + 1];
+ } inode;
+ } data;
+};
+
+#if (defined(__STDC_VERSION__) && __STDC_VERSION__ >= 201112l) || \
+ (defined(__cplusplus) && __cplusplus >= 201103L)
+static_assert(sizeof(ZixBTreeNode) == ZIX_BTREE_PAGE_SIZE, "");
+#endif
+
+typedef struct {
+ ZixBTreeNode* node;
+ unsigned index;
+} ZixBTreeIterFrame;
+
+struct ZixBTreeIterImpl {
+ unsigned n_levels; ///< Maximum depth of stack
+ unsigned level; ///< Current level in stack
+ ZixBTreeIterFrame stack[]; ///< Position stack
+};
+
+#ifdef ZIX_BTREE_DEBUG
+
+ZIX_PRIVATE
+void
+print_node(const ZixBTreeNode* n, const char* prefix)
+{
+ printf("%s[", prefix);
+ for (uint16_t v = 0; v < n->n_vals; ++v) {
+ printf(" %lu", (uintptr_t)n->vals[v]);
+ }
+ printf(" ]\n");
+}
+
+ZIX_PRIVATE
+void
+print_tree(const ZixBTreeNode* parent, const ZixBTreeNode* node, int level)
+{
+ if (node) {
+ if (!parent) {
+ printf("TREE {\n");
+ }
+ for (int i = 0; i < level + 1; ++i) {
+ printf(" ");
+ }
+ print_node(node, "");
+ if (!node->is_leaf) {
+ for (uint16_t i = 0; i < node->n_vals + 1; ++i) {
+ print_tree(node, node->data.inode.children[i], level + 1);
+ }
+ }
+ if (!parent) {
+ printf("}\n");
+ }
+ }
+}
+
+#endif // ZIX_BTREE_DEBUG
+
+ZIX_PRIVATE
+ZixBTreeNode*
+zix_btree_node_new(const bool leaf)
+{
+#if !((defined(__STDC_VERSION__) && __STDC_VERSION__ >= 201112l) || \
+ (defined(__cplusplus) && __cplusplus >= 201103L))
+ assert(sizeof(ZixBTreeNode) == ZIX_BTREE_PAGE_SIZE);
+#endif
+
+ ZixBTreeNode* node = (ZixBTreeNode*)malloc(sizeof(ZixBTreeNode));
+ if (node) {
+ node->is_leaf = leaf;
+ node->n_vals = 0;
+ }
+ return node;
+}
+
+ZIX_PRIVATE
+void*
+zix_btree_value(const ZixBTreeNode* const node, const unsigned i)
+{
+ assert(i < node->n_vals);
+ return node->is_leaf ? node->data.leaf.vals[i] : node->data.inode.vals[i];
+}
+
+ZIX_PRIVATE
+ZixBTreeNode*
+zix_btree_child(const ZixBTreeNode* const node, const unsigned i)
+{
+ assert(!node->is_leaf);
+ assert(i <= ZIX_BTREE_INODE_VALS);
+ return node->data.inode.children[i];
+}
+
+ZixBTree*
+zix_btree_new(const ZixComparator cmp,
+ const void* const cmp_data,
+ const ZixDestroyFunc destroy)
+{
+ ZixBTree* t = (ZixBTree*)malloc(sizeof(ZixBTree));
+ if (t) {
+ t->root = zix_btree_node_new(true);
+ t->destroy = destroy;
+ t->cmp = cmp;
+ t->cmp_data = cmp_data;
+ t->size = 0;
+ t->height = 1;
+ if (!t->root) {
+ free(t);
+ return NULL;
+ }
+ }
+ return t;
+}
+
+ZIX_PRIVATE
+void
+zix_btree_free_rec(ZixBTree* const t, ZixBTreeNode* const n)
+{
+ if (n) {
+ if (n->is_leaf) {
+ if (t->destroy) {
+ for (uint16_t i = 0; i < n->n_vals; ++i) {
+ t->destroy(n->data.leaf.vals[i]);
+ }
+ }
+ } else {
+ if (t->destroy) {
+ for (uint16_t i = 0; i < n->n_vals; ++i) {
+ t->destroy(n->data.inode.vals[i]);
+ }
+ }
+
+ for (uint16_t i = 0; i < n->n_vals + 1; ++i) {
+ zix_btree_free_rec(t, zix_btree_child(n, i));
+ }
+ }
+
+ free(n);
+ }
+}
+
+void
+zix_btree_free(ZixBTree* const t)
+{
+ if (t) {
+ zix_btree_free_rec(t, t->root);
+ free(t);
+ }
+}
+
+size_t
+zix_btree_size(const ZixBTree* const t)
+{
+ return t->size;
+}
+
+ZIX_PRIVATE
+uint16_t
+zix_btree_max_vals(const ZixBTreeNode* const node)
+{
+ return node->is_leaf ? ZIX_BTREE_LEAF_VALS : ZIX_BTREE_INODE_VALS;
+}
+
+ZIX_PRIVATE
+uint16_t
+zix_btree_min_vals(const ZixBTreeNode* const node)
+{
+ return (uint16_t)(((zix_btree_max_vals(node) + 1U) / 2U) - 1U);
+}
+
+/** Shift pointers in `array` of length `n` right starting at `i`. */
+ZIX_PRIVATE
+void
+zix_btree_ainsert(void** const array,
+ const unsigned n,
+ const unsigned i,
+ void* const e)
+{
+ memmove(array + i + 1, array + i, (n - i) * sizeof(e));
+ array[i] = e;
+}
+
+/** Erase element `i` in `array` of length `n` and return erased element. */
+ZIX_PRIVATE
+void*
+zix_btree_aerase(void** const array, const unsigned n, const unsigned i)
+{
+ void* const ret = array[i];
+ memmove(array + i, array + i + 1, (n - i) * sizeof(ret));
+ return ret;
+}
+
+/** Split lhs, the i'th child of `n`, into two nodes. */
+ZIX_PRIVATE
+ZixBTreeNode*
+zix_btree_split_child(ZixBTreeNode* const n,
+ const unsigned i,
+ ZixBTreeNode* const lhs)
+{
+ assert(lhs->n_vals == zix_btree_max_vals(lhs));
+ assert(n->n_vals < ZIX_BTREE_INODE_VALS);
+ assert(i < n->n_vals + 1U);
+ assert(zix_btree_child(n, i) == lhs);
+
+ const uint16_t max_n_vals = zix_btree_max_vals(lhs);
+ ZixBTreeNode* rhs = zix_btree_node_new(lhs->is_leaf);
+ if (!rhs) {
+ return NULL;
+ }
+
+ // LHS and RHS get roughly half, less the middle value which moves up
+ lhs->n_vals = max_n_vals / 2U;
+ rhs->n_vals = (uint16_t)(max_n_vals - lhs->n_vals - 1);
+
+ if (lhs->is_leaf) {
+ // Copy large half from LHS to new RHS node
+ memcpy(rhs->data.leaf.vals,
+ lhs->data.leaf.vals + lhs->n_vals + 1,
+ rhs->n_vals * sizeof(void*));
+
+ // Move middle value up to parent
+ zix_btree_ainsert(
+ n->data.inode.vals, n->n_vals, i, lhs->data.leaf.vals[lhs->n_vals]);
+ } else {
+ // Copy large half from LHS to new RHS node
+ memcpy(rhs->data.inode.vals,
+ lhs->data.inode.vals + lhs->n_vals + 1,
+ rhs->n_vals * sizeof(void*));
+ memcpy(rhs->data.inode.children,
+ lhs->data.inode.children + lhs->n_vals + 1,
+ (rhs->n_vals + 1U) * sizeof(ZixBTreeNode*));
+
+ // Move middle value up to parent
+ zix_btree_ainsert(
+ n->data.inode.vals, n->n_vals, i, lhs->data.inode.vals[lhs->n_vals]);
+ }
+
+ // Insert new RHS node in parent at position i
+ zix_btree_ainsert((void**)n->data.inode.children, ++n->n_vals, i + 1U, rhs);
+
+ return rhs;
+}
+
+#ifdef ZIX_BTREE_SORTED_CHECK
+/** Check that `n` is sorted with respect to search key `e`. */
+ZIX_PRIVATE
+bool
+zix_btree_node_is_sorted_with_respect_to(const ZixBTree* const t,
+ const ZixBTreeNode* const n,
+ const void* const e)
+{
+ if (n->n_vals <= 1) {
+ return true;
+ }
+
+ int cmp = t->cmp(zix_btree_value(n, 0), e, t->cmp_data);
+ for (uint16_t i = 1; i < n->n_vals; ++i) {
+ const int next_cmp = t->cmp(zix_btree_value(n, i), e, t->cmp_data);
+ if ((cmp >= 0 && next_cmp < 0) || (cmp > 0 && next_cmp <= 0)) {
+ return false;
+ }
+ cmp = next_cmp;
+ }
+
+ return true;
+}
+#endif
+
+/** Find the first value in `n` that is not less than `e` (lower bound). */
+ZIX_PRIVATE
+unsigned
+zix_btree_node_find(const ZixBTree* const t,
+ const ZixBTreeNode* const n,
+ const void* const e,
+ bool* const equal)
+{
+#ifdef ZIX_BTREE_SORTED_CHECK
+ assert(zix_btree_node_is_sorted_with_respect_to(t, n, e));
+#endif
+
+ unsigned first = 0U;
+ unsigned len = n->n_vals;
+ while (len > 0) {
+ const unsigned half = len >> 1U;
+ const unsigned i = first + half;
+ const int cmp = t->cmp(zix_btree_value(n, i), e, t->cmp_data);
+ if (cmp == 0) {
+ *equal = true;
+ len = half; // Keep searching for wildcard matches
+ } else if (cmp < 0) {
+ const unsigned chop = half + 1U;
+ first += chop;
+ len -= chop;
+ } else {
+ len = half;
+ }
+ }
+
+ assert(!*equal || t->cmp(zix_btree_value(n, first), e, t->cmp_data) == 0);
+ return first;
+}
+
+ZixStatus
+zix_btree_insert(ZixBTree* const t, void* const e)
+{
+ ZixBTreeNode* parent = NULL; // Parent of n
+ ZixBTreeNode* n = t->root; // Current node
+ unsigned i = 0; // Index of n in parent
+ while (n) {
+ if (n->n_vals == zix_btree_max_vals(n)) {
+ // Node is full, split to ensure there is space for a leaf split
+ if (!parent) {
+ // Root is full, grow tree upwards
+ if (!(parent = zix_btree_node_new(false))) {
+ return ZIX_STATUS_NO_MEM;
+ }
+ t->root = parent;
+ parent->data.inode.children[0] = n;
+ ++t->height;
+ }
+
+ ZixBTreeNode* const rhs = zix_btree_split_child(parent, i, n);
+ if (!rhs) {
+ return ZIX_STATUS_NO_MEM;
+ }
+
+ const int cmp = t->cmp(parent->data.inode.vals[i], e, t->cmp_data);
+ if (cmp == 0) {
+ return ZIX_STATUS_EXISTS;
+ }
+
+ if (cmp < 0) {
+ // Move to new RHS
+ n = rhs;
+ ++i;
+ }
+ }
+
+ assert(!parent || zix_btree_child(parent, i) == n);
+
+ bool equal = false;
+ i = zix_btree_node_find(t, n, e, &equal);
+ if (equal) {
+ return ZIX_STATUS_EXISTS;
+ }
+
+ if (!n->is_leaf) {
+ // Descend to child node left of value
+ parent = n;
+ n = zix_btree_child(n, i);
+ } else {
+ // Insert into internal node
+ zix_btree_ainsert(n->data.leaf.vals, n->n_vals++, i, e);
+ break;
+ }
+ }
+
+ ++t->size;
+
+ return ZIX_STATUS_SUCCESS;
+}
+
+ZIX_PRIVATE
+ZixBTreeIter*
+zix_btree_iter_new(const ZixBTree* const t)
+{
+ const size_t s = t->height * sizeof(ZixBTreeIterFrame);
+
+ ZixBTreeIter* i = (ZixBTreeIter*)calloc(1, sizeof(ZixBTreeIter) + s);
+ if (i) {
+ i->n_levels = t->height;
+ }
+ return i;
+}
+
+ZIX_PRIVATE
+void
+zix_btree_iter_set_frame(ZixBTreeIter* const ti,
+ ZixBTreeNode* const n,
+ const unsigned i)
+{
+ if (ti) {
+ ti->stack[ti->level].node = n;
+ ti->stack[ti->level].index = i;
+ }
+}
+
+ZIX_PRIVATE
+bool
+zix_btree_node_is_minimal(ZixBTreeNode* const n)
+{
+ assert(n->n_vals >= zix_btree_min_vals(n));
+ return n->n_vals == zix_btree_min_vals(n);
+}
+
+/** Enlarge left child by stealing a value from its right sibling. */
+ZIX_PRIVATE
+ZixBTreeNode*
+zix_btree_rotate_left(ZixBTreeNode* const parent, const unsigned i)
+{
+ ZixBTreeNode* const lhs = zix_btree_child(parent, i);
+ ZixBTreeNode* const rhs = zix_btree_child(parent, i + 1);
+
+ assert(lhs->is_leaf == rhs->is_leaf);
+
+ if (lhs->is_leaf) {
+ // Move parent value to end of LHS
+ lhs->data.leaf.vals[lhs->n_vals++] = parent->data.inode.vals[i];
+
+ // Move first value in RHS to parent
+ parent->data.inode.vals[i] =
+ zix_btree_aerase(rhs->data.leaf.vals, rhs->n_vals, 0);
+ } else {
+ // Move parent value to end of LHS
+ lhs->data.inode.vals[lhs->n_vals++] = parent->data.inode.vals[i];
+
+ // Move first value in RHS to parent
+ parent->data.inode.vals[i] =
+ zix_btree_aerase(rhs->data.inode.vals, rhs->n_vals, 0);
+
+ // Move first child pointer from RHS to end of LHS
+ lhs->data.inode.children[lhs->n_vals] = (ZixBTreeNode*)zix_btree_aerase(
+ (void**)rhs->data.inode.children, rhs->n_vals, 0);
+ }
+
+ --rhs->n_vals;
+
+ return lhs;
+}
+
+/** Enlarge right child by stealing a value from its left sibling. */
+ZIX_PRIVATE
+ZixBTreeNode*
+zix_btree_rotate_right(ZixBTreeNode* const parent, const unsigned i)
+{
+ ZixBTreeNode* const lhs = zix_btree_child(parent, i - 1);
+ ZixBTreeNode* const rhs = zix_btree_child(parent, i);
+
+ assert(lhs->is_leaf == rhs->is_leaf);
+
+ if (lhs->is_leaf) {
+ // Prepend parent value to RHS
+ zix_btree_ainsert(
+ rhs->data.leaf.vals, rhs->n_vals++, 0, parent->data.inode.vals[i - 1]);
+
+ // Move last value from LHS to parent
+ parent->data.inode.vals[i - 1] = lhs->data.leaf.vals[--lhs->n_vals];
+ } else {
+ // Prepend parent value to RHS
+ zix_btree_ainsert(
+ rhs->data.inode.vals, rhs->n_vals++, 0, parent->data.inode.vals[i - 1]);
+
+ // Move last child pointer from LHS and prepend to RHS
+ zix_btree_ainsert((void**)rhs->data.inode.children,
+ rhs->n_vals,
+ 0,
+ lhs->data.inode.children[lhs->n_vals]);
+
+ // Move last value from LHS to parent
+ parent->data.inode.vals[i - 1] = lhs->data.inode.vals[--lhs->n_vals];
+ }
+
+ return rhs;
+}
+
+/** Move n[i] down, merge the left and right child, return the merged node. */
+ZIX_PRIVATE
+ZixBTreeNode*
+zix_btree_merge(ZixBTree* const t, ZixBTreeNode* const n, const unsigned i)
+{
+ ZixBTreeNode* const lhs = zix_btree_child(n, i);
+ ZixBTreeNode* const rhs = zix_btree_child(n, i + 1);
+
+ assert(lhs->is_leaf == rhs->is_leaf);
+ assert(zix_btree_node_is_minimal(lhs));
+ assert(lhs->n_vals + rhs->n_vals < zix_btree_max_vals(lhs));
+
+ // Move parent value to end of LHS
+ if (lhs->is_leaf) {
+ lhs->data.leaf.vals[lhs->n_vals++] =
+ zix_btree_aerase(n->data.inode.vals, n->n_vals, i);
+ } else {
+ lhs->data.inode.vals[lhs->n_vals++] =
+ zix_btree_aerase(n->data.inode.vals, n->n_vals, i);
+ }
+
+ // Erase corresponding child pointer (to RHS) in parent
+ zix_btree_aerase((void**)n->data.inode.children, n->n_vals, i + 1U);
+
+ // Add everything from RHS to end of LHS
+ if (lhs->is_leaf) {
+ memcpy(lhs->data.leaf.vals + lhs->n_vals,
+ rhs->data.leaf.vals,
+ rhs->n_vals * sizeof(void*));
+ } else {
+ memcpy(lhs->data.inode.vals + lhs->n_vals,
+ rhs->data.inode.vals,
+ rhs->n_vals * sizeof(void*));
+ memcpy(lhs->data.inode.children + lhs->n_vals,
+ rhs->data.inode.children,
+ (rhs->n_vals + 1U) * sizeof(void*));
+ }
+
+ lhs->n_vals = (uint16_t)(lhs->n_vals + rhs->n_vals);
+
+ if (--n->n_vals == 0) {
+ // Root is now empty, replace it with its only child
+ assert(n == t->root);
+ t->root = lhs;
+ free(n);
+ }
+
+ free(rhs);
+ return lhs;
+}
+
+/** Remove and return the min value from the subtree rooted at `n`. */
+ZIX_PRIVATE
+void*
+zix_btree_remove_min(ZixBTree* const t, ZixBTreeNode* n)
+{
+ while (!n->is_leaf) {
+ if (zix_btree_node_is_minimal(zix_btree_child(n, 0))) {
+ // Leftmost child is minimal, must expand
+ if (!zix_btree_node_is_minimal(zix_btree_child(n, 1))) {
+ // Child's right sibling has at least one key to steal
+ n = zix_btree_rotate_left(n, 0);
+ } else {
+ // Both child and right sibling are minimal, merge
+ n = zix_btree_merge(t, n, 0);
+ }
+ } else {
+ n = zix_btree_child(n, 0);
+ }
+ }
+
+ return zix_btree_aerase(n->data.leaf.vals, --n->n_vals, 0);
+}
+
+/** Remove and return the max value from the subtree rooted at `n`. */
+ZIX_PRIVATE
+void*
+zix_btree_remove_max(ZixBTree* const t, ZixBTreeNode* n)
+{
+ while (!n->is_leaf) {
+ if (zix_btree_node_is_minimal(zix_btree_child(n, n->n_vals))) {
+ // Leftmost child is minimal, must expand
+ if (!zix_btree_node_is_minimal(zix_btree_child(n, n->n_vals - 1))) {
+ // Child's left sibling has at least one key to steal
+ n = zix_btree_rotate_right(n, n->n_vals);
+ } else {
+ // Both child and left sibling are minimal, merge
+ n = zix_btree_merge(t, n, n->n_vals - 1U);
+ }
+ } else {
+ n = zix_btree_child(n, n->n_vals);
+ }
+ }
+
+ return n->data.leaf.vals[--n->n_vals];
+}
+
+ZixStatus
+zix_btree_remove(ZixBTree* const t,
+ const void* const e,
+ void** const out,
+ ZixBTreeIter** const next)
+{
+ ZixBTreeNode* n = t->root;
+ ZixBTreeIter* ti = NULL;
+ const bool user_iter = next && *next;
+ if (next) {
+ if (!*next && !(*next = zix_btree_iter_new(t))) {
+ return ZIX_STATUS_NO_MEM;
+ }
+ ti = *next;
+ ti->level = 0;
+ }
+
+ while (true) {
+ /* To remove in a single walk down, the tree is adjusted along the way
+ so that the current node always has at least one more value than the
+ minimum required in general. Thus, there is always room to remove
+ without adjusting on the way back up. */
+ assert(n == t->root || !zix_btree_node_is_minimal(n));
+
+ bool equal = false;
+ const unsigned i = zix_btree_node_find(t, n, e, &equal);
+ zix_btree_iter_set_frame(ti, n, i);
+ if (n->is_leaf) {
+ if (equal) {
+ // Found in leaf node
+ *out = zix_btree_aerase(n->data.leaf.vals, --n->n_vals, i);
+ if (ti && i == n->n_vals) {
+ if (i == 0) {
+ ti->level = 0;
+ ti->stack[0].node = NULL;
+ } else {
+ --ti->stack[ti->level].index;
+ zix_btree_iter_increment(ti);
+ }
+ }
+ --t->size;
+ return ZIX_STATUS_SUCCESS;
+ }
+
+ // Not found in leaf node, or tree
+ if (ti && !user_iter) {
+ zix_btree_iter_free(ti);
+ *next = NULL;
+ }
+
+ return ZIX_STATUS_NOT_FOUND;
+ }
+
+ if (equal) {
+ // Found in internal node
+ ZixBTreeNode* const lhs = zix_btree_child(n, i);
+ ZixBTreeNode* const rhs = zix_btree_child(n, i + 1);
+ const size_t l_size = lhs->n_vals;
+ const size_t r_size = rhs->n_vals;
+ if (zix_btree_node_is_minimal(lhs) && zix_btree_node_is_minimal(rhs)) {
+ // Both preceding and succeeding child are minimal
+ n = zix_btree_merge(t, n, i);
+ } else if (l_size >= r_size) {
+ // Left child can remove without merge
+ assert(!zix_btree_node_is_minimal(lhs));
+ *out = n->data.inode.vals[i];
+ n->data.inode.vals[i] = zix_btree_remove_max(t, lhs);
+ --t->size;
+ return ZIX_STATUS_SUCCESS;
+ } else {
+ // Right child can remove without merge
+ assert(!zix_btree_node_is_minimal(rhs));
+ *out = n->data.inode.vals[i];
+ n->data.inode.vals[i] = zix_btree_remove_min(t, rhs);
+ --t->size;
+ return ZIX_STATUS_SUCCESS;
+ }
+ } else {
+ // Not found in internal node, key is in/under children[i]
+ if (zix_btree_node_is_minimal(zix_btree_child(n, i))) {
+ if (i > 0 && !zix_btree_node_is_minimal(zix_btree_child(n, i - 1))) {
+ // Steal a key from child's left sibling
+ n = zix_btree_rotate_right(n, i);
+ } else if (i < n->n_vals &&
+ !zix_btree_node_is_minimal(zix_btree_child(n, i + 1))) {
+ // Steal a key from child's right sibling
+ n = zix_btree_rotate_left(n, i);
+ } else if (n == t->root && n->n_vals == 1) {
+ // Root has two children, both minimal, delete it
+ assert(i == 0 || i == 1);
+ const uint16_t counts[2] = {zix_btree_child(n, 0)->n_vals,
+ zix_btree_child(n, 1)->n_vals};
+
+ n = zix_btree_merge(t, n, 0);
+ 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) {
+ n = zix_btree_merge(t, n, i);
+ } else {
+ n = zix_btree_merge(t, n, i - 1U);
+ if (ti) {
+ --ti->stack[ti->level].index;
+ }
+ }
+ }
+ } else {
+ n = zix_btree_child(n, i);
+ }
+ }
+ if (ti) {
+ ++ti->level;
+ }
+ }
+
+ assert(false); // Not reached
+ return ZIX_STATUS_ERROR;
+}
+
+ZixStatus
+zix_btree_find(const ZixBTree* const t,
+ const void* const e,
+ ZixBTreeIter** const ti)
+{
+ ZixBTreeNode* n = t->root;
+ if (!(*ti = zix_btree_iter_new(t))) {
+ return ZIX_STATUS_NO_MEM;
+ }
+
+ while (n) {
+ bool equal = false;
+ const unsigned i = zix_btree_node_find(t, n, e, &equal);
+
+ zix_btree_iter_set_frame(*ti, n, i);
+
+ if (equal) {
+ return ZIX_STATUS_SUCCESS;
+ }
+
+ if (n->is_leaf) {
+ break;
+ }
+
+ ++(*ti)->level;
+ n = zix_btree_child(n, i);
+ }
+
+ zix_btree_iter_free(*ti);
+ *ti = NULL;
+ return ZIX_STATUS_NOT_FOUND;
+}
+
+ZixStatus
+zix_btree_lower_bound(const ZixBTree* const t,
+ const void* const e,
+ ZixBTreeIter** const ti)
+{
+ if (!t) {
+ *ti = NULL;
+ return ZIX_STATUS_BAD_ARG;
+ }
+
+ if (!t->root) {
+ *ti = NULL;
+ return ZIX_STATUS_SUCCESS;
+ }
+
+ ZixBTreeNode* n = t->root;
+ bool found = false;
+ unsigned found_level = 0;
+ if (!(*ti = zix_btree_iter_new(t))) {
+ return ZIX_STATUS_NO_MEM;
+ }
+
+ while (n) {
+ bool equal = false;
+ const unsigned i = zix_btree_node_find(t, n, e, &equal);
+
+ zix_btree_iter_set_frame(*ti, n, i);
+
+ if (equal) {
+ found_level = (*ti)->level;
+ found = true;
+ }
+
+ if (n->is_leaf) {
+ break;
+ }
+
+ ++(*ti)->level;
+ n = zix_btree_child(n, i);
+ assert(n);
+ }
+
+ const ZixBTreeIterFrame* const frame = &(*ti)->stack[(*ti)->level];
+ assert(frame->node);
+ if (frame->index == frame->node->n_vals) {
+ if (found) {
+ // Found on a previous level but went too far
+ (*ti)->level = found_level;
+ } else {
+ // Reached end (key is greater than everything in tree)
+ (*ti)->level = 0;
+ (*ti)->stack[0].node = NULL;
+ }
+ }
+
+ return ZIX_STATUS_SUCCESS;
+}
+
+void*
+zix_btree_get(const ZixBTreeIter* const ti)
+{
+ const ZixBTreeIterFrame* const frame = &ti->stack[ti->level];
+ assert(frame->node);
+ assert(frame->index < frame->node->n_vals);
+ return zix_btree_value(frame->node, frame->index);
+}
+
+ZixBTreeIter*
+zix_btree_begin(const ZixBTree* const t)
+{
+ ZixBTreeIter* const i = zix_btree_iter_new(t);
+ if (!i) {
+ return NULL;
+ }
+
+ if (t->size == 0) {
+ i->level = 0;
+ i->stack[0].node = NULL;
+ } else {
+ ZixBTreeNode* n = t->root;
+ i->stack[0].node = n;
+ i->stack[0].index = 0;
+ while (!n->is_leaf) {
+ n = zix_btree_child(n, 0);
+ ++i->level;
+ i->stack[i->level].node = n;
+ i->stack[i->level].index = 0;
+ }
+ }
+
+ return i;
+}
+
+ZixBTreeIter*
+zix_btree_end(const ZixBTree* const t)
+{
+ return zix_btree_iter_new(t);
+}
+
+ZixBTreeIter*
+zix_btree_iter_copy(const ZixBTreeIter* const i)
+{
+ if (!i) {
+ return NULL;
+ }
+
+ const size_t s = i->n_levels * sizeof(ZixBTreeIterFrame);
+ ZixBTreeIter* j = (ZixBTreeIter*)calloc(1, sizeof(ZixBTreeIter) + s);
+ if (j) {
+ memcpy(j, i, sizeof(ZixBTreeIter) + s);
+ }
+
+ return j;
+}
+
+bool
+zix_btree_iter_is_end(const ZixBTreeIter* const i)
+{
+ return !i || i->stack[0].node == NULL;
+}
+
+bool
+zix_btree_iter_equals(const ZixBTreeIter* const lhs,
+ const ZixBTreeIter* const rhs)
+{
+ if (zix_btree_iter_is_end(lhs) && zix_btree_iter_is_end(rhs)) {
+ return true;
+ }
+
+ if (zix_btree_iter_is_end(lhs) || zix_btree_iter_is_end(rhs) ||
+ lhs->level != rhs->level) {
+ return false;
+ }
+
+ return !memcmp(lhs,
+ rhs,
+ sizeof(ZixBTreeIter) +
+ (lhs->level + 1) * sizeof(ZixBTreeIterFrame));
+}
+
+void
+zix_btree_iter_increment(ZixBTreeIter* const i)
+{
+ ZixBTreeIterFrame* f = &i->stack[i->level];
+ if (f->node->is_leaf) {
+ // Leaf, move right
+ assert(f->index < f->node->n_vals);
+ if (++f->index == f->node->n_vals) {
+ // Reached end of leaf, move up
+ f = &i->stack[i->level];
+ while (i->level > 0 && f->index == f->node->n_vals) {
+ f = &i->stack[--i->level];
+ assert(f->index <= f->node->n_vals);
+ }
+
+ if (f->index == f->node->n_vals) {
+ // Reached end of tree
+ assert(i->level == 0);
+ f->node = NULL;
+ f->index = 0;
+ }
+ }
+ } else {
+ // Internal node, move down to next child
+ assert(f->index < f->node->n_vals);
+ ZixBTreeNode* child = zix_btree_child(f->node, ++f->index);
+
+ f = &i->stack[++i->level];
+ f->node = child;
+ f->index = 0;
+
+ // Move down and left until we hit a leaf
+ while (!f->node->is_leaf) {
+ child = zix_btree_child(f->node, 0);
+ f = &i->stack[++i->level];
+ f->node = child;
+ f->index = 0;
+ }
+ }
+}
+
+void
+zix_btree_iter_free(ZixBTreeIter* const i)
+{
+ free(i);
+}
diff --git a/src/chunk.c b/src/chunk.c
new file mode 100644
index 0000000..bf80f88
--- /dev/null
+++ b/src/chunk.c
@@ -0,0 +1,33 @@
+/*
+ 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/chunk.h"
+
+#include "zix/digest.h"
+
+#include <string.h>
+
+uint32_t
+zix_chunk_hash(const ZixChunk* const chunk)
+{
+ return zix_digest_add(zix_digest_start(), chunk->buf, chunk->len);
+}
+
+bool
+zix_chunk_equal(const ZixChunk* a, const ZixChunk* b)
+{
+ return a->len == b->len && !memcmp(a->buf, b->buf, a->len);
+}
diff --git a/src/digest.c b/src/digest.c
new file mode 100644
index 0000000..941b05c
--- /dev/null
+++ b/src/digest.c
@@ -0,0 +1,141 @@
+/*
+ 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
+ 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
+
+#include <assert.h>
+#include <stdint.h>
+
+#ifdef __SSE4_2__
+
+// SSE 4.2 CRC32
+
+uint32_t
+zix_digest_start(void)
+{
+ return 1;
+}
+
+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 __x86_64__
+ 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);
+ }
+# else
+ for (size_t i = 0; i < (len / sizeof(uint32_t)); ++i) {
+ hash = _mm_crc32_u32(hash, *(const uint32_t*)str);
+ str += sizeof(uint32_t);
+ }
+# endif
+ if (len & sizeof(uint16_t)) {
+ hash = _mm_crc32_u16(hash, *(const uint16_t*)str);
+ str += sizeof(uint16_t);
+ }
+ if (len & sizeof(uint8_t)) {
+ hash = _mm_crc32_u8(hash, *(const uint8_t*)str);
+ }
+
+ return hash;
+}
+
+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);
+
+# ifdef __x86_64__
+ 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;
+# else
+ const uint32_t* ptr = (const uint32_t*)buf;
+
+ for (size_t i = 0; i < (len / sizeof(uint32_t)); ++i) {
+ hash = _mm_crc32_u32(hash, *ptr);
+ ++ptr;
+ }
+
+ return hash;
+# endif
+}
+
+uint32_t
+zix_digest_add_ptr(const uint32_t hash, const void* const ptr)
+{
+# ifdef __x86_64__
+ return (uint32_t)_mm_crc32_u64(hash, (uintptr_t)ptr);
+# else
+ return _mm_crc32_u32(hash, (uintptr_t)ptr);
+# endif
+}
+
+#else
+
+// Classic DJB hash
+
+uint32_t
+zix_digest_start(void)
+{
+ return 5381;
+}
+
+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 << 5u) + hash + str[i];
+ }
+
+ return hash;
+}
+
+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);
+}
+
+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/hash.c b/src/hash.c
new file mode 100644
index 0000000..34464d4
--- /dev/null
+++ b/src/hash.c
@@ -0,0 +1,230 @@
+/*
+ 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
+ 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/hash.h"
+
+#include <assert.h>
+#include <stdlib.h>
+#include <string.h>
+
+/**
+ Primes, each slightly less than twice its predecessor, and as far away
+ from powers of two as possible.
+*/
+static const unsigned sizes[] = {
+ 53, 97, 193, 389, 769, 1543, 3079,
+ 6151, 12289, 24593, 49157, 98317, 196613, 393241,
+ 786433, 1572869, 3145739, 6291469, 12582917, 25165843, 50331653,
+ 100663319, 201326611, 402653189, 805306457, 1610612741, 0};
+
+typedef struct ZixHashEntry {
+ struct ZixHashEntry* next; ///< Next entry in bucket
+ uint32_t hash; ///< Non-modulo hash value
+ // Value follows here (access with zix_hash_value)
+} ZixHashEntry;
+
+struct ZixHashImpl {
+ ZixHashFunc hash_func;
+ ZixEqualFunc equal_func;
+ ZixHashEntry** buckets;
+ const unsigned* n_buckets;
+ size_t value_size;
+ unsigned count;
+};
+
+static inline void*
+zix_hash_value(ZixHashEntry* entry)
+{
+ return entry + 1;
+}
+
+ZixHash*
+zix_hash_new(ZixHashFunc hash_func, ZixEqualFunc equal_func, size_t value_size)
+{
+ ZixHash* hash = (ZixHash*)malloc(sizeof(ZixHash));
+ if (hash) {
+ hash->hash_func = hash_func;
+ hash->equal_func = equal_func;
+ hash->n_buckets = &sizes[0];
+ hash->value_size = value_size;
+ hash->count = 0;
+ if (!(hash->buckets =
+ (ZixHashEntry**)calloc(*hash->n_buckets, sizeof(ZixHashEntry*)))) {
+ free(hash);
+ return NULL;
+ }
+ }
+ return hash;
+}
+
+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;) {
+ ZixHashEntry* next = e->next;
+ free(e);
+ e = next;
+ }
+ }
+
+ free(hash->buckets);
+ free(hash);
+}
+
+size_t
+zix_hash_size(const ZixHash* hash)
+{
+ return hash->count;
+}
+
+static inline void
+insert_entry(ZixHashEntry** bucket, ZixHashEntry* entry)
+{
+ entry->next = *bucket;
+ *bucket = entry;
+}
+
+static inline ZixStatus
+rehash(ZixHash* hash, unsigned new_n_buckets)
+{
+ ZixHashEntry** new_buckets =
+ (ZixHashEntry**)calloc(new_n_buckets, sizeof(ZixHashEntry*));
+ if (!new_buckets) {
+ return ZIX_STATUS_NO_MEM;
+ }
+
+ 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;
+ insert_entry(&new_buckets[h], e);
+ e = next;
+ }
+ }
+
+ free(hash->buckets);
+ hash->buckets = new_buckets;
+
+ return ZIX_STATUS_SUCCESS;
+}
+
+static inline ZixHashEntry*
+find_entry(const ZixHash* hash,
+ const void* key,
+ const unsigned h,
+ const unsigned h_nomod)
+{
+ for (ZixHashEntry* e = hash->buckets[h]; e; e = e->next) {
+ if (e->hash == h_nomod && hash->equal_func(zix_hash_value(e), key)) {
+ return e;
+ }
+ }
+ return NULL;
+}
+
+void*
+zix_hash_find(const ZixHash* hash, const void* value)
+{
+ 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;
+}
+
+ZixStatus
+zix_hash_insert(ZixHash* hash, const void* value, void** inserted)
+{
+ unsigned h_nomod = hash->hash_func(value);
+ unsigned h = h_nomod % *hash->n_buckets;
+
+ 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) + hash->value_size);
+ if (!elem) {
+ return ZIX_STATUS_NO_MEM;
+ }
+ 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)) {
+ h = h_nomod % *(++hash->n_buckets);
+ }
+ }
+
+ insert_entry(&hash->buckets[h], elem);
+ ++hash->count;
+ if (inserted) {
+ *inserted = zix_hash_value(elem);
+ }
+ return ZIX_STATUS_SUCCESS;
+}
+
+ZixStatus
+zix_hash_remove(ZixHash* hash, const void* value)
+{
+ 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 (h_nomod == e->hash && hash->equal_func(zix_hash_value(e), value)) {
+ *next_ptr = e->next;
+ free(e);
+ return ZIX_STATUS_SUCCESS;
+ }
+ next_ptr = &e->next;
+ }
+
+ if (hash->n_buckets != sizes) {
+ const unsigned prev_n_buckets = *(hash->n_buckets - 1);
+ if (hash->count - 1 <= prev_n_buckets) {
+ if (!rehash(hash, prev_n_buckets)) {
+ --hash->n_buckets;
+ }
+ }
+ }
+
+ --hash->count;
+ return ZIX_STATUS_NOT_FOUND;
+}
+
+void
+zix_hash_foreach(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(zix_hash_value(e), user_data);
+ }
+ }
+}
diff --git a/src/ring.c b/src/ring.c
new file mode 100644
index 0000000..0607a18
--- /dev/null
+++ b/src/ring.c
@@ -0,0 +1,222 @@
+/*
+ Copyright 2011 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/ring.h"
+
+#include <stdlib.h>
+#include <string.h>
+
+#ifdef HAVE_MLOCK
+# include <sys/mman.h>
+# define ZIX_MLOCK(ptr, size) mlock((ptr), (size))
+#elif defined(_WIN32)
+# include <windows.h>
+# define ZIX_MLOCK(ptr, size) VirtualLock((ptr), (size))
+#else
+# pragma message("warning: No memory locking, possible RT violations")
+# define ZIX_MLOCK(ptr, size)
+#endif
+
+#if defined(_MSC_VER)
+# include <windows.h>
+# define ZIX_READ_BARRIER() MemoryBarrier()
+# define ZIX_WRITE_BARRIER() MemoryBarrier()
+#elif defined(__GNUC__)
+# define ZIX_READ_BARRIER() __atomic_thread_fence(__ATOMIC_ACQUIRE)
+# define ZIX_WRITE_BARRIER() __atomic_thread_fence(__ATOMIC_RELEASE)
+#else
+# pragma message("warning: No memory barriers, possible SMP bugs")
+# define ZIX_READ_BARRIER()
+# define ZIX_WRITE_BARRIER()
+#endif
+
+struct ZixRingImpl {
+ uint32_t write_head; ///< Read index into buf
+ uint32_t read_head; ///< Write index into buf
+ uint32_t size; ///< Size (capacity) in bytes
+ uint32_t size_mask; ///< Mask for fast modulo
+ char* buf; ///< Contents
+};
+
+static inline uint32_t
+next_power_of_two(uint32_t size)
+{
+ // http://graphics.stanford.edu/~seander/bithacks.html#RoundUpPowerOf2
+ size--;
+ size |= size >> 1u;
+ size |= size >> 2u;
+ size |= size >> 4u;
+ size |= size >> 8u;
+ size |= size >> 16u;
+ size++;
+ return size;
+}
+
+ZixRing*
+zix_ring_new(uint32_t size)
+{
+ ZixRing* ring = (ZixRing*)malloc(sizeof(ZixRing));
+ ring->write_head = 0;
+ ring->read_head = 0;
+ ring->size = next_power_of_two(size);
+ ring->size_mask = ring->size - 1;
+ ring->buf = (char*)malloc(ring->size);
+ return ring;
+}
+
+void
+zix_ring_free(ZixRing* ring)
+{
+ free(ring->buf);
+ free(ring);
+}
+
+void
+zix_ring_mlock(ZixRing* ring)
+{
+ ZIX_MLOCK(ring, sizeof(ZixRing));
+ ZIX_MLOCK(ring->buf, ring->size);
+}
+
+void
+zix_ring_reset(ZixRing* ring)
+{
+ ring->write_head = 0;
+ ring->read_head = 0;
+}
+
+static inline uint32_t
+read_space_internal(const ZixRing* ring, uint32_t r, uint32_t w)
+{
+ if (r < w) {
+ return w - r;
+ }
+
+ return (w - r + ring->size) & ring->size_mask;
+}
+
+uint32_t
+zix_ring_read_space(const ZixRing* ring)
+{
+ return read_space_internal(ring, ring->read_head, ring->write_head);
+}
+
+static inline uint32_t
+write_space_internal(const ZixRing* ring, uint32_t r, uint32_t w)
+{
+ if (r == w) {
+ return ring->size - 1;
+ }
+
+ if (r < w) {
+ return ((r - w + ring->size) & ring->size_mask) - 1;
+ }
+
+ return (r - w) - 1;
+}
+
+uint32_t
+zix_ring_write_space(const ZixRing* ring)
+{
+ return write_space_internal(ring, ring->read_head, ring->write_head);
+}
+
+uint32_t
+zix_ring_capacity(const ZixRing* ring)
+{
+ return ring->size - 1;
+}
+
+static inline uint32_t
+peek_internal(const ZixRing* ring,
+ uint32_t r,
+ uint32_t w,
+ uint32_t size,
+ void* dst)
+{
+ if (read_space_internal(ring, r, w) < size) {
+ return 0;
+ }
+
+ if (r + size < ring->size) {
+ memcpy(dst, &ring->buf[r], size);
+ } else {
+ const uint32_t first_size = ring->size - r;
+ memcpy(dst, &ring->buf[r], first_size);
+ memcpy((char*)dst + first_size, &ring->buf[0], size - first_size);
+ }
+
+ return size;
+}
+
+uint32_t
+zix_ring_peek(ZixRing* ring, void* dst, uint32_t size)
+{
+ return peek_internal(ring, ring->read_head, ring->write_head, size, dst);
+}
+
+uint32_t
+zix_ring_read(ZixRing* ring, void* dst, uint32_t size)
+{
+ const uint32_t r = ring->read_head;
+ const uint32_t w = ring->write_head;
+
+ if (peek_internal(ring, r, w, size, dst)) {
+ ZIX_READ_BARRIER();
+ ring->read_head = (r + size) & ring->size_mask;
+ return size;
+ }
+
+ return 0;
+}
+
+uint32_t
+zix_ring_skip(ZixRing* ring, uint32_t size)
+{
+ const uint32_t r = ring->read_head;
+ const uint32_t w = ring->write_head;
+ if (read_space_internal(ring, r, w) < size) {
+ return 0;
+ }
+
+ ZIX_READ_BARRIER();
+ ring->read_head = (r + size) & ring->size_mask;
+ return size;
+}
+
+uint32_t
+zix_ring_write(ZixRing* ring, const void* src, uint32_t size)
+{
+ const uint32_t r = ring->read_head;
+ const uint32_t w = ring->write_head;
+ if (write_space_internal(ring, r, w) < size) {
+ return 0;
+ }
+
+ if (w + size <= ring->size) {
+ memcpy(&ring->buf[w], src, size);
+ ZIX_WRITE_BARRIER();
+ ring->write_head = (w + size) & ring->size_mask;
+ } else {
+ const uint32_t this_size = ring->size - w;
+ memcpy(&ring->buf[w], src, this_size);
+ memcpy(&ring->buf[0], (const char*)src + this_size, size - this_size);
+ ZIX_WRITE_BARRIER();
+ ring->write_head = size - this_size;
+ }
+
+ return size;
+}
diff --git a/src/sorted_array.c b/src/sorted_array.c
new file mode 100644
index 0000000..0f84227
--- /dev/null
+++ b/src/sorted_array.c
@@ -0,0 +1,193 @@
+/*
+ Copyright 2011 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/sorted_array.h"
+
+#include "zix/common.h"
+
+#include <assert.h>
+#include <stdint.h>
+#include <stdlib.h>
+#include <string.h>
+
+// #define ZIX_SORTED_ARRAY_DUMP 1
+
+struct ZixSortedArrayImpl {
+ void* array;
+ ZixComparator cmp;
+ void* cmp_data;
+ size_t elem_size;
+ size_t num_elems;
+ bool allow_duplicates;
+};
+
+#ifdef ZIX_SORTED_ARRAY_DUMP
+static void
+zix_sorted_array_print(ZixSortedArray* a)
+{
+ for (size_t i = 0; i < a->num_elems; ++i) {
+ printf(" %ld", *(intptr_t*)((char*)a->array + (i * a->elem_size)));
+ }
+ printf("\n");
+}
+# define DUMP(a) zix_sorted_array_print(a)
+#else
+# define DUMP(a)
+#endif
+
+ZixSortedArray*
+zix_sorted_array_new(bool allow_duplicates,
+ ZixComparator cmp,
+ void* cmp_data,
+ size_t elem_size)
+{
+ ZixSortedArray* a = (ZixSortedArray*)malloc(sizeof(ZixSortedArray));
+ a->array = NULL;
+ a->cmp = cmp;
+ a->cmp_data = cmp_data;
+ a->elem_size = elem_size;
+ a->num_elems = 0;
+ a->allow_duplicates = allow_duplicates;
+ return a;
+}
+
+void
+zix_sorted_array_free(ZixSortedArray* a)
+{
+ free(a->array);
+ free(a);
+}
+
+size_t
+zix_sorted_array_size(const ZixSortedArray* a)
+{
+ return a->num_elems;
+}
+
+ZixStatus
+zix_sorted_array_insert(ZixSortedArray* a,
+ const void* e,
+ ZixSortedArrayIter* ai)
+{
+ if (a->num_elems == 0) {
+ assert(!a->array);
+ a->array = malloc(a->elem_size);
+ memcpy(a->array, e, a->elem_size);
+ ++a->num_elems;
+ *ai = a->array;
+ return ZIX_STATUS_SUCCESS;
+ }
+
+ zix_sorted_array_find(a, e, ai);
+ assert(*ai);
+ const size_t i = (size_t)((char*)*ai - (char*)a->array) / a->elem_size;
+
+ a->array = realloc(a->array, ++a->num_elems * a->elem_size);
+ memmove((char*)a->array + ((i + 1) * a->elem_size),
+ (char*)a->array + (i * a->elem_size),
+ (a->num_elems - i - 1) * a->elem_size);
+ memcpy((char*)a->array + (i * a->elem_size), e, a->elem_size);
+
+ *ai = (char*)a->array + (i * a->elem_size);
+ DUMP(t);
+ return ZIX_STATUS_SUCCESS;
+}
+
+ZixStatus
+zix_sorted_array_remove(ZixSortedArray* a, ZixSortedArrayIter ai)
+{
+ const size_t i = (size_t)((char*)ai - (char*)a->array) / a->elem_size;
+ memmove((char*)a->array + (i * a->elem_size),
+ (char*)a->array + ((i + 1) * a->elem_size),
+ (a->num_elems - i - 1) * a->elem_size);
+ --a->num_elems;
+ DUMP(a);
+ return ZIX_STATUS_SUCCESS;
+}
+
+static inline void*
+zix_sorted_array_index_unchecked(const ZixSortedArray* a, size_t index)
+{
+ return (char*)a->array + (a->elem_size * index);
+}
+
+void*
+zix_sorted_array_index(const ZixSortedArray* a, size_t index)
+{
+ if (index >= a->num_elems) {
+ return NULL;
+ }
+
+ return zix_sorted_array_index_unchecked(a, index);
+}
+
+ZixStatus
+zix_sorted_array_find(const ZixSortedArray* a,
+ const void* e,
+ ZixSortedArrayIter* ai)
+{
+ intptr_t lower = 0;
+ intptr_t upper = a->num_elems - 1;
+ while (upper >= lower) {
+ const intptr_t i = lower + ((upper - lower) / 2);
+ void* const elem_i = zix_sorted_array_index_unchecked(a, i);
+ const int cmp = a->cmp(elem_i, e, a->cmp_data);
+
+ if (cmp == 0) {
+ *ai = elem_i;
+ return ZIX_STATUS_SUCCESS;
+ }
+
+ if (cmp > 0) {
+ upper = i - 1;
+ } else {
+ lower = i + 1;
+ }
+ }
+
+ *ai = zix_sorted_array_index_unchecked(a, lower);
+ return ZIX_STATUS_NOT_FOUND;
+}
+
+void*
+zix_sorted_array_get_data(ZixSortedArrayIter ai)
+{
+ return ai;
+}
+
+ZixSortedArrayIter
+zix_sorted_array_begin(ZixSortedArray* a)
+{
+ return a->array;
+}
+
+ZixSortedArrayIter
+zix_sorted_array_end(ZixSortedArray* a)
+{
+ return (char*)a->array + (a->elem_size * a->num_elems);
+}
+
+bool
+zix_sorted_array_iter_is_end(ZixSortedArray* a, ZixSortedArrayIter i)
+{
+ return i != zix_sorted_array_end(a);
+}
+
+ZixSortedArrayIter
+zix_sorted_array_iter_next(ZixSortedArray* a, ZixSortedArrayIter i)
+{
+ return (char*)i + a->elem_size;
+}
diff --git a/src/strindex.c b/src/strindex.c
new file mode 100644
index 0000000..8cb05c9
--- /dev/null
+++ b/src/strindex.c
@@ -0,0 +1,261 @@
+/*
+ Copyright 2011 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.
+ */
+
+#define _XOPEN_SOURCE 500
+
+#include "zix/strindex.h"
+
+#include "zix/common.h"
+
+#include <assert.h>
+#include <stdio.h>
+#include <stdlib.h>
+#include <string.h>
+
+typedef struct _ZixStrindexNode {
+ struct _ZixStrindexNode* children; /* Children of this node */
+ size_t num_children; /* Number of outgoing edges */
+ char* first; /* Start of this suffix */
+ char* label_first; /* Start of incoming label */
+ char* label_last; /* End of incoming label */
+} ZixStrindexNode;
+
+struct _ZixStrindex {
+ char* s; /* String contained in this tree */
+ ZixStrindexNode* root; /* Root of the tree */
+};
+
+static ZixStatus
+strindex_insert(ZixStrindexNode* n,
+ char* suffix_first,
+ char* first,
+ char* last);
+
+ZixStrindex*
+zix_strindex_new(const char* s)
+{
+ const size_t len = strlen(s);
+
+ ZixStrindex* t = (ZixStrindex*)malloc(sizeof(ZixStrindex));
+ memset(t, '\0', sizeof(struct _ZixStrindex));
+
+ t->s = (char*)calloc(1, len + 1);
+ memcpy(t->s, s, len);
+
+ t->root = (ZixStrindexNode*)malloc(sizeof(ZixStrindexNode));
+ memset(t->root, '\0', sizeof(ZixStrindexNode));
+ t->root->num_children = 0;
+ t->root->first = t->s;
+
+ for (size_t i = 0; i < len; ++i) {
+ strindex_insert(t->root, t->s + i, t->s + i, t->s + (len - 1));
+ }
+
+ return t;
+}
+
+static void
+zix_strindex_free_rec(ZixStrindexNode* n)
+{
+ if (n) {
+ for (size_t i = 0; i < n->num_children; ++i) {
+ zix_strindex_free_rec(&n->children[i]);
+ }
+
+ free(n->children);
+ }
+}
+
+void
+zix_strindex_free(ZixStrindex* strindex)
+{
+ zix_strindex_free_rec(strindex->root);
+ free(strindex->s);
+ free(strindex->root);
+ free(strindex);
+}
+
+static inline int
+strindex_is_leaf(ZixStrindexNode* n)
+{
+ return n->num_children == 0;
+}
+
+static int
+strindex_find_edge(ZixStrindexNode* n, char c, size_t* index)
+{
+ for (size_t i = 0; i < n->num_children; ++i) {
+ if (n->children[i].label_first[0] == c) {
+ *index = i;
+ return 1;
+ }
+ }
+
+ return 0;
+}
+
+static void
+strindex_add_edge(ZixStrindexNode* n,
+ char* suffix_first,
+ char* first,
+ char* last)
+{
+ assert(last > first);
+ n->children = (ZixStrindexNode*)realloc(
+ n->children, (n->num_children + 1) * sizeof(ZixStrindexNode));
+
+ memset(&n->children[n->num_children], '\0', sizeof(ZixStrindexNode));
+
+ n->children[n->num_children].first = suffix_first;
+ n->children[n->num_children].label_first = first;
+ n->children[n->num_children].label_last = last;
+ ++n->num_children;
+}
+
+/* Split an outgoing edge (to a child) at the given index */
+static void
+strindex_split_edge(ZixStrindexNode* child, size_t index)
+{
+ ZixStrindexNode* children = child->children;
+ size_t num_children = child->num_children;
+
+ char* first = child->label_first + index;
+ char* last = child->label_last;
+ assert(last > first);
+ assert(child->first);
+
+ child->children = (ZixStrindexNode*)malloc(sizeof(ZixStrindexNode));
+
+ child->children[0].children = children;
+ child->children[0].num_children = num_children;
+ child->children[0].first = child->first;
+ child->children[0].label_first = first;
+ child->children[0].label_last = last;
+
+ child->label_last = child->label_first + (index - 1); // chop end
+
+ child->num_children = 1;
+}
+
+static ZixStatus
+strindex_insert(ZixStrindexNode* n, char* suffix_first, char* first, char* last)
+{
+ size_t child_i;
+ ZixStrindexNode* child;
+ assert(first <= last);
+
+ if (strindex_find_edge(n, *first, &child_i)) {
+ char* label_first = n->children[child_i].label_first;
+ char* label_last = n->children[child_i].label_last;
+ size_t split_i = 0;
+ const size_t label_len = label_last - label_first + 1;
+ const size_t s_len = last - first + 1;
+ const size_t max_len = (s_len < label_len) ? s_len : label_len;
+
+ while (split_i < max_len && first[split_i] == label_first[split_i]) {
+ ++split_i;
+ }
+ child = n->children + child_i;
+
+ if (label_len < s_len) {
+ if (split_i == label_len) {
+ strindex_insert(child, suffix_first, first + label_len, last);
+ } else {
+ strindex_split_edge(child, split_i);
+ strindex_insert(child, suffix_first, first + split_i, last);
+ }
+ } else if ((label_len != split_i) && (label_len != s_len)) {
+ strindex_split_edge(child, split_i);
+ if (split_i != s_len) {
+ strindex_add_edge(child, suffix_first, first + split_i, last);
+ }
+ }
+ } else {
+ strindex_add_edge(n, suffix_first, first, last);
+ }
+
+ return ZIX_STATUS_SUCCESS;
+}
+
+ZixStatus
+zix_strindex_find(ZixStrindex* strindex, const char* const str, char** match)
+{
+ const char* p = str;
+
+#ifndef NDEBUG
+ const char* orig_p = p;
+#endif
+
+ ZixStrindexNode* n = strindex->root;
+ size_t child_i;
+
+ *match = NULL;
+
+ while (*p != '\0') {
+ size_t p_len = strlen(p);
+ if (strindex_find_edge(n, p[0], &child_i)) {
+ char* label_first = n->children[child_i].label_first;
+ char* label_last = n->children[child_i].label_last;
+ size_t label_len = label_last - label_first + 1;
+ size_t max_len = (p_len < label_len) ? p_len : label_len;
+ assert(child_i <= n->num_children);
+ assert(max_len > 0);
+
+ /* Set match to the start of substring
+ (but may not actually be a complete match yet)
+ */
+ if (*match == NULL) {
+ assert(p[0] == orig_p[0]);
+ assert(orig_p[0] == label_first[0]);
+ *match = n->children[child_i].first;
+ assert((*match)[0] == orig_p[0]);
+ }
+
+ if (strncmp(p, label_first, max_len)) {
+ /* no match */
+ *match = NULL;
+ return ZIX_STATUS_NOT_FOUND;
+ }
+
+ if (p_len <= label_len) {
+ /* At the last node, match */
+ *match = n->children[child_i].first;
+ assert(!strncmp(*match, orig_p, strlen(orig_p)));
+ return ZIX_STATUS_SUCCESS;
+ }
+
+ if (strindex_is_leaf(n)) {
+ /* Hit leaf early, no match */
+ return ZIX_STATUS_NOT_FOUND;
+ }
+
+ /* Match at this node, continue search downwards (or match) */
+ p += label_len;
+ n = &n->children[child_i];
+ if (label_len >= p_len) {
+ assert(strstr(strindex->s, orig_p) != NULL);
+ assert(strncmp(orig_p, *match, max_len));
+ return ZIX_STATUS_SUCCESS;
+ }
+
+ } else {
+ assert(strstr(strindex->s, orig_p) == NULL);
+ return ZIX_STATUS_NOT_FOUND;
+ }
+ }
+
+ return ZIX_STATUS_NOT_FOUND;
+}
diff --git a/src/tree.c b/src/tree.c
new file mode 100644
index 0000000..a204baf
--- /dev/null
+++ b/src/tree.c
@@ -0,0 +1,735 @@
+/*
+ Copyright 2011-2014 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/tree.h"
+
+#include "zix/common.h"
+
+#include <assert.h>
+#include <stdint.h>
+#include <stdlib.h>
+#include <string.h>
+
+typedef struct ZixTreeNodeImpl ZixTreeNode;
+
+struct ZixTreeImpl {
+ ZixTreeNode* root;
+ ZixDestroyFunc destroy;
+ ZixComparator cmp;
+ void* cmp_data;
+ size_t size;
+ bool allow_duplicates;
+};
+
+struct ZixTreeNodeImpl {
+ void* data;
+ struct ZixTreeNodeImpl* left;
+ struct ZixTreeNodeImpl* right;
+ struct ZixTreeNodeImpl* parent;
+ int_fast8_t balance;
+};
+
+#define MIN(a, b) (((a) < (b)) ? (a) : (b))
+#define MAX(a, b) (((a) > (b)) ? (a) : (b))
+
+// Uncomment these for debugging features
+// #define ZIX_TREE_DUMP 1
+// #define ZIX_TREE_VERIFY 1
+// #define ZIX_TREE_HYPER_VERIFY 1
+
+#if defined(ZIX_TREE_VERIFY) || defined(ZIX_TREE_HYPER_VERIFY)
+# include "tree_debug.h"
+# define ASSERT_BALANCE(n) assert(verify_balance(n))
+#else
+# define ASSERT_BALANCE(n)
+#endif
+
+#ifdef ZIX_TREE_DUMP
+# include "tree_debug.h"
+# define DUMP(t) zix_tree_print(t->root, 0)
+# define DEBUG_PRINTF(fmt, ...) printf(fmt, __VA_ARGS__)
+#else
+# define DUMP(t)
+# define DEBUG_PRINTF(fmt, ...)
+#endif
+
+ZixTree*
+zix_tree_new(bool allow_duplicates,
+ ZixComparator cmp,
+ void* cmp_data,
+ ZixDestroyFunc destroy)
+{
+ ZixTree* t = (ZixTree*)malloc(sizeof(ZixTree));
+ t->root = NULL;
+ t->destroy = destroy;
+ t->cmp = cmp;
+ t->cmp_data = cmp_data;
+ t->size = 0;
+ t->allow_duplicates = allow_duplicates;
+ return t;
+}
+
+ZIX_PRIVATE
+void
+zix_tree_free_rec(ZixTree* t, ZixTreeNode* n)
+{
+ if (n) {
+ zix_tree_free_rec(t, n->left);
+ zix_tree_free_rec(t, n->right);
+ if (t->destroy) {
+ t->destroy(n->data);
+ }
+ free(n);
+ }
+}
+
+void
+zix_tree_free(ZixTree* t)
+{
+ if (t) {
+ zix_tree_free_rec(t, t->root);
+ free(t);
+ }
+}
+
+size_t
+zix_tree_size(const ZixTree* t)
+{
+ return t->size;
+}
+
+ZIX_PRIVATE
+void
+rotate(ZixTreeNode* p, ZixTreeNode* q)
+{
+ assert(q->parent == p);
+ assert(p->left == q || p->right == q);
+
+ q->parent = p->parent;
+ if (q->parent) {
+ if (q->parent->left == p) {
+ q->parent->left = q;
+ } else {
+ q->parent->right = q;
+ }
+ }
+
+ if (p->right == q) {
+ // Rotate left
+ p->right = q->left;
+ q->left = p;
+ if (p->right) {
+ p->right->parent = p;
+ }
+ } else {
+ // Rotate right
+ assert(p->left == q);
+ p->left = q->right;
+ q->right = p;
+ if (p->left) {
+ p->left->parent = p;
+ }
+ }
+
+ p->parent = q;
+}
+
+/**
+ * Rotate left about `p`.
+ *
+ * p q
+ * / \ / \
+ * A q => p C
+ * / \ / \
+ * B C A B
+ */
+ZIX_PRIVATE
+ZixTreeNode*
+rotate_left(ZixTreeNode* p, int* height_change)
+{
+ ZixTreeNode* const q = p->right;
+ *height_change = (q->balance == 0) ? 0 : -1;
+
+ DEBUG_PRINTF("LL %ld\n", (intptr_t)p->data);
+
+ assert(p->balance == 2);
+ assert(q->balance == 0 || q->balance == 1);
+
+ rotate(p, q);
+
+ // p->balance -= 1 + MAX(0, q->balance);
+ // q->balance -= 1 - MIN(0, p->balance);
+ --q->balance;
+ p->balance = -(q->balance);
+
+ ASSERT_BALANCE(p);
+ ASSERT_BALANCE(q);
+ return q;
+}
+
+/**
+ * Rotate right about `p`.
+ *
+ * p q
+ * / \ / \
+ * q C => A p
+ * / \ / \
+ * A B B C
+ *
+ */
+ZIX_PRIVATE
+ZixTreeNode*
+rotate_right(ZixTreeNode* p, int* height_change)
+{
+ ZixTreeNode* const q = p->left;
+ *height_change = (q->balance == 0) ? 0 : -1;
+
+ DEBUG_PRINTF("RR %ld\n", (intptr_t)p->data);
+
+ assert(p->balance == -2);
+ assert(q->balance == 0 || q->balance == -1);
+
+ rotate(p, q);
+
+ // p->balance += 1 - MIN(0, q->balance);
+ // q->balance += 1 + MAX(0, p->balance);
+ ++q->balance;
+ p->balance = -(q->balance);
+
+ ASSERT_BALANCE(p);
+ ASSERT_BALANCE(q);
+ return q;
+}
+
+/**
+ * Rotate left about `p->left` then right about `p`.
+ *
+ * p r
+ * / \ / \
+ * q D => q p
+ * / \ / \ / \
+ * A r A B C D
+ * / \
+ * B C
+ *
+ */
+ZIX_PRIVATE
+ZixTreeNode*
+rotate_left_right(ZixTreeNode* p, int* height_change)
+{
+ ZixTreeNode* const q = p->left;
+ ZixTreeNode* const r = q->right;
+
+ assert(p->balance == -2);
+ assert(q->balance == 1);
+ assert(r->balance == -1 || r->balance == 0 || r->balance == 1);
+
+ DEBUG_PRINTF("LR %ld P: %2d Q: %2d R: %2d\n",
+ (intptr_t)p->data,
+ p->balance,
+ q->balance,
+ r->balance);
+
+ rotate(q, r);
+ rotate(p, r);
+
+ q->balance -= 1 + MAX(0, r->balance);
+ p->balance += 1 - MIN(MIN(0, r->balance) - 1, r->balance + q->balance);
+ // r->balance += MAX(0, p->balance) + MIN(0, q->balance);
+
+ // p->balance = (p->left && p->right) ? -MIN(r->balance, 0) : 0;
+ // q->balance = - MAX(r->balance, 0);
+ r->balance = 0;
+
+ *height_change = -1;
+
+ ASSERT_BALANCE(p);
+ ASSERT_BALANCE(q);
+ ASSERT_BALANCE(r);
+ return r;
+}
+
+/**
+ * Rotate right about `p->right` then right about `p`.
+ *
+ * p r
+ * / \ / \
+ * A q => p q
+ * / \ / \ / \
+ * r D A B C D
+ * / \
+ * B C
+ *
+ */
+ZIX_PRIVATE
+ZixTreeNode*
+rotate_right_left(ZixTreeNode* p, int* height_change)
+{
+ ZixTreeNode* const q = p->right;
+ ZixTreeNode* const r = q->left;
+
+ assert(p->balance == 2);
+ assert(q->balance == -1);
+ assert(r->balance == -1 || r->balance == 0 || r->balance == 1);
+
+ DEBUG_PRINTF("RL %ld P: %2d Q: %2d R: %2d\n",
+ (intptr_t)p->data,
+ p->balance,
+ q->balance,
+ r->balance);
+
+ rotate(q, r);
+ rotate(p, r);
+
+ q->balance += 1 - MIN(0, r->balance);
+ p->balance -= 1 + MAX(MAX(0, r->balance) + 1, r->balance + q->balance);
+ // r->balance += MAX(0, q->balance) + MIN(0, p->balance);
+
+ // p->balance = (p->left && p->right) ? -MAX(r->balance, 0) : 0;
+ // q->balance = - MIN(r->balance, 0);
+ r->balance = 0;
+ // assert(r->balance == 0);
+
+ *height_change = -1;
+
+ ASSERT_BALANCE(p);
+ ASSERT_BALANCE(q);
+ ASSERT_BALANCE(r);
+ return r;
+}
+
+ZIX_PRIVATE
+ZixTreeNode*
+zix_tree_rebalance(ZixTree* t, ZixTreeNode* node, int* height_change)
+{
+#ifdef ZIX_TREE_HYPER_VERIFY
+ const size_t old_height = height(node);
+#endif
+ DEBUG_PRINTF("REBALANCE %ld (%d)\n", (intptr_t)node->data, node->balance);
+ *height_change = 0;
+ const bool is_root = !node->parent;
+ assert((is_root && t->root == node) || (!is_root && t->root != node));
+ ZixTreeNode* replacement = node;
+ if (node->balance == -2) {
+ assert(node->left);
+ if (node->left->balance == 1) {
+ replacement = rotate_left_right(node, height_change);
+ } else {
+ replacement = rotate_right(node, height_change);
+ }
+ } else if (node->balance == 2) {
+ assert(node->right);
+ if (node->right->balance == -1) {
+ replacement = rotate_right_left(node, height_change);
+ } else {
+ replacement = rotate_left(node, height_change);
+ }
+ }
+ if (is_root) {
+ assert(!replacement->parent);
+ t->root = replacement;
+ }
+ DUMP(t);
+#ifdef ZIX_TREE_HYPER_VERIFY
+ assert(old_height + *height_change == height(replacement));
+#endif
+ return replacement;
+}
+
+ZixStatus
+zix_tree_insert(ZixTree* t, void* e, ZixTreeIter** ti)
+{
+ DEBUG_PRINTF("**** INSERT %ld\n", (intptr_t)e);
+ int cmp = 0;
+ ZixTreeNode* n = t->root;
+ ZixTreeNode* p = NULL;
+
+ // Find the parent p of e
+ while (n) {
+ p = n;
+ cmp = t->cmp(e, n->data, t->cmp_data);
+ if (cmp < 0) {
+ n = n->left;
+ } else if (cmp > 0 || t->allow_duplicates) {
+ n = n->right;
+ } else {
+ if (ti) {
+ *ti = n;
+ }
+ DEBUG_PRINTF("%ld EXISTS!\n", (intptr_t)e);
+ return ZIX_STATUS_EXISTS;
+ }
+ }
+
+ // Allocate a new node n
+ if (!(n = (ZixTreeNode*)malloc(sizeof(ZixTreeNode)))) {
+ return ZIX_STATUS_NO_MEM;
+ }
+ memset(n, '\0', sizeof(ZixTreeNode));
+ n->data = e;
+ n->balance = 0;
+ if (ti) {
+ *ti = n;
+ }
+
+ bool p_height_increased = false;
+
+ // Make p the parent of n
+ n->parent = p;
+ if (!p) {
+ t->root = n;
+ } else {
+ if (cmp < 0) {
+ assert(!p->left);
+ assert(p->balance == 0 || p->balance == 1);
+ p->left = n;
+ --p->balance;
+ p_height_increased = !p->right;
+ } else {
+ assert(!p->right);
+ assert(p->balance == 0 || p->balance == -1);
+ p->right = n;
+ ++p->balance;
+ p_height_increased = !p->left;
+ }
+ }
+
+ DUMP(t);
+
+ // Rebalance if necessary (at most 1 rotation)
+ assert(!p || p->balance == -1 || p->balance == 0 || p->balance == 1);
+ if (p && p_height_increased) {
+ int height_change = 0;
+ for (ZixTreeNode* i = p; i && i->parent; i = i->parent) {
+ if (i == i->parent->left) {
+ if (--i->parent->balance == -2) {
+ zix_tree_rebalance(t, i->parent, &height_change);
+ break;
+ }
+ } else {
+ assert(i == i->parent->right);
+ if (++i->parent->balance == 2) {
+ zix_tree_rebalance(t, i->parent, &height_change);
+ break;
+ }
+ }
+
+ if (i->parent->balance == 0) {
+ break;
+ }
+ }
+ }
+
+ DUMP(t);
+
+ ++t->size;
+
+#ifdef ZIX_TREE_VERIFY
+ if (!verify(t, t->root)) {
+ return ZIX_STATUS_ERROR;
+ }
+#endif
+
+ return ZIX_STATUS_SUCCESS;
+}
+
+ZixStatus
+zix_tree_remove(ZixTree* t, ZixTreeIter* ti)
+{
+ ZixTreeNode* const n = ti;
+ ZixTreeNode** pp = NULL; // parent pointer
+ ZixTreeNode* to_balance = n->parent; // lowest node to balance
+ int8_t d_balance = 0; // delta(balance) for n->parent
+
+ DEBUG_PRINTF("*** REMOVE %ld\n", (intptr_t)n->data);
+
+ if ((n == t->root) && !n->left && !n->right) {
+ t->root = NULL;
+ if (t->destroy) {
+ t->destroy(n->data);
+ }
+ free(n);
+ --t->size;
+ assert(t->size == 0);
+ return ZIX_STATUS_SUCCESS;
+ }
+
+ // Set pp to the parent pointer to n, if applicable
+ if (n->parent) {
+ assert(n->parent->left == n || n->parent->right == n);
+ if (n->parent->left == n) { // n is left child
+ pp = &n->parent->left;
+ d_balance = 1;
+ } else { // n is right child
+ assert(n->parent->right == n);
+ pp = &n->parent->right;
+ d_balance = -1;
+ }
+ }
+
+ assert(!pp || *pp == n);
+
+ int height_change = 0;
+ if (!n->left && !n->right) {
+ // n is a leaf, just remove it
+ if (pp) {
+ *pp = NULL;
+ to_balance = n->parent;
+ height_change = (!n->parent->left && !n->parent->right) ? -1 : 0;
+ }
+
+ } else if (!n->left) {
+ // Replace n with right (only) child
+ if (pp) {
+ *pp = n->right;
+ to_balance = n->parent;
+ } else {
+ t->root = n->right;
+ }
+ n->right->parent = n->parent;
+ height_change = -1;
+
+ } else if (!n->right) {
+ // Replace n with left (only) child
+ if (pp) {
+ *pp = n->left;
+ to_balance = n->parent;
+ } else {
+ t->root = n->left;
+ }
+ n->left->parent = n->parent;
+ height_change = -1;
+
+ } else {
+ // Replace n with in-order successor (leftmost child of right subtree)
+ ZixTreeNode* replace = n->right;
+ while (replace->left) {
+ assert(replace->left->parent == replace);
+ replace = replace->left;
+ }
+
+ // Remove replace from parent (replace_p)
+ if (replace->parent->left == replace) {
+ height_change = replace->parent->right ? 0 : -1;
+ d_balance = 1;
+ to_balance = replace->parent;
+ replace->parent->left = replace->right;
+ } else {
+ assert(replace->parent == n);
+ height_change = replace->parent->left ? 0 : -1;
+ d_balance = -1;
+ to_balance = replace->parent;
+ replace->parent->right = replace->right;
+ }
+
+ if (to_balance == n) {
+ to_balance = replace;
+ }
+
+ if (replace->right) {
+ replace->right->parent = replace->parent;
+ }
+
+ replace->balance = n->balance;
+
+ // Swap node to delete with replace
+ if (pp) {
+ *pp = replace;
+ } else {
+ assert(t->root == n);
+ t->root = replace;
+ }
+
+ replace->parent = n->parent;
+ replace->left = n->left;
+ n->left->parent = replace;
+ replace->right = n->right;
+ if (n->right) {
+ n->right->parent = replace;
+ }
+
+ assert(!replace->parent || replace->parent->left == replace ||
+ replace->parent->right == replace);
+ }
+
+ // Rebalance starting at to_balance upwards.
+ for (ZixTreeNode* i = to_balance; i; i = i->parent) {
+ i->balance += d_balance;
+ if (d_balance == 0 || i->balance == -1 || i->balance == 1) {
+ break;
+ }
+
+ assert(i != n);
+ i = zix_tree_rebalance(t, i, &height_change);
+ if (i->balance == 0) {
+ height_change = -1;
+ }
+
+ if (i->parent) {
+ if (i == i->parent->left) {
+ d_balance = (uint8_t)height_change * -1;
+ } else {
+ assert(i == i->parent->right);
+ d_balance = (uint8_t)height_change;
+ }
+ }
+ }
+
+ DUMP(t);
+
+ if (t->destroy) {
+ t->destroy(n->data);
+ }
+ free(n);
+
+ --t->size;
+
+#ifdef ZIX_TREE_VERIFY
+ if (!verify(t, t->root)) {
+ return ZIX_STATUS_ERROR;
+ }
+#endif
+
+ return ZIX_STATUS_SUCCESS;
+}
+
+ZixStatus
+zix_tree_find(const ZixTree* t, const void* e, ZixTreeIter** ti)
+{
+ ZixTreeNode* n = t->root;
+ while (n) {
+ const int cmp = t->cmp(e, n->data, t->cmp_data);
+ if (cmp == 0) {
+ break;
+ }
+
+ if (cmp < 0) {
+ n = n->left;
+ } else {
+ n = n->right;
+ }
+ }
+
+ *ti = n;
+ return (n) ? ZIX_STATUS_SUCCESS : ZIX_STATUS_NOT_FOUND;
+}
+
+void*
+zix_tree_get(const ZixTreeIter* ti)
+{
+ return ti ? ti->data : NULL;
+}
+
+ZixTreeIter*
+zix_tree_begin(ZixTree* t)
+{
+ if (!t->root) {
+ return NULL;
+ }
+
+ ZixTreeNode* n = t->root;
+ while (n->left) {
+ n = n->left;
+ }
+
+ return n;
+}
+
+ZixTreeIter*
+zix_tree_end(ZixTree* ZIX_UNUSED(t))
+{
+ return NULL;
+}
+
+ZixTreeIter*
+zix_tree_rbegin(ZixTree* t)
+{
+ if (!t->root) {
+ return NULL;
+ }
+
+ ZixTreeNode* n = t->root;
+ while (n->right) {
+ n = n->right;
+ }
+
+ return n;
+}
+
+ZixTreeIter*
+zix_tree_rend(ZixTree* ZIX_UNUSED(t))
+{
+ return NULL;
+}
+
+bool
+zix_tree_iter_is_end(const ZixTreeIter* i)
+{
+ return !i;
+}
+
+bool
+zix_tree_iter_is_rend(const ZixTreeIter* i)
+{
+ return !i;
+}
+
+ZixTreeIter*
+zix_tree_iter_next(ZixTreeIter* i)
+{
+ if (!i) {
+ return NULL;
+ }
+
+ if (i->right) {
+ i = i->right;
+ while (i->left) {
+ i = i->left;
+ }
+ } else {
+ while (i->parent && i->parent->right == i) { // i is a right child
+ i = i->parent;
+ }
+
+ i = i->parent;
+ }
+
+ return i;
+}
+
+ZixTreeIter*
+zix_tree_iter_prev(ZixTreeIter* i)
+{
+ if (!i) {
+ return NULL;
+ }
+
+ if (i->left) {
+ i = i->left;
+ while (i->right) {
+ i = i->right;
+ }
+
+ } else {
+ while (i->parent && i->parent->left == i) { // i is a left child
+ i = i->parent;
+ }
+
+ i = i->parent;
+ }
+
+ return i;
+}
diff --git a/src/tree_debug.h b/src/tree_debug.h
new file mode 100644
index 0000000..68e37b6
--- /dev/null
+++ b/src/tree_debug.h
@@ -0,0 +1,175 @@
+/*
+ Copyright 2011 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_TREE_DEBUG_H
+#define ZIX_TREE_DEBUG_H
+
+#include <inttypes.h>
+
+#ifdef ZIX_TREE_DUMP
+static void
+zix_tree_print(ZixTreeNode* node, int level)
+{
+ if (node) {
+ if (!node->parent) {
+ printf("{{{\n");
+ }
+
+ zix_tree_print(node->right, level + 1);
+ for (int i = 0; i < level; i++) {
+ printf(" ");
+ }
+
+ printf("%ld.%d\n", (intptr_t)node->data, node->balance);
+ zix_tree_print(node->left, level + 1);
+ if (!node->parent) {
+ printf("}}}\n");
+ }
+ }
+}
+#endif
+
+#ifdef ZIX_TREE_HYPER_VERIFY
+static size_t
+height(ZixTreeNode* n)
+{
+ if (!n) {
+ return 0;
+ } else {
+ return 1 + MAX(height(n->left), height(n->right));
+ }
+}
+#endif
+
+#if defined(ZIX_TREE_VERIFY) || !defined(NDEBUG)
+static bool
+verify_balance(ZixTreeNode* n)
+{
+ if (!n) {
+ return true;
+ }
+
+ if (n->balance < -2 || n->balance > 2) {
+ fprintf(stderr,
+ "Balance out of range : %ld (balance %d)\n",
+ (intptr_t)n->data,
+ n->balance);
+ return false;
+ }
+
+ if (n->balance < 0 && !n->left) {
+ fprintf(stderr,
+ "Bad balance : %ld (balance %d) has no left child\n",
+ (intptr_t)n->data,
+ n->balance);
+ return false;
+ }
+
+ if (n->balance > 0 && !n->right) {
+ fprintf(stderr,
+ "Bad balance : %ld (balance %d) has no right child\n",
+ (intptr_t)n->data,
+ n->balance);
+ return false;
+ }
+
+ if (n->balance != 0 && !n->left && !n->right) {
+ fprintf(stderr,
+ "Bad balance : %ld (balance %d) has no children\n",
+ (intptr_t)n->data,
+ n->balance);
+ return false;
+ }
+
+# ifdef ZIX_TREE_HYPER_VERIFY
+ const intptr_t left_height = (intptr_t)height(n->left);
+ const intptr_t right_height = (intptr_t)height(n->right);
+ if (n->balance != right_height - left_height) {
+ fprintf(stderr,
+ "Bad balance at %ld: h_r (%" PRIdPTR ")"
+ "- l_h (%" PRIdPTR ") != %d\n",
+ (intptr_t)n->data,
+ right_height,
+ left_height,
+ n->balance);
+ assert(false);
+ return false;
+ }
+# endif
+
+ return true;
+}
+#endif
+
+#ifdef ZIX_TREE_VERIFY
+static bool
+verify(ZixTree* t, ZixTreeNode* n)
+{
+ if (!n) {
+ return true;
+ }
+
+ if (n->parent) {
+ if ((n->parent->left != n) && (n->parent->right != n)) {
+ fprintf(stderr, "Corrupt child/parent pointers\n");
+ return false;
+ }
+ }
+
+ if (n->left) {
+ if (t->cmp(n->left->data, n->data, t->cmp_data) > 0) {
+ fprintf(
+ stderr, "Bad order: %" PRIdPTR " with left child\n", (intptr_t)n->data);
+ fprintf(stderr, "%p ? %p\n", (void*)n, (void*)n->left);
+ fprintf(stderr,
+ "%" PRIdPTR " ? %" PRIdPTR "\n",
+ (intptr_t)n->data,
+ (intptr_t)n->left->data);
+ return false;
+ }
+
+ if (!verify(t, n->left)) {
+ return false;
+ }
+ }
+
+ if (n->right) {
+ if (t->cmp(n->right->data, n->data, t->cmp_data) < 0) {
+ fprintf(stderr,
+ "Bad order: %" PRIdPTR " with right child\n",
+ (intptr_t)n->data);
+ return false;
+ }
+
+ if (!verify(t, n->right)) {
+ return false;
+ }
+ }
+
+ if (!verify_balance(n)) {
+ return false;
+ }
+
+ if (n->balance <= -2 || n->balance >= 2) {
+ fprintf(stderr, "Imbalance: %p (balance %d)\n", (void*)n, n->balance);
+ return false;
+ }
+
+ return true;
+}
+#endif
+
+#endif // ZIX_TREE_DEBUG_H
generated by cgit v1.2.1 (git 2.18.0) at 2025-02-10 04:55:42 +0000