2.4.1 BTree

struct ZixBTreeIter

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.

ZixBTreeNode *nodes[ZIX_BTREE_MAX_HEIGHT]

Node stack.

uint16_t indexes[ZIX_BTREE_MAX_HEIGHT]

Index stack.

uint16_t level

Current level.

typedef struct ZixBTreeImpl ZixBTree

A B-Tree.

typedef struct ZixBTreeNodeImpl ZixBTreeNode

A B-Tree node (opaque)

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.

const ZixBTreeIter zix_btree_end_iter

A static end iterator for convenience.

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_user_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_user_data – Opaque pointer to pass to destroy.

void zix_btree_clear(ZixBTree *t, ZixBTreeDestroyFunc destroy, const void *destroy_user_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_user_data – Opaque pointer to pass to destroy.

size_t zix_btree_size(const ZixBTree *t)

Return the number of elements in t

ZixStatus zix_btree_insert(ZixBTree *t, void *e)

Insert the element e into t

ZixStatus zix_btree_remove(ZixBTree *t, const void *e, void **out, ZixBTreeIter *next)

Remove the value e from t.

Parameters:
  • t – Tree to remove from.

  • e – Value to remove.

  • out – Set to point to the removed pointer (which may not equal e).

  • next – On successful return, set to point at the value that immediately followed e.

ZixStatus zix_btree_find(const ZixBTree *t, const void *e, ZixBTreeIter *ti)

Set ti to an element exactly equal to e in t.

If no such item exists, ti is set to the end.

ZixStatus zix_btree_lower_bound(const ZixBTree *t, ZixBTreeCompareFunc compare_key, const void *compare_key_user_data, const void *key, 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.

void *zix_btree_get(ZixBTreeIter ti)

Return the data at the given position in the tree.

ZixBTreeIter zix_btree_begin(const ZixBTree *t)

Return an iterator to the first (smallest) element in t

ZixBTreeIter zix_btree_end(const ZixBTree *t)

Return an iterator to the end of t (one past the last element)

bool zix_btree_iter_equals(ZixBTreeIter lhs, ZixBTreeIter rhs)

Return true iff lhs is equal to rhs

bool zix_btree_iter_is_end(const ZixBTreeIter i)

Return true iff i is an iterator at the end of a tree.

ZixStatus zix_btree_iter_increment(ZixBTreeIter *i)

Increment i to point to the next element in the tree.

ZixBTreeIter zix_btree_iter_next(ZixBTreeIter iter)

Return an iterator one past iter

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.