"Fossies" - the Fresh Open Source Software Archive 
Member "xombrero-1.6.4/linux/tree.h" (17 Feb 2015, 25140 Bytes) of package /linux/www/old/xombrero-1.6.4.tgz:
As a special service "Fossies" has tried to format the requested source page into HTML format using (guessed) C and C++ source code syntax highlighting (style:
standard) with prefixed line numbers and
code folding option.
Alternatively you can here
view or
download the uninterpreted source code file.
For more information about "tree.h" see the
Fossies "Dox" file reference documentation.
1 /* $OpenBSD: tree.h,v 1.13 2011/07/09 00:19:45 pirofti Exp $ */
2 /*
3 * Copyright 2002 Niels Provos <provos@citi.umich.edu>
4 * All rights reserved.
5 *
6 * Redistribution and use in source and binary forms, with or without
7 * modification, are permitted provided that the following conditions
8 * are met:
9 * 1. Redistributions of source code must retain the above copyright
10 * notice, this list of conditions and the following disclaimer.
11 * 2. Redistributions in binary form must reproduce the above copyright
12 * notice, this list of conditions and the following disclaimer in the
13 * documentation and/or other materials provided with the distribution.
14 *
15 * THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR
16 * IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES
17 * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED.
18 * IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT,
19 * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT
20 * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
21 * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
22 * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
23 * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF
24 * THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
25 */
26
27 #ifndef _SYS_TREE_H_
28 #define _SYS_TREE_H_
29
30 /*
31 * This file defines data structures for different types of trees:
32 * splay trees and red-black trees.
33 *
34 * A splay tree is a self-organizing data structure. Every operation
35 * on the tree causes a splay to happen. The splay moves the requested
36 * node to the root of the tree and partly rebalances it.
37 *
38 * This has the benefit that request locality causes faster lookups as
39 * the requested nodes move to the top of the tree. On the other hand,
40 * every lookup causes memory writes.
41 *
42 * The Balance Theorem bounds the total access time for m operations
43 * and n inserts on an initially empty tree as O((m + n)lg n). The
44 * amortized cost for a sequence of m accesses to a splay tree is O(lg n);
45 *
46 * A red-black tree is a binary search tree with the node color as an
47 * extra attribute. It fulfills a set of conditions:
48 * - every search path from the root to a leaf consists of the
49 * same number of black nodes,
50 * - each red node (except for the root) has a black parent,
51 * - each leaf node is black.
52 *
53 * Every operation on a red-black tree is bounded as O(lg n).
54 * The maximum height of a red-black tree is 2lg (n+1).
55 */
56
57 #define SPLAY_HEAD(name, type) \
58 struct name { \
59 struct type *sph_root; /* root of the tree */ \
60 }
61
62 #define SPLAY_INITIALIZER(root) \
63 { NULL }
64
65 #define SPLAY_INIT(root) do { \
66 (root)->sph_root = NULL; \
67 } while (0)
68
69 #define SPLAY_ENTRY(type) \
70 struct { \
71 struct type *spe_left; /* left element */ \
72 struct type *spe_right; /* right element */ \
73 }
74
75 #define SPLAY_LEFT(elm, field) (elm)->field.spe_left
76 #define SPLAY_RIGHT(elm, field) (elm)->field.spe_right
77 #define SPLAY_ROOT(head) (head)->sph_root
78 #define SPLAY_EMPTY(head) (SPLAY_ROOT(head) == NULL)
79
80 /* SPLAY_ROTATE_{LEFT,RIGHT} expect that tmp hold SPLAY_{RIGHT,LEFT} */
81 #define SPLAY_ROTATE_RIGHT(head, tmp, field) do { \
82 SPLAY_LEFT((head)->sph_root, field) = SPLAY_RIGHT(tmp, field); \
83 SPLAY_RIGHT(tmp, field) = (head)->sph_root; \
84 (head)->sph_root = tmp; \
85 } while (0)
86
87 #define SPLAY_ROTATE_LEFT(head, tmp, field) do { \
88 SPLAY_RIGHT((head)->sph_root, field) = SPLAY_LEFT(tmp, field); \
89 SPLAY_LEFT(tmp, field) = (head)->sph_root; \
90 (head)->sph_root = tmp; \
91 } while (0)
92
93 #define SPLAY_LINKLEFT(head, tmp, field) do { \
94 SPLAY_LEFT(tmp, field) = (head)->sph_root; \
95 tmp = (head)->sph_root; \
96 (head)->sph_root = SPLAY_LEFT((head)->sph_root, field); \
97 } while (0)
98
99 #define SPLAY_LINKRIGHT(head, tmp, field) do { \
100 SPLAY_RIGHT(tmp, field) = (head)->sph_root; \
101 tmp = (head)->sph_root; \
102 (head)->sph_root = SPLAY_RIGHT((head)->sph_root, field); \
103 } while (0)
104
105 #define SPLAY_ASSEMBLE(head, node, left, right, field) do { \
106 SPLAY_RIGHT(left, field) = SPLAY_LEFT((head)->sph_root, field); \
107 SPLAY_LEFT(right, field) = SPLAY_RIGHT((head)->sph_root, field);\
108 SPLAY_LEFT((head)->sph_root, field) = SPLAY_RIGHT(node, field); \
109 SPLAY_RIGHT((head)->sph_root, field) = SPLAY_LEFT(node, field); \
110 } while (0)
111
112 /* Generates prototypes and inline functions */
113
114 #define SPLAY_PROTOTYPE(name, type, field, cmp) \
115 void name##_SPLAY(struct name *, struct type *); \
116 void name##_SPLAY_MINMAX(struct name *, int); \
117 struct type *name##_SPLAY_INSERT(struct name *, struct type *); \
118 struct type *name##_SPLAY_REMOVE(struct name *, struct type *); \
119 \
120 /* Finds the node with the same key as elm */ \
121 static __inline struct type * \
122 name##_SPLAY_FIND(struct name *head, struct type *elm) \
123 { \
124 if (SPLAY_EMPTY(head)) \
125 return(NULL); \
126 name##_SPLAY(head, elm); \
127 if ((cmp)(elm, (head)->sph_root) == 0) \
128 return (head->sph_root); \
129 return (NULL); \
130 } \
131 \
132 static __inline struct type * \
133 name##_SPLAY_NEXT(struct name *head, struct type *elm) \
134 { \
135 name##_SPLAY(head, elm); \
136 if (SPLAY_RIGHT(elm, field) != NULL) { \
137 elm = SPLAY_RIGHT(elm, field); \
138 while (SPLAY_LEFT(elm, field) != NULL) { \
139 elm = SPLAY_LEFT(elm, field); \
140 } \
141 } else \
142 elm = NULL; \
143 return (elm); \
144 } \
145 \
146 static __inline struct type * \
147 name##_SPLAY_MIN_MAX(struct name *head, int val) \
148 { \
149 name##_SPLAY_MINMAX(head, val); \
150 return (SPLAY_ROOT(head)); \
151 }
152
153 /* Main splay operation.
154 * Moves node close to the key of elm to top
155 */
156 #define SPLAY_GENERATE(name, type, field, cmp) \
157 struct type * \
158 name##_SPLAY_INSERT(struct name *head, struct type *elm) \
159 { \
160 if (SPLAY_EMPTY(head)) { \
161 SPLAY_LEFT(elm, field) = SPLAY_RIGHT(elm, field) = NULL; \
162 } else { \
163 int __comp; \
164 name##_SPLAY(head, elm); \
165 __comp = (cmp)(elm, (head)->sph_root); \
166 if(__comp < 0) { \
167 SPLAY_LEFT(elm, field) = SPLAY_LEFT((head)->sph_root, field);\
168 SPLAY_RIGHT(elm, field) = (head)->sph_root; \
169 SPLAY_LEFT((head)->sph_root, field) = NULL; \
170 } else if (__comp > 0) { \
171 SPLAY_RIGHT(elm, field) = SPLAY_RIGHT((head)->sph_root, field);\
172 SPLAY_LEFT(elm, field) = (head)->sph_root; \
173 SPLAY_RIGHT((head)->sph_root, field) = NULL; \
174 } else \
175 return ((head)->sph_root); \
176 } \
177 (head)->sph_root = (elm); \
178 return (NULL); \
179 } \
180 \
181 struct type * \
182 name##_SPLAY_REMOVE(struct name *head, struct type *elm) \
183 { \
184 struct type *__tmp; \
185 if (SPLAY_EMPTY(head)) \
186 return (NULL); \
187 name##_SPLAY(head, elm); \
188 if ((cmp)(elm, (head)->sph_root) == 0) { \
189 if (SPLAY_LEFT((head)->sph_root, field) == NULL) { \
190 (head)->sph_root = SPLAY_RIGHT((head)->sph_root, field);\
191 } else { \
192 __tmp = SPLAY_RIGHT((head)->sph_root, field); \
193 (head)->sph_root = SPLAY_LEFT((head)->sph_root, field);\
194 name##_SPLAY(head, elm); \
195 SPLAY_RIGHT((head)->sph_root, field) = __tmp; \
196 } \
197 return (elm); \
198 } \
199 return (NULL); \
200 } \
201 \
202 void \
203 name##_SPLAY(struct name *head, struct type *elm) \
204 { \
205 struct type __node, *__left, *__right, *__tmp; \
206 int __comp; \
207 \
208 SPLAY_LEFT(&__node, field) = SPLAY_RIGHT(&__node, field) = NULL;\
209 __left = __right = &__node; \
210 \
211 while ((__comp = (cmp)(elm, (head)->sph_root))) { \
212 if (__comp < 0) { \
213 __tmp = SPLAY_LEFT((head)->sph_root, field); \
214 if (__tmp == NULL) \
215 break; \
216 if ((cmp)(elm, __tmp) < 0){ \
217 SPLAY_ROTATE_RIGHT(head, __tmp, field); \
218 if (SPLAY_LEFT((head)->sph_root, field) == NULL)\
219 break; \
220 } \
221 SPLAY_LINKLEFT(head, __right, field); \
222 } else if (__comp > 0) { \
223 __tmp = SPLAY_RIGHT((head)->sph_root, field); \
224 if (__tmp == NULL) \
225 break; \
226 if ((cmp)(elm, __tmp) > 0){ \
227 SPLAY_ROTATE_LEFT(head, __tmp, field); \
228 if (SPLAY_RIGHT((head)->sph_root, field) == NULL)\
229 break; \
230 } \
231 SPLAY_LINKRIGHT(head, __left, field); \
232 } \
233 } \
234 SPLAY_ASSEMBLE(head, &__node, __left, __right, field); \
235 } \
236 \
237 /* Splay with either the minimum or the maximum element \
238 * Used to find minimum or maximum element in tree. \
239 */ \
240 void name##_SPLAY_MINMAX(struct name *head, int __comp) \
241 { \
242 struct type __node, *__left, *__right, *__tmp; \
243 \
244 SPLAY_LEFT(&__node, field) = SPLAY_RIGHT(&__node, field) = NULL;\
245 __left = __right = &__node; \
246 \
247 while (1) { \
248 if (__comp < 0) { \
249 __tmp = SPLAY_LEFT((head)->sph_root, field); \
250 if (__tmp == NULL) \
251 break; \
252 if (__comp < 0){ \
253 SPLAY_ROTATE_RIGHT(head, __tmp, field); \
254 if (SPLAY_LEFT((head)->sph_root, field) == NULL)\
255 break; \
256 } \
257 SPLAY_LINKLEFT(head, __right, field); \
258 } else if (__comp > 0) { \
259 __tmp = SPLAY_RIGHT((head)->sph_root, field); \
260 if (__tmp == NULL) \
261 break; \
262 if (__comp > 0) { \
263 SPLAY_ROTATE_LEFT(head, __tmp, field); \
264 if (SPLAY_RIGHT((head)->sph_root, field) == NULL)\
265 break; \
266 } \
267 SPLAY_LINKRIGHT(head, __left, field); \
268 } \
269 } \
270 SPLAY_ASSEMBLE(head, &__node, __left, __right, field); \
271 }
272
273 #define SPLAY_NEGINF -1
274 #define SPLAY_INF 1
275
276 #define SPLAY_INSERT(name, x, y) name##_SPLAY_INSERT(x, y)
277 #define SPLAY_REMOVE(name, x, y) name##_SPLAY_REMOVE(x, y)
278 #define SPLAY_FIND(name, x, y) name##_SPLAY_FIND(x, y)
279 #define SPLAY_NEXT(name, x, y) name##_SPLAY_NEXT(x, y)
280 #define SPLAY_MIN(name, x) (SPLAY_EMPTY(x) ? NULL \
281 : name##_SPLAY_MIN_MAX(x, SPLAY_NEGINF))
282 #define SPLAY_MAX(name, x) (SPLAY_EMPTY(x) ? NULL \
283 : name##_SPLAY_MIN_MAX(x, SPLAY_INF))
284
285 #define SPLAY_FOREACH(x, name, head) \
286 for ((x) = SPLAY_MIN(name, head); \
287 (x) != NULL; \
288 (x) = SPLAY_NEXT(name, head, x))
289
290 /* Macros that define a red-black tree */
291 #define RB_HEAD(name, type) \
292 struct name { \
293 struct type *rbh_root; /* root of the tree */ \
294 }
295
296 #define RB_INITIALIZER(root) \
297 { NULL }
298
299 #define RB_INIT(root) do { \
300 (root)->rbh_root = NULL; \
301 } while (0)
302
303 #define RB_BLACK 0
304 #define RB_RED 1
305 #define RB_ENTRY(type) \
306 struct { \
307 struct type *rbe_left; /* left element */ \
308 struct type *rbe_right; /* right element */ \
309 struct type *rbe_parent; /* parent element */ \
310 int rbe_color; /* node color */ \
311 }
312
313 #define RB_LEFT(elm, field) (elm)->field.rbe_left
314 #define RB_RIGHT(elm, field) (elm)->field.rbe_right
315 #define RB_PARENT(elm, field) (elm)->field.rbe_parent
316 #define RB_COLOR(elm, field) (elm)->field.rbe_color
317 #define RB_ROOT(head) (head)->rbh_root
318 #define RB_EMPTY(head) (RB_ROOT(head) == NULL)
319
320 #define RB_SET(elm, parent, field) do { \
321 RB_PARENT(elm, field) = parent; \
322 RB_LEFT(elm, field) = RB_RIGHT(elm, field) = NULL; \
323 RB_COLOR(elm, field) = RB_RED; \
324 } while (0)
325
326 #define RB_SET_BLACKRED(black, red, field) do { \
327 RB_COLOR(black, field) = RB_BLACK; \
328 RB_COLOR(red, field) = RB_RED; \
329 } while (0)
330
331 #ifndef RB_AUGMENT
332 #define RB_AUGMENT(x) do {} while (0)
333 #endif
334
335 #define RB_ROTATE_LEFT(head, elm, tmp, field) do { \
336 (tmp) = RB_RIGHT(elm, field); \
337 if ((RB_RIGHT(elm, field) = RB_LEFT(tmp, field))) { \
338 RB_PARENT(RB_LEFT(tmp, field), field) = (elm); \
339 } \
340 RB_AUGMENT(elm); \
341 if ((RB_PARENT(tmp, field) = RB_PARENT(elm, field))) { \
342 if ((elm) == RB_LEFT(RB_PARENT(elm, field), field)) \
343 RB_LEFT(RB_PARENT(elm, field), field) = (tmp); \
344 else \
345 RB_RIGHT(RB_PARENT(elm, field), field) = (tmp); \
346 } else \
347 (head)->rbh_root = (tmp); \
348 RB_LEFT(tmp, field) = (elm); \
349 RB_PARENT(elm, field) = (tmp); \
350 RB_AUGMENT(tmp); \
351 if ((RB_PARENT(tmp, field))) \
352 RB_AUGMENT(RB_PARENT(tmp, field)); \
353 } while (0)
354
355 #define RB_ROTATE_RIGHT(head, elm, tmp, field) do { \
356 (tmp) = RB_LEFT(elm, field); \
357 if ((RB_LEFT(elm, field) = RB_RIGHT(tmp, field))) { \
358 RB_PARENT(RB_RIGHT(tmp, field), field) = (elm); \
359 } \
360 RB_AUGMENT(elm); \
361 if ((RB_PARENT(tmp, field) = RB_PARENT(elm, field))) { \
362 if ((elm) == RB_LEFT(RB_PARENT(elm, field), field)) \
363 RB_LEFT(RB_PARENT(elm, field), field) = (tmp); \
364 else \
365 RB_RIGHT(RB_PARENT(elm, field), field) = (tmp); \
366 } else \
367 (head)->rbh_root = (tmp); \
368 RB_RIGHT(tmp, field) = (elm); \
369 RB_PARENT(elm, field) = (tmp); \
370 RB_AUGMENT(tmp); \
371 if ((RB_PARENT(tmp, field))) \
372 RB_AUGMENT(RB_PARENT(tmp, field)); \
373 } while (0)
374
375 /* Generates prototypes and inline functions */
376 #define RB_PROTOTYPE(name, type, field, cmp) \
377 RB_PROTOTYPE_INTERNAL(name, type, field, cmp,)
378 #define RB_PROTOTYPE_STATIC(name, type, field, cmp) \
379 RB_PROTOTYPE_INTERNAL(name, type, field, cmp, __attribute__((__unused__)) static)
380 #define RB_PROTOTYPE_INTERNAL(name, type, field, cmp, attr) \
381 attr void name##_RB_INSERT_COLOR(struct name *, struct type *); \
382 attr void name##_RB_REMOVE_COLOR(struct name *, struct type *, struct type *);\
383 attr struct type *name##_RB_REMOVE(struct name *, struct type *); \
384 attr struct type *name##_RB_INSERT(struct name *, struct type *); \
385 attr struct type *name##_RB_FIND(struct name *, struct type *); \
386 attr struct type *name##_RB_NFIND(struct name *, struct type *); \
387 attr struct type *name##_RB_NEXT(struct type *); \
388 attr struct type *name##_RB_PREV(struct type *); \
389 attr struct type *name##_RB_MINMAX(struct name *, int); \
390 \
391
392 /* Main rb operation.
393 * Moves node close to the key of elm to top
394 */
395 #define RB_GENERATE(name, type, field, cmp) \
396 RB_GENERATE_INTERNAL(name, type, field, cmp,)
397 #define RB_GENERATE_STATIC(name, type, field, cmp) \
398 RB_GENERATE_INTERNAL(name, type, field, cmp, __attribute__((__unused__)) static)
399 #define RB_GENERATE_INTERNAL(name, type, field, cmp, attr) \
400 attr void \
401 name##_RB_INSERT_COLOR(struct name *head, struct type *elm) \
402 { \
403 struct type *parent, *gparent, *tmp; \
404 while ((parent = RB_PARENT(elm, field)) && \
405 RB_COLOR(parent, field) == RB_RED) { \
406 gparent = RB_PARENT(parent, field); \
407 if (parent == RB_LEFT(gparent, field)) { \
408 tmp = RB_RIGHT(gparent, field); \
409 if (tmp && RB_COLOR(tmp, field) == RB_RED) { \
410 RB_COLOR(tmp, field) = RB_BLACK; \
411 RB_SET_BLACKRED(parent, gparent, field);\
412 elm = gparent; \
413 continue; \
414 } \
415 if (RB_RIGHT(parent, field) == elm) { \
416 RB_ROTATE_LEFT(head, parent, tmp, field);\
417 tmp = parent; \
418 parent = elm; \
419 elm = tmp; \
420 } \
421 RB_SET_BLACKRED(parent, gparent, field); \
422 RB_ROTATE_RIGHT(head, gparent, tmp, field); \
423 } else { \
424 tmp = RB_LEFT(gparent, field); \
425 if (tmp && RB_COLOR(tmp, field) == RB_RED) { \
426 RB_COLOR(tmp, field) = RB_BLACK; \
427 RB_SET_BLACKRED(parent, gparent, field);\
428 elm = gparent; \
429 continue; \
430 } \
431 if (RB_LEFT(parent, field) == elm) { \
432 RB_ROTATE_RIGHT(head, parent, tmp, field);\
433 tmp = parent; \
434 parent = elm; \
435 elm = tmp; \
436 } \
437 RB_SET_BLACKRED(parent, gparent, field); \
438 RB_ROTATE_LEFT(head, gparent, tmp, field); \
439 } \
440 } \
441 RB_COLOR(head->rbh_root, field) = RB_BLACK; \
442 } \
443 \
444 attr void \
445 name##_RB_REMOVE_COLOR(struct name *head, struct type *parent, struct type *elm) \
446 { \
447 struct type *tmp; \
448 while ((elm == NULL || RB_COLOR(elm, field) == RB_BLACK) && \
449 elm != RB_ROOT(head)) { \
450 if (RB_LEFT(parent, field) == elm) { \
451 tmp = RB_RIGHT(parent, field); \
452 if (RB_COLOR(tmp, field) == RB_RED) { \
453 RB_SET_BLACKRED(tmp, parent, field); \
454 RB_ROTATE_LEFT(head, parent, tmp, field);\
455 tmp = RB_RIGHT(parent, field); \
456 } \
457 if ((RB_LEFT(tmp, field) == NULL || \
458 RB_COLOR(RB_LEFT(tmp, field), field) == RB_BLACK) &&\
459 (RB_RIGHT(tmp, field) == NULL || \
460 RB_COLOR(RB_RIGHT(tmp, field), field) == RB_BLACK)) {\
461 RB_COLOR(tmp, field) = RB_RED; \
462 elm = parent; \
463 parent = RB_PARENT(elm, field); \
464 } else { \
465 if (RB_RIGHT(tmp, field) == NULL || \
466 RB_COLOR(RB_RIGHT(tmp, field), field) == RB_BLACK) {\
467 struct type *oleft; \
468 if ((oleft = RB_LEFT(tmp, field)))\
469 RB_COLOR(oleft, field) = RB_BLACK;\
470 RB_COLOR(tmp, field) = RB_RED; \
471 RB_ROTATE_RIGHT(head, tmp, oleft, field);\
472 tmp = RB_RIGHT(parent, field); \
473 } \
474 RB_COLOR(tmp, field) = RB_COLOR(parent, field);\
475 RB_COLOR(parent, field) = RB_BLACK; \
476 if (RB_RIGHT(tmp, field)) \
477 RB_COLOR(RB_RIGHT(tmp, field), field) = RB_BLACK;\
478 RB_ROTATE_LEFT(head, parent, tmp, field);\
479 elm = RB_ROOT(head); \
480 break; \
481 } \
482 } else { \
483 tmp = RB_LEFT(parent, field); \
484 if (RB_COLOR(tmp, field) == RB_RED) { \
485 RB_SET_BLACKRED(tmp, parent, field); \
486 RB_ROTATE_RIGHT(head, parent, tmp, field);\
487 tmp = RB_LEFT(parent, field); \
488 } \
489 if ((RB_LEFT(tmp, field) == NULL || \
490 RB_COLOR(RB_LEFT(tmp, field), field) == RB_BLACK) &&\
491 (RB_RIGHT(tmp, field) == NULL || \
492 RB_COLOR(RB_RIGHT(tmp, field), field) == RB_BLACK)) {\
493 RB_COLOR(tmp, field) = RB_RED; \
494 elm = parent; \
495 parent = RB_PARENT(elm, field); \
496 } else { \
497 if (RB_LEFT(tmp, field) == NULL || \
498 RB_COLOR(RB_LEFT(tmp, field), field) == RB_BLACK) {\
499 struct type *oright; \
500 if ((oright = RB_RIGHT(tmp, field)))\
501 RB_COLOR(oright, field) = RB_BLACK;\
502 RB_COLOR(tmp, field) = RB_RED; \
503 RB_ROTATE_LEFT(head, tmp, oright, field);\
504 tmp = RB_LEFT(parent, field); \
505 } \
506 RB_COLOR(tmp, field) = RB_COLOR(parent, field);\
507 RB_COLOR(parent, field) = RB_BLACK; \
508 if (RB_LEFT(tmp, field)) \
509 RB_COLOR(RB_LEFT(tmp, field), field) = RB_BLACK;\
510 RB_ROTATE_RIGHT(head, parent, tmp, field);\
511 elm = RB_ROOT(head); \
512 break; \
513 } \
514 } \
515 } \
516 if (elm) \
517 RB_COLOR(elm, field) = RB_BLACK; \
518 } \
519 \
520 attr struct type * \
521 name##_RB_REMOVE(struct name *head, struct type *elm) \
522 { \
523 struct type *child, *parent, *old = elm; \
524 int color; \
525 if (RB_LEFT(elm, field) == NULL) \
526 child = RB_RIGHT(elm, field); \
527 else if (RB_RIGHT(elm, field) == NULL) \
528 child = RB_LEFT(elm, field); \
529 else { \
530 struct type *left; \
531 elm = RB_RIGHT(elm, field); \
532 while ((left = RB_LEFT(elm, field))) \
533 elm = left; \
534 child = RB_RIGHT(elm, field); \
535 parent = RB_PARENT(elm, field); \
536 color = RB_COLOR(elm, field); \
537 if (child) \
538 RB_PARENT(child, field) = parent; \
539 if (parent) { \
540 if (RB_LEFT(parent, field) == elm) \
541 RB_LEFT(parent, field) = child; \
542 else \
543 RB_RIGHT(parent, field) = child; \
544 RB_AUGMENT(parent); \
545 } else \
546 RB_ROOT(head) = child; \
547 if (RB_PARENT(elm, field) == old) \
548 parent = elm; \
549 (elm)->field = (old)->field; \
550 if (RB_PARENT(old, field)) { \
551 if (RB_LEFT(RB_PARENT(old, field), field) == old)\
552 RB_LEFT(RB_PARENT(old, field), field) = elm;\
553 else \
554 RB_RIGHT(RB_PARENT(old, field), field) = elm;\
555 RB_AUGMENT(RB_PARENT(old, field)); \
556 } else \
557 RB_ROOT(head) = elm; \
558 RB_PARENT(RB_LEFT(old, field), field) = elm; \
559 if (RB_RIGHT(old, field)) \
560 RB_PARENT(RB_RIGHT(old, field), field) = elm; \
561 if (parent) { \
562 left = parent; \
563 do { \
564 RB_AUGMENT(left); \
565 } while ((left = RB_PARENT(left, field))); \
566 } \
567 goto color; \
568 } \
569 parent = RB_PARENT(elm, field); \
570 color = RB_COLOR(elm, field); \
571 if (child) \
572 RB_PARENT(child, field) = parent; \
573 if (parent) { \
574 if (RB_LEFT(parent, field) == elm) \
575 RB_LEFT(parent, field) = child; \
576 else \
577 RB_RIGHT(parent, field) = child; \
578 RB_AUGMENT(parent); \
579 } else \
580 RB_ROOT(head) = child; \
581 color: \
582 if (color == RB_BLACK) \
583 name##_RB_REMOVE_COLOR(head, parent, child); \
584 return (old); \
585 } \
586 \
587 /* Inserts a node into the RB tree */ \
588 attr struct type * \
589 name##_RB_INSERT(struct name *head, struct type *elm) \
590 { \
591 struct type *tmp; \
592 struct type *parent = NULL; \
593 int comp = 0; \
594 tmp = RB_ROOT(head); \
595 while (tmp) { \
596 parent = tmp; \
597 comp = (cmp)(elm, parent); \
598 if (comp < 0) \
599 tmp = RB_LEFT(tmp, field); \
600 else if (comp > 0) \
601 tmp = RB_RIGHT(tmp, field); \
602 else \
603 return (tmp); \
604 } \
605 RB_SET(elm, parent, field); \
606 if (parent != NULL) { \
607 if (comp < 0) \
608 RB_LEFT(parent, field) = elm; \
609 else \
610 RB_RIGHT(parent, field) = elm; \
611 RB_AUGMENT(parent); \
612 } else \
613 RB_ROOT(head) = elm; \
614 name##_RB_INSERT_COLOR(head, elm); \
615 return (NULL); \
616 } \
617 \
618 /* Finds the node with the same key as elm */ \
619 attr struct type * \
620 name##_RB_FIND(struct name *head, struct type *elm) \
621 { \
622 struct type *tmp = RB_ROOT(head); \
623 int comp; \
624 while (tmp) { \
625 comp = cmp(elm, tmp); \
626 if (comp < 0) \
627 tmp = RB_LEFT(tmp, field); \
628 else if (comp > 0) \
629 tmp = RB_RIGHT(tmp, field); \
630 else \
631 return (tmp); \
632 } \
633 return (NULL); \
634 } \
635 \
636 /* Finds the first node greater than or equal to the search key */ \
637 attr struct type * \
638 name##_RB_NFIND(struct name *head, struct type *elm) \
639 { \
640 struct type *tmp = RB_ROOT(head); \
641 struct type *res = NULL; \
642 int comp; \
643 while (tmp) { \
644 comp = cmp(elm, tmp); \
645 if (comp < 0) { \
646 res = tmp; \
647 tmp = RB_LEFT(tmp, field); \
648 } \
649 else if (comp > 0) \
650 tmp = RB_RIGHT(tmp, field); \
651 else \
652 return (tmp); \
653 } \
654 return (res); \
655 } \
656 \
657 /* ARGSUSED */ \
658 attr struct type * \
659 name##_RB_NEXT(struct type *elm) \
660 { \
661 if (RB_RIGHT(elm, field)) { \
662 elm = RB_RIGHT(elm, field); \
663 while (RB_LEFT(elm, field)) \
664 elm = RB_LEFT(elm, field); \
665 } else { \
666 if (RB_PARENT(elm, field) && \
667 (elm == RB_LEFT(RB_PARENT(elm, field), field))) \
668 elm = RB_PARENT(elm, field); \
669 else { \
670 while (RB_PARENT(elm, field) && \
671 (elm == RB_RIGHT(RB_PARENT(elm, field), field)))\
672 elm = RB_PARENT(elm, field); \
673 elm = RB_PARENT(elm, field); \
674 } \
675 } \
676 return (elm); \
677 } \
678 \
679 /* ARGSUSED */ \
680 attr struct type * \
681 name##_RB_PREV(struct type *elm) \
682 { \
683 if (RB_LEFT(elm, field)) { \
684 elm = RB_LEFT(elm, field); \
685 while (RB_RIGHT(elm, field)) \
686 elm = RB_RIGHT(elm, field); \
687 } else { \
688 if (RB_PARENT(elm, field) && \
689 (elm == RB_RIGHT(RB_PARENT(elm, field), field))) \
690 elm = RB_PARENT(elm, field); \
691 else { \
692 while (RB_PARENT(elm, field) && \
693 (elm == RB_LEFT(RB_PARENT(elm, field), field)))\
694 elm = RB_PARENT(elm, field); \
695 elm = RB_PARENT(elm, field); \
696 } \
697 } \
698 return (elm); \
699 } \
700 \
701 attr struct type * \
702 name##_RB_MINMAX(struct name *head, int val) \
703 { \
704 struct type *tmp = RB_ROOT(head); \
705 struct type *parent = NULL; \
706 while (tmp) { \
707 parent = tmp; \
708 if (val < 0) \
709 tmp = RB_LEFT(tmp, field); \
710 else \
711 tmp = RB_RIGHT(tmp, field); \
712 } \
713 return (parent); \
714 }
715
716 #define RB_NEGINF -1
717 #define RB_INF 1
718
719 #define RB_INSERT(name, x, y) name##_RB_INSERT(x, y)
720 #define RB_REMOVE(name, x, y) name##_RB_REMOVE(x, y)
721 #define RB_FIND(name, x, y) name##_RB_FIND(x, y)
722 #define RB_NFIND(name, x, y) name##_RB_NFIND(x, y)
723 #define RB_NEXT(name, x, y) name##_RB_NEXT(y)
724 #define RB_PREV(name, x, y) name##_RB_PREV(y)
725 #define RB_MIN(name, x) name##_RB_MINMAX(x, RB_NEGINF)
726 #define RB_MAX(name, x) name##_RB_MINMAX(x, RB_INF)
727
728 #define RB_FOREACH(x, name, head) \
729 for ((x) = RB_MIN(name, head); \
730 (x) != NULL; \
731 (x) = name##_RB_NEXT(x))
732
733 #define RB_FOREACH_SAFE(x, name, head, y) \
734 for ((x) = RB_MIN(name, head); \
735 ((x) != NULL) && ((y) = name##_RB_NEXT(x), 1); \
736 (x) = (y))
737
738 #define RB_FOREACH_REVERSE(x, name, head) \
739 for ((x) = RB_MAX(name, head); \
740 (x) != NULL; \
741 (x) = name##_RB_PREV(x))
742
743 #define RB_FOREACH_REVERSE_SAFE(x, name, head, y) \
744 for ((x) = RB_MAX(name, head); \
745 ((x) != NULL) && ((y) = name##_RB_PREV(x), 1); \
746 (x) = (y))
747
748 #endif /* _SYS_TREE_H_ */