Minimal space overhead inline value hash table.

Add ZixChunk.
Add SSE 4.2 accelerated digest (with fallback) in zix/digest.h.
Make library optionally header-only (define ZIX_INLINE).

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

8 files changed, 0 insertions, 2410 deletions

diff --git a/src/fat_patree.c b/src/fat_patree.c
deleted file mode 100644
index 454cfba..0000000
--- a/src/fat_patree.c
+++ /dev/null
@@ -1,239 +0,0 @@
-/*
-  Copyright 2011 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.
-*/
-
-#define _XOPEN_SOURCE 500
-
-#include <assert.h>
-#include <stdint.h>
-#include <stdio.h>
-#include <stdlib.h>
-#include <string.h>
-
-#include "zix/common.h"
-#include "zix/fat_patree.h"
-
-#define N_CHILDREN 256
-
-typedef uint_fast8_t n_edges_t;
-
-typedef struct _ZixFatPatreeNode {
-	char*                     label_first;           /* Start of incoming label */
-	char*                     label_last;            /* End of incoming label */
-	char*                     str;                   /* String stored at this node */
-	struct _ZixFatPatreeNode* children[N_CHILDREN];  /* Children of this node */
-} ZixFatPatreeNode;
-
-struct _ZixFatPatree {
-	ZixFatPatreeNode* root;  /* Root of the tree */
-};
-
-ZIX_API
-ZixFatPatree*
-zix_fat_patree_new(void)
-{
-	ZixFatPatree* t = (ZixFatPatree*)malloc(sizeof(ZixFatPatree));
-	memset(t, '\0', sizeof(struct _ZixFatPatree));
-
-	t->root = (ZixFatPatreeNode*)malloc(sizeof(ZixFatPatreeNode));
-	memset(t->root, '\0', sizeof(ZixFatPatreeNode));
-
-	return t;
-}
-
-static void
-zix_fat_patree_free_rec(ZixFatPatreeNode* n)
-{
-	if (n) {
-		for (int i = 0; i < N_CHILDREN; ++i) {
-			zix_fat_patree_free_rec(n->children[i]);
-		}
-	}
-}
-
-ZIX_API
-void
-zix_fat_patree_free(ZixFatPatree* t)
-{
-	zix_fat_patree_free_rec(t->root);
-	free(t->root);
-	free(t);
-}
-
-static inline bool
-patree_find_edge(ZixFatPatreeNode* n, uint8_t c, n_edges_t* index)
-{
-	if (n->children[c]) {
-		*index = c;
-		return true;
-	}
-	return false;
-}
-
-static void
-patree_add_edge(ZixFatPatreeNode* n,
-                char*             str,
-                char*             first,
-                char*             last)
-{
-	assert(last >= first);
-	const int index = (uint8_t)first[0];
-	assert(!n->children[index]);
-
-	ZixFatPatreeNode* new_node = (ZixFatPatreeNode*)malloc(
-		sizeof(ZixFatPatreeNode));
-	n->children[index] = new_node;
-	n->children[index]->label_first = first;
-	n->children[index]->label_last  = last;
-	n->children[index]->str         = str;
-	for (int i = 0; i < N_CHILDREN; ++i) {
-		n->children[index]->children[i] = NULL;
-	}
-}
-
-/* Split an outgoing edge (to a child) at the given index */
-static void
-patree_split_edge(ZixFatPatreeNode* child,
-                  size_t         index)
-{
-	char* const first = child->label_first + index;
-	char* const last  = child->label_last;
-	assert(last >= first);
-
-	ZixFatPatreeNode* new_node = (ZixFatPatreeNode*)malloc(
-		sizeof(ZixFatPatreeNode));
-	new_node->label_first  = first;
-	new_node->label_last   = last;
-	new_node->str          = child->str;
-	memcpy(new_node->children, child->children,
-	       sizeof(ZixFatPatreeNode*) * N_CHILDREN);
-
-	child->label_last = child->label_first + (index - 1);  // chop end
-	child->str = NULL;
-
-	for (int i = 0; i < N_CHILDREN; ++i) {
-		child->children[i] = NULL;
-	}
-	const int new_node_index = (int)first[0];
-	assert(new_node_index < N_CHILDREN);
-	assert(!child->children[new_node_index]);
-	child->children[new_node_index] = new_node;
-}
-
-static ZixStatus
-patree_insert_internal(ZixFatPatreeNode* n, char* str, char* first, char* last)
-{
-	n_edges_t child_i;
-	assert(first <= last);
-
-	if (patree_find_edge(n, *first, &child_i)) {
-		ZixFatPatreeNode* child       = n->children[child_i];
-		char* const    label_first = child->label_first;
-		char* const    label_last  = child->label_last;
-		size_t         split_i     = 0;
-		const size_t   label_len   = label_last - label_first + 1;
-		const size_t   s_len       = last - first + 1;
-		const size_t   max_len     = (s_len < label_len) ? s_len : label_len;
-
-		while (split_i < max_len && first[split_i] == label_first[split_i]) {
-			++split_i;
-		}
-		child = n->children[child_i];
-
-		if (label_len < s_len) {
-			if (split_i == label_len) {
-				return patree_insert_internal(child, str, first + label_len, last);
-			} else {
-				patree_split_edge(child, split_i);
-				return patree_insert_internal(child, str, first + split_i, last);
-			}
-		} else if (label_len != split_i) {
-			patree_split_edge(child, split_i);
-			if (split_i != s_len) {
-				patree_add_edge(child, str, first + split_i, last);
-			} else {
-				assert(!child->str);
-				child->str = str;
-			}
-			return ZIX_STATUS_SUCCESS;
-		} else if (label_len == s_len && !child->str) {
-			child->str = str;
-		} else {
-			return ZIX_STATUS_EXISTS;
-		}
-
-	} else {
-		patree_add_edge(n, str, first, last);
-	}
-
-	return ZIX_STATUS_SUCCESS;
-}
-
-ZIX_API
-ZixStatus
-zix_fat_patree_insert(ZixFatPatree* t, const char* str)
-{
-	const size_t len = strlen(str);
-	// FIXME: awful casts
-	return patree_insert_internal(t->root, (char*)str, (char*)str, (char*)str + len - 1);
-}
-
-ZIX_API
-ZixStatus
-zix_fat_patree_find(ZixFatPatree* t, const char* p, char** match)
-{
-	ZixFatPatreeNode* n = t->root;
-	n_edges_t         child_i;
-
-	*match = NULL;
-
-	while (*p != '\0') {
-		if (patree_find_edge(n, p[0], &child_i)) {
-			ZixFatPatreeNode* const child       = n->children[child_i];
-			const char* const    label_first = child->label_first;
-			const char* const    label_last  = child->label_last;
-
-			/* Prefix compare search string and label */
-			const char* l = label_first;
-			while (*p != '\0' && l <= label_last) {
-				if (*l++ != *p++) {
-					return ZIX_STATUS_NOT_FOUND;
-				}
-			}
-
-			if (!*p) {
-				/* Reached end of search string */
-				if (l == label_last + 1) {
-					/* Reached end of label string as well, match */
-					*match = child->str;
-					return *match ? ZIX_STATUS_SUCCESS : ZIX_STATUS_NOT_FOUND;
-				} else {
-					/* Label string is longer, no match (prefix match) */
-					return ZIX_STATUS_NOT_FOUND;
-				}
-			} else {
-				/* Match at this node, continue search downwards.
-				   Possibly we have prematurely hit a leaf, so the next
-				   edge search will fail.
-				*/
-				n  = child;
-			}
-		} else {
-			return ZIX_STATUS_NOT_FOUND;
-		}
-	}
-
-	return ZIX_STATUS_NOT_FOUND;
-}
diff --git a/src/hash.c b/src/hash.c
deleted file mode 100644
index f654e91..0000000
--- a/src/hash.c
+++ /dev/null
@@ -1,226 +0,0 @@
-/*
-  Copyright 2011 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 <stdlib.h>
-#include <string.h>
-
-#include "zix/hash.h"
-
-/**
-   Primes, each slightly less than twice its predecessor, and as far away
-   from powers of two as possible.
-*/
-static const unsigned sizes[] = {
-	53, 97, 193, 389, 769, 1543, 3079, 6151, 12289, 24593, 49157, 98317,
-	196613, 393241, 786433, 1572869, 3145739, 6291469, 12582917, 25165843,
-	50331653, 100663319, 201326611, 402653189, 805306457, 1610612741, 0
-};
-
-typedef struct _Entry {
-	const void*    key;   ///< Hash key
-	void*          data;  ///< Value
-	struct _Entry* next;  ///< Next entry in bucket
-	unsigned       hash;  ///< Non-modulo hash value (for cheap rehash)
-} Entry;
-
-struct ZixHashImpl {
-	ZixHashFunc     hash_func;
-	ZixEqualFunc    key_equal_func;
-	Entry**         buckets;
-	const unsigned* n_buckets;
-	unsigned        count;
-};
-
-ZixHash*
-zix_hash_new(ZixHashFunc  hash_func,
-             ZixEqualFunc key_equal_func)
-
-{
-	ZixHash* hash = (ZixHash*)malloc(sizeof(ZixHash));
-	hash->hash_func      = hash_func;
-	hash->key_equal_func = key_equal_func;
-	hash->count          = 0;
-	hash->n_buckets      = &sizes[0];
-	hash->buckets        = (Entry**)malloc(*hash->n_buckets * sizeof(Entry*));
-	memset(hash->buckets, 0, *hash->n_buckets * sizeof(Entry*));
-
-	return hash;
-}
-
-void
-zix_hash_free(ZixHash* hash)
-{
-	for (unsigned b = 0; b < *hash->n_buckets; ++b) {
-		Entry* bucket = hash->buckets[b];
-		for (Entry* e = bucket; e;) {
-			Entry* next = e->next;
-			free(e);
-			e = next;
-		}
-	}
-
-	free(hash->buckets);
-	free(hash);
-}
-
-unsigned
-zix_string_hash(const void* key)
-{
-	// Trusty old DJB hash
-	const char* str = (const char*)key;
-	unsigned    h   = 5381;
-	for (const char* s = str; *s != '\0'; ++s) {
-		h = (h << 5) + h + *s;  // h = h * 33 + c
-	}
-	return h;
-}
-
-bool
-zix_string_equal(const void* a, const void* b)
-{
-	return !strcmp((const char*)a, (const char*)b);
-}
-
-static void
-insert_entry(Entry** bucket,
-             Entry*  entry)
-{
-	entry->next = *bucket;
-	*bucket     = entry;
-}
-
-static ZixStatus
-rehash(ZixHash* hash, unsigned new_n_buckets)
-{
-	Entry** new_buckets = (Entry**)malloc(new_n_buckets * sizeof(Entry*));
-	if (!new_buckets) {
-		return ZIX_STATUS_NO_MEM;
-	}
-
-	memset(new_buckets, 0, new_n_buckets * sizeof(Entry*));
-
-	for (unsigned b = 0; b < *hash->n_buckets; ++b) {
-		for (Entry* e = hash->buckets[b]; e;) {
-			Entry* const   next = e->next;
-			const unsigned h    = e->hash % new_n_buckets;
-			insert_entry(&new_buckets[h], e);
-			e = next;
-		}
-	}
-
-	free(hash->buckets);
-	hash->buckets = new_buckets;
-
-	return ZIX_STATUS_SUCCESS;
-}
-
-static Entry*
-find_entry(const ZixHash* hash,
-           const void*    key,
-           unsigned   h)
-{
-	for (Entry* e = hash->buckets[h]; e; e = e->next) {
-		if (hash->key_equal_func(e->key, key)) {
-			return e;
-		}
-	}
-
-	return NULL;
-}
-
-void*
-zix_hash_find(const ZixHash* hash, const void* key)
-{
-	const unsigned h     = hash->hash_func(key) % *hash->n_buckets;
-	Entry* const   entry = find_entry(hash, key, h);
-	return entry ? entry->data : 0;
-}
-
-ZixStatus
-zix_hash_insert(ZixHash* hash, const void* key, void* data)
-{
-	unsigned h_nomod = hash->hash_func(key);
-	unsigned h       = h_nomod % *hash->n_buckets;
-
-	Entry* elem = find_entry(hash, key, h);
-	if (elem) {
-		assert(elem->hash == h_nomod);
-		return ZIX_STATUS_EXISTS;
-	}
-
-	elem = (Entry*)malloc(sizeof(Entry));
-	if (!elem) {
-		return ZIX_STATUS_NO_MEM;
-	}
-	elem->key  = key;
-	elem->data = data;
-	elem->next = NULL;
-	elem->hash = h_nomod;
-	const unsigned next_n_buckets = *(hash->n_buckets + 1);
-	if (next_n_buckets != 0 && (hash->count + 1) >= next_n_buckets) {
-		if (!rehash(hash, next_n_buckets)) {
-			h = h_nomod % *(++hash->n_buckets);
-		}
-	}
-
-	insert_entry(&hash->buckets[h], elem);
-	++hash->count;
-	return ZIX_STATUS_SUCCESS;
-}
-
-ZixStatus
-zix_hash_remove(ZixHash* hash, const void* key)
-{
-	unsigned h = hash->hash_func(key) % *hash->n_buckets;
-
-	Entry** next_ptr = &hash->buckets[h];
-	for (Entry* e = hash->buckets[h]; e; e = e->next) {
-		if (hash->key_equal_func(e->key, key)) {
-			*next_ptr = e->next;
-			free(e);
-			return ZIX_STATUS_SUCCESS;
-		}
-		next_ptr = &e->next;
-	}
-
-	if (hash->n_buckets != sizes) {
-		const unsigned prev_n_buckets = *(hash->n_buckets - 1);
-		if (hash->count - 1 <= prev_n_buckets) {
-			if (!rehash(hash, prev_n_buckets)) {
-				--hash->n_buckets;
-			}
-		}
-	}
-
-	--hash->count;
-	return ZIX_STATUS_NOT_FOUND;
-}
-
-ZIX_API
-void
-zix_hash_foreach(const ZixHash* hash,
-                 void (*f)(const void* key, void* value, void* user_data),
-                 void* user_data)
-{
-	for (unsigned b = 0; b < *hash->n_buckets; ++b) {
-		Entry* bucket = hash->buckets[b];
-		for (Entry* e = bucket; e; e = e->next) {
-			f(e->key, e->data, user_data);
-		}
-	}
-}
-
diff --git a/src/patree.c b/src/patree.c
deleted file mode 100644
index f3603a2..0000000
--- a/src/patree.c
+++ /dev/null
@@ -1,373 +0,0 @@
-/*
-  Copyright 2011 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.
-*/
-
-#define _XOPEN_SOURCE 500
-
-#include <assert.h>
-#include <stdint.h>
-#include <stdio.h>
-#include <stdlib.h>
-#include <string.h>
-
-#include "zix/common.h"
-#include "zix/patree.h"
-
-//#undef __SSE4_2__
-
-#ifdef __SSE4_2__
-#include <smmintrin.h>
-//#warning Using SSE 4.2
-#else
-//#warning SSE 4.2 disabled
-#endif
-
-typedef uint_fast8_t n_edges_t;
-
-struct _ZixPatreeNode;
-
-typedef struct {
-	struct _ZixPatreeNode* child;
-	char                   first_char;
-} ZixChildRef;
-
-typedef struct _ZixPatreeNode {
-	const char* label_first;   /* Start of incoming label */
-	const char* label_last;    /* End of incoming label */
-	const char* str;           /* String stored at this node */
-	n_edges_t   num_children;  /* Number of outgoing edges */
-	ZixChildRef children[];    /* Children of this node */
-} ZixPatreeNode;
-
-struct _ZixPatree {
-	ZixPatreeNode* root;  /* Root of the tree */
-};
-
-static void
-zix_patree_print_rec(ZixPatreeNode* node, FILE* fd)
-{
-	if (node->label_first) {
-		size_t edge_label_len = node->label_last - node->label_first + 1;
-		char*  edge_label     = (char*)malloc(edge_label_len + 1);
-		strncpy(edge_label, node->label_first, edge_label_len);
-		fprintf(fd, "\t\"%p\" [label=<"
-		        "<TABLE BORDER=\"0\" CELLBORDER=\"1\" CELLSPACING=\"0\">"
-		        "<TR><TD>%s</TD></TR>", (void*)node, edge_label);
-		free(edge_label);
-		if (node->str) {
-			fprintf(fd, "<TR><TD>\"%s\"</TD></TR>", node->str);
-		}
-		fprintf(fd, "</TABLE>>,shape=\"plaintext\"] ;\n");
-	} else {
-		fprintf(fd, "\t\"%p\" [label=\"\"] ;\n", (void*)node);
-	}
-
-
-	for (n_edges_t i = 0; i < node->num_children; ++i) {
-		ZixPatreeNode* const child = node->children[i].child;
-		zix_patree_print_rec(child, fd);
-		fprintf(fd, "\t\"%p\" -> \"%p\" ;\n", (void*)node, (void*)child);
-	}
-}
-
-ZIX_API
-void
-zix_patree_print_dot(const ZixPatree* t, FILE* fd)
-{
-	fprintf(fd, "digraph Patree { \n");
-	zix_patree_print_rec(t->root, fd);
-	fprintf(fd, "}\n");
-}
-
-static inline ZixPatreeNode*
-realloc_node(ZixPatreeNode* n, int num_children)
-{
-	return (ZixPatreeNode*)realloc(n, sizeof(ZixPatreeNode)
-	                               + num_children * sizeof(ZixChildRef));
-}
-
-ZIX_API
-ZixPatree*
-zix_patree_new(void)
-{
-	ZixPatree* t = (ZixPatree*)malloc(sizeof(ZixPatree));
-	memset(t, '\0', sizeof(struct _ZixPatree));
-
-	t->root = realloc_node(NULL, 0);
-	memset(t->root, '\0', sizeof(ZixPatreeNode));
-
-	return t;
-}
-
-static void
-zix_patree_free_rec(ZixPatreeNode* n)
-{
-	if (n) {
-		for (n_edges_t i = 0; i < n->num_children; ++i) {
-			zix_patree_free_rec(n->children[i].child);
-		}
-		free(n);
-	}
-}
-
-ZIX_API
-void
-zix_patree_free(ZixPatree* t)
-{
-	zix_patree_free_rec(t->root);
-	free(t);
-}
-
-static inline bool
-patree_is_leaf(const ZixPatreeNode* n)
-{
-	return n->num_children == 0;
-}
-
-static bool
-patree_find_edge(const ZixPatreeNode* n, const char c, n_edges_t* const index)
-{
-	for (n_edges_t i = 0; i < n->num_children; ++i) {
-		if (n->children[i].first_char == c) {
-			*index = i;
-			return true;
-		}
-	}
-	return false;
-}
-
-static void
-patree_add_edge(ZixPatreeNode** n_ptr,
-                const char*     str,
-                const char*     first)
-{
-	ZixPatreeNode* n = *n_ptr;
-
-	const char* last = first;
-	for (; *last; ++last) ;
-	--last;
-
-	/* Interesting performance note: building a sorted array here makes
-	   the search considerably slower, regardless of whether binary search
-	   or the existing search algorithm is used.  I suppose moving things
-	   around blows the cache for child->children which trumps everything.
-	*/
-	assert(last >= first);
-
-	ZixPatreeNode* const child = realloc_node(NULL, 0);
-	child->label_first       = first;
-	child->label_last        = last;
-	child->str               = str;
-	child->num_children      = 0;
-
-	++n->num_children;
-	n = realloc_node(n, n->num_children);
-	n->children[n->num_children - 1].first_char = first[0];
-	n->children[n->num_children - 1].child      = child;
-
-	*n_ptr = n;
-
-	for (n_edges_t i = 0; i < n->num_children; ++i) {
-		assert(n->children[i].first_char != '\0');
-	}
-	for (n_edges_t i = 0; i < child->num_children; ++i) {
-		assert(child->children[i].first_char != '\0');
-	}
-}
-
-/* Split an outgoing edge (to a child) at the given index */
-static void
-patree_split_edge(ZixPatreeNode** child_ptr,
-                  size_t          index)
-{
-	ZixPatreeNode* child = *child_ptr;
-
-	const size_t grandchild_size = sizeof(ZixPatreeNode)
-		+ (child->num_children * sizeof(ZixChildRef));
-
-	ZixPatreeNode* const grandchild = realloc_node(NULL, child->num_children);
-	memcpy(grandchild, child, grandchild_size);
-	grandchild->label_first = child->label_first + index;
-
-	child = realloc_node(child, 1);
-	child->children[0].first_char = grandchild->label_first[0];
-	child->children[0].child = grandchild;
-	child->label_last = child->label_first + (index - 1);  // chop end
-
-	child->num_children = 1;
-
-	child->str = NULL;
-
-	*child_ptr = child;
-
-	for (n_edges_t i = 0; i < child->num_children; ++i) {
-		assert(child->children[i].first_char != '\0');
-	}
-	for (n_edges_t i = 0; i < grandchild->num_children; ++i) {
-		assert(grandchild->children[i].first_char != '\0');
-	}
-}
-
-static ZixStatus
-patree_insert_internal(ZixPatreeNode** n_ptr, const char* str, const char* first)
-{
-	ZixPatreeNode* n = *n_ptr;
-	n_edges_t      child_i;
-	if (patree_find_edge(n, *first, &child_i)) {
-		ZixPatreeNode**   child_ptr   = &n->children[child_i].child;
-		ZixPatreeNode*    child       = *child_ptr;
-		const char* const label_first = child->label_first;
-		const char* const label_last  = child->label_last;
-		size_t            split_i     = 0;
-		const size_t      label_len   = label_last - label_first + 1;
-
-		while (first[split_i] && split_i < label_len
-		       && first[split_i] == label_first[split_i]) {
-			++split_i;
-		}
-
-		if (first[split_i]) {
-			if (split_i == label_len) {
-				return patree_insert_internal(child_ptr, str, first + label_len);
-			} else {
-				patree_split_edge(child_ptr, split_i);
-				return patree_insert_internal(child_ptr, str, first + split_i);
-			}
-		} else if (label_len != split_i) {
-			patree_split_edge(child_ptr, split_i);
-			if (first[split_i]) {
-				patree_add_edge(child_ptr, str, first + split_i);
-			} else {
-				assert(!(*child_ptr)->str);
-				(*child_ptr)->str = str;
-			}
-			return ZIX_STATUS_SUCCESS;
-		} else if (label_first[split_i] && !child->str) {
-			child->str = str;
-		} else {
-			return ZIX_STATUS_EXISTS;
-		}
-	} else {
-		patree_add_edge(n_ptr, str, first);
-	}
-
-	return ZIX_STATUS_SUCCESS;
-}
-
-ZIX_API
-ZixStatus
-zix_patree_insert(ZixPatree* t, const char* str)
-{
-	return patree_insert_internal(&t->root, str, str);
-}
-
-static inline int
-change_index_c(const char* a, const char* b, size_t len)
-{
-	for (size_t i = 0; i < len; ++i) {
-		if (a[i] != b[i]) {
-			return i;
-		}
-	}
-	return len;
-}
-
-#ifdef __SSE4_2__
-static inline int
-change_index_sse(const char* a, const char* b, const size_t len)
-{
-	for (size_t i = 0; i < len; i += sizeof(__m128i)) {
-		const __m128i  r    = _mm_loadu_si128((const __m128i*)(a + i));
-		const __m128i* s    = (const __m128i*)(b + i);
-		const int     index = _mm_cmpistri(
-			r, *s, _SIDD_SBYTE_OPS|_SIDD_CMP_EQUAL_EACH|_SIDD_NEGATIVE_POLARITY);
-
-		if (index != sizeof(__m128i)) {
-			size_t ret = i + index;
-			if (ret > len) {
-				ret = len;
-			}
-			return ret;
-		}
-	}
-
-	return len;
-}
-#endif
-
-ZIX_API
-ZixStatus
-zix_patree_find(const ZixPatree* t, const char* const str, const char** match)
-{
-	ZixPatreeNode* n = t->root;
-	n_edges_t      child_i;
-
-	const char* p = str;
-
-	while (patree_find_edge(n, p[0], &child_i)) {
-		assert(child_i <= n->num_children);
-		ZixPatreeNode* const child     = n->children[child_i].child;
-		const char* const    child_str = child->str;
-
-		/* Prefix compare search string and label */
-		const char*       l     = child->label_first;
-		const char* const l_end = child->label_last;
-		const size_t      len   = l_end - l + 1;
-#ifdef __SSE4_2__
-		int change_index;
-		if (len >= sizeof(__m128i)) {
-			change_index = change_index_sse(p, l, len);
-		} else {
-			change_index = change_index_c(p, l, len);
-		}
-#else
-		int change_index = change_index_c(p, l, len);
-#endif
-
-		l += change_index;
-		p += change_index;
-
-#if 0
-		while (l <= l_end) {
-			if (*l++ != *p++) {
-				return ZIX_STATUS_NOT_FOUND;
-			}
-		}
-#endif
-
-		if (!*p) {
-			/* Reached end of search string */
-			if (l == l_end + 1) {
-				/* Reached end of label string as well, match */
-				*match = child_str;
-				return *match ? ZIX_STATUS_SUCCESS : ZIX_STATUS_NOT_FOUND;
-			} else {
-				/* Label string is longer, no match (prefix match) */
-				return ZIX_STATUS_NOT_FOUND;
-			}
-		} else {
-			/* Didn't reach end of search string */
-			if (patree_is_leaf(n)) {
-				/* Hit leaf early, no match */
-				return ZIX_STATUS_NOT_FOUND;
-			} else {
-				/* Match at this node, continue search downwards (or match) */
-				n  = child;
-			}
-		}
-	}
-
-	return ZIX_STATUS_NOT_FOUND;
-}
diff --git a/src/ring.c b/src/ring.c
deleted file mode 100644
index b701497..0000000
--- a/src/ring.c
+++ /dev/null
@@ -1,225 +0,0 @@
-/*
-  Copyright 2011 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 <stdint.h>
-#include <stdlib.h>
-#include <string.h>
-
-#ifdef HAVE_MLOCK
-#    include <sys/mman.h>
-#    define ZIX_MLOCK(ptr, size) mlock((ptr), (size))
-#elif defined(_WIN32)
-#    include <windows.h>
-#    define ZIX_MLOCK(ptr, size) VirtualLock((ptr), (size))
-#else
-#    pragma message("warning: No memory locking, possible RT violations")
-#    define ZIX_MLOCK(ptr, size)
-#endif
-
-#if defined(__APPLE__)
-#    include <libkern/OSAtomic.h>
-#    define ZIX_FULL_BARRIER() OSMemoryBarrier()
-#elif defined(_WIN32)
-#    include <windows.h>
-#    define ZIX_FULL_BARRIER() MemoryBarrier()
-#elif (__GNUC__ > 4) || (__GNUC__ == 4 && __GNUC_MINOR__ >= 1)
-#    define ZIX_FULL_BARRIER() __sync_synchronize()
-#else
-#    pragma message("warning: No memory barriers, possible SMP bugs")
-#    define ZIX_FULL_BARRIER()
-#endif
-
-/* No support for any systems with separate read and write barriers */
-#define ZIX_READ_BARRIER() ZIX_FULL_BARRIER()
-#define ZIX_WRITE_BARRIER() ZIX_FULL_BARRIER()
-
-#include "zix/ring.h"
-
-struct ZixRingImpl {
-	uint32_t write_head;  ///< Read index into buf
-	uint32_t read_head;   ///< Write index into buf
-	uint32_t size;        ///< Size (capacity) in bytes
-	uint32_t size_mask;   ///< Mask for fast modulo
-	char*    buf;         ///< Contents
-};
-
-static inline uint32_t
-next_power_of_two(uint32_t size)
-{
-	// http://graphics.stanford.edu/~seander/bithacks.html#RoundUpPowerOf2
-	size--;
-	size |= size >> 1;
-	size |= size >> 2;
-	size |= size >> 4;
-	size |= size >> 8;
-	size |= size >> 16;
-	size++;
-	return size;
-}
-
-ZixRing*
-zix_ring_new(uint32_t size)
-{
-	ZixRing* ring = (ZixRing*)malloc(sizeof(ZixRing));
-	ring->write_head = 0;
-	ring->read_head  = 0;
-	ring->size       = next_power_of_two(size);
-	ring->size_mask  = ring->size - 1;
-	ring->buf        = (char*)malloc(ring->size);
-	return ring;
-}
-
-void
-zix_ring_free(ZixRing* ring)
-{
-	free(ring->buf);
-	free(ring);
-}
-
-void
-zix_ring_mlock(ZixRing* ring)
-{
-	ZIX_MLOCK(ring, sizeof(ZixRing));
-	ZIX_MLOCK(ring->buf, ring->size);
-}
-
-void
-zix_ring_reset(ZixRing* ring)
-{
-	ring->write_head = 0;
-	ring->read_head  = 0;
-}
-
-static inline uint32_t
-read_space_internal(const ZixRing* ring, uint32_t r, uint32_t w)
-{
-	if (r < w) {
-		return w - r;
-	} else {
-		return (w - r + ring->size) & ring->size_mask;
-	}
-}
-
-uint32_t
-zix_ring_read_space(const ZixRing* ring)
-{
-	return read_space_internal(ring, ring->read_head, ring->write_head);
-}
-
-static inline uint32_t
-write_space_internal(const ZixRing* ring, uint32_t r, uint32_t w)
-{
-	if (r == w) {
-		return ring->size - 1;
-	} else if (r < w) {
-		return ((r - w + ring->size) & ring->size_mask) - 1;
-	} else {
-		return (r - w) - 1;
-	}
-}
-
-uint32_t
-zix_ring_write_space(const ZixRing* ring)
-{
-	return write_space_internal(ring, ring->read_head, ring->write_head);
-}
-
-uint32_t
-zix_ring_capacity(const ZixRing* ring)
-{
-	return ring->size - 1;
-}
-
-static inline uint32_t
-peek_internal(const ZixRing* ring, uint32_t r, uint32_t w,
-              uint32_t size, void* dst)
-{
-	if (read_space_internal(ring, r, w) < size) {
-		return 0;
-	}
-
-	if (r + size < ring->size) {
-		memcpy(dst, &ring->buf[r], size);
-	} else {
-		const uint32_t first_size = ring->size - r;
-		memcpy(dst, &ring->buf[r], first_size);
-		memcpy((char*)dst + first_size, &ring->buf[0], size - first_size);
-	}
-
-	return size;
-}
-
-uint32_t
-zix_ring_peek(ZixRing* ring, void* dst, uint32_t size)
-{
-	const uint32_t r = ring->read_head;
-	const uint32_t w = ring->write_head;
-
-	return peek_internal(ring, r, w, size, dst);
-}
-
-uint32_t
-zix_ring_read(ZixRing* ring, void* dst, uint32_t size)
-{
-	const uint32_t r = ring->read_head;
-	const uint32_t w = ring->write_head;
-
-	if (peek_internal(ring, r, w, size, dst)) {
-		ZIX_READ_BARRIER();
-		ring->read_head = (r + size) & ring->size_mask;
-		return size;
-	} else {
-		return 0;
-	}
-}
-
-uint32_t
-zix_ring_skip(ZixRing* ring, uint32_t size)
-{
-	const uint32_t r = ring->read_head;
-	const uint32_t w = ring->write_head;
-	if (read_space_internal(ring, r, w) < size) {
-		return 0;
-	}
-
-	ZIX_READ_BARRIER();
-	ring->read_head = (r + size) & ring->size_mask;
-	return size;
-}
-
-uint32_t
-zix_ring_write(ZixRing* ring, const void* src, uint32_t size)
-{
-	const uint32_t r = ring->read_head;
-	const uint32_t w = ring->write_head;
-	if (write_space_internal(ring, r, w) < size) {
-		return 0;
-	}
-
-	if (w + size <= ring->size) {
-		memcpy(&ring->buf[w], src, size);
-		ZIX_WRITE_BARRIER();
-		ring->write_head = (w + size) & ring->size_mask;
-	} else {
-		const uint32_t this_size = ring->size - w;
-		memcpy(&ring->buf[w], src, this_size);
-		memcpy(&ring->buf[0], (const char*)src + this_size, size - this_size);
-		ZIX_WRITE_BARRIER();
-		ring->write_head = size - this_size;
-	}
-
-	return size;
-}
diff --git a/src/sorted_array.c b/src/sorted_array.c
deleted file mode 100644
index f8e785d..0000000
--- a/src/sorted_array.c
+++ /dev/null
@@ -1,205 +0,0 @@
-/*
-  Copyright 2011 David Robillard <http://drobilla.net>
-
-  Permission to use, copy, modify, and/or distribute this software for any
-  purpose with or without fee is hereby granted, provided that the above
-  copyright notice and this permission notice appear in all copies.
-
-  THIS SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL WARRANTIES
-  WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF
-  MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR
-  ANY SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES
-  WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN
-  ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF
-  OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE.
-*/
-
-#include <assert.h>
-#include <stdint.h>
-#include <stdio.h>
-#include <stdlib.h>
-#include <string.h>
-
-#include "zix/common.h"
-#include "zix/sorted_array.h"
-
-// #define ZIX_SORTED_ARRAY_DUMP 1
-
-struct ZixSortedArrayImpl {
-	void*         array;
-	ZixComparator cmp;
-	void*         cmp_data;
-	size_t        elem_size;
-	size_t        num_elems;
-	bool          allow_duplicates;
-};
-
-#ifdef ZIX_SORTED_ARRAY_DUMP
-static void
-zix_sorted_array_print(ZixSortedArray* a)
-{
-	for (size_t i = 0; i < a->num_elems; ++i) {
-		printf(" %ld", *(intptr_t*)((char*)a->array + (i * a->elem_size)));
-	}
-	printf("\n");
-}
-#    define DUMP(a) zix_sorted_array_print(a)
-#else
-#    define DUMP(a)
-#endif
-
-ZIX_API
-ZixSortedArray*
-zix_sorted_array_new(bool          allow_duplicates,
-                     ZixComparator cmp,
-                     void*         cmp_data,
-                     size_t        elem_size)
-{
-	ZixSortedArray* a = (ZixSortedArray*)malloc(sizeof(ZixSortedArray));
-	a->array            = NULL;
-	a->cmp              = cmp;
-	a->cmp_data         = cmp_data;
-	a->elem_size        = elem_size;
-	a->num_elems        = 0;
-	a->allow_duplicates = allow_duplicates;
-	return a;
-}
-
-ZIX_API
-void
-zix_sorted_array_free(ZixSortedArray* a)
-{
-	free(a->array);
-	free(a);
-}
-
-ZIX_API
-size_t
-zix_sorted_array_size(ZixSortedArray* a)
-{
-	return a->num_elems;
-}
-
-ZIX_API
-ZixStatus
-zix_sorted_array_insert(ZixSortedArray*     a,
-                        const void*         e,
-                        ZixSortedArrayIter* ai)
-{
-	if (a->num_elems == 0) {
-		assert(!a->array);
-		a->array = malloc(a->elem_size);
-		memcpy(a->array, e, a->elem_size);
-		++a->num_elems;
-		*ai = a->array;
-		return ZIX_STATUS_SUCCESS;
-	}
-
-	zix_sorted_array_find(a, e, ai);
-	assert(*ai);
-	const size_t i = ((char*)*ai - (char*)a->array) / a->elem_size;
-
-	a->array = realloc(a->array, ++a->num_elems * a->elem_size);
-	memmove((char*)a->array + ((i + 1) * a->elem_size),
-	        (char*)a->array + (i * a->elem_size),
-	        (a->num_elems - i - 1) * a->elem_size);
-	memcpy((char*)a->array + (i * a->elem_size),
-	       e,
-	       a->elem_size);
-
-	*ai = (char*)a->array + (i * a->elem_size);
-	DUMP(t);
-	return ZIX_STATUS_SUCCESS;
-}
-
-ZIX_API
-ZixStatus
-zix_sorted_array_remove(ZixSortedArray* a, ZixSortedArrayIter ai)
-{
-	const size_t i = ((char*)ai - (char*)a->array) / a->elem_size;
-	memmove((char*)a->array + (i * a->elem_size),
-	        (char*)a->array + ((i + 1) * a->elem_size),
-	        (a->num_elems - i - 1) * a->elem_size);
-	--a->num_elems;
-	DUMP(a);
-	return ZIX_STATUS_SUCCESS;
-}
-
-static inline void*
-zix_sorted_array_index_unchecked(const ZixSortedArray* a, size_t index)
-{
-	return (char*)a->array + (a->elem_size * index);
-}
-
-ZIX_API
-void*
-zix_sorted_array_index(const ZixSortedArray* a, size_t index)
-{
-	if (index >= a->num_elems) {
-		return NULL;
-	}
-
-	return zix_sorted_array_index_unchecked(a, index);
-}
-
-ZIX_API
-ZixStatus
-zix_sorted_array_find(const ZixSortedArray* a,
-                      const void*           e,
-                      ZixSortedArrayIter*   ai)
-{
-	intptr_t lower = 0;
-	intptr_t upper = a->num_elems - 1;
-	while (upper >= lower) {
-		const intptr_t i      = lower + ((upper - lower) / 2);
-		void* const    elem_i = zix_sorted_array_index_unchecked(a, i);
-		const int      cmp    = a->cmp(elem_i, e, a->cmp_data);
-
-		if (cmp == 0) {
-			*ai = elem_i;
-			return ZIX_STATUS_SUCCESS;
-		} else if (cmp > 0) {
-			upper = i - 1;
-		} else {
-			lower = i + 1;
-		}
-	}
-
-	*ai = zix_sorted_array_index_unchecked(a, lower);
-	return ZIX_STATUS_NOT_FOUND;
-}
-
-ZIX_API
-void*
-zix_sorted_array_get_data(ZixSortedArrayIter ai)
-{
-	return ai;
-}
-
-ZIX_API
-ZixSortedArrayIter
-zix_sorted_array_begin(ZixSortedArray* a)
-{
-	return a->array;
-}
-
-ZIX_API
-ZixSortedArrayIter
-zix_sorted_array_end(ZixSortedArray* a)
-{
-	return (char*)a->array + (a->elem_size * a->num_elems);
-}
-
-ZIX_API
-bool
-zix_sorted_array_iter_is_end(ZixSortedArray* a, ZixSortedArrayIter i)
-{
-	return i != zix_sorted_array_end(a);
-}
-
-ZIX_API
-ZixSortedArrayIter
-zix_sorted_array_iter_next(ZixSortedArray* a, ZixSortedArrayIter i)
-{
-	return (char*)i + a->elem_size;
-}
diff --git a/src/strindex.c b/src/strindex.c
deleted file mode 100644
index bd97db5..0000000
--- a/src/strindex.c
+++ /dev/null
@@ -1,253 +0,0 @@
-/*
-   Copyright 2011 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.
- */
-
-#define _XOPEN_SOURCE 500
-
-#include <assert.h>
-#include <stdio.h>
-#include <stdlib.h>
-#include <string.h>
-
-#include "zix/common.h"
-#include "zix/strindex.h"
-
-typedef struct _ZixStrindexNode {
-	struct _ZixStrindexNode* children;      /* Children of this node */
-	size_t                   num_children;  /* Number of outgoing edges */
-	char*                    first;         /* Start of this suffix */
-	char*                    label_first;   /* Start of incoming label */
-	char*                    label_last;    /* End of incoming label */
-} ZixStrindexNode;
-
-struct _ZixStrindex {
-	char*            s;     /* String contained in this tree */
-	ZixStrindexNode* root;  /* Root of the tree */
-};
-
-static ZixStatus
-strindex_insert(ZixStrindexNode* n,
-                char*            suffix_first,
-                char*            first,
-                char*            last);
-
-ZIX_API
-ZixStrindex*
-zix_strindex_new(const char* s)
-{
-	ZixStrindex* t = (ZixStrindex*)malloc(sizeof(ZixStrindex));
-	memset(t, '\0', sizeof(struct _ZixStrindex));
-	t->s    = strdup(s);
-	t->root = (ZixStrindexNode*)malloc(sizeof(ZixStrindexNode));
-	memset(t->root, '\0', sizeof(ZixStrindexNode));
-	t->root->num_children = 0;
-	t->root->first        = t->s;
-
-	const size_t len = strlen(t->s);
-	for (size_t i = 0; i < len; ++i) {
-		strindex_insert(t->root, t->s + i, t->s + i, t->s + (len - 1));
-	}
-
-	return t;
-}
-
-static void
-zix_strindex_free_rec(ZixStrindexNode* n)
-{
-	if (n) {
-		for (size_t i = 0; i < n->num_children; ++i) {
-			zix_strindex_free_rec(&n->children[i]);
-		}
-		free(n->children);
-	}
-}
-
-ZIX_API
-void
-zix_strindex_free(ZixStrindex* t)
-{
-	zix_strindex_free_rec(t->root);
-	free(t->s);
-	free(t->root);
-	free(t);
-}
-
-static inline int
-strindex_is_leaf(ZixStrindexNode* n)
-{
-	return n->num_children == 0;
-}
-
-static int
-strindex_find_edge(ZixStrindexNode* n, char c, size_t* index)
-{
-	for (size_t i = 0; i < n->num_children; ++i) {
-		if (n->children[i].label_first[0] == c) {
-			*index = i;
-			return 1;
-		}
-	}
-	return 0;
-}
-
-static void
-strindex_add_edge(ZixStrindexNode* n,
-                  char*            suffix_first,
-                  char*            first,
-                  char*            last)
-{
-	assert(last > first);
-	n->children = (ZixStrindexNode*)realloc(
-		n->children, (n->num_children + 1) * sizeof(ZixStrindexNode));
-
-	memset(&n->children[n->num_children], '\0', sizeof(ZixStrindexNode));
-
-	n->children[n->num_children].first       = suffix_first;
-	n->children[n->num_children].label_first = first;
-	n->children[n->num_children].label_last  = last;
-	++n->num_children;
-}
-
-/* Split an outgoing edge (to a child) at the given index */
-static void
-strindex_split_edge(ZixStrindexNode* child,
-                    size_t           index)
-{
-	ZixStrindexNode* children     = child->children;
-	size_t           num_children = child->num_children;
-
-	char* first = child->label_first + index;
-	char* last  = child->label_last;
-	assert(last > first);
-	assert(child->first);
-
-	child->children = (ZixStrindexNode*)malloc(sizeof(ZixStrindexNode));
-
-	child->children[0].children     = children;
-	child->children[0].num_children = num_children;
-	child->children[0].first        = child->first;
-	child->children[0].label_first  = first;
-	child->children[0].label_last   = last;
-
-	child->label_last = child->label_first + (index - 1);  // chop end
-
-	child->num_children = 1;
-}
-
-static ZixStatus
-strindex_insert(ZixStrindexNode* n, char* suffix_first, char* first, char* last)
-{
-	size_t           child_i;
-	ZixStrindexNode* child;
-	assert(first <= last);
-
-	if (strindex_find_edge(n, *first, &child_i)) {
-		char*        label_first = n->children[child_i].label_first;
-		char*        label_last  = n->children[child_i].label_last;
-		size_t       split_i     = 0;
-		const size_t label_len   = label_last - label_first + 1;
-		const size_t s_len       = last - first + 1;
-		const size_t max_len     = (s_len < label_len) ? s_len : label_len;
-
-		while (split_i < max_len && first[split_i] == label_first[split_i]) {
-			++split_i;
-		}
-		child = n->children + child_i;
-
-		if (label_len < s_len) {
-			if (split_i == label_len) {
-				strindex_insert(child, suffix_first, first + label_len, last);
-			} else {
-				strindex_split_edge(child, split_i);
-				strindex_insert(child, suffix_first, first + split_i, last);
-			}
-		} else if ((label_len != split_i) && (label_len != s_len)) {
-			strindex_split_edge(child, split_i);
-			if (split_i != s_len) {
-				strindex_add_edge(child, suffix_first, first + split_i, last);
-			}
-		}
-	} else {
-		strindex_add_edge(n, suffix_first, first, last);
-	}
-
-	return ZIX_STATUS_SUCCESS;
-}
-
-ZIX_API
-ZixStatus
-zix_strindex_find(ZixStrindex* t, const char* p, char** match)
-{
-#ifndef NDEBUG
-	const char* orig_p = p;
-#endif
-
-	ZixStrindexNode* n = t->root;
-	size_t           child_i;
-
-	*match = NULL;
-
-	while (*p != '\0') {
-		size_t p_len = strlen(p);
-		if (strindex_find_edge(n, p[0], &child_i)) {
-			char*  label_first = n->children[child_i].label_first;
-			char*  label_last  = n->children[child_i].label_last;
-			size_t label_len   = label_last - label_first + 1;
-			size_t max_len     = (p_len < label_len) ? p_len : label_len;
-			assert(child_i <= n->num_children);
-			assert(max_len > 0);
-
-			/* Set match to the start of substring
-			   (but may not actually be a complete match yet)
-			 */
-			if (*match == NULL) {
-				assert(p[0] == orig_p[0]);
-				assert(orig_p[0] == label_first[0]);
-				*match = n->children[child_i].first;
-				assert((*match)[0] == orig_p[0]);
-			}
-
-			if (strncmp(p, label_first, max_len)) {
-				/* no match */
-				*match = NULL;
-				return ZIX_STATUS_NOT_FOUND;
-			}
-
-			if (p_len <= label_len) {
-				/* At the last node, match */
-				*match = n->children[child_i].first;
-				assert(!strncmp(*match, orig_p, strlen(orig_p)));
-				return ZIX_STATUS_SUCCESS;
-			} else if (strindex_is_leaf(n)) {
-				/* Hit leaf early, no match */
-				return ZIX_STATUS_NOT_FOUND;
-			} else {
-				/* Match at this node, continue search downwards (or match) */
-				p += label_len;
-				n  = &n->children[child_i];
-				if (label_len >= p_len) {
-					assert(strstr(t->s, orig_p) != NULL);
-					assert(strncmp(orig_p, *match, max_len));
-					return ZIX_STATUS_SUCCESS;
-				}
-			}
-
-		} else {
-			assert(strstr(t->s, orig_p) == NULL);
-			return ZIX_STATUS_NOT_FOUND;
-		}
-	}
-	return ZIX_STATUS_NOT_FOUND;
-}
diff --git a/src/tree.c b/src/tree.c
deleted file mode 100644
index 8523228..0000000
--- a/src/tree.c
+++ /dev/null
@@ -1,730 +0,0 @@
-/*
-  Copyright 2011 David Robillard <http://drobilla.net>
-
-  Permission to use, copy, modify, and/or distribute this software for any
-  purpose with or without fee is hereby granted, provided that the above
-  copyright notice and this permission notice appear in all copies.
-
-  THIS SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL WARRANTIES
-  WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF
-  MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR
-  ANY SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES
-  WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN
-  ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF
-  OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE.
-*/
-
-#include <assert.h>
-#include <stdint.h>
-#include <stdio.h>
-#include <stdlib.h>
-#include <string.h>
-
-#include "zix/common.h"
-#include "zix/tree.h"
-
-typedef struct ZixTreeNodeImpl ZixTreeNode;
-
-struct ZixTreeImpl {
-	ZixTreeNode*   root;
-	ZixDestroyFunc destroy;
-	ZixComparator  cmp;
-	void*          cmp_data;
-	size_t         size;
-	bool           allow_duplicates;
-};
-
-struct ZixTreeNodeImpl {
-	void*                   data;
-	struct ZixTreeNodeImpl* left;
-	struct ZixTreeNodeImpl* right;
-	struct ZixTreeNodeImpl* parent;
-	int_fast8_t             balance;
-};
-
-#define MIN(a, b) (((a) < (b)) ? (a) : (b))
-#define MAX(a, b) (((a) > (b)) ? (a) : (b))
-
-// Uncomment these for debugging features
-// #define ZIX_TREE_DUMP         1
-// #define ZIX_TREE_VERIFY       1
-// #define ZIX_TREE_HYPER_VERIFY 1
-
-#if defined(ZIX_TREE_VERIFY) || defined(ZIX_TREE_HYPER_VERIFY)
-#    include "tree_debug.h"
-#    define ASSERT_BALANCE(n) assert(verify_balance(n))
-#else
-#    define ASSERT_BALANCE(n)
-#endif
-
-#ifdef ZIX_TREE_DUMP
-#    include "tree_debug.h"
-#    define DUMP(t) zix_tree_print(t->root, 0)
-#    define DEBUG_PRINTF(fmt, ...) printf(fmt, __VA_ARGS__)
-#else
-#    define DUMP(t)
-#    define DEBUG_PRINTF(fmt, ...)
-#endif
-
-ZIX_API
-ZixTree*
-zix_tree_new(bool           allow_duplicates,
-             ZixComparator  cmp,
-             void*          cmp_data,
-             ZixDestroyFunc destroy)
-{
-	ZixTree* t = (ZixTree*)malloc(sizeof(ZixTree));
-	t->root             = NULL;
-	t->destroy          = destroy;
-	t->cmp              = cmp;
-	t->cmp_data         = cmp_data;
-	t->size             = 0;
-	t->allow_duplicates = allow_duplicates;
-	return t;
-}
-
-static void
-zix_tree_free_rec(ZixTree* t, ZixTreeNode* n)
-{
-	if (n) {
-		zix_tree_free_rec(t, n->left);
-		zix_tree_free_rec(t, n->right);
-		if (t->destroy) {
-			t->destroy(n->data);
-		}
-		free(n);
-	}
-}
-
-ZIX_API
-void
-zix_tree_free(ZixTree* t)
-{
-	if (t) {
-		zix_tree_free_rec(t, t->root);
-		free(t);
-	}
-}
-
-size_t
-zix_tree_size(const ZixTree* t)
-{
-	return t->size;
-}
-
-static void
-rotate(ZixTreeNode* p, ZixTreeNode* q)
-{
-	assert(q->parent == p);
-	assert(p->left == q || p->right == q);
-
-	q->parent = p->parent;
-	if (q->parent) {
-		if (q->parent->left == p) {
-			q->parent->left = q;
-		} else {
-			q->parent->right = q;
-		}
-	}
-
-	if (p->right == q) {
-		// Rotate left
-		p->right = q->left;
-		q->left  = p;
-		if (p->right) {
-			p->right->parent = p;
-		}
-	} else {
-		// Rotate right
-		assert(p->left == q);
-		p->left  = q->right;
-		q->right = p;
-		if (p->left) {
-			p->left->parent = p;
-		}
-	}
-
-	p->parent = q;
-}
-
-/**
- * Rotate left about @a p.
- *
- *    p              q
- *   / \            / \
- *  A   q    =>    p   C
- *     / \        / \
- *    B   C      A   B
- */
-static ZixTreeNode*
-rotate_left(ZixTreeNode* p, int* height_change)
-{
-	ZixTreeNode* const q = p->right;
-	*height_change = (q->balance == 0) ? 0 : -1;
-
-	DEBUG_PRINTF("LL %ld\n", (intptr_t)p->data);
-
-	assert(p->balance == 2);
-	assert(q->balance == 0 || q->balance == 1);
-
-	rotate(p, q);
-
-	// p->balance -= 1 + MAX(0, q->balance);
-	// q->balance -= 1 - MIN(0, p->balance);
-	--q->balance;
-	p->balance = -(q->balance);
-
-	ASSERT_BALANCE(p);
-	ASSERT_BALANCE(q);
-	return q;
-}
-
-/**
- * Rotate right about @a p.
- *
- *      p          q
- *     / \        / \
- *    q   C  =>  A   p
- *   / \            / \
- *  A   B          B   C
- *
- */
-static ZixTreeNode*
-rotate_right(ZixTreeNode* p, int* height_change)
-{
-	ZixTreeNode* const q = p->left;
-	*height_change = (q->balance == 0) ? 0 : -1;
-
-	DEBUG_PRINTF("RR %ld\n", (intptr_t)p->data);
-
-	assert(p->balance == -2);
-	assert(q->balance == 0 || q->balance == -1);
-
-	rotate(p, q);
-
-	// p->balance += 1 - MIN(0, q->balance);
-	// q->balance += 1 + MAX(0, p->balance);
-	++q->balance;
-	p->balance = -(q->balance);
-
-	ASSERT_BALANCE(p);
-	ASSERT_BALANCE(q);
-	return q;
-}
-
-/**
- * Rotate left about @a p->left then right about @a p.
- *
- *      p             r
- *     / \           / \
- *    q   D  =>    q     p
- *   / \          / \   / \
- *  A   r        A   B C   D
- *     / \
- *    B   C
- *
- */
-static ZixTreeNode*
-rotate_left_right(ZixTreeNode* p, int* height_change)
-{
-	ZixTreeNode* const q = p->left;
-	ZixTreeNode* const r = q->right;
-
-	assert(p->balance == -2);
-	assert(q->balance == 1);
-	assert(r->balance == -1 || r->balance == 0 || r->balance == 1);
-
-	DEBUG_PRINTF("LR %ld  P: %2d  Q: %2d  R: %2d\n",
-	             (intptr_t)p->data, p->balance, q->balance, r->balance);
-
-	rotate(q, r);
-	rotate(p, r);
-
-	q->balance -= 1 + MAX(0, r->balance);
-	p->balance += 1 - MIN(MIN(0, r->balance) - 1, r->balance + q->balance);
-	// r->balance += MAX(0, p->balance) + MIN(0, q->balance);
-
-	// p->balance = (p->left && p->right) ? -MIN(r->balance, 0) : 0;
-	// q->balance = - MAX(r->balance, 0);
-	r->balance = 0;
-
-	*height_change = -1;
-
-	ASSERT_BALANCE(p);
-	ASSERT_BALANCE(q);
-	ASSERT_BALANCE(r);
-	return r;
-}
-
-/**
- * Rotate right about @a p->right then right about @a p.
- *
- *    p               r
- *   / \             / \
- *  A   q    =>    p     q
- *     / \        / \   / \
- *    r   D      A   B C   D
- *   / \
- *  B   C
- *
- */
-static ZixTreeNode*
-rotate_right_left(ZixTreeNode* p, int* height_change)
-{
-	ZixTreeNode* const q = p->right;
-	ZixTreeNode* const r = q->left;
-
-	assert(p->balance == 2);
-	assert(q->balance == -1);
-	assert(r->balance == -1 || r->balance == 0 || r->balance == 1);
-
-	DEBUG_PRINTF("RL %ld  P: %2d  Q: %2d  R: %2d\n",
-	             (intptr_t)p->data, p->balance, q->balance, r->balance);
-
-	rotate(q, r);
-	rotate(p, r);
-
-	q->balance += 1 - MIN(0, r->balance);
-	p->balance -= 1 + MAX(MAX(0, r->balance) + 1, r->balance + q->balance);
-	// r->balance += MAX(0, q->balance) + MIN(0, p->balance);
-
-	// p->balance = (p->left && p->right) ? -MAX(r->balance, 0) : 0;
-	// q->balance = - MIN(r->balance, 0);
-	r->balance = 0;
-	// assert(r->balance == 0);
-
-	*height_change = -1;
-
-	ASSERT_BALANCE(p);
-	ASSERT_BALANCE(q);
-	ASSERT_BALANCE(r);
-	return r;
-}
-
-static ZixTreeNode*
-zix_tree_rebalance(ZixTree* t, ZixTreeNode* node, int* height_change)
-{
-#ifdef ZIX_TREE_HYPER_VERIFY
-	const size_t old_height = height(node);
-#endif
-	DEBUG_PRINTF("REBALANCE %ld (%d)\n", (intptr_t)node->data, node->balance);
-	*height_change = 0;
-	const bool is_root = !node->parent;
-	assert((is_root && t->root == node) || (!is_root && t->root != node));
-	ZixTreeNode* replacement = node;
-	if (node->balance == -2) {
-		assert(node->left);
-		if (node->left->balance == 1) {
-			replacement = rotate_left_right(node, height_change);
-		} else {
-			replacement = rotate_right(node, height_change);
-		}
-	} else if (node->balance == 2) {
-		assert(node->right);
-		if (node->right->balance == -1) {
-			replacement = rotate_right_left(node, height_change);
-		} else {
-			replacement = rotate_left(node, height_change);
-		}
-	}
-	if (is_root) {
-		assert(!replacement->parent);
-		t->root = replacement;
-	}
-	DUMP(t);
-#ifdef ZIX_TREE_HYPER_VERIFY
-	assert(old_height + *height_change == height(replacement));
-#endif
-	return replacement;
-}
-
-ZIX_API
-ZixStatus
-zix_tree_insert(ZixTree* t, void* e, ZixTreeIter** ti)
-{
-	DEBUG_PRINTF("**** INSERT %ld\n", (intptr_t)e);
-	int          cmp = 0;
-	ZixTreeNode* n   = t->root;
-	ZixTreeNode* p   = NULL;
-
-	// Find the parent p of e
-	while (n) {
-		p   = n;
-		cmp = t->cmp(e, n->data, t->cmp_data);
-		if (cmp < 0) {
-			n = n->left;
-		} else if (cmp > 0) {
-			n = n->right;
-		} else if (t->allow_duplicates) {
-			n = n->right;
-		} else {
-			if (ti) {
-				*ti = n;
-			}
-			DEBUG_PRINTF("%ld EXISTS!\n", (intptr_t)e);
-			return ZIX_STATUS_EXISTS;
-		}
-	}
-
-	// Allocate a new node n
-	if (!(n = (ZixTreeNode*)malloc(sizeof(ZixTreeNode)))) {
-		return ZIX_STATUS_NO_MEM;
-	}
-	memset(n, '\0', sizeof(ZixTreeNode));
-	n->data    = e;
-	n->balance = 0;
-	if (ti) {
-		*ti = n;
-	}
-
-	bool p_height_increased = false;
-
-	// Make p the parent of n
-	n->parent = p;
-	if (!p) {
-		t->root = n;
-	} else {
-		if (cmp < 0) {
-			assert(!p->left);
-			assert(p->balance == 0 || p->balance == 1);
-			p->left = n;
-			--p->balance;
-			p_height_increased = !p->right;
-		} else {
-			assert(!p->right);
-			assert(p->balance == 0 || p->balance == -1);
-			p->right = n;
-			++p->balance;
-			p_height_increased = !p->left;
-		}
-	}
-
-	DUMP(t);
-
-	// Rebalance if necessary (at most 1 rotation)
-	assert(!p || p->balance == -1 || p->balance == 0 || p->balance == 1);
-	if (p && p_height_increased) {
-		int height_change = 0;
-		for (ZixTreeNode* i = p; i && i->parent; i = i->parent) {
-			if (i == i->parent->left) {
-				if (--i->parent->balance == -2) {
-					zix_tree_rebalance(t, i->parent, &height_change);
-					break;
-				}
-			} else {
-				assert(i == i->parent->right);
-				if (++i->parent->balance == 2) {
-					zix_tree_rebalance(t, i->parent, &height_change);
-					break;
-				}
-			}
-
-			if (i->parent->balance == 0) {
-				break;
-			}
-		}
-	}
-
-	DUMP(t);
-
-	++t->size;
-
-#ifdef ZIX_TREE_VERIFY
-	if (!verify(t, t->root)) {
-		return ZIX_STATUS_ERROR;
-	}
-#endif
-
-	return ZIX_STATUS_SUCCESS;
-}
-
-ZIX_API
-ZixStatus
-zix_tree_remove(ZixTree* t, ZixTreeIter* ti)
-{
-	ZixTreeNode* const n          = ti;
-	ZixTreeNode**      pp         = NULL;  // parent pointer
-	ZixTreeNode*       to_balance = n->parent;  // lowest node to balance
-	int8_t             d_balance  = 0;  // delta(balance) for n->parent
-
-	DEBUG_PRINTF("*** REMOVE %ld\n", (intptr_t)n->data);
-
-	if ((n == t->root) && !n->left && !n->right) {
-		t->root = NULL;
-		if (t->destroy) {
-			t->destroy(n->data);
-		}
-		free(n);
-		--t->size;
-		assert(t->size == 0);
-		return ZIX_STATUS_SUCCESS;
-	}
-
-	// Set pp to the parent pointer to n, if applicable
-	if (n->parent) {
-		assert(n->parent->left == n || n->parent->right == n);
-		if (n->parent->left == n) {  // n is left child
-			pp        = &n->parent->left;
-			d_balance = 1;
-		} else {  // n is right child
-			assert(n->parent->right == n);
-			pp        = &n->parent->right;
-			d_balance = -1;
-		}
-	}
-
-	assert(!pp || *pp == n);
-
-	int height_change = 0;
-	if (!n->left && !n->right) {
-		// n is a leaf, just remove it
-		if (pp) {
-			*pp           = NULL;
-			to_balance    = n->parent;
-			height_change = (!n->parent->left && !n->parent->right) ? -1 : 0;
-		}
-	} else if (!n->left) {
-		// Replace n with right (only) child
-		if (pp) {
-			*pp        = n->right;
-			to_balance = n->parent;
-		} else {
-			t->root = n->right;
-		}
-		n->right->parent = n->parent;
-		height_change    = -1;
-	} else if (!n->right) {
-		// Replace n with left (only) child
-		if (pp) {
-			*pp        = n->left;
-			to_balance = n->parent;
-		} else {
-			t->root = n->left;
-		}
-		n->left->parent = n->parent;
-		height_change   = -1;
-	} else {
-		// Replace n with in-order successor (leftmost child of right subtree)
-		ZixTreeNode* replace = n->right;
-		while (replace->left) {
-			assert(replace->left->parent == replace);
-			replace = replace->left;
-		}
-
-		// Remove replace from parent (replace_p)
-		if (replace->parent->left == replace) {
-			height_change = replace->parent->right ? 0 : -1;
-			d_balance     = 1;
-			to_balance    = replace->parent;
-			replace->parent->left = replace->right;
-		} else {
-			assert(replace->parent == n);
-			height_change = replace->parent->left ? 0 : -1;
-			d_balance     = -1;
-			to_balance    = replace->parent;
-			replace->parent->right = replace->right;
-		}
-
-		if (to_balance == n) {
-			to_balance = replace;
-		}
-
-		if (replace->right) {
-			replace->right->parent = replace->parent;
-		}
-
-		replace->balance = n->balance;
-
-		// Swap node to delete with replace
-		if (pp) {
-			*pp = replace;
-		} else {
-			assert(t->root == n);
-			t->root = replace;
-		}
-		replace->parent = n->parent;
-		replace->left   = n->left;
-		n->left->parent = replace;
-		replace->right  = n->right;
-		if (n->right) {
-			n->right->parent = replace;
-		}
-
-		assert(!replace->parent
-		       || replace->parent->left == replace
-		       || replace->parent->right == replace);
-	}
-
-	// Rebalance starting at to_balance upwards.
-	for (ZixTreeNode* i = to_balance; i; i = i->parent) {
-		i->balance += d_balance;
-		if (d_balance == 0 || i->balance == -1 || i->balance == 1) {
-			break;
-		}
-
-		assert(i != n);
-		i = zix_tree_rebalance(t, i, &height_change);
-		if (i->balance == 0) {
-			height_change = -1;
-		}
-
-		if (i->parent) {
-			if (i == i->parent->left) {
-				d_balance = height_change * -1;
-			} else {
-				assert(i == i->parent->right);
-				d_balance = height_change;
-			}
-		}
-	}
-
-	DUMP(t);
-
-	if (t->destroy) {
-		t->destroy(n->data);
-	}
-	free(n);
-
-	--t->size;
-
-#ifdef ZIX_TREE_VERIFY
-	if (!verify(t, t->root)) {
-		return ZIX_STATUS_ERROR;
-	}
-#endif
-
-	return ZIX_STATUS_SUCCESS;
-}
-
-ZIX_API
-ZixStatus
-zix_tree_find(const ZixTree* t, const void* e, ZixTreeIter** ti)
-{
-	ZixTreeNode* n = t->root;
-	while (n) {
-		const int cmp = t->cmp(e, n->data, t->cmp_data);
-		if (cmp == 0) {
-			break;
-		} else if (cmp < 0) {
-			n = n->left;
-		} else {
-			n = n->right;
-		}
-	}
-
-	*ti = n;
-	return (n) ? ZIX_STATUS_SUCCESS : ZIX_STATUS_NOT_FOUND;
-}
-
-ZIX_API
-void*
-zix_tree_get(ZixTreeIter* ti)
-{
-	return ti ? ti->data : NULL;
-}
-
-ZIX_API
-ZixTreeIter*
-zix_tree_begin(ZixTree* t)
-{
-	if (!t->root) {
-		return NULL;
-	}
-
-	ZixTreeNode* n = t->root;
-	while (n->left) {
-		n = n->left;
-	}
-	return n;
-}
-
-ZIX_API
-ZixTreeIter*
-zix_tree_end(ZixTree* t)
-{
-	return NULL;
-}
-
-ZIX_API
-ZixTreeIter*
-zix_tree_rbegin(ZixTree* t)
-{
-	if (!t->root) {
-		return NULL;
-	}
-
-	ZixTreeNode* n = t->root;
-	while (n->right) {
-		n = n->right;
-	}
-	return n;
-}
-
-ZIX_API
-ZixTreeIter*
-zix_tree_rend(ZixTree* t)
-{
-	return NULL;
-}
-
-ZIX_API
-bool
-zix_tree_iter_is_end(ZixTreeIter* i)
-{
-	return !i;
-}
-
-ZIX_API
-bool
-zix_tree_iter_is_rend(ZixTreeIter* i)
-{
-	return !i;
-}
-
-ZIX_API
-ZixTreeIter*
-zix_tree_iter_next(ZixTreeIter* i)
-{
-	if (!i) {
-		return NULL;
-	}
-
-	if (i->right) {
-		i = i->right;
-		while (i->left) {
-			i = i->left;
-		}
-	} else {
-		while (i->parent && i->parent->right == i) {  // i is a right child
-			i = i->parent;
-		}
-
-		i = i->parent;
-	}
-
-	return i;
-}
-
-ZIX_API
-ZixTreeIter*
-zix_tree_iter_prev(ZixTreeIter* i)
-{
-	if (!i) {
-		return NULL;
-	}
-
-	if (i->left) {
-		i = i->left;
-		while (i->right) {
-			i = i->right;
-		}
-	} else {
-		while (i->parent && i->parent->left == i) {  // i is a left child
-			i = i->parent;
-		}
-
-		i = i->parent;
-	}
-
-	return i;
-}
diff --git a/src/tree_debug.h b/src/tree_debug.h
deleted file mode 100644
index e903265..0000000
--- a/src/tree_debug.h
+++ /dev/null
@@ -1,159 +0,0 @@
-/*
-  Copyright 2011 David Robillard <http://drobilla.net>
-
-  Permission to use, copy, modify, and/or distribute this software for any
-  purpose with or without fee is hereby granted, provided that the above
-  copyright notice and this permission notice appear in all copies.
-
-  THIS SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL WARRANTIES
-  WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF
-  MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR
-  ANY SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES
-  WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN
-  ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF
-  OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE.
-*/
-
-#ifndef ZIX_TREE_DEBUG_H
-#define ZIX_TREE_DEBUG_H
-
-#ifndef _MSC_VER
-#    include <inttypes.h>
-#endif
-
-#ifdef ZIX_TREE_DUMP
-static void
-zix_tree_print(ZixTreeNode* node, int level)
-{
-	if (node) {
-		if (!node->parent) {
-			printf("{{{\n");
-		}
-		zix_tree_print(node->right, level + 1);
-		for (int i = 0; i < level; i++) {
-			printf("  ");
-		}
-		printf("%ld.%d\n", (intptr_t)node->data, node->balance);
-		zix_tree_print(node->left, level + 1);
-		if (!node->parent) {
-			printf("}}}\n");
-		}
-	}
-}
-#endif
-
-#ifdef ZIX_TREE_HYPER_VERIFY
-static size_t
-height(ZixTreeNode* n)
-{
-	if (!n) {
-		return 0;
-	} else {
-		return 1 + MAX(height(n->left), height(n->right));
-	}
-}
-#endif
-
-#if defined(ZIX_TREE_VERIFY) || !defined(NDEBUG)
-static bool
-verify_balance(ZixTreeNode* n)
-{
-	if (!n) {
-		return true;
-	}
-
-	if (n->balance < -2 || n->balance > 2) {
-		fprintf(stderr, "Balance out of range : %ld (balance %d)\n",
-		        (intptr_t)n->data, n->balance);
-		return false;
-	}
-
-	if (n->balance < 0 && !n->left) {
-		fprintf(stderr, "Bad balance : %ld (balance %d) has no left child\n",
-		        (intptr_t)n->data, n->balance);
-		return false;
-	}
-
-	if (n->balance > 0 && !n->right) {
-		fprintf(stderr, "Bad balance : %ld (balance %d) has no right child\n",
-		        (intptr_t)n->data, n->balance);
-		return false;
-	}
-
-	if (n->balance != 0 && !n->left && !n->right) {
-		fprintf(stderr, "Bad balance : %ld (balance %d) has no children\n",
-		        (intptr_t)n->data, n->balance);
-		return false;
-	}
-
-#ifdef ZIX_TREE_HYPER_VERIFY
-	const intptr_t left_height  = (intptr_t)height(n->left);
-	const intptr_t right_height = (intptr_t)height(n->right);
-	if (n->balance != right_height - left_height) {
-		fprintf(stderr, "Bad balance at %ld: h_r (%" PRIdPTR ")"
-		        "- l_h (%" PRIdPTR ") != %d\n",
-		        (intptr_t)n->data, right_height, left_height, n->balance);
-		assert(false);
-		return false;
-	}
-#endif
-
-	return true;
-}
-#endif
-
-#ifdef ZIX_TREE_VERIFY
-static bool
-verify(ZixTree* t, ZixTreeNode* n)
-{
-	if (!n) {
-		return true;
-	}
-
-	if (n->parent) {
-		if ((n->parent->left != n) && (n->parent->right != n)) {
-			fprintf(stderr, "Corrupt child/parent pointers\n");
-			return false;
-		}
-	}
-
-	if (n->left) {
-		if (t->cmp(n->left->data, n->data, t->cmp_data) > 0) {
-			fprintf(stderr, "Bad order: %" PRIdPTR " with left child\n",
-			        (intptr_t)n->data);
-			fprintf(stderr, "%p ? %p\n", (void*)n, (void*)n->left);
-			fprintf(stderr, "%" PRIdPTR " ? %" PRIdPTR "\n", (intptr_t)n->data,
-			        (intptr_t)n->left->data);
-			return false;
-		}
-		if (!verify(t, n->left)) {
-			return false;
-		}
-	}
-
-	if (n->right) {
-		if (t->cmp(n->right->data, n->data, t->cmp_data) < 0) {
-			fprintf(stderr, "Bad order: %" PRIdPTR " with right child\n",
-			        (intptr_t)n->data);
-			return false;
-		}
-		if (!verify(t, n->right)) {
-			return false;
-		}
-	}
-
-	if (!verify_balance(n)) {
-		return false;
-	}
-
-	if (n->balance <= -2 || n->balance >= 2) {
-		fprintf(stderr, "Imbalance: %p (balance %d)\n",
-		        (void*)n, n->balance);
-		return false;
-	}
-
-	return true;
-}
-#endif
-
-#endif  // ZIX_TREE_DEBUG_H