StarPU Internal Handbook
Loading...
Searching...
No Matches
rbtree.h
Go to the documentation of this file.
1/*
2 * Copyright (c) 2010, 2011 Richard Braun.
3 * All rights reserved.
4 *
5 * Redistribution and use in source and binary forms, with or without
6 * modification, are permitted provided that the following conditions
7 * are met:
8 * 1. Redistributions of source code must retain the above copyright
9 * notice, this list of conditions and the following disclaimer.
10 * 2. Redistributions in binary form must reproduce the above copyright
11 * notice, this list of conditions and the following disclaimer in the
12 * documentation and/or other materials provided with the distribution.
13 *
14 * THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR
15 * IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES
16 * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED.
17 * IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT,
18 * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT
19 * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
20 * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
21 * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
22 * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF
23 * THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
24 *
25 *
26 * Red-black tree.
27 */
28
29#ifndef _KERN_RBTREE_H
30#define _KERN_RBTREE_H
31
34#include <stddef.h>
35#include <assert.h>
36#include <stdint.h>
37#include <sys/types.h>
38
39#include <starpu_util.h>
40
41#define MACRO_BEGIN ({
42#define MACRO_END })
43/*
44 * Indexes of the left and right nodes in the children array of a node.
45 */
46#define STARPU_RBTREE_LEFT 0
47#define STARPU_RBTREE_RIGHT 1
48
53
57struct starpu_rbtree;
58
62#define STARPU_RBTREE_INITIALIZER { NULL }
63
64#include "rbtree_i.h"
65
69static inline void starpu_rbtree_init(struct starpu_rbtree *tree)
70{
71 tree->root = NULL;
72}
73
77static inline void starpu_rbtree_init0(struct starpu_rbtree *tree STARPU_ATTRIBUTE_UNUSED)
78{
79}
80
86static inline void starpu_rbtree_node_init(struct starpu_rbtree_node *node)
87{
89
90 node->parent = (uintptr_t)node | STARPU_RBTREE_COLOR_RED;
91 node->children[STARPU_RBTREE_LEFT] = NULL;
92 node->children[STARPU_RBTREE_RIGHT] = NULL;
93}
94
98static inline void starpu_rbtree_node_init0(struct starpu_rbtree_node *node)
99{
100 assert(starpu_rbtree_check_alignment(node));
101
102 node->parent = (uintptr_t)node | STARPU_RBTREE_COLOR_RED;
103 //node->children[STARPU_RBTREE_LEFT] = NULL;
104 //node->children[STARPU_RBTREE_RIGHT] = NULL;
105}
106
110static inline int starpu_rbtree_node_unlinked(const struct starpu_rbtree_node *node)
111{
112 return starpu_rbtree_parent(node) == node;
113}
114
119#define starpu_rbtree_entry(node, type, member) structof(node, type, member)
120
124static inline int starpu_rbtree_empty(const struct starpu_rbtree *tree)
125{
126 return tree->root == NULL;
127}
128
141#define starpu_rbtree_lookup(tree, key, cmp_fn) \
142MACRO_BEGIN \
143 struct starpu_rbtree_node *___cur; \
144 int ___diff; \
145 \
146 ___cur = (tree)->root; \
147 \
148 while (___cur != NULL) { \
149 ___diff = cmp_fn(key, ___cur); \
150 \
151 if (___diff == 0) \
152 break; \
153 \
154 ___cur = ___cur->children[starpu_rbtree_d2i(___diff)]; \
155 } \
156 \
157 ___cur; \
158MACRO_END
159
170#define starpu_rbtree_lookup_nearest(tree, key, cmp_fn, dir) \
171MACRO_BEGIN \
172 struct starpu_rbtree_node *___cur, *___prev; \
173 int ___diff, ___index; \
174 \
175 ___prev = NULL; \
176 ___index = -1; \
177 ___cur = (tree)->root; \
178 \
179 while (___cur != NULL) { \
180 ___diff = cmp_fn(key, ___cur); \
181 \
182 if (___diff == 0) \
183 break; \
184 \
185 ___prev = ___cur; \
186 ___index = starpu_rbtree_d2i(___diff); \
187 ___cur = ___cur->children[___index]; \
188 } \
189 \
190 if (___cur == NULL) \
191 ___cur = starpu_rbtree_nearest(___prev, ___index, dir); \
192 \
193 ___cur; \
194MACRO_END
195
212#define starpu_rbtree_insert(tree, node, cmp_fn) \
213MACRO_BEGIN \
214 struct starpu_rbtree_node *___cur, *___prev; \
215 int ___diff, ___index; \
216 \
217 ___prev = NULL; \
218 ___index = -1; \
219 ___cur = (tree)->root; \
220 \
221 while (___cur != NULL) { \
222 ___diff = cmp_fn(node, ___cur); \
223 assert(___diff != 0); \
224 ___prev = ___cur; \
225 ___index = starpu_rbtree_d2i(___diff); \
226 ___cur = ___cur->children[___index]; \
227 } \
228 \
229 starpu_rbtree_insert_rebalance(tree, ___prev, ___index, node); \
230MACRO_END
231
244#define starpu_rbtree_lookup_slot(tree, key, cmp_fn, slot) \
245MACRO_BEGIN \
246 struct starpu_rbtree_node *___cur, *___prev; \
247 int ___diff, ___index; \
248 \
249 ___prev = NULL; \
250 ___index = 0; \
251 ___cur = (tree)->root; \
252 \
253 while (___cur != NULL) { \
254 ___diff = cmp_fn(key, ___cur); \
255 \
256 if (___diff == 0) \
257 break; \
258 \
259 ___prev = ___cur; \
260 ___index = starpu_rbtree_d2i(___diff); \
261 ___cur = ___cur->children[___index]; \
262 } \
263 \
264 (slot) = starpu_rbtree_slot(___prev, ___index); \
265 ___cur; \
266MACRO_END
267
277static inline void starpu_rbtree_insert_slot(struct starpu_rbtree *tree, uintptr_t slot,
278 struct starpu_rbtree_node *node)
279{
280 struct starpu_rbtree_node *parent;
281 int index;
282
283 parent = starpu_rbtree_slot_parent(slot);
284 index = starpu_rbtree_slot_index(slot);
285 starpu_rbtree_insert_rebalance(tree, parent, index, node);
286}
287
294
298/* TODO: optimize by maintaining the first node of the tree */
299#define starpu_rbtree_first(tree) starpu_rbtree_firstlast(tree, STARPU_RBTREE_LEFT)
300
304/* TODO: optimize by maintaining the first node of the tree */
305/* TODO: could be useful to optimize the case when the key being inserted is
306 * bigger that the biggest node */
307#define starpu_rbtree_last(tree) starpu_rbtree_firstlast(tree, STARPU_RBTREE_RIGHT)
308
312#define starpu_rbtree_prev(node) starpu_rbtree_walk(node, STARPU_RBTREE_LEFT)
313
317#define starpu_rbtree_next(node) starpu_rbtree_walk(node, STARPU_RBTREE_RIGHT)
318
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); \
331 node != NULL; \
332 node = tmp, tmp = starpu_rbtree_postwalk_unlink(node)) \
333
334#endif /* _KERN_RBTREE_H */
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
Definition rbtree_i.h:57
Definition rbtree_i.h:48