rbtree.c File Reference

Red/Black tree. More...

Classes
struct	rbtree_node_t
	Stores information of a node. More...
struct	rbtree_t
	Stores information of a rbtree. More...
struct	rbtree_iter_t
	Stores information for iterating a rbtree. More...

Functions
rbtree_node_t *	rbtree_node_alloc (void)
	Allocate memory for a node. More...
rbtree_node_t *	rbtree_node_init (rbtree_node_t *node, void *value)
	Initializes the already allocated node. More...
rbtree_node_t *	rbtree_node_create (void *value)
	Allocate memory for a node and sets its value. More...
void *	rbtree_node_get_value (rbtree_node_t *node)
	Provides access to the value associated to a node. More...
void	rbtree_node_dealloc (rbtree_node_t *node)
	Deallocate a node. More...
static int	rbtree_node_is_red (const rbtree_node_t *node)
	Checks if the node is red. More...
static rbtree_node_t *	rbtree_node_rotate (rbtree_node_t *node, int dir)
	Performs a node rotation. More...
static rbtree_node_t *	rbtree_node_rotate2 (rbtree_node_t *node, int dir)
	Performs a double rotation. More...
static int	rbtree_tree_node_cmp_ptr_cb (rbtree_t *tree, rbtree_node_t *a, rbtree_node_t *b)
	Peforms a comparison between the pointers of two elements. More...
static void	rbtree_tree_node_dealloc_cb (rbtree_t *tree, rbtree_node_t *node)
	Default deallocation callback. More...
rbtree_t *	rbtree_tree_alloc (void)
	Allocate memory for a tree. More...
rbtree_t *	rbtree_tree_init (rbtree_t *tree, rbtree_tree_node_cmp_f node_cmp_cb)
	Initializes the tree. More...
rbtree_t *	rbtree_tree_create (rbtree_tree_node_cmp_f node_cb)
	Allocate memory for a tree and sets the function used to compare nodes. More...
void	rbtree_tree_dealloc (rbtree_t *tree, rbtree_tree_node_f node_cb)
	Deallocate a node. More...
void *	rbtree_tree_find (rbtree_t *tree, void *value)
	Searches the node inside the tree with the given value. More...
void *	rbtree_tree_find_by_value (rbtree_t *tree, rbtree_tree_cmp_f cmp_fun, void *value)
	Searches the node inside the tree with the given value. More...
int	rbtree_tree_insert (rbtree_t *tree, void *value)
	Interts the value inside the tree. More...
int	rbtree_tree_insert_node (rbtree_t *tree, rbtree_node_t *node)
	Interts the value inside the tree. More...
int	rbtree_tree_remove_with_cb (rbtree_t *tree, void *value, rbtree_tree_node_f node_cb)
	Removes the value from the tree. More...
int	rbtree_tree_remove (rbtree_t *tree, void *value)
	Removes the value from the given tree. More...
unsigned int	rbtree_tree_size (rbtree_t *tree)
	Returns the size of the tree. More...
rbtree_iter_t *	rbtree_iter_alloc (void)
	Allocate the memory for the iterator. More...
rbtree_iter_t *	rbtree_iter_init (rbtree_iter_t *iter)
	Deallocate the memory for the iterator. More...
rbtree_iter_t *	rbtree_iter_create (void)
	Allocate the memory for the iterator and initializes it. More...
void	rbtree_iter_dealloc (rbtree_iter_t *iter)
	Deallocate the memory for the iterator. More...
static void *	rbtree_iter_start (rbtree_iter_t *iter, rbtree_t *tree, int dir)
	Internal function, init traversal object, dir determines whether to begin traversal at the smallest or largest valued node. More...
static void *	rbtree_iter_move (rbtree_iter_t *iter, int dir)
	Traverse a red black tree in the user-specified direction (0 asc, 1 desc) More...
void *	rbtree_iter_first (rbtree_iter_t *iter, rbtree_t *tree)
	Initializes the iterator the the first element of the tree. More...
void *	rbtree_iter_last (rbtree_iter_t *iter, rbtree_t *tree)
	Initializes the iterator the the last element of the tree. More...
void *	rbtree_iter_next (rbtree_iter_t *iter)
	Moves the iterator to the next element. More...
void *	rbtree_iter_prev (rbtree_iter_t *iter)
	Moves the iterator to the previous element. More...
int	rbtree_tree_test (rbtree_t *tree, rbtree_node_t *root)
	Checks the tree. More...
static void	rbtree_tree_print_iter (rbtree_t *tree, rbtree_node_t *node, rbtree_tree_node_f fun)
	Prints the tree using a user-defined function. More...
