summaryrefslogtreecommitdiffstats
diff options
context:
space:
mode:
authorDavid Robillard <d@drobilla.net>2014-09-22 07:36:26 +0000
committerDavid Robillard <d@drobilla.net>2014-09-22 07:36:26 +0000
commitb5896fff67d150e6ba96cea7d3679f9958b787ea (patch)
tree69b1e9f00b2d4dacedbfe2037ecaaeda63774ecf
parente0478e0044975678fce9093d01264a20bc2e1ae2 (diff)
downloadzix-b5896fff67d150e6ba96cea7d3679f9958b787ea.tar.gz
zix-b5896fff67d150e6ba96cea7d3679f9958b787ea.tar.bz2
zix-b5896fff67d150e6ba96cea7d3679f9958b787ea.zip
Add ZixBTree.
git-svn-id: http://svn.drobilla.net/zix/trunk@84 df6676b4-ccc9-40e5-b5d6-7c4628a128e3
-rwxr-xr-xplot.py76
-rw-r--r--test/bench.h6
-rw-r--r--test/tree_bench.c200
-rw-r--r--test/tree_test.c10
-rw-r--r--wscript16
-rw-r--r--zix/btree.c623
-rw-r--r--zix/btree.h134
-rw-r--r--zix/btree_test.c249
-rw-r--r--zix/zix.h1
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"
/**
@}