39#include <starpu_util.h>
46#define STARPU_RBTREE_LEFT 0
47#define STARPU_RBTREE_RIGHT 1
62#define STARPU_RBTREE_INITIALIZER { NULL }
91 node->children[STARPU_RBTREE_LEFT] = NULL;
92 node->children[STARPU_RBTREE_RIGHT] = NULL;
119#define starpu_rbtree_entry(node, type, member) structof(node, type, member)
126 return tree->root == NULL;
141#define starpu_rbtree_lookup(tree, key, cmp_fn) \
143 struct starpu_rbtree_node *___cur; \
146 ___cur = (tree)->root; \
148 while (___cur != NULL) { \
149 ___diff = cmp_fn(key, ___cur); \
154 ___cur = ___cur->children[starpu_rbtree_d2i(___diff)]; \
170#define starpu_rbtree_lookup_nearest(tree, key, cmp_fn, dir) \
172 struct starpu_rbtree_node *___cur, *___prev; \
173 int ___diff, ___index; \
177 ___cur = (tree)->root; \
179 while (___cur != NULL) { \
180 ___diff = cmp_fn(key, ___cur); \
186 ___index = starpu_rbtree_d2i(___diff); \
187 ___cur = ___cur->children[___index]; \
190 if (___cur == NULL) \
191 ___cur = starpu_rbtree_nearest(___prev, ___index, dir); \
212#define starpu_rbtree_insert(tree, node, cmp_fn) \
214 struct starpu_rbtree_node *___cur, *___prev; \
215 int ___diff, ___index; \
219 ___cur = (tree)->root; \
221 while (___cur != NULL) { \
222 ___diff = cmp_fn(node, ___cur); \
223 assert(___diff != 0); \
225 ___index = starpu_rbtree_d2i(___diff); \
226 ___cur = ___cur->children[___index]; \
229 starpu_rbtree_insert_rebalance(tree, ___prev, ___index, node); \
244#define starpu_rbtree_lookup_slot(tree, key, cmp_fn, slot) \
246 struct starpu_rbtree_node *___cur, *___prev; \
247 int ___diff, ___index; \
251 ___cur = (tree)->root; \
253 while (___cur != NULL) { \
254 ___diff = cmp_fn(key, ___cur); \
260 ___index = starpu_rbtree_d2i(___diff); \
261 ___cur = ___cur->children[___index]; \
264 (slot) = starpu_rbtree_slot(___prev, ___index); \
299#define starpu_rbtree_first(tree) starpu_rbtree_firstlast(tree, STARPU_RBTREE_LEFT)
307#define starpu_rbtree_last(tree) starpu_rbtree_firstlast(tree, STARPU_RBTREE_RIGHT)
312#define starpu_rbtree_prev(node) starpu_rbtree_walk(node, STARPU_RBTREE_LEFT)
317#define starpu_rbtree_next(node) starpu_rbtree_walk(node, STARPU_RBTREE_RIGHT)
328#define starpu_rbtree_for_each_remove(tree, node, tmp) \
329 for (node = starpu_rbtree_postwalk_deepest(tree), \
330 tmp = starpu_rbtree_postwalk_unlink(node); \
332 node = tmp, tmp = starpu_rbtree_postwalk_unlink(node)) \
void starpu_rbtree_remove(struct starpu_rbtree *tree, struct starpu_rbtree_node *node)
static int starpu_rbtree_node_unlinked(const struct starpu_rbtree_node *node)
Definition rbtree.h:110
static void starpu_rbtree_init(struct starpu_rbtree *tree)
Definition rbtree.h:69
static void starpu_rbtree_insert_slot(struct starpu_rbtree *tree, uintptr_t slot, struct starpu_rbtree_node *node)
Definition rbtree.h:277
static void starpu_rbtree_node_init0(struct starpu_rbtree_node *node)
Definition rbtree.h:98
static int starpu_rbtree_empty(const struct starpu_rbtree *tree)
Definition rbtree.h:124
static void starpu_rbtree_init0(struct starpu_rbtree *tree STARPU_ATTRIBUTE_UNUSED)
Definition rbtree.h:77
static void starpu_rbtree_node_init(struct starpu_rbtree_node *node)
Definition rbtree.h:86
static int starpu_rbtree_slot_index(uintptr_t slot)
Definition rbtree_i.h:137
static struct starpu_rbtree_node * starpu_rbtree_slot_parent(uintptr_t slot)
Definition rbtree_i.h:129
#define STARPU_RBTREE_COLOR_RED
Definition rbtree_i.h:71
static int starpu_rbtree_check_alignment(const struct starpu_rbtree_node *node)
Definition rbtree_i.h:84
void starpu_rbtree_insert_rebalance(struct starpu_rbtree *tree, struct starpu_rbtree_node *parent, int index, struct starpu_rbtree_node *node)
static struct starpu_rbtree_node * starpu_rbtree_parent(const struct starpu_rbtree_node *node)
Definition rbtree_i.h:111