Binary Search Tree

Overview

This module implements interfaces that let you work with a simple binary search tree.

Load

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.

Search

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;
    }

Termination

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`.

Enumeration Type Documentation

enum u_bst_opt_t

Enumerator:

U_BST_OPT_PUSH_TOP	New nodes added on BST top.
U_BST_OPT_PUSH_BOTTOM	New nodes added at BST bottom.
U_BST_OPT_RANDOMIZED	Operations are randomized.

Definition at line 45 of file bst.h.

enum u_bst_rot_t

Enumerator:

U_BST_ROT_LEFT	Left rotation.
U_BST_ROT_RIGHT	Right rotation.

Definition at line 39 of file bst.h.

enum u_bst_type_t

Enumerator:

U_BST_TYPE_STRING	String, i.e. NUL-terminated char array.
U_BST_TYPE_OPAQUE	Any type, given by its byte size.
U_BST_TYPE_PTR	Pointer type.

Definition at line 32 of file bst.h.

Function Documentation

int u_bst_balance ( u_bst_t * bst )

Try to rebalance the supplied bst internal structure by doing the needed promote/rotate dance

Parameters:

bst

an u_bst_t object handler

Return values:

	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

Parameters:

bst

an u_bst_t object handler

Returns:: the number of elements in BST, or -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

Parameters:

	bst	an u_bst_t object handler
	key	the key to match for eviction

Return values:

	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

Parameters:

bst

an u_bst_t object handler

Returns:: 1 if empty, 0 otherwise

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 --

See also:: u_bst_set_cmp) element in the BST.

Parameters:

	bst	an u_bst_t object handler
	n	the ordinal position of the element that must be retrieved

Returns:: the handler for the found node on success, 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.

Parameters:

	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`

Return values:

	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

Parameters:

bst

handler of the object that needs to be destroyed

Returns:: nothing

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

Parameters:

	opts	bitwise inclusive OR of U_BST_OPTS_* values
	pbst	handler of the newly created u_bst_t object as a result argument

Return values:

	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

Parameters:

node

node's handler

Returns:: the number of elements "under" 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

Parameters:

node

the node whose key needs to be retrieved

Returns:: the node's key or 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

Parameters:

node

the node whose value needs to be retrieved

Returns:: the node's value or 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.

Parameters:

	bst	an u_bst_t object handler
	key	the key of the node that will be inserted
	val	value stick to the inserted node

Return values:

	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.

Parameters:

	pivot	the node in the BST around which the BST is rotated
	dir	one of U_BST_ROT_LEFT or U_BST_ROT_RIGHT

Returns:: the new parent node, i.e the left or right child of the 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

Parameters:

	bst	an u_bst_t object handler
	key	the key to match

Returns:: the handler for the found node on success, 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

Parameters:

	bst	an u_bst_t object handler
	f	custom compare function

Return values:

	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.

Parameters:

	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)

Return values:

	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

Parameters:

	bst	an u_bst_t object handler
	f	custom key free function

Return values:

	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.

Parameters:

	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)

Return values:

	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

Parameters:

	bst	an u_bst_t object handler
	f	custom value free function

Return values:

	0	on success
	~0	on error (i.e. invalid parameter)

Definition at line 494 of file srcs/toolbox/bst.c.

Binary Search Tree

Overview

Load

Search

Termination

Typedefs

Enumerations

Functions

Enumeration Type Documentation

Function Documentation