diff options
Diffstat (limited to 'include')
| -rw-r--r-- | include/zix/btree.h | 38 |
1 files changed, 31 insertions, 7 deletions
diff --git a/include/zix/btree.h b/include/zix/btree.h index 5212ec7..d19da3c 100644 --- a/include/zix/btree.h +++ b/include/zix/btree.h @@ -74,7 +74,15 @@ static const ZixBTreeIter zix_btree_end_iter = { {0u, 0u, 0u, 0u, 0u, 0u}, 0u}; -/// Create a new (empty) B-Tree +/** + 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); @@ -126,7 +134,7 @@ ZixStatus zix_btree_remove(ZixBTree* t, const void* e, void** out, ZixBTreeIter* next); /** - Set `ti` to an element equal to `e` in `t`. + Set `ti` to an element exactly equal to `e` in `t`. If no such item exists, `ti` is set to the end. */ @@ -137,15 +145,26 @@ 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`. - Wildcards are supported, so if the search key `e` compares equal to many - values in the tree, `ti` will be set to the least such element. The search - key `e` is always passed as the second argument to the comparator. + 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, const void* e, ZixBTreeIter* ti); +zix_btree_lower_bound(const ZixBTree* t, + ZixComparator compare_key, + const void* compare_key_user_data, + const void* key, + ZixBTreeIter* ti); -/// Return the data associated with the given tree item +/// Return the data at the given position in the tree ZIX_PURE_API void* zix_btree_get(ZixBTreeIter ti); @@ -177,6 +196,11 @@ ZIX_API ZixStatus zix_btree_iter_increment(ZixBTreeIter* i); +/// Return an iterator one past `iter` +ZIX_API +ZixBTreeIter +zix_btree_iter_next(ZixBTreeIter iter); + /** @} @} |