Remove glib dependency

git-svn-id: http://svn.drobilla.net/sord/trunk@163 3d64ff67-21c5-427c-a301-fe4f08042e5a

7 files changed, 1199 insertions, 132 deletions

diff --git a/src/sord.c b/src/sord.c
index eafc99f..241e5c9 100644
--- a/src/sord.c
+++ b/src/sord.c
@@ -23,8 +23,8 @@
 #include <stdlib.h>
 #include <string.h>
 
-// GLib
-#include <glib.h>
+#include "zix/hash.h"
+#include "zix/tree.h"
 
 #include "sord-config.h"
 #include "sord_internal.h"
@@ -54,7 +54,7 @@
 #define DEFAULT_GRAPH_ORDER GSPO
 
 #define TUP_FMT         "(%s %s %s %s)"
-#define TUP_FMT_ELEM(e) ((e) ? sord_node_get_string(e) : "*")
+#define TUP_FMT_ELEM(e) ((e) ? sord_node_get_string(e) : (const uint8_t*)"*")
 #define TUP_FMT_ARGS(t) \
 	TUP_FMT_ELEM((t)[0]), \
 	TUP_FMT_ELEM((t)[1]), \
@@ -99,10 +99,10 @@ static const int orderings[NUM_ORDERS][TUP_LEN] = {
 
 /** World */
 struct SordWorldImpl {
-	GHashTable* names;    ///< URI or blank node identifier string => ID
-	GHashTable* langs;    ///< Language tag => Interned language tag
-	GHashTable* literals; ///< Literal => ID
-	size_t      n_nodes;  ///< Number of nodes
+	ZixHash* names;    ///< URI or blank node identifier string => ID
+	ZixHash* langs;    ///< Language tag => Interned language tag
+	ZixHash* literals; ///< Literal => ID
+	size_t   n_nodes;  ///< Number of nodes
 };
 
 /** Store */
@@ -113,7 +113,7 @@ struct SordModelImpl {
 	 * If an index for e.g. SPO exists, it is a dictionary with
 	 * (S P O) keys (as a SordTuplrID), and ignored values.
 	 */
-	GSequence* indices[NUM_ORDERS];
+	ZixTree* indices[NUM_ORDERS];
 
 	size_t n_quads;
 };
@@ -130,7 +130,7 @@ typedef enum {
 /** Iterator over some range of a store */
 struct SordIterImpl {
 	const SordModel* sord;              ///< Store this is an iterator for
-	GSequenceIter*   cur;               ///< Current DB cursor
+	ZixTreeIter*     cur;               ///< Current DB cursor
 	SordQuad         pat;               ///< Iteration pattern (in ordering order)
 	int              ordering[TUP_LEN]; ///< Store ordering
 	SearchMode       mode;              ///< Iteration mode
@@ -143,17 +143,18 @@ static unsigned
 sord_literal_hash(const void* n)
 {
 	SordNode* node = (SordNode*)n;
-	return g_str_hash(node->node.buf) + (node->lang ? g_str_hash(node->lang) : 0);
+	return zix_string_hash(node->node.buf)
+		+ (node->lang ? zix_string_hash(node->lang) : 0);
 }
 
-static gboolean
+static bool
 sord_literal_equal(const void* a, const void* b)
 {
 	SordNode* a_node = (SordNode*)a;
 	SordNode* b_node = (SordNode*)b;
 	return (a_node == b_node)
-		|| (g_str_equal(sord_node_get_string(a_node),
-		                sord_node_get_string(b_node))
+		|| (zix_string_equal(sord_node_get_string(a_node),
+		                     sord_node_get_string(b_node))
 		    && (a_node->lang == b_node->lang)
 		    && (a_node->datatype == b_node->datatype));
 }
@@ -162,32 +163,39 @@ SordWorld*
 sord_world_new(void)
 {
 	SordWorld* world = malloc(sizeof(struct SordWorldImpl));
-	world->names    = g_hash_table_new_full(g_str_hash, g_str_equal, 0, 0);
-	world->langs    = g_hash_table_new_full(g_str_hash, g_str_equal, g_free, 0);
-	world->literals = g_hash_table_new_full(sord_literal_hash, sord_literal_equal, 0, 0);
+	world->names    = zix_hash_new(zix_string_hash, zix_string_equal);
+	world->langs    = zix_hash_new(zix_string_hash, zix_string_equal);
+	world->literals = zix_hash_new(sord_literal_hash, sord_literal_equal);
 	world->n_nodes  = 0;
 	return world;
 }
 
 static void
-free_hash_entry(void* key, void* value, void* user_data)
+free_node_entry(const void* key, void* value, void* user_data)
 {
 	SordNode* node = (SordNode*)value;
 	if (node->node.type == SERD_LITERAL) {
 		sord_node_free((SordWorld*)user_data, node->datatype);
 	}
-	g_free((uint8_t*)node->node.buf);
+	free((uint8_t*)node->node.buf);
 	free(node);
 }
 
+static void
+free_lang_entry(const void* key, void* value, void* user_data)
+{
+	free(value);
+}
+
 void
 sord_world_free(SordWorld* world)
 {
-	g_hash_table_foreach(world->literals, free_hash_entry, world);
-	g_hash_table_foreach(world->names, free_hash_entry, world);
-	g_hash_table_unref(world->names);
-	g_hash_table_unref(world->langs);
-	g_hash_table_unref(world->literals);
+	zix_hash_foreach(world->literals, free_node_entry, world);
+	zix_hash_foreach(world->names, free_node_entry, world);
+	zix_hash_foreach(world->langs, free_lang_entry, world);
+	zix_hash_free(world->names);
+	zix_hash_free(world->langs);
+	zix_hash_free(world->literals);
 	free(world);
 }
 
@@ -195,7 +203,7 @@ static inline int
 sord_node_compare(const SordNode* a, const SordNode* b)
 {
 	if (a == b || !a || !b) {
-		return (const char*)a - (const char*)b;
+		return 0;
 	} else if (a->node.type != b->node.type) {
 		return a->node.type - b->node.type;
 	}
@@ -274,8 +282,9 @@ sord_quad_compare(const void* x_ptr, const void* y_ptr, void* user_data)
 	for (int i = 0; i < TUP_LEN; ++i) {
 		const int idx = ordering[i];
 		const int cmp = sord_node_compare(x[idx], y[idx]);
-		if (cmp)
+		if (cmp) {
 			return cmp;
+		}
 	}
 
 	return 0;
@@ -285,18 +294,18 @@ static inline bool
 sord_iter_forward(SordIter* iter)
 {
 	if (!iter->skip_graphs) {
-		iter->cur = g_sequence_iter_next(iter->cur);
-		return g_sequence_iter_is_end(iter->cur);
+		iter->cur = zix_tree_iter_next(iter->cur);
+		return zix_tree_iter_is_end(iter->cur);
 	}
 
-	SordNode** key = (SordNode**)g_sequence_get(iter->cur);
+	SordNode** key = (SordNode**)zix_tree_get(iter->cur);
 	const SordQuad initial = { key[0], key[1], key[2], key[3] };
 	while (true) {
-		iter->cur = g_sequence_iter_next(iter->cur);
-		if (g_sequence_iter_is_end(iter->cur))
+		iter->cur = zix_tree_iter_next(iter->cur);
+		if (zix_tree_iter_is_end(iter->cur))
 			return true;
 
-		key = (SordNode**)g_sequence_get(iter->cur);
+		key = (SordNode**)zix_tree_get(iter->cur);
 		for (int i = 0; i < 3; ++i)
 			if (key[i] != initial[i])
 				return false;
@@ -312,9 +321,9 @@ static inline bool
 sord_iter_seek_match(SordIter* iter)
 {
 	for (iter->end = true;
-	     !g_sequence_iter_is_end(iter->cur);
+	     !zix_tree_iter_is_end(iter->cur);
 	     sord_iter_forward(iter)) {
-		const SordNode** const key = (const SordNode**)g_sequence_get(iter->cur);
+		const SordNode** const key = (const SordNode**)zix_tree_get(iter->cur);
 		if (sord_quad_match_inline(key, iter->pat))
 			return (iter->end = false);
 	}
@@ -333,7 +342,7 @@ sord_iter_seek_match_range(SordIter* iter)
 		return true;
 
 	do {
-		const SordNode** key = (const SordNode**)g_sequence_get(iter->cur);
+		const SordNode** key = (const SordNode**)zix_tree_get(iter->cur);
 
 		if (sord_quad_match_inline(key, iter->pat))
 			return false; // Found match
@@ -351,7 +360,7 @@ sord_iter_seek_match_range(SordIter* iter)
 }
 
 static SordIter*
-sord_iter_new(const SordModel* sord, GSequenceIter* cur, const SordQuad pat,
+sord_iter_new(const SordModel* sord, ZixTreeIter* cur, const SordQuad pat,
               SordOrder order, SearchMode mode, int n_prefix)
 {
 	const int* ordering = orderings[order];
@@ -373,7 +382,7 @@ sord_iter_new(const SordModel* sord, GSequenceIter* cur, const SordQuad pat,
 	case SINGLE:
 	case RANGE:
 		assert(
-			sord_quad_match_inline((const SordNode**)g_sequence_get(iter->cur),
+			sord_quad_match_inline((const SordNode**)zix_tree_get(iter->cur),
 			                       iter->pat));
 		break;
 	case FILTER_RANGE:
@@ -403,7 +412,7 @@ sord_iter_get_model(SordIter* iter)
 void
 sord_iter_get(const SordIter* iter, SordQuad id)
 {
-	SordNode** key = (SordNode**)g_sequence_get(iter->cur);
+	SordNode** key = (SordNode**)zix_tree_get(iter->cur);
 	for (int i = 0; i < TUP_LEN; ++i) {
 		id[i] = key[i];
 	}
@@ -429,7 +438,7 @@ sord_iter_next(SordIter* iter)
 		case RANGE:
 			SORD_ITER_LOG("%p range next\n", (void*)iter);
 			// At the end if the MSNs no longer match
-			key = (const SordNode**)g_sequence_get(iter->cur);
+			key = (const SordNode**)zix_tree_get(iter->cur);
 			assert(key);
 			for (int i = 0; i < iter->n_prefix; ++i) {
 				const int idx = iter->ordering[i];
@@ -573,10 +582,15 @@ sord_new(SordWorld* world, unsigned indices, bool graphs)
 	sord->n_quads = 0;
 
 	for (unsigned i = 0; i < (NUM_ORDERS / 2); ++i) {
+		const int* const ordering   = orderings[i];
+		const int* const g_ordering = orderings[i + (NUM_ORDERS / 2)];
+
 		if (indices & (1 << i)) {
-			sord->indices[i] = g_sequence_new(NULL);
+			sord->indices[i] = zix_tree_new(
+				false, sord_quad_compare, (void*)ordering);
 			if (graphs) {
-				sord->indices[i + (NUM_ORDERS / 2)] = g_sequence_new(NULL);
+				sord->indices[i + (NUM_ORDERS / 2)] = zix_tree_new(
+					false, sord_quad_compare, (void*)g_ordering);
 			} else {
 				sord->indices[i + (NUM_ORDERS / 2)] = NULL;
 			}
@@ -587,7 +601,8 @@ sord_new(SordWorld* world, unsigned indices, bool graphs)
 	}
 
 	if (!sord->indices[DEFAULT_ORDER]) {
-		sord->indices[DEFAULT_ORDER] = g_sequence_new(NULL);
+		sord->indices[DEFAULT_ORDER] = zix_tree_new(
+			false, sord_quad_compare, (void*)orderings[DEFAULT_ORDER]);
 	}
 
 	return sord;
@@ -598,18 +613,18 @@ sord_node_free_internal(SordWorld* world, SordNode* node)
 {
 	assert(node->refs == 0);
 	if (node->node.type == SERD_LITERAL) {
-		if (!g_hash_table_remove(world->literals, node)) {
+		if (zix_hash_remove(world->literals, node)) {
 			fprintf(stderr, "Failed to remove literal from hash.\n");
 			return;
 		}
 		sord_node_free(world, node->datatype);
 	} else {
-		if (!g_hash_table_remove(world->names, node->node.buf)) {
+		if (zix_hash_remove(world->names, node->node.buf)) {
 			fprintf(stderr, "Failed to remove resource from hash.\n");
 			return;
 		}
 	}
-	g_free((uint8_t*)node->node.buf);
+	free((uint8_t*)node->node.buf);
 	free(node);
 }
 
@@ -660,16 +675,16 @@ sord_free(SordModel* sord)
 	sord_iter_free(i);
 
 	// Free quads
-	for (GSequenceIter* i = g_sequence_get_begin_iter(sord->indices[DEFAULT_ORDER]);
-	     !g_sequence_iter_is_end(i);
-	     i = g_sequence_iter_next(i)) {
-		free(g_sequence_get(i));
+	for (ZixTreeIter* i = zix_tree_begin(sord->indices[DEFAULT_ORDER]);
+	     !zix_tree_iter_is_end(i);
+	     i = zix_tree_iter_next(i)) {
+		free(zix_tree_get(i));
 	}
 
 	// Free indices
 	for (unsigned i = 0; i < NUM_ORDERS; ++i)
 		if (sord->indices[i])
-			g_sequence_free(sord->indices[i]);
+			zix_tree_free(sord->indices[i]);
 
 	free(sord);
 }
@@ -698,67 +713,47 @@ sord_begin(const SordModel* sord)
 	if (sord_num_quads(sord) == 0) {
 		return NULL;
 	} else {
-		GSequenceIter* cur = g_sequence_get_begin_iter(sord->indices[DEFAULT_ORDER]);
+		ZixTreeIter* cur = zix_tree_begin(sord->indices[DEFAULT_ORDER]);
 		SordQuad pat = { 0, 0, 0, 0 };
 		return sord_iter_new(sord, cur, pat, DEFAULT_ORDER, ALL, 0);
 	}
 }
 
-static inline GSequenceIter*
-index_search(GSequence* db, const SordQuad search_key, const int* ordering)
+static inline ZixTreeIter*
+index_search(ZixTree* db, const SordQuad search_key)
 {
-	return g_sequence_search(
-		db, (void*)search_key, sord_quad_compare, (void*)ordering);
+	ZixTreeIter* iter = NULL;
+	zix_tree_find(db, (void*)search_key, &iter);
+	if (!iter) {
+		fprintf(stderr, "SEARCH FAILED\n");
+	}
+	return iter;
 }
 
-static inline GSequenceIter*
-index_lower_bound_iter(GSequenceIter* i, const SordQuad search_key)
+static inline ZixTreeIter*
+index_lower_bound(ZixTree* db, const SordQuad search_key)
 {
-	/* i is now at the position where search_key would be inserted,
-	   but this is not necessarily a match, and we need the leftmost...
-	*/
-
-	if (g_sequence_iter_is_begin(i)) {
-		return i;
-	} else if (g_sequence_iter_is_end(i)) {
-		i = g_sequence_iter_prev(i);
+	ZixTreeIter* iter = NULL;
+	zix_tree_find(db, (void*)search_key, &iter);
+	if (!iter) {
+		return NULL;
 	}
 
-	if (!sord_quad_match_inline(search_key, g_sequence_get(i))) {
-		// No match, but perhaps immediately after a match
-		GSequenceIter* const prev = g_sequence_iter_prev(i);
-		if (!sord_quad_match_inline(search_key, g_sequence_get(prev))) {
-			return i; // No match (caller must check)
-		} else {
-			i = prev;
+	ZixTreeIter* prev = NULL;
+	while ((prev = zix_tree_iter_prev(iter))) {
+		if (!prev) {
+			return iter;
 		}
-	}
 
-	/* i now points to some matching element,
-	   but not necessarily the first...
-	*/
-	assert(sord_quad_match_inline(search_key, g_sequence_get(i)));
-
-	while (!g_sequence_iter_is_begin(i)) {
-		if (sord_quad_match_inline(search_key, g_sequence_get(i))) {
-			GSequenceIter* const prev = g_sequence_iter_prev(i);
-			if (sord_quad_match_inline(search_key, g_sequence_get(prev))) {
-				i = prev;
-				continue;
-			}
+		const SordNode** const key = (const SordNode**)zix_tree_get(prev);
+		if (!sord_quad_match_inline(key, search_key)) {
+			return iter;
 		}
-		break;
-	}
 
-	return i;
-}
+		iter = prev;
+	}
 
-static inline GSequenceIter*
-index_lower_bound(GSequence* db, const SordQuad search_key, const int* ordering)
-{
-	GSequenceIter* i = g_sequence_search(
-		db, (void*)search_key, sord_quad_compare, (void*)ordering);
-	return index_lower_bound_iter(i, search_key);
+	return iter;
 }
 
 SordIter*
@@ -767,10 +762,9 @@ sord_find(SordModel* sord, const SordQuad pat)
 	if (!pat[0] && !pat[1] && !pat[2] && !pat[3])
 		return sord_begin(sord);
 
-	SearchMode          mode;
-	int                 prefix_len;
-	const SordOrder     index_order = sord_best_index(sord, pat, &mode, &prefix_len);
-	const int* const    ordering    = orderings[index_order];
+	SearchMode      mode;
+	int             prefix_len;
+	const SordOrder index_order = sord_best_index(sord, pat, &mode, &prefix_len);
 
 	SORD_FIND_LOG("Find " TUP_FMT "  index=%s  mode=%d  prefix_len=%d ordering=%d%d%d%d\n",
 	              TUP_FMT_ARGS(pat), order_names[index_order], mode, prefix_len,
@@ -779,13 +773,13 @@ sord_find(SordModel* sord, const SordQuad pat)
 	if (pat[0] && pat[1] && pat[2] && pat[3])
 		mode = SINGLE; // No duplicate quads (Sord is a set)
 
-	GSequence* const     db  = sord->indices[index_order];
-	GSequenceIter* const cur = index_lower_bound(db, pat, ordering);
-	if (g_sequence_iter_is_end(cur)) {
+	ZixTree* const     db  = sord->indices[index_order];
+	ZixTreeIter* const cur = index_lower_bound(db, pat);
+	if (zix_tree_iter_is_end(cur)) {
 		SORD_FIND_LOG("No match found\n");
 		return NULL;
 	}
-	const SordNode** const key = (const SordNode**)g_sequence_get(cur);
+	const SordNode** const key = (const SordNode**)zix_tree_get(cur);
 	if (!key || ( (mode == RANGE || mode == SINGLE)
 	              && !sord_quad_match_inline(pat, key) )) {
 		SORD_FIND_LOG("No match found\n");
@@ -807,7 +801,15 @@ sord_contains(SordModel* sord, const SordQuad pat)
 static SordNode*
 sord_lookup_name(SordWorld* world, const uint8_t* str)
 {
-	return g_hash_table_lookup(world->names, str);
+	return zix_hash_find(world->names, str);
+}
+
+char*
+sord_strndup(const char* str, size_t len)
+{
+	char* dup = malloc(len + 1);
+	memcpy(dup, str, len + 1);
+	return dup;
 }
 
 static SordNode*
@@ -820,7 +822,7 @@ sord_new_node(SerdType type, const uint8_t* data,
 	node->datatype     = datatype;
 	node->refs         = 1;
 	node->refs_as_obj  = 0;
-	node->node.buf     = (uint8_t*)g_strdup((const char*)data);
+	node->node.buf     = (uint8_t*)sord_strndup((const char*)data, n_bytes);
 	node->node.n_bytes = n_bytes;
 	node->node.n_chars = n_chars;
 	node->node.flags   = flags;
@@ -833,10 +835,10 @@ const char*
 sord_intern_lang(SordWorld* world, const char* lang)
 {
 	if (lang) {
-		char* ilang = g_hash_table_lookup(world->langs, lang);
+		char* ilang = zix_hash_find(world->langs, lang);
 		if (!ilang) {
-			ilang = g_strdup(lang);
-			g_hash_table_insert(world->langs, ilang, ilang);
+			ilang = sord_strndup(lang, strlen(lang));
+			zix_hash_insert(world->langs, ilang, ilang);
 		}
 		lang = ilang;
 	}
@@ -859,7 +861,7 @@ sord_lookup_literal(SordWorld* world, SordNode* type,
 	key.node.flags   = 0;
 	key.node.type    = SERD_LITERAL;
 
-	SordNode* id = g_hash_table_lookup(world->literals, &key);
+	SordNode* id = zix_hash_find(world->literals, &key);
 	if (id) {
 		return id;
 	} else {
@@ -937,8 +939,8 @@ sord_new_uri_counted(SordWorld* world, const uint8_t* str,
 	}
 
 	node = sord_new_node(SERD_URI, str, n_bytes, n_chars, 0, 0, 0);
-	assert(!g_hash_table_lookup(world->names, node->node.buf));
-	g_hash_table_insert(world->names, (char*)node->node.buf, node);
+	assert(!zix_hash_find(world->names, node->node.buf));
+	zix_hash_insert(world->names, (char*)node->node.buf, node);
 	sord_add_node(world, node);
 	return node;
 }
@@ -961,7 +963,7 @@ sord_new_blank_counted(SordWorld* world, const uint8_t* str,
 	}
 
 	node = sord_new_node(SERD_BLANK, str, n_bytes, n_chars, 0, 0, 0);
-	g_hash_table_insert(world->names, (char*)node->node.buf, node);
+	zix_hash_insert(world->names, (char*)node->node.buf, node);
 	sord_add_node(world, node);
 	return node;
 }
@@ -989,7 +991,7 @@ sord_new_literal_counted(SordWorld* world, SordNode* datatype,
 	node = sord_new_node(SERD_LITERAL,
 	                     str, n_bytes, n_chars, flags,
 	                     sord_node_copy(datatype), lang);
-	g_hash_table_insert(world->literals, node, node);  // FIXME: correct?
+	zix_hash_insert(world->literals, node, node);  // FIXME: correct?
 	sord_add_node(world, node);
 	assert(node->refs == 1);
 	return node;
@@ -1103,17 +1105,7 @@ sord_node_copy(const SordNode* node)
 static inline bool
 sord_add_to_index(SordModel* sord, const SordNode** tup, SordOrder order)
 {
-	assert(sord->indices[order]);
-	const int* const     ordering = orderings[order];
-	GSequenceIter* const cur      = index_search(sord->indices[order], tup, ordering);
-	GSequenceIter* const match    = index_lower_bound_iter(cur, tup);
-	if (!g_sequence_iter_is_end(match)
-	    && !sord_quad_compare(g_sequence_get(match), tup, (void*)ordering)) {
-		return false;  // Quad already stored in this index
-	}
-
-	g_sequence_insert_before(cur, tup);
-	return true;
+	return !zix_tree_insert(sord->indices[order], tup, NULL);
 }
 
 bool
@@ -1142,7 +1134,7 @@ sord_add(SordModel* sord, const SordQuad tup)
 		sord_add_quad_ref(sord, tup[i], i);
 
 	++sord->n_quads;
-	assert(sord->n_quads == (size_t)g_sequence_get_length(sord->indices[SPO]));
+	//assert(sord->n_quads == (size_t)zix_tree_get_length(sord->indices[SPO]));
 	return true;
 }
 
@@ -1154,14 +1146,12 @@ sord_remove(SordModel* sord, const SordQuad tup)
 	SordNode** quad = NULL;
 	for (unsigned i = 0; i < NUM_ORDERS; ++i) {
 		if (sord->indices[i]) {
-			const int* const     ordering = orderings[i];
-			GSequenceIter* const cur      = index_lower_bound(
-				sord->indices[i], tup, ordering);
-			if (!g_sequence_iter_is_end(cur)) {
+			ZixTreeIter* const cur = index_search(sord->indices[i], tup);
+			if (!zix_tree_iter_is_end(cur)) {
 				if (!quad) {
-					quad = g_sequence_get(cur);
+					quad = zix_tree_get(cur);
 				}
-				g_sequence_remove(cur);
+				zix_tree_remove(sord->indices[i], cur);
 			} else {
 				assert(i == 0); // Assuming index coherency
 				return; // Quad not found, do nothing
diff --git a/src/syntax.c b/src/syntax.c
index ac87ad4..d7e4195 100644
--- a/src/syntax.c
+++ b/src/syntax.c
@@ -18,8 +18,6 @@
 #include <stdlib.h>
 #include <string.h>
 
-#include <glib.h>
-
 #include "serd/serd.h"
 
 #include "sord-config.h"
diff --git a/src/zix/common.h b/src/zix/common.h
new file mode 100644
index 0000000..a7edf76
--- /dev/null
+++ b/src/zix/common.h
@@ -0,0 +1,67 @@
+/*
+  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_COMMON_H
+#define ZIX_COMMON_H
+
+#include <stdbool.h>
+
+/**
+   @addtogroup zix
+   @{
+*/
+
+/** @cond */
+#ifdef ZIX_SHARED
+#    ifdef __WIN32__
+#        define ZIX_LIB_IMPORT __declspec(dllimport)
+#        define ZIX_LIB_EXPORT __declspec(dllexport)
+#    else
+#        define ZIX_LIB_IMPORT __attribute__((visibility("default")))
+#        define ZIX_LIB_EXPORT __attribute__((visibility("default")))
+#    endif
+#    ifdef ZIX_INTERNAL
+#        define ZIX_API ZIX_LIB_EXPORT
+#    else
+#        define ZIX_API ZIX_LIB_IMPORT
+#    endif
+#else
+#    define ZIX_API
+#endif
+/** @endcond */
+
+typedef enum {
+	ZIX_STATUS_SUCCESS,
+	ZIX_STATUS_ERROR,
+	ZIX_STATUS_NO_MEM,
+	ZIX_STATUS_NOT_FOUND,
+	ZIX_STATUS_EXISTS,
+} ZixStatus;
+
+/**
+   Function for comparing two elements.
+*/
+typedef int (*ZixComparator)(const void* a, const void* b, void* user_data);
+
+/**
+   Function for testing equality of two elements.
+*/
+typedef bool (*ZixEqualFunc)(const void* a, const void* b);
+   
+/**@}
+*/
+
+#endif  /* ZIX_COMMON_H */
diff --git a/src/zix/hash.c b/src/zix/hash.c
new file mode 100644
index 0000000..c267757
--- /dev/null
+++ b/src/zix/hash.c
@@ -0,0 +1,226 @@
+/*
+  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        = 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/zix/hash.h b/src/zix/hash.h
new file mode 100644
index 0000000..44521f1
--- /dev/null
+++ b/src/zix/hash.h
@@ -0,0 +1,75 @@
+/*
+  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_HASH_H
+#define ZIX_HASH_H
+
+#include "zix/common.h"
+
+#ifdef __cplusplus
+extern "C" {
+#endif
+
+typedef struct ZixHashImpl ZixHash;
+
+/**
+   Function for computing the hash of an element.
+*/
+typedef unsigned (*ZixHashFunc)(const void* key);
+
+ZIX_API
+ZixHash*
+zix_hash_new(ZixHashFunc  hash_func,
+             ZixEqualFunc key_equal_func);
+
+ZIX_API
+void
+zix_hash_free(ZixHash* hash);
+
+ZIX_API
+unsigned
+zix_string_hash(const void* key);
+
+ZIX_API
+bool
+zix_string_equal(const void* a, const void* b);
+
+ZIX_API
+ZixStatus
+zix_hash_insert(ZixHash*    hash,
+                const void* key,
+                void*       data);
+
+ZIX_API
+ZixStatus
+zix_hash_remove(ZixHash* hash, const void* key);
+
+ZIX_API
+void*
+zix_hash_find(const ZixHash* hash,
+              const void*    key);
+
+ZIX_API
+void
+zix_hash_foreach(const ZixHash* hash,
+                 void (*f)(const void* key, void* value, void* user_data),
+                 void* user_data);
+
+#ifdef __cplusplus
+}  /* extern "C" */
+#endif
+
+#endif  /* ZIX_HASH_H */
diff --git a/src/zix/tree.c b/src/zix/tree.c
new file mode 100644
index 0000000..30ac3e2
--- /dev/null
+++ b/src/zix/tree.c
@@ -0,0 +1,590 @@
+/*
+  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 <inttypes.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;
+	ZixComparator cmp;
+	void*         cmp_data;
+	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))
+
+ZIX_API
+ZixTree*
+zix_tree_new(bool allow_duplicates, ZixComparator cmp, void* cmp_data)
+{
+	ZixTree* t = malloc(sizeof(ZixTree));
+	t->root             = NULL;
+	t->cmp              = cmp;
+	t->cmp_data         = cmp_data;
+	t->allow_duplicates = allow_duplicates;
+	return t;
+}
+
+static void
+zix_tree_free_rec(ZixTreeNode* n)
+{
+	if (n) {
+		zix_tree_free_rec(n->left);
+		zix_tree_free_rec(n->right);
+		free(n);
+	}
+}
+
+ZIX_API
+void
+zix_tree_free(ZixTree* t)
+{
+	zix_tree_free_rec(t->root);
+
+	free(t);
+}
+
+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;
+
+	assert(p->balance == 2);
+	assert(q->balance == 0 || q->balance == 1);
+
+	rotate(p, q);
+
+	--q->balance;
+	p->balance = -(q->balance);
+
+	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;
+
+	assert(p->balance == -2);
+	assert(q->balance == 0 || q->balance == -1);
+
+	rotate(p, q);
+
+	++q->balance;
+	p->balance = -(q->balance);
+
+	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);
+
+	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 = 0;
+
+	*height_change = -1;
+
+	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);
+
+	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 = 0;
+
+	*height_change = -1;
+
+	return r;
+}
+
+static ZixTreeNode*
+zix_tree_rebalance(ZixTree* t, ZixTreeNode* node, int* height_change)
+{
+	*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;
+	}
+
+	return replacement;
+}
+
+ZIX_API
+ZixStatus
+zix_tree_insert(ZixTree* t, void* e, ZixTreeIter** ti)
+{
+	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;
+			}
+			return ZIX_STATUS_EXISTS;
+		}
+	}
+
+	// Allocate a new node n
+	if (!(n = 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;
+		}
+	}
+
+	// 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;
+			}
+		}
+	}
+
+	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
+
+	if ((n == t->root) && !n->left && !n->right) {
+		t->root = NULL;
+		free(n);
+		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;
+			}
+		}
+	}
+
+	free(n);
+
+	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->data;
+}
+
+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
+bool
+zix_tree_iter_is_end(ZixTreeIter* i)
+{
+	return !i;
+}
+
+ZIX_API
+ZixTreeIter*
+zix_tree_iter_next(ZixTreeIter* i)
+{
+	if (!i) {
+		return NULL;
+	}
+
+	if (i->right) {
+		i = i->right;
+		while (i->left) {
+			i = i->left;
+		}
+	} else {
+		while (i->parent && i->parent->right == i) {  // i is a right child
+			i = i->parent;
+		}
+
+		i = i->parent;
+	}
+
+	return i;
+}
+
+ZIX_API
+ZixTreeIter*
+zix_tree_iter_prev(ZixTreeIter* i)
+{
+	if (!i) {
+		return NULL;
+	}
+
+	if (i->left) {
+		i = i->left;
+		while (i->right) {
+			i = i->right;
+		}
+	} else {
+		while (i->parent && i->parent->left == i) {  // i is a left child
+			i = i->parent;
+		}
+
+		i = i->parent;
+	}
+
+	return i;
+}
diff --git a/src/zix/tree.h b/src/zix/tree.h
new file mode 100644
index 0000000..670c437
--- /dev/null
+++ b/src/zix/tree.h
@@ -0,0 +1,121 @@
+/*
+  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_H
+#define ZIX_TREE_H
+
+#include <stdbool.h>
+
+#include "zix/common.h"
+
+#ifdef __cplusplus
+extern "C" {
+#endif
+
+/**
+   @addtogroup zix
+   @{
+   @name Tree
+   @{
+*/
+
+/**
+   A balanced binary search tree.
+*/
+typedef struct ZixTreeImpl ZixTree;
+
+/**
+   An iterator over a @ref ZixTree.
+*/
+typedef struct ZixTreeNodeImpl ZixTreeIter;
+
+/**
+   Create a new (empty) tree.
+*/
+ZixTree*
+zix_tree_new(bool allow_duplicates, ZixComparator cmp, void* cmp_data);
+
+/**
+   Free @a t.
+*/
+void
+zix_tree_free(ZixTree* t);
+
+/**
+   Insert the element @a e into @a t and point @a ti at the new element.
+*/
+ZixStatus
+zix_tree_insert(ZixTree* t, void* e, ZixTreeIter** ti);
+
+/**
+   Remove the item pointed at by @a ti from @a t.
+*/
+ZixStatus
+zix_tree_remove(ZixTree* t, ZixTreeIter* ti);
+
+/**
+   Set @a ti to an element equal to @a e in @a t.
+   If no such item exists, @a ti is set to NULL.
+*/
+ZixStatus
+zix_tree_find(const ZixTree* t, const void* e, ZixTreeIter** ti);
+
+/**
+   Return the data associated with the given tree item.
+*/
+void*
+zix_tree_get(ZixTreeIter* ti);
+
+/**
+   Return an iterator to the first (smallest) element in @a t.
+*/
+ZixTreeIter*
+zix_tree_begin(ZixTree* t);
+
+/**
+   Return an iterator the the element one past the last element in @a t.
+*/
+ZixTreeIter*
+zix_tree_end(ZixTree* t);
+
+/**
+   Return true iff @a i is an iterator to the end of its tree.
+*/
+bool
+zix_tree_iter_is_end(ZixTreeIter* i);
+
+/**
+   Return an iterator that points to the element one past @a i.
+*/
+ZixTreeIter*
+zix_tree_iter_next(ZixTreeIter* i);
+
+/**
+   Return an iterator that points to the element one before @a i.
+*/
+ZixTreeIter*
+zix_tree_iter_prev(ZixTreeIter* i);
+
+/**
+   @}
+   @}
+*/
+
+#ifdef __cplusplus
+}  /* extern "C" */
+#endif
+
+#endif  /* ZIX_TREE_H */