Add ZixBTree.

git-svn-id: http://svn.drobilla.net/zix/trunk@84 df6676b4-ccc9-40e5-b5d6-7c4628a128e3

9 files changed, 1222 insertions, 93 deletions

diff --git a/plot.py b/plot.py
index 1534bc4..4eab800 100755
--- a/plot.py
+++ b/plot.py
@@ -4,52 +4,90 @@ import math
 import os
 import sys
 
+import matplotlib
 from matplotlib import pyplot
 from matplotlib.pyplot import *
 
+matplotlib.rc('text', **{
+    'usetex': True})
+matplotlib.rc('font', **{
+    'family':     'serif',
+    'serif':      'Times',
+    'sans-serif': 'Helvetica',
+    'monospace':  'Courier'})
+
 pyplot.subplots_adjust(wspace=0.2, hspace=0.2)
 
-n_plots = len(sys.argv) - 1
+class SensibleScalarFormatter(matplotlib.ticker.ScalarFormatter):
+    "ScalarFormatter which rounds order of magnitude to a multiple of 3"
+    def __init__(self):
+        matplotlib.ticker.ScalarFormatter.__init__(self)
+        self.set_powerlimits([-6, 6])
+        self.set_scientific(True)
+
+    def _set_orderOfMagnitude(self, range):
+        # Calculate "best" order in the usual way
+        matplotlib.ticker.ScalarFormatter._set_orderOfMagnitude(self, range)
+        
+        # Round down to sensible (millions, billions, etc) order
+        self.orderOfMagnitude = self.orderOfMagnitude - (self.orderOfMagnitude % 3)
+
+        self.set_scientific(True)
+
+n_plots = len(sys.argv) - 2
 for i in range(n_plots):
-    filename = sys.argv[i+1]
+    filename = sys.argv[i+2]
     file = open(filename, 'r')
 
-    header = file.readline()
+    # pyplot.clf()
+
+    ax = pyplot.subplot(math.ceil(math.sqrt(n_plots)),
+                        math.ceil(math.sqrt(n_plots)),
+                        i + 1)
+
+    ax.xaxis.set_major_formatter(SensibleScalarFormatter())
+    ax.yaxis.set_major_formatter(SensibleScalarFormatter())
+    for a in ['x', 'y']:
+        ax.grid(which='major', axis=a, zorder=1,
+                linewidth=0.5, linestyle=':', color='0', dashes=[0.5, 8.0])
+
+    header  = file.readline()
     columns = header[1:].split()
 
-    pyplot.subplot(math.ceil(math.sqrt(n_plots)),
-                   math.ceil(math.sqrt(n_plots)),
-                   i + 1)
-    pyplot.xlabel('# Elements')
+    pyplot.xlabel('Elements')
     pyplot.ylabel('Time (s)')
 
     times = []
     for i in columns:
         times.append([])
-    ns = []
-    zix_tree_times = []
-    zix_sorted_array_times = []
-    glib_times = []
     for line in file:
         if line[0] == '#':
             continue;
-        #(n, zix_tree, zix_sorted_array, glib) = line.split()
+
         fields = line.split()
-        num = 0
+        num    = 0
         for i in fields:
             times[num].append([float(i)])
             num += 1
             
-        #ns.append(int(n))
-        #zix_tree_times.append(float(zix_tree))
-        #zix_sorted_array_times.append(float(zix_sorted_array))
-        #glib_times.append(float(glib))
     file.close()
 
     for i in range(len(times) - 1):
         matplotlib.pyplot.plot(times[0], times[i + 1], '-o', label=columns[i + 1])
 
-    pyplot.legend(loc='upper left')
+    pyplot.legend(loc='upper left',
+                  handletextpad=0.15, borderpad=0.20, borderaxespad=0,
+                  labelspacing=0.10, columnspacing=0,
+                  framealpha=0.90)
+
     pyplot.title(os.path.splitext(os.path.basename(filename))[0].title())
 
-matplotlib.pyplot.show()
+    # out = filename.replace('.dat', '.png')
+    # print('Writing %s' % out)
+    # matplotlib.pyplot.savefig(out, bbox_inches='tight', pad_inches=0.025)
+
+print('Writing %s' % sys.argv[1])
+matplotlib.pyplot.tight_layout()
+matplotlib.pyplot.savefig(sys.argv[1])
+
+#matplotlib.pyplot.show()
diff --git a/test/bench.h b/test/bench.h
index 4227e2d..93d4002 100644
--- a/test/bench.h
+++ b/test/bench.h
@@ -27,10 +27,10 @@ elapsed_s(const struct timespec* start, const struct timespec* end)
 }
 
 static inline struct timespec
