OpenMPI 0.1.1

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

- File List
- Globals

opal_tree.h
Go to the documentation of this file.
1 /*
2 * Copyright (c) 2011 Oracle and/or its affiliates. All rights reserved.
3 * $COPYRIGHT$
4 *
5 * Additional copyrights may follow
6 *
7 * $HEADER$
8 */
9 /**
10 * @file
11 *
12 * The opal_tree_t interface is used to provide a generic
13 * tree list container for Open MPI. It was inspired by the opal_list_t
14 * interface but instead of organizing items in a doubly-linked list
15 * fashion, we order them in a finite tree structure.
16 *
17 * The general idea is a user creates an class instance that has two
18 * components. A tree structure component as defined by opal_tree_item_t
19 * that links all the items together to form the tree. Then there is
20 * a user specific data component which the user defines what is stored at
21 * each item. When a user create a type to be used for a OBJ_CLASS_INSTANCE
22 * it will contain the opal_tree_item_t followed by any user specific
23 * data. Then the opal_tree_item_t objects can be put in an
24 * opal_tree_t. Hence, you create a new type that derives from
25 * opal_tree_item_t; this new type can then be used with opal_tree_t
26 * containers.
27 *
28 * NOTE: opal_tree_item_t instances can only be on \em one tree at a
29 * time. Specifically, if you add an opal_tree_item_t to one tree,
30 * and then add it to another tree (without first removing it from the
31 * first tree), you will effectively be hosing the first tree. You
32 * have been warned.
33 *
34 * If OPAL_ENABLE_DEBUG is true, a bunch of checks occur, including
35 * some spot checks for a debugging reference count in an attempt to
36 * ensure that an opal_tree_item_t is only one *one* tree at a time.
37 * Given the highly concurrent nature of this class, these spot checks
38 * cannot guarantee that an item is only one tree at a time.
39 * Specifically, since it is a desirable attribute of this class to
40 * not use locks for normal operations, it is possible that two
41 * threads may [erroneously] modify an opal_tree_item_t concurrently.
42 *
43 * The only way to guarantee that a debugging reference count is valid
44 * for the duration of an operation is to lock the item_t during the
45 * operation. But this fundamentally changes the desirable attribute
46 * of this class (i.e., no locks). So all we can do is spot-check the
47 * reference count in a bunch of places and check that it is still the
48 * value that we think it should be. But this doesn't mean that you
49 * can run into "unlucky" cases where two threads are concurrently
50 * modifying an item_t, but all the spot checks still return the
51 * "right" values. All we can do is hope that we have enough spot
52 * checks to statistically drive down the possibility of the unlucky
53 * cases happening.
54 */
55
56 #ifndef OPAL_TREE_H
57 #define OPAL_TREE_H
58
59 #include "opal_config.h"
60 #include <stdio.h>
61 #include <stdlib.h>
62 #include "opal/class/opal_object.h"
63 #include "opal/dss/dss.h"
64
65 #if OPAL_ENABLE_DEBUG
66 /* Need atomics for debugging (reference counting) */
67 #include "opal/sys/atomic.h"
68 #include "opal/threads/mutex.h"
69 #endif
70
71 BEGIN_C_DECLS
72
73 /**
74 * \internal
75 *
76 * The class for the tree container.
77 */
78 OPAL_DECLSPEC OBJ_CLASS_DECLARATION(opal_tree_t);
79 /**
80 * \internal
81 *
82 * Base class for items that are put in tree containers.
83 */
84 OPAL_DECLSPEC OBJ_CLASS_DECLARATION(opal_tree_item_t);
85
86 /**
87 * \internal
88 *
89 * Struct of an opal_tree_item_t
90 */
91 typedef struct opal_tree_item_t
92 {
93 /** Generic parent class for all Open MPI objects */
94 opal_object_t super;
95 /** Pointer to the tree this item belongs to */
96 struct opal_tree_t *opal_tree_container;
97 /* Parent info */
98 /** Pointer to parent tree item */
99 struct opal_tree_item_t *opal_tree_parent;
100 /** Depth from the root item in tree */
101 unsigned opal_tree_num_ancestors;
102 /* Logical rank we are compared to other siblings */
103 unsigned opal_tree_sibling_rank;
104 /** Pointer to next item below same parent (or NULL if this is the
105 leftmost sibling) */
106 struct opal_tree_item_t *opal_tree_next_sibling;
107 /** Pointer to previous item below same parent (or NULL if this is
108 the rightmost sibling) */
109 struct opal_tree_item_t *opal_tree_prev_sibling;
110
111 /* Children info */
112 /** Number of children */
113 unsigned opal_tree_num_children;
114 /** Pointer to first child item, or NULL if there are no children */
115 struct opal_tree_item_t *opal_tree_first_child;
116 /** Pointer to last child item, or NULL if there are no children */
117 struct opal_tree_item_t *opal_tree_last_child;
118
119 #if OPAL_ENABLE_DEBUG
120 /** Atomic reference count for debugging */
121 int32_t opal_tree_item_refcount;
122 /** The tree this item belong to */
123 struct opal_tree_t* opal_tree_item_belong_to;
124 #endif
125 } opal_tree_item_t;
126
127 /**
128 * Check to see if item's user specific data matches key
129 *
130 * @param item - The item we want to check to see if it matches key
131 * @param key - The opaque key that we want the match function to check
132 * in the item's user specific data.
133 *
134 * @returns 0 - If item's user specific data matches key
135 * @returns non-zero - If item's user specific data does not match key
136 *
137 * This function is implemented by the code that constructs the tree
138 * and initialized the pointer by the call to opal_tree_init.
139 *
140 */
141 typedef int (*opal_tree_comp_fn_t)(opal_tree_item_t *item, void *key);
142
143 /**
144 * The serialize function typedef. This function is called by the
145 * opal tree serialize code to serialize a tree item's user specific
146 * data of a class type.
147 *
148 * @params item - item to serialize the user specific data from
149 * @params buffer - the opal_buffer_t to store the serialized data in.
150 *
151 * @returns OPAL_SUCCESS - when successfully serialized item
152 */
153 typedef int (*opal_tree_item_serialize_fn_t)(opal_tree_item_t *item,
154 opal_buffer_t *buffer);
155
156 /**
157 * The deserialize function typedef. This function is called by the
158 * opal tree deserialize code to deserialize a tree item's user
159 * specific data.
160 *
161 * @params buffer - the opal_buffer_t to deserialized data.
162 * @params item - item to store the deserialized data into the user
163 * specific data
164 *
165 * @returns OPAL_SUCCESS - when successfully deserialized item
166 */
167 typedef int (*opal_tree_item_deserialize_fn_t)(opal_buffer_t *buffer,
168 opal_tree_item_t **item);
169
170 /**
171 * \internal
172 *
173 * Struct of an opal_tree_t
174 *
175 */
176 typedef struct opal_tree_t
177 {
178 /** Generic parent class for all Open MPI objects */
179 opal_object_t super;
180 /** Guard item of the tree that child points to root */
181 opal_tree_item_t opal_tree_sentinel;
182 /** Quick reference to the number of items in the tree */
183 volatile size_t opal_tree_num_items;
184 /** Function to compare two items in tree */
185 opal_tree_comp_fn_t comp;
186 /** Function to serialize tree item data */
187 opal_tree_item_serialize_fn_t serialize;
188 /** Function to deserialize tree item data */
189 opal_tree_item_deserialize_fn_t deserialize;
190 } opal_tree_t;
191
192 /** Macros to access items in the tree */
193
194 /**
195 * Get the parent of item in the tree.
196 *
197 * @param item A tree item.
198 *
199 * @returns The parent item in the tree
200 *
201 * This function is safe to be called with a null item pointer.
202 */
203 static inline opal_tree_item_t *opal_tree_get_parent(opal_tree_item_t *item)
204 {
205 return ((item) ? item->opal_tree_parent : NULL);
206 }
207
208 /**
209 * Get the next sibling item in the tree.
210 *
211 * @param item A tree item.
212 *
213 * @returns The next sibling item in the tree
214 *
215 * This function is safe to be called with a null item pointer.
216 */
217 static inline opal_tree_item_t *opal_tree_get_next_sibling(opal_tree_item_t
218 *item)
219 {
220 return ((item) ? item->opal_tree_next_sibling : NULL);
221 }
222
223
224 /**
225 * Get the previous sibling item in the tree.
226 *
227 * @param item A tree item.
228 *
229 * @returns The previous sibling item in the tree
230 *
231 * This function is safe to be called with a null item pointer.
232 */
233 static inline opal_tree_item_t *opal_tree_get_prev_sibling(opal_tree_item_t
234 *item)
235 {
236 return ((item) ? item->opal_tree_prev_sibling : NULL);
237 }
238
239 /**
240 * Get the first child item in the tree.
241 *
242 * @param item A tree item.
243 *
244 * @returns The first child item in the tree
245 *
246 * This function is safe to be called with a null item pointer.
247 *
248 */
249 static inline opal_tree_item_t *opal_tree_get_first_child(opal_tree_item_t
250 *item)
251 {
252 return ((item) ? item->opal_tree_first_child : NULL);
253 }
254
255 /**
256 * Get the last child item in the tree.
257 *
258 * @param item A tree item.
259 *
260 * @returns The last child item in the tree
261 *
262 * This function is safe to be called with a null item pointer.
263 *
264 */
265 static inline opal_tree_item_t *opal_tree_get_last_child(opal_tree_item_t
266 *item)
267 {
268 return ((item) ? item->opal_tree_last_child : NULL);
269 }
270
271 /**
272 * Check for empty tree
273 *
274 * @param tree The tree container
275 *
276 * @returns true if tree's size is 0, false otherwise
277 *
278 * This is an O(1) operation.
279 *
280 * This is an inlined function in compilers that support inlining,
281 * so it's usually a cheap operation.
282 *
283 */
284 static inline bool opal_tree_is_empty(opal_tree_t* tree)
285 {
286 #if OPAL_ENABLE_DEBUG
287 /* Spot check that the tree is a non-null pointer */
288 assert(NULL != tree);
289 #endif
290 return (tree->opal_tree_sentinel.opal_tree_first_child ==
291 &(tree->opal_tree_sentinel) ? true : false);
292 }
293
294
295 /**
296 * Return the root item on the tree (does not remove it).
297 *
298 * @param tree The tree container
299 *
300 * @returns A pointer to the first item in the tree
301 *
302 * This is an O(1) operation to return the first item in the tree.
303 *
304 * This is an inlined function in compilers that support inlining, so
305 * it's usually a cheap operation.
306 *
307 */
308 static inline opal_tree_item_t* opal_tree_get_root(opal_tree_t* tree)
309 {
310 opal_tree_item_t* item;
311 #if OPAL_ENABLE_DEBUG
312 assert(NULL != tree);
313 #endif
314 item = tree->opal_tree_sentinel.opal_tree_first_child;
315 #if OPAL_ENABLE_DEBUG
316 /* Spot check: ensure that the first item is only on one list */
317 assert(1 == item->opal_tree_item_refcount);
318 assert(tree == item->opal_tree_item_belong_to );
319 #endif
320 return item;
321 }
322
323 /**
324 * Return the number of items in a tree
325 *
326 * @param tree The tree container
327 *
328 * @returns The size of the tree (size_t)
329 *
330 * This is an O(1) (in non-debug mode) lookup to return the
331 * size of the list.
332 */
333 OPAL_DECLSPEC size_t opal_tree_get_size(opal_tree_t* tree);
334
335
336 /* Functions to manage the tree */
337 /**
338 * Initialize tree container; must be called before using
339 * the tree.
340 *
341 * @param tree The tree to initialize
342 * @param comp Comparison function to attach to tree.
343 * @param serialize Serialization function to attach to tree.
344 * @param deserialize De-serialization function to attach to tree.
345 *
346 */
347 OPAL_DECLSPEC void opal_tree_init(opal_tree_t *tree,
348 opal_tree_comp_fn_t comp,
349 opal_tree_item_serialize_fn_t serialize,
350 opal_tree_item_deserialize_fn_t deserialize);
351
352 /**
353 * Add new item as child to its parent item
354 *
355 * @param parent_item pointer to what parent the new item belongs to
356 * @param new_item the item to be added as a child to parent_item
357 *
358 * The new_item is added at the end of the child list of the parent_item.
359 */
360 OPAL_DECLSPEC void opal_tree_add_child(opal_tree_item_t *parent_item,
361 opal_tree_item_t *new_item);
362
363 /**
364 * Remove an item and everything below from a tree.
365 *
366 * @param item The item at the top of subtree to remove
367 *
368 * @returns A pointer to the item on the list previous to the one
369 * that was removed.
370 *
371 * This is an O(1) operation to remove an item from the tree. The
372 * item and all children below it will be removed from the tree. This
373 * means the item's siblings pointers and potentially the parents first
374 * and last pointers will be updated to skip over the item. The tree container
375 * will also have its num_items adjusted to reflect the number of items
376 * that were removed. The tree item (and all children below it) that is
377 * returned is now "owned" by the caller -- they are responsible for
378 * OBJ_RELEASE()'ing it.
379 *
380 * With ENABLE_DEBUG on this routine will validate whether the item is actually
381 * in the tree before doing pointer manipulation.
382 */
383 OPAL_DECLSPEC opal_tree_item_t *opal_tree_remove_subtree(opal_tree_item_t *item);
384 /**
385 * Serialize tree data
386 *
387 * @param start_item The item of a tree to start serializing data
388 * @param buffer The opal buffer that contains the serialized
389 * data stream of the tree
390 *
391 * @returns OPAL_SUCCESS if data has been successfully converted.
392 *
393 * This routine walks the tree starting at start_item until it has serialized
394 * all children items of start_item and creates a bytestream of data,
395 * using the opal_dss.pack routine, that can be sent over a network.
396 * The format of the bytestream represents the tree parent/child relationship
397 * of each item in the tree plus the data inside the tree. This routine calls
398 * the tree's serialization method to serialize the user specific data for
399 * each item.
400 *
401 */
402 OPAL_DECLSPEC int opal_tree_serialize(opal_tree_item_t *start_item,
403 opal_buffer_t *buffer);
404
405 /**
406 * De-serialize tree data
407 *
408 * @param buffer The opal buffer that is to be deserialized
409 * @param start_item The item in the tree the data should be
410 * deserialized into
411 *
412 * @returns Status of call OPAL_SUCCESS if everything worked
413 *
414 * This routine takes a bytestream that was created by the
415 * opal_tree_serialize() function and deserializes it into the
416 * tree given. If the tree already has data in it, this routine
417 * will start adding the new data as a new child of the root
418 * item. This routine calls the tree's de-serialization
419 * method to deserialize the user specific data for each item.
420 *
421 */
422 OPAL_DECLSPEC int opal_tree_deserialize(opal_buffer_t *buffer,
423 opal_tree_item_t *start_item);
424
425 /* Functions to search for items on tree */
426 /**
427 * Return the next tree item that matches key provided
428 *
429 * @param item The item to start the find from
430 * @param key the key we are wanting to match with
431 *
432 * @returns A pointer to the next item that in the tree (starting from item)
433 * that matches the key based on a depth first search of the tree. A null
434 * pointer is returned if we've reached the end of the tree and have not
435 * matched the key.
436 *
437 * This routine uses the tree container's comp function to determine the
438 * whether there is a match between the key and each item we search in the
439 * tree. This means the actual tree type constructed determines how the
440 * compare is done with the key. In the case no compare routine is given
441 * and NULL pointer is always returned for this function.
442 *
443 */
444 OPAL_DECLSPEC opal_tree_item_t *opal_tree_find_with(opal_tree_item_t *item,
445 void *key);
446 END_C_DECLS
447
448 #endif /* OPAL_TREE_H */
opal_tree_t::opal_tree_num_items
volatile size_t opal_tree_num_items
Quick reference to the number of items in the tree.
Definition: opal_tree.h:183
opal_tree_get_root
static opal_tree_item_t * opal_tree_get_root(opal_tree_t *tree)
Return the root item on the tree (does not remove it).
Definition: opal_tree.h:308
opal_tree_item_t::opal_tree_first_child
struct opal_tree_item_t * opal_tree_first_child
Pointer to first child item, or NULL if there are no children.
Definition: opal_tree.h:115
opal_tree_item_t::opal_tree_num_ancestors
unsigned opal_tree_num_ancestors
Depth from the root item in tree.
Definition: opal_tree.h:101
opal_tree_get_prev_sibling
static opal_tree_item_t * opal_tree_get_prev_sibling(opal_tree_item_t *item)
Get the previous sibling item in the tree.
Definition: opal_tree.h:233
opal_tree_item_serialize_fn_t
int(* opal_tree_item_serialize_fn_t)(opal_tree_item_t *item, opal_buffer_t *buffer)
The serialize function typedef.
Definition: opal_tree.h:153
opal_tree_item_t::opal_tree_container
struct opal_tree_t * opal_tree_container
Pointer to the tree this item belongs to.
Definition: opal_tree.h:96
opal_tree_item_t
Definition: opal_tree.h:91
opal_tree_item_t::opal_tree_num_children
unsigned opal_tree_num_children
Number of children.
Definition: opal_tree.h:113
opal_tree_t::comp
opal_tree_comp_fn_t comp
Function to compare two items in tree.
Definition: opal_tree.h:185
opal_tree_t
Definition: opal_tree.h:176
opal_tree_t::opal_tree_sentinel
opal_tree_item_t opal_tree_sentinel
Guard item of the tree that child points to root.
Definition: opal_tree.h:181
opal_tree_item_t::super
opal_object_t super
Generic parent class for all Open MPI objects.
Definition: opal_tree.h:94
opal_tree_get_size
OPAL_DECLSPEC size_t opal_tree_get_size(opal_tree_t *tree)
Return the number of items in a tree.
Definition: opal_tree.c:141
opal_tree_remove_subtree
OPAL_DECLSPEC opal_tree_item_t * opal_tree_remove_subtree(opal_tree_item_t *item)
Remove an item and everything below from a tree.
Definition: opal_tree.c:235
opal_tree_find_with
OPAL_DECLSPEC opal_tree_item_t * opal_tree_find_with(opal_tree_item_t *item, void *key)
Return the next tree item that matches key provided.
Definition: opal_tree.c:446
opal_tree_t::deserialize
opal_tree_item_deserialize_fn_t deserialize
Function to deserialize tree item data.
Definition: opal_tree.h:189
opal_tree_t::serialize
opal_tree_item_serialize_fn_t serialize
Function to serialize tree item data.
Definition: opal_tree.h:187
opal_tree_item_t::opal_tree_last_child
struct opal_tree_item_t * opal_tree_last_child
Pointer to last child item, or NULL if there are no children.
Definition: opal_tree.h:117
opal_tree_t::super
opal_object_t super
Generic parent class for all Open MPI objects.
Definition: opal_tree.h:179
opal_tree_get_parent
static opal_tree_item_t * opal_tree_get_parent(opal_tree_item_t *item)
Macros to access items in the tree.
Definition: opal_tree.h:203
opal_tree_get_next_sibling
static opal_tree_item_t * opal_tree_get_next_sibling(opal_tree_item_t *item)
Get the next sibling item in the tree.
Definition: opal_tree.h:217
opal_tree_comp_fn_t
int(* opal_tree_comp_fn_t)(opal_tree_item_t *item, void *key)
Check to see if item's user specific data matches key.
Definition: opal_tree.h:141
opal_tree_item_t::opal_tree_prev_sibling
struct opal_tree_item_t * opal_tree_prev_sibling
Pointer to previous item below same parent (or NULL if this is the rightmost sibling) ...
Definition: opal_tree.h:109
opal_tree_add_child
OPAL_DECLSPEC void opal_tree_add_child(opal_tree_item_t *parent_item, opal_tree_item_t *new_item)
Add new item as child to its parent item.
Definition: opal_tree.c:170
opal_tree_get_first_child
static opal_tree_item_t * opal_tree_get_first_child(opal_tree_item_t *item)
Get the first child item in the tree.
Definition: opal_tree.h:249
opal_object_t
Base object.
Definition: opal_object.h:182
opal_tree_init
OPAL_DECLSPEC void opal_tree_init(opal_tree_t *tree, opal_tree_comp_fn_t comp, opal_tree_item_serialize_fn_t serialize, opal_tree_item_deserialize_fn_t deserialize)
Initialize tree container; must be called before using the tree.
Definition: opal_tree.c:113
opal_tree_item_t::opal_tree_next_sibling
struct opal_tree_item_t * opal_tree_next_sibling
Pointer to next item below same parent (or NULL if this is the leftmost sibling)
Definition: opal_tree.h:106
opal_tree_deserialize
OPAL_DECLSPEC int opal_tree_deserialize(opal_buffer_t *buffer, opal_tree_item_t *start_item)
De-serialize tree data.
Definition: opal_tree.c:409
opal_tree_get_last_child
static opal_tree_item_t * opal_tree_get_last_child(opal_tree_item_t *item)
Get the last child item in the tree.
Definition: opal_tree.h:265
opal_buffer_t
Structure for holding a buffer to be used with the RML or OOB subsystems.
Definition: dss_types.h:159
opal_tree_item_t::opal_tree_parent
struct opal_tree_item_t * opal_tree_parent
Pointer to parent tree item.
Definition: opal_tree.h:99
atomic.h
Atomic operations.
opal_tree_is_empty
static bool opal_tree_is_empty(opal_tree_t *tree)
Check for empty tree.
Definition: opal_tree.h:284
mutex.h
Mutual exclusion functions.
opal_object.h
A simple C-language object-oriented system with single inheritance and ownership-based memory managem...
opal_tree_serialize
OPAL_DECLSPEC int opal_tree_serialize(opal_tree_item_t *start_item, opal_buffer_t *buffer)
Serialize tree data.
Definition: opal_tree.c:339
dss.h
Data packing subsystem.
OBJ_CLASS_DECLARATION
#define OBJ_CLASS_DECLARATION(NAME)
Declaration for class descriptor.
Definition: opal_object.h:236
opal_tree_item_deserialize_fn_t
int(* opal_tree_item_deserialize_fn_t)(opal_buffer_t *buffer, opal_tree_item_t **item)
The deserialize function typedef.
Definition: opal_tree.h:167