Allow ZixBTreeIter to be allocated on the stack

7 files changed, 174 insertions, 268 deletions

diff --git a/benchmark/tree_bench.c b/benchmark/tree_bench.c
index e01b64f..d27c506 100644
--- a/benchmark/tree_bench.c
+++ b/benchmark/tree_bench.c
@@ -154,9 +154,9 @@ bench_zix_btree(size_t n_elems,
 {
   start_test("ZixBTree");
 
-  uintptr_t     r  = 0u;
-  ZixBTreeIter* ti = NULL;
-  ZixBTree*     t  = zix_btree_new(int_cmp, NULL);
+  uintptr_t    r  = 0u;
+  ZixBTreeIter ti = zix_btree_end_iter;
+  ZixBTree*    t  = zix_btree_new(int_cmp, NULL);
 
   // Insert n_elems elements
   struct timespec insert_start = bench_start();
@@ -185,12 +185,11 @@ bench_zix_btree(size_t n_elems,
 
   // Iterate over all elements
   struct timespec iter_start = bench_start();
-  ZixBTreeIter*   iter       = zix_btree_begin(t);
-  for (; !zix_btree_iter_is_end(iter); zix_btree_iter_increment(iter)) {
+  ZixBTreeIter    iter       = zix_btree_begin(t);
+  for (; !zix_btree_iter_is_end(iter); zix_btree_iter_increment(&iter)) {
     volatile void* const value = zix_btree_get(iter);
     (void)value;
   }
-  zix_btree_iter_free(iter);
   fprintf(iter_dat, "\t%lf", bench_end(&iter_start));
 
   // Delete all elements
diff --git a/include/.clang-tidy b/include/.clang-tidy
index 8399cae..fec15b8 100644
--- a/include/.clang-tidy
+++ b/include/.clang-tidy
@@ -1,5 +1,6 @@
 Checks: >
   *,
+  -*-uppercase-literal-suffix,
   -altera-struct-pack-align,
   -clang-diagnostic-unused-function,
   -clang-diagnostic-unused-macros,
diff --git a/include/zix/btree.h b/include/zix/btree.h
index 5472eca..5212ec7 100644
--- a/include/zix/btree.h
+++ b/include/zix/btree.h
@@ -21,6 +21,7 @@
 
 #include <stdbool.h>
 #include <stddef.h>
+#include <stdint.h>
 
 #ifdef __cplusplus
 extern "C" {
@@ -33,6 +34,19 @@ extern "C" {
    @{
 */
 
+/**
+   The maximum height of a ZixBTree.
+
+   This is exposed because it determines the size of iterators, which are
+   statically sized so they can used on the stack.  The usual degree (or
+   "fanout") of a B-Tree is high enough that a relatively short tree can
+   contain many elements.  With the default page size of 4 KiB, the default
+   height of 6 is enough to store trillions.
+*/
+#ifndef ZIX_BTREE_MAX_HEIGHT
+#  define ZIX_BTREE_MAX_HEIGHT 6u
+#endif
+
 /// A B-Tree
 typedef struct ZixBTreeImpl ZixBTree;
 
@@ -42,10 +56,23 @@ typedef struct ZixBTreeNodeImpl ZixBTreeNode;
 /**
    An iterator over a B-Tree.
 
-   Note that modifying the trees invalidates all iterators, so all iterators
-   are const iterators.
+   Note that modifying the tree invalidates all iterators.
+
+   The contents of this type are considered an implementation detail and should
+   not be used directly by clients.  They are nevertheless exposed here so that
+   iterators can be allocated on the stack.
 */
-typedef struct ZixBTreeIterImpl ZixBTreeIter;
+typedef struct {
+  ZixBTreeNode* nodes[ZIX_BTREE_MAX_HEIGHT];   ///< Parallel node pointer stack
+  uint16_t      indexes[ZIX_BTREE_MAX_HEIGHT]; ///< Parallel child index stack
+  uint16_t      level;                         ///< Current level in stack
+} ZixBTreeIter;
+
+/// A static end iterator for convenience
+static const ZixBTreeIter zix_btree_end_iter = {
+  {NULL, NULL, NULL, NULL, NULL, NULL},
+  {0u, 0u, 0u, 0u, 0u, 0u},
+  0u};
 
 /// Create a new (empty) B-Tree
 ZIX_API
@@ -91,22 +118,21 @@ zix_btree_insert(ZixBTree* t, void* e);
 
    @param out Set to point to the removed pointer (which may not equal `e`).
 
-   @param next If non-NULL, pointed to the value following `e`.  If *next is
-   also non-NULL, the iterator is reused, otherwise a new one is allocated.  To
-   reuse an iterator, no items may have been added since its creation.
+   @param next On successful return, set to point at the value that immediately
+   followed `e`.
 */
 ZIX_API
 ZixStatus
-zix_btree_remove(ZixBTree* t, const void* e, void** out, ZixBTreeIter** next);
+zix_btree_remove(ZixBTree* t, const void* e, void** out, ZixBTreeIter* next);
 
 /**
    Set `ti` to an element equal to `e` in `t`.
 
-   If no such item exists, `ti` is set to NULL.
+   If no such item exists, `ti` is set to the end.
 */
 ZIX_API
 ZixStatus
-zix_btree_find(const ZixBTree* t, const void* e, ZixBTreeIter** ti);
+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`.
@@ -117,56 +143,40 @@ zix_btree_find(const ZixBTree* t, const void* e, ZixBTreeIter** ti);
 */
 ZIX_API
 ZixStatus
-zix_btree_lower_bound(const ZixBTree* t, const void* e, ZixBTreeIter** ti);
+zix_btree_lower_bound(const ZixBTree* t, const void* e, ZixBTreeIter* ti);
 
 /// Return the data associated with the given tree item
 ZIX_PURE_API
 void*
-zix_btree_get(const ZixBTreeIter* ti);
+zix_btree_get(ZixBTreeIter ti);
 
-/**
-   Return an iterator to the first (smallest) element in `t`.
-
-   The returned iterator must be freed with zix_btree_iter_free().
-*/
+/// Return an iterator to the first (smallest) element in `t`
 ZIX_PURE_API
-ZixBTreeIter*
+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*
+/// Return an iterator to the end of `t` (one past the last element)
+ZIX_CONST_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_PURE_API
 bool
-zix_btree_iter_equals(const ZixBTreeIter* lhs, const ZixBTreeIter* rhs);
+zix_btree_iter_equals(ZixBTreeIter lhs, ZixBTreeIter rhs);
 
-/// Return true iff `i` is an iterator to the end of its tree
-ZIX_PURE_API
-bool
-zix_btree_iter_is_end(const ZixBTreeIter* i);
+/// Return true iff `i` is an iterator at the end of a tree
+static inline bool
+zix_btree_iter_is_end(const ZixBTreeIter i)
+{
+  return i.level == 0 && !i.nodes[0];
+}
 
 /// Increment `i` to point to the next element in the tree
 ZIX_API
-void
+ZixStatus
 zix_btree_iter_increment(ZixBTreeIter* i);
 
-/// Free `i`
-ZIX_API
-void
-zix_btree_iter_free(ZixBTreeIter* i);
-
 /**
    @}
    @}
diff --git a/include/zix/common.h b/include/zix/common.h
index 926e281..02f00b4 100644
--- a/include/zix/common.h
+++ b/include/zix/common.h
@@ -87,7 +87,8 @@ typedef enum {
   ZIX_STATUS_NOT_FOUND,
   ZIX_STATUS_EXISTS,
   ZIX_STATUS_BAD_ARG,
-  ZIX_STATUS_BAD_PERMS
+  ZIX_STATUS_BAD_PERMS,
+  ZIX_STATUS_REACHED_END
 } ZixStatus;
 
 static inline const char*
@@ -108,6 +109,8 @@ zix_strerror(const ZixStatus status)
     return "Bad argument";
   case ZIX_STATUS_BAD_PERMS:
     return "Bad permissions";
+  case ZIX_STATUS_REACHED_END:
+    return "Reached end";
   }
   return "Unknown error";
 }
diff --git a/meson.build b/meson.build
index 8be6321..cdde084 100644
--- a/meson.build
+++ b/meson.build
@@ -54,7 +54,7 @@ if get_option('strict')
       '-Wformat-signedness',
       '-Wformat-truncation=2',
       '-Wformat=2',
-      '-Wframe-larger-than=512',
+      '-Wframe-larger-than=1024',
       '-Wimplicit-fallthrough=2',
       '-Winit-self',
       # '-Winline',
@@ -74,7 +74,7 @@ if get_option('strict')
       '-Wshift-overflow=2',
       '-Wsizeof-array-argument',
       '-Wstack-protector',
-      '-Wstack-usage=512',
+      '-Wstack-usage=1024',
       '-Wstrict-aliasing=3',
       # '-Wstrict-overflow=5',
       '-Wstringop-overflow=3',
diff --git a/src/btree.c b/src/btree.c
index eb5a5f5..483cfa8 100644
--- a/src/btree.c
+++ b/src/btree.c
@@ -43,7 +43,6 @@ struct ZixBTreeImpl {
   ZixComparator cmp;
   const void*   cmp_data;
   size_t        size;
-  unsigned      height; ///< Number of levels, i.e. root only has height 1
 };
 
 struct ZixBTreeNodeImpl {
@@ -83,7 +82,9 @@ zix_btree_node_new(const bool leaf)
 {
 #if !((defined(__STDC_VERSION__) && __STDC_VERSION__ >= 201112l) || \
       (defined(__cplusplus) && __cplusplus >= 201103L))
-  assert(sizeof(ZixBTreeNode) == ZIX_BTREE_PAGE_SIZE);
+  assert(sizeof(ZixBTreeNode) <= ZIX_BTREE_PAGE_SIZE);
+  assert(sizeof(ZixBTreeNode) >=
+         ZIX_BTREE_PAGE_SIZE - 2u * sizeof(ZixBTreeNode*));
 #endif
 
   ZixBTreeNode* node = (ZixBTreeNode*)malloc(sizeof(ZixBTreeNode));
@@ -120,7 +121,6 @@ zix_btree_new(const ZixComparator cmp, const void* const cmp_data)
     t->cmp      = cmp;
     t->cmp_data = cmp_data;
     t->size     = 0;
-    t->height   = 1;
     if (!t->root) {
       free(t);
       return NULL;
@@ -172,7 +172,6 @@ zix_btree_clear(ZixBTree* const t, ZixDestroyFunc destroy)
   memset(t->root, 0, sizeof(ZixBTreeNode));
   t->root->is_leaf = true;
   t->size          = 0u;
-  t->height        = 1u;
 }
 
 size_t
@@ -336,7 +335,6 @@ zix_btree_insert(ZixBTree* const t, void* const e)
         }
         t->root                        = parent;
         parent->data.inode.children[0] = n;
-        ++t->height;
       }
 
       ZixBTreeNode* const rhs = zix_btree_split_child(parent, i, n);
@@ -380,27 +378,35 @@ zix_btree_insert(ZixBTree* const t, void* const e)
   return ZIX_STATUS_SUCCESS;
 }
 
-static ZixBTreeIter*
-zix_btree_iter_new(const ZixBTree* const t)
+static void
+zix_btree_iter_set_frame(ZixBTreeIter* const ti,
+                         ZixBTreeNode* const n,
+                         const ZixShort      i)
 {
-  const size_t s = t->height * sizeof(ZixBTreeIterFrame);
+  assert(i <= ZIX_BTREE_LEAF_VALS);
 
-  ZixBTreeIter* i = (ZixBTreeIter*)calloc(1, sizeof(ZixBTreeIter) + s);
-  if (i) {
-    i->n_levels = t->height;
-  }
-  return i;
+  ti->nodes[ti->level]   = n;
+  ti->indexes[ti->level] = (uint16_t)i;
 }
 
 static void
-zix_btree_iter_set_frame(ZixBTreeIter* const ti,
-                         ZixBTreeNode* const n,
-                         const unsigned      i)
+zix_btree_iter_push(ZixBTreeIter* const ti,
+                    ZixBTreeNode* const n,
+                    const ZixShort      i)
 {
-  if (ti) {
-    ti->stack[ti->level].node  = n;
-    ti->stack[ti->level].index = i;
-  }
+  assert(ti->level < ZIX_BTREE_MAX_HEIGHT);
+  ++ti->level;
+  ti->nodes[ti->level]   = n;
+  ti->indexes[ti->level] = (uint16_t)i;
+}
+
+static void
+zix_btree_iter_pop(ZixBTreeIter* const ti)
+{
+  assert(ti->level > 0u);
+  ti->nodes[ti->level]   = NULL;
+  ti->indexes[ti->level] = 0u;
+  --ti->level;
 }
 
 ZIX_PURE_FUNC
@@ -574,21 +580,15 @@ zix_btree_remove_max(ZixBTree* const t, ZixBTreeNode* n)
 }
 
 ZixStatus
-zix_btree_remove(ZixBTree* const      t,
-                 const void* const    e,
-                 void** const         out,
-                 ZixBTreeIter** const next)
-{
-  ZixBTreeNode* n         = t->root;
-  ZixBTreeIter* ti        = NULL;
-  const bool    user_iter = next && *next;
-  if (next) {
-    if (!*next && !(*next = zix_btree_iter_new(t))) {
-      return ZIX_STATUS_NO_MEM;
-    }
-    ti        = *next;
-    ti->level = 0;
-  }
+zix_btree_remove(ZixBTree* const     t,
+                 const void* const   e,
+                 void** const        out,
+                 ZixBTreeIter* const next)
+{
+  ZixBTreeNode* n  = t->root;
+  ZixBTreeIter* ti = next;
+
+  *ti = zix_btree_end_iter;
 
   while (true) {
     /* To remove in a single walk down, the tree is adjusted along the way
@@ -606,10 +606,10 @@ zix_btree_remove(ZixBTree* const      t,
         *out = zix_btree_aerase(n->data.leaf.vals, --n->n_vals, i);
         if (ti && i == n->n_vals) {
           if (i == 0) {
-            ti->level         = 0;
-            ti->stack[0].node = NULL;
+            ti->level    = 0;
+            ti->nodes[0] = NULL;
           } else {
-            --ti->stack[ti->level].index;
+            --ti->indexes[ti->level];
             zix_btree_iter_increment(ti);
           }
         }
@@ -618,11 +618,7 @@ zix_btree_remove(ZixBTree* const      t,
       }
 
       // Not found in leaf node, or tree
-      if (ti && !user_iter) {
-        zix_btree_iter_free(ti);
-        *next = NULL;
-      }
-
+      *next = zix_btree_end_iter;
       return ZIX_STATUS_NOT_FOUND;
     }
 
@@ -666,11 +662,9 @@ zix_btree_remove(ZixBTree* const      t,
           const ZixShort counts[2] = {zix_btree_child(n, 0)->n_vals,
                                       zix_btree_child(n, 1)->n_vals};
 
-          n = zix_btree_merge(t, n, 0);
-          if (ti) {
-            ti->stack[ti->level].node  = n;
-            ti->stack[ti->level].index = counts[i];
-          }
+          n                      = zix_btree_merge(t, n, 0);
+          ti->nodes[ti->level]   = n;
+          ti->indexes[ti->level] = (uint16_t)counts[i];
         } else {
           // Both child's siblings are minimal, merge them
           if (i < n->n_vals) {
@@ -678,7 +672,7 @@ zix_btree_remove(ZixBTree* const      t,
           } else {
             n = zix_btree_merge(t, n, i - 1U);
             if (ti) {
-              --ti->stack[ti->level].index;
+              --ti->indexes[ti->level];
             }
           }
         }
@@ -698,18 +692,17 @@ zix_btree_remove(ZixBTree* const      t,
 ZixStatus
 zix_btree_find(const ZixBTree* const t,
                const void* const     e,
-               ZixBTreeIter** const  ti)
+               ZixBTreeIter* const   ti)
 {
   ZixBTreeNode* n = t->root;
-  if (!(*ti = zix_btree_iter_new(t))) {
-    return ZIX_STATUS_NO_MEM;
-  }
+
+  *ti = zix_btree_end_iter;
 
   while (n) {
     bool           equal = false;
     const unsigned i     = zix_btree_node_find(t, n, e, &equal);
 
-    zix_btree_iter_set_frame(*ti, n, i);
+    zix_btree_iter_set_frame(ti, n, (uint16_t)i);
 
     if (equal) {
       return ZIX_STATUS_SUCCESS;
@@ -719,45 +712,33 @@ zix_btree_find(const ZixBTree* const t,
       break;
     }
 
-    ++(*ti)->level;
+    ++ti->level;
     n = zix_btree_child(n, i);
   }
 
-  zix_btree_iter_free(*ti);
-  *ti = NULL;
+  *ti = zix_btree_end_iter;
   return ZIX_STATUS_NOT_FOUND;
 }
 
 ZixStatus
 zix_btree_lower_bound(const ZixBTree* const t,
                       const void* const     e,
-                      ZixBTreeIter** const  ti)
+                      ZixBTreeIter* const   ti)
 {
-  if (!t) {
-    *ti = NULL;
-    return ZIX_STATUS_BAD_ARG;
-  }
-
-  if (!t->root) {
-    *ti = NULL;
-    return ZIX_STATUS_SUCCESS;
-  }
-
   ZixBTreeNode* n           = t->root;
   bool          found       = false;
   unsigned      found_level = 0;
-  if (!(*ti = zix_btree_iter_new(t))) {
-    return ZIX_STATUS_NO_MEM;
-  }
+
+  *ti = zix_btree_end_iter;
 
   while (n) {
     bool           equal = false;
     const unsigned i     = zix_btree_node_find(t, n, e, &equal);
 
-    zix_btree_iter_set_frame(*ti, n, i);
+    zix_btree_iter_set_frame(ti, n, (uint16_t)i);
 
     if (equal) {
-      found_level = (*ti)->level;
+      found_level = ti->level;
       found       = true;
     }
 
@@ -765,21 +746,18 @@ zix_btree_lower_bound(const ZixBTree* const t,
       break;
     }
 
-    ++(*ti)->level;
+    ++ti->level;
     n = zix_btree_child(n, i);
     assert(n);
   }
 
-  const ZixBTreeIterFrame* const frame = &(*ti)->stack[(*ti)->level];
-  assert(frame->node);
-  if (frame->index == frame->node->n_vals) {
+  if (ti->indexes[ti->level] == ti->nodes[ti->level]->n_vals) {
     if (found) {
       // Found on a previous level but went too far
-      (*ti)->level = found_level;
+      ti->level = (uint16_t)found_level;
     } else {
       // Reached end (key is greater than everything in tree)
-      (*ti)->level         = 0;
-      (*ti)->stack[0].node = NULL;
+      *ti = zix_btree_end_iter;
     }
   }
 
@@ -787,130 +765,86 @@ zix_btree_lower_bound(const ZixBTree* const t,
 }
 
 void*
-zix_btree_get(const ZixBTreeIter* const ti)
+zix_btree_get(const ZixBTreeIter ti)
 {
-  const ZixBTreeIterFrame* const frame = &ti->stack[ti->level];
-  assert(frame->node);
-  assert(frame->index < frame->node->n_vals);
-  return zix_btree_value(frame->node, frame->index);
+  const ZixBTreeNode* const node  = ti.nodes[ti.level];
+  const unsigned            index = ti.indexes[ti.level];
+
+  assert(node);
+  assert(index < node->n_vals);
+
+  return node->is_leaf ? node->data.leaf.vals[index]
+                       : node->data.inode.vals[index];
 }
 
-ZixBTreeIter*
+ZixBTreeIter
 zix_btree_begin(const ZixBTree* const t)
 {
-  ZixBTreeIter* const i = zix_btree_iter_new(t);
-  if (!i) {
-    return NULL;
-  }
+  ZixBTreeIter iter = zix_btree_end_iter;
+
+  if (t->size > 0u) {
+    ZixBTreeNode* n = t->root;
+    zix_btree_iter_set_frame(&iter, n, 0u);
 
-  if (t->size == 0) {
-    i->level         = 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 = zix_btree_child(n, 0);
-      ++i->level;
-      i->stack[i->level].node  = n;
-      i->stack[i->level].index = 0;
+      zix_btree_iter_push(&iter, n, 0u);
     }
   }
 
-  return i;
+  return iter;
 }
 
-ZixBTreeIter*
+ZixBTreeIter
 zix_btree_end(const ZixBTree* const t)
 {
-  return zix_btree_iter_new(t);
-}
-
-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);
-  }
+  (void)t;
 
-  return j;
-}
-
-bool
-zix_btree_iter_is_end(const ZixBTreeIter* const i)
-{
-  return !i || (i->level == 0 && i->stack[0].node == NULL);
+  return zix_btree_end_iter;
 }
 
 bool
-zix_btree_iter_equals(const ZixBTreeIter* const lhs,
-                      const ZixBTreeIter* const rhs)
+zix_btree_iter_equals(const ZixBTreeIter lhs, const ZixBTreeIter rhs)
 {
-  if (zix_btree_iter_is_end(lhs) && zix_btree_iter_is_end(rhs)) {
-    return true;
-  }
-
-  if (zix_btree_iter_is_end(lhs) || zix_btree_iter_is_end(rhs) ||
-      lhs->level != rhs->level) {
-    return false;
-  }
+  const size_t indexes_size = (lhs.level + 1u) * sizeof(uint16_t);
 
-  return !memcmp(lhs,
-                 rhs,
-                 sizeof(ZixBTreeIter) +
-                   (lhs->level + 1) * sizeof(ZixBTreeIterFrame));
+  return (lhs.level == rhs.level) && (lhs.nodes[0] == rhs.nodes[0]) &&
+         (!lhs.nodes[0] || !memcmp(lhs.indexes, rhs.indexes, indexes_size));
 }
 
-void
+ZixStatus
 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);
-      }
+  assert(!zix_btree_iter_is_end(*i));
 
-      if (f->index == f->node->n_vals) {
-        // Reached end of tree
-        assert(i->level == 0);
-        f->node  = NULL;
-        f->index = 0;
+  // Move to the next value in the current node
+  const uint16_t index = ++i->indexes[i->level];
+
+  if (i->nodes[i->level]->is_leaf) {
+    // Leaf, move up if necessary until we're not at the end of the node
+    while (i->indexes[i->level] >= i->nodes[i->level]->n_vals) {
+      if (i->level == 0) {
+        // End of root, end of tree
+        i->nodes[0] = NULL;
+        return ZIX_STATUS_REACHED_END;
       }
+
+      // At end of internal node, move up
+      zix_btree_iter_pop(i);
     }
+
   } else {
     // Internal node, move down to next child
-    assert(f->index < f->node->n_vals);
-    ZixBTreeNode* child = zix_btree_child(f->node, ++f->index);
+    const ZixBTreeNode* const node  = i->nodes[i->level];
+    ZixBTreeNode* const       child = node->data.inode.children[index];
 
-    f        = &i->stack[++i->level];
-    f->node  = child;
-    f->index = 0;
+    zix_btree_iter_push(i, child, 0u);
 
     // Move down and left until we hit a leaf
-    while (!f->node->is_leaf) {
-      child    = zix_btree_child(f->node, 0);
-      f        = &i->stack[++i->level];
-      f->node  = child;
-      f->index = 0;
+    while (!i->nodes[i->level]->is_leaf) {
+      zix_btree_iter_push(i, i->nodes[i->level]->data.inode.children[0], 0u);
     }
   }
-}
 
-void
-zix_btree_iter_free(ZixBTreeIter* const i)
-{
-  free(i);
+  return ZIX_STATUS_SUCCESS;
 }
diff --git a/test/btree_test.c b/test/btree_test.c
index 4e84ac4..c5b575d 100644
--- a/test/btree_test.c
+++ b/test/btree_test.c
@@ -172,11 +172,8 @@ stress(const unsigned test_num, const size_t n_elems)
   }
 
   // Ensure begin iterator is end on empty tree
-  ZixBTreeIter* ti  = zix_btree_begin(t);
-  ZixBTreeIter* end = zix_btree_end(t);
-  if (!ti) {
-    return test_fail(t, "Failed to allocate iterator\n");
-  }
+  ZixBTreeIter ti  = zix_btree_begin(t);
+  ZixBTreeIter end = zix_btree_end(t);
 
   if (!zix_btree_iter_is_end(ti)) {
     return test_fail(t, "Begin iterator on empty tree is not end\n");
@@ -186,13 +183,6 @@ stress(const unsigned test_num, const size_t n_elems)
     return test_fail(t, "Begin and end of empty tree are not equal\n");
   }
 
-  zix_btree_iter_free(end);
-  zix_btree_iter_free(ti);
-
-  if (zix_btree_iter_copy(NULL)) {
-    return test_fail(t, "Copy of null iterator returned non-null\n");
-  }
-
   // Insert n_elems elements
   for (size_t i = 0; i < n_elems; ++i) {
     r = ith_elem(test_num, n_elems, i);
@@ -220,15 +210,6 @@ stress(const unsigned test_num, const size_t n_elems)
   if (zix_btree_iter_equals(ti, end)) {
     return test_fail(t, "Begin and end of non-empty tree are equal\n");
   }
-  zix_btree_iter_free(end);
-
-  // Ensure non-null iterator copying works
-  ZixBTreeIter* begin_copy = zix_btree_iter_copy(ti);
-  if (!zix_btree_iter_equals(ti, begin_copy)) {
-    return test_fail(t, "Iterator copy is not equal to original\n");
-  }
-  zix_btree_iter_free(begin_copy);
-  zix_btree_iter_free(ti);
 
   // Search for all elements
   for (size_t i = 0; i < n_elems; ++i) {
@@ -244,12 +225,6 @@ stress(const unsigned test_num, const size_t n_elems)
                        (uintptr_t)zix_btree_get(ti),
                        r);
     }
-
-    zix_btree_iter_free(ti);
-  }
-
-  if (zix_btree_lower_bound(NULL, (void*)r, &ti) != ZIX_STATUS_BAD_ARG) {
-    return test_fail(t, "Lower bound on NULL tree succeeded\n");
   }
 
   // Find the lower bound of all elements and ensure it's exact
@@ -273,8 +248,6 @@ stress(const unsigned test_num, const size_t n_elems)
                        (uintptr_t)zix_btree_get(ti),
                        r);
     }
-
-    zix_btree_iter_free(ti);
   }
 
   // Search for elements that don't exist
@@ -289,7 +262,7 @@ stress(const unsigned test_num, const size_t n_elems)
   size_t    i    = 0;
   uintptr_t last = 0;
   for (ti = zix_btree_begin(t); !zix_btree_iter_is_end(ti);
-       zix_btree_iter_increment(ti), ++i) {
+       zix_btree_iter_increment(&ti), ++i) {
     const uintptr_t iter_data = (uintptr_t)zix_btree_get(ti);
     if (iter_data < last) {
       return test_fail(t,
@@ -301,7 +274,7 @@ stress(const unsigned test_num, const size_t n_elems)
     }
     last = iter_data;
   }
-  zix_btree_iter_free(ti);
+
   if (i != n_elems) {
     return test_fail(t,
                      "Iteration stopped at %" PRIuPTR "/%" PRIuPTR
@@ -324,18 +297,17 @@ stress(const unsigned test_num, const size_t n_elems)
     return test_fail(t, "Find %" PRIuPTR " failed\n", (uintptr_t)r);
   }
   last = (uintptr_t)zix_btree_get(ti);
-  zix_btree_iter_increment(ti);
-  for (i = 1; !zix_btree_iter_is_end(ti); zix_btree_iter_increment(ti), ++i) {
+  zix_btree_iter_increment(&ti);
+  for (i = 1; !zix_btree_iter_is_end(ti); zix_btree_iter_increment(&ti), ++i) {
     if ((uintptr_t)zix_btree_get(ti) == last) {
       return test_fail(
         t, "Duplicate element @ %" PRIuPTR " %" PRIuPTR "\n", i, last);
     }
     last = (uintptr_t)zix_btree_get(ti);
   }
-  zix_btree_iter_free(ti);
 
   // Delete all elements
-  ZixBTreeIter* next = NULL;
+  ZixBTreeIter next = zix_btree_end_iter;
   for (size_t e = 0; e < n_elems; e++) {
     r = ith_elem(test_num, n_elems, e);
 
@@ -363,8 +335,6 @@ stress(const unsigned test_num, const size_t n_elems)
       }
     }
   }
-  zix_btree_iter_free(next);
-  next = NULL;
 
   // Ensure the tree is empty
   if (zix_btree_size(t) != 0) {
@@ -388,8 +358,6 @@ stress(const unsigned test_num, const size_t n_elems)
         t, "Non-existant deletion of %" PRIuPTR " succeeded\n", (uintptr_t)r);
     }
   }
-  zix_btree_iter_free(next);
-  next = NULL;
 
   // Ensure tree size is still correct
   if (zix_btree_size(t) != n_elems) {
@@ -425,8 +393,6 @@ stress(const unsigned test_num, const size_t n_elems)
       }
     }
   }
-  zix_btree_iter_free(next);
-  next = NULL;
 
   // Check tree size
   if (zix_btree_size(t) != n_elems - (n_elems / 4)) {
@@ -446,8 +412,6 @@ stress(const unsigned test_num, const size_t n_elems)
       return test_fail(t, "Error deleting %" PRIuPTR "\n", (uintptr_t)r);
     }
   }
-  zix_btree_iter_free(next);
-  next = NULL;
 
   // Delete all remaining elements via next iterator
   next                 = zix_btree_begin(t);
@@ -477,10 +441,8 @@ stress(const unsigned test_num, const size_t n_elems)
 
     last_value = removed;
   }
-  assert(!next || zix_btree_size(t) == 0);
-  zix_btree_iter_free(next);
-  next = NULL;
 
+  assert(zix_btree_size(t) == 0);
   zix_btree_free(t, NULL);
 
   // Test lower_bound with wildcard comparator
@@ -526,8 +488,6 @@ stress(const unsigned test_num, const size_t n_elems)
       t, "Wildcard lower bound %" PRIuPTR " != %" PRIuPTR "\n", iter_data, cut);
   }
 
-  zix_btree_iter_free(ti);
-
   // Find lower bound of value past end
   const uintptr_t max = (uintptr_t)-1;
   if (zix_btree_lower_bound(t, (void*)max, &ti)) {
@@ -538,7 +498,6 @@ stress(const unsigned test_num, const size_t n_elems)
     return test_fail(t, "Lower bound of maximum value is not end\n");
   }
 
-  zix_btree_iter_free(ti);
   zix_btree_free(t, NULL);
 
   return EXIT_SUCCESS;