Red/Black tree. More...

Classes
struct	ndtree_node_t
	Stores data about an NDTree node. More...

struct	ndtree_t
	Stores data about an NDTree. More...

struct	ndtree_iter_t
	Stores data about an NDTree iterator. More...

Functions
static int	__ndtree_tree_node_cmp_ptr_cb (ndtree_t self, void a, void *b)
	Default comparison function. More...

ndtree_node_t *	ndtree_node_alloc (void)
	Allocate memory for a node. More...

ndtree_node_t *	ndtree_node_create (void *value)
	Allocate memory for a node and sets its value. More...

ndtree_node_t *	ndtree_node_init (ndtree_node_t node, void value)
	Initializes the already allocated node. More...

void	ndtree_node_set_value (ndtree_node_t node, void value)
	Sets the value of the given node. More...

void *	ndtree_node_get_value (ndtree_node_t *node)
	Provides access to the value associated to a node. More...

void	ndtree_set_root (ndtree_t tree, ndtree_node_t node)
	Sets the given node as root of the tree. More...

ndtree_node_t *	ndtree_create_root (ndtree_t tree, void value)
	Creates a new node and assigns it as root of the tree. More...

ndtree_node_t *	ndtree_get_root (ndtree_t *tree)
	Provides access to the root of the tree. More...

void	ndtree_add_child_to_node (ndtree_t tree, ndtree_node_t parent, ndtree_node_t *child)
	Adds the given `child` as child of `parent`. More...

ndtree_node_t *	ndtree_create_child_of_node (ndtree_t tree, ndtree_node_t parent, void *value)
	Creates a new node and sets it as child of `parent`. More...

unsigned int	ndtree_node_count_children (ndtree_node_t *node)
	Counts the number of children of the given node. More...

void	ndtree_node_dealloc (ndtree_node_t *node)
	Deallocate a node. More...

ndtree_t *	ndtree_tree_alloc (void)
	Allocate memory for a tree. More...

ndtree_t *	ndtree_tree_create (ndtree_tree_cmp_f cmp)
	Allocate memory for a tree and sets the function used to compare nodes. More...

ndtree_t *	ndtree_tree_init (ndtree_t *tree, ndtree_tree_cmp_f node_cmp_cb)
	Initializes the tree. More...

static void	__ndtree_tree_dealloc_rec (ndtree_t tree, ndtree_node_t node, ndtree_tree_node_f node_cb)
	Recursive deallocation of the memory of the tree. More...

void	ndtree_tree_dealloc (ndtree_t *tree, ndtree_tree_node_f node_cb)
	Deallocate a node. More...

static ndtree_node_t *	__ndtree_tree_find_rec (ndtree_t tree, ndtree_tree_cmp_f cmp, void value, ndtree_node_t *node)
	Recursive search in the tree. More...

ndtree_node_t *	ndtree_tree_find (ndtree_t tree, ndtree_tree_cmp_f cmp, void value)
	Searches the node inside the tree with the given value. More...

ndtree_node_t *	ndtree_node_find (ndtree_t tree, ndtree_node_t node, ndtree_tree_cmp_f cmp, void *value)
	Searches the given value among the children of node. More...

unsigned int	ndtree_tree_size (ndtree_t *tree)
	Returns the size of the tree. More...

int	ndtree_tree_remove_node_with_cb (ndtree_t tree, ndtree_node_t node, ndtree_tree_node_f node_cb)
	Removes the node from the given tree. More...

int	ndtree_tree_remove_with_cb (ndtree_t tree, void value, ndtree_tree_node_f node_cb)
	Removes the node from the given tree. More...

ndtree_iter_t *	ndtree_iter_alloc (void)
	Allocate the memory for the iterator. More...

void	ndtree_iter_dealloc (ndtree_iter_t *iter)
	Deallocate the memory for the iterator. More...

ndtree_node_t *	ndtree_iter_first (ndtree_node_t node, ndtree_iter_t iter)
	Initializes the iterator the the first child of the node. More...

ndtree_node_t *	ndtree_iter_last (ndtree_node_t node, ndtree_iter_t iter)
	Initializes the iterator the the last child of the node. More...

ndtree_node_t *	ndtree_iter_next (ndtree_iter_t *iter)
	Moves the iterator to the next element. More...

ndtree_node_t *	ndtree_iter_prev (ndtree_iter_t *iter)
	Moves the iterator to the previous element. More...

static void	__ndtree_tree_visitor_iter (ndtree_t tree, ndtree_node_t node, ndtree_tree_node_f enter_fun, ndtree_tree_node_f exit_fun)
	A visitor function. More...

void	ndtree_tree_visitor (ndtree_t *tree, ndtree_tree_node_f enter_fun, ndtree_tree_node_f exit_fun)
	Run a visit of the tree (DFS). 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

◆ __ndtree_tree_dealloc_rec()

