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