void	rbtree_tree_print (rbtree_t *tree, rbtree_tree_node_f fun)
	Prints the tree using the provided callback. More...

Detailed Description

Red/Black tree.

Copyright

(c) 2014-2024 This file is distributed under the MIT License. See LICENSE.md for details.

Function Documentation

rbtree_iter_alloc()

rbtree_iter_t* rbtree_iter_alloc

(

void

)

Allocate the memory for the iterator.

Returns

Pointer to the allocated iterator.

rbtree_iter_create()

rbtree_iter_t* rbtree_iter_create

(

void

)

Allocate the memory for the iterator and initializes it.

Returns

Pointer to the allocated iterator.

rbtree_iter_dealloc()

void rbtree_iter_dealloc

(

rbtree_iter_t *

iter

)

Deallocate the memory for the iterator.

Parameters

iter	Pointer to the allocated iterator.

rbtree_iter_first()

void* rbtree_iter_first	(	rbtree_iter_t *	iter,
		rbtree_t *	tree
	)

Initializes the iterator the the first element of the tree.

Parameters

iter	The iterator we want to initialize.
tree	The tree.

Returns

Pointer to the first value of the tree.

rbtree_iter_init()

rbtree_iter_t* rbtree_iter_init

(

rbtree_iter_t *

iter

)

Deallocate the memory for the iterator.

Parameters

iter	Pointer to the allocated iterator.

Returns

Pointer to the iterator itself.

rbtree_iter_last()

void* rbtree_iter_last	(	rbtree_iter_t *	iter,
		rbtree_t *	tree
	)

Initializes the iterator the the last element of the tree.

Parameters

iter	The iterator we want to initialize.
tree	The tree.

Returns

Pointer to the last value of the tree.

rbtree_iter_move()

static void* rbtree_iter_move ( rbtree_iter_t *  iter, int  dir  )

static

Traverse a red black tree in the user-specified direction (0 asc, 1 desc)

Parameters

iter	the iterator.
dir	the direction.

Returns

result of the iteration.

rbtree_iter_next()

void* rbtree_iter_next

(

rbtree_iter_t *

iter

)

Moves the iterator to the next element.

Parameters

iter	The iterator.

Returns

Pointer to the next element.

rbtree_iter_prev()

void* rbtree_iter_prev

(

rbtree_iter_t *

iter

)

Moves the iterator to the previous element.

Parameters

iter	The iterator.

Returns

Pointer to the previous element.

rbtree_iter_start()

static void* rbtree_iter_start ( rbtree_iter_t *  iter, rbtree_t *  tree, int  dir  )

static

Internal function, init traversal object, dir determines whether to begin traversal at the smallest or largest valued node.

Parameters

iter	the iterator.
tree	the tree.
dir	the direction.

Returns

result of the iteration.

rbtree_node_alloc()

rbtree_node_t* rbtree_node_alloc

(

void

)

Allocate memory for a node.

Returns

Pointer to the allocated node.

rbtree_node_create()

rbtree_node_t* rbtree_node_create

(

void *

value

)

Allocate memory for a node and sets its value.

Parameters

value

Value to associated node.

Returns

Pointer to the allocated node.

rbtree_node_dealloc()

void rbtree_node_dealloc

(

rbtree_node_t *

node

)

Deallocate a node.

Parameters

node	The node to destroy.

rbtree_node_get_value()

void* rbtree_node_get_value

(

rbtree_node_t *

node

)

Provides access to the value associated to a node.

Parameters

node	The node itself.

Returns

The value associated to the node.

rbtree_node_init()

rbtree_node_t* rbtree_node_init	(	rbtree_node_t *	node,
		void *	value
	)

Initializes the already allocated node.

Parameters

node	The node itself.
value	The value associated to the node.

Returns

Pointer to the node itself.

rbtree_node_is_red()

static int rbtree_node_is_red ( const rbtree_node_t *  node )

static

Checks if the node is red.

Parameters

node	the node to check.

Returns

1 if the node is red, 0 otherwise.

rbtree_node_rotate()

static rbtree_node_t* rbtree_node_rotate ( rbtree_node_t *  node, int  dir  )

static

Performs a node rotation.

Parameters

node	the node.
dir	the direction of the rotation (0: left, 1: right).

Returns

the result of the rotate operation.

rbtree_node_rotate2()

static rbtree_node_t* rbtree_node_rotate2 ( rbtree_node_t *  node, int  dir  )

static

Performs a double rotation.

Parameters

