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