1 /* $NetBSD: tree.h,v 1.1.1.2 2012/07/22 13:44:50 darrenr Exp $ */ 2 /* $OpenBSD: tree.h,v 1.7 2002/10/17 21:51:54 art Exp $ */ 3 /* $FreeBSD: src/sys/sys/tree.h,v 1.7 2007/12/28 07:03:26 jasone Exp $ */ 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 /* 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) \ 61 struct 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) \ 73 struct { \ 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) \ 118 void name##_SPLAY(struct name *, struct type *); \ 119 void name##_SPLAY_MINMAX(struct name *, int); \ 120 struct type *name##_SPLAY_INSERT(struct name *, struct type *); \ 121 struct type *name##_SPLAY_REMOVE(struct name *, struct type *); \ 122 \ 123 /* Finds the node with the same key as elm */ \ 124 static __inline struct type * \ 125 name##_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 \ 135 static __inline struct type * \ 136 name##_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 \ 149 static __inline struct type * \ 150 name##_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) \ 160 struct type * \ 161 name##_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 \ 184 struct type * \ 185 name##_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 \ 205 void \ 206 name##_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 */ \ 243 void 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) \ 295 struct 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 /* 307 * Undef for Linux 308 */ 309 #undef RB_BLACK 310 #undef RB_RED 311 #undef RB_ROOT 312 313 #define RB_BLACK 0 314 #define RB_RED 1 315 #define RB_ENTRY(type) \ 316 struct { \ 317 struct type *rbe_left; /* left element */ \ 318 struct type *rbe_right; /* right element */ \ 319 struct type *rbe_parent; /* parent element */ \ 320 int rbe_color; /* node color */ \ 321 } 322 323 #define RB_LEFT(elm, field) (elm)->field.rbe_left 324 #define RB_RIGHT(elm, field) (elm)->field.rbe_right 325 #define RB_PARENT(elm, field) (elm)->field.rbe_parent 326 #define RB_COLOR(elm, field) (elm)->field.rbe_color 327 #define RB_ROOT(head) (head)->rbh_root 328 #define RB_EMPTY(head) (RB_ROOT(head) == NULL) 329 330 #define RB_SET(elm, parent, field) do { \ 331 RB_PARENT(elm, field) = parent; \ 332 RB_LEFT(elm, field) = RB_RIGHT(elm, field) = NULL; \ 333 RB_COLOR(elm, field) = RB_RED; \ 334 } while (/*CONSTCOND*/ 0) 335 336 #define RB_SET_BLACKRED(black, red, field) do { \ 337 RB_COLOR(black, field) = RB_BLACK; \ 338 RB_COLOR(red, field) = RB_RED; \ 339 } while (/*CONSTCOND*/ 0) 340 341 #ifndef RB_AUGMENT 342 #define RB_AUGMENT(x) do {} while (0) 343 #endif 344 345 #define RB_ROTATE_LEFT(head, elm, tmp, field) do { \ 346 (tmp) = RB_RIGHT(elm, field); \ 347 if ((RB_RIGHT(elm, field) = RB_LEFT(tmp, field)) != NULL) { \ 348 RB_PARENT(RB_LEFT(tmp, field), field) = (elm); \ 349 } \ 350 RB_AUGMENT(elm); \ 351 if ((RB_PARENT(tmp, field) = RB_PARENT(elm, field)) != NULL) { \ 352 if ((elm) == RB_LEFT(RB_PARENT(elm, field), field)) \ 353 RB_LEFT(RB_PARENT(elm, field), field) = (tmp); \ 354 else \ 355 RB_RIGHT(RB_PARENT(elm, field), field) = (tmp); \ 356 } else \ 357 (head)->rbh_root = (tmp); \ 358 RB_LEFT(tmp, field) = (elm); \ 359 RB_PARENT(elm, field) = (tmp); \ 360 RB_AUGMENT(tmp); \ 361 if ((RB_PARENT(tmp, field))) \ 362 RB_AUGMENT(RB_PARENT(tmp, field)); \ 363 } while (/*CONSTCOND*/ 0) 364 365 #define RB_ROTATE_RIGHT(head, elm, tmp, field) do { \ 366 (tmp) = RB_LEFT(elm, field); \ 367 if ((RB_LEFT(elm, field) = RB_RIGHT(tmp, field)) != NULL) { \ 368 RB_PARENT(RB_RIGHT(tmp, field), field) = (elm); \ 369 } \ 370 RB_AUGMENT(elm); \ 371 if ((RB_PARENT(tmp, field) = RB_PARENT(elm, field)) != NULL) { \ 372 if ((elm) == RB_LEFT(RB_PARENT(elm, field), field)) \ 373 RB_LEFT(RB_PARENT(elm, field), field) = (tmp); \ 374 else \ 375 RB_RIGHT(RB_PARENT(elm, field), field) = (tmp); \ 376 } else \ 377 (head)->rbh_root = (tmp); \ 378 RB_RIGHT(tmp, field) = (elm); \ 379 RB_PARENT(elm, field) = (tmp); \ 380 RB_AUGMENT(tmp); \ 381 if ((RB_PARENT(tmp, field))) \ 382 RB_AUGMENT(RB_PARENT(tmp, field)); \ 383 } while (/*CONSTCOND*/ 0) 384 385 /* Generates prototypes and inline functions */ 386 #define RB_PROTOTYPE(name, type, field, cmp) \ 387 RB_PROTOTYPE_INTERNAL(name, type, field, cmp,) 388 #define RB_PROTOTYPE_STATIC(name, type, field, cmp) \ 389 RB_PROTOTYPE_INTERNAL(name, type, field, cmp, __unused static) 390 #define RB_PROTOTYPE_INTERNAL(name, type, field, cmp, attr) \ 391 attr void name##_RB_INSERT_COLOR(struct name *, struct type *); \ 392 attr void name##_RB_REMOVE_COLOR(struct name *, struct type *, struct type *);\ 393 attr struct type *name##_RB_REMOVE(struct name *, struct type *); \ 394 attr struct type *name##_RB_INSERT(struct name *, struct type *); \ 395 attr struct type *name##_RB_FIND(struct name *, struct type *); \ 396 attr struct type *name##_RB_NFIND(struct name *, struct type *); \ 397 attr struct type *name##_RB_NEXT(struct type *); \ 398 attr struct type *name##_RB_PREV(struct type *); \ 399 attr struct type *name##_RB_MINMAX(struct name *, int); \ 400 \ 401 402 /* Main rb operation. 403 * Moves node close to the key of elm to top 404 */ 405 #define RB_GENERATE(name, type, field, cmp) \ 406 RB_GENERATE_INTERNAL(name, type, field, cmp,) 407 #define RB_GENERATE_STATIC(name, type, field, cmp) \ 408 RB_GENERATE_INTERNAL(name, type, field, cmp, __unused static) 409 #define RB_GENERATE_INTERNAL(name, type, field, cmp, attr) \ 410 attr void \ 411 name##_RB_INSERT_COLOR(struct name *head, struct type *elm) \ 412 { \ 413 struct type *parent, *gparent, *tmp; \ 414 while ((parent = RB_PARENT(elm, field)) != NULL && \ 415 RB_COLOR(parent, field) == RB_RED) { \ 416 gparent = RB_PARENT(parent, field); \ 417 if (parent == RB_LEFT(gparent, field)) { \ 418 tmp = RB_RIGHT(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_RIGHT(parent, field) == elm) { \ 426 RB_ROTATE_LEFT(head, parent, tmp, field);\ 427 tmp = parent; \ 428 parent = elm; \ 429 elm = tmp; \ 430 } \ 431 RB_SET_BLACKRED(parent, gparent, field); \ 432 RB_ROTATE_RIGHT(head, gparent, tmp, field); \ 433 } else { \ 434 tmp = RB_LEFT(gparent, field); \ 435 if (tmp && RB_COLOR(tmp, field) == RB_RED) { \ 436 RB_COLOR(tmp, field) = RB_BLACK; \ 437 RB_SET_BLACKRED(parent, gparent, field);\ 438 elm = gparent; \ 439 continue; \ 440 } \ 441 if (RB_LEFT(parent, field) == elm) { \ 442 RB_ROTATE_RIGHT(head, parent, tmp, field);\ 443 tmp = parent; \ 444 parent = elm; \ 445 elm = tmp; \ 446 } \ 447 RB_SET_BLACKRED(parent, gparent, field); \ 448 RB_ROTATE_LEFT(head, gparent, tmp, field); \ 449 } \ 450 } \ 451 RB_COLOR(head->rbh_root, field) = RB_BLACK; \ 452 } \ 453 \ 454 attr void \ 455 name##_RB_REMOVE_COLOR(struct name *head, struct type *parent, struct type *elm) \ 456 { \ 457 struct type *tmp; \ 458 while ((elm == NULL || RB_COLOR(elm, field) == RB_BLACK) && \ 459 elm != RB_ROOT(head)) { \ 460 if (RB_LEFT(parent, field) == elm) { \ 461 tmp = RB_RIGHT(parent, field); \ 462 if (RB_COLOR(tmp, field) == RB_RED) { \ 463 RB_SET_BLACKRED(tmp, parent, field); \ 464 RB_ROTATE_LEFT(head, parent, tmp, field);\ 465 tmp = RB_RIGHT(parent, field); \ 466 } \ 467 if ((RB_LEFT(tmp, field) == NULL || \ 468 RB_COLOR(RB_LEFT(tmp, field), field) == RB_BLACK) &&\ 469 (RB_RIGHT(tmp, field) == NULL || \ 470 RB_COLOR(RB_RIGHT(tmp, field), field) == RB_BLACK)) {\ 471 RB_COLOR(tmp, field) = RB_RED; \ 472 elm = parent; \ 473 parent = RB_PARENT(elm, field); \ 474 } else { \ 475 if (RB_RIGHT(tmp, field) == NULL || \ 476 RB_COLOR(RB_RIGHT(tmp, field), field) == RB_BLACK) {\ 477 struct type *oleft; \ 478 if ((oleft = RB_LEFT(tmp, field)) \ 479 != NULL) \ 480 RB_COLOR(oleft, field) = RB_BLACK;\ 481 RB_COLOR(tmp, field) = RB_RED; \ 482 RB_ROTATE_RIGHT(head, tmp, oleft, field);\ 483 tmp = RB_RIGHT(parent, field); \ 484 } \ 485 RB_COLOR(tmp, field) = RB_COLOR(parent, field);\ 486 RB_COLOR(parent, field) = RB_BLACK; \ 487 if (RB_RIGHT(tmp, field)) \ 488 RB_COLOR(RB_RIGHT(tmp, field), field) = RB_BLACK;\ 489 RB_ROTATE_LEFT(head, parent, tmp, field);\ 490 elm = RB_ROOT(head); \ 491 break; \ 492 } \ 493 } else { \ 494 tmp = RB_LEFT(parent, field); \ 495 if (RB_COLOR(tmp, field) == RB_RED) { \ 496 RB_SET_BLACKRED(tmp, parent, field); \ 497 RB_ROTATE_RIGHT(head, parent, tmp, field);\ 498 tmp = RB_LEFT(parent, field); \ 499 } \ 500 if ((RB_LEFT(tmp, field) == NULL || \ 501 RB_COLOR(RB_LEFT(tmp, field), field) == RB_BLACK) &&\ 502 (RB_RIGHT(tmp, field) == NULL || \ 503 RB_COLOR(RB_RIGHT(tmp, field), field) == RB_BLACK)) {\ 504 RB_COLOR(tmp, field) = RB_RED; \ 505 elm = parent; \ 506 parent = RB_PARENT(elm, field); \ 507 } else { \ 508 if (RB_LEFT(tmp, field) == NULL || \ 509 RB_COLOR(RB_LEFT(tmp, field), field) == RB_BLACK) {\ 510 struct type *oright; \ 511 if ((oright = RB_RIGHT(tmp, field)) \ 512 != NULL) \ 513 RB_COLOR(oright, field) = RB_BLACK;\ 514 RB_COLOR(tmp, field) = RB_RED; \ 515 RB_ROTATE_LEFT(head, tmp, oright, field);\ 516 tmp = RB_LEFT(parent, field); \ 517 } \ 518 RB_COLOR(tmp, field) = RB_COLOR(parent, field);\ 519 RB_COLOR(parent, field) = RB_BLACK; \ 520 if (RB_LEFT(tmp, field)) \ 521 RB_COLOR(RB_LEFT(tmp, field), field) = RB_BLACK;\ 522 RB_ROTATE_RIGHT(head, parent, tmp, field);\ 523 elm = RB_ROOT(head); \ 524 break; \ 525 } \ 526 } \ 527 } \ 528 if (elm) \ 529 RB_COLOR(elm, field) = RB_BLACK; \ 530 } \ 531 \ 532 attr struct type * \ 533 name##_RB_REMOVE(struct name *head, struct type *elm) \ 534 { \ 535 struct type *child, *parent, *old = elm; \ 536 int color; \ 537 if (RB_LEFT(elm, field) == NULL) \ 538 child = RB_RIGHT(elm, field); \ 539 else if (RB_RIGHT(elm, field) == NULL) \ 540 child = RB_LEFT(elm, field); \ 541 else { \ 542 struct type *left; \ 543 elm = RB_RIGHT(elm, field); \ 544 while ((left = RB_LEFT(elm, field)) != NULL) \ 545 elm = left; \ 546 child = RB_RIGHT(elm, field); \ 547 parent = RB_PARENT(elm, field); \ 548 color = RB_COLOR(elm, field); \ 549 if (child) \ 550 RB_PARENT(child, field) = parent; \ 551 if (parent) { \ 552 if (RB_LEFT(parent, field) == elm) \ 553 RB_LEFT(parent, field) = child; \ 554 else \ 555 RB_RIGHT(parent, field) = child; \ 556 RB_AUGMENT(parent); \ 557 } else \ 558 RB_ROOT(head) = child; \ 559 if (RB_PARENT(elm, field) == old) \ 560 parent = elm; \ 561 (elm)->field = (old)->field; \ 562 if (RB_PARENT(old, field)) { \ 563 if (RB_LEFT(RB_PARENT(old, field), field) == old)\ 564 RB_LEFT(RB_PARENT(old, field), field) = elm;\ 565 else \ 566 RB_RIGHT(RB_PARENT(old, field), field) = elm;\ 567 RB_AUGMENT(RB_PARENT(old, field)); \ 568 } else \ 569 RB_ROOT(head) = elm; \ 570 RB_PARENT(RB_LEFT(old, field), field) = elm; \ 571 if (RB_RIGHT(old, field)) \ 572 RB_PARENT(RB_RIGHT(old, field), field) = elm; \ 573 if (parent) { \ 574 left = parent; \ 575 do { \ 576 RB_AUGMENT(left); \ 577 } while ((left = RB_PARENT(left, field)) != NULL); \ 578 } \ 579 goto color; \ 580 } \ 581 parent = RB_PARENT(elm, field); \ 582 color = RB_COLOR(elm, field); \ 583 if (child) \ 584 RB_PARENT(child, field) = parent; \ 585 if (parent) { \ 586 if (RB_LEFT(parent, field) == elm) \ 587 RB_LEFT(parent, field) = child; \ 588 else \ 589 RB_RIGHT(parent, field) = child; \ 590 RB_AUGMENT(parent); \ 591 } else \ 592 RB_ROOT(head) = child; \ 593 color: \ 594 if (color == RB_BLACK) \ 595 name##_RB_REMOVE_COLOR(head, parent, child); \ 596 return (old); \ 597 } \ 598 \ 599 /* Inserts a node into the RB tree */ \ 600 attr struct type * \ 601 name##_RB_INSERT(struct name *head, struct type *elm) \ 602 { \ 603 struct type *tmp; \ 604 struct type *parent = NULL; \ 605 int comp = 0; \ 606 tmp = RB_ROOT(head); \ 607 while (tmp) { \ 608 parent = tmp; \ 609 comp = (cmp)(elm, parent); \ 610 if (comp < 0) \ 611 tmp = RB_LEFT(tmp, field); \ 612 else if (comp > 0) \ 613 tmp = RB_RIGHT(tmp, field); \ 614 else \ 615 return (tmp); \ 616 } \ 617 RB_SET(elm, parent, field); \ 618 if (parent != NULL) { \ 619 if (comp < 0) \ 620 RB_LEFT(parent, field) = elm; \ 621 else \ 622 RB_RIGHT(parent, field) = elm; \ 623 RB_AUGMENT(parent); \ 624 } else \ 625 RB_ROOT(head) = elm; \ 626 name##_RB_INSERT_COLOR(head, elm); \ 627 return (NULL); \ 628 } \ 629 \ 630 /* Finds the node with the same key as elm */ \ 631 attr struct type * \ 632 name##_RB_FIND(struct name *head, struct type *elm) \ 633 { \ 634 struct type *tmp = RB_ROOT(head); \ 635 int comp; \ 636 while (tmp) { \ 637 comp = cmp(elm, tmp); \ 638 if (comp < 0) \ 639 tmp = RB_LEFT(tmp, field); \ 640 else if (comp > 0) \ 641 tmp = RB_RIGHT(tmp, field); \ 642 else \ 643 return (tmp); \ 644 } \ 645 return (NULL); \ 646 } \ 647 \ 648 /* Finds the first node greater than or equal to the search key */ \ 649 attr struct type * \ 650 name##_RB_NFIND(struct name *head, struct type *elm) \ 651 { \ 652 struct type *tmp = RB_ROOT(head); \ 653 struct type *res = NULL; \ 654 int comp; \ 655 while (tmp) { \ 656 comp = cmp(elm, tmp); \ 657 if (comp < 0) { \ 658 res = tmp; \ 659 tmp = RB_LEFT(tmp, field); \ 660 } \ 661 else if (comp > 0) \ 662 tmp = RB_RIGHT(tmp, field); \ 663 else \ 664 return (tmp); \ 665 } \ 666 return (res); \ 667 } \ 668 \ 669 /* ARGSUSED */ \ 670 attr struct type * \ 671 name##_RB_NEXT(struct type *elm) \ 672 { \ 673 if (RB_RIGHT(elm, field)) { \ 674 elm = RB_RIGHT(elm, field); \ 675 while (RB_LEFT(elm, field)) \ 676 elm = RB_LEFT(elm, field); \ 677 } else { \ 678 if (RB_PARENT(elm, field) && \ 679 (elm == RB_LEFT(RB_PARENT(elm, field), field))) \ 680 elm = RB_PARENT(elm, field); \ 681 else { \ 682 while (RB_PARENT(elm, field) && \ 683 (elm == RB_RIGHT(RB_PARENT(elm, field), field)))\ 684 elm = RB_PARENT(elm, field); \ 685 elm = RB_PARENT(elm, field); \ 686 } \ 687 } \ 688 return (elm); \ 689 } \ 690 \ 691 /* ARGSUSED */ \ 692 attr struct type * \ 693 name##_RB_PREV(struct type *elm) \ 694 { \ 695 if (RB_LEFT(elm, field)) { \ 696 elm = RB_LEFT(elm, field); \ 697 while (RB_RIGHT(elm, field)) \ 698 elm = RB_RIGHT(elm, field); \ 699 } else { \ 700 if (RB_PARENT(elm, field) && \ 701 (elm == RB_RIGHT(RB_PARENT(elm, field), field))) \ 702 elm = RB_PARENT(elm, field); \ 703 else { \ 704 while (RB_PARENT(elm, field) && \ 705 (elm == RB_LEFT(RB_PARENT(elm, field), field)))\ 706 elm = RB_PARENT(elm, field); \ 707 elm = RB_PARENT(elm, field); \ 708 } \ 709 } \ 710 return (elm); \ 711 } \ 712 \ 713 attr struct type * \ 714 name##_RB_MINMAX(struct name *head, int val) \ 715 { \ 716 struct type *tmp = RB_ROOT(head); \ 717 struct type *parent = NULL; \ 718 while (tmp) { \ 719 parent = tmp; \ 720 if (val < 0) \ 721 tmp = RB_LEFT(tmp, field); \ 722 else \ 723 tmp = RB_RIGHT(tmp, field); \ 724 } \ 725 return (parent); \ 726 } 727 728 #define RB_NEGINF -1 729 #define RB_INF 1 730 731 #define RB_INSERT(name, x, y) name##_RB_INSERT(x, y) 732 #define RB_REMOVE(name, x, y) name##_RB_REMOVE(x, y) 733 #define RB_FIND(name, x, y) name##_RB_FIND(x, y) 734 #define RB_NFIND(name, x, y) name##_RB_NFIND(x, y) 735 #define RB_NEXT(name, x, y) name##_RB_NEXT(y) 736 #define RB_PREV(name, x, y) name##_RB_PREV(y) 737 #define RB_MIN(name, x) name##_RB_MINMAX(x, RB_NEGINF) 738 #define RB_MAX(name, x) name##_RB_MINMAX(x, RB_INF) 739 740 #define RB_FOREACH(x, name, head) \ 741 for ((x) = RB_MIN(name, head); \ 742 (x) != NULL; \ 743 (x) = name##_RB_NEXT(x)) 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 #endif /* _SYS_TREE_H_ */ 751