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

5 files changed, 859 insertions, 873 deletions

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 */