Hide zix symbols (fix static builds with lilv).

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

6 files changed, 274 insertions, 116 deletions

diff --git a/src/sord.c b/src/sord.c
index f0f3428..bd68d65 100644
--- a/src/sord.c
+++ b/src/sord.c
@@ -22,7 +22,10 @@
 #include <stdlib.h>
 #include <string.h>
 
+#define ZIX_INLINE
+#include "zix/hash.c"
 #include "zix/hash.h"
+#include "zix/tree.c"
 #include "zix/tree.h"
 
 #include "sord_config.h"
@@ -640,10 +643,10 @@ sord_new(SordWorld* world, unsigned indices, bool graphs)
 
 		if (indices & (1 << i)) {
 			sord->indices[i] = zix_tree_new(
-				false, sord_quad_compare, (void*)ordering);
+				false, sord_quad_compare, (void*)ordering, NULL);
 			if (graphs) {
 				sord->indices[i + (NUM_ORDERS / 2)] = zix_tree_new(
-					false, sord_quad_compare, (void*)g_ordering);
+					false, sord_quad_compare, (void*)g_ordering, NULL);
 			} else {
 				sord->indices[i + (NUM_ORDERS / 2)] = NULL;
 			}
@@ -655,11 +658,11 @@ sord_new(SordWorld* world, unsigned indices, bool graphs)
 
 	if (!sord->indices[DEFAULT_ORDER]) {
 		sord->indices[DEFAULT_ORDER] = zix_tree_new(
-			false, sord_quad_compare, (void*)orderings[DEFAULT_ORDER]);
+			false, sord_quad_compare, (void*)orderings[DEFAULT_ORDER], NULL);
 	}
 	if (graphs && !sord->indices[DEFAULT_GRAPH_ORDER]) {
 		sord->indices[DEFAULT_GRAPH_ORDER] = zix_tree_new(
-			false, sord_quad_compare, (void*)orderings[DEFAULT_GRAPH_ORDER]);
+			false, sord_quad_compare, (void*)orderings[DEFAULT_GRAPH_ORDER], NULL);
 	}
 
 	return sord;
diff --git a/src/zix/common.h b/src/zix/common.h
index e7d35e1..f126cd1 100644
--- a/src/zix/common.h
+++ b/src/zix/common.h
@@ -36,8 +36,13 @@
 #    else
 #        define ZIX_API ZIX_LIB_IMPORT
 #    endif
+#    define ZIX_PRIVATE static
+#elif defined(ZIX_INLINE)
+#    define ZIX_API     static inline
+#    define ZIX_PRIVATE static inline
 #else
 #    define ZIX_API
+#    define ZIX_PRIVATE static
 #endif
 /** @endcond */
 
@@ -53,6 +58,8 @@ typedef enum {
 	ZIX_STATUS_NO_MEM,
 	ZIX_STATUS_NOT_FOUND,
 	ZIX_STATUS_EXISTS,
+	ZIX_STATUS_BAD_ARG,
+	ZIX_STATUS_BAD_PERMS,
 } ZixStatus;
 
 /**
@@ -66,6 +73,11 @@ typedef int (*ZixComparator)(const void* a, const void* b, void* user_data);
 typedef bool (*ZixEqualFunc)(const void* a, const void* b);
 
 /**
+   Function to destroy an element.
+*/
+typedef void (*ZixDestroyFunc)(void* ptr);
+
+/**
    @}
 */
 
diff --git a/src/zix/hash.c b/src/zix/hash.c
index f654e91..aacf993 100644
--- a/src/zix/hash.c
+++ b/src/zix/hash.c
@@ -30,44 +30,42 @@ static const unsigned sizes[] = {
 	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;
+typedef struct ZixHashEntry {
+	const void*          key;   ///< Hash key
+	void*                data;  ///< Value
+	struct ZixHashEntry* next;  ///< Next entry in bucket
+	unsigned             hash;  ///< Non-modulo hash value (for cheap rehash)
+} ZixHashEntry;
 
 struct ZixHashImpl {
 	ZixHashFunc     hash_func;
 	ZixEqualFunc    key_equal_func;
-	Entry**         buckets;
+	ZixHashEntry**  buckets;
 	const unsigned* n_buckets;
 	unsigned        count;
 };
 
-ZixHash*
+ZIX_API 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*));
-
+	hash->buckets        = (ZixHashEntry**)calloc(*hash->n_buckets,
+	                                              sizeof(ZixHashEntry*));
 	return hash;
 }
 
-void
+ZIX_API 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;
+		ZixHashEntry* bucket = hash->buckets[b];
+		for (ZixHashEntry* e = bucket; e;) {
+			ZixHashEntry* next = e->next;
 			free(e);
 			e = next;
 		}
