2.4.1.1 Setup¶
-
typedef struct ZixBTreeImpl
ZixBTree
¶ A B-Tree.
-
typedef int (*
ZixBTreeCompareFunc
)(const void *a, const void *b, const void *user_data)¶ Function for comparing two B-Tree elements.
-
typedef void (*
ZixBTreeDestroyFunc
)(void *ptr, const void *user_data)¶ Function to destroy a B-Tree element.
-
ZixBTree *
zix_btree_new
(ZixAllocator *allocator, ZixBTreeCompareFunc cmp, const void *cmp_data)¶ 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.
-
void
zix_btree_free
(ZixBTree *t, ZixBTreeDestroyFunc destroy, const void *destroy_data)¶ Free
t
and all the nodes it contains.- Parameters
t – The tree to free.
destroy – Function to call once for every value in the tree. This can be used to free values if they are dynamically allocated.
destroy_data – Opaque user data pointer to pass to
destroy
.
-
void
zix_btree_clear
(ZixBTree *t, ZixBTreeDestroyFunc destroy, const void *destroy_data)¶ Clear everything from
t
, leaving it empty.- Parameters
t – The tree to clear.
destroy – Function called exactly once for every value in the tree, just before that value is removed from the tree.
destroy_data – Opaque user data pointer to pass to
destroy
.
-
ZIX_BTREE_MAX_HEIGHT
¶ 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.