A red black tree.
More...
#include "ompi_config.h"
#include <stdlib.h>
#include "ompi/constants.h"
#include "opal/class/opal_object.h"
#include "ompi/class/ompi_free_list.h"
Go to the source code of this file.
|
OMPI_DECLSPEC | OBJ_CLASS_DECLARATION (ompi_rb_tree_node_t) |
| declare the tree node as a class
|
|
OMPI_DECLSPEC | OBJ_CLASS_DECLARATION (ompi_rb_tree_t) |
| declare the tree as a class
|
|
OMPI_DECLSPEC void | ompi_rb_tree_construct (opal_object_t *object) |
| the construct function. More...
|
|
OMPI_DECLSPEC void | ompi_rb_tree_destruct (opal_object_t *object) |
| the destruct function. More...
|
|
OMPI_DECLSPEC int | ompi_rb_tree_init (ompi_rb_tree_t *tree, ompi_rb_tree_comp_fn_t comp) |
| the function creates a new tree More...
|
|
OMPI_DECLSPEC int | ompi_rb_tree_insert (ompi_rb_tree_t *tree, void *key, void *value) |
| inserts a node into the tree More...
|
|
OMPI_DECLSPEC void * | ompi_rb_tree_find_with (ompi_rb_tree_t *tree, void *key, ompi_rb_tree_comp_fn_t compfn) |
| finds a value in the tree based on the passed key using passed compare function More...
|
|
static void * | ompi_rb_tree_find (ompi_rb_tree_t *tree, void *key) |
| finds a value in the tree based on the passed key More...
|
|
OMPI_DECLSPEC int | ompi_rb_tree_delete (ompi_rb_tree_t *tree, void *key) |
| deletes a node based on its key More...
|
|
OMPI_DECLSPEC int | ompi_rb_tree_destroy (ompi_rb_tree_t *tree) |
| frees all the nodes on the tree More...
|
|
OMPI_DECLSPEC int | ompi_rb_tree_traverse (ompi_rb_tree_t *tree, ompi_rb_tree_condition_fn_t cond, ompi_rb_tree_action_fn_t action) |
| traverses the entire tree, performing the cond function on each of the values and if it returns one it performs the action function on the values More...
|
|
OMPI_DECLSPEC int | ompi_rb_tree_size (ompi_rb_tree_t *tree) |
| returns the size of the tree More...
|
|
typedef void(* ompi_rb_tree_action_fn_t)(void *, void *) |
this function is uused for the user to perform any action on the passed values.
The first argument is the key and the second is the value. note that this function SHOULD NOT modify the keys, as that would mess up the tree.
typedef int(* ompi_rb_tree_comp_fn_t)(void *key1, void *key2) |
the compare function typedef.
This function is used to compare 2 nodes.
typedef int(* ompi_rb_tree_condition_fn_t)(void *) |
this function is used for the ompi_rb_tree_traverse function.
it is passed a pointer to the value for each node and, if it returns a one, the action function is called on that node. Otherwise, the node is ignored.
OMPI_DECLSPEC void ompi_rb_tree_construct |
( |
opal_object_t * |
object | ) |
|
OMPI_DECLSPEC int ompi_rb_tree_delete |
( |
ompi_rb_tree_t * |
tree, |
|
|
void * |
key |
|
) |
| |
deletes a node based on its key
- Parameters
-
tree | a pointer to the tree data structure |
key | a pointer to the key |
- Return values
-
OMPI_SUCCESS | if the node is found and deleted |
OMPI_ERR_NOT_FOUND | if the node is not found |
References ompi_rb_tree_node_t::color, ompi_rb_tree_t::free_list, ompi_rb_tree_node_t::key, ompi_rb_tree_node_t::left, ompi_rb_tree_t::nill, ompi_rb_tree_node_t::parent, ompi_rb_tree_node_t::right, ompi_rb_tree_t::root_ptr, ompi_rb_tree_t::tree_size, and ompi_rb_tree_node_t::value.
Referenced by mca_rcache_rb_tree_delete(), and mca_rcache_vma_tree_delete().
OMPI_DECLSPEC void ompi_rb_tree_destruct |
( |
opal_object_t * |
object | ) |
|
OMPI_DECLSPEC int ompi_rb_tree_insert |
( |
ompi_rb_tree_t * |
tree, |
|
|
void * |
key, |
|
|
void * |
value |
|
) |
| |
returns the size of the tree
- Parameters
-
tree | a pointer to the tree data structure |
- Return values
-
int | the nuber of items on the tree |
References ompi_rb_tree_t::tree_size.
traverses the entire tree, performing the cond function on each of the values and if it returns one it performs the action function on the values
- Parameters
-
tree | a pointer to the tree |
cond | a pointer to the condition function |
action | a pointer to the action function |
- Return values
-
OMPI_SUCCESS | |
OMPI_ERROR | if there is an error |
References ompi_rb_tree_node_t::left, and ompi_rb_tree_t::root_ptr.