1 /* $NetBSD: tree.h,v 1.8 2004/03/28 19:38:30 provos Exp $ */ 2 /* $OpenBSD: tree.h,v 1.7 2002/10/17 21:51:54 art Exp $ */ 3 /* $FreeBSD$ */ 4 5 /*- 6 * Copyright 2002 Niels Provos <provos@citi.umich.edu> 7 * All rights reserved. 8 * 9 * Redistribution and use in source and binary forms, with or without 10 * modification, are permitted provided that the following conditions 11 * are met: 12 * 1. Redistributions of source code must retain the above copyright 13 * notice, this list of conditions and the following disclaimer. 14 * 2. Redistributions in binary form must reproduce the above copyright 15 * notice, this list of conditions and the following disclaimer in the 16 * documentation and/or other materials provided with the distribution. 17 * 18 * THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR 19 * IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES 20 * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED. 21 * IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT, 22 * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT 23 * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, 24 * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY 25 * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT 26 * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF 27 * THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. 28 */ 29 30 #ifndef _SYS_TREE_H_ 31 #define _SYS_TREE_H_ 32 33 #include <sys/cdefs.h> 34 35 /* 36 * This file defines data structures for different types of trees: 37 * splay trees and red-black trees. 38 * 39 * A splay tree is a self-organizing data structure. Every operation 40 * on the tree causes a splay to happen. The splay moves the requested 41 * node to the root of the tree and partly rebalances it. 42 * 43 * This has the benefit that request locality causes faster lookups as 44 * the requested nodes move to the top of the tree. On the other hand, 45 * every lookup causes memory writes. 46 * 47 * The Balance Theorem bounds the total access time for m operations 48 * and n inserts on an initially empty tree as O((m + n)lg n). The 49 * amortized cost for a sequence of m accesses to a splay tree is O(lg n); 50 * 51 * A red-black tree is a binary search tree with the node color as an 52 * extra attribute. It fulfills a set of conditions: 53 * - every search path from the root to a leaf consists of the 54 * same number of black nodes, 55 * - each red node (except for the root) has a black parent, 56 * - each leaf node is black. 57 * 58 * Every operation on a red-black tree is bounded as O(lg n). 59 * The maximum height of a red-black tree is 2lg (n+1). 60 */ 61 62 #define SPLAY_HEAD(name, type) \ 63 struct name { \ 64 struct type *sph_root; /* root of the tree */ \ 65 } 66 67 #define SPLAY_INITIALIZER(root) \ 68 { NULL } 69 70 #define SPLAY_INIT(root) do { \ 71 (root)->sph_root = NULL; \ 72 } while (/*CONSTCOND*/ 0) 73 74 #define SPLAY_ENTRY(type) \ 75 struct { \ 76 struct type *spe_left; /* left element */ \ 77 struct type *spe_right; /* right element */ \ 78 } 79 80 #define SPLAY_LEFT(elm, field) (elm)->field.spe_left 81 #define SPLAY_RIGHT(elm, field) (elm)->field.spe_right 82 #define SPLAY_ROOT(head) (head)->sph_root 83 #define SPLAY_EMPTY(head) (SPLAY_ROOT(head) == NULL) 84 85 /* SPLAY_ROTATE_{LEFT,RIGHT} expect that tmp hold SPLAY_{RIGHT,LEFT} */ 86 #define SPLAY_ROTATE_RIGHT(head, tmp, field) do { \ 87 SPLAY_LEFT((head)->sph_root, field) = SPLAY_RIGHT(tmp, field); \ 88 SPLAY_RIGHT(tmp, field) = (head)->sph_root; \ 89 (head)->sph_root = tmp; \ 90 } while (/*CONSTCOND*/ 0) 91 92 #define SPLAY_ROTATE_LEFT(head, tmp, field) do { \ 93 SPLAY_RIGHT((head)->sph_root, field) = SPLAY_LEFT(tmp, field); \ 94 SPLAY_LEFT(tmp, field) = (head)->sph_root; \ 95 (head)->sph_root = tmp; \ 96 } while (/*CONSTCOND*/ 0) 97 98 #define SPLAY_LINKLEFT(head, tmp, field) do { \ 99 SPLAY_LEFT(tmp, field) = (head)->sph_root; \ 100 tmp = (head)->sph_root; \ 101 (head)->sph_root = SPLAY_LEFT((head)->sph_root, field); \ 102 } while (/*CONSTCOND*/ 0) 103 104 #define SPLAY_LINKRIGHT(head, tmp, field) do { \ 105 SPLAY_RIGHT(tmp, field) = (head)->sph_root; \ 106 tmp = (head)->sph_root; \ 107 (head)->sph_root = SPLAY_RIGHT((head)->sph_root, field); \ 108 } while (/*CONSTCOND*/ 0) 109 110 #define SPLAY_ASSEMBLE(head, node, left, right, field) do { \ 111 SPLAY_RIGHT(left, field) = SPLAY_LEFT((head)->sph_root, field); \ 112 SPLAY_LEFT(right, field) = SPLAY_RIGHT((head)->sph_root, field);\ 113 SPLAY_LEFT((head)->sph_root, field) = SPLAY_RIGHT(node, field); \ 114 SPLAY_RIGHT((head)->sph_root, field) = SPLAY_LEFT(node, field); \ 115 } while (/*CONSTCOND*/ 0) 116 117 /* Generates prototypes and inline functions */ 118 119 #define SPLAY_PROTOTYPE(name, type, field, cmp) \ 120 void name##_SPLAY(struct name *, struct type *); \ 121 void name##_SPLAY_MINMAX(struct name *, int); \ 122 struct type *name##_SPLAY_INSERT(struct name *, struct type *); \ 123 struct type *name##_SPLAY_REMOVE(struct name *, struct type *); \ 124 \ 125 /* Finds the node with the same key as elm */ \ 126 static __inline struct type * \ 127 name##_SPLAY_FIND(struct name *head, struct type *elm) \ 128 { \ 129 if (SPLAY_EMPTY(head)) \ 130 return(NULL); \ 131 name##_SPLAY(head, elm); \ 132 if ((cmp)(elm, (head)->sph_root) == 0) \ 133 return (head->sph_root); \ 134 return (NULL); \ 135 } \ 136 \ 137 static __inline struct type * \ 138 name##_SPLAY_NEXT(struct name *head, struct type *elm) \ 139 { \ 140 name##_SPLAY(head, elm); \ 141 if (SPLAY_RIGHT(elm, field) != NULL) { \ 142 elm = SPLAY_RIGHT(elm, field); \ 143 while (SPLAY_LEFT(elm, field) != NULL) { \ 144 elm = SPLAY_LEFT(elm, field); \ 145 } \ 146 } else \ 147 elm = NULL; \ 148 return (elm); \ 149 } \ 150 \ 151 static __inline struct type * \ 152 name##_SPLAY_MIN_MAX(struct name *head, int val) \ 153 { \ 154 name##_SPLAY_MINMAX(head, val); \ 155 return (SPLAY_ROOT(head)); \ 156 } 157 158 /* Main splay operation. 159 * Moves node close to the key of elm to top 160 */ 161 #define SPLAY_GENERATE(name, type, field, cmp) \ 162 struct type * \ 163 name##_SPLAY_INSERT(struct name *head, struct type *elm) \ 164 { \ 165 if (SPLAY_EMPTY(head)) { \ 166 SPLAY_LEFT(elm, field) = SPLAY_RIGHT(elm, field) = NULL; \ 167 } else { \ 168 int __comp; \ 169 name##_SPLAY(head, elm); \ 170 __comp = (cmp)(elm, (head)->sph_root); \ 171 if(__comp < 0) { \ 172 SPLAY_LEFT(elm, field) = SPLAY_LEFT((head)->sph_root, field);\ 173 SPLAY_RIGHT(elm, field) = (head)->sph_root; \ 174 SPLAY_LEFT((head)->sph_root, field) = NULL; \ 175 } else if (__comp > 0) { \ 176 SPLAY_RIGHT(elm, field) = SPLAY_RIGHT((head)->sph_root, field);\ 177 SPLAY_LEFT(elm, field) = (head)->sph_root; \ 178 SPLAY_RIGHT((head)->sph_root, field) = NULL; \ 179 } else \ 180 return ((head)->sph_root); \ 181 } \ 182 (head)->sph_root = (elm); \ 183 return (NULL); \ 184 } \ 185 \ 186 struct type * \ 187 name##_SPLAY_REMOVE(struct name *head, struct type *elm) \ 188 { \ 189 struct type *__tmp; \ 190 if (SPLAY_EMPTY(head)) \ 191 return (NULL); \ 192 name##_SPLAY(head, elm); \ 193 if ((cmp)(elm, (head)->sph_root) == 0) { \ 194 if (SPLAY_LEFT((head)->sph_root, field) == NULL) { \ 195 (head)->sph_root = SPLAY_RIGHT((head)->sph_root, field);\ 196 } else { \ 197 __tmp = SPLAY_RIGHT((head)->sph_root, field); \ 198 (head)->sph_root = SPLAY_LEFT((head)->sph_root, field);\ 199 name##_SPLAY(head, elm); \ 200 SPLAY_RIGHT((head)->sph_root, field) = __tmp; \ 201 } \ 202 return (elm); \ 203 } \ 204 return (NULL); \ 205 } \ 206 \ 207 void \ 208 name##_SPLAY(struct name *head, struct type *elm) \ 209 { \ 210 struct type __node, *__left, *__right, *__tmp; \ 211 int __comp; \ 212 \ 213 SPLAY_LEFT(&__node, field) = SPLAY_RIGHT(&__node, field) = NULL;\ 214 __left = __right = &__node; \ 215 \ 216 while ((__comp = (cmp)(elm, (head)->sph_root)) != 0) { \ 217 if (__comp < 0) { \ 218 __tmp = SPLAY_LEFT((head)->sph_root, field); \ 219 if (__tmp == NULL) \ 220 break; \ 221 if ((cmp)(elm, __tmp) < 0){ \ 222 SPLAY_ROTATE_RIGHT(head, __tmp, field); \ 223 if (SPLAY_LEFT((head)->sph_root, field) == NULL)\ 224 break; \ 225 } \ 226 SPLAY_LINKLEFT(head, __right, field); \ 227 } else if (__comp > 0) { \ 228 __tmp = SPLAY_RIGHT((head)->sph_root, field); \ 229 if (__tmp == NULL) \ 230 break; \ 231 if ((cmp)(elm, __tmp) > 0){ \ 232 SPLAY_ROTATE_LEFT(head, __tmp, field); \ 233 if (SPLAY_RIGHT((head)->sph_root, field) == NULL)\ 234 break; \ 235 } \ 236 SPLAY_LINKRIGHT(head, __left, field); \ 237 } \ 238 } \ 239 SPLAY_ASSEMBLE(head, &__node, __left, __right, field); \ 240 } \ 241 \ 242 /* Splay with either the minimum or the maximum element \ 243 * Used to find minimum or maximum element in tree. \ 244 */ \ 245 void name##_SPLAY_MINMAX(struct name *head, int __comp) \ 246 { \ 247 struct type __node, *__left, *__right, *__tmp; \ 248 \ 249 SPLAY_LEFT(&__node, field) = SPLAY_RIGHT(&__node, field) = NULL;\ 250 __left = __right = &__node; \ 251 \ 252 while (1) { \ 253 if (__comp < 0) { \ 254 __tmp = SPLAY_LEFT((head)->sph_root, field); \ 255 if (__tmp == NULL) \ 256 break; \ 257 if (__comp < 0){ \ 258 SPLAY_ROTATE_RIGHT(head, __tmp, field); \ 259 if (SPLAY_LEFT((head)->sph_root, field) == NULL)\ 260 break; \ 261 } \ 262 SPLAY_LINKLEFT(head, __right, field); \ 263 } else if (__comp > 0) { \ 264 __tmp = SPLAY_RIGHT((head)->sph_root, field); \ 265 if (__tmp == NULL) \ 266 break; \ 267 if (__comp > 0) { \ 268 SPLAY_ROTATE_LEFT(head, __tmp, field); \ 269 if (SPLAY_RIGHT((head)->sph_root, field) == NULL)\ 270 break; \ 271 } \ 272 SPLAY_LINKRIGHT(head, __left, field); \ 273 } \ 274 } \ 275 SPLAY_ASSEMBLE(head, &__node, __left, __right, field); \ 276 } 277 278 #define SPLAY_NEGINF -1 279 #define SPLAY_INF 1 280 281 #define SPLAY_INSERT(name, x, y) name##_SPLAY_INSERT(x, y) 282 #define SPLAY_REMOVE(name, x, y) name##_SPLAY_REMOVE(x, y) 283 #define SPLAY_FIND(name, x, y) name##_SPLAY_FIND(x, y) 284 #define SPLAY_NEXT(name, x, y) name##_SPLAY_NEXT(x, y) 285 #define SPLAY_MIN(name, x) (SPLAY_EMPTY(x) ? NULL \ 286 : name##_SPLAY_MIN_MAX(x, SPLAY_NEGINF)) 287 #define SPLAY_MAX(name, x) (SPLAY_EMPTY(x) ? NULL \ 288 : name##_SPLAY_MIN_MAX(x, SPLAY_INF)) 289 290 #define SPLAY_FOREACH(x, name, head) \ 291 for ((x) = SPLAY_MIN(name, head); \ 292 (x) != NULL; \ 293 (x) = SPLAY_NEXT(name, head, x)) 294 295 /* Macros that define a red-black tree */ 296 #define RB_HEAD(name, type) \ 297 struct name { \ 298 struct type *rbh_root; /* root of the tree */ \ 299 } 300 301 #define RB_INITIALIZER(root) \ 302 { NULL } 303 304 #define RB_INIT(root) do { \ 305 (root)->rbh_root = NULL; \ 306 } while (/*CONSTCOND*/ 0) 307 308 #define RB_BLACK 0 309 #define RB_RED 1 310 #define RB_ENTRY(type) \ 311 struct { \ 312 struct type *rbe_left; /* left element */ \ 313 struct type *rbe_right; /* right element */ \ 314 struct type *rbe_parent; /* parent element */ \ 315 int rbe_color; /* node color */ \ 316 } 317 318 #define RB_LEFT(elm, field) (elm)->field.rbe_left 319 #define RB_RIGHT(elm, field) (elm)->field.rbe_right 320 #define RB_PARENT(elm, field) (elm)->field.rbe_parent 321 #define RB_COLOR(elm, field) (elm)->field.rbe_color 322 #define RB_ROOT(head) (head)->rbh_root 323 #define RB_EMPTY(head) (RB_ROOT(head) == NULL) 324 325 #define RB_SET(elm, parent, field) do { \ 326 RB_PARENT(elm, field) = parent; \ 327 RB_LEFT(elm, field) = RB_RIGHT(elm, field) = NULL; \ 328 RB_COLOR(elm, field) = RB_RED; \ 329 } while (/*CONSTCOND*/ 0) 330 331 #define RB_SET_BLACKRED(black, red, field) do { \ 332 RB_COLOR(black, field) = RB_BLACK; \ 333 RB_COLOR(red, field) = RB_RED; \ 334 } while (/*CONSTCOND*/ 0) 335 336 #ifndef RB_AUGMENT 337 #define RB_AUGMENT(x) do {} while (0) 338 #endif 339 340 #define RB_ROTATE_LEFT(head, elm, tmp, field) do { \ 341 (tmp) = RB_RIGHT(elm, field); \ 342 if ((RB_RIGHT(elm, field) = RB_LEFT(tmp, field)) != NULL) { \ 343 RB_PARENT(RB_LEFT(tmp, field), field) = (elm); \ 344 } \ 345 RB_AUGMENT(elm); \ 346 if ((RB_PARENT(tmp, field) = RB_PARENT(elm, field)) != NULL) { \ 347 if ((elm) == RB_LEFT(RB_PARENT(elm, field), field)) \ 348 RB_LEFT(RB_PARENT(elm, field), field) = (tmp); \ 349 else \ 350 RB_RIGHT(RB_PARENT(elm, field), field) = (tmp); \ 351 } else \ 352 (head)->rbh_root = (tmp); \ 353 RB_LEFT(tmp, field) = (elm); \ 354 RB_PARENT(elm, field) = (tmp); \ 355 RB_AUGMENT(tmp); \ 356 if ((RB_PARENT(tmp, field))) \ 357 RB_AUGMENT(RB_PARENT(tmp, field)); \ 358 } while (/*CONSTCOND*/ 0) 359 360 #define RB_ROTATE_RIGHT(head, elm, tmp, field) do { \ 361 (tmp) = RB_LEFT(elm, field); \ 362 if ((RB_LEFT(elm, field) = RB_RIGHT(tmp, field)) != NULL) { \ 363 RB_PARENT(RB_RIGHT(tmp, field), field) = (elm); \ 364 } \ 365 RB_AUGMENT(elm); \ 366 if ((RB_PARENT(tmp, field) = RB_PARENT(elm, field)) != NULL) { \ 367 if ((elm) == RB_LEFT(RB_PARENT(elm, field), field)) \ 368 RB_LEFT(RB_PARENT(elm, field), field) = (tmp); \ 369 else \ 370 RB_RIGHT(RB_PARENT(elm, field), field) = (tmp); \ 371 } else \ 372 (head)->rbh_root = (tmp); \ 373 RB_RIGHT(tmp, field) = (elm); \ 374 RB_PARENT(elm, field) = (tmp); \ 375 RB_AUGMENT(tmp); \ 376 if ((RB_PARENT(tmp, field))) \ 377 RB_AUGMENT(RB_PARENT(tmp, field)); \ 378 } while (/*CONSTCOND*/ 0) 379 380 /* Generates prototypes and inline functions */ 381 #define RB_PROTOTYPE(name, type, field, cmp) \ 382 RB_PROTOTYPE_INTERNAL(name, type, field, cmp,) 383 #define RB_PROTOTYPE_STATIC(name, type, field, cmp) \ 384 RB_PROTOTYPE_INTERNAL(name, type, field, cmp, __unused static) 385 #define RB_PROTOTYPE_INTERNAL(name, type, field, cmp, attr) \ 386 attr void name##_RB_INSERT_COLOR(struct name *, struct type *); \ 387 attr void name##_RB_REMOVE_COLOR(struct name *, struct type *, struct type *);\ 388 attr struct type *name##_RB_REMOVE(struct name *, struct type *); \ 389 attr struct type *name##_RB_INSERT(struct name *, struct type *); \ 390 attr struct type *name##_RB_FIND(struct name *, struct type *); \ 391 attr struct type *name##_RB_NFIND(struct name *, struct type *); \ 392 attr struct type *name##_RB_NEXT(struct type *); \ 393 attr struct type *name##_RB_MINMAX(struct name *, int); \ 394 \ 395 396 /* Main rb operation. 397 * Moves node close to the key of elm to top 398 */ 399 #define RB_GENERATE(name, type, field, cmp) \ 400 RB_GENERATE_INTERNAL(name, type, field, cmp,) 401 #define RB_GENERATE_STATIC(name, type, field, cmp) \ 402 RB_GENERATE_INTERNAL(name, type, field, cmp, __unused static) 403 #define RB_GENERATE_INTERNAL(name, type, field, cmp, attr) \ 404 attr void \ 405 name##_RB_INSERT_COLOR(struct name *head, struct type *elm) \ 406 { \ 407 struct type *parent, *gparent, *tmp; \ 408 while ((parent = RB_PARENT(elm, field)) != NULL && \ 409 RB_COLOR(parent, field) == RB_RED) { \ 410 gparent = RB_PARENT(parent, field); \ 411 if (parent == RB_LEFT(gparent, field)) { \ 412 tmp = RB_RIGHT(gparent, field); \ 413 if (tmp && RB_COLOR(tmp, field) == RB_RED) { \ 414 RB_COLOR(tmp, field) = RB_BLACK; \ 415 RB_SET_BLACKRED(parent, gparent, field);\ 416 elm = gparent; \ 417 continue; \ 418 } \ 419 if (RB_RIGHT(parent, field) == elm) { \ 420 RB_ROTATE_LEFT(head, parent, tmp, field);\ 421 tmp = parent; \ 422 parent = elm; \ 423 elm = tmp; \ 424 } \ 425 RB_SET_BLACKRED(parent, gparent, field); \ 426 RB_ROTATE_RIGHT(head, gparent, tmp, field); \ 427 } else { \ 428 tmp = RB_LEFT(gparent, field); \ 429 if (tmp && RB_COLOR(tmp, field) == RB_RED) { \ 430 RB_COLOR(tmp, field) = RB_BLACK; \ 431 RB_SET_BLACKRED(parent, gparent, field);\ 432 elm = gparent; \ 433 continue; \ 434 } \ 435 if (RB_LEFT(parent, field) == elm) { \ 436 RB_ROTATE_RIGHT(head, parent, tmp, field);\ 437 tmp = parent; \ 438 parent = elm; \ 439 elm = tmp; \ 440 } \ 441 RB_SET_BLACKRED(parent, gparent, field); \ 442 RB_ROTATE_LEFT(head, gparent, tmp, field); \ 443 } \ 444 } \ 445 RB_COLOR(head->rbh_root, field) = RB_BLACK; \ 446 } \ 447 \ 448 attr void \ 449 name##_RB_REMOVE_COLOR(struct name *head, struct type *parent, struct type *elm) \ 450 { \ 451 struct type *tmp; \ 452 while ((elm == NULL || RB_COLOR(elm, field) == RB_BLACK) && \ 453 elm != RB_ROOT(head)) { \ 454 if (RB_LEFT(parent, field) == elm) { \ 455 tmp = RB_RIGHT(parent, field); \ 456 if (RB_COLOR(tmp, field) == RB_RED) { \ 457 RB_SET_BLACKRED(tmp, parent, field); \ 458 RB_ROTATE_LEFT(head, parent, tmp, field);\ 459 tmp = RB_RIGHT(parent, field); \ 460 } \ 461 if ((RB_LEFT(tmp, field) == NULL || \ 462 RB_COLOR(RB_LEFT(tmp, field), field) == RB_BLACK) &&\ 463 (RB_RIGHT(tmp, field) == NULL || \ 464 RB_COLOR(RB_RIGHT(tmp, field), field) == RB_BLACK)) {\ 465 RB_COLOR(tmp, field) = RB_RED; \ 466 elm = parent; \ 467 parent = RB_PARENT(elm, field); \ 468 } else { \ 469 if (RB_RIGHT(tmp, field) == NULL || \ 470 RB_COLOR(RB_RIGHT(tmp, field), field) == RB_BLACK) {\ 471 struct type *oleft; \ 472 if ((oleft = RB_LEFT(tmp, field)) \ 473 != NULL) \ 474 RB_COLOR(oleft, field) = RB_BLACK;\ 475 RB_COLOR(tmp, field) = RB_RED; \ 476 RB_ROTATE_RIGHT(head, tmp, oleft, field);\ 477 tmp = RB_RIGHT(parent, field); \ 478 } \ 479 RB_COLOR(tmp, field) = RB_COLOR(parent, field);\ 480 RB_COLOR(parent, field) = RB_BLACK; \ 481 if (RB_RIGHT(tmp, field)) \ 482 RB_COLOR(RB_RIGHT(tmp, field), field) = RB_BLACK;\ 483 RB_ROTATE_LEFT(head, parent, tmp, field);\ 484 elm = RB_ROOT(head); \ 485 break; \ 486 } \ 487 } else { \ 488 tmp = RB_LEFT(parent, field); \ 489 if (RB_COLOR(tmp, field) == RB_RED) { \ 490 RB_SET_BLACKRED(tmp, parent, field); \ 491 RB_ROTATE_RIGHT(head, parent, tmp, field);\ 492 tmp = RB_LEFT(parent, field); \ 493 } \ 494 if ((RB_LEFT(tmp, field) == NULL || \ 495 RB_COLOR(RB_LEFT(tmp, field), field) == RB_BLACK) &&\ 496 (RB_RIGHT(tmp, field) == NULL || \ 497 RB_COLOR(RB_RIGHT(tmp, field), field) == RB_BLACK)) {\ 498 RB_COLOR(tmp, field) = RB_RED; \ 499 elm = parent; \ 500 parent = RB_PARENT(elm, field); \ 501 } else { \ 502 if (RB_LEFT(tmp, field) == NULL || \ 503 RB_COLOR(RB_LEFT(tmp, field), field) == RB_BLACK) {\ 504 struct type *oright; \ 505 if ((oright = RB_RIGHT(tmp, field)) \ 506 != NULL) \ 507 RB_COLOR(oright, field) = RB_BLACK;\ 508 RB_COLOR(tmp, field) = RB_RED; \ 509 RB_ROTATE_LEFT(head, tmp, oright, field);\ 510 tmp = RB_LEFT(parent, field); \ 511 } \ 512 RB_COLOR(tmp, field) = RB_COLOR(parent, field);\ 513 RB_COLOR(parent, field) = RB_BLACK; \ 514 if (RB_LEFT(tmp, field)) \ 515 RB_COLOR(RB_LEFT(tmp, field), field) = RB_BLACK;\ 516 RB_ROTATE_RIGHT(head, parent, tmp, field);\ 517 elm = RB_ROOT(head); \ 518 break; \ 519 } \ 520 } \ 521 } \ 522 if (elm) \ 523 RB_COLOR(elm, field) = RB_BLACK; \ 524 } \ 525 \ 526 attr struct type * \ 527 name##_RB_REMOVE(struct name *head, struct type *elm) \ 528 { \ 529 struct type *child, *parent, *old = elm; \ 530 int color; \ 531 if (RB_LEFT(elm, field) == NULL) \ 532 child = RB_RIGHT(elm, field); \ 533 else if (RB_RIGHT(elm, field) == NULL) \ 534 child = RB_LEFT(elm, field); \ 535 else { \ 536 struct type *left; \ 537 elm = RB_RIGHT(elm, field); \ 538 while ((left = RB_LEFT(elm, field)) != NULL) \ 539 elm = left; \ 540 child = RB_RIGHT(elm, field); \ 541 parent = RB_PARENT(elm, field); \ 542 color = RB_COLOR(elm, field); \ 543 if (child) \ 544 RB_PARENT(child, field) = parent; \ 545 if (parent) { \ 546 if (RB_LEFT(parent, field) == elm) \ 547 RB_LEFT(parent, field) = child; \ 548 else \ 549 RB_RIGHT(parent, field) = child; \ 550 RB_AUGMENT(parent); \ 551 } else \ 552 RB_ROOT(head) = child; \ 553 if (RB_PARENT(elm, field) == old) \ 554 parent = elm; \ 555 (elm)->field = (old)->field; \ 556 if (RB_PARENT(old, field)) { \ 557 if (RB_LEFT(RB_PARENT(old, field), field) == old)\ 558 RB_LEFT(RB_PARENT(old, field), field) = elm;\ 559 else \ 560 RB_RIGHT(RB_PARENT(old, field), field) = elm;\ 561 RB_AUGMENT(RB_PARENT(old, field)); \ 562 } else \ 563 RB_ROOT(head) = elm; \ 564 RB_PARENT(RB_LEFT(old, field), field) = elm; \ 565 if (RB_RIGHT(old, field)) \ 566 RB_PARENT(RB_RIGHT(old, field), field) = elm; \ 567 if (parent) { \ 568 left = parent; \ 569 do { \ 570 RB_AUGMENT(left); \ 571 } while ((left = RB_PARENT(left, field)) != NULL); \ 572 } \ 573 goto color; \ 574 } \ 575 parent = RB_PARENT(elm, field); \ 576 color = RB_COLOR(elm, field); \ 577 if (child) \ 578 RB_PARENT(child, field) = parent; \ 579 if (parent) { \ 580 if (RB_LEFT(parent, field) == elm) \ 581 RB_LEFT(parent, field) = child; \ 582 else \ 583 RB_RIGHT(parent, field) = child; \ 584 RB_AUGMENT(parent); \ 585 } else \ 586 RB_ROOT(head) = child; \ 587 color: \ 588 if (color == RB_BLACK) \ 589 name##_RB_REMOVE_COLOR(head, parent, child); \ 590 return (old); \ 591 } \ 592 \ 593 /* Inserts a node into the RB tree */ \ 594 attr struct type * \ 595 name##_RB_INSERT(struct name *head, struct type *elm) \ 596 { \ 597 struct type *tmp; \ 598 struct type *parent = NULL; \ 599 int comp = 0; \ 600 tmp = RB_ROOT(head); \ 601 while (tmp) { \ 602 parent = tmp; \ 603 comp = (cmp)(elm, parent); \ 604 if (comp < 0) \ 605 tmp = RB_LEFT(tmp, field); \ 606 else if (comp > 0) \ 607 tmp = RB_RIGHT(tmp, field); \ 608 else \ 609 return (tmp); \ 610 } \ 611 RB_SET(elm, parent, field); \ 612 if (parent != NULL) { \ 613 if (comp < 0) \ 614 RB_LEFT(parent, field) = elm; \ 615 else \ 616 RB_RIGHT(parent, field) = elm; \ 617 RB_AUGMENT(parent); \ 618 } else \ 619 RB_ROOT(head) = elm; \ 620 name##_RB_INSERT_COLOR(head, elm); \ 621 return (NULL); \ 622 } \ 623 \ 624 /* Finds the node with the same key as elm */ \ 625 attr struct type * \ 626 name##_RB_FIND(struct name *head, struct type *elm) \ 627 { \ 628 struct type *tmp = RB_ROOT(head); \ 629 int comp; \ 630 while (tmp) { \ 631 comp = cmp(elm, tmp); \ 632 if (comp < 0) \ 633 tmp = RB_LEFT(tmp, field); \ 634 else if (comp > 0) \ 635 tmp = RB_RIGHT(tmp, field); \ 636 else \ 637 return (tmp); \ 638 } \ 639 return (NULL); \ 640 } \ 641 \ 642 /* Finds the first node greater than or equal to the search key */ \ 643 attr struct type * \ 644 name##_RB_NFIND(struct name *head, struct type *elm) \ 645 { \ 646 struct type *ret = RB_ROOT(head); \ 647 struct type *tmp; \ 648 int comp; \ 649 while (ret && (comp = cmp(elm, ret)) != 0) { \ 650 if (comp < 0) { \ 651 if ((tmp = RB_LEFT(ret, field)) == NULL) \ 652 break; \ 653 ret = tmp; \ 654 } else { \ 655 if ((tmp = RB_RIGHT(ret, field)) == NULL) { \ 656 tmp = ret; \ 657 ret = RB_PARENT(ret, field); \ 658 while (ret && tmp == RB_RIGHT(ret, \ 659 field)) { \ 660 tmp = ret; \ 661 ret = RB_PARENT(ret, field); \ 662 } \ 663 break; \ 664 } \ 665 ret = tmp; \ 666 } \ 667 } \ 668 return (ret); \ 669 } \ 670 \ 671 /* ARGSUSED */ \ 672 attr struct type * \ 673 name##_RB_NEXT(struct type *elm) \ 674 { \ 675 if (RB_RIGHT(elm, field)) { \ 676 elm = RB_RIGHT(elm, field); \ 677 while (RB_LEFT(elm, field)) \ 678 elm = RB_LEFT(elm, field); \ 679 } else { \ 680 if (RB_PARENT(elm, field) && \ 681 (elm == RB_LEFT(RB_PARENT(elm, field), field))) \ 682 elm = RB_PARENT(elm, field); \ 683 else { \ 684 while (RB_PARENT(elm, field) && \ 685 (elm == RB_RIGHT(RB_PARENT(elm, field), field)))\ 686 elm = RB_PARENT(elm, field); \ 687 elm = RB_PARENT(elm, field); \ 688 } \ 689 } \ 690 return (elm); \ 691 } \ 692 \ 693 attr struct type * \ 694 name##_RB_MINMAX(struct name *head, int val) \ 695 { \ 696 struct type *tmp = RB_ROOT(head); \ 697 struct type *parent = NULL; \ 698 while (tmp) { \ 699 parent = tmp; \ 700 if (val < 0) \ 701 tmp = RB_LEFT(tmp, field); \ 702 else \ 703 tmp = RB_RIGHT(tmp, field); \ 704 } \ 705 return (parent); \ 706 } 707 708 #define RB_NEGINF -1 709 #define RB_INF 1 710 711 #define RB_INSERT(name, x, y) name##_RB_INSERT(x, y) 712 #define RB_REMOVE(name, x, y) name##_RB_REMOVE(x, y) 713 #define RB_FIND(name, x, y) name##_RB_FIND(x, y) 714 #define RB_NFIND(name, x, y) name##_RB_NFIND(x, y) 715 #define RB_NEXT(name, x, y) name##_RB_NEXT(y) 716 #define RB_MIN(name, x) name##_RB_MINMAX(x, RB_NEGINF) 717 #define RB_MAX(name, x) name##_RB_MINMAX(x, RB_INF) 718 719 #define RB_FOREACH(x, name, head) \ 720 for ((x) = RB_MIN(name, head); \ 721 (x) != NULL; \ 722 (x) = name##_RB_NEXT(x)) 723 724 #endif /* _SYS_TREE_H_ */ 725