StarPU Internal Handbook
Loading...
Searching...
No Matches
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_nodestarpu_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_nodestarpu_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_nodestarpu_rbtree_nearest (struct starpu_rbtree_node *parent, int index, int direction)
 
struct starpu_rbtree_nodestarpu_rbtree_firstlast (const struct starpu_rbtree *tree, int direction)
 
struct starpu_rbtree_nodestarpu_rbtree_walk (struct starpu_rbtree_node *node, int direction)
 
struct starpu_rbtree_nodestarpu_rbtree_postwalk_deepest (const struct starpu_rbtree *tree)
 
struct starpu_rbtree_nodestarpu_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)
inlinestatic

Return true if the given pointer is suitably aligned.

◆ starpu_rbtree_check_index()

static int starpu_rbtree_check_index ( int  index)
inlinestatic

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

◆ starpu_rbtree_d2i()

static int starpu_rbtree_d2i ( int  diff)
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.

◆ starpu_rbtree_parent()

static struct starpu_rbtree_node * starpu_rbtree_parent ( const struct starpu_rbtree_node node)
inlinestatic

Return the parent of a node.

◆ starpu_rbtree_slot()

static uintptr_t starpu_rbtree_slot ( struct starpu_rbtree_node parent,
int  index 
)
inlinestatic

Translate an insertion point into a slot.

◆ starpu_rbtree_slot_parent()

static struct starpu_rbtree_node * starpu_rbtree_slot_parent ( uintptr_t  slot)
inlinestatic

Extract the parent address from a slot.

◆ starpu_rbtree_slot_index()

static int starpu_rbtree_slot_index ( uintptr_t  slot)
inlinestatic

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.