Red/Black tree. More...

Macros
#define	RBTREE_ITER_MAX_HEIGHT 64
	Tallest allowable tree to iterate.

Typedefs
typedef struct rbtree_node_t	rbtree_node_t
	Node of the tree.

typedef struct rbtree_t	rbtree_t
	The tree itself.

typedef struct rbtree_iter_t	rbtree_iter_t
	Iterator for traversing the tree.

typedef int(*	rbtree_tree_cmp_f) (rbtree_t tree, rbtree_node_t a, void *arg)
	Function for comparing elements in the tree.

typedef int(*	rbtree_tree_node_cmp_f) (rbtree_t tree, rbtree_node_t a, rbtree_node_t *b)
	Function for comparing elements in the tree.

typedef void(*	rbtree_tree_node_f) (rbtree_t tree, rbtree_node_t node)
	Callback to call on elements of the tree.

Functions
rbtree_node_t *	rbtree_node_alloc (void)
	Allocate memory for a node. More...

rbtree_node_t *	rbtree_node_create (void *value)
	Allocate memory for a node and sets its value. More...

rbtree_node_t *	rbtree_node_init (rbtree_node_t node, void value)
	Initializes the already allocated node. 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...

rbtree_t *	rbtree_tree_alloc (void)
	Allocate memory for a tree. More...

rbtree_t *	rbtree_tree_create (rbtree_tree_node_cmp_f cmp)
	Allocate memory for a tree and sets the function used to compare nodes. More...

rbtree_t *	rbtree_tree_init (rbtree_t *tree, rbtree_tree_node_cmp_f cmp)
	Initializes the tree. 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_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...

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

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

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

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

Macros

Typedefs

Functions

Detailed Description

Function Documentation

◆ rbtree_iter_alloc()

◆ rbtree_iter_create()

◆ rbtree_iter_dealloc()

◆ rbtree_iter_first()

◆ rbtree_iter_init()

◆ rbtree_iter_last()

◆ rbtree_iter_next()

◆ rbtree_iter_prev()

◆ rbtree_node_alloc()

◆ rbtree_node_create()

◆ rbtree_node_dealloc()

◆ rbtree_node_get_value()

◆ rbtree_node_init()

◆ rbtree_tree_alloc()

◆ rbtree_tree_create()

◆ rbtree_tree_dealloc()

◆ rbtree_tree_find()

◆ rbtree_tree_find_by_value()

◆ rbtree_tree_init()

◆ rbtree_tree_insert()

◆ rbtree_tree_insert_node()

◆ rbtree_tree_print()

◆ rbtree_tree_remove()

◆ rbtree_tree_remove_with_cb()

◆ rbtree_tree_size()

◆ rbtree_tree_test()