-bench_start()
+bench_start(void)
 {
 	struct timespec start_t;
-	clock_gettime(CLOCK_REALTIME, &start_t);
+	clock_gettime(CLOCK_MONOTONIC, &start_t);
 	return start_t;
 }
 
@@ -38,7 +38,7 @@ static inline double
 bench_end(const struct timespec* start_t)
 {
 	struct timespec end_t;
-	clock_gettime(CLOCK_REALTIME, &end_t);
+	clock_gettime(CLOCK_MONOTONIC, &end_t);
 	return elapsed_s(start_t, &end_t);
 }
 
diff --git a/test/tree_bench.c b/test/tree_bench.c
index ff6bd5e..f4bcb0b 100644
--- a/test/tree_bench.c
+++ b/test/tree_bench.c
@@ -17,31 +17,46 @@
 #include "bench.h"
 
 #include <inttypes.h>
+#include <limits.h>
 #include <stdint.h>
 #include <stdio.h>
 #include <stdlib.h>
-#include <limits.h>
 
 #include <glib.h>
 
 #include "zix/zix.h"
 
-const unsigned seed = 1;
+// #define BENCH_SORTED_ARRAY 1
 
-static int
-int_cmp(const void* a, const void* b, void* user_data)
+// Return a pseudo-pseudo-pseudo-random-ish integer with no duplicates
+static uint32_t
+unique_rand(uint32_t i)
 {
-	const intptr_t ia = (intptr_t)a;
-	const intptr_t ib = (intptr_t)b;
-	return ia - ib;
+	i ^= 0x5CA1AB1E;  // Juggle bits to avoid linear clumps
+
+	// Largest prime < 2^32 which satisfies (2^32 = 3 mod 4)
+	static const uint32_t prime = 4294967291;
+	if (i >= prime) {
+		return i;  // Values >= prime are mapped to themselves
+	} else {
+		const uint32_t residue = ((uint64_t)i * i) % prime;
+		return (i <= prime / 2) ? residue : prime - residue;
+	}
 }
 
 static int
-int_ptr_cmp(const void* a, const void* b, void* user_data)
+int_cmp(const void* a, const void* b, void* user_data)
 {
-	const intptr_t ia = *(intptr_t*)a;
-	const intptr_t ib = *(intptr_t*)b;
-	return ia - ib;
+	const intptr_t ia = (intptr_t)a;
+	const intptr_t ib = (intptr_t)b;
+	// note the (ia - ib) trick here would overflow
+	if (ia == ib) {
+		return 0;
+	} else if (ia < ib) {
+		return -1;
+	} else {
+		return 1;
+	}
 }
 
 static int
@@ -55,21 +70,26 @@ test_fail(const char* fmt, ...)
 	return EXIT_FAILURE;
 }
 
