OpenMPI  0.1.1
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  */
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 };
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  */
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 */
82 /** declare the tree as a class */
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  */
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,
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_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_nodecolor_t color
the node color
Definition: ompi_rb_tree.h:50
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_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_node_t * root_ptr
a pointer to the root of the tree
Definition: ompi_rb_tree.h:72
ompi_rb_tree_nodecolor_t
red and black enum
Definition: ompi_rb_tree.h:42
int(* ompi_rb_tree_comp_fn_t)(void *key1, void *key2)
the compare function typedef.
Definition: ompi_rb_tree.h:62
node data structure
Definition: ompi_rb_tree.h:47
ompi_rb_tree_comp_fn_t comp
the compare function
Definition: ompi_rb_tree.h:74
OMPI_DECLSPEC void ompi_rb_tree_destruct(opal_object_t *object)
the destruct function.
Definition: ompi_rb_tree.c:60
OMPI_DECLSPEC int ompi_rb_tree_size(ompi_rb_tree_t *tree)
returns the size of the tree
Definition: ompi_rb_tree.c:531
size_t tree_size
the size of the tree
Definition: ompi_rb_tree.h:76
struct ompi_rb_tree_node_t * right
the right child - can be nill
Definition: ompi_rb_tree.h:53
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
OMPI_DECLSPEC OBJ_CLASS_DECLARATION(ompi_rb_tree_node_t)
declare the tree node as a class
OMPI_DECLSPEC void ompi_rb_tree_construct(opal_object_t *object)
the construct function.
Definition: ompi_rb_tree.c:48
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
void * value
a pointer to the value
Definition: ompi_rb_tree.h:55
struct ompi_rb_tree_node_t * parent
the parent node, can be NULL
Definition: ompi_rb_tree.h:51
ompi_rb_tree_node_t * nill
the nill sentinal node
Definition: ompi_rb_tree.h:73
void * key
a pointer to the key
Definition: ompi_rb_tree.h:54
Definition: ompi_free_list.h:39
Definition: ompi_free_list.h:62
Base object.
Definition: opal_object.h:182
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
the data structure that holds all the needed information about the tree.
Definition: ompi_rb_tree.h:67
ompi_free_list_t free_list
the free list to get the memory from
Definition: ompi_rb_tree.h:75
ompi_free_list_item_t super
the parent class
Definition: ompi_rb_tree.h:49
opal_object_t parent
the parent class
Definition: ompi_rb_tree.h:68
A simple C-language object-oriented system with single inheritance and ownership-based memory managem...
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
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
struct ompi_rb_tree_node_t * left
the left child - can be nill
Definition: ompi_rb_tree.h:52
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