OpenMPI 0.1.1

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

- File List
- Globals

ompi_rb_tree.h
Go to the documentation of this file.
1 /*
2 * Copyright (c) 2004-2005 The Trustees of Indiana University and Indiana
3 * University Research and Technology
4 * Corporation. All rights reserved.
5 * Copyright (c) 2004-2005 The University of Tennessee and The University
6 * of Tennessee Research Foundation. All rights
7 * reserved.
8 * Copyright (c) 2004-2005 High Performance Computing Center Stuttgart,
9 * University of Stuttgart. All rights reserved.
10 * Copyright (c) 2004-2005 The Regents of the University of California.
11 * All rights reserved.
12 * $COPYRIGHT$
13 *
14 * Additional copyrights may follow
15 *
16 * $HEADER$
17 *
18 */
19
20 /** @file
21 *
22 * A red black tree
23 */
24
25 #ifndef OMPI_RB_TREE_H
26 #define OMPI_RB_TREE_H
27
28 #include "ompi_config.h"
29 #include <stdlib.h>
30 #include "ompi/constants.h"
31 #include "opal/class/opal_object.h"
32 #include "ompi/class/ompi_free_list.h"
33
34 BEGIN_C_DECLS
35 /*
36 * Data structures and datatypes
37 */
38
39 /**
40 * red and black enum
41 */
42 typedef enum {RED, BLACK} ompi_rb_tree_nodecolor_t;
43
44 /**
45 * node data structure
46 */
47 struct ompi_rb_tree_node_t
48 {
49 ompi_free_list_item_t super; /**< the parent class */
50 ompi_rb_tree_nodecolor_t color; /**< the node color */
51 struct ompi_rb_tree_node_t * parent;/**< the parent node, can be NULL */
52 struct ompi_rb_tree_node_t * left; /**< the left child - can be nill */
53 struct ompi_rb_tree_node_t * right; /**< the right child - can be nill */
54 void *key; /**< a pointer to the key */
55 void *value; /**< a pointer to the value */
56 };
57 typedef struct ompi_rb_tree_node_t ompi_rb_tree_node_t;
58
59 /**
60 * the compare function typedef. This function is used to compare 2 nodes.
61 */
62 typedef int (*ompi_rb_tree_comp_fn_t)(void *key1, void *key2);
63
64 /**
65 * the data structure that holds all the needed information about the tree.
66 */
67 struct ompi_rb_tree_t {
68 opal_object_t parent; /**< the parent class */
69 /* this root pointer doesn't actually point to the root of the tree.
70 * rather, it points to a sentinal node who's left branch is the real
71 * root of the tree. This is done to eliminate special cases */
72 ompi_rb_tree_node_t * root_ptr;/**< a pointer to the root of the tree */
73 ompi_rb_tree_node_t * nill; /**< the nill sentinal node */
74 ompi_rb_tree_comp_fn_t comp; /**< the compare function */
75 ompi_free_list_t free_list; /**< the free list to get the memory from */
76 size_t tree_size; /**< the size of the tree */
77 };
78 typedef struct ompi_rb_tree_t ompi_rb_tree_t;
79
80 /** declare the tree node as a class */
81 OMPI_DECLSPEC OBJ_CLASS_DECLARATION(ompi_rb_tree_node_t);
82 /** declare the tree as a class */
83 OMPI_DECLSPEC OBJ_CLASS_DECLARATION(ompi_rb_tree_t);
84
85 /* Function pointers for map traversal function */
86 /**
87 * this function is used for the ompi_rb_tree_traverse function.
88 * it is passed a pointer to the value for each node and, if it returns
89 * a one, the action function is called on that node. Otherwise, the node is ignored.
90 */
91 typedef int (*ompi_rb_tree_condition_fn_t)(void *);
92 /**
93 * this function is uused for the user to perform any action on the passed
94 * values. The first argument is the key and the second is the value.
95 * note that this function SHOULD NOT modify the keys, as that would
96 * mess up the tree.
97 */
98 typedef void (*ompi_rb_tree_action_fn_t)(void *, void *);
99
100 /*
101 * Public function protoypes
102 */
103
104 /**
105 * the construct function. creates the free list to get the nodes from
106 *
107 * @param object the tree that is to be used
108 *
109 * @retval NONE
110 */
111 OMPI_DECLSPEC void ompi_rb_tree_construct(opal_object_t * object);
112
113 /**
114 * the destruct function. tries to free the tree and destroys the free list
115 *
116 * @param object the tree object
117 */
118 OMPI_DECLSPEC void ompi_rb_tree_destruct(opal_object_t * object);
119
120 /**
121 * the function creates a new tree
122 *
123 * @param tree a pointer to an allocated area of memory for the main
124 * tree data structure.
125 * @param comp a pointer to the function to use for comaparing 2 nodes
126 *
127 * @retval OMPI_SUCCESS if it is successful
128 * @retval OMPI_ERR_TEMP_OUT_OF_RESOURCE if unsuccessful
129 */
130 OMPI_DECLSPEC int ompi_rb_tree_init(ompi_rb_tree_t * tree, ompi_rb_tree_comp_fn_t comp);
131
132
133 /**
134 * inserts a node into the tree
135 *
136 * @param tree a pointer to the tree data structure
137 * @param key the key for the node
138 * @param value the value for the node
139 *
140 * @retval OMPI_SUCCESS
141 * @retval OMPI_ERR_TEMP_OUT_OF_RESOURCE if unsuccessful
142 */
143 OMPI_DECLSPEC int ompi_rb_tree_insert(ompi_rb_tree_t *tree, void * key, void * value);
144
145 /**
146 * finds a value in the tree based on the passed key using passed
147 * compare function
148 *
149 * @param tree a pointer to the tree data structure
150 * @param key a pointer to the key
151 * @param compare function
152 *
153 * @retval pointer to the value if found
154 * @retval NULL if not found
155 */
156 OMPI_DECLSPEC void * ompi_rb_tree_find_with(ompi_rb_tree_t *tree, void *key, ompi_rb_tree_comp_fn_t compfn);
157
158 /**
159 * finds a value in the tree based on the passed key
160 *
161 * @param tree a pointer to the tree data structure
162 * @param key a pointer to the key
163 *
164 * @retval pointer to the value if found
165 * @retval NULL if not found
166 */
167 static inline void * ompi_rb_tree_find(ompi_rb_tree_t *tree, void *key)
168 {
169 return ompi_rb_tree_find_with(tree, key, tree->comp);
170 }
171
172 /**
173 * deletes a node based on its key
174 *
175 * @param tree a pointer to the tree data structure
176 * @param key a pointer to the key
177 *
178 * @retval OMPI_SUCCESS if the node is found and deleted
179 * @retval OMPI_ERR_NOT_FOUND if the node is not found
180 */
181 OMPI_DECLSPEC int ompi_rb_tree_delete(ompi_rb_tree_t *tree, void *key);
182
183 /**
184 * frees all the nodes on the tree
185 *
186 * @param tree a pointer to the tree data structure
187 *
188 * @retval OMPI_SUCCESS
189 */
190 OMPI_DECLSPEC int ompi_rb_tree_destroy(ompi_rb_tree_t *tree);
191
192 /**
193 * traverses the entire tree, performing the cond function on each of the
194 * values and if it returns one it performs the action function on the values
195 *
196 * @param tree a pointer to the tree
197 * @param cond a pointer to the condition function
198 * @param action a pointer to the action function
199 *
200 * @retval OMPI_SUCCESS
201 * @retval OMPI_ERROR if there is an error
202 */
203 OMPI_DECLSPEC int ompi_rb_tree_traverse(ompi_rb_tree_t *tree,
204 ompi_rb_tree_condition_fn_t cond,
205 ompi_rb_tree_action_fn_t action);
206
207 /**
208 * returns the size of the tree
209 *
210 * @param tree a pointer to the tree data structure
211 *
212 * @retval int the nuber of items on the tree
213 */
214 OMPI_DECLSPEC int ompi_rb_tree_size(ompi_rb_tree_t *tree);
215
216 END_C_DECLS
217 #endif /* OMPI_RB_TREE_H */
218
ompi_rb_tree_destroy
OMPI_DECLSPEC int ompi_rb_tree_destroy(ompi_rb_tree_t *tree)
frees all the nodes on the tree
Definition: ompi_rb_tree.c:268
ompi_rb_tree_node_t::color
ompi_rb_tree_nodecolor_t color
the node color
Definition: ompi_rb_tree.h:50
ompi_rb_tree_init
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
Definition: ompi_rb_tree.c:70
ompi_rb_tree_delete
OMPI_DECLSPEC int ompi_rb_tree_delete(ompi_rb_tree_t *tree, void *key)
deletes a node based on its key
Definition: ompi_rb_tree.c:217
ompi_rb_tree_t::root_ptr
ompi_rb_tree_node_t * root_ptr
a pointer to the root of the tree
Definition: ompi_rb_tree.h:72
ompi_rb_tree_nodecolor_t
ompi_rb_tree_nodecolor_t
red and black enum
Definition: ompi_rb_tree.h:42
ompi_rb_tree_comp_fn_t
int(* ompi_rb_tree_comp_fn_t)(void *key1, void *key2)
the compare function typedef.
Definition: ompi_rb_tree.h:62
ompi_rb_tree_node_t
node data structure
Definition: ompi_rb_tree.h:47
ompi_rb_tree_t::comp
ompi_rb_tree_comp_fn_t comp
the compare function
Definition: ompi_rb_tree.h:74
ompi_rb_tree_destruct
OMPI_DECLSPEC void ompi_rb_tree_destruct(opal_object_t *object)
the destruct function.
Definition: ompi_rb_tree.c:60
ompi_rb_tree_size
OMPI_DECLSPEC int ompi_rb_tree_size(ompi_rb_tree_t *tree)
returns the size of the tree
Definition: ompi_rb_tree.c:531
ompi_rb_tree_t::tree_size
size_t tree_size
the size of the tree
Definition: ompi_rb_tree.h:76
ompi_rb_tree_node_t::right
struct ompi_rb_tree_node_t * right
the right child - can be nill
Definition: ompi_rb_tree.h:53
ompi_rb_tree_find
static void * ompi_rb_tree_find(ompi_rb_tree_t *tree, void *key)
finds a value in the tree based on the passed key
Definition: ompi_rb_tree.h:167
OBJ_CLASS_DECLARATION
OMPI_DECLSPEC OBJ_CLASS_DECLARATION(ompi_rb_tree_node_t)
declare the tree node as a class
ompi_rb_tree_construct
OMPI_DECLSPEC void ompi_rb_tree_construct(opal_object_t *object)
the construct function.
Definition: ompi_rb_tree.c:48
ompi_rb_tree_find_with
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
Definition: ompi_rb_tree.c:174
ompi_rb_tree_node_t::value
void * value
a pointer to the value
Definition: ompi_rb_tree.h:55
ompi_rb_tree_node_t::parent
struct ompi_rb_tree_node_t * parent
the parent node, can be NULL
Definition: ompi_rb_tree.h:51
ompi_rb_tree_t::nill
ompi_rb_tree_node_t * nill
the nill sentinal node
Definition: ompi_rb_tree.h:73
ompi_rb_tree_node_t::key
void * key
a pointer to the key
Definition: ompi_rb_tree.h:54
ompi_free_list_t
Definition: ompi_free_list.h:39
ompi_free_list_item_t
Definition: ompi_free_list.h:62
opal_object_t
Base object.
Definition: opal_object.h:182
ompi_rb_tree_condition_fn_t
int(* ompi_rb_tree_condition_fn_t)(void *)
this function is used for the ompi_rb_tree_traverse function.
Definition: ompi_rb_tree.h:91
ompi_rb_tree_t
the data structure that holds all the needed information about the tree.
Definition: ompi_rb_tree.h:67
ompi_rb_tree_t::free_list
ompi_free_list_t free_list
the free list to get the memory from
Definition: ompi_rb_tree.h:75
ompi_rb_tree_node_t::super
ompi_free_list_item_t super
the parent class
Definition: ompi_rb_tree.h:49
ompi_rb_tree_t::parent
opal_object_t parent
the parent class
Definition: ompi_rb_tree.h:68
opal_object.h
A simple C-language object-oriented system with single inheritance and ownership-based memory managem...
ompi_rb_tree_insert
OMPI_DECLSPEC int ompi_rb_tree_insert(ompi_rb_tree_t *tree, void *key, void *value)
inserts a node into the tree
Definition: ompi_rb_tree.c:110
ompi_rb_tree_action_fn_t
void(* ompi_rb_tree_action_fn_t)(void *, void *)
this function is uused for the user to perform any action on the passed values.
Definition: ompi_rb_tree.h:98
ompi_rb_tree_node_t::left
struct ompi_rb_tree_node_t * left
the left child - can be nill
Definition: ompi_rb_tree.h:52
ompi_rb_tree_traverse
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 i...
Definition: ompi_rb_tree.c:439