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