1 /* $NetBSD: tree.h,v 1.5 2002/11/02 07:35:07 perry Exp $ */ 2 /* $OpenBSD: tree.h,v 1.7 2002/10/17 21:51:54 art 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 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 __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))) { \ 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-back 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) 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))) { \ 339 RB_PARENT(RB_LEFT(tmp, field), field) = (elm); \ 340 } \ 341 RB_AUGMENT(elm); \ 342 if ((RB_PARENT(tmp, field) = RB_PARENT(elm, field))) { \ 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))) { \ 359 RB_PARENT(RB_RIGHT(tmp, field), field) = (elm); \ 360 } \ 361 RB_AUGMENT(elm); \ 362 if ((RB_PARENT(tmp, field) = RB_PARENT(elm, field))) { \ 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 void name##_RB_INSERT_COLOR(struct name *, struct type *); \ 379 void name##_RB_REMOVE_COLOR(struct name *, struct type *, struct type *);\ 380 struct type *name##_RB_REMOVE(struct name *, struct type *); \ 381 struct type *name##_RB_INSERT(struct name *, struct type *); \ 382 struct type *name##_RB_FIND(struct name *, struct type *); \ 383 struct type *name##_RB_NEXT(struct name *, struct type *); \ 384 struct type *name##_RB_MINMAX(struct name *, int); \ 385 \ 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 #endif /* _SYS_TREE_H_ */ 679