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 <[email protected]> 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) \ 89 struct 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) \ 101 struct { \ 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) \ 146 void name##_SPLAY(struct name *, struct type *); \ 147 void name##_SPLAY_MINMAX(struct name *, int); \ 148 struct type *name##_SPLAY_INSERT(struct name *, struct type *); \ 149 struct type *name##_SPLAY_REMOVE(struct name *, struct type *); \ 150 \ 151 /* Finds the node with the same key as elm */ \ 152 static __inline struct type * \ 153 name##_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 \ 163 static __inline struct type * \ 164 name##_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 \ 177 static __inline struct type * \ 178 name##_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) \ 188 struct type * \ 189 name##_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 \ 212 struct type * \ 213 name##_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 \ 233 void \ 234 name##_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 */ \ 269 static __inline struct type * \ 270 name##_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 */ \ 289 void 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) \ 342 struct 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) \ 357 struct { \ 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) \ 427 void name##_RB_INSERT_COLOR(struct name *, struct type *); \ 428 void name##_RB_REMOVE_COLOR(struct name *, struct type *, struct type *);\ 429 struct type *name##_RB_REMOVE(struct name *, struct type *); \ 430 struct type *name##_RB_INSERT(struct name *, struct type *); \ 431 struct type *name##_RB_FIND(struct name *, struct type *); \ 432 struct type *name##_RB_NFIND(struct name *, struct type *); \ 433 struct type *name##_RB_NEXT(struct type *); \ 434 struct type *name##_RB_MINMAX(struct name *, int); \ 435 struct type *name##_RB_GETPARENT(struct type*); \ 436 struct type *name##_RB_SETPARENT(struct type*, struct type*); \ 437 int name##_RB_GETCOLOR(struct type*); \ 438 void 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) \ 460 struct type *name##_RB_GETPARENT(struct type *elm) { \ 461 struct type *__single 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 } \ 468 int 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 } \ 473 void name##_RB_SETCOLOR(struct type *elm,int color) { \ 474 struct type *__single 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 } \ 481 struct 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 \ 488 void \ 489 name##_RB_INSERT_COLOR(struct name *head, struct type *elm) \ 490 { \ 491 struct type *__single parent, *__single gparent, *__single 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 \ 532 void \ 533 name##_RB_REMOVE_COLOR(struct name *head, struct type *parent, struct type *elm) \ 534 { \ 535 struct type *__single 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 *__single 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 *__single 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 \ 610 struct type * \ 611 name##_RB_REMOVE(struct name *head, struct type *elm) \ 612 { \ 613 struct type *__single child, *__single parent, *__single 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 *__single 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; \ 671 color: \ 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 */ \ 678 struct type * \ 679 name##_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 */ \ 709 struct type * \ 710 name##_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)) \ 728 struct type * \ 729 name##_RB_NFIND(struct name *head, struct type *elm) \ 730 { \ 731 struct type *__single tmp = RB_ROOT(head); \ 732 struct type *__single 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 */ \ 749 struct type * \ 750 name##_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 \ 770 struct type * \ 771 name##_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) \ 788 struct 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); \ 797 struct type * \ 798 name##_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