static void __ndtree_tree_dealloc_rec	(	ndtree_t *	tree,
		ndtree_node_t *	node,
		ndtree_tree_node_f	node_cb
	)

static

Recursive deallocation of the memory of the tree.

Parameters

tree	the tree.
node	the node to deallocate.
node_cb	the callback to call before freeing the memory of the node.

◆ __ndtree_tree_find_rec()

static ndtree_node_t* __ndtree_tree_find_rec	(	ndtree_t *	tree,
		ndtree_tree_cmp_f	cmp,
		void *	value,
		ndtree_node_t *	node
	)

static

Recursive search in the tree.

Parameters

tree	the tree.
cmp	the comparison function.
value	the value to compare against.
node	the current node.

Returns: the node we found, NULL otherwise.

◆ __ndtree_tree_node_cmp_ptr_cb()

static int __ndtree_tree_node_cmp_ptr_cb	(	ndtree_t *	self,
		void *	a,
		void *	b
	)

inlinestatic

Default comparison function.

Parameters

self	the ndtree.
a	the first element.
b	the second element.

Returns: comparison between the elements.

◆ __ndtree_tree_visitor_iter()

static void __ndtree_tree_visitor_iter	(	ndtree_t *	tree,
		ndtree_node_t *	node,
		ndtree_tree_node_f	enter_fun,
		ndtree_tree_node_f	exit_fun
	)

static

A visitor function.

Parameters

tree	the tree.
node	the current node.
enter_fun	the enter function.
exit_fun	the exit function.

◆ ndtree_add_child_to_node()

void ndtree_add_child_to_node	(	ndtree_t *	tree,
		ndtree_node_t *	parent,
		ndtree_node_t *	child
	)

Adds the given child as child of parent.

Parameters

tree	The tree.
parent	The `parent` node.
child	The new `child` node.

◆ ndtree_create_child_of_node()

ndtree_node_t* ndtree_create_child_of_node	(	ndtree_t *	tree,
		ndtree_node_t *	parent,
		void *	value
	)

Creates a new node and sets it as child of parent.

Parameters

tree	The tree.
parent	The `parent` node.
value	Value associated with the new child.

Returns: Pointer to the newly created child node.

◆ ndtree_create_root()

ndtree_node_t* ndtree_create_root	(	ndtree_t *	tree,
		void *	value
	)

Creates a new node and assigns it as root of the tree.

Parameters

tree	The tree.
value	The value associated to the node.

Returns: The newly created node.

◆ ndtree_get_root()

ndtree_node_t* ndtree_get_root ( ndtree_t * tree )

Provides access to the root of the tree.

Parameters

tree The tree.

Returns: Pointer to the node.

◆ ndtree_iter_alloc()

ndtree_iter_t* ndtree_iter_alloc ( void )

Allocate the memory for the iterator.

Returns: Pointer to the allocated iterator.

◆ ndtree_iter_dealloc()

void ndtree_iter_dealloc ( ndtree_iter_t * iter )

Deallocate the memory for the iterator.

Parameters

iter	Pointer to the allocated iterator.

◆ ndtree_iter_first()

ndtree_node_t* ndtree_iter_first	(	ndtree_node_t *	node,
		ndtree_iter_t *	iter
	)

Initializes the iterator the the first child of the node.

Parameters

node	The node of which we want to iterate the children.
iter	The iterator we want to initialize.

Returns: Pointer to the first node of the list.

◆ ndtree_iter_last()

ndtree_node_t* ndtree_iter_last	(	ndtree_node_t *	node,
		ndtree_iter_t *	iter
	)

Initializes the iterator the the last child of the node.

Parameters

node	The node of which we want to iterate the children.
iter	The iterator we want to initialize.

Returns: Pointer to the last node of the list.

◆ ndtree_iter_next()

ndtree_node_t* ndtree_iter_next ( ndtree_iter_t * iter )

Moves the iterator to the next element.

Parameters

iter	The iterator.

Returns: Pointer to the next element.

◆ ndtree_iter_prev()

ndtree_node_t* ndtree_iter_prev ( ndtree_iter_t * iter )

Moves the iterator to the previous element.

Parameters

iter	The iterator.

Returns: Pointer to the previous element.

◆ ndtree_node_alloc()

ndtree_node_t* ndtree_node_alloc ( void )

Allocate memory for a node.

Returns: Pointer to the allocated node.

◆ ndtree_node_count_children()

unsigned int ndtree_node_count_children ( ndtree_node_t * node )

Counts the number of children of the given node.

Parameters

node	The node of which we count the children.

Returns: The number of children.

◆ ndtree_node_create()

ndtree_node_t* ndtree_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.

◆ ndtree_node_dealloc()

void ndtree_node_dealloc ( ndtree_node_t * node )

Deallocate a node.

Parameters

node	The node to destroy.

◆ ndtree_node_find()

ndtree_node_t* ndtree_node_find	(	ndtree_t *	tree,
		ndtree_node_t *	node,
		ndtree_tree_cmp_f	cmp,
		void *	value
	)

