OpenMPI  0.1.1
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  */
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 */
95  /** Pointer to the tree this item belongs to */
97  /* Parent info */
98  /** Pointer to parent tree item */
100  /** Depth from the root item in tree */
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) */
107  /** Pointer to previous item below same parent (or NULL if this is
108  the rightmost sibling) */
110 
111  /* Children info */
112  /** Number of children */
114  /** Pointer to first child item, or NULL if there are no children */
116  /** Pointer to last child item, or NULL if there are no children */
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
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  */
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  */
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 */
180  /** Guard item of the tree that child points to root */
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 */
186  /** Function to serialize tree item data */
188  /** Function to deserialize tree item data */
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  */
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  */
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  */
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  */
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  */
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
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  */
309 {
310  opal_tree_item_t* item;
311 #if OPAL_ENABLE_DEBUG
312  assert(NULL != tree);
313 #endif
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,
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  */
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  */
445  void *key);
446 END_C_DECLS
447 
448 #endif /* OPAL_TREE_H */
volatile size_t opal_tree_num_items
Quick reference to the number of items in the tree.
Definition: opal_tree.h:183
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
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
unsigned opal_tree_num_ancestors
Depth from the root item in tree.
Definition: opal_tree.h:101
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
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
struct opal_tree_t * opal_tree_container
Pointer to the tree this item belongs to.
Definition: opal_tree.h:96
Definition: opal_tree.h:91
unsigned opal_tree_num_children
Number of children.
Definition: opal_tree.h:113
opal_tree_comp_fn_t comp
Function to compare two items in tree.
Definition: opal_tree.h:185
Definition: opal_tree.h:176
opal_tree_item_t opal_tree_sentinel
Guard item of the tree that child points to root.
Definition: opal_tree.h:181
opal_object_t super
Generic parent class for all Open MPI objects.
Definition: opal_tree.h:94
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_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_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_item_deserialize_fn_t deserialize
Function to deserialize tree item data.
Definition: opal_tree.h:189
opal_tree_item_serialize_fn_t serialize
Function to serialize tree item data.
Definition: opal_tree.h:187
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_object_t super
Generic parent class for all Open MPI objects.
Definition: opal_tree.h:179
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
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
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
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_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
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
Base object.
Definition: opal_object.h:182
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
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_DECLSPEC int opal_tree_deserialize(opal_buffer_t *buffer, opal_tree_item_t *start_item)
De-serialize tree data.
Definition: opal_tree.c:409
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
Structure for holding a buffer to be used with the RML or OOB subsystems.
Definition: dss_types.h:159
struct opal_tree_item_t * opal_tree_parent
Pointer to parent tree item.
Definition: opal_tree.h:99
Atomic operations.
static bool opal_tree_is_empty(opal_tree_t *tree)
Check for empty tree.
Definition: opal_tree.h:284
Mutual exclusion functions.
A simple C-language object-oriented system with single inheritance and ownership-based memory managem...
OPAL_DECLSPEC int opal_tree_serialize(opal_tree_item_t *start_item, opal_buffer_t *buffer)
Serialize tree data.
Definition: opal_tree.c:339
Data packing subsystem.
#define OBJ_CLASS_DECLARATION(NAME)
Declaration for class descriptor.
Definition: opal_object.h:236
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