// Copyright 2011-2022 David Robillard // SPDX-License-Identifier: ISC #ifndef ZIX_BTREE_H #define ZIX_BTREE_H #include "zix/allocator.h" #include "zix/attributes.h" #include "zix/status.h" #include #include #include ZIX_BEGIN_DECLS /** @defgroup zix_btree BTree @ingroup zix_data_structures @{ */ /** 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; /// A B-Tree node (opaque) typedef struct ZixBTreeNodeImpl ZixBTreeNode; /// Function for comparing two B-Tree elements typedef int (*ZixBTreeCompareFunc)(const void* ZIX_UNSPECIFIED a, const void* ZIX_UNSPECIFIED b, const void* ZIX_UNSPECIFIED user_data); /// Function to destroy a B-Tree element typedef void (*ZixBTreeDestroyFunc)(void* ZIX_UNSPECIFIED ptr, const void* ZIX_UNSPECIFIED user_data); /** An iterator over a B-Tree. 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 { ZixBTreeNode* ZIX_NULLABLE nodes[ZIX_BTREE_MAX_HEIGHT]; ///< Node stack uint16_t indexes[ZIX_BTREE_MAX_HEIGHT]; ///< Index stack uint16_t level; ///< Current level } 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. The given comparator must be a total ordering and is used to internally organize the tree and look for values exactly. Searching can be done with a custom comparator that supports wildcards, see zix_btree_lower_bound() for details. */ ZIX_API ZixBTree* ZIX_ALLOCATED zix_btree_new(ZixAllocator* ZIX_NULLABLE allocator, ZixBTreeCompareFunc ZIX_NONNULL cmp, const void* ZIX_UNSPECIFIED cmp_data); /** Free `t` and all the nodes it contains. @param t The tree to free. @param destroy Function to call once for every value in the tree. This can be used to free values if they are dynamically allocated. @param destroy_user_data Opaque pointer to pass to `destroy`. */ ZIX_API void zix_btree_free(ZixBTree* ZIX_NULLABLE t, ZixBTreeDestroyFunc ZIX_NULLABLE destroy, const void* ZIX_NULLABLE destroy_user_data); /** Clear everything from `t`, leaving it empty. @param t The tree to clear. @param destroy Function called exactly once for every value in the tree, just before that value is removed from the tree. @param destroy_user_data Opaque pointer to pass to `destroy`. */ ZIX_API void zix_btree_clear(ZixBTree* ZIX_NONNULL t, ZixBTreeDestroyFunc ZIX_NULLABLE destroy, const void* ZIX_NULLABLE destroy_user_data); /// Return the number of elements in `t` ZIX_PURE_API size_t zix_btree_size(const ZixBTree* ZIX_NONNULL t); /// Insert the element `e` into `t` ZIX_API ZixStatus zix_btree_insert(ZixBTree* ZIX_NONNULL t, void* ZIX_UNSPECIFIED e); /** Remove the value `e` from `t`. @param t Tree to remove from. @param e Value to remove. @param out Set to point to the removed pointer (which may not equal `e`). @param next On successful return, set to point at the value that immediately followed `e`. */ ZIX_API ZixStatus zix_btree_remove(ZixBTree* ZIX_NONNULL t, const void* ZIX_UNSPECIFIED e, void* ZIX_UNSPECIFIED* ZIX_NONNULL out, ZixBTreeIter* ZIX_NONNULL next); /** Set `ti` to an element exactly equal to `e` in `t`. If no such item exists, `ti` is set to the end. */ ZIX_API ZixStatus zix_btree_find(const ZixBTree* ZIX_NONNULL t, const void* ZIX_UNSPECIFIED e, ZixBTreeIter* ZIX_NONNULL ti); /** Set `ti` to the smallest element in `t` that is not less than `e`. The given comparator must be compatible with the tree comparator, that is, any two values must have the same ordering according to both. Within this constraint, it may implement fuzzier searching by handling special search key values, for example with wildcards. If the search key `e` compares equal to many values in the tree, then `ti` will be set to the least such element. The comparator is always called with an actual value in the tree as the first argument, and `key` as the second argument. */ ZIX_API ZixStatus zix_btree_lower_bound(const ZixBTree* ZIX_NONNULL t, ZixBTreeCompareFunc ZIX_NULLABLE compare_key, const void* ZIX_NULLABLE compare_key_user_data, const void* ZIX_UNSPECIFIED key, ZixBTreeIter* ZIX_NONNULL ti); /// Return the data at the given position in the tree ZIX_PURE_API void* ZIX_UNSPECIFIED zix_btree_get(ZixBTreeIter ti); /// Return an iterator to the first (smallest) element in `t` ZIX_PURE_API ZixBTreeIter zix_btree_begin(const ZixBTree* ZIX_NONNULL t); /// Return an iterator to the end of `t` (one past the last element) ZIX_CONST_API ZixBTreeIter zix_btree_end(const ZixBTree* ZIX_NULLABLE t); /// Return true iff `lhs` is equal to `rhs` ZIX_CONST_API bool zix_btree_iter_equals(ZixBTreeIter lhs, ZixBTreeIter rhs); /// 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 ZixStatus zix_btree_iter_increment(ZixBTreeIter* ZIX_NONNULL i); /// Return an iterator one past `iter` ZIX_API ZixBTreeIter zix_btree_iter_next(ZixBTreeIter iter); /** @} */ ZIX_END_DECLS #endif /* ZIX_BTREE_H */