Reduce memory usage and increase performance with a better data structure.

git-svn-id: http://svn.drobilla.net/sord/trunk@307 3d64ff67-21c5-427c-a301-fe4f08042e5a

8 files changed, 904 insertions, 954 deletions

diff --git a/src/sord.c b/src/sord.c
index cdfef62..9b4a11a 100644
--- a/src/sord.c
+++ b/src/sord.c
@@ -25,7 +25,7 @@
 #define ZIX_INLINE
 #include "zix/digest.c"
 #include "zix/hash.c"
-#include "zix/tree.c"
+#include "zix/btree.c"
 
 #include "sord_config.h"
 #include "sord_internal.h"
@@ -116,7 +116,7 @@ struct SordModelImpl {
 	/** Index for each possible triple ordering (may or may not exist).
 	 * Each index is a tree of SordQuad with the appropriate ordering.
 	 */
-	ZixTree* indices[NUM_ORDERS];
+	ZixBTree* indices[NUM_ORDERS];
 
 	size_t n_quads;
 };
@@ -133,7 +133,7 @@ typedef enum {
 /** Iterator over some range of a store */
 struct SordIterImpl {
 	const SordModel* sord;               ///< Model being iterated over
-	ZixTreeIter*     cur;                ///< Current DB cursor
+	ZixBTreeIter*    cur;                ///< Current DB cursor
 	SordQuad         pat;                ///< Pattern (in ordering order)
 	int              ordering[TUP_LEN];  ///< Store ordering
 	SearchMode       mode;               ///< Iteration mode
@@ -316,18 +316,18 @@ static inline bool
 sord_iter_forward(SordIter* iter)
 {
 	if (!iter->skip_graphs) {
-		iter->cur = zix_tree_iter_next(iter->cur);
-		return zix_tree_iter_is_end(iter->cur);
+		zix_btree_iter_increment(iter->cur);
+		return zix_btree_iter_is_end(iter->cur);
 	}
 
-	SordNode** key = (SordNode**)zix_tree_get(iter->cur);
+	SordNode** key = (SordNode**)zix_btree_get(iter->cur);
 	const SordQuad initial = { key[0], key[1], key[2], key[3] };
 	while (true) {
-		iter->cur = zix_tree_iter_next(iter->cur);
-		if (zix_tree_iter_is_end(iter->cur))
+		zix_btree_iter_increment(iter->cur);
+		if (zix_btree_iter_is_end(iter->cur))
 			return true;
 
-		key = (SordNode**)zix_tree_get(iter->cur);
+		key = (SordNode**)zix_btree_get(iter->cur);
 		for (int i = 0; i < 3; ++i)
 			if (key[i] != initial[i])
 				return false;
@@ -343,9 +343,9 @@ static inline bool
 sord_iter_seek_match(SordIter* iter)
 {
 	for (iter->end = true;
-	     !zix_tree_iter_is_end(iter->cur);
+	     !zix_btree_iter_is_end(iter->cur);
 	     sord_iter_forward(iter)) {
-		const SordNode** const key = (const SordNode**)zix_tree_get(iter->cur);
+		const SordNode** const key = (const SordNode**)zix_btree_get(iter->cur);
 		if (sord_quad_match_inline(key, iter->pat))
 			return (iter->end = false);
 	}
@@ -364,7 +364,7 @@ sord_iter_seek_match_range(SordIter* iter)
 		return true;
 
 	do {
-		const SordNode** key = (const SordNode**)zix_tree_get(iter->cur);
+		const SordNode** key = (const SordNode**)zix_btree_get(iter->cur);
 
 		if (sord_quad_match_inline(key, iter->pat))
 			return false;  // Found match
@@ -382,7 +382,7 @@ sord_iter_seek_match_range(SordIter* iter)
 }
 
 static SordIter*
-sord_iter_new(const SordModel* sord, ZixTreeIter* cur, const SordQuad pat,
+sord_iter_new(const SordModel* sord, ZixBTreeIter* cur, const SordQuad pat,
               SordOrder order, SearchMode mode, int n_prefix)
 {
 	const int* ordering = orderings[order];
@@ -404,7 +404,7 @@ sord_iter_new(const SordModel* sord, ZixTreeIter* cur, const SordQuad pat,
 	case SINGLE:
 	case RANGE:
 		assert(
-			sord_quad_match_inline((const SordNode**)zix_tree_get(iter->cur),
+			sord_quad_match_inline((const SordNode**)zix_btree_get(iter->cur),
 			                       iter->pat));
 		break;
 	case FILTER_RANGE:
@@ -434,7 +434,7 @@ sord_iter_get_model(SordIter* iter)
 void
 sord_iter_get(const SordIter* iter, SordQuad id)
 {
-	SordNode** key = (SordNode**)zix_tree_get(iter->cur);
+	SordNode** key = (SordNode**)zix_btree_get(iter->cur);
 	for (int i = 0; i < TUP_LEN; ++i) {
 		id[i] = key[i];
 	}
@@ -443,7 +443,7 @@ sord_iter_get(const SordIter* iter, SordQuad id)
 const SordNode*
 sord_iter_get_node(const SordIter* iter, SordQuadIndex index)
 {
-	return iter ? ((SordNode**)zix_tree_get(iter->cur))[index] : NULL;
+	return iter ? ((SordNode**)zix_btree_get(iter->cur))[index] : NULL;
 }
 
 bool
@@ -466,7 +466,7 @@ sord_iter_next(SordIter* iter)
 		case RANGE:
 			SORD_ITER_LOG("%p range next\n", (void*)iter);
 			// At the end if the MSNs no longer match
-			key = (const SordNode**)zix_tree_get(iter->cur);
+			key = (const SordNode**)zix_btree_get(iter->cur);
 			assert(key);
 			for (int i = 0; i < iter->n_prefix; ++i) {
 				const int idx = iter->ordering[i];
@@ -515,6 +515,7 @@ sord_iter_free(SordIter* iter)
 {
 	SORD_ITER_LOG("%p Free\n", (void*)iter);
 	if (iter) {
+		zix_btree_iter_free(iter->cur);
 		free(iter);
 	}
 }
@@ -637,11 +638,11 @@ sord_new(SordWorld* world, unsigned indices, bool graphs)
 		const int* const g_ordering = orderings[i + (NUM_ORDERS / 2)];
 
 		if (indices & (1 << i)) {
-			sord->indices[i] = zix_tree_new(
-				false, sord_quad_compare, (void*)ordering, NULL);
+			sord->indices[i] = zix_btree_new(
+				sord_quad_compare, (void*)ordering, NULL);
 			if (graphs) {
-				sord->indices[i + (NUM_ORDERS / 2)] = zix_tree_new(
-					false, sord_quad_compare, (void*)g_ordering, NULL);
+				sord->indices[i + (NUM_ORDERS / 2)] = zix_btree_new(
+					sord_quad_compare, (void*)g_ordering, NULL);
 			} else {
 				sord->indices[i + (NUM_ORDERS / 2)] = NULL;
 			}
@@ -652,12 +653,12 @@ sord_new(SordWorld* world, unsigned indices, bool graphs)
 	}
 
 	if (!sord->indices[DEFAULT_ORDER]) {
-		sord->indices[DEFAULT_ORDER] = zix_tree_new(
-			false, sord_quad_compare, (void*)orderings[DEFAULT_ORDER], NULL);
+		sord->indices[DEFAULT_ORDER] = zix_btree_new(
+			sord_quad_compare, (void*)orderings[DEFAULT_ORDER], NULL);
 	}
 	if (graphs && !sord->indices[DEFAULT_GRAPH_ORDER]) {
-		sord->indices[DEFAULT_GRAPH_ORDER] = zix_tree_new(
-			false, sord_quad_compare, (void*)orderings[DEFAULT_GRAPH_ORDER], NULL);
+		sord->indices[DEFAULT_GRAPH_ORDER] = zix_btree_new(
+			sord_quad_compare, (void*)orderings[DEFAULT_GRAPH_ORDER], NULL);
 	}
 
 	return sord;
@@ -727,16 +728,16 @@ sord_free(SordModel* sord)
 	sord_iter_free(i);
 
 	// Free quads
-	for (ZixTreeIter* t = zix_tree_begin(sord->indices[DEFAULT_ORDER]);
-	     !zix_tree_iter_is_end(t);
-	     t = zix_tree_iter_next(t)) {
-		free(zix_tree_get(t));
+	ZixBTreeIter* t = zix_btree_begin(sord->indices[DEFAULT_ORDER]);
+	for (; !zix_btree_iter_is_end(t); zix_btree_iter_increment(t)) {
+		free(zix_btree_get(t));
 	}
+	zix_btree_iter_free(t);
 
 	// Free indices
 	for (unsigned o = 0; o < NUM_ORDERS; ++o)
 		if (sord->indices[o])
-			zix_tree_free(sord->indices[o]);
+			zix_btree_free(sord->indices[o]);
 
 	free(sord);
 }
@@ -765,46 +766,12 @@ sord_begin(const SordModel* sord)
 	if (sord_num_quads(sord) == 0) {
 		return NULL;
 	} else {
-		ZixTreeIter* cur = zix_tree_begin(sord->indices[DEFAULT_ORDER]);
+		ZixBTreeIter* cur = zix_btree_begin(sord->indices[DEFAULT_ORDER]);
 		SordQuad pat = { 0, 0, 0, 0 };
 		return sord_iter_new(sord, cur, pat, DEFAULT_ORDER, ALL, 0);
 	}
 }
 
-static inline ZixTreeIter*
-index_search(ZixTree* db, const SordQuad search_key)
-{
-	ZixTreeIter* iter = NULL;
-	zix_tree_find(db, (const void*)search_key, &iter);
-	return iter;
-}
-
-static inline ZixTreeIter*
-index_lower_bound(ZixTree* db, const SordQuad search_key)
-{
-	ZixTreeIter* iter = NULL;
-	zix_tree_find(db, (const void*)search_key, &iter);
-	if (!iter) {
-		return NULL;
-	}
-
-	ZixTreeIter* prev = NULL;
-	while ((prev = zix_tree_iter_prev(iter))) {
-		if (!prev) {
-			return iter;
-		}
-
-		const SordNode** const key = (const SordNode**)zix_tree_get(prev);
-		if (!sord_quad_match_inline(key, search_key)) {
-			return iter;
-		}
-
-		iter = prev;
-	}
-
-	return iter;
-}
-
 SordIter*
 sord_find(SordModel* sord, const SordQuad pat)
 {
@@ -821,16 +788,19 @@ sord_find(SordModel* sord, const SordQuad pat)
 	if (pat[0] && pat[1] && pat[2] && pat[3])
 		mode = SINGLE;  // No duplicate quads (Sord is a set)
 
-	ZixTree* const     db  = sord->indices[index_order];
-	ZixTreeIter* const cur = index_lower_bound(db, pat);
-	if (zix_tree_iter_is_end(cur)) {
+	ZixBTree* const db  = sord->indices[index_order];
+	ZixBTreeIter*   cur = NULL;
+	zix_btree_lower_bound(db, pat, &cur);
+	if (zix_btree_iter_is_end(cur)) {
 		SORD_FIND_LOG("No match found\n");
+		zix_btree_iter_free(cur);
 		return NULL;
 	}
-	const SordNode** const key = (const SordNode**)zix_tree_get(cur);
+	const SordNode** const key = (const SordNode**)zix_btree_get(cur);
 	if (!key || ( (mode == RANGE || mode == SINGLE)
 	              && !sord_quad_match_inline(pat, key) )) {
 		SORD_FIND_LOG("No match found\n");
+		zix_btree_iter_free(cur);
 		return NULL;
 	}
 
@@ -1202,7 +1172,7 @@ sord_node_copy(const SordNode* node)
 static inline bool
 sord_add_to_index(SordModel* sord, const SordNode** tup, SordOrder order)
 {
-	return !zix_tree_insert(sord->indices[order], tup, NULL);
+	return !zix_btree_insert(sord->indices[order], tup);
 }
 
 bool
@@ -1240,16 +1210,10 @@ sord_remove(SordModel* sord, const SordQuad tup)
 {
 	SORD_WRITE_LOG("Remove " TUP_FMT "\n", TUP_FMT_ARGS(tup));
 
-	SordNode** quad = NULL;
+	SordNode* quad = NULL;
 	for (unsigned i = 0; i < NUM_ORDERS; ++i) {
 		if (sord->indices[i]) {
-			ZixTreeIter* const cur = index_search(sord->indices[i], tup);
-			if (!zix_tree_iter_is_end(cur)) {
-				if (!quad) {
-					quad = (SordNode**)zix_tree_get(cur);
-				}
-				zix_tree_remove(sord->indices[i], cur);
-			} else {
+			if (zix_btree_remove(sord->indices[i], tup, (void**)&quad)) {
 				assert(i == 0);  // Assuming index coherency
 				return;  // Quad not found, do nothing
 			}
diff --git a/src/sord_test.c b/src/sord_test.c
index b0cee35..a845c9e 100644
--- a/src/sord_test.c
+++ b/src/sord_test.c
@@ -533,7 +533,7 @@ main(int argc, char** argv)
 	sord_add(sord, tup);
 	sord_remove(sord, tup);
 	if (sord_num_quads(sord) != 1) {
-		fprintf(stderr, "Removed failed (%zu quads, expected 1)\n",
+		fprintf(stderr, "Remove failed (%zu quads, expected 1)\n",
 		        sord_num_quads(sord));
 		goto fail;
 	}
diff --git a/src/sord_validate.c b/src/sord_validate.c
index 8b5f04b..7c44941 100644
--- a/src/sord_validate.c
+++ b/src/sord_validate.c
@@ -242,7 +242,7 @@ check_restriction(SordModel*      model,
 			        sord_node_get_string(type),
 			        sord_node_get_string(lower));
 		}
-			        
+
 		sord_iter_free(l);
 		return good;
 	}
@@ -267,7 +267,7 @@ check_restriction(SordModel*      model,
 			        sord_node_get_string(type),
 			        sord_node_get_string(upper));
 		}
-			        
+
 		sord_iter_free(u);
 		return good;
 	}
diff --git a/src/zix/btree.c b/src/zix/btree.c
new file mode 100644
index 0000000..26885e2
--- /dev/null
+++ b/src/zix/btree.c
@@ -0,0 +1,702 @@
+/*
+  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 <assert.h>
+#include <stdint.h>
+#include <stdio.h>
+#include <stdlib.h>
+#include <string.h>
+
+#include "zix/btree.h"
+
+// #define ZIX_BTREE_DEBUG 1
+
+#define ZIX_BTREE_PAGE_SIZE  4096
+#define ZIX_BTREE_NODE_SPACE (ZIX_BTREE_PAGE_SIZE - 2 * sizeof(uint32_t))
+#define ZIX_BTREE_LEAF_VALS  (ZIX_BTREE_NODE_SPACE / sizeof(void*))
+#define ZIX_BTREE_INODE_VALS (ZIX_BTREE_LEAF_VALS / 2)
+
+struct ZixBTreeImpl {
+	ZixBTreeNode*  root;
+	ZixDestroyFunc destroy;
+	ZixComparator  cmp;
+	void*          cmp_data;
+	size_t         size;
+	unsigned       height;  ///< Number of levels, i.e. root only has height 1
+};
+
+struct ZixBTreeNodeImpl {
+	uint32_t      is_leaf;
+	uint32_t      n_vals;
+	void*         vals[ZIX_BTREE_INODE_VALS];  // ZIX_BTREE_LEAF_VALS for leaves
+	ZixBTreeNode* children[ZIX_BTREE_INODE_VALS + 1];  // Nonexistent for leaves
+};
+
+typedef struct {
+	ZixBTreeNode* node;
+	unsigned      index;
+} ZixBTreeIterFrame;
+
+struct ZixBTreeIterImpl {
+	unsigned          level;    ///< Current level in pos
+	ZixBTreeIterFrame stack[];  ///< Position stack
+};
+
+#ifdef ZIX_BTREE_DEBUG
+
+ZIX_PRIVATE void
+print_node(const ZixBTreeNode* n, const char* prefix)
+{
+	printf("%s[", prefix);
+	for (unsigned 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 (unsigned i = 0; i < node->n_vals + 1; ++i) {
+				print_tree(node, node->children[i], level + 1);
+			}
+		}
+		if (!parent) {
+			printf("}\n");
+		}
+	}
+}
+
+#endif  // ZIX_BTREE_DEBUG
+
+ZIX_PRIVATE ZixBTreeNode*
+zix_btree_node_new(const bool leaf)
+{
+	assert(sizeof(ZixBTreeNode) == ZIX_BTREE_PAGE_SIZE);
+	ZixBTreeNode* node = (ZixBTreeNode*)malloc(sizeof(ZixBTreeNode));
+	if (node) {
+		node->is_leaf = leaf;
+		node->n_vals  = 0;
+	}
+	return node;
+}
+
+ZIX_API ZixBTree*
+zix_btree_new(const ZixComparator  cmp,
+              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 (t->destroy) {
+			for (unsigned i = 0; i < n->n_vals; ++i) {
+				t->destroy(n->vals[i]);
+			}
+		}
+		if (!n->is_leaf) {
+			for (unsigned i = 0; i < n->n_vals + 1; ++i) {
+				zix_btree_free_rec(t, n->children[i]);
+			}
+		}
+		free(n);
+	}
+}
+
+ZIX_API void
+zix_btree_free(ZixBTree* const t)
+{
+	if (t) {
+		zix_btree_free_rec(t, t->root);
+		free(t);
+	}
+}
+
+ZIX_API size_t
+zix_btree_size(const ZixBTree* const t)
+{
+	return t->size;
+}
+
+ZIX_PRIVATE unsigned
+zix_btree_max_vals(const ZixBTreeNode* const node)
+{
+	return node->is_leaf ? ZIX_BTREE_LEAF_VALS : ZIX_BTREE_INODE_VALS;
+}
+
+ZIX_PRIVATE unsigned
+zix_btree_min_vals(const ZixBTreeNode* const node)
+{
+	return ((zix_btree_max_vals(node) + 1) / 2) - 1;
+}
+
+/** 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 uint32_t      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 + 1);
+	assert(n->children[i] == lhs);
+
+	const unsigned 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 / 2;
+	rhs->n_vals = max_n_vals - lhs->n_vals - 1;
+
+	// Copy large half of values from LHS to new RHS node
+	memcpy(rhs->vals,
+	       lhs->vals + lhs->n_vals + 1,
+	       rhs->n_vals * sizeof(void*));
+
+	// Copy large half of children from LHS to new RHS node
+	if (!lhs->is_leaf) {
+		memcpy(rhs->children,
+		       lhs->children + lhs->n_vals + 1,
+		       (rhs->n_vals + 1) * sizeof(ZixBTreeNode*));
+	}
+
+	// Move middle value up to parent
+	zix_btree_ainsert(n->vals, n->n_vals, i, lhs->vals[lhs->n_vals]);
+
+	// Insert new RHS node in parent at position i
+	zix_btree_ainsert((void**)n->children, ++n->n_vals, i + 1, rhs);
+
+	return rhs;
+}
+
+/** 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)
+{
+	unsigned first = 0;
+	unsigned len   = n->n_vals;
+	while (len > 0) {
+		const unsigned half = len >> 1;
+		const unsigned i    = first + half;
+		const int      cmp  = t->cmp(n->vals[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 + 1;
+			first += chop;
+			len   -= chop;
+		} else {
+			len = half;
+		}
+	}
+	assert(!*equal || t->cmp(n->vals[first], e, t->cmp_data) == 0);
+	return first;
+}
+
+ZIX_API 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->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->vals[i], e, t->cmp_data);
+			if (cmp == 0) {
+				return ZIX_STATUS_EXISTS;
+			} else if (cmp < 0) {
+				// Move to new RHS
+				n = rhs;
+				++i;
+			}
+		}
+
+		assert(!parent || parent->children[i] == n);
+
+		bool equal = false;
+		i          = zix_btree_node_find(t, n, e, &equal);
+		if (equal) {
+			return ZIX_STATUS_EXISTS;
+		} else if (!n->is_leaf) {
+			// Descend to child node left of value
+			parent = n;
+			n      = n->children[i];
+		} else {
+			// Insert into internal node
+			zix_btree_ainsert(n->vals, n->n_vals, i, e);
+			break;
+		}
+	}
+
+	++n->n_vals;
+	++t->size;
+
+	return ZIX_STATUS_SUCCESS;
+}
+
+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 = parent->children[i];
+	ZixBTreeNode* const rhs = parent->children[i + 1];
+
+	// Move parent value to end of LHS
+	lhs->vals[lhs->n_vals++] = parent->vals[i];
+
+	// Move first child pointer from RHS to end of LHS
+	if (!lhs->is_leaf) {
+		lhs->children[lhs->n_vals] = zix_btree_aerase(
+			(void**)rhs->children, rhs->n_vals, 0);
+	}
+
+	// Move first value in RHS to parent
+	parent->vals[i] = zix_btree_aerase(rhs->vals, --rhs->n_vals, 0);
+
+	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 = parent->children[i - 1];
+	ZixBTreeNode* const rhs = parent->children[i];
+
+	// Prepend parent value to RHS
+	zix_btree_ainsert(rhs->vals, rhs->n_vals++, 0, parent->vals[i - 1]);
+
+	// Move last child pointer from LHS and prepend to RHS
+	if (!lhs->is_leaf) {
+		zix_btree_ainsert((void**)rhs->children,
+		                  rhs->n_vals,
+		                  0,
+		                  lhs->children[lhs->n_vals]);
+	}
+
+	// Move last value from LHS to parent
+	parent->vals[i - 1] = lhs->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 = n->children[i];
+	ZixBTreeNode* const rhs = n->children[i + 1];
+
+	assert(zix_btree_node_is_minimal(n->children[i]));
+	assert(lhs->n_vals + rhs->n_vals < zix_btree_max_vals(lhs));
+
+	// Move parent value to end of LHS
+	lhs->vals[lhs->n_vals++] = zix_btree_aerase(n->vals, n->n_vals, i);
+
+	// Erase corresponding child pointer (to RHS) in parent
+	zix_btree_aerase((void**)n->children, n->n_vals, i + 1);
+
+	// Add everything from RHS to end of LHS
+	memcpy(lhs->vals + lhs->n_vals, rhs->vals, rhs->n_vals * sizeof(void*));
+	if (!lhs->is_leaf) {
+		memcpy(lhs->children + lhs->n_vals,
+		       rhs->children,
+		       (rhs->n_vals + 1) * sizeof(void*));
+	}
+	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(n->children[0])) {
+			// Leftmost child is minimal, must expand
+			if (!zix_btree_node_is_minimal(n->children[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 = n->children[0];
+		}
+	}
+
+	return zix_btree_aerase(n->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(n->children[n->n_vals])) {
+			// Leftmost child is minimal, must expand
+			if (!zix_btree_node_is_minimal(n->children[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 - 1);
+			}
+		} else {
+			n = n->children[n->n_vals];
+		}
+	}
+
+	return n->vals[--n->n_vals];
+}
+
+ZIX_PRIVATE ZixStatus
+zix_btree_remove_rec(ZixBTree* const     t,
+                     ZixBTreeNode* const n,
+                     const void* const   e,
+                     void** const        removed)
+{
+	/* 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);
+
+	if (n->is_leaf) {
+		if (equal) {
+			// Found in leaf node
+			*removed = zix_btree_aerase(n->vals, --n->n_vals, i);
+			return ZIX_STATUS_SUCCESS;
+		} else {
+			// Not found in leaf node, or tree
+			return ZIX_STATUS_NOT_FOUND;
+		}
+	} else if (equal) {
+		// Found in internal node
+		if (!zix_btree_node_is_minimal(n->children[i])) {
+			// Left child can remove without merge
+			*removed = n->vals[i];
+			n->vals[i] = zix_btree_remove_max(t, n->children[i]);
+			return ZIX_STATUS_SUCCESS;
+		} else if (!zix_btree_node_is_minimal(n->children[i + 1])) {
+			// Right child can remove without merge
+			*removed = n->vals[i];
+			n->vals[i] = zix_btree_remove_min(t, n->children[i + 1]);
+			return ZIX_STATUS_SUCCESS;
+		} else {
+			// Both preceding and succeeding child are minimal
+			ZixBTreeNode* const merged = zix_btree_merge(t, n, i);
+			return zix_btree_remove_rec(t, merged, e, removed);
+		}
+	} else {
+		// Not found in internal node, key is in/under children[i]
+		if (zix_btree_node_is_minimal(n->children[i])) {
+			if (i > 0 && !zix_btree_node_is_minimal(n->children[i - 1])) {
+				// Child's left sibling has at least one key to steal
+				ZixBTreeNode* const rhs = zix_btree_rotate_right(n, i);
+				return zix_btree_remove_rec(t, rhs, e, removed);
+			} else if (i < n->n_vals &&
+			           !zix_btree_node_is_minimal(n->children[i + 1])) {
+				// Child's right sibling has at least one key to steal
+				ZixBTreeNode* const lhs = zix_btree_rotate_left(n, i);
+				return zix_btree_remove_rec(t, lhs, e, removed);
+			} else {
+				// Both child's siblings are minimal, merge them
+				const unsigned m = (i < n->n_vals) ? i : i - 1;
+				ZixBTreeNode* const merged = zix_btree_merge(t, n, m);
+				return zix_btree_remove_rec(t, merged, e, removed);
+			}
+		} else {
+			return zix_btree_remove_rec(t, n->children[i], e, removed);
+		}
+	}
+
+	assert(false);  // Not reached
+	return ZIX_STATUS_ERROR;
+}
+
+ZIX_API ZixStatus
+zix_btree_remove(ZixBTree* const t, const void* const e, void** const removed)
+{
+	const ZixStatus st = zix_btree_remove_rec(t, t->root, e, removed);
+	if (!st) {
+		--t->size;
+	}
+	return st;
+}
+
+ZIX_PRIVATE ZixBTreeIter*
+zix_btree_iter_new(const ZixBTree* const t)
+{
+	const size_t        s = t->height * sizeof(ZixBTreeIterFrame);
+	ZixBTreeIter* const i = (ZixBTreeIter*)malloc(sizeof(ZixBTreeIter) + s);
+	if (i) {
+		i->level = 0;
+	}
+	return i;
+}
+
+ZIX_API 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);
+
+		// Update iterator stack
+		(*ti)->stack[(*ti)->level].node  = n;
+		(*ti)->stack[(*ti)->level].index = i;
+
+		if (equal) {
+			return ZIX_STATUS_SUCCESS;
+		} else if (n->is_leaf) {
+			break;
+		} else {
+			++(*ti)->level;
+			n = n->children[i];
+		}
+	}
+
+	zix_btree_iter_free(*ti);
+	*ti = NULL;
+	return ZIX_STATUS_NOT_FOUND;
+}
+
+ZIX_API ZixStatus
+zix_btree_lower_bound(const ZixBTree* const t,
+                      const void* const     e,
+                      ZixBTreeIter** const  ti)
+{
+	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);
+
+		// Update iterator stack
+		(*ti)->stack[(*ti)->level].node  = n;
+		(*ti)->stack[(*ti)->level].index = i;
+
+		if (equal) {
+			found_level = (*ti)->level;
+			found       = true;
+		}
+
+		if (n->is_leaf) {
+			break;
+		} else {
+			++(*ti)->level;
+			n = n->children[i];
+		}
+	}
+
+	const ZixBTreeIterFrame* const frame = &(*ti)->stack[(*ti)->level];
+	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)->stack[0].node = NULL;
+		}
+	}
+
+	return ZIX_STATUS_SUCCESS;
+}
+
+ZIX_API void*
+zix_btree_get(const ZixBTreeIter* const ti)
+{
+	const ZixBTreeIterFrame* const frame = &ti->stack[ti->level];
+	assert(frame->index < frame->node->n_vals);
+	return frame->node->vals[frame->index];
+}
+
+ZIX_API ZixBTreeIter*
+zix_btree_begin(const ZixBTree* const t)
+{
+	ZixBTreeIter* const i = zix_btree_iter_new(t);
+	if (!i) {
+		return NULL;
+	} else if (t->size == 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 = n->children[0];
+			++i->level;
+			i->stack[i->level].node  = n;
+			i->stack[i->level].index = 0;
+		}
+	}
+	return i;
+}
+
+ZIX_API bool
+zix_btree_iter_is_end(const ZixBTreeIter* const i)
+{
+	return !i || i->stack[0].node == NULL;
+}
+
+ZIX_API 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 = f->node->children[++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    = f->node->children[0];
+			f        = &i->stack[++i->level];
+			f->node  = child;
+			f->index = 0;
+		}
+	}
+}
+
+ZIX_API void
+zix_btree_iter_free(ZixBTreeIter* const i)
+{
+	free(i);
+}
diff --git a/src/zix/btree.h b/src/zix/btree.h
new file mode 100644
index 0000000..0cd549a
--- /dev/null
+++ b/src/zix/btree.h
@@ -0,0 +1,144 @@
+/*
+  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.
+*/
+
+#ifndef ZIX_BTREE_H
+#define ZIX_BTREE_H
+
+#include <stdbool.h>
+#include <stddef.h>
+
+#include "zix/common.h"
+
+#ifdef __cplusplus
+extern "C" {
+#endif
+
+/**
+   @addtogroup zix
+   @{
+   @name BTree
+   @{
+*/
+
+/**
+   A B-Tree.
+*/
+typedef struct ZixBTreeImpl ZixBTree;
+
+/**
+   A B-Tree node (opaque).
+*/
+typedef struct ZixBTreeNodeImpl ZixBTreeNode;
+
+/**
+   An iterator over a B-Tree.
+
+   Note that modifying the trees invalidates all iterators, so all iterators
+   are const iterators.
+*/
+typedef struct ZixBTreeIterImpl ZixBTreeIter;
+
+/**
+   Create a new (empty) B-Tree.
+*/
+ZIX_API ZixBTree*
+zix_btree_new(ZixComparator  cmp,
+              void*          cmp_data,
+              ZixDestroyFunc destroy);
+
+/**
+   Free `t`.
+*/
+ZIX_API void
+zix_btree_free(ZixBTree* t);
+
+/**
+   Return the number of elements in `t`.
+*/
+ZIX_API size_t
+zix_btree_size(const ZixBTree* t);
+
+/**
+   Insert the element `e` into `t`.
+*/
+ZIX_API ZixStatus
+zix_btree_insert(ZixBTree* t, void* e);
+
+/**
+   Remove the value `e` from `t`, set `removed` to the removed pointer.
+*/
+ZIX_API ZixStatus
+zix_btree_remove(ZixBTree* t, const void* e, void** removed);
+
+/**
+   Set `ti` to an element equal to `e` in `t`.
+   If no such item exists, `ti` is set to NULL.
+*/
+ZIX_API ZixStatus
+zix_btree_find(const ZixBTree* t, const void* e, ZixBTreeIter** ti);
+
+/**
+   Set `ti` to the smallest element in `t` that is not less than `e`.
+
+   Wildcards are supported, so if the search key `e` compares equal to many
+   values in the tree, `ti` will be set to the least such element.  The search
+   key `e` is always passed as the second argument to the comparator.
+*/
+ZIX_API ZixStatus
+zix_btree_lower_bound(const ZixBTree* t, const void* e, ZixBTreeIter** ti);
+
+/**
+   Return the data associated with the given tree item.
+*/
+ZIX_API void*
+zix_btree_get(const ZixBTreeIter* ti);
+
+/**
+   Return an iterator to the first (smallest) element in `t`.
+
+   The returned iterator must be freed with zix_btree_iter_free().
+*/
+ZIX_API ZixBTreeIter*
+zix_btree_begin(const ZixBTree* t);
+
+/**
+   Return true iff `i` is an iterator to the end of its tree.
+*/
+ZIX_API bool
+zix_btree_iter_is_end(const ZixBTreeIter* i);
+
+/**
+   Increment `i` to point to the next element in the tree.
+*/
+ZIX_API void
+zix_btree_iter_increment(ZixBTreeIter* i);
+
+/**
+   Free `i`.
+*/
+ZIX_API void
+zix_btree_iter_free(ZixBTreeIter* i);
+
+/**
+   @}
+   @}
+*/
+
+#ifdef __cplusplus
+}  /* extern "C" */
+#endif
+
+#endif  /* ZIX_BTREE_H */
diff --git a/src/zix/hash.c b/src/zix/hash.c
index 655c5df..f633e16 100644
--- a/src/zix/hash.c
+++ b/src/zix/hash.c
@@ -1,5 +1,5 @@
 /*
-  Copyright 2011 David Robillard <http://drobilla.net>
+  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
@@ -58,13 +58,18 @@ zix_hash_new(ZixHashFunc  hash_func,
              size_t       value_size)
 {
 	ZixHash* hash = (ZixHash*)malloc(sizeof(ZixHash));
-	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*));
+	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;
 }
 
@@ -225,4 +230,3 @@ zix_hash_foreach(ZixHash*         hash,
 		}
 	}
 }
-
diff --git a/src/zix/tree.c b/src/zix/tree.c
deleted file mode 100644
index 23a7e8c..0000000
--- a/src/zix/tree.c
+++ /dev/null
@@ -1,716 +0,0 @@
-/*
-  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 <assert.h>
-#include <stdint.h>
-#include <stdio.h>
-#include <stdlib.h>
-#include <string.h>
-
-#include "zix/common.h"
-#include "zix/tree.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
-
-ZIX_API 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);
-	}
-}
-
-ZIX_API void
-zix_tree_free(ZixTree* t)
-{
-	if (t) {
-		zix_tree_free_rec(t, t->root);
-		free(t);
-	}
-}
-
-ZIX_API 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;
-}
-
-ZIX_API 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) {
-			n = n->right;
-		} else if (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;
-}
-
-ZIX_API 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 = height_change * -1;
-			} else {
-				assert(i == i->parent->right);
-				d_balance = 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;
-}
-
-ZIX_API 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;
-		} else if (cmp < 0) {
-			n = n->left;
-		} else {
-			n = n->right;
-		}
-	}
-
-	*ti = n;
-	return (n) ? ZIX_STATUS_SUCCESS : ZIX_STATUS_NOT_FOUND;
-}
-
-ZIX_API void*
-zix_tree_get(ZixTreeIter* ti)
-{
-	return ti ? ti->data : NULL;
-}
-
-ZIX_API ZixTreeIter*
-zix_tree_begin(ZixTree* t)
-{
-	if (!t->root) {
-		return NULL;
-	}
-
-	ZixTreeNode* n = t->root;
-	while (n->left) {
-		n = n->left;
-	}
-	return n;
-}
-
-ZIX_API ZixTreeIter*
-zix_tree_end(ZixTree* t)
-{
-	return NULL;
-}
-
-ZIX_API ZixTreeIter*
-zix_tree_rbegin(ZixTree* t)
-{
-	if (!t->root) {
-		return NULL;
-	}
-
-	ZixTreeNode* n = t->root;
-	while (n->right) {
-		n = n->right;
-	}
-	return n;
-}
-
-ZIX_API ZixTreeIter*
-zix_tree_rend(ZixTree* t)
-{
-	return NULL;
-}
-
-ZIX_API bool
-zix_tree_iter_is_end(ZixTreeIter* i)
-{
-	return !i;
-}
-
-ZIX_API bool
-zix_tree_iter_is_rend(ZixTreeIter* i)
-{
-	return !i;
-}
-
-ZIX_API 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;
-}
-
-ZIX_API 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/zix/tree.h b/src/zix/tree.h
deleted file mode 100644
index 8474b1c..0000000
--- a/src/zix/tree.h
+++ /dev/null
@@ -1,148 +0,0 @@
-/*
-  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.
-*/
-
-#ifndef ZIX_TREE_H
-#define ZIX_TREE_H
-
-#include <stddef.h>
-
-#include "zix/common.h"
-
-#ifdef __cplusplus
-extern "C" {
-#endif
-
-/**
-   @addtogroup zix
-   @{
-   @name Tree
-   @{
-*/
-
-/**
-   A balanced binary search tree.
-*/
-typedef struct ZixTreeImpl ZixTree;
-
-/**
-   An iterator over a ZixTree.
-*/
-typedef struct ZixTreeNodeImpl ZixTreeIter;
-
-/**
-   Create a new (empty) tree.
-*/
-ZIX_API ZixTree*
-zix_tree_new(bool           allow_duplicates,
-             ZixComparator  cmp,
-             void*          cmp_data,
-             ZixDestroyFunc destroy);
-
-/**
-   Free `t`.
-*/
-ZIX_API void
-zix_tree_free(ZixTree* t);
-
-/**
-   Return the number of elements in `t`.
-*/
-ZIX_API size_t
-zix_tree_size(const ZixTree* t);
-
-/**
-   Insert the element `e` into `t` and point `ti` at the new element.
-*/
-ZIX_API ZixStatus
-zix_tree_insert(ZixTree* t, void* e, ZixTreeIter** ti);
-
-/**
-   Remove the item pointed at by `ti` from `t`.
-*/
-ZIX_API ZixStatus
-zix_tree_remove(ZixTree* t, ZixTreeIter* ti);
-
-/**
-   Set `ti` to an element equal to `e` in `t`.
-   If no such item exists, `ti` is set to NULL.
-*/
-ZIX_API ZixStatus
-zix_tree_find(const ZixTree* t, const void* e, ZixTreeIter** ti);
-
-/**
-   Return the data associated with the given tree item.
-*/
-ZIX_API void*
-zix_tree_get(ZixTreeIter* ti);
-
-/**
-   Return an iterator to the first (smallest) element in `t`.
-*/
-ZIX_API ZixTreeIter*
-zix_tree_begin(ZixTree* t);
-
-/**
-   Return an iterator the the element one past the last element in `t`.
-*/
-ZIX_API ZixTreeIter*
-zix_tree_end(ZixTree* t);
-
-/**
-   Return true iff `i` is an iterator to the end of its tree.
-*/
-ZIX_API bool
-zix_tree_iter_is_end(ZixTreeIter* i);
-
-/**
-   Return an iterator to the last (largest) element in `t`.
-*/
-ZIX_API ZixTreeIter*
-zix_tree_rbegin(ZixTree* t);
-
-/**
-   Return an iterator the the element one before the first element in `t`.
-*/
-ZIX_API ZixTreeIter*
-zix_tree_rend(ZixTree* t);
-
-/**
-   Return true iff `i` is an iterator to the reverse end of its tree.
-*/
-ZIX_API bool
-zix_tree_iter_is_rend(ZixTreeIter* i);
-
-/**
-   Return an iterator that points to the element one past `i`.
-*/
-ZIX_API ZixTreeIter*
-zix_tree_iter_next(ZixTreeIter* i);
-
-/**
-   Return an iterator that points to the element one before `i`.
-*/
-ZIX_API ZixTreeIter*
-zix_tree_iter_prev(ZixTreeIter* i);
-
-/**
-   @}
-   @}
-*/
-
-#ifdef __cplusplus
-}  /* extern "C" */
-#endif
-
-#endif  /* ZIX_TREE_H */