+static void
+start_test(const char* name)
+{
+	fprintf(stderr, "Benchmarking %s\n", name);
+}
+
 static int
 bench_zix_tree(size_t n_elems,
                FILE* insert_dat, FILE* search_dat, FILE* iter_dat, FILE* del_dat)
 {
-	intptr_t     r;
-	ZixTreeIter* ti;
-
-	ZixTree* t = zix_tree_new(true, int_cmp, NULL, NULL);
+	start_test("ZixTree");
 
-	srand(seed);
+	intptr_t     r  = 0;
+	ZixTreeIter* ti = NULL;
+	ZixTree*     t  = zix_tree_new(false, int_cmp, NULL, NULL);
 
 	// Insert n_elems elements
 	struct timespec insert_start = bench_start();
 	for (size_t i = 0; i < n_elems; i++) {
-		r = rand();
+		r = unique_rand(i);
 		int status = zix_tree_insert(t, (void*)r, &ti);
 		if (status) {
 			return test_fail("Failed to insert %zu\n", r);
@@ -77,12 +97,10 @@ bench_zix_tree(size_t n_elems,
 	}
 	fprintf(insert_dat, "\t%lf", bench_end(&insert_start));
 
-	srand(seed);
-
 	// Search for all elements
 	struct timespec search_start = bench_start();
 	for (size_t i = 0; i < n_elems; i++) {
-		r = rand();
+		r = unique_rand(i);
 		if (zix_tree_find(t, (void*)r, &ti)) {
 			return test_fail("Failed to find %zu\n", r);
 		}
@@ -92,8 +110,6 @@ bench_zix_tree(size_t n_elems,
 	}
 	fprintf(search_dat, "\t%lf", bench_end(&search_start));
 
-	srand(seed);
-
 	// Iterate over all elements
 	struct timespec iter_start = bench_start();
 	for (ZixTreeIter* iter = zix_tree_begin(t);
@@ -103,14 +119,11 @@ bench_zix_tree(size_t n_elems,
 	}
 	fprintf(iter_dat, "\t%lf", bench_end(&iter_start));
 
-	srand(seed);
-
 	// Delete all elements
 	struct timespec del_start = bench_start();
 	for (size_t i = 0; i < n_elems; i++) {
-		r = rand();
-		ZixTreeIter*
-			item;
+		r = unique_rand(i);
+		ZixTreeIter* item;
 		if (zix_tree_find(t, (void*)r, &item)) {
 			return test_fail("Failed to find %zu to delete\n", r);
 		}
@@ -126,20 +139,89 @@ bench_zix_tree(size_t n_elems,
 }
 
 static int
+bench_zix_btree(size_t n_elems,
+                FILE* insert_dat, FILE* search_dat, FILE* iter_dat, FILE* del_dat)
+{
+	start_test("ZixBTree");
+
+	intptr_t      r  = 0;
+	ZixBTreeIter* ti = NULL;
+	ZixBTree*     t  = zix_btree_new(int_cmp, NULL, NULL);
+
+	// Insert n_elems elements
+	struct timespec insert_start = bench_start();
+	for (size_t i = 0; i < n_elems; i++) {
+		r = unique_rand(i);
+		int status = zix_btree_insert(t, (void*)r);
+		if (status) {
+			return test_fail("Failed to insert %zu\n", r);
+		}
+	}
+	fprintf(insert_dat, "\t%lf", bench_end(&insert_start));
+
+	// Search for all elements
+	struct timespec search_start = bench_start();
+	for (size_t i = 0; i < n_elems; i++) {
+		r = unique_rand(i);
+		if (zix_btree_find(t, (void*)r, &ti)) {
+			return test_fail("Failed to find %zu\n", r);
+		}
+		if ((intptr_t)zix_btree_get(ti) != r) {
+			return test_fail("Failed to get %zu\n", r);
+		}
+	}
+	fprintf(search_dat, "\t%lf", bench_end(&search_start));
+
+	// Iterate over all elements
+	struct timespec iter_start = bench_start();
+	ZixBTreeIter* iter = zix_btree_begin(t);
+	for (;
+	     !zix_btree_iter_is_end(iter);
+	      zix_btree_iter_increment(iter)) {
+		zix_btree_get(iter);
+	}
+	zix_btree_iter_free(iter);
+	fprintf(iter_dat, "\t%lf", bench_end(&iter_start));
+
+	// Delete all elements
+	struct timespec del_start = bench_start();
+	for (size_t i = 0; i < n_elems; i++) {
+		r = unique_rand(i);
+		if (zix_btree_remove(t, (void*)r)) {
+			return test_fail("Failed to remove %zu\n", r);
+		}
+	}
+	fprintf(del_dat, "\t%lf", bench_end(&del_start));
+
+	zix_btree_free(t);
+
+	return EXIT_SUCCESS;
+}
+
+#ifdef BENCH_SORTED_ARRAY
+
+static int
+int_ptr_cmp(const void* a, const void* b, void* user_data)
+{
+	const intptr_t ia = *(const intptr_t*)a;
+	const intptr_t ib = *(const intptr_t*)b;
+	return ia - ib;
+}
+
+static int
 bench_zix_sorted_array(size_t n_elems,
                        FILE* insert_dat, FILE* search_dat, FILE* iter_dat, FILE* del_dat)
 {
-	intptr_t    r;
-	ZixSortedArrayIter ti;
-
-	ZixSortedArray* t = zix_sorted_array_new(true, int_ptr_cmp, NULL, sizeof(intptr_t));
+	start_test("ZixSortedArray");
 
-	srand(seed);
+	intptr_t           r  = 0;
+	ZixSortedArrayIter ti = NULL;
+	ZixSortedArray*    t  = zix_sorted_array_new(true, int_ptr_cmp, NULL, sizeof(intptr_t));
 
 	// Insert n_elems elements
 	struct timespec insert_start = bench_start();
 	for (size_t i = 0; i < n_elems; ++i) {
-		r = rand();
+		r = unique_rand(i);
 		int status = zix_sorted_array_insert(t, &r, &ti);
 		if (status) {
 			return test_fail("Insert failed\n");
@@ -151,12 +233,10 @@ bench_zix_sorted_array(size_t n_elems,
 	}
 	fprintf(insert_dat, "\t%lf", bench_end(&insert_start));
 
-	srand(seed);
-
 	// Search for all elements
 	struct timespec search_start = bench_start();
 	for (size_t i = 0; i < n_elems; ++i) {
-		r = rand();
+		r = unique_rand(i);
 		if (zix_sorted_array_find(t, &r, &ti)) {
 			return test_fail("Find failed\n");
 		}
@@ -167,8 +247,6 @@ bench_zix_sorted_array(size_t n_elems,
 	}
 	fprintf(search_dat, "\t%lf", bench_end(&search_start));
 
-	srand(seed);
-
 	// Iterate over all elements
 	struct timespec iter_start = bench_start();
 	size_t i = 0;
@@ -176,7 +254,7 @@ bench_zix_sorted_array(size_t n_elems,
 	for (ZixSortedArrayIter iter = zix_sorted_array_begin(t);
 	     !zix_sorted_array_iter_is_end(t, iter);
 	     iter = zix_sorted_array_iter_next(t, iter), ++i) {
-		r = rand();
+		r = unique_rand(i);
 		const intptr_t iter_data = *(intptr_t*)zix_sorted_array_get_data(iter);
 		if (iter_data < last) {
 			return test_fail("Iter corrupt (%" PRIdPTR " < %zu)\n",
@@ -186,12 +264,10 @@ bench_zix_sorted_array(size_t n_elems,
 	}
 	fprintf(iter_dat, "\t%lf", bench_end(&iter_start));
 
-	srand(seed);
-
 	// Delete all elements
 	struct timespec del_start = bench_start();
-	for (size_t i = 0; i < n_elems; i++) {
-		r = rand();
+	for (i = 0; i < n_elems; i++) {
+		r = unique_rand(i);
 		ZixSortedArrayIter item;
 		if (zix_sorted_array_find(t, &r, &item) != ZIX_STATUS_SUCCESS) {
 			return test_fail("Failed to find item to remove\n");
@@ -212,19 +288,21 @@ bench_zix_sorted_array(size_t n_elems,
 
 }
 
+#endif  // BENCH_SORTED_ARRAY
+
 static int
 bench_glib(size_t n_elems,
            FILE* insert_dat, FILE* search_dat, FILE* iter_dat, FILE* del_dat)
 {
-	intptr_t   r;
-	GSequence* t = g_sequence_new(NULL);
+	start_test("GSequence");
 
-	srand(seed);
+	intptr_t   r = 0;
+	GSequence* t = g_sequence_new(NULL);
 
 	// Insert n_elems elements
 	struct timespec insert_start = bench_start();
 	for (size_t i = 0; i < n_elems; ++i) {
-		r = rand();
+		r = unique_rand(i);
 		GSequenceIter* iter = g_sequence_insert_sorted(t, (void*)r, int_cmp, NULL);
 		if (!iter || g_sequence_iter_is_end(iter)) {
 			return test_fail("Failed to insert %zu\n", r);
@@ -232,12 +310,10 @@ bench_glib(size_t n_elems,
 	}
 	fprintf(insert_dat, "\t%lf", bench_end(&insert_start));
 
-	srand(seed);
-
 	// Search for all elements
 	struct timespec search_start = bench_start();
 	for (size_t i = 0; i < n_elems; ++i) {
-		r = rand();
+		r = unique_rand(i);
 		GSequenceIter* iter = g_sequence_lookup(t, (void*)r, int_cmp, NULL);
 		if (!iter || g_sequence_iter_is_end(iter)) {
 			return test_fail("Failed to find %zu\n", r);
@@ -245,8 +321,6 @@ bench_glib(size_t n_elems,
 	}
 	fprintf(search_dat, "\t%lf", bench_end(&search_start));
 
-	srand(seed);
-
 	// Iterate over all elements
 	struct timespec iter_start = bench_start();
 	for (GSequenceIter* iter = g_sequence_get_begin_iter(t);
@@ -256,12 +330,10 @@ bench_glib(size_t n_elems,
 	}
 	fprintf(iter_dat, "\t%lf", bench_end(&iter_start));
 
-	srand(seed);
-
 	// Delete all elements
 	struct timespec del_start = bench_start();
 	for (size_t i = 0; i < n_elems; ++i) {
-		r = rand();
+		r = unique_rand(i);
 		GSequenceIter* iter = g_sequence_lookup(t, (void*)r, int_cmp, NULL);
 		if (!iter || g_sequence_iter_is_end(iter)) {
 			return test_fail("Failed to remove %zu\n", r);
@@ -288,21 +360,27 @@ main(int argc, char** argv)
 
 	fprintf(stderr, "Benchmarking %zu .. %zu elements\n", min_n, max_n);
 
+#define HEADER "# n\tZixTree\tZixBTree\tGSequence\n"
+
 	FILE* insert_dat = fopen("insert.dat", "w");
 	FILE* search_dat = fopen("search.dat", "w");
 	FILE* iter_dat   = fopen("iterate.dat", "w");
-	FILE* del_dat    = fopen("del.dat", "w");
-	fprintf(insert_dat, "# n\tZixTree\tZixSortedArray\tGSequence\n");
-	fprintf(search_dat, "# n\tZixTree\tZixSortedArray\tGSequence\n");
-	fprintf(iter_dat, "# n\tZixTree\tZixSortedArray\tGSequence\n");
-	fprintf(del_dat, "# n\tZixTree\tZixSortedArray\tGSequence\n");
+	FILE* del_dat    = fopen("delete.dat", "w");
+	fprintf(insert_dat, HEADER);
+	fprintf(search_dat, HEADER);
+	fprintf(iter_dat, HEADER);
+	fprintf(del_dat, HEADER);
 	for (size_t n = min_n; n <= max_n; n *= 2) {
+		fprintf(stderr, "n = %zu\n", n);
 		fprintf(insert_dat, "%zu", n);
 		fprintf(search_dat, "%zu", n);
 		fprintf(iter_dat, "%zu", n);
 		fprintf(del_dat, "%zu", n);
 		bench_zix_tree(n, insert_dat, search_dat, iter_dat, del_dat);
+#ifdef BENCH_SORTED_ARRAY
 		bench_zix_sorted_array(n, insert_dat, search_dat, iter_dat, del_dat);
+#endif
+		bench_zix_btree(n, insert_dat, search_dat, iter_dat, del_dat);
 		bench_glib(n, insert_dat, search_dat, iter_dat, del_dat);
 		fprintf(insert_dat, "\n");
 		fprintf(search_dat, "\n");
@@ -314,5 +392,7 @@ main(int argc, char** argv)
 	fclose(iter_dat);
 	fclose(del_dat);
 
+	fprintf(stderr, "Wrote insert.dat search.dat iterate.dat del.dat\n");
+
 	return EXIT_SUCCESS;
 }
diff --git a/test/tree_test.c b/test/tree_test.c
index 5eb5a11..b806acd 100644
--- a/test/tree_test.c
+++ b/test/tree_test.c
@@ -108,12 +108,11 @@ stress(int test_num, size_t n_elems)
 	srand(seed);
 
 	// Iterate over all elements
-	size_t i = 0;
+	size_t   i    = 0;
 	intptr_t last = -1;
 	for (ZixTreeIter* iter = zix_tree_begin(t);
 	     !zix_tree_iter_is_end(iter);
 	     iter = zix_tree_iter_next(iter), ++i) {
-		r = ith_elem(test_num, n_elems, i);
 		const intptr_t iter_data = (intptr_t)zix_tree_get(iter);
 		if (iter_data < last) {
 			fprintf(stderr, "Iter corrupt (%" PRIdPTR " < %" PRIdPTR ")\n",
@@ -122,6 +121,10 @@ stress(int test_num, size_t n_elems)
 		}
 		last = iter_data;
 	}
+	if (i != n_elems) {
+		fprintf(stderr, "Iteration stopped at %zu/%zu elements\n", i, n_elems);
+		return test_fail();
+	}
 
 	srand(seed);
 
@@ -131,7 +134,6 @@ stress(int test_num, size_t n_elems)
 	for (ZixTreeIter* iter = zix_tree_rbegin(t);
 	     !zix_tree_iter_is_rend(iter);
 	     iter = zix_tree_iter_prev(iter), ++i) {
-		r = ith_elem(test_num, n_elems, i);
 		const intptr_t iter_data = (intptr_t)zix_tree_get(iter);
 		if (iter_data > last) {
 			fprintf(stderr, "Iter corrupt (%" PRIdPTR " < %" PRIdPTR ")\n",
@@ -197,7 +199,7 @@ main(int argc, char** argv)
 	unsigned       n_elems = 0;
 
 	if (argc == 1) {
-		n_elems = 4096;
+		n_elems = 100000;
 	} else {
 		n_elems = atol(argv[1]);
 		if (argc > 2) {
diff --git a/wscript b/wscript
index f13b12d..63259fa 100644
--- a/wscript
+++ b/wscript
@@ -77,7 +77,8 @@ tests = [
     'sem_test',
     'sorted_array_test',
     'strindex_test',
-    'tree_test'
+    'tree_test',
+    'btree_test'
 ]
 
 def build(bld):
@@ -106,13 +107,14 @@ def build(bld):
         zix/sorted_array.c
         zix/strindex.c
         zix/tree.c
+        zix/btree.c
     '''
 
     # Library
     obj = bld(features        = 'c cshlib',
               export_includes = ['.'],
               source          = lib_source,
-              includes        = ['.', './src'],
+              includes        = ['.'],
               name            = 'libzix',
               target          = 'zix',
               vnum            = ZIX_LIB_VERSION,
@@ -133,7 +135,7 @@ def build(bld):
         # Static library (for unit test code coverage)
         obj = bld(features     = 'c cstlib',
                   source       = lib_source,
-                  includes     = ['.', './src'],
+                  includes     = ['.'],
                   lib          = test_libs,
                   name         = 'libzix_profiled',
                   target       = 'zix_profiled',
@@ -149,7 +151,7 @@ def build(bld):
                       use          = 'libzix_profiled',
                       lib          = test_libs,
                       target       = 'test/%s' % i,
-                      install_path = '',
+                      install_path = None,
                       framework    = framework,
                       cflags       = test_cflags)
 
@@ -174,7 +176,7 @@ def build(bld):
         bld.add_post_fun(fix_docs)
 
 def lint(ctx):
-    subprocess.call('cpplint.py --filter=-whitespace/tab,-whitespace/braces,-build/header_guard,-readability/casting,-readability/todo src/* zix/*', shell=True)
+    subprocess.call('cpplint.py --filter=-whitespace/tab,-whitespace/braces,-build/header_guard,-readability/casting,-readability/todo zix/*', shell=True)
 
 def build_dir(ctx, subdir):
     if autowaf.is_child():
@@ -192,5 +194,5 @@ def upload_docs(ctx):
 def test(ctx):
     autowaf.pre_test(ctx, APPNAME)
     os.environ['PATH'] = 'test' + os.pathsep + os.getenv('PATH')
-    autowaf.run_tests(ctx, APPNAME, tests, dirs=['.','src','test'])
-    autowaf.post_test(ctx, APPNAME)
+    autowaf.run_tests(ctx, APPNAME, tests, dirs=['.', './test'])
+    autowaf.post_test(ctx, APPNAME, dirs=['.', './test'])
diff --git a/zix/btree.c b/zix/btree.c
new file mode 100644
index 0000000..5c4d2a9
--- /dev/null
+++ b/zix/btree.c
@@ -0,0 +1,623 @@
+/*
+  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_alloc_node(const bool leaf)
+{
+	assert(sizeof(ZixBTreeNode) == ZIX_BTREE_PAGE_SIZE);
+	ZixBTreeNode* node = (ZixBTreeNode*)malloc(sizeof(ZixBTreeNode));
+	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));
+	t->root     = zix_btree_alloc_node(true);
+	t->destroy  = destroy;
+	t->cmp      = cmp;
+	t->cmp_data = cmp_data;
+	t->size     = 0;
+	t->height   = 1;
+	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);
+
+	ZixBTreeNode*  rhs        = zix_btree_alloc_node(lhs->is_leaf);
+	const unsigned max_n_vals = zix_btree_max_vals(lhs);
+
+	// 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;
+			return i;
+		} else if (cmp < 0) {
+			const unsigned chop = half + 1;
+			first += chop;
+			len   -= chop;
+		} else {
+			len = half;
+		}
+	}
+	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
+				t->root             = parent = zix_btree_alloc_node(false);
+				parent->children[0] = n;
+				++t->height;
+			}
+
+			ZixBTreeNode* const rhs = zix_btree_split_child(parent, i, n);
+			const int           cmp = t->cmp(e, parent->vals[i], 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(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)
+{
+	/* 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
+			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
+			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
+			n->vals[i] = zix_btree_remove_min(t, n->children[i + 1]);
+			return ZIX_STATUS_SUCCESS;
+		} else {
+			// Both preceding and succeeding child are minimal
+			return zix_btree_remove_rec(t, zix_btree_merge(t, n, i), e);
+		}
+	} 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
+				return zix_btree_remove_rec(t, zix_btree_rotate_right(n, i), e);
+			} 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
+				return zix_btree_remove_rec(t, zix_btree_rotate_left(n, i), e);
+			} else {
+				// Both child's siblings are minimal, merge them
+				const unsigned m = (i < n->n_vals) ? i : i - 1;
+				assert(zix_btree_node_is_minimal(n->children[m]));
+				return zix_btree_remove_rec(t, zix_btree_merge(t, n, m), e);
+			}
+		} else {
+			return zix_btree_remove_rec(t, n->children[i], e);
+		}
+	}
+
+	assert(false);  // Not reached
+	return ZIX_STATUS_ERROR;
+}
+
+ZIX_API ZixStatus
+zix_btree_remove(ZixBTree* const t, const void* const e)
+{
+	const ZixStatus st = zix_btree_remove_rec(t, t->root, e);
+	if (!st) {
+		--t->size;
+	}
+	return st;
+}
+
+ZIX_PRIVATE ZixBTreeIter*
+zix_btree_iter_new(const ZixBTree* const t)
+{
+	ZixBTreeIter* const i = (ZixBTreeIter*)malloc(
+		sizeof(ZixBTreeIter) + t->height * sizeof(ZixBTreeIterFrame));
+	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;
+
+	*ti = zix_btree_iter_new(t);
+	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 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 (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->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/zix/btree.h b/zix/btree.h
new file mode 100644
index 0000000..d8b11c7
--- /dev/null
+++ b/zix/btree.h
@@ -0,0 +1,134 @@
+/*
+  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`.
+*/
+ZIX_API ZixStatus
+zix_btree_remove(ZixBTree* t, const void* e);
+
+/**
+   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);
+
+/**
+   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/zix/btree_test.c b/zix/btree_test.c
new file mode 100644
index 0000000..93c2b1d
--- /dev/null
+++ b/zix/btree_test.c
@@ -0,0 +1,249 @@
+/*
+  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 <limits.h>
+#include <stdarg.h>
+#include <stdint.h>
+#include <stdio.h>
+#include <stdlib.h>
+#include <time.h>
+
+#ifdef _MSC_VER
+#    define PRIdPTR "Id"
+#else
+#    include <inttypes.h>
+#endif
+
+#include "zix/zix.h"
+
+unsigned seed = 1;
+
+// Return a pseudo-pseudo-pseudo-random-ish integer with no duplicates
+static uint32_t
+unique_rand(uint32_t i)
+{
+	i ^= 0x5CA1AB1E;  // Juggle bits to avoid linear clumps
+
+	// Largest prime < 2^32 which satisfies (2^32 = 3 mod 4)
+	static const uint32_t prime = 4294967291;
+	if (i >= prime) {
+		return i;  // Values >= prime are mapped to themselves
+	} else {
+		const uint32_t residue = ((uint64_t)i * i) % prime;
+		return (i <= prime / 2) ? residue : prime - residue;
+	}
+}
+
+static int
+int_cmp(const void* a, const void* b, void* user_data)
+{
+	const intptr_t ia = (intptr_t)a;
+	const intptr_t ib = (intptr_t)b;
+	// note the (ia - ib) trick here would overflow
+	if (ia == ib) {
+		return 0;
+	} else if (ia < ib) {
+		return -1;
+	} else {
+		return 1;
+	}
+}
+
+static uint32_t
+ith_elem(int test_num, size_t n_elems, int i)
+{
+	switch (test_num % 3) {
+	case 0:  return i;                // Increasing
+	case 1:  return n_elems - i - 1;  // Decreasing
+	default: return unique_rand(i);   // Pseudo-random
+	}
+}
+
+static int
+test_fail(const char* fmt, ...)
+{
+	va_list args;
+	va_start(args, fmt);
+	fprintf(stderr, "error: ");
+	vfprintf(stderr, fmt, args);
+	va_end(args);
+	return EXIT_FAILURE;
+}
+
+static int
+stress(int test_num, size_t n_elems)
+{
+	intptr_t      r  = 0;
+	ZixBTreeIter* ti = NULL;
+	ZixBTree*     t  = zix_btree_new(int_cmp, NULL, NULL);
+
+	// Ensure begin iterator is end on empty tree
+	ti = zix_btree_begin(t);
+	if (!zix_btree_iter_is_end(ti)) {
+		return test_fail("Begin iterator on empty tree is not end\n");
+	}
+	zix_btree_iter_free(ti);
+
+	// Insert n_elems elements
+	for (size_t i = 0; i < n_elems; ++i) {
+		r = ith_elem(test_num, n_elems, i);
+		if (zix_btree_insert(t, (void*)r)) {
+			return test_fail("Insert failed\n");
+		}
+	}
+
+	// Ensure tree size is correct
+	if (zix_btree_size(t) != n_elems) {
+		return test_fail("Tree size %zu != %zu\n", zix_btree_size(t), n_elems);
+	}
+
+	// Search for all elements
+	for (size_t i = 0; i < n_elems; ++i) {
+		r = ith_elem(test_num, n_elems, i);
+		if (zix_btree_find(t, (void*)r, &ti)) {
+			return test_fail("Find %lu @ %zu failed\n", (uintptr_t)r, i);
+		}
+		if ((intptr_t)zix_btree_get(ti) != r) {
+			return test_fail("Corrupt search: %" PRIdPTR " != %" PRIdPTR "\n",
+			                 (intptr_t)zix_btree_get(ti), r);
+		}
+		zix_btree_iter_free(ti);
+	}
+
+	// Search for elements that don't exist
+	for (size_t i = 0; i < n_elems; ++i) {
+		r = ith_elem(test_num, n_elems * 3, n_elems + i);
+		if (!zix_btree_find(t, (void*)r, &ti)) {
+			return test_fail("Unexpectedly found %lu\n", (uintptr_t)r);
+		}
+	}
+
+	// Iterate over all elements
+	size_t        i    = 0;
+	intptr_t      last = -1;
+	for (ti = zix_btree_begin(t);
+	     !zix_btree_iter_is_end(ti);
+	     zix_btree_iter_increment(ti), ++i) {
+		const intptr_t iter_data = (intptr_t)zix_btree_get(ti);
+		if (iter_data < last) {
+			return test_fail("Corrupt iter: %" PRIdPTR " < %" PRIdPTR "\n",
+			                 iter_data, last);
+		}
+		last = iter_data;
+	}
+	zix_btree_iter_free(ti);
+	if (i != n_elems) {
+		return test_fail("Iteration stopped at %zu/%zu elements\n", i, n_elems);
+	}
+
+	// Insert n_elems elements again, ensuring duplicates fail
+	for (i = 0; i < n_elems; ++i) {
+		r = ith_elem(test_num, n_elems, i);
+		if (!zix_btree_insert(t, (void*)r)) {
+			return test_fail("Duplicate insert succeeded\n");
+		}
+	}
+
+	// Search for the middle element then iterate from there
+	r = ith_elem(test_num, n_elems, n_elems / 2);
+	if (zix_btree_find(t, (void*)r, &ti)) {
+		return test_fail("Find %lu failed\n", (uintptr_t)r);
+	}
+	zix_btree_iter_increment(ti);
+	for (i = 0; !zix_btree_iter_is_end(ti); zix_btree_iter_increment(ti), ++i) {
+		if ((intptr_t)zix_btree_get(ti) == r) {
+			return test_fail("Duplicate element %" PRIdPTR "\n",
+			                 (intptr_t)zix_btree_get(ti), r);
+		}
+		r = ith_elem(test_num, n_elems, n_elems / 2 + i + 1);
+	}
+	zix_btree_iter_free(ti);
+
+	// Delete all elements
+	for (size_t e = 0; e < n_elems; e++) {
+		r = ith_elem(test_num, n_elems, e);
+		if (zix_btree_remove(t, (void*)r)) {
+			return test_fail("Error removing item %lu\n", (uintptr_t)r);
+		}
+	}
+
+	// Ensure the tree is empty
+	if (zix_btree_size(t) != 0) {
+		return test_fail("Tree size %zu != 0\n", zix_btree_size(t));
+	}
+
+	// Insert n_elems elements again (to test non-empty destruction)
+	for (size_t e = 0; e < n_elems; ++e) {
+		r = ith_elem(test_num, n_elems, e);
+		if (zix_btree_insert(t, (void*)r)) {
+			return test_fail("Post-deletion insert failed\n");
+		}
+	}
+
+	// Delete elements that don't exist
+	for (size_t e = 0; e < n_elems; e++) {
+		r = ith_elem(test_num, n_elems * 3, n_elems + e);
+		if (!zix_btree_remove(t, (void*)r)) {
+			return test_fail("Unexpected successful deletion of %lu\n",
+			                 (uintptr_t)r);
+		}
+	}
+
+	// Ensure tree size is still correct
+	if (zix_btree_size(t) != n_elems) {
+		return test_fail("Tree size %zu != %zu\n", zix_btree_size(t), n_elems);
+	}
+
+	// Delete some elements towards the end
+	for (size_t e = 0; e < n_elems / 4; e++) {
+		r = ith_elem(test_num, n_elems, n_elems - (n_elems / 4) + e);
+		if (zix_btree_remove(t, (void*)r)) {
+			return test_fail("Deletion of %lu faileded\n", (uintptr_t)r);
+		}
+	}
+
+	// Check tree size
+	if (zix_btree_size(t) != n_elems - (n_elems / 4)) {
+		return test_fail("Tree size %zu != %zu\n", zix_btree_size(t), n_elems);
+	}
+
+	zix_btree_free(t);
+
+	return EXIT_SUCCESS;
+}
+
+int
+main(int argc, char** argv)
+{
+	if (argc > 2) {
+		fprintf(stderr, "Usage: %s [N_ELEMS]\n", argv[0]);
+		return EXIT_FAILURE;
+	}
+
+	const unsigned n_tests = 3;
+	unsigned       n_elems = (argc > 1) ? atol(argv[1]) : 10000;
+
+	printf("Running %u tests with %u elements", n_tests, n_elems);
+	for (unsigned i = 0; i < n_tests; ++i) {
+		printf(".");
+		fflush(stdout);
+		if (stress(i, n_elems)) {
+			return EXIT_FAILURE;
+		}
+	}
+	printf("\n");
+	return EXIT_SUCCESS;
+}
diff --git a/zix/zix.h b/zix/zix.h
index f6e0b5d..659bb1b 100644
--- a/zix/zix.h
+++ b/zix/zix.h
@@ -26,6 +26,7 @@
 #include "zix/common.h"
 #include "zix/sorted_array.h"
 #include "zix/tree.h"
+#include "zix/btree.h"
 
 /**
    @}