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-2018 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 thread-safe interval tree derived from opal_rb_tree_t
26 */
27
28 #ifndef OPAL_INTERVAL_TREE_H
29 #define OPAL_INTERVAL_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 {OPAL_INTERVAL_TREE_COLOR_RED, OPAL_INTERVAL_TREE_COLOR_BLACK} opal_interval_tree_nodecolor_t;
46
47 /**
48 * node data structure
49 */
50 struct opal_interval_tree_node_t
51 {
52 opal_free_list_item_t super; /**< the parent class */
53 opal_interval_tree_nodecolor_t color; /**< the node color */
54 struct opal_interval_tree_node_t *parent;/**< the parent node, can be NULL */
55 struct opal_interval_tree_node_t *left; /**< the left child - can be nill */
56 struct opal_interval_tree_node_t *right; /**< the right child - can be nill */
57 /** edit epoch associated with this node */
58 uint32_t epoch;
59 /** data for this interval */
60 void *data;
61 /** low value of this interval */
62 uint64_t low;
63 /** high value of this interval */
64 uint64_t high;
65 /** maximum value of all intervals in tree rooted at this node */
66 uint64_t max;
67 };
68 typedef struct opal_interval_tree_node_t opal_interval_tree_node_t;
69
70 /** maximum number of simultaneous readers */
71 #define OPAL_INTERVAL_TREE_MAX_READERS 128
72
73 /**
74 * the data structure that holds all the needed information about the tree.
75 */
76 struct opal_interval_tree_t {
77 opal_object_t super; /**< the parent class */
78 /* this root pointer doesn't actually point to the root of the tree.
79 * rather, it points to a sentinal node who's left branch is the real
80 * root of the tree. This is done to eliminate special cases */
81 opal_interval_tree_node_t root; /**< a pointer to the root of the tree */
82 opal_interval_tree_node_t nill; /**< the nill sentinal node */
83 opal_free_list_t free_list; /**< the free list to get the memory from */
84 opal_list_t gc_list; /**< list of nodes that need to be released */
85 uint32_t epoch; /**< current update epoch */
86 opal_atomic_size_t tree_size; /**< the current size of the tree */
87 opal_atomic_int32_t lock; /**< update lock */
88 opal_atomic_int32_t reader_count; /**< current highest reader slot to check */
89 volatile uint32_t reader_id; /**< next reader slot to check */
90 opal_atomic_uint32_t reader_epochs[OPAL_INTERVAL_TREE_MAX_READERS];
91 };
92 typedef struct opal_interval_tree_t opal_interval_tree_t;
93
94 /** declare the tree node as a class */
95 OPAL_DECLSPEC OBJ_CLASS_DECLARATION(opal_interval_tree_node_t);
96 /** declare the tree as a class */
97 OPAL_DECLSPEC OBJ_CLASS_DECLARATION(opal_interval_tree_t);
98
99 /* Function pointers for map traversal function */
100 /**
101 * this function is used for the opal_interval_tree_traverse function.
102 * it is passed a pointer to the value for each node and, if it returns
103 * a one, the action function is called on that node. Otherwise, the node is ignored.
104 */
105 typedef int (*opal_interval_tree_condition_fn_t)(void *);
106 /**
107 * this function is used for the user to perform any action on the passed
108 * values. The first argument is the key and the second is the value.
109 * note that this function SHOULD NOT modify the keys, as that would
110 * mess up the tree.
111 */
112 typedef int (*opal_interval_tree_action_fn_t)(uint64_t low, uint64_t high, void *data, void *ctx);
113
114 /*
115 * Public function protoypes
116 */
117
118 /**
119 * the function creates a new tree
120 *
121 * @param tree a pointer to an allocated area of memory for the main
122 * tree data structure.
123 * @param comp a pointer to the function to use for comaparing 2 nodes
124 *
125 * @retval OPAL_SUCCESS if it is successful
126 * @retval OPAL_ERR_TEMP_OUT_OF_RESOURCE if unsuccessful
127 */
128 OPAL_DECLSPEC int opal_interval_tree_init(opal_interval_tree_t * tree);
129
130
131 /**
132 * inserts a node into the tree
133 *
134 * @param tree a pointer to the tree data structure
135 * @param key the key for the node
136 * @param value the value for the node
137 *
138 * @retval OPAL_SUCCESS
139 * @retval OPAL_ERR_TEMP_OUT_OF_RESOURCE if unsuccessful
140 */
141 OPAL_DECLSPEC int opal_interval_tree_insert(opal_interval_tree_t *tree, void *value, uint64_t low, uint64_t high);
142
143 /**
144 * finds a value in the tree based on the passed key using passed
145 * compare function
146 *
147 * @param tree a pointer to the tree data structure
148 * @param key a pointer to the key
149 * @param compare function
150 *
151 * @retval pointer to the value if found
152 * @retval NULL if not found
153 */
154 OPAL_DECLSPEC void *opal_interval_tree_find_overlapping (opal_interval_tree_t *tree, uint64_t low, uint64_t high);
155
156 /**
157 * deletes a node based on its interval
158 *
159 * @param tree a pointer to the tree data structure
160 * @param low low value of interval
161 * @param high high value of interval
162 * @param data data to match (NULL for any)
163 *
164 * @retval OPAL_SUCCESS if the node is found and deleted
165 * @retval OPAL_ERR_NOT_FOUND if the node is not found
166 *
167 * This function finds and deletes an interval from the tree that exactly matches
168 * the given range.
169 */
170 OPAL_DECLSPEC int opal_interval_tree_delete(opal_interval_tree_t *tree, uint64_t low, uint64_t high, void *data);
171
172 /**
173 * frees all the nodes on the tree
174 *
175 * @param tree a pointer to the tree data structure
176 *
177 * @retval OPAL_SUCCESS
178 */
179 OPAL_DECLSPEC int opal_interval_tree_destroy(opal_interval_tree_t *tree);
180
181 /**
182 * traverses the entire tree, performing the cond function on each of the
183 * values and if it returns one it performs the action function on the values
184 *
185 * @param tree a pointer to the tree
186 * @param low low value of interval
187 * @param high high value of interval
188 * @param partial_ok traverse nodes that parially overlap the given range
189 * @param action a pointer to the action function
190 * @param ctx context to pass to action function
191 *
192 * @retval OPAL_SUCCESS
193 * @retval OPAL_ERROR if there is an error
194 */
195 OPAL_DECLSPEC int opal_interval_tree_traverse (opal_interval_tree_t *tree, uint64_t low, uint64_t high,
196 bool complete, opal_interval_tree_action_fn_t action, void *ctx);
197
198 /**
199 * returns the size of the tree
200 *
201 * @param tree a pointer to the tree data structure
202 *
203 * @retval int the nuber of items on the tree
204 */
205 OPAL_DECLSPEC size_t opal_interval_tree_size (opal_interval_tree_t *tree);
206
207 /**
208 * Diagnostic function to get the max depth of an interval tree.
209 *
210 * @param[in] tree opal interval tree pointer
211 *
212 * This is an expensive function that walks the entire tree to find the
213 * maximum depth. For a valid interval tree this depth will always be
214 * O(log(n)) where n is the number of intervals in the tree.
215 */
216 OPAL_DECLSPEC size_t opal_interval_tree_depth (opal_interval_tree_t *tree);
217
218 /**
219 * Diagnostic function that can be used to verify that an interval tree
220 * is valid.
221 *
222 * @param[in] tree opal interval tree pointer
223 *
224 * @returns true if the tree is a valid interval tree
225 * @returns false otherwise
226 */
227 OPAL_DECLSPEC bool opal_interval_tree_verify (opal_interval_tree_t *tree);
228
229 /**
230 * Dump a DOT representation of the interval tree
231 *
232 * @param[in] tree opal interval tree pointer
233 * @param[in] path output file path
234 *
235 * This function dumps the tree and includes: color, data value, interval, and sub-tree
236 * min and max.
237 */
238 OPAL_DECLSPEC int opal_interval_tree_dump (opal_interval_tree_t *tree, const char *path);
239
240 END_C_DECLS
241 #endif /* OPAL_INTERVAL_TREE_H */