node	the node.
dir	the direction of the rotation (0: left, 1: right).

Returns

the result of the rotate operation.

Suppose U has a parent V and a grandparent W. Then two successive rotations on U will ensure that V and W are descendents of U.

rbtree_tree_alloc()

rbtree_t* rbtree_tree_alloc

(

void

)

Allocate memory for a tree.

Returns

Pointer to the allocated tree.

rbtree_tree_create()

rbtree_t* rbtree_tree_create

(

rbtree_tree_node_cmp_f

cmp

)

Allocate memory for a tree and sets the function used to compare nodes.

Parameters

cmp	Function used to compare elements of the tree.

Returns

Pointer to the allocated tree.

rbtree_tree_dealloc()

void rbtree_tree_dealloc	(	rbtree_t *	tree,
		rbtree_tree_node_f	node_cb
	)

Deallocate a node.

Parameters

tree	The tree to destroy.
node_cb	The function called on each element of the tree before destroying the tree.

rbtree_tree_find()

void* rbtree_tree_find	(	rbtree_t *	tree,
		void *	value
	)

Searches the node inside the tree with the given value.

Parameters

tree	The tree.
value	The value to search.

Returns

Pointer to the value itself.

rbtree_tree_find_by_value()

void* rbtree_tree_find_by_value	(	rbtree_t *	tree,
		rbtree_tree_cmp_f	cmp_fun,
		void *	value
	)

Searches the node inside the tree with the given value.

Parameters

tree	The tree.
cmp_fun	The node compare function.
value	The value to search.

Returns

Pointer to the value itself.

rbtree_tree_init()

rbtree_t* rbtree_tree_init	(	rbtree_t *	tree,
		rbtree_tree_node_cmp_f	cmp
	)

Initializes the tree.

Parameters

tree	The tree to initialize.
cmp	The compare function to associate to the tree.

Returns

Pointer to tree itself.

rbtree_tree_insert()

int rbtree_tree_insert	(	rbtree_t *	tree,
		void *	value
	)

Interts the value inside the tree.

Parameters

tree	The tree.
value	The value to insert.

Returns

1 on success, 0 on failure.

rbtree_tree_insert_node()

int rbtree_tree_insert_node	(	rbtree_t *	tree,
		rbtree_node_t *	node
	)

Interts the value inside the tree.

Parameters

tree	The tree.
node	The node to insert.

Returns

1 on success, 0 on failure.

rbtree_tree_node_cmp_ptr_cb()

static int rbtree_tree_node_cmp_ptr_cb ( rbtree_t *  tree, rbtree_node_t *  a, rbtree_node_t *  b  )

static

Peforms a comparison between the pointers of two elements.

Parameters

tree	the tree.
a	the first element.
b	the second element.

Returns

result of the comparison.

rbtree_tree_node_dealloc_cb()

static void rbtree_tree_node_dealloc_cb ( rbtree_t *  tree, rbtree_node_t *  node  )

static

Default deallocation callback.

Parameters

tree	the tree.
node	the node.

rbtree_tree_print()

void rbtree_tree_print	(	rbtree_t *	tree,
		rbtree_tree_node_f	fun
	)

Prints the tree using the provided callback.

Parameters

tree	The tree.
fun	The print callback.

rbtree_tree_print_iter()

static void rbtree_tree_print_iter ( rbtree_t *  tree, rbtree_node_t *  node, rbtree_tree_node_f  fun  )

static

Prints the tree using a user-defined function.

Parameters

tree	the tree.
node	the current node.
fun	the print function.

rbtree_tree_remove()

int rbtree_tree_remove	(	rbtree_t *	tree,
		void *	value
	)

Removes the value from the given tree.

Parameters

tree	The tree.
value	The value to search.

Returns

Returns 1 if the value was removed, 0 otherwise.

rbtree_tree_remove_with_cb()

int rbtree_tree_remove_with_cb	(	rbtree_t *	tree,
		void *	value,
		rbtree_tree_node_f	node_cb
	)

Removes the value from the tree.

Parameters

tree	The tree.
value	The value to remove.
node_cb	The callback to call on the node before removing the node.

Returns

1 on success, 0 on failure.

rbtree_tree_size()

unsigned int rbtree_tree_size

(

rbtree_t *

tree

)

Returns the size of the tree.

Parameters

tree

The tree.

Returns

The size of the tree.

rbtree_tree_test()

int rbtree_tree_test	(	rbtree_t *	tree,
		rbtree_node_t *	root
	)

Checks the tree.

Parameters

tree	The tree.
root	The root of the tree.

Returns

1 on failure, 0 on success.