diff options
Diffstat (limited to 'src/zix/btree.h')
| -rw-r--r-- | src/zix/btree.h | 213 |
1 files changed, 213 insertions, 0 deletions
diff --git a/src/zix/btree.h b/src/zix/btree.h new file mode 100644 index 00000000..3576789c --- /dev/null +++ b/src/zix/btree.h @@ -0,0 +1,213 @@ +/* + Copyright 2011-2020 David Robillard <d@drobilla.net> + + Permission to use, copy, modify, and/or distribute this software for any + purpose with or without fee is hereby granted, provided that the above + copyright notice and this permission notice appear in all copies. + + THIS SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL WARRANTIES + WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF + MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR + ANY SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES + WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN + ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF + OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE. +*/ + +#ifndef ZIX_BTREE_H +#define ZIX_BTREE_H + +#include "zix/common.h" + +#include <stdbool.h> +#include <stddef.h> +#include <stdint.h> + +#ifdef __cplusplus +extern "C" { +#endif + +/** + @addtogroup zix + @{ + @name BTree + @{ +*/ + +/** + 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; + +/** + 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* 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. + + 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_btree_new(ZixComparator cmp, const void* cmp_data); + +/** + Free `t` and all the nodes it contains. + + @param destroy Function to call once for every value in the tree. This can + be used to free values if they are dynamically allocated. +*/ +ZIX_API +void +zix_btree_free(ZixBTree* t, ZixDestroyFunc destroy); + +/** + Clear everything from `t`, leaving it empty. + + @param destroy Function called exactly once for every value in the tree, + just before that value is removed from the tree. +*/ +ZIX_API +void +zix_btree_clear(ZixBTree* t, ZixDestroyFunc destroy); + +/// Return the number of elements in `t` +ZIX_PURE_API +size_t +zix_btree_size(const ZixBTree* t); + +/// Insert the element `e` into `t` +ZIX_API +ZixStatus +zix_btree_insert(ZixBTree* t, void* 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* t, const void* e, void** out, ZixBTreeIter* 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* t, const void* e, ZixBTreeIter* 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* t, + ZixComparator compare, + const void* compare_user_data, + const void* key, + ZixBTreeIter* ti); + +/// Return the data at the given position in the tree +ZIX_PURE_API +void* +zix_btree_get(ZixBTreeIter ti); + +/// Return an iterator to the first (smallest) element in `t` +ZIX_PURE_API +ZixBTreeIter +zix_btree_begin(const ZixBTree* t); + +/// Return an iterator to the end of `t` (one past the last element) +ZIX_CONST_API +ZixBTreeIter +zix_btree_end(const ZixBTree* t); + +/// Return true iff `lhs` is equal to `rhs` +ZIX_PURE_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* i); + +/// Return an iterator one past `iter` +ZIX_PURE_API +ZixBTreeIter +zix_btree_iter_next(ZixBTreeIter iter); + +/** + @} + @} +*/ + +#ifdef __cplusplus +} /* extern "C" */ +#endif + +#endif /* ZIX_BTREE_H */ |