StarPU Internal Handbook

Data Structures | Macros | Functions
rbtree_i.h File Reference
`#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

## Functions
static int | starpu_rbtree_check_alignment (const struct starpu_rbtree_node *node)
static int | starpu_rbtree_check_index (int index)
static int | starpu_rbtree_d2i (int diff)
static struct starpu_rbtree_node * | starpu_rbtree_parent (const struct starpu_rbtree_node *node)
static uintptr_t | starpu_rbtree_slot (struct starpu_rbtree_node *parent, int index)
static struct starpu_rbtree_node * | starpu_rbtree_slot_parent (uintptr_t slot)
static int | starpu_rbtree_slot_index (uintptr_t slot)
void | starpu_rbtree_insert_rebalance (struct starpu_rbtree *tree, struct starpu_rbtree_node *parent, int index, struct starpu_rbtree_node *node)
struct starpu_rbtree_node * | starpu_rbtree_nearest (struct starpu_rbtree_node *parent, int index, int direction)
struct starpu_rbtree_node * | starpu_rbtree_firstlast (const struct starpu_rbtree *tree, int direction)
struct starpu_rbtree_node * | starpu_rbtree_walk (struct starpu_rbtree_node *node, int direction)
struct starpu_rbtree_node * | starpu_rbtree_postwalk_deepest (const struct starpu_rbtree *tree)
struct starpu_rbtree_node * | starpu_rbtree_postwalk_unlink (struct starpu_rbtree_node *node)

## Data Structure Documentation

## ◆ starpu_rbtree_node

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] |

## ◆ starpu_rbtree

struct starpu_rbtree

Red-black tree structure.

Data Fields
struct starpu_rbtree_node * | root |

## Macro Definition Documentation

## ◆ STARPU_RBTREE_COLOR_MASK

#define STARPU_RBTREE_COLOR_MASK

Masks applied on the parent member of a node to obtain either the color or the parent address.

## ◆ STARPU_RBTREE_COLOR_RED

#define STARPU_RBTREE_COLOR_RED

Node colors.

## ◆ STARPU_RBTREE_SLOT_INDEX_MASK

#define STARPU_RBTREE_SLOT_INDEX_MASK

Masks applied on slots to obtain either the child index or the parent address.

## Function Documentation

## ◆ starpu_rbtree_check_alignment()

static int starpu_rbtree_check_alignment | ( | const struct starpu_rbtree_node * | node | ) |
| inline static

Return true if the given pointer is suitably aligned.

## ◆ starpu_rbtree_check_index()

static int starpu_rbtree_check_index | ( | int | index | ) |
| inline static

Return true if the given index is a valid child index.

## ◆ starpu_rbtree_d2i()

static int starpu_rbtree_d2i | ( | int | diff | ) |
| inline static

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.

## ◆ starpu_rbtree_parent()

static struct starpu_rbtree_node * starpu_rbtree_parent | ( | const struct starpu_rbtree_node * | node | ) |
| inline static

Return the parent of a node.

## ◆ starpu_rbtree_slot()

static uintptr_t starpu_rbtree_slot | ( | struct starpu_rbtree_node * | parent,
|  | int | index
| ) |  |
| inline static

Translate an insertion point into a slot.

## ◆ starpu_rbtree_slot_parent()

static struct starpu_rbtree_node * starpu_rbtree_slot_parent | ( | uintptr_t | slot | ) |
| inline static

Extract the parent address from a slot.

## ◆ starpu_rbtree_slot_index()

static int starpu_rbtree_slot_index | ( | uintptr_t | slot | ) |
| inline static

Extract the index from a slot.

## ◆ starpu_rbtree_insert_rebalance()

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.

## ◆ starpu_rbtree_nearest()

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).

## ◆ starpu_rbtree_firstlast()

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).

## ◆ starpu_rbtree_walk()

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).

## ◆ starpu_rbtree_postwalk_deepest()

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().

## ◆ starpu_rbtree_postwalk_unlink()

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.