Remove glib dependency

git-svn-id: http://svn.drobilla.net/lad/trunk/lilv@3501 a436a847-0d15-0410-975c-d299462d15a1

13 files changed, 820 insertions, 92 deletions

diff --git a/ChangeLog b/ChangeLog
index 4bc1805..46413e9 100644
--- a/ChangeLog
+++ b/ChangeLog
@@ -1,5 +1,6 @@
 lilv (UNRELEASED) unstable; urgency=low
 
+  * Remove glib dependency
   * Add lv2core as a pkg-config dependency (for lv2.h header include)
   * Obey prefix when installing bash completion script
   * Support integer minimum, maximum, and default port values in
diff --git a/src/collections.c b/src/collections.c
index b969aff..fc24669 100644
--- a/src/collections.c
+++ b/src/collections.c
@@ -14,36 +14,40 @@
   OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE.
 */
 
-#include <glib.h>
-
 #include "lilv_internal.h"
 
+int
+lilv_ptr_cmp(const void* a, const void* b, void* user_data)
+{
+	return (intptr_t)a - (intptr_t)b;
+}
+
 /* Generic collection functions */
 
 static inline LilvCollection*
-lilv_collection_new(GDestroyNotify destructor)
+lilv_collection_new(ZixComparator cmp, ZixDestroyFunc destructor)
 {
-	return g_sequence_new(destructor);
+	return zix_tree_new(false, cmp, NULL, destructor);
 }
 
 void
 lilv_collection_free(LilvCollection* coll)
 {
 	if (coll)
-		g_sequence_free((GSequence*)coll);
+		zix_tree_free((ZixTree*)coll);
 }
 
 unsigned
 lilv_collection_size(const LilvCollection* coll)
 {
-	return (coll ? g_sequence_get_length((GSequence*)coll) : 0);
+	return (coll ? zix_tree_size((ZixTree*)coll) : 0);
 }
 
 LilvIter*
 lilv_collection_begin(const LilvCollection* collection)
 {
 	if (collection) {
-		return g_sequence_get_begin_iter((LilvCollection*)collection);
+		return zix_tree_begin((LilvCollection*)collection);
 	}
 	return NULL;
 }
@@ -52,7 +56,7 @@ void*
 lilv_collection_get(const LilvCollection* collection,
                     const LilvIter*       i)
 {
-	return g_sequence_get((GSequenceIter*)i);
+	return zix_tree_get((ZixTreeIter*)i);
 }
 
 /* Constructors */
