StarPU Internal Handbook

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#define MACRO_BEGIN ({
40#define MACRO_END })
41/*
42 * Indexes of the left and right nodes in the children array of a node.
43 */
44#define STARPU_RBTREE_LEFT 0
45#define STARPU_RBTREE_RIGHT 1
46
50 struct starpu_rbtree_node;
51
55 struct starpu_rbtree;
56
60#define STARPU_RBTREE_INITIALIZER { NULL }
61
62#include "rbtree_i.h"
63
67 static inline void starpu_rbtree_init(struct starpu_rbtree *tree)
68{
69 tree->root = NULL;
70}
71
77 static inline void starpu_rbtree_node_init(struct starpu_rbtree_node *node)
78{
79 assert(starpu_rbtree_check_alignment(node));
80
81 node->parent = (uintptr_t)node | STARPU_RBTREE_COLOR_RED;
82 node->children[STARPU_RBTREE_LEFT] = NULL;
83 node->children[STARPU_RBTREE_RIGHT] = NULL;
84}
85
86/*
87 * Return true if node is in no tree.
88 */
89 static inline int starpu_rbtree_node_unlinked(const struct starpu_rbtree_node *node)
90{
91 return starpu_rbtree_parent(node) == node;
92}
93
98#define starpu_rbtree_entry(node, type, member) structof(node, type, member)
99
103 static inline int starpu_rbtree_empty(const struct starpu_rbtree *tree)
104{
105 return tree->root == NULL;
106}
107
120#define starpu_rbtree_lookup(tree, key, cmp_fn) \
121 MACRO_BEGIN \
122 struct starpu_rbtree_node *___cur; \
123 int ___diff; \
124 \
125 ___cur = (tree)->root; \
126 \
127 while (___cur != NULL) { \
128 ___diff = cmp_fn(key, ___cur); \
129 \
130 if (___diff == 0) \
131 break; \
132 \
133 ___cur = ___cur->children[starpu_rbtree_d2i(___diff)]; \
134 } \
135 \
136 ___cur; \
137 MACRO_END
138
149#define starpu_rbtree_lookup_nearest(tree, key, cmp_fn, dir) \
150 MACRO_BEGIN \
151 struct starpu_rbtree_node *___cur, *___prev; \
152 int ___diff, ___index; \
153 \
154 ___prev = NULL; \
155 ___index = -1; \
156 ___cur = (tree)->root; \
157 \
158 while (___cur != NULL) { \
159 ___diff = cmp_fn(key, ___cur); \
160 \
161 if (___diff == 0) \
162 break; \
163 \
164 ___prev = ___cur; \
165 ___index = starpu_rbtree_d2i(___diff); \
166 ___cur = ___cur->children[___index]; \
167 } \
168 \
169 if (___cur == NULL) \
170 ___cur = starpu_rbtree_nearest(___prev, ___index, dir); \
171 \
172 ___cur; \
173 MACRO_END
174
191#define starpu_rbtree_insert(tree, node, cmp_fn) \
192 MACRO_BEGIN \
193 struct starpu_rbtree_node *___cur, *___prev; \
194 int ___diff, ___index; \
195 \
196 ___prev = NULL; \
197 ___index = -1; \
198 ___cur = (tree)->root; \
199 \
200 while (___cur != NULL) { \
201 ___diff = cmp_fn(node, ___cur); \
202 assert(___diff != 0); \
203 ___prev = ___cur; \
204 ___index = starpu_rbtree_d2i(___diff); \
205 ___cur = ___cur->children[___index]; \
206 } \
207 \
208 starpu_rbtree_insert_rebalance(tree, ___prev, ___index, node); \
209 MACRO_END
210
223#define starpu_rbtree_lookup_slot(tree, key, cmp_fn, slot) \
224 MACRO_BEGIN \
225 struct starpu_rbtree_node *___cur, *___prev; \
226 int ___diff, ___index; \
227 \
228 ___prev = NULL; \
229 ___index = 0; \
230 ___cur = (tree)->root; \
231 \
232 while (___cur != NULL) { \
233 ___diff = cmp_fn(key, ___cur); \
234 \
235 if (___diff == 0) \
236 break; \
237 \
238 ___prev = ___cur; \
239 ___index = starpu_rbtree_d2i(___diff); \
240 ___cur = ___cur->children[___index]; \
241 } \
242 \
243 (slot) = starpu_rbtree_slot(___prev, ___index); \
244 ___cur; \
245 MACRO_END
246
256 static inline void starpu_rbtree_insert_slot(struct starpu_rbtree *tree, uintptr_t slot,
257 struct starpu_rbtree_node *node)
258{
259 struct starpu_rbtree_node *parent;
260 int index;
261
262 parent = starpu_rbtree_slot_parent(slot);
263 index = starpu_rbtree_slot_index(slot);
264 starpu_rbtree_insert_rebalance(tree, parent, index, node);
265}
266
272 void starpu_rbtree_remove(struct starpu_rbtree *tree, struct starpu_rbtree_node *node);
273
277/* TODO: optimize by maintaining the first node of the tree */
278#define starpu_rbtree_first(tree) starpu_rbtree_firstlast(tree, STARPU_RBTREE_LEFT)
279
283/* TODO: optimize by maintaining the first node of the tree */
284/* TODO: could be useful to optimize the case when the key being inserted is
285 * bigger that the biggest node */
286#define starpu_rbtree_last(tree) starpu_rbtree_firstlast(tree, STARPU_RBTREE_RIGHT)
287
291#define starpu_rbtree_prev(node) starpu_rbtree_walk(node, STARPU_RBTREE_LEFT)
292
296#define starpu_rbtree_next(node) starpu_rbtree_walk(node, STARPU_RBTREE_RIGHT)
297
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); \
310 node != NULL; \
311 node = tmp, tmp = starpu_rbtree_postwalk_unlink(node)) \
312
313#endif /* _KERN_RBTREE_H */
starpu_rbtree_remove
void starpu_rbtree_remove(struct starpu_rbtree *tree, struct starpu_rbtree_node *node)
starpu_rbtree_init
static void starpu_rbtree_init(struct starpu_rbtree *tree)
Definition: rbtree.h:67
starpu_rbtree_insert_slot
static void starpu_rbtree_insert_slot(struct starpu_rbtree *tree, uintptr_t slot, struct starpu_rbtree_node *node)
Definition: rbtree.h:256
starpu_rbtree_empty
static int starpu_rbtree_empty(const struct starpu_rbtree *tree)
Definition: rbtree.h:103
starpu_rbtree_node_init
static void starpu_rbtree_node_init(struct starpu_rbtree_node *node)
Definition: rbtree.h:77
rbtree_i.h
starpu_rbtree_slot_index
static int starpu_rbtree_slot_index(uintptr_t slot)
Definition: rbtree_i.h:135
starpu_rbtree_slot_parent
static struct starpu_rbtree_node * starpu_rbtree_slot_parent(uintptr_t slot)
Definition: rbtree_i.h:127
STARPU_RBTREE_COLOR_RED
#define STARPU_RBTREE_COLOR_RED
Definition: rbtree_i.h:69
starpu_rbtree_check_alignment
static int starpu_rbtree_check_alignment(const struct starpu_rbtree_node *node)
Definition: rbtree_i.h:82
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)
starpu_rbtree_parent
static struct starpu_rbtree_node * starpu_rbtree_parent(const struct starpu_rbtree_node *node)
Definition: rbtree_i.h:109
starpu_rbtree
Definition: rbtree_i.h:55
starpu_rbtree_node
Definition: rbtree_i.h:47