StarPU Internal Handbook
|
#include <assert.h>
Go to the source code of this file.
Data Structures | |
struct | starpu_rbtree_node |
struct | starpu_rbtree |
Macros | |
#define | STARPU_RBTREE_COLOR_MASK |
#define | STARPU_RBTREE_PARENT_MASK |
#define | STARPU_RBTREE_COLOR_RED |
#define | STARPU_RBTREE_COLOR_BLACK |
#define | STARPU_RBTREE_SLOT_INDEX_MASK |
#define | STARPU_RBTREE_SLOT_PARENT_MASK |
struct starpu_rbtree_node |
Red-black node structure.
To reduce the number of branches and the instruction cache footprint, the left and right child pointers are stored in an array, and the symmetry of most tree operations is exploited by using left/right variables when referring to children.
In addition, this implementation assumes that all nodes are 4-byte aligned, so that the least significant bit of the parent member can be used to store the color of the node. This is true for all modern 32 and 64 bits architectures, as long as the nodes aren't embedded in structures with special alignment constraints such as member packing.
Data Fields | ||
---|---|---|
uintptr_t | parent | |
struct starpu_rbtree_node * | children[2] |
struct starpu_rbtree |
Red-black tree structure.
Data Fields | ||
---|---|---|
struct starpu_rbtree_node * | root |
#define STARPU_RBTREE_COLOR_MASK |
Masks applied on the parent member of a node to obtain either the color or the parent address.
#define STARPU_RBTREE_COLOR_RED |
Node colors.
#define STARPU_RBTREE_SLOT_INDEX_MASK |
Masks applied on slots to obtain either the child index or the parent address.
|
inlinestatic |
Return true if the given pointer is suitably aligned.
|
inlinestatic |
Return true if the given index is a valid child index.
|
inlinestatic |
Convert the result of a comparison into an index in the children array (0 or 1).
This function is mostly used when looking up a node.
|
inlinestatic |
Return the parent of a node.
|
inlinestatic |
Translate an insertion point into a slot.
|
inlinestatic |
Extract the parent address from a slot.
|
inlinestatic |
Extract the index from a slot.
void starpu_rbtree_insert_rebalance | ( | struct starpu_rbtree * | tree, |
struct starpu_rbtree_node * | parent, | ||
int | index, | ||
struct starpu_rbtree_node * | node | ||
) |
Insert a node in a tree, rebalancing it if necessary.
The index parameter is the index in the children array of the parent where the new node is to be inserted. It is ignored if the parent is null.
This function is intended to be used by the starpu_rbtree_insert() macro only.
struct starpu_rbtree_node * starpu_rbtree_nearest | ( | struct starpu_rbtree_node * | parent, |
int | index, | ||
int | direction | ||
) |
Return the previous or next node relative to a location in a tree.
The parent and index parameters define the location, which can be empty. The direction parameter is either STARPU_RBTREE_LEFT (to obtain the previous node) or STARPU_RBTREE_RIGHT (to obtain the next one).
struct starpu_rbtree_node * starpu_rbtree_firstlast | ( | const struct starpu_rbtree * | tree, |
int | direction | ||
) |
Return the first or last node of a tree.
The direction parameter is either STARPU_RBTREE_LEFT (to obtain the first node) or STARPU_RBTREE_RIGHT (to obtain the last one).
struct starpu_rbtree_node * starpu_rbtree_walk | ( | struct starpu_rbtree_node * | node, |
int | direction | ||
) |
Return the node next to, or previous to the given node.
The direction parameter is either STARPU_RBTREE_LEFT (to obtain the previous node) or STARPU_RBTREE_RIGHT (to obtain the next one).
struct starpu_rbtree_node * starpu_rbtree_postwalk_deepest | ( | const struct starpu_rbtree * | tree | ) |
Return the left-most deepest node of a tree, which is the starting point of the postorder traversal performed by starpu_rbtree_for_each_remove().
struct starpu_rbtree_node * starpu_rbtree_postwalk_unlink | ( | struct starpu_rbtree_node * | node | ) |
Unlink a node from its tree and return the next (right) node in postorder.