summaryrefslogtreecommitdiffstats
path: root/src/zix
diff options
context:
space:
mode:
authorDavid Robillard <d@drobilla.net>2011-09-28 21:31:44 +0000
committerDavid Robillard <d@drobilla.net>2011-09-28 21:31:44 +0000
commitdb7df61c02f28a86ebf496436d34a2d327c3ae30 (patch)
tree961b0f00f87155c03e50ff78ccc6518676fabaed /src/zix
parent84ad1bf1317992127aac405feedbfd68c7be6697 (diff)
downloadsord-db7df61c02f28a86ebf496436d34a2d327c3ae30.tar.gz
sord-db7df61c02f28a86ebf496436d34a2d327c3ae30.tar.bz2
sord-db7df61c02f28a86ebf496436d34a2d327c3ae30.zip
Remove glib dependency
git-svn-id: http://svn.drobilla.net/sord/trunk@163 3d64ff67-21c5-427c-a301-fe4f08042e5a
Diffstat (limited to 'src/zix')
-rw-r--r--src/zix/common.h67
-rw-r--r--src/zix/hash.c226
-rw-r--r--src/zix/hash.h75
-rw-r--r--src/zix/tree.c590
-rw-r--r--src/zix/tree.h121
5 files changed, 1079 insertions, 0 deletions
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 */