1 /* -*- Mode: C; c-basic-offset:4 ; indent-tabs-mode:nil -*- */
2 /*
3 * Copyright (c) 2004-2005 The Trustees of Indiana University and Indiana
4 * University Research and Technology
5 * Corporation. All rights reserved.
6 * Copyright (c) 2004-2005 The University of Tennessee and The University
7 * of Tennessee Research Foundation. All rights
8 * reserved.
9 * Copyright (c) 2004-2005 High Performance Computing Center Stuttgart,
10 * University of Stuttgart. All rights reserved.
11 * Copyright (c) 2004-2005 The Regents of the University of California.
12 * All rights reserved.
13 * Copyright (c) 2015 Los Alamos National Security, LLC. All rights
14 * reserved.
15 * $COPYRIGHT$
16 *
17 * Additional copyrights may follow
18 *
19 * $HEADER$
20 *
21 */
22
23 /** @file
24 *
25 * A red black tree
26 */
27
28 #ifndef OPAL_RB_TREE_H
29 #define OPAL_RB_TREE_H
30
31 #include "opal_config.h"
32 #include <stdlib.h>
33 #include "opal/constants.h"
34 #include "opal/class/opal_object.h"
35 #include "opal/class/opal_free_list.h"
36
37 BEGIN_C_DECLS
38 /*
39 * Data structures and datatypes
40 */
41
42 /**
43 * red and black enum
44 */
45 typedef enum {RED, BLACK} opal_rb_tree_nodecolor_t;
46
47 /**
48 * node data structure
49 */
50 struct opal_rb_tree_node_t
51 {
52 opal_free_list_item_t super; /**< the parent class */
53 opal_rb_tree_nodecolor_t color; /**< the node color */
54 struct opal_rb_tree_node_t * parent;/**< the parent node, can be NULL */
55 struct opal_rb_tree_node_t * left; /**< the left child - can be nill */
56 struct opal_rb_tree_node_t * right; /**< the right child - can be nill */
57 void *key; /**< a pointer to the key */
58 void *value; /**< a pointer to the value */
59 };
60 typedef struct opal_rb_tree_node_t opal_rb_tree_node_t;
61
62 /**
63 * the compare function typedef. This function is used to compare 2 nodes.
64 */
65 typedef int (*opal_rb_tree_comp_fn_t)(void *key1, void *key2);
66
67 /**
68 * the data structure that holds all the needed information about the tree.
69 */
70 struct opal_rb_tree_t {
71 opal_object_t parent; /**< the parent class */
72 /* this root pointer doesn't actually point to the root of the tree.
73 * rather, it points to a sentinal node who's left branch is the real
74 * root of the tree. This is done to eliminate special cases */
75 opal_rb_tree_node_t * root_ptr; /**< a pointer to the root of the tree */
76 opal_rb_tree_node_t * nill; /**< the nill sentinal node */
77 opal_rb_tree_comp_fn_t comp; /**< the compare function */
78 opal_free_list_t free_list; /**< the free list to get the memory from */
79 size_t tree_size; /**< the size of the tree */
80 };
81 typedef struct opal_rb_tree_t opal_rb_tree_t;
82
83 /** declare the tree node as a class */
84 OPAL_DECLSPEC OBJ_CLASS_DECLARATION(opal_rb_tree_node_t);
85 /** declare the tree as a class */
86 OPAL_DECLSPEC OBJ_CLASS_DECLARATION(opal_rb_tree_t);
87
88 /* Function pointers for map traversal function */
89 /**
90 * this function is used for the opal_rb_tree_traverse function.
91 * it is passed a pointer to the value for each node and, if it returns
92 * a one, the action function is called on that node. Otherwise, the node is ignored.
93 */
94 typedef int (*opal_rb_tree_condition_fn_t)(void *);
95 /**
96 * this function is used for the user to perform any action on the passed
97 * values. The first argument is the key and the second is the value.
98 * note that this function SHOULD NOT modify the keys, as that would
99 * mess up the tree.
100 */
101 typedef void (*opal_rb_tree_action_fn_t)(void *, void *);
102
103 /*
104 * Public function protoypes
105 */
106
107 /**
108 * the function creates a new tree
109 *
110 * @param tree a pointer to an allocated area of memory for the main
111 * tree data structure.
112 * @param comp a pointer to the function to use for comaparing 2 nodes
113 *
114 * @retval OPAL_SUCCESS if it is successful
115 * @retval OPAL_ERR_TEMP_OUT_OF_RESOURCE if unsuccessful
116 */
117 OPAL_DECLSPEC int opal_rb_tree_init(opal_rb_tree_t * tree, opal_rb_tree_comp_fn_t comp);
118
119
120 /**
121 * inserts a node into the tree
122 *
123 * @param tree a pointer to the tree data structure
124 * @param key the key for the node
125 * @param value the value for the node
126 *
127 * @retval OPAL_SUCCESS
128 * @retval OPAL_ERR_TEMP_OUT_OF_RESOURCE if unsuccessful
129 */
130 OPAL_DECLSPEC int opal_rb_tree_insert(opal_rb_tree_t *tree, void * key, void * value);
131
132 /**
133 * finds a value in the tree based on the passed key using passed
134 * compare function
135 *
136 * @param tree a pointer to the tree data structure
137 * @param key a pointer to the key
138 * @param compare function
139 *
140 * @retval pointer to the value if found
141 * @retval NULL if not found
142 */
143 OPAL_DECLSPEC void * opal_rb_tree_find_with(opal_rb_tree_t *tree, void *key, opal_rb_tree_comp_fn_t compfn);
144
145 /**
146 * finds a value in the tree based on the passed key
147 *
148 * @param tree a pointer to the tree data structure
149 * @param key a pointer to the key
150 *
151 * @retval pointer to the value if found
152 * @retval NULL if not found
153 */
154 static inline void * opal_rb_tree_find(opal_rb_tree_t *tree, void *key)
155 {
156 return opal_rb_tree_find_with(tree, key, tree->comp);
157 }
158
159 /**
160 * deletes a node based on its key
161 *
162 * @param tree a pointer to the tree data structure
163 * @param key a pointer to the key
164 *
165 * @retval OPAL_SUCCESS if the node is found and deleted
166 * @retval OPAL_ERR_NOT_FOUND if the node is not found
167 */
168 OPAL_DECLSPEC int opal_rb_tree_delete(opal_rb_tree_t *tree, void *key);
169
170 /**
171 * frees all the nodes on the tree
172 *
173 * @param tree a pointer to the tree data structure
174 *
175 * @retval OPAL_SUCCESS
176 */
177 OPAL_DECLSPEC int opal_rb_tree_destroy(opal_rb_tree_t *tree);
178
179 /**
180 * traverses the entire tree, performing the cond function on each of the
181 * values and if it returns one it performs the action function on the values
182 *
183 * @param tree a pointer to the tree
184 * @param cond a pointer to the condition function
185 * @param action a pointer to the action function
186 *
187 * @retval OPAL_SUCCESS
188 * @retval OPAL_ERROR if there is an error
189 */
190 OPAL_DECLSPEC int opal_rb_tree_traverse(opal_rb_tree_t *tree,
191 opal_rb_tree_condition_fn_t cond,
192 opal_rb_tree_action_fn_t action);
193
194 /**
195 * returns the size of the tree
196 *
197 * @param tree a pointer to the tree data structure
198 *
199 * @retval int the nuber of items on the tree
200 */
201 OPAL_DECLSPEC int opal_rb_tree_size(opal_rb_tree_t *tree);
202
203 END_C_DECLS
204 #endif /* OPAL_RB_TREE_H */
205