diff options
Diffstat (limited to 'include/zix/btree.h')
| -rw-r--r-- | include/zix/btree.h | 90 |
1 files changed, 50 insertions, 40 deletions
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); - /** @} @} |