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