OpenMPI  0.1.1
ompi_rb_tree.h File Reference

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.

Data Structures

struct  ompi_rb_tree_node_t
 node data structure More...
 
struct  ompi_rb_tree_t
 the data structure that holds all the needed information about the tree. More...
 

Typedefs

typedef struct ompi_rb_tree_node_t ompi_rb_tree_node_t
 
typedef int(* ompi_rb_tree_comp_fn_t )(void *key1, void *key2)
 the compare function typedef. More...
 
typedef struct ompi_rb_tree_t ompi_rb_tree_t
 
typedef int(* ompi_rb_tree_condition_fn_t )(void *)
 this function is used for the ompi_rb_tree_traverse function. 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. More...
 

Enumerations

enum  ompi_rb_tree_nodecolor_t { RED, BLACK }
 red and black enum
 

Functions

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...
 

Detailed Description

A red black tree.

Typedef Documentation

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.

Function Documentation

OMPI_DECLSPEC void ompi_rb_tree_construct ( opal_object_t object)

the construct function.

creates the free list to get the nodes from

Parameters
objectthe tree that is to be used
Return values
NONE

References ompi_rb_tree_t::free_list, OBJ_CLASS, OBJ_CONSTRUCT, and ompi_rb_tree_t::root_ptr.

OMPI_DECLSPEC int ompi_rb_tree_delete ( ompi_rb_tree_t tree,
void *  key 
)

deletes a node based on its key

Parameters
treea pointer to the tree data structure
keya pointer to the key
Return values
OMPI_SUCCESSif the node is found and deleted
OMPI_ERR_NOT_FOUNDif 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 int ompi_rb_tree_destroy ( ompi_rb_tree_t tree)

frees all the nodes on the tree

Parameters
treea pointer to the tree data structure
Return values
OMPI_SUCCESS

References ompi_rb_tree_t::free_list, ompi_rb_tree_t::nill, and ompi_rb_tree_t::root_ptr.

Referenced by ompi_rb_tree_destruct().

OMPI_DECLSPEC void ompi_rb_tree_destruct ( opal_object_t object)

the destruct function.

tries to free the tree and destroys the free list

Parameters
objectthe tree object

References OBJ_DESTRUCT, and ompi_rb_tree_destroy().

static void* ompi_rb_tree_find ( ompi_rb_tree_t tree,
void *  key 
)
inlinestatic

finds a value in the tree based on the passed key

Parameters
treea pointer to the tree data structure
keya pointer to the key
Return values
pointerto the value if found
NULLif not found

References ompi_rb_tree_t::comp, and ompi_rb_tree_find_with().

Referenced by mca_mpool_base_tree_find(), and mca_rcache_rb_tree_find().

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

Parameters
treea pointer to the tree data structure
keya pointer to the key
comparefunction
Return values
pointerto the value if found
NULLif not found

References ompi_rb_tree_node_t::key, ompi_rb_tree_node_t::left, ompi_rb_tree_t::nill, ompi_rb_tree_node_t::right, ompi_rb_tree_t::root_ptr, and ompi_rb_tree_node_t::value.

Referenced by mca_rcache_vma_tree_delete(), mca_rcache_vma_tree_find(), mca_rcache_vma_tree_find_all(), and ompi_rb_tree_find().

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

Parameters
treea pointer to an allocated area of memory for the main tree data structure.
compa pointer to the function to use for comaparing 2 nodes
Return values
OMPI_SUCCESSif it is successful
OMPI_ERR_TEMP_OUT_OF_RESOURCEif unsuccessful

References ompi_rb_tree_node_t::color, ompi_rb_tree_t::comp, ompi_rb_tree_t::free_list, 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, and ompi_rb_tree_t::tree_size.

OMPI_DECLSPEC int ompi_rb_tree_insert ( ompi_rb_tree_t tree,
void *  key,
void *  value 
)

inserts a node into the tree

Parameters
treea pointer to the tree data structure
keythe key for the node
valuethe value for the node
Return values
OMPI_SUCCESS
OMPI_ERR_TEMP_OUT_OF_RESOURCEif unsuccessful

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_node_t::parent, ompi_rb_tree_node_t::right, ompi_rb_tree_t::root_ptr, and ompi_rb_tree_node_t::value.

OMPI_DECLSPEC int ompi_rb_tree_size ( ompi_rb_tree_t tree)

returns the size of the tree

Parameters
treea pointer to the tree data structure
Return values
intthe nuber of items on the tree

References ompi_rb_tree_t::tree_size.

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

Parameters
treea pointer to the tree
conda pointer to the condition function
actiona pointer to the action function
Return values
OMPI_SUCCESS
OMPI_ERRORif there is an error

References ompi_rb_tree_node_t::left, and ompi_rb_tree_t::root_ptr.