StarPU Internal Handbook
Loading...
Searching...
No Matches
rbtree.h File Reference
#include <stddef.h>
#include <assert.h>
#include <stdint.h>
#include <sys/types.h>
#include <starpu_util.h>
#include "rbtree_i.h"

Go to the source code of this file.

Macros

#define MACRO_BEGIN
 
#define MACRO_END
 
#define STARPU_RBTREE_LEFT
 
#define STARPU_RBTREE_RIGHT
 
#define STARPU_RBTREE_INITIALIZER
 
#define starpu_rbtree_entry(node, type, member)
 
#define starpu_rbtree_lookup(tree, key, cmp_fn)
 
#define starpu_rbtree_lookup_nearest(tree, key, cmp_fn, dir)
 
#define starpu_rbtree_insert(tree, node, cmp_fn)
 
#define starpu_rbtree_lookup_slot(tree, key, cmp_fn, slot)
 
#define starpu_rbtree_first(tree)
 
#define starpu_rbtree_last(tree)
 
#define starpu_rbtree_prev(node)
 
#define starpu_rbtree_next(node)
 
#define starpu_rbtree_for_each_remove(tree, node, tmp)
 

Functions

static void starpu_rbtree_init (struct starpu_rbtree *tree)
 
static void starpu_rbtree_init0 (struct starpu_rbtree *tree STARPU_ATTRIBUTE_UNUSED)
 
static void starpu_rbtree_node_init (struct starpu_rbtree_node *node)
 
static void starpu_rbtree_node_init0 (struct starpu_rbtree_node *node)
 
static int starpu_rbtree_node_unlinked (const struct starpu_rbtree_node *node)
 
static int starpu_rbtree_empty (const struct starpu_rbtree *tree)
 
static void starpu_rbtree_insert_slot (struct starpu_rbtree *tree, uintptr_t slot, struct starpu_rbtree_node *node)
 
void starpu_rbtree_remove (struct starpu_rbtree *tree, struct starpu_rbtree_node *node)
 

Macro Definition Documentation

◆ STARPU_RBTREE_INITIALIZER

#define STARPU_RBTREE_INITIALIZER

Static tree initializer.

◆ starpu_rbtree_entry

#define starpu_rbtree_entry (   node,
  type,
  member 
)

Macro that evaluates to the address of the structure containing the given node based on the given type and member.

◆ starpu_rbtree_lookup

#define starpu_rbtree_lookup (   tree,
  key,
  cmp_fn 
)

Look up a node in a tree.

Note that implementing the lookup algorithm as a macro gives two benefits: First, it avoids the overhead of a callback function. Next, the type of the cmp_fn parameter isn't rigid. The only guarantee offered by this implementation is that the key parameter is the first parameter given to cmp_fn. This way, users can pass only the value they need for comparison instead of e.g. allocating a full structure on the stack.

See starpu_rbtree_insert().

◆ starpu_rbtree_lookup_nearest

#define starpu_rbtree_lookup_nearest (   tree,
  key,
  cmp_fn,
  dir 
)

Look up a node or one of its nearest nodes in a tree.

This macro essentially acts as starpu_rbtree_lookup() but if no entry matched the key, an additional step is performed to obtain the next or previous node, depending on the direction (left or right).

The constraints that apply to the key parameter are the same as for starpu_rbtree_lookup().

◆ starpu_rbtree_insert

#define starpu_rbtree_insert (   tree,
  node,
  cmp_fn 
)

Insert a node in a tree.

This macro performs a standard lookup to obtain the insertion point of the given node in the tree (it is assumed that the inserted node never compares equal to any other entry in the tree) and links the node. It then checks red-black rules violations, and rebalances the tree if necessary.

Unlike starpu_rbtree_lookup(), the cmp_fn parameter must compare two complete entries, so it is suggested to use two different comparison inline functions, such as myobj_cmp_lookup() and myobj_cmp_insert(). There is no guarantee about the order of the nodes given to the comparison function.

See starpu_rbtree_lookup().

◆ starpu_rbtree_lookup_slot

#define starpu_rbtree_lookup_slot (   tree,
  key,
  cmp_fn,
  slot 
)

Look up a node/slot pair in a tree.

This macro essentially acts as starpu_rbtree_lookup() but in addition to a node, it also returns a slot, which identifies an insertion point in the tree. If the returned node is null, the slot can be used by starpu_rbtree_insert_slot() to insert without the overhead of an additional lookup. The slot is a simple uintptr_t integer.

The constraints that apply to the key parameter are the same as for starpu_rbtree_lookup().

◆ starpu_rbtree_first

#define starpu_rbtree_first (   tree)

Return the first node of a tree.

◆ starpu_rbtree_last

#define starpu_rbtree_last (   tree)

Return the last node of a tree.

◆ starpu_rbtree_prev

#define starpu_rbtree_prev (   node)

Return the node previous to the given node.

◆ starpu_rbtree_next

#define starpu_rbtree_next (   node)

Return the node next to the given node.

◆ starpu_rbtree_for_each_remove

#define starpu_rbtree_for_each_remove (   tree,
  node,
  tmp 
)

Forge a loop to process all nodes of a tree, removing them when visited.

This macro can only be used to destroy a tree, so that the resources used by the entries can be released by the user. It basically removes all nodes without doing any color checking.

After completion, all nodes and the tree root member are stale.

Function Documentation

◆ starpu_rbtree_init()

static void starpu_rbtree_init ( struct starpu_rbtree tree)
inlinestatic

Initialize a tree.

◆ starpu_rbtree_init0()

static void starpu_rbtree_init0 ( struct starpu_rbtree *tree  STARPU_ATTRIBUTE_UNUSED)
inlinestatic

This version assumes that the content of tree was already zeroed

◆ starpu_rbtree_node_init()

static void starpu_rbtree_node_init ( struct starpu_rbtree_node node)
inlinestatic

Initialize a node.

A node is in no tree when its parent points to itself.

◆ starpu_rbtree_node_init0()

static void starpu_rbtree_node_init0 ( struct starpu_rbtree_node node)
inlinestatic

This version assumes that the content of node was already zeroed

◆ starpu_rbtree_node_unlinked()

static int starpu_rbtree_node_unlinked ( const struct starpu_rbtree_node node)
inlinestatic

Return true if node is in no tree.

◆ starpu_rbtree_empty()

static int starpu_rbtree_empty ( const struct starpu_rbtree tree)
inlinestatic

Return true if tree is empty.

◆ starpu_rbtree_insert_slot()

static void starpu_rbtree_insert_slot ( struct starpu_rbtree tree,
uintptr_t  slot,
struct starpu_rbtree_node node 
)
inlinestatic

Insert a node at an insertion point in a tree.

This macro essentially acts as starpu_rbtree_insert() except that it doesn't obtain the insertion point with a standard lookup. The insertion point is obtained by calling starpu_rbtree_lookup_slot(). In addition, the new node must not compare equal to an existing node in the tree (i.e. the slot must denote a null node).

◆ starpu_rbtree_remove()

void starpu_rbtree_remove ( struct starpu_rbtree tree,
struct starpu_rbtree_node node 
)

Remove a node from a tree.

After completion, the node is stale.