OpenMPI
0.1.1
|
The opal_tree_t interface is used to provide a generic tree list container for Open MPI. More...
#include "opal_config.h"
#include <stdio.h>
#include <stdlib.h>
#include "opal/class/opal_object.h"
#include "opal/dss/dss.h"
Go to the source code of this file.
Data Structures | |
struct | opal_tree_item_t |
struct | opal_tree_t |
Typedefs | |
typedef struct opal_tree_item_t | opal_tree_item_t |
typedef int(* | opal_tree_comp_fn_t )(opal_tree_item_t *item, void *key) |
Check to see if item's user specific data matches key. More... | |
typedef int(* | opal_tree_item_serialize_fn_t )(opal_tree_item_t *item, opal_buffer_t *buffer) |
The serialize function typedef. More... | |
typedef int(* | opal_tree_item_deserialize_fn_t )(opal_buffer_t *buffer, opal_tree_item_t **item) |
The deserialize function typedef. More... | |
typedef struct opal_tree_t | opal_tree_t |
Functions | |
BEGIN_C_DECLS OPAL_DECLSPEC | OBJ_CLASS_DECLARATION (opal_tree_t) |
OPAL_DECLSPEC | OBJ_CLASS_DECLARATION (opal_tree_item_t) |
static opal_tree_item_t * | opal_tree_get_parent (opal_tree_item_t *item) |
Macros to access items in the tree. More... | |
static opal_tree_item_t * | opal_tree_get_next_sibling (opal_tree_item_t *item) |
Get the next sibling item in the tree. More... | |
static opal_tree_item_t * | opal_tree_get_prev_sibling (opal_tree_item_t *item) |
Get the previous sibling item in the tree. More... | |
static opal_tree_item_t * | opal_tree_get_first_child (opal_tree_item_t *item) |
Get the first child item in the tree. More... | |
static opal_tree_item_t * | opal_tree_get_last_child (opal_tree_item_t *item) |
Get the last child item in the tree. More... | |
static bool | opal_tree_is_empty (opal_tree_t *tree) |
Check for empty tree. More... | |
static opal_tree_item_t * | opal_tree_get_root (opal_tree_t *tree) |
Return the root item on the tree (does not remove it). More... | |
OPAL_DECLSPEC size_t | opal_tree_get_size (opal_tree_t *tree) |
Return the number of items in a tree. More... | |
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. More... | |
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. More... | |
OPAL_DECLSPEC opal_tree_item_t * | opal_tree_remove_subtree (opal_tree_item_t *item) |
Remove an item and everything below from a tree. More... | |
OPAL_DECLSPEC int | opal_tree_serialize (opal_tree_item_t *start_item, opal_buffer_t *buffer) |
Serialize tree data. More... | |
OPAL_DECLSPEC int | opal_tree_deserialize (opal_buffer_t *buffer, opal_tree_item_t *start_item) |
De-serialize tree data. More... | |
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. More... | |
The opal_tree_t interface is used to provide a generic tree list container for Open MPI.
It was inspired by the opal_list_t interface but instead of organizing items in a doubly-linked list fashion, we order them in a finite tree structure.
The general idea is a user creates an class instance that has two components. A tree structure component as defined by opal_tree_item_t that links all the items together to form the tree. Then there is a user specific data component which the user defines what is stored at each item. When a user create a type to be used for a OBJ_CLASS_INSTANCE it will contain the opal_tree_item_t followed by any user specific data. Then the opal_tree_item_t objects can be put in an opal_tree_t. Hence, you create a new type that derives from opal_tree_item_t; this new type can then be used with opal_tree_t containers.
NOTE: opal_tree_item_t instances can only be on one tree at a time. Specifically, if you add an opal_tree_item_t to one tree, and then add it to another tree (without first removing it from the first tree), you will effectively be hosing the first tree. You have been warned.
If OPAL_ENABLE_DEBUG is true, a bunch of checks occur, including some spot checks for a debugging reference count in an attempt to ensure that an opal_tree_item_t is only one one tree at a time. Given the highly concurrent nature of this class, these spot checks cannot guarantee that an item is only one tree at a time. Specifically, since it is a desirable attribute of this class to not use locks for normal operations, it is possible that two threads may [erroneously] modify an opal_tree_item_t concurrently.
The only way to guarantee that a debugging reference count is valid for the duration of an operation is to lock the item_t during the operation. But this fundamentally changes the desirable attribute of this class (i.e., no locks). So all we can do is spot-check the reference count in a bunch of places and check that it is still the value that we think it should be. But this doesn't mean that you can run into "unlucky" cases where two threads are concurrently modifying an item_t, but all the spot checks still return the "right" values. All we can do is hope that we have enough spot checks to statistically drive down the possibility of the unlucky cases happening.
typedef int(* opal_tree_comp_fn_t)(opal_tree_item_t *item, void *key) |
Check to see if item's user specific data matches key.
item | - The item we want to check to see if it matches key |
key | - The opaque key that we want the match function to check in the item's user specific data. |
This function is implemented by the code that constructs the tree and initialized the pointer by the call to opal_tree_init.
typedef int(* opal_tree_item_deserialize_fn_t)(opal_buffer_t *buffer, opal_tree_item_t **item) |
The deserialize function typedef.
This function is called by the opal tree deserialize code to deserialize a tree item's user specific data.
buffer - the opal_buffer_t to deserialized data. item - item to store the deserialized data into the user specific data
typedef int(* opal_tree_item_serialize_fn_t)(opal_tree_item_t *item, opal_buffer_t *buffer) |
The serialize function typedef.
This function is called by the opal tree serialize code to serialize a tree item's user specific data of a class type.
item - item to serialize the user specific data from buffer - the opal_buffer_t to store the serialized data in.
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.
parent_item | pointer to what parent the new item belongs to |
new_item | the item to be added as a child to parent_item |
The new_item is added at the end of the child list of the parent_item.
References OPAL_THREAD_ADD32, opal_tree_item_t::opal_tree_container, opal_tree_item_t::opal_tree_first_child, opal_tree_item_t::opal_tree_last_child, opal_tree_item_t::opal_tree_next_sibling, opal_tree_item_t::opal_tree_num_ancestors, opal_tree_item_t::opal_tree_num_children, opal_tree_t::opal_tree_num_items, opal_tree_item_t::opal_tree_parent, and opal_tree_item_t::opal_tree_prev_sibling.
OPAL_DECLSPEC int opal_tree_deserialize | ( | opal_buffer_t * | buffer, |
opal_tree_item_t * | start_item | ||
) |
De-serialize tree data.
buffer | The opal buffer that is to be deserialized |
start_item | The item in the tree the data should be deserialized into |
This routine takes a bytestream that was created by the opal_tree_serialize() function and deserializes it into the tree given. If the tree already has data in it, this routine will start adding the new data as a new child of the root item. This routine calls the tree's de-serialization method to deserialize the user specific data for each item.
References opal_tree_t::deserialize, and opal_tree_item_t::opal_tree_container.
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.
item | The item to start the find from |
key | the key we are wanting to match with |
This routine uses the tree container's comp function to determine the whether there is a match between the key and each item we search in the tree. This means the actual tree type constructed determines how the compare is done with the key. In the case no compare routine is given and NULL pointer is always returned for this function.
References opal_tree_item_t::opal_tree_container, opal_tree_get_first_child(), opal_tree_get_next_sibling(), opal_tree_get_root(), opal_tree_is_empty(), opal_tree_item_t::opal_tree_num_ancestors, and opal_tree_item_t::opal_tree_parent.
|
inlinestatic |
Get the first child item in the tree.
item | A tree item. |
This function is safe to be called with a null item pointer.
References opal_tree_item_t::opal_tree_first_child.
Referenced by opal_tree_find_with().
|
inlinestatic |
Get the last child item in the tree.
item | A tree item. |
This function is safe to be called with a null item pointer.
References opal_tree_item_t::opal_tree_last_child.
|
inlinestatic |
Get the next sibling item in the tree.
item | A tree item. |
This function is safe to be called with a null item pointer.
References opal_tree_item_t::opal_tree_next_sibling.
Referenced by opal_tree_find_with().
|
inlinestatic |
Macros to access items in the tree.
Get the parent of item in the tree.
item | A tree item. |
This function is safe to be called with a null item pointer.
References opal_tree_item_t::opal_tree_parent.
|
inlinestatic |
Get the previous sibling item in the tree.
item | A tree item. |
This function is safe to be called with a null item pointer.
References opal_tree_item_t::opal_tree_prev_sibling.
|
inlinestatic |
Return the root item on the tree (does not remove it).
tree | The tree container |
This is an O(1) operation to return the first item in the tree.
This is an inlined function in compilers that support inlining, so it's usually a cheap operation.
References opal_tree_item_t::opal_tree_first_child, and opal_tree_t::opal_tree_sentinel.
Referenced by opal_tree_find_with(), opal_tree_get_size(), and opal_tree_remove_subtree().
OPAL_DECLSPEC size_t opal_tree_get_size | ( | opal_tree_t * | tree | ) |
Return the number of items in a tree.
tree | The tree container |
This is an O(1) (in non-debug mode) lookup to return the size of the list.
References opal_tree_get_root(), opal_tree_is_empty(), and opal_tree_t::opal_tree_num_items.
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.
tree | The tree to initialize |
comp | Comparison function to attach to tree. |
serialize | Serialization function to attach to tree. |
deserialize | De-serialization function to attach to tree. |
References opal_tree_t::comp, opal_tree_t::deserialize, and opal_tree_t::serialize.
|
inlinestatic |
Check for empty tree.
tree | The tree container |
This is an O(1) operation.
This is an inlined function in compilers that support inlining, so it's usually a cheap operation.
References opal_tree_item_t::opal_tree_first_child, and opal_tree_t::opal_tree_sentinel.
Referenced by opal_tree_find_with(), and opal_tree_get_size().
OPAL_DECLSPEC opal_tree_item_t* opal_tree_remove_subtree | ( | opal_tree_item_t * | item | ) |
Remove an item and everything below from a tree.
item | The item at the top of subtree to remove |
This is an O(1) operation to remove an item from the tree. The item and all children below it will be removed from the tree. This means the item's siblings pointers and potentially the parents first and last pointers will be updated to skip over the item. The tree container will also have its num_items adjusted to reflect the number of items that were removed. The tree item (and all children below it) that is returned is now "owned" by the caller – they are responsible for OBJ_RELEASE()'ing it.
With ENABLE_DEBUG on this routine will validate whether the item is actually in the tree before doing pointer manipulation.
References opal_tree_item_t::opal_tree_container, opal_tree_item_t::opal_tree_first_child, opal_tree_get_root(), opal_tree_item_t::opal_tree_last_child, opal_tree_item_t::opal_tree_next_sibling, opal_tree_item_t::opal_tree_num_children, opal_tree_t::opal_tree_num_items, opal_tree_item_t::opal_tree_parent, and opal_tree_item_t::opal_tree_prev_sibling.
OPAL_DECLSPEC int opal_tree_serialize | ( | opal_tree_item_t * | start_item, |
opal_buffer_t * | buffer | ||
) |
Serialize tree data.
start_item | The item of a tree to start serializing data |
buffer | The opal buffer that contains the serialized data stream of the tree |
This routine walks the tree starting at start_item until it has serialized all children items of start_item and creates a bytestream of data, using the opal_dss.pack routine, that can be sent over a network. The format of the bytestream represents the tree parent/child relationship of each item in the tree plus the data inside the tree. This routine calls the tree's serialization method to serialize the user specific data for each item.
References OPAL_STRING, opal_tree_item_t::opal_tree_container, and opal_tree_t::serialize.