Bst
Ordered binary search tree of void *. Insert, find, and remove use a qsort-style cmp; remove splices one node and does not prune a subtree (use binarytree to attach children by hand).
Usage#
Initialize with a comparator and an optional payload destructor. The comparator receives the stored pointers. Pass NULL for the destructor when the tree does not own the payloads.
int compare_int(const void *a, const void *b) {
int x = *(const int *)a, y = *(const int *)b;
return (x > y) - (x < y);
}
Bst tree;
if (bst_init(&tree, compare_int, NULL) == 0) {
int value = 42;
if (bst_insert(&tree, &value) == 0) {
int key = 42;
void *found = bst_find(&tree, &key);
/* found == &value */
(void)found;
}
bst_destroy(&tree);
}
bst_destroy frees the nodes and, when a destructor was given, calls it on payloads still in the tree. It does not free the Bst handle. Stored keys must not change in any way cmp observes. The tree is not balanced, so inserting keys in order makes a later search walk every node.
Structs#
Bst#
typedef struct {
BinTree tree;
int (*cmp)(const void *a, const void *b);
} Bst;
cmp is required. It returns <0 when a < b, 0 when equal, and >0 when a > b.
Functions#
bst_init#
Initializes an empty tree. Returns 0 on success and -1 if tree or cmp is NULL. Failure leaves the handle unchanged. Do not initialize a live tree: the existing nodes are dropped and not freed.
int bst_init(Bst *tree, int (*cmp)(const void *a, const void *b),
void (*destroy)(void *data));bst_destroy#
Frees the nodes through bintree_destroy. Payloads are passed to destroy only when that callback was set. Does not free the Bst handle. A NULL handle is ignored, and destroying an already destroyed tree is safe.
void bst_destroy(Bst *tree);bst_insert#
Inserts data as a leaf. Returns 0 when inserted, 1 when cmp reports a duplicate, and -1 if tree or cmp is NULL or the node cannot be created. A duplicate or a failed insert leaves the tree unchanged and leaves the payload with the caller.
int bst_insert(Bst *tree, void *data);bst_find#
Returns the stored payload that compares equal to key. Returns NULL if tree or cmp is NULL, if no node matches, or if the stored payload is NULL.
void *bst_find(const Bst *tree, const void *key);bst_remove#
Finds the node matching *data, splices out one node, and writes that payload through data. Does not call destroy. Returns 0 on success. Returns -1 if the node is missing or an argument is invalid, and does not write through data on failure.
int bst_remove(Bst *tree, void **data);bst_min / bst_max#
Return the leftmost or rightmost payload. Return NULL if tree is NULL, the tree is empty, or that payload is NULL.
void *bst_min(const Bst *tree);
void *bst_max(const Bst *tree);Macros#
#define bst_size(t) ((t)->tree.size)
#define bst_root(t) ((t)->tree.root)
Walk in order with bintree_traverse(&t.tree, bst_root(&t), BINTREE_INORDER, visitor).