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