]> git.saurik.com Git - apple/xnu.git/blob - libkern/libkern/tree.h
projects / apple / xnu.git / blob
? search:


15b6636395c5950aa8c22221097217b4eed98c99
[apple/xnu.git] / libkern / libkern / tree.h
1 /*
2 * Copyright (c) 2009-2010 Apple 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 _LIBKERN_TREE_H_
57 #define _LIBKERN_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) \
87 struct 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) \
99 struct { \
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) \
144 void name##_SPLAY(struct name *, struct type *); \
145 void name##_SPLAY_MINMAX(struct name *, int); \
146 struct type *name##_SPLAY_INSERT(struct name *, struct type *); \
147 struct type *name##_SPLAY_REMOVE(struct name *, struct type *); \
148 \
149 /* Finds the node with the same key as elm */ \
150 static __inline struct type * \
151 name##_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 \
161 static __inline struct type * \
162 name##_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 \
175 static __inline struct type * \
176 name##_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) \
186 struct type * \
187 name##_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 \
210 struct type * \
211 name##_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 \
231 void \
232 name##_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 */ \
269 void 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) \
321 struct 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_PLACEHOLDER NULL
335 #define RB_ENTRY(type) \
336 struct { \
337 struct type *rbe_left; /* left element */ \
338 struct type *rbe_right; /* right element */ \
339 struct type *rbe_parent; /* parent element */ \
340 }
341
342 #define RB_COLOR_MASK (uintptr_t)0x1
343 #define RB_LEFT(elm, field) (elm)->field.rbe_left
344 #define RB_RIGHT(elm, field) (elm)->field.rbe_right
345 #define _RB_PARENT(elm, field) (elm)->field.rbe_parent
346 #define RB_ROOT(head) (head)->rbh_root
347 #define RB_EMPTY(head) (RB_ROOT(head) == NULL)
348
349 #define RB_SET(name, elm, parent, field) do { \
350 name##_RB_SETPARENT(elm, parent); \
351 RB_LEFT(elm, field) = RB_RIGHT(elm, field) = NULL; \
352 name##_RB_SETCOLOR(elm, RB_RED); \
353 } while ( /*CONSTCOND*/ 0)
354
355 #define RB_SET_BLACKRED(name, black, red, field) do { \
356 name##_RB_SETCOLOR(black, RB_BLACK); \
357 name##_RB_SETCOLOR(red, 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(name, head, elm, tmp, field) do { \
365 (tmp) = RB_RIGHT(elm, field); \
366 if ((RB_RIGHT(elm, field) = RB_LEFT(tmp, field)) != NULL) { \
367 name##_RB_SETPARENT(RB_LEFT(tmp, field),(elm)); \
368 } \
369 RB_AUGMENT(elm); \
370 if (name##_RB_SETPARENT(tmp, name##_RB_GETPARENT(elm)) != NULL) { \
371 if ((elm) == RB_LEFT(name##_RB_GETPARENT(elm), field)) \
372 RB_LEFT(name##_RB_GETPARENT(elm), field) = (tmp); \
373 else \
374 RB_RIGHT(name##_RB_GETPARENT(elm), field) = (tmp); \
375 } else \
376 (head)->rbh_root = (tmp); \
377 RB_LEFT(tmp, field) = (elm); \
378 name##_RB_SETPARENT(elm, (tmp)); \
379 RB_AUGMENT(tmp); \
380 if ((name##_RB_GETPARENT(tmp))) \
381 RB_AUGMENT(name##_RB_GETPARENT(tmp)); \
382 } while ( /*CONSTCOND*/ 0)
383
384 #define RB_ROTATE_RIGHT(name, head, elm, tmp, field) do { \
385 (tmp) = RB_LEFT(elm, field); \
386 if ((RB_LEFT(elm, field) = RB_RIGHT(tmp, field)) != NULL) { \
387 name##_RB_SETPARENT(RB_RIGHT(tmp, field), (elm)); \
388 } \
389 RB_AUGMENT(elm); \
390 if (name##_RB_SETPARENT(tmp, name##_RB_GETPARENT(elm)) != NULL) { \
391 if ((elm) == RB_LEFT(name##_RB_GETPARENT(elm), field)) \
392 RB_LEFT(name##_RB_GETPARENT(elm), field) = (tmp); \
393 else \
394 RB_RIGHT(name##_RB_GETPARENT(elm), field) = (tmp); \
395 } else \
396 (head)->rbh_root = (tmp); \
397 RB_RIGHT(tmp, field) = (elm); \
398 name##_RB_SETPARENT(elm, tmp); \
399 RB_AUGMENT(tmp); \
400 if ((name##_RB_GETPARENT(tmp))) \
401 RB_AUGMENT(name##_RB_GETPARENT(tmp)); \
402 } while ( /*CONSTCOND*/ 0)
403
404 /* Generates prototypes and inline functions */
405 #define RB_PROTOTYPE(name, type, field, cmp) \
406 void name##_RB_INSERT_COLOR(struct name *, struct type *); \
407 void name##_RB_REMOVE_COLOR(struct name *, struct type *, struct type *);\
408 struct type *name##_RB_REMOVE(struct name *, struct type *); \
409 struct type *name##_RB_INSERT(struct name *, struct type *); \
410 struct type *name##_RB_FIND(struct name *, struct type *); \
411 struct type *name##_RB_NEXT(struct type *); \
412 struct type *name##_RB_MINMAX(struct name *, int); \
413 struct type *name##_RB_GETPARENT(struct type*); \
414 struct type *name##_RB_SETPARENT(struct type*, struct type*); \
415 int name##_RB_GETCOLOR(struct type*); \
416 void name##_RB_SETCOLOR(struct type*,int);
417
418 /* Generates prototypes (with storage class) and inline functions */
419 #define RB_PROTOTYPE_SC(_sc_, name, type, field, cmp) \
420 _sc_ void name##_RB_INSERT_COLOR(struct name *, struct type *); \
421 _sc_ void name##_RB_REMOVE_COLOR(struct name *, struct type *, struct type *); \
422 _sc_ struct type *name##_RB_REMOVE(struct name *, struct type *); \
423 _sc_ struct type *name##_RB_INSERT(struct name *, struct type *); \
424 _sc_ struct type *name##_RB_FIND(struct name *, struct type *); \
425 _sc_ struct type *name##_RB_NEXT(struct type *); \
426 _sc_ struct type *name##_RB_MINMAX(struct name *, int); \
427 _sc_ struct type *name##_RB_GETPARENT(struct type*); \
428 _sc_ struct type *name##_RB_SETPARENT(struct type*, struct type*); \
429 _sc_ int name##_RB_GETCOLOR(struct type*); \
430 _sc_ void name##_RB_SETCOLOR(struct type*,int);
431
432
433 /* Main rb operation.
434 * Moves node close to the key of elm to top
435 */
436 #define RB_GENERATE(name, type, field, cmp) \
437 struct type *name##_RB_GETPARENT(struct type *elm) { \
438 struct type *parent = _RB_PARENT(elm, field); \
439 if( parent != NULL) { \
440 parent = (struct type*)((uintptr_t)parent & ~RB_COLOR_MASK);\
441 return( (struct type*) ( (parent == (struct type*) RB_PLACEHOLDER) ? NULL: parent));\
442 } \
443 return((struct type*)NULL); \
444 } \
445 int name##_RB_GETCOLOR(struct type *elm) { \
446 int color = 0; \
447 color = (int)((uintptr_t)_RB_PARENT(elm,field) & RB_COLOR_MASK);\
448 return(color); \
449 } \
450 void name##_RB_SETCOLOR(struct type *elm,int color) { \
451 struct type *parent = name##_RB_GETPARENT(elm); \
452 if(parent == (struct type*)NULL) \
453 parent = (struct type*) RB_PLACEHOLDER; \
454 _RB_PARENT(elm, field) = (struct type*)((uintptr_t)parent | (unsigned int)color);\
455 } \
456 struct type *name##_RB_SETPARENT(struct type *elm, struct type *parent) { \
457 int color = name##_RB_GETCOLOR(elm); \
458 _RB_PARENT(elm, field) = parent; \
459 if(color) name##_RB_SETCOLOR(elm, color); \
460 return(name##_RB_GETPARENT(elm)); \
461 } \
462 \
463 void \
464 name##_RB_INSERT_COLOR(struct name *head, struct type *elm) \
465 { \
466 struct type *parent, *gparent, *tmp; \
467 while ((parent = name##_RB_GETPARENT(elm)) != NULL && \
468 name##_RB_GETCOLOR(parent) == RB_RED) { \
469 gparent = name##_RB_GETPARENT(parent); \
470 if (parent == RB_LEFT(gparent, field)) { \
471 tmp = RB_RIGHT(gparent, field); \
472 if (tmp && name##_RB_GETCOLOR(tmp) == RB_RED) { \
473 name##_RB_SETCOLOR(tmp, RB_BLACK); \
474 RB_SET_BLACKRED(name, parent, gparent, field);\
475 elm = gparent; \
476 continue; \
477 } \
478 if (RB_RIGHT(parent, field) == elm) { \
479 RB_ROTATE_LEFT(name, head, parent, tmp, field);\
480 tmp = parent; \
481 parent = elm; \
482 elm = tmp; \
483 } \
484 RB_SET_BLACKRED(name, parent, gparent, field); \
485 RB_ROTATE_RIGHT(name,head, gparent, tmp, field); \
486 } else { \
487 tmp = RB_LEFT(gparent, field); \
488 if (tmp && name##_RB_GETCOLOR(tmp) == RB_RED) { \
489 name##_RB_SETCOLOR(tmp, RB_BLACK); \
490 RB_SET_BLACKRED(name, parent, gparent, field);\
491 elm = gparent; \
492 continue; \
493 } \
494 if (RB_LEFT(parent, field) == elm) { \
495 RB_ROTATE_RIGHT(name, head, parent, tmp, field);\
496 tmp = parent; \
497 parent = elm; \
498 elm = tmp; \
499 } \
500 RB_SET_BLACKRED(name, parent, gparent, field); \
501 RB_ROTATE_LEFT(name, head, gparent, tmp, field); \
502 } \
503 } \
504 name##_RB_SETCOLOR(head->rbh_root, RB_BLACK); \
505 } \
506 \
507 void \
508 name##_RB_REMOVE_COLOR(struct name *head, struct type *parent, struct type *elm) \
509 { \
510 struct type *tmp; \
511 while ((elm == NULL || name##_RB_GETCOLOR(elm) == RB_BLACK) && \
512 elm != RB_ROOT(head)) { \
513 if (RB_LEFT(parent, field) == elm) { \
514 tmp = RB_RIGHT(parent, field); \
515 if (name##_RB_GETCOLOR(tmp) == RB_RED) { \
516 RB_SET_BLACKRED(name, tmp, parent, field); \
517 RB_ROTATE_LEFT(name, head, parent, tmp, field);\
518 tmp = RB_RIGHT(parent, field); \
519 } \
520 if ((RB_LEFT(tmp, field) == NULL || \
521 name##_RB_GETCOLOR(RB_LEFT(tmp, field)) == RB_BLACK) &&\
522 (RB_RIGHT(tmp, field) == NULL || \
523 name##_RB_GETCOLOR(RB_RIGHT(tmp, field)) == RB_BLACK)) {\
524 name##_RB_SETCOLOR(tmp, RB_RED); \
525 elm = parent; \
526 parent = name##_RB_GETPARENT(elm); \
527 } else { \
528 if (RB_RIGHT(tmp, field) == NULL || \
529 name##_RB_GETCOLOR(RB_RIGHT(tmp, field)) == RB_BLACK) {\
530 struct type *oleft; \
531 if ((oleft = RB_LEFT(tmp, field)) \
532 != NULL) \
533 name##_RB_SETCOLOR(oleft, RB_BLACK);\
534 name##_RB_SETCOLOR(tmp, RB_RED); \
535 RB_ROTATE_RIGHT(name, head, tmp, oleft, field);\
536 tmp = RB_RIGHT(parent, field); \
537 } \
538 name##_RB_SETCOLOR(tmp, (name##_RB_GETCOLOR(parent)));\
539 name##_RB_SETCOLOR(parent, RB_BLACK); \
540 if (RB_RIGHT(tmp, field)) \
541 name##_RB_SETCOLOR(RB_RIGHT(tmp, field),RB_BLACK);\
542 RB_ROTATE_LEFT(name, head, parent, tmp, field);\
543 elm = RB_ROOT(head); \
544 break; \
545 } \
546 } else { \
547 tmp = RB_LEFT(parent, field); \
548 if (name##_RB_GETCOLOR(tmp) == RB_RED) { \
549 RB_SET_BLACKRED(name, tmp, parent, field); \
550 RB_ROTATE_RIGHT(name, head, parent, tmp, field);\
551 tmp = RB_LEFT(parent, field); \
552 } \
553 if ((RB_LEFT(tmp, field) == NULL || \
554 name##_RB_GETCOLOR(RB_LEFT(tmp, field)) == RB_BLACK) &&\
555 (RB_RIGHT(tmp, field) == NULL || \
556 name##_RB_GETCOLOR(RB_RIGHT(tmp, field)) == RB_BLACK)) {\
557 name##_RB_SETCOLOR(tmp, RB_RED); \
558 elm = parent; \
559 parent = name##_RB_GETPARENT(elm); \
560 } else { \
561 if (RB_LEFT(tmp, field) == NULL || \
562 name##_RB_GETCOLOR(RB_LEFT(tmp, field)) == RB_BLACK) {\
563 struct type *oright; \
564 if ((oright = RB_RIGHT(tmp, field)) \
565 != NULL) \
566 name##_RB_SETCOLOR(oright, RB_BLACK);\
567 name##_RB_SETCOLOR(tmp, RB_RED); \
568 RB_ROTATE_LEFT(name, head, tmp, oright, field);\
569 tmp = RB_LEFT(parent, field); \
570 } \
571 name##_RB_SETCOLOR(tmp,(name##_RB_GETCOLOR(parent)));\
572 name##_RB_SETCOLOR(parent, RB_BLACK); \
573 if (RB_LEFT(tmp, field)) \
574 name##_RB_SETCOLOR(RB_LEFT(tmp, field), RB_BLACK);\
575 RB_ROTATE_RIGHT(name, head, parent, tmp, field);\
576 elm = RB_ROOT(head); \
577 break; \
578 } \
579 } \
580 } \
581 if (elm) \
582 name##_RB_SETCOLOR(elm, RB_BLACK); \
583 } \
584 \
585 struct type * \
586 name##_RB_REMOVE(struct name *head, struct type *elm) \
587 { \
588 struct type *child, *parent, *old = elm; \
589 int color; \
590 if (RB_LEFT(elm, field) == NULL) \
591 child = RB_RIGHT(elm, field); \
592 else if (RB_RIGHT(elm, field) == NULL) \
593 child = RB_LEFT(elm, field); \
594 else { \
595 struct type *left; \
596 elm = RB_RIGHT(elm, field); \
597 while ((left = RB_LEFT(elm, field)) != NULL) \
598 elm = left; \
599 child = RB_RIGHT(elm, field); \
600 parent = name##_RB_GETPARENT(elm); \
601 color = name##_RB_GETCOLOR(elm); \
602 if (child) \
603 name##_RB_SETPARENT(child, parent); \
604 if (parent) { \
605 if (RB_LEFT(parent, field) == elm) \
606 RB_LEFT(parent, field) = child; \
607 else \
608 RB_RIGHT(parent, field) = child; \
609 RB_AUGMENT(parent); \
610 } else \
611 RB_ROOT(head) = child; \
612 if (name##_RB_GETPARENT(elm) == old) \
613 parent = elm; \
614 (elm)->field = (old)->field; \
615 if (name##_RB_GETPARENT(old)) { \
616 if (RB_LEFT(name##_RB_GETPARENT(old), field) == old)\
617 RB_LEFT(name##_RB_GETPARENT(old), field) = elm;\
618 else \
619 RB_RIGHT(name##_RB_GETPARENT(old), field) = elm;\
620 RB_AUGMENT(name##_RB_GETPARENT(old)); \
621 } else \
622 RB_ROOT(head) = elm; \
623 name##_RB_SETPARENT(RB_LEFT(old, field), elm); \
624 if (RB_RIGHT(old, field)) \
625 name##_RB_SETPARENT(RB_RIGHT(old, field), elm); \
626 if (parent) { \
627 left = parent; \
628 do { \
629 RB_AUGMENT(left); \
630 } while ((left = name##_RB_GETPARENT(left)) != NULL); \
631 } \
632 goto color; \
633 } \
634 parent = name##_RB_GETPARENT(elm); \
635 color = name##_RB_GETCOLOR(elm); \
636 if (child) \
637 name##_RB_SETPARENT(child, parent); \
638 if (parent) { \
639 if (RB_LEFT(parent, field) == elm) \
640 RB_LEFT(parent, field) = child; \
641 else \
642 RB_RIGHT(parent, field) = child; \
643 RB_AUGMENT(parent); \
644 } else \
645 RB_ROOT(head) = child; \
646 color: \
647 if (color == RB_BLACK) \
648 name##_RB_REMOVE_COLOR(head, parent, child); \
649 return (old); \
650 } \
651 \
652 /* Inserts a node into the RB tree */ \
653 struct type * \
654 name##_RB_INSERT(struct name *head, struct type *elm) \
655 { \
656 struct type *tmp; \
657 struct type *parent = NULL; \
658 int comp = 0; \
659 tmp = RB_ROOT(head); \
660 while (tmp) { \
661 parent = tmp; \
662 comp = (cmp)(elm, parent); \
663 if (comp < 0) \
664 tmp = RB_LEFT(tmp, field); \
665 else if (comp > 0) \
666 tmp = RB_RIGHT(tmp, field); \
667 else \
668 return (tmp); \
669 } \
670 RB_SET(name, elm, parent, field); \
671 if (parent != NULL) { \
672 if (comp < 0) \
673 RB_LEFT(parent, field) = elm; \
674 else \
675 RB_RIGHT(parent, field) = elm; \
676 RB_AUGMENT(parent); \
677 } else \
678 RB_ROOT(head) = elm; \
679 name##_RB_INSERT_COLOR(head, elm); \
680 return (NULL); \
681 } \
682 \
683 /* Finds the node with the same key as elm */ \
684 struct type * \
685 name##_RB_FIND(struct name *head, struct type *elm) \
686 { \
687 struct type *tmp = RB_ROOT(head); \
688 int comp; \
689 while (tmp) { \
690 comp = cmp(elm, tmp); \
691 if (comp < 0) \
692 tmp = RB_LEFT(tmp, field); \
693 else if (comp > 0) \
694 tmp = RB_RIGHT(tmp, field); \
695 else \
696 return (tmp); \
697 } \
698 return (NULL); \
699 } \
700 \
701 /* ARGSUSED */ \
702 struct type * \
703 name##_RB_NEXT(struct type *elm) \
704 { \
705 if (RB_RIGHT(elm, field)) { \
706 elm = RB_RIGHT(elm, field); \
707 while (RB_LEFT(elm, field)) \
708 elm = RB_LEFT(elm, field); \
709 } else { \
710 if (name##_RB_GETPARENT(elm) && \
711 (elm == RB_LEFT(name##_RB_GETPARENT(elm), field))) \
712 elm = name##_RB_GETPARENT(elm); \
713 else { \
714 while (name##_RB_GETPARENT(elm) && \
715 (elm == RB_RIGHT(name##_RB_GETPARENT(elm), field)))\
716 elm = name##_RB_GETPARENT(elm); \
717 elm = name##_RB_GETPARENT(elm); \
718 } \
719 } \
720 return (elm); \
721 } \
722 \
723 struct type * \
724 name##_RB_MINMAX(struct name *head, int val) \
725 { \
726 struct type *tmp = RB_ROOT(head); \
727 struct type *parent = NULL; \
728 while (tmp) { \
729 parent = tmp; \
730 if (val < 0) \
731 tmp = RB_LEFT(tmp, field); \
732 else \
733 tmp = RB_RIGHT(tmp, field); \
734 } \
735 return (parent); \
736 }
737
738
739 #define RB_PROTOTYPE_PREV(name, type, field, cmp) \
740 RB_PROTOTYPE(name, type, field, cmp) \
741 struct type *name##_RB_PREV(struct type *);
742
743
744 #define RB_PROTOTYPE_SC_PREV(_sc_, name, type, field, cmp) \
745 RB_PROTOTYPE_SC(_sc_, name, type, field, cmp) \
746 _sc_ struct type *name##_RB_PREV(struct type *);
747
748 #define RB_GENERATE_PREV(name, type, field, cmp) \
749 RB_GENERATE(name, type, field, cmp) \
750 struct type * \
751 name##_RB_PREV(struct type *elm) \
752 { \
753 if (RB_LEFT(elm, field)) { \
754 elm = RB_LEFT(elm, field); \
755 while (RB_RIGHT(elm, field)) \
756 elm = RB_RIGHT(elm, field); \
757 } else { \
758 if (name##_RB_GETPARENT(elm) && \
759 (elm == RB_RIGHT(name##_RB_GETPARENT(elm), field))) \
760 elm = name##_RB_GETPARENT(elm); \
761 else { \
762 while (name##_RB_GETPARENT(elm) && \
763 (elm == RB_LEFT(name##_RB_GETPARENT(elm), field)))\
764 elm = name##_RB_GETPARENT(elm); \
765 elm = name##_RB_GETPARENT(elm); \
766 } \
767 } \
768 return (elm); \
769 } \
770
771 #define RB_NEGINF -1
772 #define RB_INF 1
773
774 #define RB_INSERT(name, x, y) name##_RB_INSERT(x, y)
775 #define RB_REMOVE(name, x, y) name##_RB_REMOVE(x, y)
776 #define RB_FIND(name, x, y) name##_RB_FIND(x, y)
777 #define RB_NEXT(name, x, y) name##_RB_NEXT(y)
778 #define RB_PREV(name, x, y) name##_RB_PREV(y)
779 #define RB_MIN(name, x) name##_RB_MINMAX(x, RB_NEGINF)
780 #define RB_MAX(name, x) name##_RB_MINMAX(x, RB_INF)
781
782 #define RB_FOREACH(x, name, head) \
783 for ((x) = RB_MIN(name, head); \
784 (x) != NULL; \
785 (x) = name##_RB_NEXT(x))
786
787 #define RB_FOREACH_FROM(x, name, y) \
788 for ((x) = (y); \
789 ((x) != NULL) && ((y) = name##_RB_NEXT(x), (x) != NULL); \
790 (x) = (y))
791
792 #define RB_FOREACH_REVERSE_FROM(x, name, y) \
793 for ((x) = (y); \
794 ((x) != NULL) && ((y) = name##_RB_PREV(x), (x) != NULL); \
795 (x) = (y))
796
797 #define RB_FOREACH_SAFE(x, name, head, y) \
798 for ((x) = RB_MIN(name, head); \
799 ((x) != NULL) && ((y) = name##_RB_NEXT(x), (x) != NULL); \
800 (x) = (y))
801
802 #endif /* _LIBKERN_TREE_H_ */
mirror of XNU