MentOS
0.8.0
The Mentoring Operating System
|
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... | |
Red/Black tree.
|
static |
Recursive deallocation of the memory of the tree.
tree | the tree. |
node | the node to deallocate. |
node_cb | the callback to call before freeing the memory of the node. |
|
static |
Recursive search in the tree.
tree | the tree. |
cmp | the comparison function. |
value | the value to compare against. |
node | the current node. |
|
inlinestatic |
Default comparison function.
self | the ndtree. |
a | the first element. |
b | the second element. |
|
static |
A visitor function.
tree | the tree. |
node | the current node. |
enter_fun | the enter function. |
exit_fun | the exit function. |
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
.
tree | The tree. |
parent | The parent node. |
child | The new child 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
.
tree | The tree. |
parent | The parent node. |
value | Value associated with the new child. |
ndtree_node_t* ndtree_create_root | ( | ndtree_t * | tree, |
void * | value | ||
) |
Creates a new node and assigns it as root of the tree.
tree | The tree. |
value | The value associated to the node. |
ndtree_node_t* ndtree_get_root | ( | ndtree_t * | tree | ) |
Provides access to the root of the tree.
tree | The tree. |
ndtree_iter_t* ndtree_iter_alloc | ( | void | ) |
Allocate the memory for the iterator.
void ndtree_iter_dealloc | ( | ndtree_iter_t * | iter | ) |
Deallocate the memory for the iterator.
iter | Pointer to the allocated iterator. |
ndtree_node_t* ndtree_iter_first | ( | ndtree_node_t * | node, |
ndtree_iter_t * | iter | ||
) |
Initializes the iterator the the first child of the node.
node | The node of which we want to iterate the children. |
iter | The iterator we want to initialize. |
ndtree_node_t* ndtree_iter_last | ( | ndtree_node_t * | node, |
ndtree_iter_t * | iter | ||
) |
Initializes the iterator the the last child of the node.
node | The node of which we want to iterate the children. |
iter | The iterator we want to initialize. |
ndtree_node_t* ndtree_iter_next | ( | ndtree_iter_t * | iter | ) |
Moves the iterator to the next element.
iter | The iterator. |
ndtree_node_t* ndtree_iter_prev | ( | ndtree_iter_t * | iter | ) |
Moves the iterator to the previous element.
iter | The iterator. |
ndtree_node_t* ndtree_node_alloc | ( | void | ) |
Allocate memory for a node.
unsigned int ndtree_node_count_children | ( | ndtree_node_t * | node | ) |
Counts the number of children of the given node.
node | The node of which we count the children. |
ndtree_node_t* ndtree_node_create | ( | void * | value | ) |
Allocate memory for a node and sets its value.
value | Value to associated node. |
void ndtree_node_dealloc | ( | ndtree_node_t * | node | ) |
Deallocate a node.
node | The node to destroy. |
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.
tree | The tree. |
node | The node under which we search. |
cmp | The node compare function. |
value | The value to search. |
void* ndtree_node_get_value | ( | ndtree_node_t * | node | ) |
Provides access to the value associated to a node.
node | The node itself. |
ndtree_node_t* ndtree_node_init | ( | ndtree_node_t * | node, |
void * | value | ||
) |
Initializes the already allocated node.
node | The node itself. |
value | The value associated to the node. |
void ndtree_node_set_value | ( | ndtree_node_t * | node, |
void * | value | ||
) |
Sets the value of the given node.
node | The node to manipulate. |
value | The value associated to the node. |
void ndtree_set_root | ( | ndtree_t * | tree, |
ndtree_node_t * | node | ||
) |
Sets the given node as root of the tree.
tree | The tree. |
node | The node to set as root. |
ndtree_t* ndtree_tree_alloc | ( | void | ) |
Allocate memory for a tree.
ndtree_t* ndtree_tree_create | ( | ndtree_tree_cmp_f | cmp | ) |
Allocate memory for a tree and sets the function used to compare nodes.
cmp | Function used to compare elements of the tree. |
void ndtree_tree_dealloc | ( | ndtree_t * | tree, |
ndtree_tree_node_f | node_cb | ||
) |
Deallocate a node.
tree | The tree to destroy. |
node_cb | The function called on each element of the tree before destroying the tree. |
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.
tree | The tree. |
cmp | The node compare function. |
value | The value to search. |
ndtree_t* ndtree_tree_init | ( | ndtree_t * | tree, |
ndtree_tree_cmp_f | cmp | ||
) |
Initializes the tree.
tree | The tree to initialize. |
cmp | The compare function to associate to the tree. |
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.
tree | The tree. |
node | The node to remove. |
node_cb | The function called on the node before removing it. |
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(...).
int ndtree_tree_remove_with_cb | ( | ndtree_t * | tree, |
void * | value, | ||
ndtree_tree_node_f | node_cb | ||
) |
Removes the node from the given tree.
tree | The tree. |
value | The value to search. |
node_cb | The function called on the node before removing it. |
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(...).
unsigned int ndtree_tree_size | ( | ndtree_t * | tree | ) |
Returns the size of the tree.
tree | The tree. |
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).
tree | The tree to visit. |
enter_fun | Function to call when entering a node. |
exit_fun | Function to call when exiting a node. |