1 /* 2 * Copyright (c) 2008 Apple Computer, Inc. All rights reserved. 3 * 4 * @APPLE_OSREFERENCE_LICENSE_HEADER_START@ 5 * 6 * This file contains Original Code and/or Modifications of Original Code 7 * as defined in and that are subject to the Apple Public Source License 8 * Version 2.0 (the 'License'). You may not use this file except in 9 * compliance with the License. The rights granted to you under the License 10 * may not be used to create, or enable the creation or redistribution of, 11 * unlawful or unlicensed copies of an Apple operating system, or to 12 * circumvent, violate, or enable the circumvention or violation of, any 13 * terms of an Apple operating system software license agreement. 14 * 15 * Please obtain a copy of the License at 16 * http://www.opensource.apple.com/apsl/ and read it before using this file. 17 * 18 * The Original Code and all software distributed under the License are 19 * distributed on an 'AS IS' basis, WITHOUT WARRANTY OF ANY KIND, EITHER 20 * EXPRESS OR IMPLIED, AND APPLE HEREBY DISCLAIMS ALL SUCH WARRANTIES, 21 * INCLUDING WITHOUT LIMITATION, ANY WARRANTIES OF MERCHANTABILITY, 22 * FITNESS FOR A PARTICULAR PURPOSE, QUIET ENJOYMENT OR NON-INFRINGEMENT. 23 * Please see the License for the specific language governing rights and 24 * limitations under the License. 25 * 26 * @APPLE_OSREFERENCE_LICENSE_HEADER_END@ 27 */ 28 29 /* $NetBSD: tree.h,v 1.13 2006/08/27 22:32:38 christos Exp $ */ 30 /* $OpenBSD: tree.h,v 1.7 2002/10/17 21:51:54 art Exp $ */ 31 /* 32 * Copyright 2002 Niels Provos <provos@citi.umich.edu> 33 * All rights reserved. 34 * 35 * Redistribution and use in source and binary forms, with or without 36 * modification, are permitted provided that the following conditions 37 * are met: 38 * 1. Redistributions of source code must retain the above copyright 39 * notice, this list of conditions and the following disclaimer. 40 * 2. Redistributions in binary form must reproduce the above copyright 41 * notice, this list of conditions and the following disclaimer in the 42 * documentation and/or other materials provided with the distribution. 43 * 44 * THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR 45 * IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES 46 * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED. 47 * IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT, 48 * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT 49 * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, 50 * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY 51 * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT 52 * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF 53 * THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. 54 */ 55 56 #ifndef _SYS_TREE_H_ 57 #define _SYS_TREE_H_ 58 59 /* 60 * This file defines data structures for different types of trees: 61 * splay trees and red-black trees. 62 * 63 * A splay tree is a self-organizing data structure. Every operation 64 * on the tree causes a splay to happen. The splay moves the requested 65 * node to the root of the tree and partly rebalances it. 66 * 67 * This has the benefit that request locality causes faster lookups as 68 * the requested nodes move to the top of the tree. On the other hand, 69 * every lookup causes memory writes. 70 * 71 * The Balance Theorem bounds the total access time for m operations 72 * and n inserts on an initially empty tree as O((m + n)lg n). The 73 * amortized cost for a sequence of m accesses to a splay tree is O(lg n); 74 * 75 * A red-black tree is a binary search tree with the node color as an 76 * extra attribute. It fulfills a set of conditions: 77 * - every search path from the root to a leaf consists of the 78 * same number of black nodes, 79 * - each red node (except for the root) has a black parent, 80 * - each leaf node is black. 81 * 82 * Every operation on a red-black tree is bounded as O(lg n). 83 * The maximum height of a red-black tree is 2lg (n+1). 84 */ 85 86 #define SPLAY_HEAD(name, type) \ 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_ENTRY(type) \ 335 struct { \ 336 struct type *rbe_left; /* left element */ \ 337 struct type *rbe_right; /* right element */ \ 338 struct type *rbe_parent; /* parent element */ \ 339 int rbe_color; /* node color */ \ 340 } 341 342 #define RB_LEFT(elm, field) (elm)->field.rbe_left 343 #define RB_RIGHT(elm, field) (elm)->field.rbe_right 344 #define RB_PARENT(elm, field) (elm)->field.rbe_parent 345 #define RB_COLOR(elm, field) (elm)->field.rbe_color 346 #define RB_ROOT(head) (head)->rbh_root 347 #define RB_EMPTY(head) (RB_ROOT(head) == NULL) 348 349 #define RB_SET(elm, parent, field) do { \ 350 RB_PARENT(elm, field) = parent; \ 351 RB_LEFT(elm, field) = RB_RIGHT(elm, field) = NULL; \ 352 RB_COLOR(elm, field) = RB_RED; \ 353 } while (/*CONSTCOND*/ 0) 354 355 #define RB_SET_BLACKRED(black, red, field) do { \ 356 RB_COLOR(black, field) = RB_BLACK; \ 357 RB_COLOR(red, field) = RB_RED; \ 358 } while (/*CONSTCOND*/ 0) 359 360 #ifndef RB_AUGMENT 361 #define RB_AUGMENT(x) (void)(x) 362 #endif 363 364 #define RB_ROTATE_LEFT(head, elm, tmp, field) do { \ 365 (tmp) = RB_RIGHT(elm, field); \ 366 if ((RB_RIGHT(elm, field) = RB_LEFT(tmp, field)) != NULL) { \ 367 RB_PARENT(RB_LEFT(tmp, field), field) = (elm); \ 368 } \ 369 RB_AUGMENT(elm); \ 370 if ((RB_PARENT(tmp, field) = RB_PARENT(elm, field)) != NULL) { \ 371 if ((elm) == RB_LEFT(RB_PARENT(elm, field), field)) \ 372 RB_LEFT(RB_PARENT(elm, field), field) = (tmp); \ 373 else \ 374 RB_RIGHT(RB_PARENT(elm, field), field) = (tmp); \ 375 } else \ 376 (head)->rbh_root = (tmp); \ 377 RB_LEFT(tmp, field) = (elm); \ 378 RB_PARENT(elm, field) = (tmp); \ 379 RB_AUGMENT(tmp); \ 380 if ((RB_PARENT(tmp, field))) \ 381 RB_AUGMENT(RB_PARENT(tmp, field)); \ 382 } while (/*CONSTCOND*/ 0) 383 384 #define RB_ROTATE_RIGHT(head, elm, tmp, field) do { \ 385 (tmp) = RB_LEFT(elm, field); \ 386 if ((RB_LEFT(elm, field) = RB_RIGHT(tmp, field)) != NULL) { \ 387 RB_PARENT(RB_RIGHT(tmp, field), field) = (elm); \ 388 } \ 389 RB_AUGMENT(elm); \ 390 if ((RB_PARENT(tmp, field) = RB_PARENT(elm, field)) != NULL) { \ 391 if ((elm) == RB_LEFT(RB_PARENT(elm, field), field)) \ 392 RB_LEFT(RB_PARENT(elm, field), field) = (tmp); \ 393 else \ 394 RB_RIGHT(RB_PARENT(elm, field), field) = (tmp); \ 395 } else \ 396 (head)->rbh_root = (tmp); \ 397 RB_RIGHT(tmp, field) = (elm); \ 398 RB_PARENT(elm, field) = (tmp); \ 399 RB_AUGMENT(tmp); \ 400 if ((RB_PARENT(tmp, field))) \ 401 RB_AUGMENT(RB_PARENT(tmp, field)); \ 402 } while (/*CONSTCOND*/ 0) 403 404 /* Generates prototypes and inline functions */ 405 #define RB_PROTOTYPE(name, type, field, cmp) \ 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 414 /* Generates prototypes (with storage class) and inline functions */ 415 #define RB_PROTOTYPE_SC(_sc_, name, type, field, cmp) \ 416 _sc_ void name##_RB_INSERT_COLOR(struct name *, struct type *); \ 417 _sc_ void name##_RB_REMOVE_COLOR(struct name *, struct type *, struct type *); \ 418 _sc_ struct type *name##_RB_REMOVE(struct name *, struct type *); \ 419 _sc_ struct type *name##_RB_INSERT(struct name *, struct type *); \ 420 _sc_ struct type *name##_RB_FIND(struct name *, struct type *); \ 421 _sc_ struct type *name##_RB_NEXT(struct type *); \ 422 _sc_ struct type *name##_RB_MINMAX(struct name *, int); 423 424 /* Main rb operation. 425 * Moves node close to the key of elm to top 426 */ 427 #define RB_GENERATE(name, type, field, cmp) \ 428 void \ 429 name##_RB_INSERT_COLOR(struct name *head, struct type *elm) \ 430 { \ 431 struct type *parent, *gparent, *tmp; \ 432 while ((parent = RB_PARENT(elm, field)) != NULL && \ 433 RB_COLOR(parent, field) == RB_RED) { \ 434 gparent = RB_PARENT(parent, field); \ 435 if (parent == RB_LEFT(gparent, field)) { \ 436 tmp = RB_RIGHT(gparent, field); \ 437 if (tmp && RB_COLOR(tmp, field) == RB_RED) { \ 438 RB_COLOR(tmp, field) = RB_BLACK; \ 439 RB_SET_BLACKRED(parent, gparent, field);\ 440 elm = gparent; \ 441 continue; \ 442 } \ 443 if (RB_RIGHT(parent, field) == elm) { \ 444 RB_ROTATE_LEFT(head, parent, tmp, field);\ 445 tmp = parent; \ 446 parent = elm; \ 447 elm = tmp; \ 448 } \ 449 RB_SET_BLACKRED(parent, gparent, field); \ 450 RB_ROTATE_RIGHT(head, gparent, tmp, field); \ 451 } else { \ 452 tmp = RB_LEFT(gparent, field); \ 453 if (tmp && RB_COLOR(tmp, field) == RB_RED) { \ 454 RB_COLOR(tmp, field) = RB_BLACK; \ 455 RB_SET_BLACKRED(parent, gparent, field);\ 456 elm = gparent; \ 457 continue; \ 458 } \ 459 if (RB_LEFT(parent, field) == elm) { \ 460 RB_ROTATE_RIGHT(head, parent, tmp, field);\ 461 tmp = parent; \ 462 parent = elm; \ 463 elm = tmp; \ 464 } \ 465 RB_SET_BLACKRED(parent, gparent, field); \ 466 RB_ROTATE_LEFT(head, gparent, tmp, field); \ 467 } \ 468 } \ 469 RB_COLOR(head->rbh_root, field) = RB_BLACK; \ 470 } \ 471 \ 472 void \ 473 name##_RB_REMOVE_COLOR(struct name *head, struct type *parent, struct type *elm) \ 474 { \ 475 struct type *tmp; \ 476 while ((elm == NULL || RB_COLOR(elm, field) == RB_BLACK) && \ 477 elm != RB_ROOT(head)) { \ 478 if (RB_LEFT(parent, field) == elm) { \ 479 tmp = RB_RIGHT(parent, field); \ 480 if (RB_COLOR(tmp, field) == RB_RED) { \ 481 RB_SET_BLACKRED(tmp, parent, field); \ 482 RB_ROTATE_LEFT(head, parent, tmp, field);\ 483 tmp = RB_RIGHT(parent, field); \ 484 } \ 485 if ((RB_LEFT(tmp, field) == NULL || \ 486 RB_COLOR(RB_LEFT(tmp, field), field) == RB_BLACK) &&\ 487 (RB_RIGHT(tmp, field) == NULL || \ 488 RB_COLOR(RB_RIGHT(tmp, field), field) == RB_BLACK)) {\ 489 RB_COLOR(tmp, field) = RB_RED; \ 490 elm = parent; \ 491 parent = RB_PARENT(elm, field); \ 492 } else { \ 493 if (RB_RIGHT(tmp, field) == NULL || \ 494 RB_COLOR(RB_RIGHT(tmp, field), field) == RB_BLACK) {\ 495 struct type *oleft; \ 496 if ((oleft = RB_LEFT(tmp, field)) \ 497 != NULL) \ 498 RB_COLOR(oleft, field) = RB_BLACK;\ 499 RB_COLOR(tmp, field) = RB_RED; \ 500 RB_ROTATE_RIGHT(head, tmp, oleft, field);\ 501 tmp = RB_RIGHT(parent, field); \ 502 } \ 503 RB_COLOR(tmp, field) = RB_COLOR(parent, field);\ 504 RB_COLOR(parent, field) = RB_BLACK; \ 505 if (RB_RIGHT(tmp, field)) \ 506 RB_COLOR(RB_RIGHT(tmp, field), field) = RB_BLACK;\ 507 RB_ROTATE_LEFT(head, parent, tmp, field);\ 508 elm = RB_ROOT(head); \ 509 break; \ 510 } \ 511 } else { \ 512 tmp = RB_LEFT(parent, field); \ 513 if (RB_COLOR(tmp, field) == RB_RED) { \ 514 RB_SET_BLACKRED(tmp, parent, field); \ 515 RB_ROTATE_RIGHT(head, parent, tmp, field);\ 516 tmp = RB_LEFT(parent, field); \ 517 } \ 518 if ((RB_LEFT(tmp, field) == NULL || \ 519 RB_COLOR(RB_LEFT(tmp, field), field) == RB_BLACK) &&\ 520 (RB_RIGHT(tmp, field) == NULL || \ 521 RB_COLOR(RB_RIGHT(tmp, field), field) == RB_BLACK)) {\ 522 RB_COLOR(tmp, field) = RB_RED; \ 523 elm = parent; \ 524 parent = RB_PARENT(elm, field); \ 525 } else { \ 526 if (RB_LEFT(tmp, field) == NULL || \ 527 RB_COLOR(RB_LEFT(tmp, field), field) == RB_BLACK) {\ 528 struct type *oright; \ 529 if ((oright = RB_RIGHT(tmp, field)) \ 530 != NULL) \ 531 RB_COLOR(oright, field) = RB_BLACK;\ 532 RB_COLOR(tmp, field) = RB_RED; \ 533 RB_ROTATE_LEFT(head, tmp, oright, field);\ 534 tmp = RB_LEFT(parent, field); \ 535 } \ 536 RB_COLOR(tmp, field) = RB_COLOR(parent, field);\ 537 RB_COLOR(parent, field) = RB_BLACK; \ 538 if (RB_LEFT(tmp, field)) \ 539 RB_COLOR(RB_LEFT(tmp, field), field) = RB_BLACK;\ 540 RB_ROTATE_RIGHT(head, parent, tmp, field);\ 541 elm = RB_ROOT(head); \ 542 break; \ 543 } \ 544 } \ 545 } \ 546 if (elm) \ 547 RB_COLOR(elm, field) = RB_BLACK; \ 548 } \ 549 \ 550 struct type * \ 551 name##_RB_REMOVE(struct name *head, struct type *elm) \ 552 { \ 553 struct type *child, *parent, *old = elm; \ 554 int color; \ 555 if (RB_LEFT(elm, field) == NULL) \ 556 child = RB_RIGHT(elm, field); \ 557 else if (RB_RIGHT(elm, field) == NULL) \ 558 child = RB_LEFT(elm, field); \ 559 else { \ 560 struct type *left; \ 561 elm = RB_RIGHT(elm, field); \ 562 while ((left = RB_LEFT(elm, field)) != NULL) \ 563 elm = left; \ 564 child = RB_RIGHT(elm, field); \ 565 parent = RB_PARENT(elm, field); \ 566 color = RB_COLOR(elm, field); \ 567 if (child) \ 568 RB_PARENT(child, field) = parent; \ 569 if (parent) { \ 570 if (RB_LEFT(parent, field) == elm) \ 571 RB_LEFT(parent, field) = child; \ 572 else \ 573 RB_RIGHT(parent, field) = child; \ 574 RB_AUGMENT(parent); \ 575 } else \ 576 RB_ROOT(head) = child; \ 577 if (RB_PARENT(elm, field) == old) \ 578 parent = elm; \ 579 (elm)->field = (old)->field; \ 580 if (RB_PARENT(old, field)) { \ 581 if (RB_LEFT(RB_PARENT(old, field), field) == old)\ 582 RB_LEFT(RB_PARENT(old, field), field) = elm;\ 583 else \ 584 RB_RIGHT(RB_PARENT(old, field), field) = elm;\ 585 RB_AUGMENT(RB_PARENT(old, field)); \ 586 } else \ 587 RB_ROOT(head) = elm; \ 588 RB_PARENT(RB_LEFT(old, field), field) = elm; \ 589 if (RB_RIGHT(old, field)) \ 590 RB_PARENT(RB_RIGHT(old, field), field) = elm; \ 591 if (parent) { \ 592 left = parent; \ 593 do { \ 594 RB_AUGMENT(left); \ 595 } while ((left = RB_PARENT(left, field)) != NULL); \ 596 } \ 597 goto color; \ 598 } \ 599 parent = RB_PARENT(elm, field); \ 600 color = RB_COLOR(elm, field); \ 601 if (child) \ 602 RB_PARENT(child, field) = parent; \ 603 if (parent) { \ 604 if (RB_LEFT(parent, field) == elm) \ 605 RB_LEFT(parent, field) = child; \ 606 else \ 607 RB_RIGHT(parent, field) = child; \ 608 RB_AUGMENT(parent); \ 609 } else \ 610 RB_ROOT(head) = child; \ 611 color: \ 612 if (color == RB_BLACK) \ 613 name##_RB_REMOVE_COLOR(head, parent, child); \ 614 return (old); \ 615 } \ 616 \ 617 /* Inserts a node into the RB tree */ \ 618 struct type * \ 619 name##_RB_INSERT(struct name *head, struct type *elm) \ 620 { \ 621 struct type *tmp; \ 622 struct type *parent = NULL; \ 623 int comp = 0; \ 624 tmp = RB_ROOT(head); \ 625 while (tmp) { \ 626 parent = tmp; \ 627 comp = (cmp)(elm, parent); \ 628 if (comp < 0) \ 629 tmp = RB_LEFT(tmp, field); \ 630 else if (comp > 0) \ 631 tmp = RB_RIGHT(tmp, field); \ 632 else \ 633 return (tmp); \ 634 } \ 635 RB_SET(elm, parent, field); \ 636 if (parent != NULL) { \ 637 if (comp < 0) \ 638 RB_LEFT(parent, field) = elm; \ 639 else \ 640 RB_RIGHT(parent, field) = elm; \ 641 RB_AUGMENT(parent); \ 642 } else \ 643 RB_ROOT(head) = elm; \ 644 name##_RB_INSERT_COLOR(head, elm); \ 645 return (NULL); \ 646 } \ 647 \ 648 /* Finds the node with the same key as elm */ \ 649 struct type * \ 650 name##_RB_FIND(struct name *head, struct type *elm) \ 651 { \ 652 struct type *tmp = RB_ROOT(head); \ 653 int comp; \ 654 while (tmp) { \ 655 comp = cmp(elm, tmp); \ 656 if (comp < 0) \ 657 tmp = RB_LEFT(tmp, field); \ 658 else if (comp > 0) \ 659 tmp = RB_RIGHT(tmp, field); \ 660 else \ 661 return (tmp); \ 662 } \ 663 return (NULL); \ 664 } \ 665 \ 666 /* ARGSUSED */ \ 667 struct type * \ 668 name##_RB_NEXT(struct type *elm) \ 669 { \ 670 if (RB_RIGHT(elm, field)) { \ 671 elm = RB_RIGHT(elm, field); \ 672 while (RB_LEFT(elm, field)) \ 673 elm = RB_LEFT(elm, field); \ 674 } else { \ 675 if (RB_PARENT(elm, field) && \ 676 (elm == RB_LEFT(RB_PARENT(elm, field), field))) \ 677 elm = RB_PARENT(elm, field); \ 678 else { \ 679 while (RB_PARENT(elm, field) && \ 680 (elm == RB_RIGHT(RB_PARENT(elm, field), field)))\ 681 elm = RB_PARENT(elm, field); \ 682 elm = RB_PARENT(elm, field); \ 683 } \ 684 } \ 685 return (elm); \ 686 } \ 687 \ 688 struct type * \ 689 name##_RB_MINMAX(struct name *head, int val) \ 690 { \ 691 struct type *tmp = RB_ROOT(head); \ 692 struct type *parent = NULL; \ 693 while (tmp) { \ 694 parent = tmp; \ 695 if (val < 0) \ 696 tmp = RB_LEFT(tmp, field); \ 697 else \ 698 tmp = RB_RIGHT(tmp, field); \ 699 } \ 700 return (parent); \ 701 } 702 703 #define RB_NEGINF -1 704 #define RB_INF 1 705 706 #define RB_INSERT(name, x, y) name##_RB_INSERT(x, y) 707 #define RB_REMOVE(name, x, y) name##_RB_REMOVE(x, y) 708 #define RB_FIND(name, x, y) name##_RB_FIND(x, y) 709 #define RB_NEXT(name, x, y) name##_RB_NEXT(y) 710 #define RB_MIN(name, x) name##_RB_MINMAX(x, RB_NEGINF) 711 #define RB_MAX(name, x) name##_RB_MINMAX(x, RB_INF) 712 713 #define RB_FOREACH(x, name, head) \ 714 for ((x) = RB_MIN(name, head); \ 715 (x) != NULL; \ 716 (x) = name##_RB_NEXT(x)) 717 718 #endif /* _SYS_TREE_H_ */ 719