ndtree.h File Reference

N-Dimensional tree. More...

Go to the source code of this file.

Typedefs
typedef struct ndtree_node_t	ndtree_node_t
	Node of the tree.
typedef struct ndtree_t	ndtree_t
	The tree itself.
typedef struct ndtree_iter_t	ndtree_iter_t
	Iterator for traversing the tree.
typedef int(*	ndtree_tree_cmp_f) (ndtree_t *tree, void *lhs, void *rhs)
	Function for comparing elements in the tree.
typedef void(*	ndtree_tree_node_f) (ndtree_t *tree, ndtree_node_t *node)
	Callback to call on elements of the tree.

Functions
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...
void	ndtree_tree_dealloc (ndtree_t *tree, ndtree_tree_node_f node_cb)
	Deallocate a node. More...
ndtree_t *	ndtree_tree_init (ndtree_t *tree, ndtree_tree_cmp_f cmp)
	Initializes 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...
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

N-Dimensional tree.

Copyright

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

Function Documentation

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.