Flesh out BTree iterator API

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