This module implements interfaces that let you work with a simple binary search tree.
A new BST instance is created via u_bst_new. New nodes are added one after another by calling u_bst_push:
size_t i; char key[KEY_SZ]; u_bst_t *bst = NULL; // Create the root container dbg_err_if (u_bst_new(U_BST_OPT_NONE, &bst)); // Add random keys referencing dummy NULL values for (i = 0; i < NELEMS; i++) { (void) u_snprintf(key, sizeof key, "%12.12d", rand()); dbg_err_if (u_bst_push(bst, key, NULL)); }
By default keys are strings -- of which the BST holds a private copy -- and values are pointers to any data type, under the user's complete responsibility. If you need to handle other key or value types, or different ownership logics, use the u_bst_set_* family of functions.
Typically, once the tree is loaded, specific key values are searched, via u_bst_search, to retrieve their associated values (e.g. symbol table lookups), like in the following:
... dbg_err_if (u_bst_push(symtbl, "HAVE_LIBU_BST", "0")); ... if ((node = u_bst_search(symtbl, "HAVE_LIBU_BST")) == NULL || strcmp((const char *) u_bst_node_val(node), "1")) { u_con("HAVE_LIBU_BST undefined."); return ~0; }
When you are done, the resources allocated to the BST can be reclaimed back with u_bst_free:
u_bst_free(bst);
Typedefs | |
typedef struct u_bst_s | u_bst_t |
The binary search tree type. | |
typedef struct u_bst_node_s | u_bst_node_t |
The binary search tree node type. | |
Enumerations | |
enum | u_bst_type_t { U_BST_TYPE_STRING, U_BST_TYPE_OPAQUE, U_BST_TYPE_PTR } |
Available types for BST containers. More... | |
enum | u_bst_rot_t { U_BST_ROT_LEFT, U_BST_ROT_RIGHT } |
BST rotation types. More... | |
enum | u_bst_opt_t { , U_BST_OPT_PUSH_TOP = (1 << 0), U_BST_OPT_PUSH_BOTTOM = (1 << 1), U_BST_OPT_RANDOMIZED = (1 << 2) } |
BST customization options. More... | |
Functions | |
int | u_bst_new (int opts, u_bst_t **pbst) |
Create a new u_bst_t object. | |
void | u_bst_free (u_bst_t *bst) |
Destroy an u_bst_t object. | |
ssize_t | u_bst_count (u_bst_t *bst) |
Count elements stored in the BST. | |
u_bst_node_t * | u_bst_search (u_bst_t *bst, const void *key) |
Search for a node matching a given key. | |
int | u_bst_push (u_bst_t *bst, const void *key, const void *val) |
Insert a new node into the BST. | |
int | u_bst_foreach (u_bst_t *bst, void(*cb)(u_bst_node_t *, void *), void *cb_args) |
In-order walk the BST invoking a function on each traversed node. | |
u_bst_node_t * | u_bst_rotate (u_bst_node_t *pivot, u_bst_rot_t dir) |
Do left/right rotation of the BST around a given pivot node. | |
int | u_bst_empty (u_bst_t *bst) |
Tell if the supplied BST is empty. | |
u_bst_node_t * | u_bst_find_nth (u_bst_t *bst, size_t n) |
Find the n-th element in the BST. | |
int | u_bst_delete (u_bst_t *bst, const void *key) |
Evict a node from the BST given its key. | |
int | u_bst_balance (u_bst_t *bst) |
Re-balance a BST internal structure. | |
int | u_bst_set_cmp (u_bst_t *bst, int(*f)(const void *, const void *)) |
Set custom key comparison function. | |
int | u_bst_set_keyattr (u_bst_t *bst, u_bst_type_t kt, size_t ks) |
Set custom key attributes on the supplied BST. | |
int | u_bst_set_valattr (u_bst_t *bst, u_bst_type_t vt, size_t vs) |
Set custom value attributes on the supplied BST. | |
int | u_bst_set_keyfree (u_bst_t *bst, void(*f)(void *)) |
Set custom key free function. | |
int | u_bst_set_valfree (u_bst_t *bst, void(*f)(void *)) |
Set custom value free function. | |
const void * | u_bst_node_key (u_bst_node_t *node) |
Node's key getter. | |
const void * | u_bst_node_val (u_bst_node_t *node) |
Node's value getter. | |
ssize_t | u_bst_node_count (u_bst_node_t *node) |
Return the number of elements in the subtree rooted at node . |
enum u_bst_opt_t |
enum u_bst_rot_t |
enum u_bst_type_t |
int u_bst_balance | ( | u_bst_t * | bst | ) |
Try to rebalance the supplied bst
internal structure by doing the needed promote/rotate dance
bst | an u_bst_t object handler |
0 | on success | |
-1 | on error |
Definition at line 334 of file srcs/toolbox/bst.c.
ssize_t u_bst_count | ( | u_bst_t * | bst | ) |
Count the number of nodes actually stored in the supplied bst
bst | an u_bst_t object handler |
-1
in case an invalid handler was supplied Definition at line 288 of file srcs/toolbox/bst.c.
int u_bst_delete | ( | u_bst_t * | bst, | |
const void * | key | |||
) |
Evict the first node matching the supplied key key
from bst
bst | an u_bst_t object handler | |
key | the key to match for eviction |
0 | on success | |
~0 | if key was not found |
Definition at line 227 of file srcs/toolbox/bst.c.
int u_bst_empty | ( | u_bst_t * | bst | ) |
Tell if the supplied u_bst_t object bst
is empty
bst | an u_bst_t object handler |
Definition at line 561 of file srcs/toolbox/bst.c.
u_bst_node_t * u_bst_find_nth | ( | u_bst_t * | bst, | |
size_t | n | |||
) |
Find the n-th (according to the comparison function --
bst | an u_bst_t object handler | |
n | the ordinal position of the element that must be retrieved |
NULL
in case n
is out of current BST bounds Definition at line 271 of file srcs/toolbox/bst.c.
int u_bst_foreach | ( | u_bst_t * | bst, | |
void(*)(u_bst_node_t *, void *) | cb, | |||
void * | cb_args | |||
) |
In-order walk the BST handled by bst
, invoking the supplied function cb
with optional arguments cb_args
at each traversed node.
bst | an u_bst_t object handler | |
cb | the callback function to invoke on each node | |
cb_args | auxiliary arguments (aside from the BST node handler, which is automatically feeded) to be given to cb |
0 | on success | |
~0 | if bst or cb parameters are invalid |
Definition at line 312 of file srcs/toolbox/bst.c.
void u_bst_free | ( | u_bst_t * | bst | ) |
Destroy the (previously allocated) u_bst_t object bst
bst | handler of the object that needs to be destroyed |
Definition at line 174 of file srcs/toolbox/bst.c.
References u_free().
int u_bst_new | ( | int | opts, | |
u_bst_t ** | pbst | |||
) |
Create a new u_bst_t object with given opts
options
opts | bitwise inclusive OR of U_BST_OPTS_* values | |
pbst | handler of the newly created u_bst_t object as a result argument |
0 | on success | |
~0 | on error |
Definition at line 136 of file srcs/toolbox/bst.c.
References U_BST_OPT_RANDOMIZED, U_BST_TYPE_PTR, U_BST_TYPE_STRING, and u_malloc().
ssize_t u_bst_node_count | ( | u_bst_node_t * | node | ) |
Return the number of elements in the subtree rooted at node
node | node's handler |
node
or -1 on error Definition at line 545 of file srcs/toolbox/bst.c.
const void * u_bst_node_key | ( | u_bst_node_t * | node | ) |
Return the key stored in the given node
node | the node whose key needs to be retrieved |
NULL
in case node
was NULL
Definition at line 513 of file srcs/toolbox/bst.c.
const void * u_bst_node_val | ( | u_bst_node_t * | node | ) |
Return the value stored in the given node
node | the node whose value needs to be retrieved |
NULL
in case node
was NULL
Definition at line 529 of file srcs/toolbox/bst.c.
int u_bst_push | ( | u_bst_t * | bst, | |
const void * | key, | |||
const void * | val | |||
) |
Insert a new node with key key
and value val
into the BST headed by bst
. The new node will be (initially) pushed to the bottom of the tree, unless U_BST_OPT_PUSH_TOP (in which case the node is injected on the top) or U_BST_OPT_RANDOMIZED (the injection point is chosen at random) have been supplied at bst
creation.
bst | an u_bst_t object handler | |
key | the key of the node that will be inserted | |
val | value stick to the inserted node |
0 | on success | |
~0 | on error |
Definition at line 201 of file srcs/toolbox/bst.c.
References U_BST_OPT_PUSH_TOP, and U_BST_OPT_RANDOMIZED.
u_bst_node_t * u_bst_rotate | ( | u_bst_node_t * | pivot, | |
u_bst_rot_t | dir | |||
) |
Rotate -- left or right depending on dir
-- the bst
around the pivot
node.
pivot | the node in the BST around which the BST is rotated | |
dir | one of U_BST_ROT_LEFT or U_BST_ROT_RIGHT |
pivot
, depending on dir
. Definition at line 355 of file srcs/toolbox/bst.c.
References U_BST_ROT_LEFT, and U_BST_ROT_RIGHT.
u_bst_node_t * u_bst_search | ( | u_bst_t * | bst, | |
const void * | key | |||
) |
Search the u_bst_t object bst
for the first node matching the supplied key key
bst | an u_bst_t object handler | |
key | the key to match |
NULL
in case no matching node was found Definition at line 251 of file srcs/toolbox/bst.c.
int u_bst_set_cmp | ( | u_bst_t * | bst, | |
int(*)(const void *, const void *) | f | |||
) |
Set a custom key comparison function f
for the u_bst_t object bst
bst | an u_bst_t object handler | |
f | custom compare function |
0 | on success | |
~0 | on error (i.e. invalid parameter) |
Definition at line 452 of file srcs/toolbox/bst.c.
int u_bst_set_keyattr | ( | u_bst_t * | bst, | |
u_bst_type_t | kt, | |||
size_t | ks | |||
) |
Set (global) custom key attributes on the given u_bst_t object.
bst | an u_bst_t object handler | |
kt | type of the key, one of U_BST_TYPE_STRING, U_BST_TYPE_PTR or U_BST_TYPE_OPAQUE | |
ks | size of the key (needed for U_BST_TYPE_OPAQUE types) |
0 | on success | |
~0 | on error (i.e. invalid parameter) |
Definition at line 400 of file srcs/toolbox/bst.c.
References U_BST_TYPE_OPAQUE.
int u_bst_set_keyfree | ( | u_bst_t * | bst, | |
void(*)(void *) | f | |||
) |
Set a custom key free function f
for the u_bst_t object bst
bst | an u_bst_t object handler | |
f | custom key free function |
0 | on success | |
~0 | on error (i.e. invalid parameter) |
Definition at line 473 of file srcs/toolbox/bst.c.
int u_bst_set_valattr | ( | u_bst_t * | bst, | |
u_bst_type_t | vt, | |||
size_t | vs | |||
) |
Set (global) custom value attributes on the given u_bst_t object.
bst | an u_bst_t object handler | |
vt | type of the value, one of U_BST_TYPE_STRING, U_BST_TYPE_PTR or U_BST_TYPE_OPAQUE | |
vs | size of the value (needed for U_BST_TYPE_OPAQUE types) |
0 | on success | |
~0 | on error (i.e. invalid parameter) |
Definition at line 427 of file srcs/toolbox/bst.c.
References U_BST_TYPE_OPAQUE.
int u_bst_set_valfree | ( | u_bst_t * | bst, | |
void(*)(void *) | f | |||
) |
Set a custom value free function f
for the u_bst_t object bst
bst | an u_bst_t object handler | |
f | custom value free function |
0 | on success | |
~0 | on error (i.e. invalid parameter) |
Definition at line 494 of file srcs/toolbox/bst.c.