Allow ZixBTreeIter to be allocated on the stack

3 files changed, 55 insertions, 41 deletions

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";
 }