MentOS  0.8.0
The Mentoring Operating System
Classes | Functions
ndtree.c File Reference

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_tndtree_node_alloc (void)
 Allocate memory for a node. More...
 
ndtree_node_tndtree_node_create (void *value)
 Allocate memory for a node and sets its value. More...
 
ndtree_node_tndtree_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_tndtree_create_root (ndtree_t *tree, void *value)
 Creates a new node and assigns it as root of the tree. More...
 
ndtree_node_tndtree_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_tndtree_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_tndtree_tree_alloc (void)
 Allocate memory for a tree. More...
 
ndtree_tndtree_tree_create (ndtree_tree_cmp_f cmp)
 Allocate memory for a tree and sets the function used to compare nodes. More...
 
ndtree_tndtree_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_tndtree_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_tndtree_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_tndtree_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_tndtree_iter_first (ndtree_node_t *node, ndtree_iter_t *iter)
 Initializes the iterator the the first child of the node. More...
 
ndtree_node_tndtree_iter_last (ndtree_node_t *node, ndtree_iter_t *iter)
 Initializes the iterator the the last child of the node. More...
 
ndtree_node_tndtree_iter_next (ndtree_iter_t *iter)
 Moves the iterator to the next element. More...
 
ndtree_node_tndtree_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.

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
treethe tree.
nodethe node to deallocate.
node_cbthe 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
treethe tree.
cmpthe comparison function.
valuethe value to compare against.
nodethe 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
selfthe ndtree.
athe first element.
bthe 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
treethe tree.
nodethe current node.
enter_funthe enter function.
exit_funthe 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
treeThe tree.
parentThe parent node.
childThe 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
treeThe tree.
parentThe parent node.
valueValue 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
treeThe tree.
valueThe 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
treeThe 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
iterPointer 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
nodeThe node of which we want to iterate the children.
iterThe 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
nodeThe node of which we want to iterate the children.
iterThe 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
iterThe 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
iterThe 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
nodeThe 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
valueValue to associated node.
Returns
Pointer to the allocated node.

◆ ndtree_node_dealloc()

void ndtree_node_dealloc ( ndtree_node_t node)

Deallocate a node.

Parameters
nodeThe 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
treeThe tree.
nodeThe node under which we search.
cmpThe node compare function.
valueThe 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
nodeThe 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
nodeThe node itself.
valueThe 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
nodeThe node to manipulate.
valueThe 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
treeThe tree.
nodeThe 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
cmpFunction 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
treeThe tree to destroy.
node_cbThe 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
treeThe tree.
cmpThe node compare function.
valueThe 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
treeThe tree to initialize.
cmpThe 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
treeThe tree.
nodeThe node to remove.
node_cbThe 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
treeThe tree.
valueThe value to search.
node_cbThe 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
treeThe 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
treeThe tree to visit.
enter_funFunction to call when entering a node.
exit_funFunction to call when exiting a node.