Add ZixBTree.

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

3 files changed, 149 insertions, 67 deletions

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) {