29 #ifndef _KERN_RBTREE_H
30 #define _KERN_RBTREE_H
37 #include <sys/types.h>
39 #define MACRO_BEGIN ({
44 #define STARPU_RBTREE_LEFT 0
45 #define STARPU_RBTREE_RIGHT 1
60 #define STARPU_RBTREE_INITIALIZER { NULL }
82 node->children[STARPU_RBTREE_LEFT] = NULL;
83 node->children[STARPU_RBTREE_RIGHT] = NULL;
98 #define starpu_rbtree_entry(node, type, member) structof(node, type, member)
105 return tree->root == NULL;
120 #define starpu_rbtree_lookup(tree, key, cmp_fn) \
122 struct starpu_rbtree_node *___cur; \
125 ___cur = (tree)->root; \
127 while (___cur != NULL) { \
128 ___diff = cmp_fn(key, ___cur); \
133 ___cur = ___cur->children[starpu_rbtree_d2i(___diff)]; \
149 #define starpu_rbtree_lookup_nearest(tree, key, cmp_fn, dir) \
151 struct starpu_rbtree_node *___cur, *___prev; \
152 int ___diff, ___index; \
156 ___cur = (tree)->root; \
158 while (___cur != NULL) { \
159 ___diff = cmp_fn(key, ___cur); \
165 ___index = starpu_rbtree_d2i(___diff); \
166 ___cur = ___cur->children[___index]; \
169 if (___cur == NULL) \
170 ___cur = starpu_rbtree_nearest(___prev, ___index, dir); \
191 #define starpu_rbtree_insert(tree, node, cmp_fn) \
193 struct starpu_rbtree_node *___cur, *___prev; \
194 int ___diff, ___index; \
198 ___cur = (tree)->root; \
200 while (___cur != NULL) { \
201 ___diff = cmp_fn(node, ___cur); \
202 assert(___diff != 0); \
204 ___index = starpu_rbtree_d2i(___diff); \
205 ___cur = ___cur->children[___index]; \
208 starpu_rbtree_insert_rebalance(tree, ___prev, ___index, node); \
223 #define starpu_rbtree_lookup_slot(tree, key, cmp_fn, slot) \
225 struct starpu_rbtree_node *___cur, *___prev; \
226 int ___diff, ___index; \
230 ___cur = (tree)->root; \
232 while (___cur != NULL) { \
233 ___diff = cmp_fn(key, ___cur); \
239 ___index = starpu_rbtree_d2i(___diff); \
240 ___cur = ___cur->children[___index]; \
243 (slot) = starpu_rbtree_slot(___prev, ___index); \
278 #define starpu_rbtree_first(tree) starpu_rbtree_firstlast(tree, STARPU_RBTREE_LEFT)
286 #define starpu_rbtree_last(tree) starpu_rbtree_firstlast(tree, STARPU_RBTREE_RIGHT)
291 #define starpu_rbtree_prev(node) starpu_rbtree_walk(node, STARPU_RBTREE_LEFT)
296 #define starpu_rbtree_next(node) starpu_rbtree_walk(node, STARPU_RBTREE_RIGHT)
307 #define starpu_rbtree_for_each_remove(tree, node, tmp) \
308 for (node = starpu_rbtree_postwalk_deepest(tree), \
309 tmp = starpu_rbtree_postwalk_unlink(node); \
311 node = tmp, tmp = starpu_rbtree_postwalk_unlink(node)) \
void starpu_rbtree_remove(struct starpu_rbtree *tree, struct starpu_rbtree_node *node)
static void starpu_rbtree_init(struct starpu_rbtree *tree)
Definition: rbtree.h:67
static void starpu_rbtree_insert_slot(struct starpu_rbtree *tree, uintptr_t slot, struct starpu_rbtree_node *node)
Definition: rbtree.h:256
static int starpu_rbtree_empty(const struct starpu_rbtree *tree)
Definition: rbtree.h:103
static void starpu_rbtree_node_init(struct starpu_rbtree_node *node)
Definition: rbtree.h:77
static struct starpu_rbtree_node * starpu_rbtree_parent(const struct starpu_rbtree_node *node)
Definition: rbtree_i.h:109
static int starpu_rbtree_slot_index(uintptr_t slot)
Definition: rbtree_i.h:135
#define STARPU_RBTREE_COLOR_RED
Definition: rbtree_i.h:69
static struct starpu_rbtree_node * starpu_rbtree_slot_parent(uintptr_t slot)
Definition: rbtree_i.h:127
static int starpu_rbtree_check_alignment(const struct starpu_rbtree_node *node)
Definition: rbtree_i.h:82
void starpu_rbtree_insert_rebalance(struct starpu_rbtree *tree, struct starpu_rbtree_node *parent, int index, struct starpu_rbtree_node *node)
Definition: rbtree_i.h:55
Definition: rbtree_i.h:47