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.

size_t zix_btree_size(const ZixBTree *t)

Return the number of elements in t

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.