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 /* 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 /* Searches for a matching entry without splaying */ \ 267 static __inline struct type * \ 268 name##_SPLAY_SEARCH(struct name *head, struct type *elm) \ 269 { \ 270 struct type *__tmp = NULL; \ 271 int __comp; \ 272 \ 273 __tmp = (head)->sph_root; \ 274 while ((__tmp != NULL) && ((__comp = (cmp)(elm, __tmp)) != 0)) { \ 275 if (__comp < 0) { \ 276 __tmp = SPLAY_LEFT(__tmp, field); \ 277 } else { \ 278 __tmp = SPLAY_RIGHT(__tmp, field); \ 279 } \ 280 } \ 281 return __tmp; \ 282 } \ 283 \ 284 /* Splay with either the minimum or the maximum element \ 285 * Used to find minimum or maximum element in tree. \ 286 */ \ 287 void name##_SPLAY_MINMAX(struct name *head, int __comp) \ 288 { \ 289 struct type __node, *__left, *__right, *__tmp; \ 290 \ 291 SPLAY_LEFT(&__node, field) = SPLAY_RIGHT(&__node, field) = NULL;\ 292 __left = __right = &__node; \ 293 \ 294 while (1) { \ 295 if (__comp < 0) { \ 296 __tmp = SPLAY_LEFT((head)->sph_root, field); \ 297 if (__tmp == NULL) \ 298 break; \ 299 if (__comp < 0){ \ 300 SPLAY_ROTATE_RIGHT(head, __tmp, field); \ 301 if (SPLAY_LEFT((head)->sph_root, field) == NULL)\ 302 break; \ 303 } \ 304 SPLAY_LINKLEFT(head, __right, field); \ 305 } else if (__comp > 0) { \ 306 __tmp = SPLAY_RIGHT((head)->sph_root, field); \ 307 if (__tmp == NULL) \ 308 break; \ 309 if (__comp > 0) { \ 310 SPLAY_ROTATE_LEFT(head, __tmp, field); \ 311 if (SPLAY_RIGHT((head)->sph_root, field) == NULL)\ 312 break; \ 313 } \ 314 SPLAY_LINKRIGHT(head, __left, field); \ 315 } \ 316 } \ 317 SPLAY_ASSEMBLE(head, &__node, __left, __right, field); \ 318 } 319 320 #define SPLAY_NEGINF -1 321 #define SPLAY_INF 1 322 323 #define SPLAY_INSERT(name, x, y) name##_SPLAY_INSERT(x, y) 324 #define SPLAY_REMOVE(name, x, y) name##_SPLAY_REMOVE(x, y) 325 #define SPLAY_FIND(name, x, y) name##_SPLAY_FIND(x, y) 326 #define SPLAY_SEARCH(name, x, y) name##_SPLAY_SEARCH(x, y) 327 #define SPLAY_NEXT(name, x, y) name##_SPLAY_NEXT(x, y) 328 #define SPLAY_MIN(name, x) (SPLAY_EMPTY(x) ? NULL \ 329 : name##_SPLAY_MIN_MAX(x, SPLAY_NEGINF)) 330 #define SPLAY_MAX(name, x) (SPLAY_EMPTY(x) ? NULL \ 331 : name##_SPLAY_MIN_MAX(x, SPLAY_INF)) 332 333 #define SPLAY_FOREACH(x, name, head) \ 334 for ((x) = SPLAY_MIN(name, head); \ 335 (x) != NULL; \ 336 (x) = SPLAY_NEXT(name, head, x)) 337 338 /* Macros that define a red-black tree */ 339 #define RB_HEAD(name, type) \ 340 struct name { \ 341 struct type *rbh_root; /* root of the tree */ \ 342 } 343 344 #define RB_INITIALIZER(root) \ 345 { NULL } 346 347 #define RB_INIT(root) do { \ 348 (root)->rbh_root = NULL; \ 349 } while ( /*CONSTCOND*/ 0) 350 351 #define RB_BLACK 0 352 #define RB_RED 1 353 #define RB_PLACEHOLDER NULL 354 #define RB_ENTRY(type) \ 355 struct { \ 356 struct type *rbe_left; /* left element */ \ 357 struct type *rbe_right; /* right element */ \ 358 struct type *rbe_parent; /* parent element */ \ 359 } 360 361 #define RB_COLOR_MASK (uintptr_t)0x1 362 #define RB_LEFT(elm, field) (elm)->field.rbe_left 363 #define RB_RIGHT(elm, field) (elm)->field.rbe_right 364 #define _RB_PARENT(elm, field) (elm)->field.rbe_parent 365 #define RB_ROOT(head) (head)->rbh_root 366 #define RB_EMPTY(head) (RB_ROOT(head) == NULL) 367 368 #define RB_SET(name, elm, parent, field) do { \ 369 name##_RB_SETPARENT(elm, parent); \ 370 RB_LEFT(elm, field) = RB_RIGHT(elm, field) = NULL; \ 371 name##_RB_SETCOLOR(elm, RB_RED); \ 372 } while ( /*CONSTCOND*/ 0) 373 374 #define RB_SET_BLACKRED(name, black, red, field) do { \ 375 name##_RB_SETCOLOR(black, RB_BLACK); \ 376 name##_RB_SETCOLOR(red, RB_RED); \ 377 } while ( /*CONSTCOND*/ 0) 378 379 #ifndef RB_AUGMENT 380 #define RB_AUGMENT(x) (void)(x) 381 #endif 382 383 #define RB_ROTATE_LEFT(name, head, elm, tmp, field) do { \ 384 (tmp) = RB_RIGHT(elm, field); \ 385 if ((RB_RIGHT(elm, field) = RB_LEFT(tmp, field)) != NULL) { \ 386 name##_RB_SETPARENT(RB_LEFT(tmp, field),(elm)); \ 387 } \ 388 RB_AUGMENT(elm); \ 389 if (name##_RB_SETPARENT(tmp, name##_RB_GETPARENT(elm)) != NULL) { \ 390 if ((elm) == RB_LEFT(name##_RB_GETPARENT(elm), field)) \ 391 RB_LEFT(name##_RB_GETPARENT(elm), field) = (tmp); \ 392 else \ 393 RB_RIGHT(name##_RB_GETPARENT(elm), field) = (tmp); \ 394 } else \ 395 (head)->rbh_root = (tmp); \ 396 RB_LEFT(tmp, field) = (elm); \ 397 name##_RB_SETPARENT(elm, (tmp)); \ 398 RB_AUGMENT(tmp); \ 399 if ((name##_RB_GETPARENT(tmp))) \ 400 RB_AUGMENT(name##_RB_GETPARENT(tmp)); \ 401 } while ( /*CONSTCOND*/ 0) 402 403 #define RB_ROTATE_RIGHT(name, head, elm, tmp, field) do { \ 404 (tmp) = RB_LEFT(elm, field); \ 405 if ((RB_LEFT(elm, field) = RB_RIGHT(tmp, field)) != NULL) { \ 406 name##_RB_SETPARENT(RB_RIGHT(tmp, field), (elm)); \ 407 } \ 408 RB_AUGMENT(elm); \ 409 if (name##_RB_SETPARENT(tmp, name##_RB_GETPARENT(elm)) != NULL) { \ 410 if ((elm) == RB_LEFT(name##_RB_GETPARENT(elm), field)) \ 411 RB_LEFT(name##_RB_GETPARENT(elm), field) = (tmp); \ 412 else \ 413 RB_RIGHT(name##_RB_GETPARENT(elm), field) = (tmp); \ 414 } else \ 415 (head)->rbh_root = (tmp); \ 416 RB_RIGHT(tmp, field) = (elm); \ 417 name##_RB_SETPARENT(elm, tmp); \ 418 RB_AUGMENT(tmp); \ 419 if ((name##_RB_GETPARENT(tmp))) \ 420 RB_AUGMENT(name##_RB_GETPARENT(tmp)); \ 421 } while ( /*CONSTCOND*/ 0) 422 423 /* Generates prototypes and inline functions */ 424 #define RB_PROTOTYPE(name, type, field, cmp) \ 425 void name##_RB_INSERT_COLOR(struct name *, struct type *); \ 426 void name##_RB_REMOVE_COLOR(struct name *, struct type *, struct type *);\ 427 struct type *name##_RB_REMOVE(struct name *, struct type *); \ 428 struct type *name##_RB_INSERT(struct name *, struct type *); \ 429 struct type *name##_RB_FIND(struct name *, struct type *); \ 430 struct type *name##_RB_NFIND(struct name *, struct type *); \ 431 struct type *name##_RB_NEXT(struct type *); \ 432 struct type *name##_RB_MINMAX(struct name *, int); \ 433 struct type *name##_RB_GETPARENT(struct type*); \ 434 struct type *name##_RB_SETPARENT(struct type*, struct type*); \ 435 int name##_RB_GETCOLOR(struct type*); \ 436 void name##_RB_SETCOLOR(struct type*,int); 437 438 /* Generates prototypes (with storage class) and inline functions */ 439 #define RB_PROTOTYPE_SC(_sc_, name, type, field, cmp) \ 440 _sc_ void name##_RB_INSERT_COLOR(struct name *, struct type *); \ 441 _sc_ void name##_RB_REMOVE_COLOR(struct name *, struct type *, struct type *); \ 442 _sc_ struct type *name##_RB_REMOVE(struct name *, struct type *); \ 443 _sc_ struct type *name##_RB_INSERT(struct name *, struct type *); \ 444 _sc_ struct type *name##_RB_FIND(struct name *, struct type *); \ 445 _sc_ struct type *name##_RB_NFIND(struct name *, struct type *); \ 446 _sc_ struct type *name##_RB_NEXT(struct type *); \ 447 _sc_ struct type *name##_RB_MINMAX(struct name *, int); \ 448 _sc_ struct type *name##_RB_GETPARENT(struct type*); \ 449 _sc_ struct type *name##_RB_SETPARENT(struct type*, struct type*); \ 450 _sc_ int name##_RB_GETCOLOR(struct type*); \ 451 _sc_ void name##_RB_SETCOLOR(struct type*,int) 452 453 454 /* Main rb operation. 455 * Moves node close to the key of elm to top 456 */ 457 #define RB_GENERATE(name, type, field, cmp) \ 458 struct type *name##_RB_GETPARENT(struct type *elm) { \ 459 struct type *parent = _RB_PARENT(elm, field); \ 460 if( parent != NULL) { \ 461 parent = (struct type*)((uintptr_t)parent & ~RB_COLOR_MASK);\ 462 return( (struct type*) ( (parent == (struct type*) RB_PLACEHOLDER) ? NULL: parent));\ 463 } \ 464 return((struct type*)NULL); \ 465 } \ 466 int name##_RB_GETCOLOR(struct type *elm) { \ 467 int color = 0; \ 468 color = (int)((uintptr_t)_RB_PARENT(elm,field) & RB_COLOR_MASK);\ 469 return(color); \ 470 } \ 471 void name##_RB_SETCOLOR(struct type *elm,int color) { \ 472 struct type *parent = name##_RB_GETPARENT(elm); \ 473 if(parent == (struct type*)NULL) \ 474 parent = (struct type*) RB_PLACEHOLDER; \ 475 _RB_PARENT(elm, field) = (struct type*)((uintptr_t)parent | (unsigned int)color);\ 476 } \ 477 struct type *name##_RB_SETPARENT(struct type *elm, struct type *parent) { \ 478 int color = name##_RB_GETCOLOR(elm); \ 479 _RB_PARENT(elm, field) = parent; \ 480 if(color) name##_RB_SETCOLOR(elm, color); \ 481 return(name##_RB_GETPARENT(elm)); \ 482 } \ 483 \ 484 void \ 485 name##_RB_INSERT_COLOR(struct name *head, struct type *elm) \ 486 { \ 487 struct type *parent, *gparent, *tmp; \ 488 while ((parent = name##_RB_GETPARENT(elm)) != NULL && \ 489 name##_RB_GETCOLOR(parent) == RB_RED) { \ 490 gparent = name##_RB_GETPARENT(parent); \ 491 if (parent == RB_LEFT(gparent, field)) { \ 492 tmp = RB_RIGHT(gparent, field); \ 493 if (tmp && name##_RB_GETCOLOR(tmp) == RB_RED) { \ 494 name##_RB_SETCOLOR(tmp, RB_BLACK); \ 495 RB_SET_BLACKRED(name, parent, gparent, field);\ 496 elm = gparent; \ 497 continue; \ 498 } \ 499 if (RB_RIGHT(parent, field) == elm) { \ 500 RB_ROTATE_LEFT(name, head, parent, tmp, field);\ 501 tmp = parent; \ 502 parent = elm; \ 503 elm = tmp; \ 504 } \ 505 RB_SET_BLACKRED(name, parent, gparent, field); \ 506 RB_ROTATE_RIGHT(name,head, gparent, tmp, field); \ 507 } else { \ 508 tmp = RB_LEFT(gparent, field); \ 509 if (tmp && name##_RB_GETCOLOR(tmp) == RB_RED) { \ 510 name##_RB_SETCOLOR(tmp, RB_BLACK); \ 511 RB_SET_BLACKRED(name, parent, gparent, field);\ 512 elm = gparent; \ 513 continue; \ 514 } \ 515 if (RB_LEFT(parent, field) == elm) { \ 516 RB_ROTATE_RIGHT(name, head, parent, tmp, field);\ 517 tmp = parent; \ 518 parent = elm; \ 519 elm = tmp; \ 520 } \ 521 RB_SET_BLACKRED(name, parent, gparent, field); \ 522 RB_ROTATE_LEFT(name, head, gparent, tmp, field); \ 523 } \ 524 } \ 525 name##_RB_SETCOLOR(head->rbh_root, RB_BLACK); \ 526 } \ 527 \ 528 void \ 529 name##_RB_REMOVE_COLOR(struct name *head, struct type *parent, struct type *elm) \ 530 { \ 531 struct type *tmp; \ 532 while ((elm == NULL || name##_RB_GETCOLOR(elm) == RB_BLACK) && \ 533 elm != RB_ROOT(head)) { \ 534 if (RB_LEFT(parent, field) == elm) { \ 535 tmp = RB_RIGHT(parent, field); \ 536 if (name##_RB_GETCOLOR(tmp) == RB_RED) { \ 537 RB_SET_BLACKRED(name, tmp, parent, field); \ 538 RB_ROTATE_LEFT(name, head, parent, tmp, field);\ 539 tmp = RB_RIGHT(parent, field); \ 540 } \ 541 if ((RB_LEFT(tmp, field) == NULL || \ 542 name##_RB_GETCOLOR(RB_LEFT(tmp, field)) == RB_BLACK) &&\ 543 (RB_RIGHT(tmp, field) == NULL || \ 544 name##_RB_GETCOLOR(RB_RIGHT(tmp, field)) == RB_BLACK)) {\ 545 name##_RB_SETCOLOR(tmp, RB_RED); \ 546 elm = parent; \ 547 parent = name##_RB_GETPARENT(elm); \ 548 } else { \ 549 if (RB_RIGHT(tmp, field) == NULL || \ 550 name##_RB_GETCOLOR(RB_RIGHT(tmp, field)) == RB_BLACK) {\ 551 struct type *oleft; \ 552 if ((oleft = RB_LEFT(tmp, field)) \ 553 != NULL) \ 554 name##_RB_SETCOLOR(oleft, RB_BLACK);\ 555 name##_RB_SETCOLOR(tmp, RB_RED); \ 556 RB_ROTATE_RIGHT(name, head, tmp, oleft, field);\ 557 tmp = RB_RIGHT(parent, field); \ 558 } \ 559 name##_RB_SETCOLOR(tmp, (name##_RB_GETCOLOR(parent)));\ 560 name##_RB_SETCOLOR(parent, RB_BLACK); \ 561 if (RB_RIGHT(tmp, field)) \ 562 name##_RB_SETCOLOR(RB_RIGHT(tmp, field),RB_BLACK);\ 563 RB_ROTATE_LEFT(name, head, parent, tmp, field);\ 564 elm = RB_ROOT(head); \ 565 break; \ 566 } \ 567 } else { \ 568 tmp = RB_LEFT(parent, field); \ 569 if (name##_RB_GETCOLOR(tmp) == RB_RED) { \ 570 RB_SET_BLACKRED(name, tmp, parent, field); \ 571 RB_ROTATE_RIGHT(name, head, parent, tmp, field);\ 572 tmp = RB_LEFT(parent, field); \ 573 } \ 574 if ((RB_LEFT(tmp, field) == NULL || \ 575 name##_RB_GETCOLOR(RB_LEFT(tmp, field)) == RB_BLACK) &&\ 576 (RB_RIGHT(tmp, field) == NULL || \ 577 name##_RB_GETCOLOR(RB_RIGHT(tmp, field)) == RB_BLACK)) {\ 578 name##_RB_SETCOLOR(tmp, RB_RED); \ 579 elm = parent; \ 580 parent = name##_RB_GETPARENT(elm); \ 581 } else { \ 582 if (RB_LEFT(tmp, field) == NULL || \ 583 name##_RB_GETCOLOR(RB_LEFT(tmp, field)) == RB_BLACK) {\ 584 struct type *oright; \ 585 if ((oright = RB_RIGHT(tmp, field)) \ 586 != NULL) \ 587 name##_RB_SETCOLOR(oright, RB_BLACK);\ 588 name##_RB_SETCOLOR(tmp, RB_RED); \ 589 RB_ROTATE_LEFT(name, head, tmp, oright, field);\ 590 tmp = RB_LEFT(parent, field); \ 591 } \ 592 name##_RB_SETCOLOR(tmp,(name##_RB_GETCOLOR(parent)));\ 593 name##_RB_SETCOLOR(parent, RB_BLACK); \ 594 if (RB_LEFT(tmp, field)) \ 595 name##_RB_SETCOLOR(RB_LEFT(tmp, field), RB_BLACK);\ 596 RB_ROTATE_RIGHT(name, head, parent, tmp, field);\ 597 elm = RB_ROOT(head); \ 598 break; \ 599 } \ 600 } \ 601 } \ 602 if (elm) \ 603 name##_RB_SETCOLOR(elm, RB_BLACK); \ 604 } \ 605 \ 606 struct type * \ 607 name##_RB_REMOVE(struct name *head, struct type *elm) \ 608 { \ 609 struct type *child, *parent, *old = elm; \ 610 int color; \ 611 if (RB_LEFT(elm, field) == NULL) \ 612 child = RB_RIGHT(elm, field); \ 613 else if (RB_RIGHT(elm, field) == NULL) \ 614 child = RB_LEFT(elm, field); \ 615 else { \ 616 struct type *left; \ 617 elm = RB_RIGHT(elm, field); \ 618 while ((left = RB_LEFT(elm, field)) != NULL) \ 619 elm = left; \ 620 child = RB_RIGHT(elm, field); \ 621 parent = name##_RB_GETPARENT(elm); \ 622 color = name##_RB_GETCOLOR(elm); \ 623 if (child) \ 624 name##_RB_SETPARENT(child, parent); \ 625 if (parent) { \ 626 if (RB_LEFT(parent, field) == elm) \ 627 RB_LEFT(parent, field) = child; \ 628 else \ 629 RB_RIGHT(parent, field) = child; \ 630 RB_AUGMENT(parent); \ 631 } else \ 632 RB_ROOT(head) = child; \ 633 if (name##_RB_GETPARENT(elm) == old) \ 634 parent = elm; \ 635 (elm)->field = (old)->field; \ 636 if (name##_RB_GETPARENT(old)) { \ 637 if (RB_LEFT(name##_RB_GETPARENT(old), field) == old)\ 638 RB_LEFT(name##_RB_GETPARENT(old), field) = elm;\ 639 else \ 640 RB_RIGHT(name##_RB_GETPARENT(old), field) = elm;\ 641 RB_AUGMENT(name##_RB_GETPARENT(old)); \ 642 } else \ 643 RB_ROOT(head) = elm; \ 644 name##_RB_SETPARENT(RB_LEFT(old, field), elm); \ 645 if (RB_RIGHT(old, field)) \ 646 name##_RB_SETPARENT(RB_RIGHT(old, field), elm); \ 647 if (parent) { \ 648 left = parent; \ 649 do { \ 650 RB_AUGMENT(left); \ 651 } while ((left = name##_RB_GETPARENT(left)) != NULL); \ 652 } \ 653 goto color; \ 654 } \ 655 parent = name##_RB_GETPARENT(elm); \ 656 color = name##_RB_GETCOLOR(elm); \ 657 if (child) \ 658 name##_RB_SETPARENT(child, parent); \ 659 if (parent) { \ 660 if (RB_LEFT(parent, field) == elm) \ 661 RB_LEFT(parent, field) = child; \ 662 else \ 663 RB_RIGHT(parent, field) = child; \ 664 RB_AUGMENT(parent); \ 665 } else \ 666 RB_ROOT(head) = child; \ 667 color: \ 668 if (color == RB_BLACK) \ 669 name##_RB_REMOVE_COLOR(head, parent, child); \ 670 return (old); \ 671 } \ 672 \ 673 /* Inserts a node into the RB tree */ \ 674 struct type * \ 675 name##_RB_INSERT(struct name *head, struct type *elm) \ 676 { \ 677 struct type *tmp; \ 678 struct type *parent = NULL; \ 679 int comp = 0; \ 680 tmp = RB_ROOT(head); \ 681 while (tmp) { \ 682 parent = tmp; \ 683 comp = (cmp)(elm, parent); \ 684 if (comp < 0) \ 685 tmp = RB_LEFT(tmp, field); \ 686 else if (comp > 0) \ 687 tmp = RB_RIGHT(tmp, field); \ 688 else \ 689 return (tmp); \ 690 } \ 691 RB_SET(name, elm, parent, field); \ 692 if (parent != NULL) { \ 693 if (comp < 0) \ 694 RB_LEFT(parent, field) = elm; \ 695 else \ 696 RB_RIGHT(parent, field) = elm; \ 697 RB_AUGMENT(parent); \ 698 } else \ 699 RB_ROOT(head) = elm; \ 700 name##_RB_INSERT_COLOR(head, elm); \ 701 return (NULL); \ 702 } \ 703 \ 704 /* Finds the node with the same key as elm */ \ 705 struct type * \ 706 name##_RB_FIND(struct name *head, struct type *elm) \ 707 { \ 708 struct type *tmp = RB_ROOT(head); \ 709 int comp; \ 710 while (tmp) { \ 711 comp = cmp(elm, tmp); \ 712 if (comp < 0) \ 713 tmp = RB_LEFT(tmp, field); \ 714 else if (comp > 0) \ 715 tmp = RB_RIGHT(tmp, field); \ 716 else \ 717 return (tmp); \ 718 } \ 719 return (NULL); \ 720 } \ 721 \ 722 /* Finds the first node greater than or equal to the search key */ \ 723 __attribute__((unused)) \ 724 struct type * \ 725 name##_RB_NFIND(struct name *head, struct type *elm) \ 726 { \ 727 struct type *tmp = RB_ROOT(head); \ 728 struct type *res = NULL; \ 729 int comp; \ 730 while (tmp) { \ 731 comp = cmp(elm, tmp); \ 732 if (comp < 0) { \ 733 res = tmp; \ 734 tmp = RB_LEFT(tmp, field); \ 735 } \ 736 else if (comp > 0) \ 737 tmp = RB_RIGHT(tmp, field); \ 738 else \ 739 return (tmp); \ 740 } \ 741 return (res); \ 742 } \ 743 \ 744 /* ARGSUSED */ \ 745 struct type * \ 746 name##_RB_NEXT(struct type *elm) \ 747 { \ 748 if (RB_RIGHT(elm, field)) { \ 749 elm = RB_RIGHT(elm, field); \ 750 while (RB_LEFT(elm, field)) \ 751 elm = RB_LEFT(elm, field); \ 752 } else { \ 753 if (name##_RB_GETPARENT(elm) && \ 754 (elm == RB_LEFT(name##_RB_GETPARENT(elm), field))) \ 755 elm = name##_RB_GETPARENT(elm); \ 756 else { \ 757 while (name##_RB_GETPARENT(elm) && \ 758 (elm == RB_RIGHT(name##_RB_GETPARENT(elm), field)))\ 759 elm = name##_RB_GETPARENT(elm); \ 760 elm = name##_RB_GETPARENT(elm); \ 761 } \ 762 } \ 763 return (elm); \ 764 } \ 765 \ 766 struct type * \ 767 name##_RB_MINMAX(struct name *head, int val) \ 768 { \ 769 struct type *tmp = RB_ROOT(head); \ 770 struct type *parent = NULL; \ 771 while (tmp) { \ 772 parent = tmp; \ 773 if (val < 0) \ 774 tmp = RB_LEFT(tmp, field); \ 775 else \ 776 tmp = RB_RIGHT(tmp, field); \ 777 } \ 778 return (parent); \ 779 } 780 781 782 #define RB_PROTOTYPE_PREV(name, type, field, cmp) \ 783 RB_PROTOTYPE(name, type, field, cmp) \ 784 struct type *name##_RB_PREV(struct type *); 785 786 787 #define RB_PROTOTYPE_SC_PREV(_sc_, name, type, field, cmp) \ 788 RB_PROTOTYPE_SC(_sc_, name, type, field, cmp); \ 789 _sc_ struct type *name##_RB_PREV(struct type *) 790 791 #define RB_GENERATE_PREV(name, type, field, cmp) \ 792 RB_GENERATE(name, type, field, cmp); \ 793 struct type * \ 794 name##_RB_PREV(struct type *elm) \ 795 { \ 796 if (RB_LEFT(elm, field)) { \ 797 elm = RB_LEFT(elm, field); \ 798 while (RB_RIGHT(elm, field)) \ 799 elm = RB_RIGHT(elm, field); \ 800 } else { \ 801 if (name##_RB_GETPARENT(elm) && \ 802 (elm == RB_RIGHT(name##_RB_GETPARENT(elm), field))) \ 803 elm = name##_RB_GETPARENT(elm); \ 804 else { \ 805 while (name##_RB_GETPARENT(elm) && \ 806 (elm == RB_LEFT(name##_RB_GETPARENT(elm), field)))\ 807 elm = name##_RB_GETPARENT(elm); \ 808 elm = name##_RB_GETPARENT(elm); \ 809 } \ 810 } \ 811 return (elm); \ 812 } \ 813 814 #define RB_NEGINF -1 815 #define RB_INF 1 816 817 #define RB_INSERT(name, x, y) name##_RB_INSERT(x, y) 818 #define RB_REMOVE(name, x, y) name##_RB_REMOVE(x, y) 819 #define RB_FIND(name, x, y) name##_RB_FIND(x, y) 820 #define RB_NFIND(name, x, y) name##_RB_NFIND(x, y) 821 #define RB_NEXT(name, x, y) name##_RB_NEXT(y) 822 #define RB_PREV(name, x, y) name##_RB_PREV(y) 823 #define RB_MIN(name, x) name##_RB_MINMAX(x, RB_NEGINF) 824 #define RB_MAX(name, x) name##_RB_MINMAX(x, RB_INF) 825 826 #define RB_FOREACH(x, name, head) \ 827 for ((x) = RB_MIN(name, head); \ 828 (x) != NULL; \ 829 (x) = name##_RB_NEXT(x)) 830 831 #define RB_FOREACH_FROM(x, name, y) \ 832 for ((x) = (y); \ 833 ((x) != NULL) && ((y) = name##_RB_NEXT(x), (x) != NULL); \ 834 (x) = (y)) 835 836 #define RB_FOREACH_REVERSE_FROM(x, name, y) \ 837 for ((x) = (y); \ 838 ((x) != NULL) && ((y) = name##_RB_PREV(x), (x) != NULL); \ 839 (x) = (y)) 840 841 #define RB_FOREACH_SAFE(x, name, head, y) \ 842 for ((x) = RB_MIN(name, head); \ 843 ((x) != NULL) && ((y) = name##_RB_NEXT(x), (x) != NULL); \ 844 (x) = (y)) 845 846 #endif /* _LIBKERN_TREE_H_ */ 847