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