summaryrefslogtreecommitdiffstats
path: root/src/zix
diff options
context:
space:
mode:
Diffstat (limited to 'src/zix')
-rw-r--r--src/zix/btree.c702
-rw-r--r--src/zix/btree.h144
-rw-r--r--src/zix/hash.c22
-rw-r--r--src/zix/tree.c716
-rw-r--r--src/zix/tree.h148
5 files changed, 859 insertions, 873 deletions
diff --git a/src/zix/btree.c b/src/zix/btree.c
new file mode 100644
index 0000000..26885e2
--- /dev/null
+++ b/src/zix/btree.c
@@ -0,0 +1,702 @@
+/*
+ Copyright 2011-2014 David Robillard <http://drobilla.net>
+
+ Permission to use, copy, modify, and/or distribute this software for any
+ purpose with or without fee is hereby granted, provided that the above
+ copyright notice and this permission notice appear in all copies.
+
+ THIS SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL WARRANTIES
+ WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF
+ MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR
+ ANY SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES
+ WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN
+ ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF
+ OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE.
+*/
+
+#include <assert.h>
+#include <stdint.h>
+#include <stdio.h>
+#include <stdlib.h>
+#include <string.h>
+
+#include "zix/btree.h"
+
+// #define ZIX_BTREE_DEBUG 1
+
+#define ZIX_BTREE_PAGE_SIZE 4096
+#define ZIX_BTREE_NODE_SPACE (ZIX_BTREE_PAGE_SIZE - 2 * sizeof(uint32_t))
+#define ZIX_BTREE_LEAF_VALS (ZIX_BTREE_NODE_SPACE / sizeof(void*))
+#define ZIX_BTREE_INODE_VALS (ZIX_BTREE_LEAF_VALS / 2)
+
+struct ZixBTreeImpl {
+ ZixBTreeNode* root;
+ ZixDestroyFunc destroy;
+ ZixComparator cmp;
+ void* cmp_data;
+ size_t size;
+ unsigned height; ///< Number of levels, i.e. root only has height 1
+};
+
+struct ZixBTreeNodeImpl {
+ uint32_t is_leaf;
+ uint32_t n_vals;
+ void* vals[ZIX_BTREE_INODE_VALS]; // ZIX_BTREE_LEAF_VALS for leaves
+ ZixBTreeNode* children[ZIX_BTREE_INODE_VALS + 1]; // Nonexistent for leaves
+};
+
+typedef struct {
+ ZixBTreeNode* node;
+ unsigned index;
+} ZixBTreeIterFrame;
+
+struct ZixBTreeIterImpl {
+ unsigned level; ///< Current level in pos
+ ZixBTreeIterFrame stack[]; ///< Position stack
+};
+
+#ifdef ZIX_BTREE_DEBUG
+
+ZIX_PRIVATE void
+print_node(const ZixBTreeNode* n, const char* prefix)
+{
+ printf("%s[", prefix);
+ for (unsigned v = 0; v < n->n_vals; ++v) {
+ printf(" %lu", (uintptr_t)n->vals[v]);
+ }
+ printf(" ]\n");
+}
+
+ZIX_PRIVATE void
+print_tree(const ZixBTreeNode* parent, const ZixBTreeNode* node, int level)
+{
+ if (node) {
+ if (!parent) {
+ printf("TREE {\n");
+ }
+ for (int i = 0; i < level + 1; ++i) {
+ printf(" ");
+ }
+ print_node(node, "");
+ if (!node->is_leaf) {
+ for (unsigned i = 0; i < node->n_vals + 1; ++i) {
+ print_tree(node, node->children[i], level + 1);
+ }
+ }
+ if (!parent) {
+ printf("}\n");
+ }
+ }
+}
+
+#endif // ZIX_BTREE_DEBUG
+
+ZIX_PRIVATE ZixBTreeNode*
+zix_btree_node_new(const bool leaf)
+{
+ assert(sizeof(ZixBTreeNode) == ZIX_BTREE_PAGE_SIZE);
+ ZixBTreeNode* node = (ZixBTreeNode*)malloc(sizeof(ZixBTreeNode));
+ if (node) {
+ node->is_leaf = leaf;
+ node->n_vals = 0;
+ }
+ return node;
+}
+
+ZIX_API ZixBTree*
+zix_btree_new(const ZixComparator cmp,
+ void* const cmp_data,
+ const ZixDestroyFunc destroy)
+{
+ ZixBTree* t = (ZixBTree*)malloc(sizeof(ZixBTree));
+ if (t) {
+ t->root = zix_btree_node_new(true);
+ t->destroy = destroy;
+ t->cmp = cmp;
+ t->cmp_data = cmp_data;
+ t->size = 0;
+ t->height = 1;
+ if (!t->root) {
+ free(t);
+ return NULL;
+ }
+ }
+ return t;
+}
+
+ZIX_PRIVATE void
+zix_btree_free_rec(ZixBTree* const t, ZixBTreeNode* const n)
+{
+ if (n) {
+ if (t->destroy) {
+ for (unsigned i = 0; i < n->n_vals; ++i) {
+ t->destroy(n->vals[i]);
+ }
+ }
+ if (!n->is_leaf) {
+ for (unsigned i = 0; i < n->n_vals + 1; ++i) {
+ zix_btree_free_rec(t, n->children[i]);
+ }
+ }
+ free(n);
+ }
+}
+
+ZIX_API void
+zix_btree_free(ZixBTree* const t)
+{
+ if (t) {
+ zix_btree_free_rec(t, t->root);
+ free(t);
+ }
+}
+
+ZIX_API size_t
+zix_btree_size(const ZixBTree* const t)
+{
+ return t->size;
+}
+
+ZIX_PRIVATE unsigned
+zix_btree_max_vals(const ZixBTreeNode* const node)
+{
+ return node->is_leaf ? ZIX_BTREE_LEAF_VALS : ZIX_BTREE_INODE_VALS;
+}
+
+ZIX_PRIVATE unsigned
+zix_btree_min_vals(const ZixBTreeNode* const node)
+{
+ return ((zix_btree_max_vals(node) + 1) / 2) - 1;
+}
+
+/** Shift pointers in `array` of length `n` right starting at `i`. */
+ZIX_PRIVATE void
+zix_btree_ainsert(void** const array,
+ const unsigned n,
+ const unsigned i,
+ void* const e)
+{
+ memmove(array + i + 1, array + i, (n - i) * sizeof(e));
+ array[i] = e;
+}
+
+/** Erase element `i` in `array` of length `n` and return erased element. */
+ZIX_PRIVATE void*
+zix_btree_aerase(void** const array, const unsigned n, const unsigned i)
+{
+ void* const ret = array[i];
+ memmove(array + i, array + i + 1, (n - i) * sizeof(ret));
+ return ret;
+}
+
+/** Split lhs, the i'th child of `n`, into two nodes. */
+ZIX_PRIVATE ZixBTreeNode*
+zix_btree_split_child(ZixBTreeNode* const n,
+ const uint32_t i,
+ ZixBTreeNode* const lhs)
+{
+ assert(lhs->n_vals == zix_btree_max_vals(lhs));
+ assert(n->n_vals < ZIX_BTREE_INODE_VALS);
+ assert(i < n->n_vals + 1);
+ assert(n->children[i] == lhs);
+
+ const unsigned max_n_vals = zix_btree_max_vals(lhs);
+ ZixBTreeNode* rhs = zix_btree_node_new(lhs->is_leaf);
+ if (!rhs) {
+ return NULL;
+ }
+
+ // LHS and RHS get roughly half, less the middle value which moves up
+ lhs->n_vals = max_n_vals / 2;
+ rhs->n_vals = max_n_vals - lhs->n_vals - 1;
+
+ // Copy large half of values from LHS to new RHS node
+ memcpy(rhs->vals,
+ lhs->vals + lhs->n_vals + 1,
+ rhs->n_vals * sizeof(void*));
+
+ // Copy large half of children from LHS to new RHS node
+ if (!lhs->is_leaf) {
+ memcpy(rhs->children,
+ lhs->children + lhs->n_vals + 1,
+ (rhs->n_vals + 1) * sizeof(ZixBTreeNode*));
+ }
+
+ // Move middle value up to parent
+ zix_btree_ainsert(n->vals, n->n_vals, i, lhs->vals[lhs->n_vals]);
+
+ // Insert new RHS node in parent at position i
+ zix_btree_ainsert((void**)n->children, ++n->n_vals, i + 1, rhs);
+
+ return rhs;
+}
+
+/** Find the first value in `n` that is not less than `e` (lower bound). */
+ZIX_PRIVATE unsigned
+zix_btree_node_find(const ZixBTree* const t,
+ const ZixBTreeNode* const n,
+ const void* const e,
+ bool* const equal)
+{
+ unsigned first = 0;
+ unsigned len = n->n_vals;
+ while (len > 0) {
+ const unsigned half = len >> 1;
+ const unsigned i = first + half;
+ const int cmp = t->cmp(n->vals[i], e, t->cmp_data);
+ if (cmp == 0) {
+ *equal = true;
+ len = half; // Keep searching for wildcard matches
+ } else if (cmp < 0) {
+ const unsigned chop = half + 1;
+ first += chop;
+ len -= chop;
+ } else {
+ len = half;
+ }
+ }
+ assert(!*equal || t->cmp(n->vals[first], e, t->cmp_data) == 0);
+ return first;
+}
+
+ZIX_API ZixStatus
+zix_btree_insert(ZixBTree* const t, void* const e)
+{
+ ZixBTreeNode* parent = NULL; // Parent of n
+ ZixBTreeNode* n = t->root; // Current node
+ unsigned i = 0; // Index of n in parent
+ while (n) {
+ if (n->n_vals == zix_btree_max_vals(n)) {
+ // Node is full, split to ensure there is space for a leaf split
+ if (!parent) {
+ // Root is full, grow tree upwards
+ if (!(parent = zix_btree_node_new(false))) {
+ return ZIX_STATUS_NO_MEM;
+ }
+ t->root = parent;
+ parent->children[0] = n;
+ ++t->height;
+ }
+
+ ZixBTreeNode* const rhs = zix_btree_split_child(parent, i, n);
+ if (!rhs) {
+ return ZIX_STATUS_NO_MEM;
+ }
+
+ const int cmp = t->cmp(parent->vals[i], e, t->cmp_data);
+ if (cmp == 0) {
+ return ZIX_STATUS_EXISTS;
+ } else if (cmp < 0) {
+ // Move to new RHS
+ n = rhs;
+ ++i;
+ }
+ }
+
+ assert(!parent || parent->children[i] == n);
+
+ bool equal = false;
+ i = zix_btree_node_find(t, n, e, &equal);
+ if (equal) {
+ return ZIX_STATUS_EXISTS;
+ } else if (!n->is_leaf) {
+ // Descend to child node left of value
+ parent = n;
+ n = n->children[i];
+ } else {
+ // Insert into internal node
+ zix_btree_ainsert(n->vals, n->n_vals, i, e);
+ break;
+ }
+ }
+
+ ++n->n_vals;
+ ++t->size;
+
+ return ZIX_STATUS_SUCCESS;
+}
+
+ZIX_PRIVATE bool
+zix_btree_node_is_minimal(ZixBTreeNode* const n)
+{
+ assert(n->n_vals >= zix_btree_min_vals(n));
+ return n->n_vals == zix_btree_min_vals(n);
+}
+
+/** Enlarge left child by stealing a value from its right sibling. */
+ZIX_PRIVATE ZixBTreeNode*
+zix_btree_rotate_left(ZixBTreeNode* const parent, const unsigned i)
+{
+ ZixBTreeNode* const lhs = parent->children[i];
+ ZixBTreeNode* const rhs = parent->children[i + 1];
+
+ // Move parent value to end of LHS
+ lhs->vals[lhs->n_vals++] = parent->vals[i];
+
+ // Move first child pointer from RHS to end of LHS
+ if (!lhs->is_leaf) {
+ lhs->children[lhs->n_vals] = zix_btree_aerase(
+ (void**)rhs->children, rhs->n_vals, 0);
+ }
+
+ // Move first value in RHS to parent
+ parent->vals[i] = zix_btree_aerase(rhs->vals, --rhs->n_vals, 0);
+
+ return lhs;
+}
+
+/** Enlarge right child by stealing a value from its left sibling. */
+ZIX_PRIVATE ZixBTreeNode*
+zix_btree_rotate_right(ZixBTreeNode* const parent, const unsigned i)
+{
+ ZixBTreeNode* const lhs = parent->children[i - 1];
+ ZixBTreeNode* const rhs = parent->children[i];
+
+ // Prepend parent value to RHS
+ zix_btree_ainsert(rhs->vals, rhs->n_vals++, 0, parent->vals[i - 1]);
+
+ // Move last child pointer from LHS and prepend to RHS
+ if (!lhs->is_leaf) {
+ zix_btree_ainsert((void**)rhs->children,
+ rhs->n_vals,
+ 0,
+ lhs->children[lhs->n_vals]);
+ }
+
+ // Move last value from LHS to parent
+ parent->vals[i - 1] = lhs->vals[--lhs->n_vals];
+
+ return rhs;
+}
+
+/** Move n[i] down, merge the left and right child, return the merged node. */
+ZIX_PRIVATE ZixBTreeNode*
+zix_btree_merge(ZixBTree* const t, ZixBTreeNode* const n, const unsigned i)
+{
+ ZixBTreeNode* const lhs = n->children[i];
+ ZixBTreeNode* const rhs = n->children[i + 1];
+
+ assert(zix_btree_node_is_minimal(n->children[i]));
+ assert(lhs->n_vals + rhs->n_vals < zix_btree_max_vals(lhs));
+
+ // Move parent value to end of LHS
+ lhs->vals[lhs->n_vals++] = zix_btree_aerase(n->vals, n->n_vals, i);
+
+ // Erase corresponding child pointer (to RHS) in parent
+ zix_btree_aerase((void**)n->children, n->n_vals, i + 1);
+
+ // Add everything from RHS to end of LHS
+ memcpy(lhs->vals + lhs->n_vals, rhs->vals, rhs->n_vals * sizeof(void*));
+ if (!lhs->is_leaf) {
+ memcpy(lhs->children + lhs->n_vals,
+ rhs->children,
+ (rhs->n_vals + 1) * sizeof(void*));
+ }
+ lhs->n_vals += rhs->n_vals;
+
+ if (--n->n_vals == 0) {
+ // Root is now empty, replace it with its only child
+ assert(n == t->root);
+ t->root = lhs;
+ free(n);
+ }
+
+ free(rhs);
+ return lhs;
+}
+
+/** Remove and return the min value from the subtree rooted at `n`. */
+ZIX_PRIVATE void*
+zix_btree_remove_min(ZixBTree* const t, ZixBTreeNode* n)
+{
+ while (!n->is_leaf) {
+ if (zix_btree_node_is_minimal(n->children[0])) {
+ // Leftmost child is minimal, must expand
+ if (!zix_btree_node_is_minimal(n->children[1])) {
+ // Child's right sibling has at least one key to steal
+ n = zix_btree_rotate_left(n, 0);
+ } else {
+ // Both child and right sibling are minimal, merge
+ n = zix_btree_merge(t, n, 0);
+ }
+ } else {
+ n = n->children[0];
+ }
+ }
+
+ return zix_btree_aerase(n->vals, --n->n_vals, 0);
+}
+
+/** Remove and return the max value from the subtree rooted at `n`. */
+ZIX_PRIVATE void*
+zix_btree_remove_max(ZixBTree* const t, ZixBTreeNode* n)
+{
+ while (!n->is_leaf) {
+ if (zix_btree_node_is_minimal(n->children[n->n_vals])) {
+ // Leftmost child is minimal, must expand
+ if (!zix_btree_node_is_minimal(n->children[n->n_vals - 1])) {
+ // Child's left sibling has at least one key to steal
+ n = zix_btree_rotate_right(n, n->n_vals);
+ } else {
+ // Both child and left sibling are minimal, merge
+ n = zix_btree_merge(t, n, n->n_vals - 1);
+ }
+ } else {
+ n = n->children[n->n_vals];
+ }
+ }
+
+ return n->vals[--n->n_vals];
+}
+
+ZIX_PRIVATE ZixStatus
+zix_btree_remove_rec(ZixBTree* const t,
+ ZixBTreeNode* const n,
+ const void* const e,
+ void** const removed)
+{
+ /* To remove in a single walk down, the tree is adjusted along the way so
+ that the current node always has at least one more value than the
+ minimum required in general. Thus, there is always room to remove
+ without adjusting on the way back up. */
+ assert(n == t->root || !zix_btree_node_is_minimal(n));
+
+ bool equal = false;
+ const unsigned i = zix_btree_node_find(t, n, e, &equal);
+
+ if (n->is_leaf) {
+ if (equal) {
+ // Found in leaf node
+ *removed = zix_btree_aerase(n->vals, --n->n_vals, i);
+ return ZIX_STATUS_SUCCESS;
+ } else {
+ // Not found in leaf node, or tree
+ return ZIX_STATUS_NOT_FOUND;
+ }
+ } else if (equal) {
+ // Found in internal node
+ if (!zix_btree_node_is_minimal(n->children[i])) {
+ // Left child can remove without merge
+ *removed = n->vals[i];
+ n->vals[i] = zix_btree_remove_max(t, n->children[i]);
+ return ZIX_STATUS_SUCCESS;
+ } else if (!zix_btree_node_is_minimal(n->children[i + 1])) {
+ // Right child can remove without merge
+ *removed = n->vals[i];
+ n->vals[i] = zix_btree_remove_min(t, n->children[i + 1]);
+ return ZIX_STATUS_SUCCESS;
+ } else {
+ // Both preceding and succeeding child are minimal
+ ZixBTreeNode* const merged = zix_btree_merge(t, n, i);
+ return zix_btree_remove_rec(t, merged, e, removed);
+ }
+ } else {
+ // Not found in internal node, key is in/under children[i]
+ if (zix_btree_node_is_minimal(n->children[i])) {
+ if (i > 0 && !zix_btree_node_is_minimal(n->children[i - 1])) {
+ // Child's left sibling has at least one key to steal
+ ZixBTreeNode* const rhs = zix_btree_rotate_right(n, i);
+ return zix_btree_remove_rec(t, rhs, e, removed);
+ } else if (i < n->n_vals &&
+ !zix_btree_node_is_minimal(n->children[i + 1])) {
+ // Child's right sibling has at least one key to steal
+ ZixBTreeNode* const lhs = zix_btree_rotate_left(n, i);
+ return zix_btree_remove_rec(t, lhs, e, removed);
+ } else {
+ // Both child's siblings are minimal, merge them
+ const unsigned m = (i < n->n_vals) ? i : i - 1;
+ ZixBTreeNode* const merged = zix_btree_merge(t, n, m);
+ return zix_btree_remove_rec(t, merged, e, removed);
+ }
+ } else {
+ return zix_btree_remove_rec(t, n->children[i], e, removed);
+ }
+ }
+
+ assert(false); // Not reached
+ return ZIX_STATUS_ERROR;
+}
+
+ZIX_API ZixStatus
+zix_btree_remove(ZixBTree* const t, const void* const e, void** const removed)
+{
+ const ZixStatus st = zix_btree_remove_rec(t, t->root, e, removed);
+ if (!st) {
+ --t->size;
+ }
+ return st;
+}
+
+ZIX_PRIVATE ZixBTreeIter*
+zix_btree_iter_new(const ZixBTree* const t)
+{
+ const size_t s = t->height * sizeof(ZixBTreeIterFrame);
+ ZixBTreeIter* const i = (ZixBTreeIter*)malloc(sizeof(ZixBTreeIter) + s);
+ if (i) {
+ i->level = 0;
+ }
+ return i;
+}
+
+ZIX_API ZixStatus
+zix_btree_find(const ZixBTree* const t,
+ const void* const e,
+ ZixBTreeIter** const ti)
+{
+ ZixBTreeNode* n = t->root;
+ if (!(*ti = zix_btree_iter_new(t))) {
+ return ZIX_STATUS_NO_MEM;
+ }
+
+ while (n) {
+ bool equal = false;
+ const unsigned i = zix_btree_node_find(t, n, e, &equal);
+
+ // Update iterator stack
+ (*ti)->stack[(*ti)->level].node = n;
+ (*ti)->stack[(*ti)->level].index = i;
+
+ if (equal) {
+ return ZIX_STATUS_SUCCESS;
+ } else if (n->is_leaf) {
+ break;
+ } else {
+ ++(*ti)->level;
+ n = n->children[i];
+ }
+ }
+
+ zix_btree_iter_free(*ti);
+ *ti = NULL;
+ return ZIX_STATUS_NOT_FOUND;
+}
+
+ZIX_API ZixStatus
+zix_btree_lower_bound(const ZixBTree* const t,
+ const void* const e,
+ ZixBTreeIter** const ti)
+{
+ ZixBTreeNode* n = t->root;
+ bool found = false;
+ unsigned found_level = 0;
+ if (!(*ti = zix_btree_iter_new(t))) {
+ return ZIX_STATUS_NO_MEM;
+ }
+
+ while (n) {
+ bool equal = false;
+ const unsigned i = zix_btree_node_find(t, n, e, &equal);
+
+ // Update iterator stack
+ (*ti)->stack[(*ti)->level].node = n;
+ (*ti)->stack[(*ti)->level].index = i;
+
+ if (equal) {
+ found_level = (*ti)->level;
+ found = true;
+ }
+
+ if (n->is_leaf) {
+ break;
+ } else {
+ ++(*ti)->level;
+ n = n->children[i];
+ }
+ }
+
+ const ZixBTreeIterFrame* const frame = &(*ti)->stack[(*ti)->level];
+ if (frame->index == frame->node->n_vals) {
+ if (found) {
+ // Found on a previous level but went too far
+ (*ti)->level = found_level;
+ } else {
+ // Reached end (key is greater than everything in tree)
+ (*ti)->stack[0].node = NULL;
+ }
+ }
+
+ return ZIX_STATUS_SUCCESS;
+}
+
+ZIX_API void*
+zix_btree_get(const ZixBTreeIter* const ti)
+{
+ const ZixBTreeIterFrame* const frame = &ti->stack[ti->level];
+ assert(frame->index < frame->node->n_vals);
+ return frame->node->vals[frame->index];
+}
+
+ZIX_API ZixBTreeIter*
+zix_btree_begin(const ZixBTree* const t)
+{
+ ZixBTreeIter* const i = zix_btree_iter_new(t);
+ if (!i) {
+ return NULL;
+ } else if (t->size == 0) {
+ i->stack[0].node = NULL;
+ } else {
+ ZixBTreeNode* n = t->root;
+ i->stack[0].node = n;
+ i->stack[0].index = 0;
+ while (!n->is_leaf) {
+ n = n->children[0];
+ ++i->level;
+ i->stack[i->level].node = n;
+ i->stack[i->level].index = 0;
+ }
+ }
+ return i;
+}
+
+ZIX_API bool
+zix_btree_iter_is_end(const ZixBTreeIter* const i)
+{
+ return !i || i->stack[0].node == NULL;
+}
+
+ZIX_API void
+zix_btree_iter_increment(ZixBTreeIter* const i)
+{
+ ZixBTreeIterFrame* f = &i->stack[i->level];
+ if (f->node->is_leaf) {
+ // Leaf, move right
+ assert(f->index < f->node->n_vals);
+ if (++f->index == f->node->n_vals) {
+ // Reached end of leaf, move up
+ f = &i->stack[i->level];
+ while (i->level > 0 && f->index == f->node->n_vals) {
+ f = &i->stack[--i->level];
+ assert(f->index <= f->node->n_vals);
+ }
+
+ if (f->index == f->node->n_vals) {
+ // Reached end of tree
+ assert(i->level == 0);
+ f->node = NULL;
+ f->index = 0;
+ }
+ }
+ } else {
+ // Internal node, move down to next child
+ assert(f->index < f->node->n_vals);
+ ZixBTreeNode* child = f->node->children[++f->index];
+
+ f = &i->stack[++i->level];
+ f->node = child;
+ f->index = 0;
+
+ // Move down and left until we hit a leaf
+ while (!f->node->is_leaf) {
+ child = f->node->children[0];
+ f = &i->stack[++i->level];
+ f->node = child;
+ f->index = 0;
+ }
+ }
+}
+
+ZIX_API void
+zix_btree_iter_free(ZixBTreeIter* const i)
+{
+ free(i);
+}
diff --git a/src/zix/btree.h b/src/zix/btree.h
new file mode 100644
index 0000000..0cd549a
--- /dev/null
+++ b/src/zix/btree.h
@@ -0,0 +1,144 @@
+/*
+ Copyright 2011-2014 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_BTREE_H
+#define ZIX_BTREE_H
+
+#include <stdbool.h>
+#include <stddef.h>
+
+#include "zix/common.h"
+
+#ifdef __cplusplus
+extern "C" {
+#endif
+
+/**
+ @addtogroup zix
+ @{
+ @name BTree
+ @{
+*/
+
+/**
+ A B-Tree.
+*/
+typedef struct ZixBTreeImpl ZixBTree;
+
+/**
+ A B-Tree node (opaque).
+*/
+typedef struct ZixBTreeNodeImpl ZixBTreeNode;
+
+/**
+ An iterator over a B-Tree.
+
+ Note that modifying the trees invalidates all iterators, so all iterators
+ are const iterators.
+*/
+typedef struct ZixBTreeIterImpl ZixBTreeIter;
+
+/**
+ Create a new (empty) B-Tree.
+*/
+ZIX_API ZixBTree*
+zix_btree_new(ZixComparator cmp,
+ void* cmp_data,
+ ZixDestroyFunc destroy);
+
+/**
+ Free `t`.
+*/
+ZIX_API void
+zix_btree_free(ZixBTree* t);
+
+/**
+ Return the number of elements in `t`.
+*/
+ZIX_API size_t
+zix_btree_size(const ZixBTree* t);
+
+/**
+ Insert the element `e` into `t`.
+*/
+ZIX_API ZixStatus
+zix_btree_insert(ZixBTree* t, void* e);
+
+/**
+ Remove the value `e` from `t`, set `removed` to the removed pointer.
+*/
+ZIX_API ZixStatus
+zix_btree_remove(ZixBTree* t, const void* e, void** removed);
+
+/**
+ Set `ti` to an element equal to `e` in `t`.
+ If no such item exists, `ti` is set to NULL.
+*/
+ZIX_API ZixStatus
+zix_btree_find(const ZixBTree* t, const void* e, ZixBTreeIter** ti);
+
+/**
+ Set `ti` to the smallest element in `t` that is not less than `e`.
+
+ Wildcards are supported, so if the search key `e` compares equal to many
+ values in the tree, `ti` will be set to the least such element. The search
+ key `e` is always passed as the second argument to the comparator.
+*/
+ZIX_API ZixStatus
+zix_btree_lower_bound(const ZixBTree* t, const void* e, ZixBTreeIter** ti);
+
+/**
+ Return the data associated with the given tree item.
+*/
+ZIX_API void*
+zix_btree_get(const ZixBTreeIter* ti);
+
+/**
+ Return an iterator to the first (smallest) element in `t`.
+
+ The returned iterator must be freed with zix_btree_iter_free().
+*/
+ZIX_API ZixBTreeIter*
+zix_btree_begin(const ZixBTree* t);
+
+/**
+ Return true iff `i` is an iterator to the end of its tree.
+*/
+ZIX_API bool
+zix_btree_iter_is_end(const ZixBTreeIter* i);
+
+/**
+ Increment `i` to point to the next element in the tree.
+*/
+ZIX_API void
+zix_btree_iter_increment(ZixBTreeIter* i);
+
+/**
+ Free `i`.
+*/
+ZIX_API void
+zix_btree_iter_free(ZixBTreeIter* i);
+
+/**
+ @}
+ @}
+*/
+
+#ifdef __cplusplus
+} /* extern "C" */
+#endif
+
+#endif /* ZIX_BTREE_H */
diff --git a/src/zix/hash.c b/src/zix/hash.c
index 655c5df..f633e16 100644
--- a/src/zix/hash.c
+++ b/src/zix/hash.c
@@ -1,5 +1,5 @@
/*
- Copyright 2011 David Robillard <http://drobilla.net>
+ Copyright 2011-2014 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
@@ -58,13 +58,18 @@ zix_hash_new(ZixHashFunc hash_func,
size_t value_size)
{
ZixHash* hash = (ZixHash*)malloc(sizeof(ZixHash));
- hash->hash_func = hash_func;
- hash->equal_func = equal_func;
- hash->n_buckets = &sizes[0];
- hash->value_size = value_size;
- hash->count = 0;
- hash->buckets = (ZixHashEntry**)calloc(*hash->n_buckets,
- sizeof(ZixHashEntry*));
+ if (hash) {
+ hash->hash_func = hash_func;
+ hash->equal_func = equal_func;
+ hash->n_buckets = &sizes[0];
+ hash->value_size = value_size;
+ hash->count = 0;
+ if (!(hash->buckets = (ZixHashEntry**)calloc(*hash->n_buckets,
+ sizeof(ZixHashEntry*)))) {
+ free(hash);
+ return NULL;
+ }
+ }
return hash;
}
@@ -225,4 +230,3 @@ zix_hash_foreach(ZixHash* hash,
}
}
}
-
diff --git a/src/zix/tree.c b/src/zix/tree.c
deleted file mode 100644
index 23a7e8c..0000000
--- a/src/zix/tree.c
+++ /dev/null
@@ -1,716 +0,0 @@
-/*
- Copyright 2011-2014 David Robillard <http://drobilla.net>
-
- Permission to use, copy, modify, and/or distribute this software for any
- purpose with or without fee is hereby granted, provided that the above
- copyright notice and this permission notice appear in all copies.
-
- THIS SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL WARRANTIES
- WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF
- MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR
- ANY SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES
- WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN
- ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF
- OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE.
-*/
-
-#include <assert.h>
-#include <stdint.h>
-#include <stdio.h>
-#include <stdlib.h>
-#include <string.h>
-
-#include "zix/common.h"
-#include "zix/tree.h"
-
-typedef struct ZixTreeNodeImpl ZixTreeNode;
-
-struct ZixTreeImpl {
- ZixTreeNode* root;
- ZixDestroyFunc destroy;
- ZixComparator cmp;
- void* cmp_data;
- size_t size;
- bool allow_duplicates;
-};
-
-struct ZixTreeNodeImpl {
- void* data;
- struct ZixTreeNodeImpl* left;
- struct ZixTreeNodeImpl* right;
- struct ZixTreeNodeImpl* parent;
- int_fast8_t balance;
-};
-
-#define MIN(a, b) (((a) < (b)) ? (a) : (b))
-#define MAX(a, b) (((a) > (b)) ? (a) : (b))
-
-// Uncomment these for debugging features
-// #define ZIX_TREE_DUMP 1
-// #define ZIX_TREE_VERIFY 1
-// #define ZIX_TREE_HYPER_VERIFY 1
-
-#if defined(ZIX_TREE_VERIFY) || defined(ZIX_TREE_HYPER_VERIFY)
-# include "tree_debug.h"
-# define ASSERT_BALANCE(n) assert(verify_balance(n))
-#else
-# define ASSERT_BALANCE(n)
-#endif
-
-#ifdef ZIX_TREE_DUMP
-# include "tree_debug.h"
-# define DUMP(t) zix_tree_print(t->root, 0)
-# define DEBUG_PRINTF(fmt, ...) printf(fmt, __VA_ARGS__)
-#else
-# define DUMP(t)
-# define DEBUG_PRINTF(fmt, ...)
-#endif
-
-ZIX_API ZixTree*
-zix_tree_new(bool allow_duplicates,
- ZixComparator cmp,
- void* cmp_data,
- ZixDestroyFunc destroy)
-{
- ZixTree* t = (ZixTree*)malloc(sizeof(ZixTree));
- t->root = NULL;
- t->destroy = destroy;
- t->cmp = cmp;
- t->cmp_data = cmp_data;
- t->size = 0;
- t->allow_duplicates = allow_duplicates;
- return t;
-}
-
-ZIX_PRIVATE void
-zix_tree_free_rec(ZixTree* t, ZixTreeNode* n)
-{
- if (n) {
- zix_tree_free_rec(t, n->left);
- zix_tree_free_rec(t, n->right);
- if (t->destroy) {
- t->destroy(n->data);
- }
- free(n);
- }
-}
-
-ZIX_API void
-zix_tree_free(ZixTree* t)
-{
- if (t) {
- zix_tree_free_rec(t, t->root);
- free(t);
- }
-}
-
-ZIX_API size_t
-zix_tree_size(const ZixTree* t)
-{
- return t->size;
-}
-
-ZIX_PRIVATE 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 `p`.
- *
- * p q
- * / \ / \
- * A q => p C
- * / \ / \
- * B C A B
- */
-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;
-}
-
-/**
- * Rotate right about `p`.
- *
- * p q
- * / \ / \
- * q C => A p
- * / \ / \
- * A B B C
- *
- */
-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;
-}
-
-/**
- * Rotate left about `p->left` then right about `p`.
- *
- * p r
- * / \ / \
- * q D => q p
- * / \ / \ / \
- * A r A B C D
- * / \
- * B C
- *
- */
-ZIX_PRIVATE 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 `p->right` then right about `p`.
- *
- * p r
- * / \ / \
- * A q => p q
- * / \ / \ / \
- * r D A B C D
- * / \
- * B C
- *
- */
-ZIX_PRIVATE 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;
-}
-
-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));
- ZixTreeNode* replacement = node;
- if (node->balance == -2) {
- assert(node->left);
- if (node->left->balance == 1) {
- replacement = rotate_left_right(node, height_change);
- } else {
- replacement = rotate_right(node, height_change);
- }
- } else if (node->balance == 2) {
- assert(node->right);
- if (node->right->balance == -1) {
- replacement = rotate_right_left(node, height_change);
- } else {
- replacement = rotate_left(node, height_change);
- }
- }
- if (is_root) {
- assert(!replacement->parent);
- t->root = replacement;
- }
- DUMP(t);
-#ifdef ZIX_TREE_HYPER_VERIFY
- assert(old_height + *height_change == height(replacement));
-#endif
- return replacement;
-}
-
-ZIX_API ZixStatus
-zix_tree_insert(ZixTree* t, void* e, ZixTreeIter** ti)
-{
- DEBUG_PRINTF("**** INSERT %ld\n", (intptr_t)e);
- int cmp = 0;
- ZixTreeNode* n = t->root;
- ZixTreeNode* p = NULL;
-
- // Find the parent p of e
- while (n) {
- p = n;
- cmp = t->cmp(e, n->data, t->cmp_data);
- if (cmp < 0) {
- n = n->left;
- } else if (cmp > 0) {
- n = n->right;
- } else if (t->allow_duplicates) {
- n = n->right;
- } else {
- if (ti) {
- *ti = n;
- }
- DEBUG_PRINTF("%ld EXISTS!\n", (intptr_t)e);
- return ZIX_STATUS_EXISTS;
- }
- }
-
- // Allocate a new node n
- if (!(n = (ZixTreeNode*)malloc(sizeof(ZixTreeNode)))) {
- return ZIX_STATUS_NO_MEM;
- }
- memset(n, '\0', sizeof(ZixTreeNode));
- n->data = e;
- n->balance = 0;
- if (ti) {
- *ti = n;
- }
-
- bool p_height_increased = false;
-
- // Make p the parent of n
- n->parent = p;
- if (!p) {
- t->root = n;
- } else {
- if (cmp < 0) {
- assert(!p->left);
- assert(p->balance == 0 || p->balance == 1);
- p->left = n;
- --p->balance;
- p_height_increased = !p->right;
- } else {
- assert(!p->right);
- assert(p->balance == 0 || p->balance == -1);
- p->right = n;
- ++p->balance;
- p_height_increased = !p->left;
- }
- }
-
- DUMP(t);
-
- // Rebalance if necessary (at most 1 rotation)
- assert(!p || p->balance == -1 || p->balance == 0 || p->balance == 1);
- if (p && p_height_increased) {
- int height_change = 0;
- for (ZixTreeNode* i = p; i && i->parent; i = i->parent) {
- if (i == i->parent->left) {
- if (--i->parent->balance == -2) {
- zix_tree_rebalance(t, i->parent, &height_change);
- break;
- }
- } else {
- assert(i == i->parent->right);
- if (++i->parent->balance == 2) {
- zix_tree_rebalance(t, i->parent, &height_change);
- break;
- }
- }
-
- if (i->parent->balance == 0) {
- break;
- }
- }
- }
-
- DUMP(t);
-
- ++t->size;
-
-#ifdef ZIX_TREE_VERIFY
- if (!verify(t, t->root)) {
- return ZIX_STATUS_ERROR;
- }
-#endif
-
- return ZIX_STATUS_SUCCESS;
-}
-
-ZIX_API ZixStatus
-zix_tree_remove(ZixTree* t, ZixTreeIter* ti)
-{
- ZixTreeNode* const n = ti;
- ZixTreeNode** pp = NULL; // parent pointer
- ZixTreeNode* to_balance = n->parent; // lowest node to balance
- int8_t d_balance = 0; // delta(balance) for n->parent
-
- DEBUG_PRINTF("*** REMOVE %ld\n", (intptr_t)n->data);
-
- if ((n == t->root) && !n->left && !n->right) {
- t->root = NULL;
- if (t->destroy) {
- t->destroy(n->data);
- }
- free(n);
- --t->size;
- assert(t->size == 0);
- return ZIX_STATUS_SUCCESS;
- }
-
- // Set pp to the parent pointer to n, if applicable
- if (n->parent) {
- assert(n->parent->left == n || n->parent->right == n);
- if (n->parent->left == n) { // n is left child
- pp = &n->parent->left;
- d_balance = 1;
- } else { // n is right child
- assert(n->parent->right == n);
- pp = &n->parent->right;
- d_balance = -1;
- }
- }
-
- assert(!pp || *pp == n);
-
- int height_change = 0;
- if (!n->left && !n->right) {
- // n is a leaf, just remove it
- if (pp) {
- *pp = NULL;
- to_balance = n->parent;
- height_change = (!n->parent->left && !n->parent->right) ? -1 : 0;
- }
- } else if (!n->left) {
- // Replace n with right (only) child
- if (pp) {
- *pp = n->right;
- to_balance = n->parent;
- } else {
- t->root = n->right;
- }
- n->right->parent = n->parent;
- height_change = -1;
- } else if (!n->right) {
- // Replace n with left (only) child
- if (pp) {
- *pp = n->left;
- to_balance = n->parent;
- } else {
- t->root = n->left;
- }
- n->left->parent = n->parent;
- height_change = -1;
- } else {
- // Replace n with in-order successor (leftmost child of right subtree)
- ZixTreeNode* replace = n->right;
- while (replace->left) {
- assert(replace->left->parent == replace);
- replace = replace->left;
- }
-
- // Remove replace from parent (replace_p)
- if (replace->parent->left == replace) {
- height_change = replace->parent->right ? 0 : -1;
- d_balance = 1;
- to_balance = replace->parent;
- replace->parent->left = replace->right;
- } else {
- assert(replace->parent == n);
- height_change = replace->parent->left ? 0 : -1;
- d_balance = -1;
- to_balance = replace->parent;
- replace->parent->right = replace->right;
- }
-
- if (to_balance == n) {
- to_balance = replace;
- }
-
- if (replace->right) {
- replace->right->parent = replace->parent;
- }
-
- replace->balance = n->balance;
-
- // Swap node to delete with replace
- if (pp) {
- *pp = replace;
- } else {
- assert(t->root == n);
- t->root = replace;
- }
- replace->parent = n->parent;
- replace->left = n->left;
- n->left->parent = replace;
- replace->right = n->right;
- if (n->right) {
- n->right->parent = replace;
- }
-
- assert(!replace->parent
- || replace->parent->left == replace
- || replace->parent->right == replace);
- }
-
- // Rebalance starting at to_balance upwards.
- for (ZixTreeNode* i = to_balance; i; i = i->parent) {
- i->balance += d_balance;
- if (d_balance == 0 || i->balance == -1 || i->balance == 1) {
- break;
- }
-
- assert(i != n);
- i = zix_tree_rebalance(t, i, &height_change);
- if (i->balance == 0) {
- height_change = -1;
- }
-
- if (i->parent) {
- if (i == i->parent->left) {
- d_balance = height_change * -1;
- } else {
- assert(i == i->parent->right);
- d_balance = height_change;
- }
- }
- }
-
- DUMP(t);
-
- if (t->destroy) {
- t->destroy(n->data);
- }
- free(n);
-
- --t->size;
-
-#ifdef ZIX_TREE_VERIFY
- if (!verify(t, t->root)) {
- return ZIX_STATUS_ERROR;
- }
-#endif
-
- return ZIX_STATUS_SUCCESS;
-}
-
-ZIX_API ZixStatus
-zix_tree_find(const ZixTree* t, const void* e, ZixTreeIter** ti)
-{
- ZixTreeNode* n = t->root;
- while (n) {
- const int cmp = t->cmp(e, n->data, t->cmp_data);
- if (cmp == 0) {
- break;
- } else if (cmp < 0) {
- n = n->left;
- } else {
- n = n->right;
- }
- }
-
- *ti = n;
- return (n) ? ZIX_STATUS_SUCCESS : ZIX_STATUS_NOT_FOUND;
-}
-
-ZIX_API void*
-zix_tree_get(ZixTreeIter* ti)
-{
- return ti ? ti->data : NULL;
-}
-
-ZIX_API ZixTreeIter*
-zix_tree_begin(ZixTree* t)
-{
- if (!t->root) {
- return NULL;
- }
-
- ZixTreeNode* n = t->root;
- while (n->left) {
- n = n->left;
- }
- return n;
-}
-
-ZIX_API ZixTreeIter*
-zix_tree_end(ZixTree* t)
-{
- return NULL;
-}
-
-ZIX_API ZixTreeIter*
-zix_tree_rbegin(ZixTree* t)
-{
- if (!t->root) {
- return NULL;
- }
-
- ZixTreeNode* n = t->root;
- while (n->right) {
- n = n->right;
- }
- return n;
-}
-
-ZIX_API ZixTreeIter*
-zix_tree_rend(ZixTree* t)
-{
- return NULL;
-}
-
-ZIX_API bool
-zix_tree_iter_is_end(ZixTreeIter* i)
-{
- return !i;
-}
-
-ZIX_API bool
-zix_tree_iter_is_rend(ZixTreeIter* i)
-{
- return !i;
-}
-
-ZIX_API ZixTreeIter*
-zix_tree_iter_next(ZixTreeIter* i)
-{
- if (!i) {
- return NULL;
- }
-
- if (i->right) {
- i = i->right;
- while (i->left) {
- i = i->left;
- }
- } else {
- while (i->parent && i->parent->right == i) { // i is a right child
- i = i->parent;
- }
-
- i = i->parent;
- }
-
- return i;
-}
-
-ZIX_API ZixTreeIter*
-zix_tree_iter_prev(ZixTreeIter* i)
-{
- if (!i) {
- return NULL;
- }
-
- if (i->left) {
- i = i->left;
- while (i->right) {
- i = i->right;
- }
- } else {
- while (i->parent && i->parent->left == i) { // i is a left child
- i = i->parent;
- }
-
- i = i->parent;
- }
-
- return i;
-}
diff --git a/src/zix/tree.h b/src/zix/tree.h
deleted file mode 100644
index 8474b1c..0000000
--- a/src/zix/tree.h
+++ /dev/null
@@ -1,148 +0,0 @@
-/*
- Copyright 2011-2014 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 <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 ZixTree.
-*/
-typedef struct ZixTreeNodeImpl ZixTreeIter;
-
-/**
- Create a new (empty) tree.
-*/
-ZIX_API ZixTree*
-zix_tree_new(bool allow_duplicates,
- ZixComparator cmp,
- void* cmp_data,
- ZixDestroyFunc destroy);
-
-/**
- Free `t`.
-*/
-ZIX_API void
-zix_tree_free(ZixTree* t);
-
-/**
- Return the number of elements in `t`.
-*/
-ZIX_API size_t
-zix_tree_size(const ZixTree* t);
-
-/**
- Insert the element `e` into `t` and point `ti` at the new element.
-*/
-ZIX_API ZixStatus
-zix_tree_insert(ZixTree* t, void* e, ZixTreeIter** ti);
-
-/**
- Remove the item pointed at by `ti` from `t`.
-*/
-ZIX_API ZixStatus
-zix_tree_remove(ZixTree* t, ZixTreeIter* ti);
-
-/**
- Set `ti` to an element equal to `e` in `t`.
- If no such item exists, `ti` is set to NULL.
-*/
-ZIX_API ZixStatus
-zix_tree_find(const ZixTree* t, const void* e, ZixTreeIter** ti);
-
-/**
- Return the data associated with the given tree item.
-*/
-ZIX_API void*
-zix_tree_get(ZixTreeIter* ti);
-
-/**
- Return an iterator to the first (smallest) element in `t`.
-*/
-ZIX_API ZixTreeIter*
-zix_tree_begin(ZixTree* t);
-
-/**
- Return an iterator the the element one past the last element in `t`.
-*/
-ZIX_API ZixTreeIter*
-zix_tree_end(ZixTree* t);
-
-/**
- Return true iff `i` is an iterator to the end of its tree.
-*/
-ZIX_API bool
-zix_tree_iter_is_end(ZixTreeIter* i);
-
-/**
- Return an iterator to the last (largest) element in `t`.
-*/
-ZIX_API ZixTreeIter*
-zix_tree_rbegin(ZixTree* t);
-
-/**
- Return an iterator the the element one before the first element in `t`.
-*/
-ZIX_API ZixTreeIter*
-zix_tree_rend(ZixTree* t);
-
-/**
- Return true iff `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 `i`.
-*/
-ZIX_API ZixTreeIter*
-zix_tree_iter_next(ZixTreeIter* i);
-
-/**
- Return an iterator that points to the element one before `i`.
-*/
-ZIX_API ZixTreeIter*
-zix_tree_iter_prev(ZixTreeIter* i);
-
-/**
- @}
- @}
-*/
-
-#ifdef __cplusplus
-} /* extern "C" */
-#endif
-
-#endif /* ZIX_TREE_H */
generated by cgit v1.2.1 (git 2.18.0) at 2024-11-16 05:03:59 +0000