@@ -77,7 +75,7 @@ zix_hash_free(ZixHash* hash)
 	free(hash);
 }
 
-unsigned
+ZIX_API unsigned
 zix_string_hash(const void* key)
 {
 	// Trusty old DJB hash
@@ -89,34 +87,32 @@ zix_string_hash(const void* key)
 	return h;
 }
 
-bool
+ZIX_API 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)
+ZIX_PRIVATE void
+insert_entry(ZixHashEntry** bucket, ZixHashEntry*  entry)
 {
 	entry->next = *bucket;
 	*bucket     = entry;
 }
 
-static ZixStatus
+ZIX_PRIVATE ZixStatus
 rehash(ZixHash* hash, unsigned new_n_buckets)
 {
-	Entry** new_buckets = (Entry**)malloc(new_n_buckets * sizeof(Entry*));
+	ZixHashEntry** new_buckets = (ZixHashEntry**)calloc(new_n_buckets,
+	                                                    sizeof(ZixHashEntry*));
 	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;
+		for (ZixHashEntry* e = hash->buckets[b]; e;) {
+			ZixHashEntry* const next = e->next;
+			const unsigned      h    = e->hash % new_n_buckets;
 			insert_entry(&new_buckets[h], e);
 			e = next;
 		}
@@ -128,12 +124,12 @@ rehash(ZixHash* hash, unsigned new_n_buckets)
 	return ZIX_STATUS_SUCCESS;
 }
 
-static Entry*
+ZIX_PRIVATE ZixHashEntry*
 find_entry(const ZixHash* hash,
            const void*    key,
            unsigned   h)
 {
-	for (Entry* e = hash->buckets[h]; e; e = e->next) {
+	for (ZixHashEntry* e = hash->buckets[h]; e; e = e->next) {
 		if (hash->key_equal_func(e->key, key)) {
 			return e;
 		}
@@ -142,27 +138,27 @@ find_entry(const ZixHash* hash,
 	return NULL;
 }
 
-void*
+ZIX_API 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);
+	const unsigned      h     = hash->hash_func(key) % *hash->n_buckets;
+	ZixHashEntry* const entry = find_entry(hash, key, h);
 	return entry ? entry->data : 0;
 }
 
-ZixStatus
+ZIX_API 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);
+	ZixHashEntry* elem = find_entry(hash, key, h);
 	if (elem) {
 		assert(elem->hash == h_nomod);
 		return ZIX_STATUS_EXISTS;
 	}
 
-	elem = (Entry*)malloc(sizeof(Entry));
+	elem = (ZixHashEntry*)malloc(sizeof(ZixHashEntry));
 	if (!elem) {
 		return ZIX_STATUS_NO_MEM;
 	}
@@ -182,13 +178,13 @@ zix_hash_insert(ZixHash* hash, const void* key, void* data)
 	return ZIX_STATUS_SUCCESS;
 }
 
