Tree

Collaboration diagram for Tree:

Data Structures
struct	tree_node
	A single node inside a tree. More...

Macros
#define	INIT_TREE_NODE(_node)
	Initialize an empty tree node.
#define	FOREACH_CHILDREN(_iter, _node)   FOREACH_LLIST (_iter, &(_node)->children)
	Loop over each children of a tree node. More...

Typedefs
typedef tree_node_t *	tree_t
	The root of a tree structure.

Functions
static ALWAYS_INLINE tree_node_t *	tree_node (node_t *node)
	Convert a linked list node to its containing tree node. More...
void	tree_add_child (tree_node_t *node, tree_node_t *child)
	Add the given node as a children of another. More...
void	tree_add_child_sorted (tree_node_t *node, tree_node_t *child, compare_t)
	Add the given node as a children of another in a sorted manner. More...
tree_node_t *	tree_remove (tree_node_t *node)
	Remove a node from its containing tree (if any). More...
tree_node_t *	tree_find_child (tree_node_t *node, compare_t, const void *data)
	Find a specific child of a node. More...
void	tree_free (tree_t root, void(*free_function)(tree_node_t *))
	Free all the elements contained inside a tree. More...

Detailed Description

Tree

This is our implementation of an intrusive generic tree structure.

Macro Definition Documentation

FOREACH_CHILDREN

#define FOREACH_CHILDREN	(		_iter,
			_node
	)		FOREACH_LLIST (_iter, &(_node)->children)

Parameters

_iter	The name of the iterator used inside the loop
_node	The tree node

Function Documentation

tree_add_child()

void tree_add_child	(	tree_node_t *	node,
		tree_node_t *	child
	)

Note

This function appends the new child to the current list of children. If you want to keep the children sorted use tree_add_child_sorted

tree_add_child_sorted()

void tree_add_child_sorted	(	tree_node_t *	node,
		tree_node_t *	child,
		compare_t	compare
	)

Warning

This function assumes that the node's children are already sorted

Parameters

node	The parent node
child	The new child
compare	The compare function used on the children

tree_find_child()

tree_node_t * tree_find_child	(	tree_node_t *	node,
		compare_t	compare,
		const void *	data
	)

Parameters

node	The parent node
compare	The compare function used to find the node
data	Data passed to the compare function

Returns

The child or NULL

tree_free()

void tree_free	(	tree_t	root,
		void(*)(tree_node_t *)	free_function
	)

Parameters

root	The root of the tree
free	The function used to free an element

tree_node()

static ALWAYS_INLINE tree_node_t * tree_node ( node_t *  node )

static

Children of a node are linked together and addressed using a likned list, it is necessary (and trivial) to perform this conversion when iterating over them.

tree_remove()

tree_node_t * tree_remove

(

tree_node_t *

node

)

Returns

The removed node