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