summaryrefslogtreecommitdiffstats
diff options
context:
space:
mode:
authorDavid Robillard <d@drobilla.net>2019-01-06 17:21:40 +0100
committerDavid Robillard <d@drobilla.net>2019-01-06 17:21:40 +0100
commit261dba69c4dbc53335b3f75aa2d4e6b299768c7f (patch)
tree5c47e76309a0d0694048dd77dc22143bc1bede7f
parent5807e4a873730fdb245b3c39913fc6acb3779f8a (diff)
downloadzix-261dba69c4dbc53335b3f75aa2d4e6b299768c7f.tar.gz
zix-261dba69c4dbc53335b3f75aa2d4e6b299768c7f.tar.bz2
zix-261dba69c4dbc53335b3f75aa2d4e6b299768c7f.zip
Flesh out BTree iterator API
-rw-r--r--zix/btree.c43
-rw-r--r--zix/btree.h20
2 files changed, 62 insertions, 1 deletions
diff --git a/zix/btree.c b/zix/btree.c
index 75ce363..69e7575 100644
--- a/zix/btree.c
+++ b/zix/btree.c
@@ -54,6 +54,7 @@ typedef struct {
} ZixBTreeIterFrame;
struct ZixBTreeIterImpl {
+ unsigned n_levels; ///< Maximum depth of stack
unsigned level; ///< Current level in stack
ZixBTreeIterFrame stack[]; ///< Position stack
};
@@ -323,7 +324,11 @@ zix_btree_iter_new(const ZixBTree* const t)
{
const size_t s = t->height * sizeof(ZixBTreeIterFrame);
- return (ZixBTreeIter*)calloc(1, sizeof(ZixBTreeIter) + s);
+ ZixBTreeIter* i = (ZixBTreeIter*)calloc(1, sizeof(ZixBTreeIter) + s);
+ if (i) {
+ i->n_levels = t->height;
+ }
+ return i;
}
ZIX_PRIVATE void
@@ -685,12 +690,48 @@ zix_btree_begin(const ZixBTree* const t)
return i;
}
+ZIX_API ZixBTreeIter*
+zix_btree_end(const ZixBTree* const t)
+{
+ return zix_btree_iter_new(t);
+}
+
+ZIX_API ZixBTreeIter*
+zix_btree_iter_copy(const ZixBTreeIter* const i)
+{
+ if (!i) {
+ return NULL;
+ }
+
+ const size_t s = i->n_levels * sizeof(ZixBTreeIterFrame);
+ ZixBTreeIter* j = (ZixBTreeIter*)calloc(1, sizeof(ZixBTreeIter) + s);
+ if (j) {
+ memcpy(j, i, sizeof(ZixBTreeIter) + s);
+ }
+ return j;
+}
+
ZIX_API bool
zix_btree_iter_is_end(const ZixBTreeIter* const i)
{
return !i || i->stack[0].node == NULL;
}
+ZIX_API bool
+zix_btree_iter_equals(const ZixBTreeIter* const lhs, const ZixBTreeIter* const rhs)
+{
+ if (zix_btree_iter_is_end(lhs) && zix_btree_iter_is_end(rhs)) {
+ return true;
+ } else if (!lhs || !rhs || lhs->n_levels != rhs->n_levels) {
+ return false;
+ }
+
+ return !memcmp(lhs,
+ rhs,
+ sizeof(ZixBTreeIter) +
+ lhs->n_levels * sizeof(ZixBTreeIterFrame));
+}
+
ZIX_API void
zix_btree_iter_increment(ZixBTreeIter* const i)
{
diff --git a/zix/btree.h b/zix/btree.h
index 6aca9bf..4c972f6 100644
--- a/zix/btree.h
+++ b/zix/btree.h
@@ -125,6 +125,26 @@ ZIX_API ZixBTreeIter*
zix_btree_begin(const ZixBTree* t);
/**
+ Return an iterator to the end of `t` (one past the last element).
+
+ The returned iterator must be freed with zix_btree_iter_free().
+*/
+ZIX_API ZixBTreeIter*
+zix_btree_end(const ZixBTree* t);
+
+/**
+ Return a new copy of `i`.
+*/
+ZIX_API ZixBTreeIter*
+zix_btree_iter_copy(const ZixBTreeIter* i);
+
+/**
+ Return true iff `lhs` is equal to `rhs`.
+*/
+ZIX_API bool
+zix_btree_iter_equals(const ZixBTreeIter* lhs, const ZixBTreeIter* rhs);
+
+/**
Return true iff `i` is an iterator to the end of its tree.
*/
ZIX_API bool