-ZixStatus
+ZIX_API 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) {
+	ZixHashEntry** next_ptr = &hash->buckets[h];
+	for (ZixHashEntry* e = hash->buckets[h]; e; e = e->next) {
 		if (hash->key_equal_func(e->key, key)) {
 			*next_ptr = e->next;
 			free(e);
@@ -210,15 +206,14 @@ zix_hash_remove(ZixHash* hash, const void* key)
 	return ZIX_STATUS_NOT_FOUND;
 }
 
-ZIX_API
-void
+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) {
+		ZixHashEntry* bucket = hash->buckets[b];
+		for (ZixHashEntry* 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
index 44521f1..4d93eaa 100644
--- a/src/zix/hash.h
+++ b/src/zix/hash.h
@@ -30,40 +30,32 @@ typedef struct ZixHashImpl ZixHash;
 */
 typedef unsigned (*ZixHashFunc)(const void* key);
 
-ZIX_API
-ZixHash*
+ZIX_API ZixHash*
 zix_hash_new(ZixHashFunc  hash_func,
              ZixEqualFunc key_equal_func);
 
-ZIX_API
-void
+ZIX_API void
 zix_hash_free(ZixHash* hash);
 
-ZIX_API
-unsigned
+ZIX_API unsigned
 zix_string_hash(const void* key);
 
-ZIX_API
-bool
+ZIX_API bool
 zix_string_equal(const void* a, const void* b);
 
-ZIX_API
-ZixStatus
+ZIX_API ZixStatus
 zix_hash_insert(ZixHash*    hash,
                 const void* key,
                 void*       data);
 
-ZIX_API
-ZixStatus
+ZIX_API ZixStatus
 zix_hash_remove(ZixHash* hash, const void* key);
 
-ZIX_API
-void*
+ZIX_API void*
 zix_hash_find(const ZixHash* hash,
               const void*    key);
 
-ZIX_API
-void
+ZIX_API void
 zix_hash_foreach(const ZixHash* hash,
                  void (*f)(const void* key, void* value, void* user_data),
                  void* user_data);
diff --git a/src/zix/tree.c b/src/zix/tree.c
index 64e6e7c..844adb9 100644
--- a/src/zix/tree.c
+++ b/src/zix/tree.c
@@ -26,10 +26,12 @@
 typedef struct ZixTreeNodeImpl ZixTreeNode;
 
 struct ZixTreeImpl {
-	ZixTreeNode*  root;
-	ZixComparator cmp;
-	void*         cmp_data;
-	bool          allow_duplicates;
+	ZixTreeNode*   root;
+	ZixDestroyFunc destroy;
+	ZixComparator  cmp;
+	void*          cmp_data;
+	size_t         size;
+	bool           allow_duplicates;
 };
 
 struct ZixTreeNodeImpl {
@@ -43,38 +45,72 @@ struct ZixTreeNodeImpl {
 #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)
+// 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(ZixTreeNode* n)
+ZIX_PRIVATE void
+zix_tree_free_rec(ZixTree* t, ZixTreeNode* n)
 {
 	if (n) {
-		zix_tree_free_rec(n->left);
-		zix_tree_free_rec(n->right);
+		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_API void
 zix_tree_free(ZixTree* t)
 {
-	zix_tree_free_rec(t->root);
+	if (t) {
+		zix_tree_free_rec(t, t->root);
+		free(t);
+	}
+}
 
-	free(t);
+ZIX_API size_t
+zix_tree_size(const ZixTree* t)
+{
+	return t->size;
 }
 
-static void
+ZIX_PRIVATE void
 rotate(ZixTreeNode* p, ZixTreeNode* q)
 {
 	assert(q->parent == p);
@@ -118,20 +154,26 @@ rotate(ZixTreeNode* p, ZixTreeNode* q)
  *     / \        / \
  *    B   C      A   B
  */
-static ZixTreeNode*
+ZIX_PRIVATE 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;
 }
 
@@ -145,20 +187,26 @@ rotate_left(ZixTreeNode* p, int* height_change)
  *  A   B          B   C
  *
  */
-static ZixTreeNode*
+ZIX_PRIVATE 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;
 }
 
@@ -174,7 +222,7 @@ rotate_right(ZixTreeNode* p, int* height_change)
  *    B   C
  *
  */
-static ZixTreeNode*
+ZIX_PRIVATE ZixTreeNode*
 rotate_left_right(ZixTreeNode* p, int* height_change)
 {
 	ZixTreeNode* const q = p->left;
@@ -184,15 +232,25 @@ rotate_left_right(ZixTreeNode* p, int* height_change)
 	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;
 }
 
@@ -208,7 +266,7 @@ rotate_left_right(ZixTreeNode* p, int* height_change)
  *  B   C
  *
  */
-static ZixTreeNode*
+ZIX_PRIVATE ZixTreeNode*
 rotate_right_left(ZixTreeNode* p, int* height_change)
 {
 	ZixTreeNode* const q = p->right;
@@ -218,21 +276,36 @@ rotate_right_left(ZixTreeNode* p, int* height_change)
 	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_PRIVATE 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));
@@ -256,14 +329,17 @@ zix_tree_rebalance(ZixTree* t, ZixTreeNode* node, int* height_change)
 		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_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;
@@ -282,6 +358,7 @@ zix_tree_insert(ZixTree* t, void* e, ZixTreeIter** ti)
 			if (ti) {
 				*ti = n;
 			}
+			DEBUG_PRINTF("%ld EXISTS!\n", (intptr_t)e);
 			return ZIX_STATUS_EXISTS;
 		}
 	}
@@ -319,6 +396,8 @@ zix_tree_insert(ZixTree* t, void* e, ZixTreeIter** ti)
 		}
 	}
 
+	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) {
@@ -343,11 +422,20 @@ zix_tree_insert(ZixTree* t, void* e, ZixTreeIter** ti)
 		}
 	}
 
+	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_API ZixStatus
 zix_tree_remove(ZixTree* t, ZixTreeIter* ti)
 {
 	ZixTreeNode* const n          = ti;
@@ -355,9 +443,16 @@ zix_tree_remove(ZixTree* t, ZixTreeIter* ti)
 	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;
 	}
 
@@ -479,13 +574,25 @@ zix_tree_remove(ZixTree* t, ZixTreeIter* ti)
 		}
 	}
 
+	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_API ZixStatus
 zix_tree_find(const ZixTree* t, const void* e, ZixTreeIter** ti)
 {
 	ZixTreeNode* n = t->root;
@@ -504,15 +611,13 @@ zix_tree_find(const ZixTree* t, const void* e, ZixTreeIter** ti)
 	return (n) ? ZIX_STATUS_SUCCESS : ZIX_STATUS_NOT_FOUND;
 }
 
