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