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 */
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