@@ -60,25 +64,29 @@ lilv_collection_get(const LilvCollection* collection,
 LilvScalePoints*
 lilv_scale_points_new(void)
 {
-	return lilv_collection_new((GDestroyNotify)lilv_scale_point_free);
+	return lilv_collection_new(lilv_ptr_cmp,
+	                           (ZixDestroyFunc)lilv_scale_point_free);
 }
 
 LilvNodes*
 lilv_nodes_new(void)
 {
-	return lilv_collection_new((GDestroyNotify)lilv_node_free);
+	return lilv_collection_new(lilv_ptr_cmp,
+	                           (ZixDestroyFunc)lilv_node_free);
 }
 
 LilvUIs*
 lilv_uis_new(void)
 {
-	return lilv_collection_new((GDestroyNotify)lilv_ui_free);
+	return lilv_collection_new(lilv_header_compare_by_uri,
+	                           (ZixDestroyFunc)lilv_ui_free);
 }
 
 LilvPluginClasses*
 lilv_plugin_classes_new(void)
 {
-	return lilv_collection_new((GDestroyNotify)lilv_plugin_class_free);
+	return lilv_collection_new(lilv_header_compare_by_uri,
+	                           (ZixDestroyFunc)lilv_plugin_class_free);
 }
 
 /* URI based accessors (for collections of things with URIs) */
@@ -88,14 +96,14 @@ const LilvPluginClass*
 lilv_plugin_classes_get_by_uri(const LilvPluginClasses* coll,
                                const LilvNode*          uri)
 {
-	return (LilvPluginClass*)lilv_sequence_get_by_uri(coll, uri);
+	return (LilvPluginClass*)lilv_collection_get_by_uri(coll, uri);
 }
 
 LILV_API
 const LilvUI*
 lilv_uis_get_by_uri(const LilvUIs* coll, const LilvNode* uri)
 {
-	return (LilvUI*)lilv_sequence_get_by_uri((LilvUIs*)coll, uri);
+	return (LilvUI*)lilv_collection_get_by_uri((LilvUIs*)coll, uri);
 }
 
 /* Plugins */
@@ -103,14 +111,14 @@ lilv_uis_get_by_uri(const LilvUIs* coll, const LilvNode* uri)
 LilvPlugins*
 lilv_plugins_new(void)
 {
-	return g_sequence_new(NULL);
+	return lilv_collection_new(lilv_header_compare_by_uri, NULL);
 }
 
 LILV_API
 const LilvPlugin*
 lilv_plugins_get_by_uri(const LilvPlugins* list, const LilvNode* uri)
 {
-	return (LilvPlugin*)lilv_sequence_get_by_uri((LilvPlugins*)list, uri);
+	return (LilvPlugin*)lilv_collection_get_by_uri((LilvPlugins*)list, uri);
 }
 
 /* Nodes */
@@ -131,13 +139,13 @@ lilv_nodes_contains(const LilvNodes* list, const LilvNode* value)
 LilvIter*
 lilv_iter_next(LilvIter* i)
 {
-	return g_sequence_iter_next((GSequenceIter*)i);
+	return zix_tree_iter_next((ZixTreeIter*)i);
 }
 
 bool
 lilv_iter_end(LilvIter* i)
 {
-	return !i || g_sequence_iter_is_end((GSequenceIter*)i);
+	return !i || zix_tree_iter_is_end((ZixTreeIter*)i);
 }
 
 #define LILV_COLLECTION_IMPL(prefix, CT, ET) \
diff --git a/src/lilv_internal.h b/src/lilv_internal.h
index 770f144..03252a3 100644
--- a/src/lilv_internal.h
+++ b/src/lilv_internal.h
@@ -36,11 +36,11 @@ static inline char* dlerror(void) { return "Unknown error"; }
 #    include <dlfcn.h>
 #endif
 
-#include <glib.h>
-
 #include "serd/serd.h"
 #include "sord/sord.h"
 
+#include "zix/tree.h"
+
 #include "lilv-config.h"
 #include "lilv/lilv.h"
 
@@ -76,7 +76,7 @@ struct LilvSpecImpl {
 /**
    Header of an LilvPlugin, LilvPluginClass, or LilvUI.
    Any of these structs may be safely casted to LilvHeader, which is used to
-   implement sequences without code duplication (see lilv_sequence_get_by_uri).
+   implement collections using the same comparator.
 */
 struct LilvHeader {
 	LilvWorld* world;
@@ -244,19 +244,11 @@ const SordNode* lilv_node_as_node(const LilvNode* value);
 
 int lilv_header_compare_by_uri(const void* a, const void* b, void* user_data);
 
-static inline void
-lilv_sequence_insert(GSequence* seq, void* value)
-{
-	g_sequence_insert_sorted(seq, value, lilv_header_compare_by_uri, NULL);
-}
-
-static inline void
-lilv_array_append(GSequence* seq, void* value) {
-	g_sequence_append(seq, value);
-}
+int
+lilv_ptr_cmp(const void* a, const void* b, void* user_data);
 
 struct LilvHeader*
-lilv_sequence_get_by_uri(const GSequence* seq, const LilvNode* uri);
+lilv_collection_get_by_uri(const ZixTree* seq, const LilvNode* uri);
 
 LilvScalePoint* lilv_scale_point_new(LilvNode* value, LilvNode* label);
 void            lilv_scale_point_free(LilvScalePoint* point);
diff --git a/src/plugin.c b/src/plugin.c
index f7adb18..c4233c4 100644
--- a/src/plugin.c
+++ b/src/plugin.c
@@ -18,6 +18,7 @@
 
 #include <assert.h>
 #include <math.h>
+#include <stdarg.h>
 #include <stdio.h>
 #include <stdlib.h>
 #include <string.h>
@@ -244,9 +245,9 @@ lilv_plugin_load_ports_if_necessary(const LilvPlugin* const_p)
 			FOREACH_MATCH(types) {
 				const SordNode* type = lilv_match_object(types);
 				if (sord_node_get_type(type) == SORD_URI) {
-					lilv_array_append(
+					zix_tree_insert(
 						this_port->classes,
-						lilv_node_new_from_node(p->world, type));
+						lilv_node_new_from_node(p->world, type), NULL);
 				} else {
 					LILV_WARNF("Plugin <%s> port type is not a URI\n",
 					           lilv_node_as_uri(p->plugin_uri));
@@ -619,11 +620,11 @@ lilv_plugin_get_supported_features(const LilvPlugin* p)
 	LilvNodes* result   = lilv_nodes_new();
 
 	LILV_FOREACH(nodes, i, optional)
-		lilv_array_append(
-			result, lilv_node_duplicate(lilv_nodes_get(optional, i)));
+		zix_tree_insert(
+			result, lilv_node_duplicate(lilv_nodes_get(optional, i)), NULL);
 	LILV_FOREACH(nodes, i, required)
-		lilv_array_append(
-			result, lilv_node_duplicate(lilv_nodes_get(required, i)));
+		zix_tree_insert(
+			result, lilv_node_duplicate(lilv_nodes_get(required, i)), NULL);
 
 	lilv_nodes_free(optional);
 	lilv_nodes_free(required);
@@ -780,7 +781,7 @@ lilv_plugin_get_uis(const LilvPlugin* p)
 			type,
 			binary);
 
-		lilv_sequence_insert(result, lilv_ui);
+		zix_tree_insert(result, lilv_ui, NULL);
 	}
 	lilv_match_end(uis);
 
diff --git a/src/pluginclass.c b/src/pluginclass.c
index eb6923d..0764576 100644
--- a/src/pluginclass.c
+++ b/src/pluginclass.c
@@ -82,16 +82,16 @@ lilv_plugin_class_get_children(const LilvPluginClass* plugin_class)
 {
 	// Returned list doesn't own categories
 	LilvPluginClasses* all    = plugin_class->world->plugin_classes;
-	LilvPluginClasses* result = g_sequence_new(NULL);
+	LilvPluginClasses* result = zix_tree_new(false, lilv_ptr_cmp, NULL, NULL);
 
-	for (GSequenceIter* i = g_sequence_get_begin_iter(all);
-	     i != g_sequence_get_end_iter(all);
-	     i = g_sequence_iter_next(i)) {
-		const LilvPluginClass* c      = g_sequence_get(i);
-		const LilvNode*       parent = lilv_plugin_class_get_parent_uri(c);
+	for (ZixTreeIter* i = zix_tree_begin(all);
+	     i != zix_tree_end(all);
+	     i = zix_tree_iter_next(i)) {
+		const LilvPluginClass* c      = zix_tree_get(i);
+		const LilvNode*        parent = lilv_plugin_class_get_parent_uri(c);
 		if (parent && lilv_node_equals(lilv_plugin_class_get_uri(plugin_class),
 		                               parent))
-			lilv_sequence_insert(result, (LilvPluginClass*)c);
+			zix_tree_insert(result, (LilvPluginClass*)c, NULL);
 	}
 
 	return result;
diff --git a/src/port.c b/src/port.c
index 8aa4c59..c143b31 100644
--- a/src/port.c
+++ b/src/port.c
@@ -232,7 +232,7 @@ lilv_port_get_scale_points(const LilvPlugin* p,
 			p->world->rdfs_label_node);
 
 		if (value && label) {
-			lilv_array_append(ret, lilv_scale_point_new(value, label));
+			zix_tree_insert(ret, lilv_scale_point_new(value, label), NULL);
 		}
 	}
 	lilv_match_end(points);
diff --git a/src/query.c b/src/query.c
index 5f6cc57..d37527f 100644
--- a/src/query.c
+++ b/src/query.c
@@ -79,13 +79,14 @@ lilv_nodes_from_stream_objects_i18n(LilvWorld* world,
 
 			if (lm == LILV_LANG_MATCH_EXACT) {
 				// Exact language match, add to results
-				lilv_array_append(values, lilv_node_new_from_node(world, value));
+				zix_tree_insert(
+					values, lilv_node_new_from_node(world, value), NULL);
 			} else if (lm == LILV_LANG_MATCH_PARTIAL) {
 				// Partial language match, save in case we find no exact
 				partial = value;
 			}
 		} else {
-			lilv_array_append(values, lilv_node_new_from_node(world, value));
+			zix_tree_insert(values, lilv_node_new_from_node(world, value), NULL);
 		}
 	}
 	lilv_match_end(stream);
@@ -106,7 +107,7 @@ lilv_nodes_from_stream_objects_i18n(LilvWorld* world,
 	}
 
 	if (best) {
-		lilv_array_append(values, lilv_node_new_from_node(world, best));
+		zix_tree_insert(values, lilv_node_new_from_node(world, best), NULL);
 	} else {
 		// No matches whatsoever
 		lilv_nodes_free(values);
@@ -131,7 +132,7 @@ lilv_nodes_from_stream_objects(LilvWorld* world,
 			LilvNode* value = lilv_node_new_from_node(
 				world, lilv_match_object(stream));
 			if (value) {
-				lilv_array_append(values, value);
+				zix_tree_insert(values, value, NULL);
 			}
 		}
 		lilv_match_end(stream);
diff --git a/src/ui.c b/src/ui.c
index 35f06fd..02563c4 100644
--- a/src/ui.c
+++ b/src/ui.c
@@ -45,7 +45,7 @@ lilv_ui_new(LilvWorld* world,
 	free(bundle);
 
 	ui->classes = lilv_nodes_new();
-	lilv_array_append(ui->classes, type_uri);
+	zix_tree_insert(ui->classes, type_uri, NULL);
 
 	return ui;
 }
diff --git a/src/world.c b/src/world.c
index 9cb00ac..6be8a37 100644
--- a/src/world.c
+++ b/src/world.c
@@ -149,10 +149,10 @@ lilv_world_free(LilvWorld* world)
 		const LilvPlugin* p = lilv_plugins_get(world->plugins, i);
 		lilv_plugin_free((LilvPlugin*)p);
 	}
-	g_sequence_free(world->plugins);
+	zix_tree_free(world->plugins);
 	world->plugins = NULL;
 
-	g_sequence_free(world->plugin_classes);
+	zix_tree_free(world->plugin_classes);
 	world->plugin_classes = NULL;
 
 	sord_free(world->model);
@@ -278,34 +278,20 @@ lilv_header_compare_by_uri(const void* a, const void* b, void* user_data)
 	              lilv_node_as_uri(header_b->uri));
 }
 
-/** Get an element of a sequence of any object with an LilvHeader by URI. */
+/** Get an element of a collection of any object with an LilvHeader by URI. */
 struct LilvHeader*
-lilv_sequence_get_by_uri(const GSequence* const_seq,
-                         const LilvNode* uri)
+lilv_collection_get_by_uri(const ZixTree*  const_seq,
+                           const LilvNode* uri)
 {
-	GSequence*        seq = (GSequence*)const_seq;
+	ZixTree*          seq = (ZixTree*)const_seq;
 	struct LilvHeader key = { NULL, (LilvNode*)uri };
-	GSequenceIter*    i   = g_sequence_search(
-		seq, &key, lilv_header_compare_by_uri, NULL);
 
-	// i points to where plugin would be inserted (not necessarily a match)
-
-	if (!g_sequence_iter_is_end(i)) {
-		LilvPlugin* p = g_sequence_get(i);
-		if (lilv_node_equals(lilv_plugin_get_uri(p), uri)) {
-			return (struct LilvHeader*)p;
-		}
-	}
-
-	if (!g_sequence_iter_is_begin(i)) {
-		// Check if i is just past a match
-		i = g_sequence_iter_prev(i);
-		LilvPlugin* p = g_sequence_get(i);
-		if (lilv_node_equals(lilv_plugin_get_uri(p), uri)) {
-			return (struct LilvHeader*)p;
-		}
+	ZixTreeIter* i  = NULL;
+	ZixStatus    st = zix_tree_find(seq, &key, &i);
+	if (!st) {
+		return (struct LilvHeader*)zix_tree_get(i);
 	}
-
+	
 	return NULL;
 }
 
@@ -328,8 +314,9 @@ lilv_world_add_spec(LilvWorld*      world,
 		NULL);
 	FOREACH_MATCH(files) {
 		const SordNode* file_node = lilv_match_object(files);
-		lilv_array_append(spec->data_uris,
-		                  lilv_node_new_from_node(world, file_node));
+		zix_tree_insert(spec->data_uris,
+		                lilv_node_new_from_node(world, file_node),
+		                NULL);
 	}
 	lilv_match_end(files);
 
@@ -362,8 +349,9 @@ lilv_world_add_plugin(LilvWorld*      world,
 	LilvPlugin* plugin     = lilv_plugin_new(world, plugin_uri, bundle_uri);
 
 	// Add manifest as plugin data file (as if it were rdfs:seeAlso)
-	lilv_array_append(plugin->data_uris,
-	                  lilv_new_uri(world, (const char*)manifest_uri->buf));
+	zix_tree_insert(plugin->data_uris,
+	                lilv_new_uri(world, (const char*)manifest_uri->buf),
+	                NULL);
 
 	// Set dynamic manifest library URI, if applicable
 	if (dyn_manifest_lib) {
@@ -379,13 +367,14 @@ lilv_world_add_plugin(LilvWorld*      world,
 		NULL);
 	FOREACH_MATCH(files) {
 		const SordNode* file_node = lilv_match_object(files);
-		lilv_array_append(plugin->data_uris,
-		                  lilv_node_new_from_node(world, file_node));
+		zix_tree_insert(plugin->data_uris,
+		                lilv_node_new_from_node(world, file_node),
+		                NULL);
 	}
 	lilv_match_end(files);
 
 	// Add plugin to world plugin sequence
-	lilv_sequence_insert(world->plugins, plugin);
+	zix_tree_insert(world->plugins, plugin, NULL);
 }
 
 static void
@@ -760,7 +749,7 @@ lilv_world_load_plugin_classes(LilvWorld* world)
 			world, parent_node, class_node, (const char*)label);
 
 		if (pclass) {
-			lilv_sequence_insert(classes, pclass);
+			zix_tree_insert(classes, pclass, NULL);
 		}
 	}
 	lilv_match_end(classes);
diff --git a/src/zix/common.h b/src/zix/common.h
new file mode 100644
index 0000000..8ed0b0b
--- /dev/null
+++ b/src/zix/common.h
@@ -0,0 +1,72 @@
+/*
+  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);
+
+/**
+   Function to destroy an element.
+*/
+typedef void (*ZixDestroyFunc)(const void* ptr);
+   
+/**@}
+*/
+
+#endif  /* ZIX_COMMON_H */
diff --git a/src/zix/tree.c b/src/zix/tree.c
new file mode 100644
index 0000000..1be9227
--- /dev/null
+++ b/src/zix/tree.c
@@ -0,0 +1,518 @@
+/*
+  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;
+	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 = 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)
+{
+	zix_tree_free_rec(t, t->root);
+	free(t);
+}
+
+size_t
+zix_tree_size(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 = 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_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;
+}
diff --git a/src/zix/tree.h b/src/zix/tree.h
new file mode 100644
index 0000000..378db28
--- /dev/null
+++ b/src/zix/tree.h
@@ -0,0 +1,149 @@
+/*
+  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 <stddef.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,
+             ZixDestroyFunc destroy);
+
+/**
+   Free @a t.
+*/
+void
+zix_tree_free(ZixTree* t);
+
+/**
+   Return the number of elements in @a t.
+*/
+size_t
+zix_tree_size(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 to the last (largest) element in @a t.
+*/
+ZixTreeIter*
+zix_tree_rbegin(ZixTree* t);
+
+/**
+   Return an iterator the the element one before the first element in @a t.
+*/
+ZixTreeIter*
+zix_tree_rend(ZixTree* t);
+
+/**
+   Return true iff @a i is an iterator to the reverse end of its tree.
+*/
+bool
+zix_tree_iter_is_rend(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 */
diff --git a/wscript b/wscript
index 4016de7..0407b89 100644
--- a/wscript
+++ b/wscript
@@ -65,10 +65,6 @@ def configure(conf):
     autowaf.display_header('Lilv Configuration')
 
     autowaf.check_pkg(conf, 'lv2core', uselib_store='LV2CORE', mandatory=True)
-    autowaf.check_pkg(conf, 'glib-2.0', uselib_store='GLIB',
-                      atleast_version='2.0.0', mandatory=True)
-    autowaf.check_pkg(conf, 'gthread-2.0', uselib_store='GTHREAD',
-                      atleast_version='2.0.0', mandatory=False)
     autowaf.check_pkg(conf, 'sord-0', uselib_store='SORD',
                       atleast_version='0.4.0', mandatory=True)
 
@@ -158,6 +154,7 @@ def build(bld):
         src/ui.c
         src/util.c
         src/world.c
+        src/zix/tree.c
     '''.split()
 
     linkflags = [ '-ldl' ]
@@ -179,7 +176,7 @@ def build(bld):
                                   '-DLILV_SHARED',
                                   '-DLILV_INTERNAL' ],
               linkflags       = linkflags)
-    autowaf.use_lib(bld, obj, 'SORD SERD LV2CORE GLIB')
+    autowaf.use_lib(bld, obj, 'SORD LV2CORE')
 
     if bld.env['BUILD_TESTS']:
         # Static library (for unit test code coverage)
@@ -191,14 +188,14 @@ def build(bld):
                   install_path = '',
                   cflags       = [ '-fprofile-arcs',  '-ftest-coverage', '-DLILV_INTERNAL' ],
                   linkflags    = linkflags)
-        autowaf.use_lib(bld, obj, 'SORD SERD LV2CORE GLIB')
+        autowaf.use_lib(bld, obj, 'SORD LV2CORE')
 
         # Unit test program
         obj = bld(features     = 'c cprogram',
                   source       = 'test/lilv_test.c',
                   includes     = ['.', './src'],
                   use          = 'liblilv_static',
-                  uselib       = 'SORD SERD LV2CORE',
+                  uselib       = 'SORD LV2CORE',
                   linkflags    = linkflags + ['-lgcov'],
                   target       = 'test/lilv_test',
                   install_path = '',