OpenMPI 0.1.1

- Main Page
- Related Pages
- Modules
- Data Structures
- Files

- File List
- Globals

Data Structures | Typedefs | Enumerations | Functions
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

  object | the 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

  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 int ompi_rb_tree_destroy | ( | ompi_rb_tree_t * | tree | ) |

frees all the nodes on the tree

Parameters

  tree | a 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

  object | the tree object

References OBJ_DESTRUCT, and ompi_rb_tree_destroy().

static void* ompi_rb_tree_find | ( | ompi_rb_tree_t * | tree,
|  | void * | key
| ) |  |
| inline static

finds a value in the tree based on the passed key

Parameters

  tree | a pointer to the tree data structure
  key | a pointer to the key

Return values

  pointer | to the value if found
  NULL | if 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

  tree | a pointer to the tree data structure
  key | a pointer to the key
  compare | function

Return values

  pointer | to the value if found
  NULL | if 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

  tree | a pointer to an allocated area of memory for the main tree data structure.
  comp | a pointer to the function to use for comaparing 2 nodes

Return values

  OMPI_SUCCESS | if it is successful
  OMPI_ERR_TEMP_OUT_OF_RESOURCE | if 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

  tree | a pointer to the tree data structure
  key | the key for the node
  value | the value for the node

Return values

  OMPI_SUCCESS |
  OMPI_ERR_TEMP_OUT_OF_RESOURCE | if 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

  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.

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

  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.