B-tree
API
include <ds/btree.h>
Handle
Functions
-
struct btree *btree_create(size_t key_size, size_t val_size)
Initializes a btree.
Every call to btree_create must have a matching call to btree_destroy to release the managed memory.
- Parameters:
key_size – Size of each key.
val_size – Size of each value.
- Returns:
Handle to the btree.
-
void btree_destroy(struct btree *p)
Deallocates the memory managed by a B-tree created with btree_create.
- Parameters:
p – Handle to the B-tree.
-
void btree_insert(struct btree **p, void *key, void *value, int (*cmp)(void*, void*))
Inserts an entry into the tree.
Finds the appropriate position and inserts the key-value pair while preserving the B-tree properties. The comparator receives a pointer to the given key, and a pointer to the key being compared, respectively. May update the root pointer.
- Parameters:
p – Handle to the root of the tree.
key – Handle to the key to insert.
value – Handle to the value to insert.
cmp – Insertion comparator.
-
data *btree_search(struct btree *p, data *key, int (*cmp)(data*, data*))
Finds a key on the tree and returns a handle to its value, if it exists.
Finds the value associated with the given key, if it exists. Returns null otherwise. The comparator receives a pointer to the given key, and a pointer to the key being compared, respectively.
- Parameters:
p – Handle to the tree.
key – Handle to the key to search for.
cmp – Search comparator.
-
bool btree_remove(struct btree **p, void *key, int (*cmp)(void*, void*))
Finds and deletes an entry from the tree.
Deletes the given key and its associated value from the tree, if it exists. Does not change the tree if the key doesn’t exist. The comparator receives a pointer to the given key, and a pointer to the key being compared, respectively.
- Parameters:
p – Handle to the root of the tree.
key – Handle to the key to delete.
cmp – Deletion comparator.
- Returns:
Whether or not the value was on the original tree.
Todo
Document internals.