summaryrefslogtreecommitdiff
path: root/src/common/tree.h
diff options
context:
space:
mode:
Diffstat (limited to 'src/common/tree.h')
-rw-r--r--src/common/tree.h822
1 files changed, 822 insertions, 0 deletions
diff --git a/src/common/tree.h b/src/common/tree.h
new file mode 100644
index 000000000..a6b636646
--- /dev/null
+++ b/src/common/tree.h
@@ -0,0 +1,822 @@
1/* $NetBSD: tree.h,v 1.8 2004/03/28 19:38:30 provos Exp $ */
2/* $OpenBSD: tree.h,v 1.7 2002/10/17 21:51:54 art Exp $ */
3/* $FreeBSD$ */
4
5/*-
6 * Copyright 2002 Niels Provos <provos@citi.umich.edu>
7 * All rights reserved.
8 *
9 * Redistribution and use in source and binary forms, with or without
10 * modification, are permitted provided that the following conditions
11 * are met:
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.
17 *
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.
28 */
29
30#ifndef _SYS_TREE_H_
31#define _SYS_TREE_H_
32
33/* FreeBSD <sys/cdefs.h> has a lot of defines we don't really want. */
34/* tree.h only actually uses __inline and __unused, so we'll just define those. */
35
36/* #include <sys/cdefs.h> */
37
38#ifndef __inline
39#define __inline inline
40#endif
41
42/*
43 * This file defines data structures for different types of trees:
44 * splay trees and red-black trees.
45 *
46 * A splay tree is a self-organizing data structure. Every operation
47 * on the tree causes a splay to happen. The splay moves the requested
48 * node to the root of the tree and partly rebalances it.
49 *
50 * This has the benefit that request locality causes faster lookups as
51 * the requested nodes move to the top of the tree. On the other hand,
52 * every lookup causes memory writes.
53 *
54 * The Balance Theorem bounds the total access time for m operations
55 * and n inserts on an initially empty tree as O((m + n)lg n). The
56 * amortized cost for a sequence of m accesses to a splay tree is O(lg n);
57 *
58 * A red-black tree is a binary search tree with the node color as an
59 * extra attribute. It fulfills a set of conditions:
60 * - every search path from the root to a leaf consists of the
61 * same number of black nodes,
62 * - each red node (except for the root) has a black parent,
63 * - each leaf node is black.
64 *
65 * Every operation on a red-black tree is bounded as O(lg n).
66 * The maximum height of a red-black tree is 2lg (n+1).
67 */
68
69#define SPLAY_HEAD(name, type) \
70 struct name { \
71 struct type* sph_root; /* root of the tree */ \
72 }
73
74#define SPLAY_INITIALIZER(root) \
75 { NULL }
76
77#define SPLAY_INIT(root) \
78 do { \
79 (root)->sph_root = NULL; \
80 } while (/*CONSTCOND*/ 0)
81
82#define SPLAY_ENTRY(type) \
83 struct { \
84 struct type* spe_left; /* left element */ \
85 struct type* spe_right; /* right element */ \
86 }
87
88#define SPLAY_LEFT(elm, field) (elm)->field.spe_left
89#define SPLAY_RIGHT(elm, field) (elm)->field.spe_right
90#define SPLAY_ROOT(head) (head)->sph_root
91#define SPLAY_EMPTY(head) (SPLAY_ROOT(head) == NULL)
92
93/* SPLAY_ROTATE_{LEFT,RIGHT} expect that tmp hold SPLAY_{RIGHT,LEFT} */
94#define SPLAY_ROTATE_RIGHT(head, tmp, field) \
95 do { \
96 SPLAY_LEFT((head)->sph_root, field) = SPLAY_RIGHT(tmp, field); \
97 SPLAY_RIGHT(tmp, field) = (head)->sph_root; \
98 (head)->sph_root = tmp; \
99 } while (/*CONSTCOND*/ 0)
100
101#define SPLAY_ROTATE_LEFT(head, tmp, field) \
102 do { \
103 SPLAY_RIGHT((head)->sph_root, field) = SPLAY_LEFT(tmp, field); \
104 SPLAY_LEFT(tmp, field) = (head)->sph_root; \
105 (head)->sph_root = tmp; \
106 } while (/*CONSTCOND*/ 0)
107
108#define SPLAY_LINKLEFT(head, tmp, field) \
109 do { \
110 SPLAY_LEFT(tmp, field) = (head)->sph_root; \
111 tmp = (head)->sph_root; \
112 (head)->sph_root = SPLAY_LEFT((head)->sph_root, field); \
113 } while (/*CONSTCOND*/ 0)
114
115#define SPLAY_LINKRIGHT(head, tmp, field) \
116 do { \
117 SPLAY_RIGHT(tmp, field) = (head)->sph_root; \
118 tmp = (head)->sph_root; \
119 (head)->sph_root = SPLAY_RIGHT((head)->sph_root, field); \
120 } while (/*CONSTCOND*/ 0)
121
122#define SPLAY_ASSEMBLE(head, node, left, right, field) \
123 do { \
124 SPLAY_RIGHT(left, field) = SPLAY_LEFT((head)->sph_root, field); \
125 SPLAY_LEFT(right, field) = SPLAY_RIGHT((head)->sph_root, field); \
126 SPLAY_LEFT((head)->sph_root, field) = SPLAY_RIGHT(node, field); \
127 SPLAY_RIGHT((head)->sph_root, field) = SPLAY_LEFT(node, field); \
128 } while (/*CONSTCOND*/ 0)
129
130/* Generates prototypes and inline functions */
131
132#define SPLAY_PROTOTYPE(name, type, field, cmp) \
133 void name##_SPLAY(struct name*, struct type*); \
134 void name##_SPLAY_MINMAX(struct name*, int); \
135 struct type* name##_SPLAY_INSERT(struct name*, struct type*); \
136 struct type* name##_SPLAY_REMOVE(struct name*, struct type*); \
137 \
138 /* Finds the node with the same key as elm */ \
139 static __inline struct type* name##_SPLAY_FIND(struct name* head, struct type* elm) { \
140 if (SPLAY_EMPTY(head)) \
141 return (NULL); \
142 name##_SPLAY(head, elm); \
143 if ((cmp)(elm, (head)->sph_root) == 0) \
144 return (head->sph_root); \
145 return (NULL); \
146 } \
147 \
148 static __inline struct type* name##_SPLAY_NEXT(struct name* head, struct type* elm) { \
149 name##_SPLAY(head, elm); \
150 if (SPLAY_RIGHT(elm, field) != NULL) { \
151 elm = SPLAY_RIGHT(elm, field); \
152 while (SPLAY_LEFT(elm, field) != NULL) { \
153 elm = SPLAY_LEFT(elm, field); \
154 } \
155 } else \
156 elm = NULL; \
157 return (elm); \
158 } \
159 \
160 static __inline struct type* name##_SPLAY_MIN_MAX(struct name* head, int val) { \
161 name##_SPLAY_MINMAX(head, val); \
162 return (SPLAY_ROOT(head)); \
163 }
164
165/* Main splay operation.
166 * Moves node close to the key of elm to top
167 */
168#define SPLAY_GENERATE(name, type, field, cmp) \
169 struct type* name##_SPLAY_INSERT(struct name* head, struct type* elm) { \
170 if (SPLAY_EMPTY(head)) { \
171 SPLAY_LEFT(elm, field) = SPLAY_RIGHT(elm, field) = NULL; \
172 } else { \
173 int __comp; \
174 name##_SPLAY(head, elm); \
175 __comp = (cmp)(elm, (head)->sph_root); \
176 if (__comp < 0) { \
177 SPLAY_LEFT(elm, field) = SPLAY_LEFT((head)->sph_root, field); \
178 SPLAY_RIGHT(elm, field) = (head)->sph_root; \
179 SPLAY_LEFT((head)->sph_root, field) = NULL; \
180 } else if (__comp > 0) { \
181 SPLAY_RIGHT(elm, field) = SPLAY_RIGHT((head)->sph_root, field); \
182 SPLAY_LEFT(elm, field) = (head)->sph_root; \
183 SPLAY_RIGHT((head)->sph_root, field) = NULL; \
184 } else \
185 return ((head)->sph_root); \
186 } \
187 (head)->sph_root = (elm); \
188 return (NULL); \
189 } \
190 \
191 struct type* name##_SPLAY_REMOVE(struct name* head, struct type* elm) { \
192 struct type* __tmp; \
193 if (SPLAY_EMPTY(head)) \
194 return (NULL); \
195 name##_SPLAY(head, elm); \
196 if ((cmp)(elm, (head)->sph_root) == 0) { \
197 if (SPLAY_LEFT((head)->sph_root, field) == NULL) { \
198 (head)->sph_root = SPLAY_RIGHT((head)->sph_root, field); \
199 } else { \
200 __tmp = SPLAY_RIGHT((head)->sph_root, field); \
201 (head)->sph_root = SPLAY_LEFT((head)->sph_root, field); \
202 name##_SPLAY(head, elm); \
203 SPLAY_RIGHT((head)->sph_root, field) = __tmp; \
204 } \
205 return (elm); \
206 } \
207 return (NULL); \
208 } \
209 \
210 void name##_SPLAY(struct name* head, struct type* elm) { \
211 struct type __node, *__left, *__right, *__tmp; \
212 int __comp; \
213 \
214 SPLAY_LEFT(&__node, field) = SPLAY_RIGHT(&__node, field) = NULL; \
215 __left = __right = &__node; \
216 \
217 while ((__comp = (cmp)(elm, (head)->sph_root)) != 0) { \
218 if (__comp < 0) { \
219 __tmp = SPLAY_LEFT((head)->sph_root, field); \
220 if (__tmp == NULL) \
221 break; \
222 if ((cmp)(elm, __tmp) < 0) { \
223 SPLAY_ROTATE_RIGHT(head, __tmp, field); \
224 if (SPLAY_LEFT((head)->sph_root, field) == NULL) \
225 break; \
226 } \
227 SPLAY_LINKLEFT(head, __right, field); \
228 } else if (__comp > 0) { \
229 __tmp = SPLAY_RIGHT((head)->sph_root, field); \
230 if (__tmp == NULL) \
231 break; \
232 if ((cmp)(elm, __tmp) > 0) { \
233 SPLAY_ROTATE_LEFT(head, __tmp, field); \
234 if (SPLAY_RIGHT((head)->sph_root, field) == NULL) \
235 break; \
236 } \
237 SPLAY_LINKRIGHT(head, __left, field); \
238 } \
239 } \
240 SPLAY_ASSEMBLE(head, &__node, __left, __right, field); \
241 } \
242 \
243 /* Splay with either the minimum or the maximum element \
244 * Used to find minimum or maximum element in tree. \
245 */ \
246 void name##_SPLAY_MINMAX(struct name* head, int __comp) { \
247 struct type __node, *__left, *__right, *__tmp; \
248 \
249 SPLAY_LEFT(&__node, field) = SPLAY_RIGHT(&__node, field) = NULL; \
250 __left = __right = &__node; \
251 \
252 while (1) { \
253 if (__comp < 0) { \
254 __tmp = SPLAY_LEFT((head)->sph_root, field); \
255 if (__tmp == NULL) \
256 break; \
257 if (__comp < 0) { \
258 SPLAY_ROTATE_RIGHT(head, __tmp, field); \
259 if (SPLAY_LEFT((head)->sph_root, field) == NULL) \
260 break; \
261 } \
262 SPLAY_LINKLEFT(head, __right, field); \
263 } else if (__comp > 0) { \
264 __tmp = SPLAY_RIGHT((head)->sph_root, field); \
265 if (__tmp == NULL) \
266 break; \
267 if (__comp > 0) { \
268 SPLAY_ROTATE_LEFT(head, __tmp, field); \
269 if (SPLAY_RIGHT((head)->sph_root, field) == NULL) \
270 break; \
271 } \
272 SPLAY_LINKRIGHT(head, __left, field); \
273 } \
274 } \
275 SPLAY_ASSEMBLE(head, &__node, __left, __right, field); \
276 }
277
278#define SPLAY_NEGINF -1
279#define SPLAY_INF 1
280
281#define SPLAY_INSERT(name, x, y) name##_SPLAY_INSERT(x, y)
282#define SPLAY_REMOVE(name, x, y) name##_SPLAY_REMOVE(x, y)
283#define SPLAY_FIND(name, x, y) name##_SPLAY_FIND(x, y)
284#define SPLAY_NEXT(name, x, y) name##_SPLAY_NEXT(x, y)
285#define SPLAY_MIN(name, x) (SPLAY_EMPTY(x) ? NULL : name##_SPLAY_MIN_MAX(x, SPLAY_NEGINF))
286#define SPLAY_MAX(name, x) (SPLAY_EMPTY(x) ? NULL : name##_SPLAY_MIN_MAX(x, SPLAY_INF))
287
288#define SPLAY_FOREACH(x, name, head) \
289 for ((x) = SPLAY_MIN(name, head); (x) != NULL; (x) = SPLAY_NEXT(name, head, x))
290
291/* Macros that define a red-black tree */
292#define RB_HEAD(name, type) \
293 struct name { \
294 struct type* rbh_root; /* root of the tree */ \
295 }
296
297#define RB_INITIALIZER(root) \
298 { NULL }
299
300#define RB_INIT(root) \
301 do { \
302 (root)->rbh_root = NULL; \
303 } while (/*CONSTCOND*/ 0)
304
305#define RB_BLACK 0
306#define RB_RED 1
307#define RB_ENTRY(type) \
308 struct { \
309 struct type* rbe_left; /* left element */ \
310 struct type* rbe_right; /* right element */ \
311 struct type* rbe_parent; /* parent element */ \
312 int rbe_color; /* node color */ \
313 }
314
315#define RB_LEFT(elm, field) (elm)->field.rbe_left
316#define RB_RIGHT(elm, field) (elm)->field.rbe_right
317#define RB_PARENT(elm, field) (elm)->field.rbe_parent
318#define RB_COLOR(elm, field) (elm)->field.rbe_color
319#define RB_ROOT(head) (head)->rbh_root
320#define RB_EMPTY(head) (RB_ROOT(head) == NULL)
321
322#define RB_SET(elm, parent, field) \
323 do { \
324 RB_PARENT(elm, field) = parent; \
325 RB_LEFT(elm, field) = RB_RIGHT(elm, field) = NULL; \
326 RB_COLOR(elm, field) = RB_RED; \
327 } while (/*CONSTCOND*/ 0)
328
329#define RB_SET_BLACKRED(black, red, field) \
330 do { \
331 RB_COLOR(black, field) = RB_BLACK; \
332 RB_COLOR(red, field) = RB_RED; \
333 } while (/*CONSTCOND*/ 0)
334
335#ifndef RB_AUGMENT
336#define RB_AUGMENT(x) \
337 do { \
338 } while (0)
339#endif
340
341#define RB_ROTATE_LEFT(head, elm, tmp, field) \
342 do { \
343 (tmp) = RB_RIGHT(elm, field); \
344 if ((RB_RIGHT(elm, field) = RB_LEFT(tmp, field)) != NULL) { \
345 RB_PARENT(RB_LEFT(tmp, field), field) = (elm); \
346 } \
347 RB_AUGMENT(elm); \
348 if ((RB_PARENT(tmp, field) = RB_PARENT(elm, field)) != NULL) { \
349 if ((elm) == RB_LEFT(RB_PARENT(elm, field), field)) \
350 RB_LEFT(RB_PARENT(elm, field), field) = (tmp); \
351 else \
352 RB_RIGHT(RB_PARENT(elm, field), field) = (tmp); \
353 } else \
354 (head)->rbh_root = (tmp); \
355 RB_LEFT(tmp, field) = (elm); \
356 RB_PARENT(elm, field) = (tmp); \
357 RB_AUGMENT(tmp); \
358 if ((RB_PARENT(tmp, field))) \
359 RB_AUGMENT(RB_PARENT(tmp, field)); \
360 } while (/*CONSTCOND*/ 0)
361
362#define RB_ROTATE_RIGHT(head, elm, tmp, field) \
363 do { \
364 (tmp) = RB_LEFT(elm, field); \
365 if ((RB_LEFT(elm, field) = RB_RIGHT(tmp, field)) != NULL) { \
366 RB_PARENT(RB_RIGHT(tmp, field), field) = (elm); \
367 } \
368 RB_AUGMENT(elm); \
369 if ((RB_PARENT(tmp, field) = RB_PARENT(elm, field)) != NULL) { \
370 if ((elm) == RB_LEFT(RB_PARENT(elm, field), field)) \
371 RB_LEFT(RB_PARENT(elm, field), field) = (tmp); \
372 else \
373 RB_RIGHT(RB_PARENT(elm, field), field) = (tmp); \
374 } else \
375 (head)->rbh_root = (tmp); \
376 RB_RIGHT(tmp, field) = (elm); \
377 RB_PARENT(elm, field) = (tmp); \
378 RB_AUGMENT(tmp); \
379 if ((RB_PARENT(tmp, field))) \
380 RB_AUGMENT(RB_PARENT(tmp, field)); \
381 } while (/*CONSTCOND*/ 0)
382
383/* Generates prototypes and inline functions */
384#define RB_PROTOTYPE(name, type, field, cmp) RB_PROTOTYPE_INTERNAL(name, type, field, cmp, )
385#define RB_PROTOTYPE_STATIC(name, type, field, cmp) \
386 RB_PROTOTYPE_INTERNAL(name, type, field, cmp, static)
387#define RB_PROTOTYPE_INTERNAL(name, type, field, cmp, attr) \
388 RB_PROTOTYPE_INSERT_COLOR(name, type, attr); \
389 RB_PROTOTYPE_REMOVE_COLOR(name, type, attr); \
390 RB_PROTOTYPE_INSERT(name, type, attr); \
391 RB_PROTOTYPE_REMOVE(name, type, attr); \
392 RB_PROTOTYPE_FIND(name, type, attr); \
393 RB_PROTOTYPE_NFIND(name, type, attr); \
394 RB_PROTOTYPE_FIND_LIGHT(name, type, attr); \
395 RB_PROTOTYPE_NFIND_LIGHT(name, type, attr); \
396 RB_PROTOTYPE_NEXT(name, type, attr); \
397 RB_PROTOTYPE_PREV(name, type, attr); \
398 RB_PROTOTYPE_MINMAX(name, type, attr);
399#define RB_PROTOTYPE_INSERT_COLOR(name, type, attr) \
400 attr void name##_RB_INSERT_COLOR(struct name*, struct type*)
401#define RB_PROTOTYPE_REMOVE_COLOR(name, type, attr) \
402 attr void name##_RB_REMOVE_COLOR(struct name*, struct type*, struct type*)
403#define RB_PROTOTYPE_REMOVE(name, type, attr) \
404 attr struct type* name##_RB_REMOVE(struct name*, struct type*)
405#define RB_PROTOTYPE_INSERT(name, type, attr) \
406 attr struct type* name##_RB_INSERT(struct name*, struct type*)
407#define RB_PROTOTYPE_FIND(name, type, attr) \
408 attr struct type* name##_RB_FIND(struct name*, struct type*)
409#define RB_PROTOTYPE_NFIND(name, type, attr) \
410 attr struct type* name##_RB_NFIND(struct name*, struct type*)
411#define RB_PROTOTYPE_FIND_LIGHT(name, type, attr) \
412 attr struct type* name##_RB_FIND_LIGHT(struct name*, const void*)
413#define RB_PROTOTYPE_NFIND_LIGHT(name, type, attr) \
414 attr struct type* name##_RB_NFIND_LIGHT(struct name*, const void*)
415#define RB_PROTOTYPE_NEXT(name, type, attr) attr struct type* name##_RB_NEXT(struct type*)
416#define RB_PROTOTYPE_PREV(name, type, attr) attr struct type* name##_RB_PREV(struct type*)
417#define RB_PROTOTYPE_MINMAX(name, type, attr) attr struct type* name##_RB_MINMAX(struct name*, int)
418
419/* Main rb operation.
420 * Moves node close to the key of elm to top
421 */
422#define RB_GENERATE_WITHOUT_COMPARE(name, type, field) \
423 RB_GENERATE_WITHOUT_COMPARE_INTERNAL(name, type, field, )
424#define RB_GENERATE_WITHOUT_COMPARE_STATIC(name, type, field) \
425 RB_GENERATE_WITHOUT_COMPARE_INTERNAL(name, type, field, static)
426#define RB_GENERATE_WITHOUT_COMPARE_INTERNAL(name, type, field, attr) \
427 RB_GENERATE_REMOVE_COLOR(name, type, field, attr) \
428 RB_GENERATE_REMOVE(name, type, field, attr) \
429 RB_GENERATE_NEXT(name, type, field, attr) \
430 RB_GENERATE_PREV(name, type, field, attr) \
431 RB_GENERATE_MINMAX(name, type, field, attr)
432
433#define RB_GENERATE_WITH_COMPARE(name, type, field, cmp, lcmp) \
434 RB_GENERATE_WITH_COMPARE_INTERNAL(name, type, field, cmp, lcmp, )
435#define RB_GENERATE_WITH_COMPARE_STATIC(name, type, field, cmp, lcmp) \
436 RB_GENERATE_WITH_COMPARE_INTERNAL(name, type, field, cmp, lcmp, static)
437#define RB_GENERATE_WITH_COMPARE_INTERNAL(name, type, field, cmp, lcmp, attr) \
438 RB_GENERATE_INSERT_COLOR(name, type, field, attr) \
439 RB_GENERATE_INSERT(name, type, field, cmp, attr) \
440 RB_GENERATE_FIND(name, type, field, cmp, attr) \
441 RB_GENERATE_NFIND(name, type, field, cmp, attr) \
442 RB_GENERATE_FIND_LIGHT(name, type, field, lcmp, attr) \
443 RB_GENERATE_NFIND_LIGHT(name, type, field, lcmp, attr)
444
445#define RB_GENERATE_ALL(name, type, field, cmp) RB_GENERATE_ALL_INTERNAL(name, type, field, cmp, )
446#define RB_GENERATE_ALL_STATIC(name, type, field, cmp) \
447 RB_GENERATE_ALL_INTERNAL(name, type, field, cmp, static)
448#define RB_GENERATE_ALL_INTERNAL(name, type, field, cmp, attr) \
449 RB_GENERATE_WITHOUT_COMPARE_INTERNAL(name, type, field, attr) \
450 RB_GENERATE_WITH_COMPARE_INTERNAL(name, type, field, cmp, attr)
451
452#define RB_GENERATE_INSERT_COLOR(name, type, field, attr) \
453 attr void name##_RB_INSERT_COLOR(struct name* head, struct type* elm) { \
454 struct type *parent, *gparent, *tmp; \
455 while ((parent = RB_PARENT(elm, field)) != NULL && RB_COLOR(parent, field) == RB_RED) { \
456 gparent = RB_PARENT(parent, field); \
457 if (parent == RB_LEFT(gparent, field)) { \
458 tmp = RB_RIGHT(gparent, field); \
459 if (tmp && RB_COLOR(tmp, field) == RB_RED) { \
460 RB_COLOR(tmp, field) = RB_BLACK; \
461 RB_SET_BLACKRED(parent, gparent, field); \
462 elm = gparent; \
463 continue; \
464 } \
465 if (RB_RIGHT(parent, field) == elm) { \
466 RB_ROTATE_LEFT(head, parent, tmp, field); \
467 tmp = parent; \
468 parent = elm; \
469 elm = tmp; \
470 } \
471 RB_SET_BLACKRED(parent, gparent, field); \
472 RB_ROTATE_RIGHT(head, gparent, tmp, field); \
473 } else { \
474 tmp = RB_LEFT(gparent, field); \
475 if (tmp && RB_COLOR(tmp, field) == RB_RED) { \
476 RB_COLOR(tmp, field) = RB_BLACK; \
477 RB_SET_BLACKRED(parent, gparent, field); \
478 elm = gparent; \
479 continue; \
480 } \
481 if (RB_LEFT(parent, field) == elm) { \
482 RB_ROTATE_RIGHT(head, parent, tmp, field); \
483 tmp = parent; \
484 parent = elm; \
485 elm = tmp; \
486 } \
487 RB_SET_BLACKRED(parent, gparent, field); \
488 RB_ROTATE_LEFT(head, gparent, tmp, field); \
489 } \
490 } \
491 RB_COLOR(head->rbh_root, field) = RB_BLACK; \
492 }
493
494#define RB_GENERATE_REMOVE_COLOR(name, type, field, attr) \
495 attr void name##_RB_REMOVE_COLOR(struct name* head, struct type* parent, struct type* elm) { \
496 struct type* tmp; \
497 while ((elm == NULL || RB_COLOR(elm, field) == RB_BLACK) && elm != RB_ROOT(head)) { \
498 if (RB_LEFT(parent, field) == elm) { \
499 tmp = RB_RIGHT(parent, field); \
500 if (RB_COLOR(tmp, field) == RB_RED) { \
501 RB_SET_BLACKRED(tmp, parent, field); \
502 RB_ROTATE_LEFT(head, parent, tmp, field); \
503 tmp = RB_RIGHT(parent, field); \
504 } \
505 if ((RB_LEFT(tmp, field) == NULL || \
506 RB_COLOR(RB_LEFT(tmp, field), field) == RB_BLACK) && \
507 (RB_RIGHT(tmp, field) == NULL || \
508 RB_COLOR(RB_RIGHT(tmp, field), field) == RB_BLACK)) { \
509 RB_COLOR(tmp, field) = RB_RED; \
510 elm = parent; \
511 parent = RB_PARENT(elm, field); \
512 } else { \
513 if (RB_RIGHT(tmp, field) == NULL || \
514 RB_COLOR(RB_RIGHT(tmp, field), field) == RB_BLACK) { \
515 struct type* oleft; \
516 if ((oleft = RB_LEFT(tmp, field)) != NULL) \
517 RB_COLOR(oleft, field) = RB_BLACK; \
518 RB_COLOR(tmp, field) = RB_RED; \
519 RB_ROTATE_RIGHT(head, tmp, oleft, field); \
520 tmp = RB_RIGHT(parent, field); \
521 } \
522 RB_COLOR(tmp, field) = RB_COLOR(parent, field); \
523 RB_COLOR(parent, field) = RB_BLACK; \
524 if (RB_RIGHT(tmp, field)) \
525 RB_COLOR(RB_RIGHT(tmp, field), field) = RB_BLACK; \
526 RB_ROTATE_LEFT(head, parent, tmp, field); \
527 elm = RB_ROOT(head); \
528 break; \
529 } \
530 } else { \
531 tmp = RB_LEFT(parent, field); \
532 if (RB_COLOR(tmp, field) == RB_RED) { \
533 RB_SET_BLACKRED(tmp, parent, field); \
534 RB_ROTATE_RIGHT(head, parent, tmp, field); \
535 tmp = RB_LEFT(parent, field); \
536 } \
537 if ((RB_LEFT(tmp, field) == NULL || \
538 RB_COLOR(RB_LEFT(tmp, field), field) == RB_BLACK) && \
539 (RB_RIGHT(tmp, field) == NULL || \
540 RB_COLOR(RB_RIGHT(tmp, field), field) == RB_BLACK)) { \
541 RB_COLOR(tmp, field) = RB_RED; \
542 elm = parent; \
543 parent = RB_PARENT(elm, field); \
544 } else { \
545 if (RB_LEFT(tmp, field) == NULL || \
546 RB_COLOR(RB_LEFT(tmp, field), field) == RB_BLACK) { \
547 struct type* oright; \
548 if ((oright = RB_RIGHT(tmp, field)) != NULL) \
549 RB_COLOR(oright, field) = RB_BLACK; \
550 RB_COLOR(tmp, field) = RB_RED; \
551 RB_ROTATE_LEFT(head, tmp, oright, field); \
552 tmp = RB_LEFT(parent, field); \
553 } \
554 RB_COLOR(tmp, field) = RB_COLOR(parent, field); \
555 RB_COLOR(parent, field) = RB_BLACK; \
556 if (RB_LEFT(tmp, field)) \
557 RB_COLOR(RB_LEFT(tmp, field), field) = RB_BLACK; \
558 RB_ROTATE_RIGHT(head, parent, tmp, field); \
559 elm = RB_ROOT(head); \
560 break; \
561 } \
562 } \
563 } \
564 if (elm) \
565 RB_COLOR(elm, field) = RB_BLACK; \
566 }
567
568#define RB_GENERATE_REMOVE(name, type, field, attr) \
569 attr struct type* name##_RB_REMOVE(struct name* head, struct type* elm) { \
570 struct type *child, *parent, *old = elm; \
571 int color; \
572 if (RB_LEFT(elm, field) == NULL) \
573 child = RB_RIGHT(elm, field); \
574 else if (RB_RIGHT(elm, field) == NULL) \
575 child = RB_LEFT(elm, field); \
576 else { \
577 struct type* left; \
578 elm = RB_RIGHT(elm, field); \
579 while ((left = RB_LEFT(elm, field)) != NULL) \
580 elm = left; \
581 child = RB_RIGHT(elm, field); \
582 parent = RB_PARENT(elm, field); \
583 color = RB_COLOR(elm, field); \
584 if (child) \
585 RB_PARENT(child, field) = parent; \
586 if (parent) { \
587 if (RB_LEFT(parent, field) == elm) \
588 RB_LEFT(parent, field) = child; \
589 else \
590 RB_RIGHT(parent, field) = child; \
591 RB_AUGMENT(parent); \
592 } else \
593 RB_ROOT(head) = child; \
594 if (RB_PARENT(elm, field) == old) \
595 parent = elm; \
596 (elm)->field = (old)->field; \
597 if (RB_PARENT(old, field)) { \
598 if (RB_LEFT(RB_PARENT(old, field), field) == old) \
599 RB_LEFT(RB_PARENT(old, field), field) = elm; \
600 else \
601 RB_RIGHT(RB_PARENT(old, field), field) = elm; \
602 RB_AUGMENT(RB_PARENT(old, field)); \
603 } else \
604 RB_ROOT(head) = elm; \
605 RB_PARENT(RB_LEFT(old, field), field) = elm; \
606 if (RB_RIGHT(old, field)) \
607 RB_PARENT(RB_RIGHT(old, field), field) = elm; \
608 if (parent) { \
609 left = parent; \
610 do { \
611 RB_AUGMENT(left); \
612 } while ((left = RB_PARENT(left, field)) != NULL); \
613 } \
614 goto color; \
615 } \
616 parent = RB_PARENT(elm, field); \
617 color = RB_COLOR(elm, field); \
618 if (child) \
619 RB_PARENT(child, field) = parent; \
620 if (parent) { \
621 if (RB_LEFT(parent, field) == elm) \
622 RB_LEFT(parent, field) = child; \
623 else \
624 RB_RIGHT(parent, field) = child; \
625 RB_AUGMENT(parent); \
626 } else \
627 RB_ROOT(head) = child; \
628 color: \
629 if (color == RB_BLACK) \
630 name##_RB_REMOVE_COLOR(head, parent, child); \
631 return (old); \
632 }
633
634#define RB_GENERATE_INSERT(name, type, field, cmp, attr) \
635 /* Inserts a node into the RB tree */ \
636 attr struct type* name##_RB_INSERT(struct name* head, struct type* elm) { \
637 struct type* tmp; \
638 struct type* parent = NULL; \
639 int comp = 0; \
640 tmp = RB_ROOT(head); \
641 while (tmp) { \
642 parent = tmp; \
643 comp = (cmp)(elm, parent); \
644 if (comp < 0) \
645 tmp = RB_LEFT(tmp, field); \
646 else if (comp > 0) \
647 tmp = RB_RIGHT(tmp, field); \
648 else \
649 return (tmp); \
650 } \
651 RB_SET(elm, parent, field); \
652 if (parent != NULL) { \
653 if (comp < 0) \
654 RB_LEFT(parent, field) = elm; \
655 else \
656 RB_RIGHT(parent, field) = elm; \
657 RB_AUGMENT(parent); \
658 } else \
659 RB_ROOT(head) = elm; \
660 name##_RB_INSERT_COLOR(head, elm); \
661 return (NULL); \
662 }
663
664#define RB_GENERATE_FIND(name, type, field, cmp, attr) \
665 /* Finds the node with the same key as elm */ \
666 attr struct type* name##_RB_FIND(struct name* head, struct type* elm) { \
667 struct type* tmp = RB_ROOT(head); \
668 int comp; \
669 while (tmp) { \
670 comp = cmp(elm, tmp); \
671 if (comp < 0) \
672 tmp = RB_LEFT(tmp, field); \
673 else if (comp > 0) \
674 tmp = RB_RIGHT(tmp, field); \
675 else \
676 return (tmp); \
677 } \
678 return (NULL); \
679 }
680
681#define RB_GENERATE_NFIND(name, type, field, cmp, attr) \
682 /* Finds the first node greater than or equal to the search key */ \
683 attr struct type* name##_RB_NFIND(struct name* head, struct type* elm) { \
684 struct type* tmp = RB_ROOT(head); \
685 struct type* res = NULL; \
686 int comp; \
687 while (tmp) { \
688 comp = cmp(elm, tmp); \
689 if (comp < 0) { \
690 res = tmp; \
691 tmp = RB_LEFT(tmp, field); \
692 } else if (comp > 0) \
693 tmp = RB_RIGHT(tmp, field); \
694 else \
695 return (tmp); \
696 } \
697 return (res); \
698 }
699
700#define RB_GENERATE_FIND_LIGHT(name, type, field, lcmp, attr) \
701 /* Finds the node with the same key as elm */ \
702 attr struct type* name##_RB_FIND_LIGHT(struct name* head, const void* lelm) { \
703 struct type* tmp = RB_ROOT(head); \
704 int comp; \
705 while (tmp) { \
706 comp = lcmp(lelm, tmp); \
707 if (comp < 0) \
708 tmp = RB_LEFT(tmp, field); \
709 else if (comp > 0) \
710 tmp = RB_RIGHT(tmp, field); \
711 else \
712 return (tmp); \
713 } \
714 return (NULL); \
715 }
716
717#define RB_GENERATE_NFIND_LIGHT(name, type, field, lcmp, attr) \
718 /* Finds the first node greater than or equal to the search key */ \
719 attr struct type* name##_RB_NFIND_LIGHT(struct name* head, const void* lelm) { \
720 struct type* tmp = RB_ROOT(head); \
721 struct type* res = NULL; \
722 int comp; \
723 while (tmp) { \
724 comp = lcmp(lelm, tmp); \
725 if (comp < 0) { \
726 res = tmp; \
727 tmp = RB_LEFT(tmp, field); \
728 } else if (comp > 0) \
729 tmp = RB_RIGHT(tmp, field); \
730 else \
731 return (tmp); \
732 } \
733 return (res); \
734 }
735
736#define RB_GENERATE_NEXT(name, type, field, attr) \
737 /* ARGSUSED */ \
738 attr struct type* name##_RB_NEXT(struct type* elm) { \
739 if (RB_RIGHT(elm, field)) { \
740 elm = RB_RIGHT(elm, field); \
741 while (RB_LEFT(elm, field)) \
742 elm = RB_LEFT(elm, field); \
743 } else { \
744 if (RB_PARENT(elm, field) && (elm == RB_LEFT(RB_PARENT(elm, field), field))) \
745 elm = RB_PARENT(elm, field); \
746 else { \
747 while (RB_PARENT(elm, field) && (elm == RB_RIGHT(RB_PARENT(elm, field), field))) \
748 elm = RB_PARENT(elm, field); \
749 elm = RB_PARENT(elm, field); \
750 } \
751 } \
752 return (elm); \
753 }
754
755#define RB_GENERATE_PREV(name, type, field, attr) \
756 /* ARGSUSED */ \
757 attr struct type* name##_RB_PREV(struct type* elm) { \
758 if (RB_LEFT(elm, field)) { \
759 elm = RB_LEFT(elm, field); \
760 while (RB_RIGHT(elm, field)) \
761 elm = RB_RIGHT(elm, field); \
762 } else { \
763 if (RB_PARENT(elm, field) && (elm == RB_RIGHT(RB_PARENT(elm, field), field))) \
764 elm = RB_PARENT(elm, field); \
765 else { \
766 while (RB_PARENT(elm, field) && (elm == RB_LEFT(RB_PARENT(elm, field), field))) \
767 elm = RB_PARENT(elm, field); \
768 elm = RB_PARENT(elm, field); \
769 } \
770 } \
771 return (elm); \
772 }
773
774#define RB_GENERATE_MINMAX(name, type, field, attr) \
775 attr struct type* name##_RB_MINMAX(struct name* head, int val) { \
776 struct type* tmp = RB_ROOT(head); \
777 struct type* parent = NULL; \
778 while (tmp) { \
779 parent = tmp; \
780 if (val < 0) \
781 tmp = RB_LEFT(tmp, field); \
782 else \
783 tmp = RB_RIGHT(tmp, field); \
784 } \
785 return (parent); \
786 }
787
788#define RB_NEGINF -1
789#define RB_INF 1
790
791#define RB_INSERT(name, x, y) name##_RB_INSERT(x, y)
792#define RB_REMOVE(name, x, y) name##_RB_REMOVE(x, y)
793#define RB_FIND(name, x, y) name##_RB_FIND(x, y)
794#define RB_NFIND(name, x, y) name##_RB_NFIND(x, y)
795#define RB_FIND_LIGHT(name, x, y) name##_RB_FIND_LIGHT(x, y)
796#define RB_NFIND_LIGHT(name, x, y) name##_RB_NFIND_LIGHT(x, y)
797#define RB_NEXT(name, x, y) name##_RB_NEXT(y)
798#define RB_PREV(name, x, y) name##_RB_PREV(y)
799#define RB_MIN(name, x) name##_RB_MINMAX(x, RB_NEGINF)
800#define RB_MAX(name, x) name##_RB_MINMAX(x, RB_INF)
801
802#define RB_FOREACH(x, name, head) \
803 for ((x) = RB_MIN(name, head); (x) != NULL; (x) = name##_RB_NEXT(x))
804
805#define RB_FOREACH_FROM(x, name, y) \
806 for ((x) = (y); ((x) != NULL) && ((y) = name##_RB_NEXT(x), (x) != NULL); (x) = (y))
807
808#define RB_FOREACH_SAFE(x, name, head, y) \
809 for ((x) = RB_MIN(name, head); ((x) != NULL) && ((y) = name##_RB_NEXT(x), (x) != NULL); \
810 (x) = (y))
811
812#define RB_FOREACH_REVERSE(x, name, head) \
813 for ((x) = RB_MAX(name, head); (x) != NULL; (x) = name##_RB_PREV(x))
814
815#define RB_FOREACH_REVERSE_FROM(x, name, y) \
816 for ((x) = (y); ((x) != NULL) && ((y) = name##_RB_PREV(x), (x) != NULL); (x) = (y))
817
818#define RB_FOREACH_REVERSE_SAFE(x, name, head, y) \
819 for ((x) = RB_MAX(name, head); ((x) != NULL) && ((y) = name##_RB_PREV(x), (x) != NULL); \
820 (x) = (y))
821
822#endif /* _SYS_TREE_H_ */
HIC SVNT DRACONES