Searches the given value among the children of node.

Parameters

tree	The tree.
node	The node under which we search.
cmp	The node compare function.
value	The value to search.

Returns: Node associated with the value.

◆ ndtree_node_get_value()

void* ndtree_node_get_value ( ndtree_node_t * node )

Provides access to the value associated to a node.

Parameters

node	The node itself.

Returns: The value associated to the node.

◆ ndtree_node_init()

ndtree_node_t* ndtree_node_init	(	ndtree_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.

◆ ndtree_node_set_value()

void ndtree_node_set_value	(	ndtree_node_t *	node,
		void *	value
	)

Sets the value of the given node.

Parameters

node	The node to manipulate.
value	The value associated to the node.

◆ ndtree_set_root()

void ndtree_set_root	(	ndtree_t *	tree,
		ndtree_node_t *	node
	)

Sets the given node as root of the tree.

Parameters

tree	The tree.
node	The node to set as root.

◆ ndtree_tree_alloc()

ndtree_t* ndtree_tree_alloc ( void )

Allocate memory for a tree.

Returns: Pointer to the allocated tree.

◆ ndtree_tree_create()

ndtree_t* ndtree_tree_create ( ndtree_tree_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.

◆ ndtree_tree_dealloc()

void ndtree_tree_dealloc	(	ndtree_t *	tree,
		ndtree_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.

◆ ndtree_tree_find()

ndtree_node_t* ndtree_tree_find	(	ndtree_t *	tree,
		ndtree_tree_cmp_f	cmp,
		void *	value
	)

Searches the node inside the tree with the given value.

Parameters

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

Returns: Node associated with the value.

◆ ndtree_tree_init()

ndtree_t* ndtree_tree_init	(	ndtree_t *	tree,
		ndtree_tree_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.

◆ ndtree_tree_remove_node_with_cb()

int ndtree_tree_remove_node_with_cb	(	ndtree_t *	tree,
		ndtree_node_t *	node,
		ndtree_tree_node_f	node_cb
	)

Removes the node from the given tree.

Parameters

tree	The tree.
node	The node to remove.
node_cb	The function called on the node before removing it.

Returns: Returns 1 if the node was removed, 0 otherwise.

Optionally the node callback can be provided to dealloc node and/or user data. Use ndtree_tree_node_dealloc default callback to deallocate node created by ndtree_tree_insert(...).

◆ ndtree_tree_remove_with_cb()

int ndtree_tree_remove_with_cb	(	ndtree_t *	tree,
		void *	value,
		ndtree_tree_node_f	node_cb
	)

Removes the node from the given tree.

Parameters

tree	The tree.
value	The value to search.
node_cb	The function called on the node before removing it.

Returns: Returns 1 if the value was removed, 0 otherwise.

Optionally the node callback can be provided to dealloc node and/or user data. Use ndtree_tree_node_dealloc default callback to deallocate node created by ndtree_tree_insert(...).

◆ ndtree_tree_size()

unsigned int ndtree_tree_size ( ndtree_t * tree )

Returns the size of the tree.

Parameters

tree The tree.

Returns: The size of the tree.

◆ ndtree_tree_visitor()

void ndtree_tree_visitor	(	ndtree_t *	tree,
		ndtree_tree_node_f	enter_fun,
		ndtree_tree_node_f	exit_fun
	)

Run a visit of the tree (DFS).

Parameters

tree	The tree to visit.
enter_fun	Function to call when entering a node.
exit_fun	Function to call when exiting a node.

Classes

Functions

Detailed Description

Function Documentation

◆ __ndtree_tree_dealloc_rec()

◆ __ndtree_tree_find_rec()

◆ __ndtree_tree_node_cmp_ptr_cb()

◆ __ndtree_tree_visitor_iter()

◆ ndtree_add_child_to_node()

◆ ndtree_create_child_of_node()

◆ ndtree_create_root()

◆ ndtree_get_root()

◆ ndtree_iter_alloc()

◆ ndtree_iter_dealloc()

◆ ndtree_iter_first()

◆ ndtree_iter_last()

◆ ndtree_iter_next()

◆ ndtree_iter_prev()

◆ ndtree_node_alloc()

◆ ndtree_node_count_children()

◆ ndtree_node_create()

◆ ndtree_node_dealloc()

◆ ndtree_node_find()

◆ ndtree_node_get_value()

◆ ndtree_node_init()

◆ ndtree_node_set_value()

◆ ndtree_set_root()

◆ ndtree_tree_alloc()

◆ ndtree_tree_create()

◆ ndtree_tree_dealloc()

◆ ndtree_tree_find()

◆ ndtree_tree_init()

◆ ndtree_tree_remove_node_with_cb()

◆ ndtree_tree_remove_with_cb()

◆ ndtree_tree_size()

◆ ndtree_tree_visitor()