-ZIX_API
-void*
+ZIX_API void*
 zix_tree_get(ZixTreeIter* ti)
 {
-	return ti->data;
+	return ti ? ti->data : NULL;
 }
 
-ZIX_API
-ZixTreeIter*
+ZIX_API ZixTreeIter*
 zix_tree_begin(ZixTree* t)
 {
 	if (!t->root) {
@@ -526,22 +631,45 @@ zix_tree_begin(ZixTree* t)
 	return n;
 }
 
-ZIX_API
-ZixTreeIter*
+ZIX_API ZixTreeIter*
 zix_tree_end(ZixTree* t)
 {
 	return NULL;
 }
 
-ZIX_API
-bool
+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
-ZixTreeIter*
+ZIX_API bool
+zix_tree_iter_is_rend(ZixTreeIter* i)
+{
+	return !i;
+}
+
+ZIX_API ZixTreeIter*
 zix_tree_iter_next(ZixTreeIter* i)
 {
 	if (!i) {
@@ -564,8 +692,7 @@ zix_tree_iter_next(ZixTreeIter* i)
 	return i;
 }
 
-ZIX_API
-ZixTreeIter*
+ZIX_API ZixTreeIter*
 zix_tree_iter_prev(ZixTreeIter* i)
 {
 	if (!i) {
diff --git a/src/zix/tree.h b/src/zix/tree.h
index bcbde26..f89d9e5 100644
--- a/src/zix/tree.h
+++ b/src/zix/tree.h
@@ -17,6 +17,8 @@
 #ifndef ZIX_TREE_H
 #define ZIX_TREE_H
 
+#include <stddef.h>
+
 #include "zix/common.h"
 
 #ifdef __cplusplus
@@ -43,68 +45,95 @@ typedef struct ZixTreeNodeImpl ZixTreeIter;
 /**
    Create a new (empty) tree.
 */
-ZixTree*
-zix_tree_new(bool allow_duplicates, ZixComparator cmp, void* cmp_data);
+ZIX_API ZixTree*
+zix_tree_new(bool           allow_duplicates,
+             ZixComparator  cmp,
+             void*          cmp_data,
+             ZixDestroyFunc destroy);
 
 /**
    Free @a t.
 */
-void
+ZIX_API void
 zix_tree_free(ZixTree* t);
 
 /**
+   Return the number of elements in @a t.
+*/
+ZIX_API size_t
+zix_tree_size(const ZixTree* t);
+
+/**
    Insert the element @a e into @a t and point @a ti at the new element.
 */
-ZixStatus
+ZIX_API ZixStatus
 zix_tree_insert(ZixTree* t, void* e, ZixTreeIter** ti);
 
 /**
    Remove the item pointed at by @a ti from @a t.
 */
-ZixStatus
+ZIX_API 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_API ZixStatus
 zix_tree_find(const ZixTree* t, const void* e, ZixTreeIter** ti);
 
 /**
    Return the data associated with the given tree item.
 */
-void*
+ZIX_API void*
 zix_tree_get(ZixTreeIter* ti);
 
 /**
    Return an iterator to the first (smallest) element in @a t.
 */
-ZixTreeIter*
+ZIX_API ZixTreeIter*
 zix_tree_begin(ZixTree* t);
 
 /**
    Return an iterator the the element one past the last element in @a t.
 */
-ZixTreeIter*
+ZIX_API ZixTreeIter*
 zix_tree_end(ZixTree* t);
 
 /**
    Return true iff @a i is an iterator to the end of its tree.
 */
-bool
+ZIX_API bool
 zix_tree_iter_is_end(ZixTreeIter* i);
 
 /**
+   Return an iterator to the last (largest) element in @a t.
+*/
+ZIX_API ZixTreeIter*
+zix_tree_rbegin(ZixTree* t);
+
+/**
+   Return an iterator the the element one before the first element in @a t.
+*/
+ZIX_API ZixTreeIter*
+zix_tree_rend(ZixTree* t);
+
+/**
+   Return true iff @a i is an iterator to the reverse end of its tree.
+*/
+ZIX_API bool
+zix_tree_iter_is_rend(ZixTreeIter* i);
+
+/**
    Return an iterator that points to the element one past @a i.
 */
-ZixTreeIter*
+ZIX_API ZixTreeIter*
 zix_tree_iter_next(ZixTreeIter* i);
 
 /**
    Return an iterator that points to the element one before @a i.
 */
-ZixTreeIter*
+ZIX_API ZixTreeIter*
 zix_tree_iter_prev(ZixTreeIter* i);
 
 /**