1 /* This is a cut down version of NetBSD's /usr/include/sys/tree.h */
3 /* $NetBSD: tree.h,v 1.20 2013/09/14 13:20:45 joerg Exp $ */
4 /* $OpenBSD: tree.h,v 1.13 2011/07/09 00:19:45 pirofti Exp $ */
6 * Copyright 2002 Niels Provos <provos@citi.umich.edu>
9 * Redistribution and use in source and binary forms, with or without
10 * modification, are permitted provided that the following conditions
12 * 1. Redistributions of source code must retain the above copyright
13 * notice, this list of conditions and the following disclaimer.
14 * 2. Redistributions in binary form must reproduce the above copyright
15 * notice, this list of conditions and the following disclaimer in the
16 * documentation and/or other materials provided with the distribution.
18 * THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR
19 * IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES
20 * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED.
21 * IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT,
22 * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT
23 * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
24 * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
25 * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
26 * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF
27 * THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
35 /* Macros that define a red-black tree */
36 #define RB_HEAD(name, type) \
38 struct type *rbh_root; /* root of the tree */ \
41 #define RB_INITIALIZER(root) \
44 #define RB_INIT(root) do { \
45 (root)->rbh_root = NULL; \
46 } while (/*CONSTCOND*/ 0)
50 #define RB_ENTRY(type) \
52 struct type *rbe_left; /* left element */ \
53 struct type *rbe_right; /* right element */ \
54 struct type *rbe_parent; /* parent element */ \
55 int rbe_color; /* node color */ \
58 #define RB_LEFT(elm, field) (elm)->field.rbe_left
59 #define RB_RIGHT(elm, field) (elm)->field.rbe_right
60 #define RB_PARENT(elm, field) (elm)->field.rbe_parent
61 #define RB_COLOR(elm, field) (elm)->field.rbe_color
62 #define RB_ROOT(head) (head)->rbh_root
63 #define RB_EMPTY(head) (RB_ROOT(head) == NULL)
65 #define RB_SET(elm, parent, field) do { \
66 RB_PARENT(elm, field) = parent; \
67 RB_LEFT(elm, field) = RB_RIGHT(elm, field) = NULL; \
68 RB_COLOR(elm, field) = RB_RED; \
69 } while (/*CONSTCOND*/ 0)
71 #define RB_SET_BLACKRED(black, red, field) do { \
72 RB_COLOR(black, field) = RB_BLACK; \
73 RB_COLOR(red, field) = RB_RED; \
74 } while (/*CONSTCOND*/ 0)
77 #define RB_AUGMENT(x) do {} while (/*CONSTCOND*/ 0)
80 #define RB_ROTATE_LEFT(head, elm, tmp, field) do { \
81 (tmp) = RB_RIGHT(elm, field); \
82 if ((RB_RIGHT(elm, field) = RB_LEFT(tmp, field)) != NULL) { \
83 RB_PARENT(RB_LEFT(tmp, field), field) = (elm); \
86 if ((RB_PARENT(tmp, field) = RB_PARENT(elm, field)) != NULL) { \
87 if ((elm) == RB_LEFT(RB_PARENT(elm, field), field)) \
88 RB_LEFT(RB_PARENT(elm, field), field) = (tmp); \
90 RB_RIGHT(RB_PARENT(elm, field), field) = (tmp); \
92 (head)->rbh_root = (tmp); \
93 RB_LEFT(tmp, field) = (elm); \
94 RB_PARENT(elm, field) = (tmp); \
96 if ((RB_PARENT(tmp, field))) \
97 RB_AUGMENT(RB_PARENT(tmp, field)); \
98 } while (/*CONSTCOND*/ 0)
100 #define RB_ROTATE_RIGHT(head, elm, tmp, field) do { \
101 (tmp) = RB_LEFT(elm, field); \
102 if ((RB_LEFT(elm, field) = RB_RIGHT(tmp, field)) != NULL) { \
103 RB_PARENT(RB_RIGHT(tmp, field), field) = (elm); \
106 if ((RB_PARENT(tmp, field) = RB_PARENT(elm, field)) != NULL) { \
107 if ((elm) == RB_LEFT(RB_PARENT(elm, field), field)) \
108 RB_LEFT(RB_PARENT(elm, field), field) = (tmp); \
110 RB_RIGHT(RB_PARENT(elm, field), field) = (tmp); \
112 (head)->rbh_root = (tmp); \
113 RB_RIGHT(tmp, field) = (elm); \
114 RB_PARENT(elm, field) = (tmp); \
116 if ((RB_PARENT(tmp, field))) \
117 RB_AUGMENT(RB_PARENT(tmp, field)); \
118 } while (/*CONSTCOND*/ 0)
120 /* Generates prototypes and inline functions */
121 #define RB_PROTOTYPE(name, type, field, cmp) \
122 RB_PROTOTYPE_INTERNAL(name, type, field, cmp,)
123 #define RB_PROTOTYPE_STATIC(name, type, field, cmp) \
124 RB_PROTOTYPE_INTERNAL(name, type, field, cmp, _unused_ static)
125 #define RB_PROTOTYPE_INTERNAL(name, type, field, cmp, attr) \
126 attr void name##_RB_INSERT_COLOR(struct name *, struct type *); \
127 attr void name##_RB_REMOVE_COLOR(struct name *, struct type *, struct type *);\
128 attr struct type *name##_RB_REMOVE(struct name *, struct type *); \
129 attr struct type *name##_RB_INSERT(struct name *, struct type *); \
130 attr struct type *name##_RB_FIND(struct name *, struct type *); \
131 attr struct type *name##_RB_NFIND(struct name *, struct type *); \
132 attr struct type *name##_RB_NEXT(struct type *); \
133 attr struct type *name##_RB_PREV(struct type *); \
134 attr struct type *name##_RB_MINMAX(struct name *, int); \
139 /* Main rb operation.
140 * Moves node close to the key of elm to top
142 #define RB_GENERATE(name, type, field, cmp) \
143 RB_GENERATE_INTERNAL(name, type, field, cmp,)
144 #define RB_GENERATE_STATIC(name, type, field, cmp) \
145 RB_GENERATE_INTERNAL(name, type, field, cmp, _unused_ static)
146 #define RB_GENERATE_INTERNAL(name, type, field, cmp, attr) \
148 name##_RB_INSERT_COLOR(struct name *head, struct type *elm) \
150 struct type *parent, *gparent, *tmp; \
151 while ((parent = RB_PARENT(elm, field)) != NULL && \
152 RB_COLOR(parent, field) == RB_RED) { \
153 gparent = RB_PARENT(parent, field); \
154 assert(gparent != NULL); \
155 if (parent == RB_LEFT(gparent, field)) { \
156 tmp = RB_RIGHT(gparent, field); \
157 if (tmp && RB_COLOR(tmp, field) == RB_RED) { \
158 RB_COLOR(tmp, field) = RB_BLACK; \
159 RB_SET_BLACKRED(parent, gparent, field);\
163 if (RB_RIGHT(parent, field) == elm) { \
164 RB_ROTATE_LEFT(head, parent, tmp, field);\
169 RB_SET_BLACKRED(parent, gparent, field); \
170 RB_ROTATE_RIGHT(head, gparent, tmp, field); \
172 tmp = RB_LEFT(gparent, field); \
173 if (tmp && RB_COLOR(tmp, field) == RB_RED) { \
174 RB_COLOR(tmp, field) = RB_BLACK; \
175 RB_SET_BLACKRED(parent, gparent, field);\
179 if (RB_LEFT(parent, field) == elm) { \
180 RB_ROTATE_RIGHT(head, parent, tmp, field);\
185 RB_SET_BLACKRED(parent, gparent, field); \
186 RB_ROTATE_LEFT(head, gparent, tmp, field); \
189 RB_COLOR(head->rbh_root, field) = RB_BLACK; \
193 name##_RB_REMOVE_COLOR(struct name *head, struct type *parent, struct type *elm) \
196 while ((elm == NULL || RB_COLOR(elm, field) == RB_BLACK) && \
197 elm != RB_ROOT(head)) { \
198 if (RB_LEFT(parent, field) == elm) { \
199 tmp = RB_RIGHT(parent, field); \
200 if (RB_COLOR(tmp, field) == RB_RED) { \
201 RB_SET_BLACKRED(tmp, parent, field); \
202 RB_ROTATE_LEFT(head, parent, tmp, field);\
203 tmp = RB_RIGHT(parent, field); \
205 assert(tmp != NULL); \
206 if ((RB_LEFT(tmp, field) == NULL || \
207 RB_COLOR(RB_LEFT(tmp, field), field) == RB_BLACK) &&\
208 (RB_RIGHT(tmp, field) == NULL || \
209 RB_COLOR(RB_RIGHT(tmp, field), field) == RB_BLACK)) {\
210 RB_COLOR(tmp, field) = RB_RED; \
212 parent = RB_PARENT(elm, field); \
214 if (RB_RIGHT(tmp, field) == NULL || \
215 RB_COLOR(RB_RIGHT(tmp, field), field) == RB_BLACK) {\
216 struct type *oleft; \
217 if ((oleft = RB_LEFT(tmp, field)) \
219 RB_COLOR(oleft, field) = RB_BLACK;\
220 RB_COLOR(tmp, field) = RB_RED; \
221 RB_ROTATE_RIGHT(head, tmp, oleft, field);\
222 tmp = RB_RIGHT(parent, field); \
224 RB_COLOR(tmp, field) = RB_COLOR(parent, field);\
225 RB_COLOR(parent, field) = RB_BLACK; \
226 if (RB_RIGHT(tmp, field)) \
227 RB_COLOR(RB_RIGHT(tmp, field), field) = RB_BLACK;\
228 RB_ROTATE_LEFT(head, parent, tmp, field);\
229 elm = RB_ROOT(head); \
233 tmp = RB_LEFT(parent, field); \
234 if (RB_COLOR(tmp, field) == RB_RED) { \
235 RB_SET_BLACKRED(tmp, parent, field); \
236 RB_ROTATE_RIGHT(head, parent, tmp, field);\
237 tmp = RB_LEFT(parent, field); \
239 assert(tmp != NULL); \
240 if ((RB_LEFT(tmp, field) == NULL || \
241 RB_COLOR(RB_LEFT(tmp, field), field) == RB_BLACK) &&\
242 (RB_RIGHT(tmp, field) == NULL || \
243 RB_COLOR(RB_RIGHT(tmp, field), field) == RB_BLACK)) {\
244 RB_COLOR(tmp, field) = RB_RED; \
246 parent = RB_PARENT(elm, field); \
248 if (RB_LEFT(tmp, field) == NULL || \
249 RB_COLOR(RB_LEFT(tmp, field), field) == RB_BLACK) {\
250 struct type *oright; \
251 if ((oright = RB_RIGHT(tmp, field)) \
253 RB_COLOR(oright, field) = RB_BLACK;\
254 RB_COLOR(tmp, field) = RB_RED; \
255 RB_ROTATE_LEFT(head, tmp, oright, field);\
256 tmp = RB_LEFT(parent, field); \
258 RB_COLOR(tmp, field) = RB_COLOR(parent, field);\
259 RB_COLOR(parent, field) = RB_BLACK; \
260 if (RB_LEFT(tmp, field)) \
261 RB_COLOR(RB_LEFT(tmp, field), field) = RB_BLACK;\
262 RB_ROTATE_RIGHT(head, parent, tmp, field);\
263 elm = RB_ROOT(head); \
269 RB_COLOR(elm, field) = RB_BLACK; \
273 name##_RB_REMOVE(struct name *head, struct type *elm) \
275 struct type *child, *parent, *old = elm; \
277 if (RB_LEFT(elm, field) == NULL) \
278 child = RB_RIGHT(elm, field); \
279 else if (RB_RIGHT(elm, field) == NULL) \
280 child = RB_LEFT(elm, field); \
283 elm = RB_RIGHT(elm, field); \
284 while ((left = RB_LEFT(elm, field)) != NULL) \
286 child = RB_RIGHT(elm, field); \
287 parent = RB_PARENT(elm, field); \
288 color = RB_COLOR(elm, field); \
290 RB_PARENT(child, field) = parent; \
292 if (RB_LEFT(parent, field) == elm) \
293 RB_LEFT(parent, field) = child; \
295 RB_RIGHT(parent, field) = child; \
296 RB_AUGMENT(parent); \
298 RB_ROOT(head) = child; \
299 if (RB_PARENT(elm, field) == old) \
301 (elm)->field = (old)->field; \
302 if (RB_PARENT(old, field)) { \
303 if (RB_LEFT(RB_PARENT(old, field), field) == old)\
304 RB_LEFT(RB_PARENT(old, field), field) = elm;\
306 RB_RIGHT(RB_PARENT(old, field), field) = elm;\
307 RB_AUGMENT(RB_PARENT(old, field)); \
309 RB_ROOT(head) = elm; \
310 assert(RB_LEFT(old, field) != NULL); \
311 RB_PARENT(RB_LEFT(old, field), field) = elm; \
312 if (RB_RIGHT(old, field)) \
313 RB_PARENT(RB_RIGHT(old, field), field) = elm; \
318 } while ((left = RB_PARENT(left, field)) != NULL); \
322 parent = RB_PARENT(elm, field); \
323 color = RB_COLOR(elm, field); \
325 RB_PARENT(child, field) = parent; \
327 if (RB_LEFT(parent, field) == elm) \
328 RB_LEFT(parent, field) = child; \
330 RB_RIGHT(parent, field) = child; \
331 RB_AUGMENT(parent); \
333 RB_ROOT(head) = child; \
335 if (color == RB_BLACK) \
336 name##_RB_REMOVE_COLOR(head, parent, child); \
340 /* Inserts a node into the RB tree */ \
342 name##_RB_INSERT(struct name *head, struct type *elm) \
345 struct type *parent = NULL; \
347 tmp = RB_ROOT(head); \
350 comp = (cmp)(elm, parent); \
352 tmp = RB_LEFT(tmp, field); \
354 tmp = RB_RIGHT(tmp, field); \
358 RB_SET(elm, parent, field); \
359 if (parent != NULL) { \
361 RB_LEFT(parent, field) = elm; \
363 RB_RIGHT(parent, field) = elm; \
364 RB_AUGMENT(parent); \
366 RB_ROOT(head) = elm; \
367 name##_RB_INSERT_COLOR(head, elm); \
371 /* Finds the node with the same key as elm */ \
373 name##_RB_FIND(struct name *head, struct type *elm) \
375 struct type *tmp = RB_ROOT(head); \
378 comp = cmp(elm, tmp); \
380 tmp = RB_LEFT(tmp, field); \
382 tmp = RB_RIGHT(tmp, field); \
389 /* Finds the first node greater than or equal to the search key */ \
391 name##_RB_NFIND(struct name *head, struct type *elm) \
393 struct type *tmp = RB_ROOT(head); \
394 struct type *res = NULL; \
397 comp = cmp(elm, tmp); \
400 tmp = RB_LEFT(tmp, field); \
403 tmp = RB_RIGHT(tmp, field); \
412 name##_RB_NEXT(struct type *elm) \
414 if (RB_RIGHT(elm, field)) { \
415 elm = RB_RIGHT(elm, field); \
416 while (RB_LEFT(elm, field)) \
417 elm = RB_LEFT(elm, field); \
419 if (RB_PARENT(elm, field) && \
420 (elm == RB_LEFT(RB_PARENT(elm, field), field))) \
421 elm = RB_PARENT(elm, field); \
423 while (RB_PARENT(elm, field) && \
424 (elm == RB_RIGHT(RB_PARENT(elm, field), field)))\
425 elm = RB_PARENT(elm, field); \
426 elm = RB_PARENT(elm, field); \
434 name##_RB_PREV(struct type *elm) \
436 if (RB_LEFT(elm, field)) { \
437 elm = RB_LEFT(elm, field); \
438 while (RB_RIGHT(elm, field)) \
439 elm = RB_RIGHT(elm, field); \
441 if (RB_PARENT(elm, field) && \
442 (elm == RB_RIGHT(RB_PARENT(elm, field), field))) \
443 elm = RB_PARENT(elm, field); \
445 while (RB_PARENT(elm, field) && \
446 (elm == RB_LEFT(RB_PARENT(elm, field), field)))\
447 elm = RB_PARENT(elm, field); \
448 elm = RB_PARENT(elm, field); \
455 name##_RB_MINMAX(struct name *head, int val) \
457 struct type *tmp = RB_ROOT(head); \
458 struct type *parent = NULL; \
462 tmp = RB_LEFT(tmp, field); \
464 tmp = RB_RIGHT(tmp, field); \
472 #define RB_INSERT(name, x, y) name##_RB_INSERT(x, y)
473 #define RB_REMOVE(name, x, y) name##_RB_REMOVE(x, y)
474 #define RB_FIND(name, x, y) name##_RB_FIND(x, y)
475 #define RB_NFIND(name, x, y) name##_RB_NFIND(x, y)
476 #define RB_NEXT(name, x, y) name##_RB_NEXT(y)
477 #define RB_PREV(name, x, y) name##_RB_PREV(y)
478 #define RB_MIN(name, x) name##_RB_MINMAX(x, RB_NEGINF)
479 #define RB_MAX(name, x) name##_RB_MINMAX(x, RB_INF)
481 #define RB_FOREACH(x, name, head) \
482 for ((x) = RB_MIN(name, head); \
484 (x) = name##_RB_NEXT(x))
486 #define RB_FOREACH_FROM(x, name, y) \
488 ((x) != NULL) && ((y) = name##_RB_NEXT(x), (x) != NULL); \
491 #define RB_FOREACH_SAFE(x, name, head, y) \
492 for ((x) = RB_MIN(name, head); \
493 ((x) != NULL) && ((y) = name##_RB_NEXT(x), (x) != NULL); \
496 #define RB_FOREACH_REVERSE(x, name, head) \
497 for ((x) = RB_MAX(name, head); \
499 (x) = name##_RB_PREV(x))
501 #define RB_FOREACH_REVERSE_FROM(x, name, y) \
503 ((x) != NULL) && ((y) = name##_RB_PREV(x), (x) != NULL); \
506 #define RB_FOREACH_REVERSE_SAFE(x, name, head, y) \
507 for ((x) = RB_MAX(name, head); \
508 ((x) != NULL) && ((y) = name##_RB_PREV(x), (x) != NULL); \
511 #endif /* _SYS_TREE_H_ */