1 /* $OpenBSD: tree.h,v 1.7 2002/10/17 21:51:54 art 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 /* 31 * This file defines data structures for different types of trees: 32 * splay trees and red-black trees. 33 * 34 * A splay tree is a self-organizing data structure. Every operation 35 * on the tree causes a splay to happen. The splay moves the requested 36 * node to the root of the tree and partly rebalances it. 37 * 38 * This has the benefit that request locality causes faster lookups as 39 * the requested nodes move to the top of the tree. On the other hand, 40 * every lookup causes memory writes. 41 * 42 * The Balance Theorem bounds the total access time for m operations 43 * and n inserts on an initially empty tree as O((m + n)lg n). The 44 * amortized cost for a sequence of m accesses to a splay tree is O(lg n); 45 * 46 * A red-black tree is a binary search tree with the node color as an 47 * extra attribute. It fulfills a set of conditions: 48 * - every search path from the root to a leaf consists of the 49 * same number of black nodes, 50 * - each red node (except for the root) has a black parent, 51 * - each leaf node is black. 52 * 53 * Every operation on a red-black tree is bounded as O(lg n). 54 * The maximum height of a red-black tree is 2lg (n+1). 55 */ 56 57 #define SPLAY_HEAD(name, type) \ 58 struct name { \ 59 struct type *sph_root; /* root of the tree */ \ 60 } 61 62 #define SPLAY_INITIALIZER(root) \ 63 { NULL } 64 65 #define SPLAY_INIT(root) do { \ 66 (root)->sph_root = NULL; \ 67 } while (0) 68 69 #define SPLAY_ENTRY(type) \ 70 struct { \ 71 struct type *spe_left; /* left element */ \ 72 struct type *spe_right; /* right element */ \ 73 } 74 75 #define SPLAY_LEFT(elm, field) (elm)->field.spe_left 76 #define SPLAY_RIGHT(elm, field) (elm)->field.spe_right 77 #define SPLAY_ROOT(head) (head)->sph_root 78 #define SPLAY_EMPTY(head) (SPLAY_ROOT(head) == NULL) 79 80 /* SPLAY_ROTATE_{LEFT,RIGHT} expect that tmp hold SPLAY_{RIGHT,LEFT} */ 81 #define SPLAY_ROTATE_RIGHT(head, tmp, field) do { \ 82 SPLAY_LEFT((head)->sph_root, field) = SPLAY_RIGHT(tmp, field); \ 83 SPLAY_RIGHT(tmp, field) = (head)->sph_root; \ 84 (head)->sph_root = tmp; \ 85 } while (0) 86 87 #define SPLAY_ROTATE_LEFT(head, tmp, field) do { \ 88 SPLAY_RIGHT((head)->sph_root, field) = SPLAY_LEFT(tmp, field); \ 89 SPLAY_LEFT(tmp, field) = (head)->sph_root; \ 90 (head)->sph_root = tmp; \ 91 } while (0) 92 93 #define SPLAY_LINKLEFT(head, tmp, field) do { \ 94 SPLAY_LEFT(tmp, field) = (head)->sph_root; \ 95 tmp = (head)->sph_root; \ 96 (head)->sph_root = SPLAY_LEFT((head)->sph_root, field); \ 97 } while (0) 98 99 #define SPLAY_LINKRIGHT(head, tmp, field) do { \ 100 SPLAY_RIGHT(tmp, field) = (head)->sph_root; \ 101 tmp = (head)->sph_root; \ 102 (head)->sph_root = SPLAY_RIGHT((head)->sph_root, field); \ 103 } while (0) 104 105 #define SPLAY_ASSEMBLE(head, node, left, right, field) do { \ 106 SPLAY_RIGHT(left, field) = SPLAY_LEFT((head)->sph_root, field); \ 107 SPLAY_LEFT(right, field) = SPLAY_RIGHT((head)->sph_root, field);\ 108 SPLAY_LEFT((head)->sph_root, field) = SPLAY_RIGHT(node, field); \ 109 SPLAY_RIGHT((head)->sph_root, field) = SPLAY_LEFT(node, field); \ 110 } while (0) 111 112 /* Generates prototypes and inline functions */ 113 114 #define SPLAY_PROTOTYPE(name, type, field, cmp) \ 115 void name##_SPLAY(struct name *, struct type *); \ 116 void name##_SPLAY_MINMAX(struct name *, int); \ 117 struct type *name##_SPLAY_INSERT(struct name *, struct type *); \ 118 struct type *name##_SPLAY_REMOVE(struct name *, struct type *); \ 119 \ 120 /* Finds the node with the same key as elm */ \ 121 static __inline struct type * \ 122 name##_SPLAY_FIND(struct name *head, struct type *elm) \ 123 { \ 124 if (SPLAY_EMPTY(head)) \ 125 return(NULL); \ 126 name##_SPLAY(head, elm); \ 127 if ((cmp)(elm, (head)->sph_root) == 0) \ 128 return (head->sph_root); \ 129 return (NULL); \ 130 } \ 131 \ 132 static __inline struct type * \ 133 name##_SPLAY_NEXT(struct name *head, struct type *elm) \ 134 { \ 135 name##_SPLAY(head, elm); \ 136 if (SPLAY_RIGHT(elm, field) != NULL) { \ 137 elm = SPLAY_RIGHT(elm, field); \ 138 while (SPLAY_LEFT(elm, field) != NULL) { \ 139 elm = SPLAY_LEFT(elm, field); \ 140 } \ 141 } else \ 142 elm = NULL; \ 143 return (elm); \ 144 } \ 145 \ 146 static __inline struct type * \ 147 name##_SPLAY_MIN_MAX(struct name *head, int val) \ 148 { \ 149 name##_SPLAY_MINMAX(head, val); \ 150 return (SPLAY_ROOT(head)); \ 151 } 152 153 /* Main splay operation. 154 * Moves node close to the key of elm to top 155 */ 156 #define SPLAY_GENERATE(name, type, field, cmp) \ 157 struct type * \ 158 name##_SPLAY_INSERT(struct name *head, struct type *elm) \ 159 { \ 160 if (SPLAY_EMPTY(head)) { \ 161 SPLAY_LEFT(elm, field) = SPLAY_RIGHT(elm, field) = NULL; \ 162 } else { \ 163 int __comp; \ 164 name##_SPLAY(head, elm); \ 165 __comp = (cmp)(elm, (head)->sph_root); \ 166 if(__comp < 0) { \ 167 SPLAY_LEFT(elm, field) = SPLAY_LEFT((head)->sph_root, field);\ 168 SPLAY_RIGHT(elm, field) = (head)->sph_root; \ 169 SPLAY_LEFT((head)->sph_root, field) = NULL; \ 170 } else if (__comp > 0) { \ 171 SPLAY_RIGHT(elm, field) = SPLAY_RIGHT((head)->sph_root, field);\ 172 SPLAY_LEFT(elm, field) = (head)->sph_root; \ 173 SPLAY_RIGHT((head)->sph_root, field) = NULL; \ 174 } else \ 175 return ((head)->sph_root); \ 176 } \ 177 (head)->sph_root = (elm); \ 178 return (NULL); \ 179 } \ 180 \ 181 struct type * \ 182 name##_SPLAY_REMOVE(struct name *head, struct type *elm) \ 183 { \ 184 struct type *__tmp; \ 185 if (SPLAY_EMPTY(head)) \ 186 return (NULL); \ 187 name##_SPLAY(head, elm); \ 188 if ((cmp)(elm, (head)->sph_root) == 0) { \ 189 if (SPLAY_LEFT((head)->sph_root, field) == NULL) { \ 190 (head)->sph_root = SPLAY_RIGHT((head)->sph_root, field);\ 191 } else { \ 192 __tmp = SPLAY_RIGHT((head)->sph_root, field); \ 193 (head)->sph_root = SPLAY_LEFT((head)->sph_root, field);\ 194 name##_SPLAY(head, elm); \ 195 SPLAY_RIGHT((head)->sph_root, field) = __tmp; \ 196 } \ 197 return (elm); \ 198 } \ 199 return (NULL); \ 200 } \ 201 \ 202 void \ 203 name##_SPLAY(struct name *head, struct type *elm) \ 204 { \ 205 struct type __node, *__left, *__right, *__tmp; \ 206 int __comp; \ 207 \ 208 SPLAY_LEFT(&__node, field) = SPLAY_RIGHT(&__node, field) = NULL;\ 209 __left = __right = &__node; \ 210 \ 211 while ((__comp = (cmp)(elm, (head)->sph_root))) { \ 212 if (__comp < 0) { \ 213 __tmp = SPLAY_LEFT((head)->sph_root, field); \ 214 if (__tmp == NULL) \ 215 break; \ 216 if ((cmp)(elm, __tmp) < 0){ \ 217 SPLAY_ROTATE_RIGHT(head, __tmp, field); \ 218 if (SPLAY_LEFT((head)->sph_root, field) == NULL)\ 219 break; \ 220 } \ 221 SPLAY_LINKLEFT(head, __right, field); \ 222 } else if (__comp > 0) { \ 223 __tmp = SPLAY_RIGHT((head)->sph_root, field); \ 224 if (__tmp == NULL) \ 225 break; \ 226 if ((cmp)(elm, __tmp) > 0){ \ 227 SPLAY_ROTATE_LEFT(head, __tmp, field); \ 228 if (SPLAY_RIGHT((head)->sph_root, field) == NULL)\ 229 break; \ 230 } \ 231 SPLAY_LINKRIGHT(head, __left, field); \ 232 } \ 233 } \ 234 SPLAY_ASSEMBLE(head, &__node, __left, __right, field); \ 235 } \ 236 \ 237 /* Splay with either the minimum or the maximum element \ 238 * Used to find minimum or maximum element in tree. \ 239 */ \ 240 void name##_SPLAY_MINMAX(struct name *head, int __comp) \ 241 { \ 242 struct type __node, *__left, *__right, *__tmp; \ 243 \ 244 SPLAY_LEFT(&__node, field) = SPLAY_RIGHT(&__node, field) = NULL;\ 245 __left = __right = &__node; \ 246 \ 247 while (1) { \ 248 if (__comp < 0) { \ 249 __tmp = SPLAY_LEFT((head)->sph_root, field); \ 250 if (__tmp == NULL) \ 251 break; \ 252 if (__comp < 0){ \ 253 SPLAY_ROTATE_RIGHT(head, __tmp, field); \ 254 if (SPLAY_LEFT((head)->sph_root, field) == NULL)\ 255 break; \ 256 } \ 257 SPLAY_LINKLEFT(head, __right, field); \ 258 } else if (__comp > 0) { \ 259 __tmp = SPLAY_RIGHT((head)->sph_root, field); \ 260 if (__tmp == NULL) \ 261 break; \ 262 if (__comp > 0) { \ 263 SPLAY_ROTATE_LEFT(head, __tmp, field); \ 264 if (SPLAY_RIGHT((head)->sph_root, field) == NULL)\ 265 break; \ 266 } \ 267 SPLAY_LINKRIGHT(head, __left, field); \ 268 } \ 269 } \ 270 SPLAY_ASSEMBLE(head, &__node, __left, __right, field); \ 271 } 272 273 #define SPLAY_NEGINF -1 274 #define SPLAY_INF 1 275 276 #define SPLAY_INSERT(name, x, y) name##_SPLAY_INSERT(x, y) 277 #define SPLAY_REMOVE(name, x, y) name##_SPLAY_REMOVE(x, y) 278 #define SPLAY_FIND(name, x, y) name##_SPLAY_FIND(x, y) 279 #define SPLAY_NEXT(name, x, y) name##_SPLAY_NEXT(x, y) 280 #define SPLAY_MIN(name, x) (SPLAY_EMPTY(x) ? NULL \ 281 : name##_SPLAY_MIN_MAX(x, SPLAY_NEGINF)) 282 #define SPLAY_MAX(name, x) (SPLAY_EMPTY(x) ? NULL \ 283 : name##_SPLAY_MIN_MAX(x, SPLAY_INF)) 284 285 #define SPLAY_FOREACH(x, name, head) \ 286 for ((x) = SPLAY_MIN(name, head); \ 287 (x) != NULL; \ 288 (x) = SPLAY_NEXT(name, head, x)) 289 290 /* Macros that define a red-back tree */ 291 #define RB_HEAD(name, type) \ 292 struct name { \ 293 struct type *rbh_root; /* root of the tree */ \ 294 } 295 296 #define RB_INITIALIZER(root) \ 297 { NULL } 298 299 #define RB_INIT(root) do { \ 300 (root)->rbh_root = NULL; \ 301 } while (0) 302 303 #define RB_BLACK 0 304 #define RB_RED 1 305 #define RB_ENTRY(type) \ 306 struct { \ 307 struct type *rbe_left; /* left element */ \ 308 struct type *rbe_right; /* right element */ \ 309 struct type *rbe_parent; /* parent element */ \ 310 int rbe_color; /* node color */ \ 311 } 312 313 #define RB_LEFT(elm, field) (elm)->field.rbe_left 314 #define RB_RIGHT(elm, field) (elm)->field.rbe_right 315 #define RB_PARENT(elm, field) (elm)->field.rbe_parent 316 #define RB_COLOR(elm, field) (elm)->field.rbe_color 317 #define RB_ROOT(head) (head)->rbh_root 318 #define RB_EMPTY(head) (RB_ROOT(head) == NULL) 319 320 #define RB_SET(elm, parent, field) do { \ 321 RB_PARENT(elm, field) = parent; \ 322 RB_LEFT(elm, field) = RB_RIGHT(elm, field) = NULL; \ 323 RB_COLOR(elm, field) = RB_RED; \ 324 } while (0) 325 326 #define RB_SET_BLACKRED(black, red, field) do { \ 327 RB_COLOR(black, field) = RB_BLACK; \ 328 RB_COLOR(red, field) = RB_RED; \ 329 } while (0) 330 331 #ifndef RB_AUGMENT 332 #define RB_AUGMENT(x) 333 #endif 334 335 #define RB_ROTATE_LEFT(head, elm, tmp, field) do { \ 336 (tmp) = RB_RIGHT(elm, field); \ 337 if ((RB_RIGHT(elm, field) = RB_LEFT(tmp, field))) { \ 338 RB_PARENT(RB_LEFT(tmp, field), field) = (elm); \ 339 } \ 340 RB_AUGMENT(elm); \ 341 if ((RB_PARENT(tmp, field) = RB_PARENT(elm, field))) { \ 342 if ((elm) == RB_LEFT(RB_PARENT(elm, field), field)) \ 343 RB_LEFT(RB_PARENT(elm, field), field) = (tmp); \ 344 else \ 345 RB_RIGHT(RB_PARENT(elm, field), field) = (tmp); \ 346 } else \ 347 (head)->rbh_root = (tmp); \ 348 RB_LEFT(tmp, field) = (elm); \ 349 RB_PARENT(elm, field) = (tmp); \ 350 RB_AUGMENT(tmp); \ 351 if ((RB_PARENT(tmp, field))) \ 352 RB_AUGMENT(RB_PARENT(tmp, field)); \ 353 } while (0) 354 355 #define RB_ROTATE_RIGHT(head, elm, tmp, field) do { \ 356 (tmp) = RB_LEFT(elm, field); \ 357 if ((RB_LEFT(elm, field) = RB_RIGHT(tmp, field))) { \ 358 RB_PARENT(RB_RIGHT(tmp, field), field) = (elm); \ 359 } \ 360 RB_AUGMENT(elm); \ 361 if ((RB_PARENT(tmp, field) = RB_PARENT(elm, field))) { \ 362 if ((elm) == RB_LEFT(RB_PARENT(elm, field), field)) \ 363 RB_LEFT(RB_PARENT(elm, field), field) = (tmp); \ 364 else \ 365 RB_RIGHT(RB_PARENT(elm, field), field) = (tmp); \ 366 } else \ 367 (head)->rbh_root = (tmp); \ 368 RB_RIGHT(tmp, field) = (elm); \ 369 RB_PARENT(elm, field) = (tmp); \ 370 RB_AUGMENT(tmp); \ 371 if ((RB_PARENT(tmp, field))) \ 372 RB_AUGMENT(RB_PARENT(tmp, field)); \ 373 } while (0) 374 375 /* Generates prototypes and inline functions */ 376 #define RB_PROTOTYPE(name, type, field, cmp) \ 377 void name##_RB_INSERT_COLOR(struct name *, struct type *); \ 378 void name##_RB_REMOVE_COLOR(struct name *, struct type *, struct type *);\ 379 struct type *name##_RB_REMOVE(struct name *, struct type *); \ 380 struct type *name##_RB_INSERT(struct name *, struct type *); \ 381 struct type *name##_RB_FIND(struct name *, struct type *); \ 382 struct type *name##_RB_NEXT(struct type *); \ 383 struct type *name##_RB_MINMAX(struct name *, int); \ 384 \ 385 386 /* Main rb operation. 387 * Moves node close to the key of elm to top 388 */ 389 #define RB_GENERATE(name, type, field, cmp) \ 390 void \ 391 name##_RB_INSERT_COLOR(struct name *head, struct type *elm) \ 392 { \ 393 struct type *parent, *gparent, *tmp; \ 394 while ((parent = RB_PARENT(elm, field)) && \ 395 RB_COLOR(parent, field) == RB_RED) { \ 396 gparent = RB_PARENT(parent, field); \ 397 if (parent == RB_LEFT(gparent, field)) { \ 398 tmp = RB_RIGHT(gparent, field); \ 399 if (tmp && RB_COLOR(tmp, field) == RB_RED) { \ 400 RB_COLOR(tmp, field) = RB_BLACK; \ 401 RB_SET_BLACKRED(parent, gparent, field);\ 402 elm = gparent; \ 403 continue; \ 404 } \ 405 if (RB_RIGHT(parent, field) == elm) { \ 406 RB_ROTATE_LEFT(head, parent, tmp, field);\ 407 tmp = parent; \ 408 parent = elm; \ 409 elm = tmp; \ 410 } \ 411 RB_SET_BLACKRED(parent, gparent, field); \ 412 RB_ROTATE_RIGHT(head, gparent, tmp, field); \ 413 } else { \ 414 tmp = RB_LEFT(gparent, field); \ 415 if (tmp && RB_COLOR(tmp, field) == RB_RED) { \ 416 RB_COLOR(tmp, field) = RB_BLACK; \ 417 RB_SET_BLACKRED(parent, gparent, field);\ 418 elm = gparent; \ 419 continue; \ 420 } \ 421 if (RB_LEFT(parent, field) == elm) { \ 422 RB_ROTATE_RIGHT(head, parent, tmp, field);\ 423 tmp = parent; \ 424 parent = elm; \ 425 elm = tmp; \ 426 } \ 427 RB_SET_BLACKRED(parent, gparent, field); \ 428 RB_ROTATE_LEFT(head, gparent, tmp, field); \ 429 } \ 430 } \ 431 RB_COLOR(head->rbh_root, field) = RB_BLACK; \ 432 } \ 433 \ 434 void \ 435 name##_RB_REMOVE_COLOR(struct name *head, struct type *parent, struct type *elm) \ 436 { \ 437 struct type *tmp; \ 438 while ((elm == NULL || RB_COLOR(elm, field) == RB_BLACK) && \ 439 elm != RB_ROOT(head)) { \ 440 if (RB_LEFT(parent, field) == elm) { \ 441 tmp = RB_RIGHT(parent, field); \ 442 if (RB_COLOR(tmp, field) == RB_RED) { \ 443 RB_SET_BLACKRED(tmp, parent, field); \ 444 RB_ROTATE_LEFT(head, parent, tmp, field);\ 445 tmp = RB_RIGHT(parent, field); \ 446 } \ 447 if ((RB_LEFT(tmp, field) == NULL || \ 448 RB_COLOR(RB_LEFT(tmp, field), field) == RB_BLACK) &&\ 449 (RB_RIGHT(tmp, field) == NULL || \ 450 RB_COLOR(RB_RIGHT(tmp, field), field) == RB_BLACK)) {\ 451 RB_COLOR(tmp, field) = RB_RED; \ 452 elm = parent; \ 453 parent = RB_PARENT(elm, field); \ 454 } else { \ 455 if (RB_RIGHT(tmp, field) == NULL || \ 456 RB_COLOR(RB_RIGHT(tmp, field), field) == RB_BLACK) {\ 457 struct type *oleft; \ 458 if ((oleft = RB_LEFT(tmp, field)))\ 459 RB_COLOR(oleft, field) = RB_BLACK;\ 460 RB_COLOR(tmp, field) = RB_RED; \ 461 RB_ROTATE_RIGHT(head, tmp, oleft, field);\ 462 tmp = RB_RIGHT(parent, field); \ 463 } \ 464 RB_COLOR(tmp, field) = RB_COLOR(parent, field);\ 465 RB_COLOR(parent, field) = RB_BLACK; \ 466 if (RB_RIGHT(tmp, field)) \ 467 RB_COLOR(RB_RIGHT(tmp, field), field) = RB_BLACK;\ 468 RB_ROTATE_LEFT(head, parent, tmp, field);\ 469 elm = RB_ROOT(head); \ 470 break; \ 471 } \ 472 } else { \ 473 tmp = RB_LEFT(parent, field); \ 474 if (RB_COLOR(tmp, field) == RB_RED) { \ 475 RB_SET_BLACKRED(tmp, parent, field); \ 476 RB_ROTATE_RIGHT(head, parent, tmp, field);\ 477 tmp = RB_LEFT(parent, field); \ 478 } \ 479 if ((RB_LEFT(tmp, field) == NULL || \ 480 RB_COLOR(RB_LEFT(tmp, field), field) == RB_BLACK) &&\ 481 (RB_RIGHT(tmp, field) == NULL || \ 482 RB_COLOR(RB_RIGHT(tmp, field), field) == RB_BLACK)) {\ 483 RB_COLOR(tmp, field) = RB_RED; \ 484 elm = parent; \ 485 parent = RB_PARENT(elm, field); \ 486 } else { \ 487 if (RB_LEFT(tmp, field) == NULL || \ 488 RB_COLOR(RB_LEFT(tmp, field), field) == RB_BLACK) {\ 489 struct type *oright; \ 490 if ((oright = RB_RIGHT(tmp, field)))\ 491 RB_COLOR(oright, field) = RB_BLACK;\ 492 RB_COLOR(tmp, field) = RB_RED; \ 493 RB_ROTATE_LEFT(head, tmp, oright, field);\ 494 tmp = RB_LEFT(parent, field); \ 495 } \ 496 RB_COLOR(tmp, field) = RB_COLOR(parent, field);\ 497 RB_COLOR(parent, field) = RB_BLACK; \ 498 if (RB_LEFT(tmp, field)) \ 499 RB_COLOR(RB_LEFT(tmp, field), field) = RB_BLACK;\ 500 RB_ROTATE_RIGHT(head, parent, tmp, field);\ 501 elm = RB_ROOT(head); \ 502 break; \ 503 } \ 504 } \ 505 } \ 506 if (elm) \ 507 RB_COLOR(elm, field) = RB_BLACK; \ 508 } \ 509 \ 510 struct type * \ 511 name##_RB_REMOVE(struct name *head, struct type *elm) \ 512 { \ 513 struct type *child, *parent, *old = elm; \ 514 int color; \ 515 if (RB_LEFT(elm, field) == NULL) \ 516 child = RB_RIGHT(elm, field); \ 517 else if (RB_RIGHT(elm, field) == NULL) \ 518 child = RB_LEFT(elm, field); \ 519 else { \ 520 struct type *left; \ 521 elm = RB_RIGHT(elm, field); \ 522 while ((left = RB_LEFT(elm, field))) \ 523 elm = left; \ 524 child = RB_RIGHT(elm, field); \ 525 parent = RB_PARENT(elm, field); \ 526 color = RB_COLOR(elm, field); \ 527 if (child) \ 528 RB_PARENT(child, field) = parent; \ 529 if (parent) { \ 530 if (RB_LEFT(parent, field) == elm) \ 531 RB_LEFT(parent, field) = child; \ 532 else \ 533 RB_RIGHT(parent, field) = child; \ 534 RB_AUGMENT(parent); \ 535 } else \ 536 RB_ROOT(head) = child; \ 537 if (RB_PARENT(elm, field) == old) \ 538 parent = elm; \ 539 (elm)->field = (old)->field; \ 540 if (RB_PARENT(old, field)) { \ 541 if (RB_LEFT(RB_PARENT(old, field), field) == old)\ 542 RB_LEFT(RB_PARENT(old, field), field) = elm;\ 543 else \ 544 RB_RIGHT(RB_PARENT(old, field), field) = elm;\ 545 RB_AUGMENT(RB_PARENT(old, field)); \ 546 } else \ 547 RB_ROOT(head) = elm; \ 548 RB_PARENT(RB_LEFT(old, field), field) = elm; \ 549 if (RB_RIGHT(old, field)) \ 550 RB_PARENT(RB_RIGHT(old, field), field) = elm; \ 551 if (parent) { \ 552 left = parent; \ 553 do { \ 554 RB_AUGMENT(left); \ 555 } while ((left = RB_PARENT(left, field))); \ 556 } \ 557 goto color; \ 558 } \ 559 parent = RB_PARENT(elm, field); \ 560 color = RB_COLOR(elm, field); \ 561 if (child) \ 562 RB_PARENT(child, field) = parent; \ 563 if (parent) { \ 564 if (RB_LEFT(parent, field) == elm) \ 565 RB_LEFT(parent, field) = child; \ 566 else \ 567 RB_RIGHT(parent, field) = child; \ 568 RB_AUGMENT(parent); \ 569 } else \ 570 RB_ROOT(head) = child; \ 571 color: \ 572 if (color == RB_BLACK) \ 573 name##_RB_REMOVE_COLOR(head, parent, child); \ 574 return (old); \ 575 } \ 576 \ 577 /* Inserts a node into the RB tree */ \ 578 struct type * \ 579 name##_RB_INSERT(struct name *head, struct type *elm) \ 580 { \ 581 struct type *tmp; \ 582 struct type *parent = NULL; \ 583 int comp = 0; \ 584 tmp = RB_ROOT(head); \ 585 while (tmp) { \ 586 parent = tmp; \ 587 comp = (cmp)(elm, parent); \ 588 if (comp < 0) \ 589 tmp = RB_LEFT(tmp, field); \ 590 else if (comp > 0) \ 591 tmp = RB_RIGHT(tmp, field); \ 592 else \ 593 return (tmp); \ 594 } \ 595 RB_SET(elm, parent, field); \ 596 if (parent != NULL) { \ 597 if (comp < 0) \ 598 RB_LEFT(parent, field) = elm; \ 599 else \ 600 RB_RIGHT(parent, field) = elm; \ 601 RB_AUGMENT(parent); \ 602 } else \ 603 RB_ROOT(head) = elm; \ 604 name##_RB_INSERT_COLOR(head, elm); \ 605 return (NULL); \ 606 } \ 607 \ 608 /* Finds the node with the same key as elm */ \ 609 struct type * \ 610 name##_RB_FIND(struct name *head, struct type *elm) \ 611 { \ 612 struct type *tmp = RB_ROOT(head); \ 613 int comp; \ 614 while (tmp) { \ 615 comp = cmp(elm, tmp); \ 616 if (comp < 0) \ 617 tmp = RB_LEFT(tmp, field); \ 618 else if (comp > 0) \ 619 tmp = RB_RIGHT(tmp, field); \ 620 else \ 621 return (tmp); \ 622 } \ 623 return (NULL); \ 624 } \ 625 \ 626 struct type * \ 627 name##_RB_NEXT(struct type *elm) \ 628 { \ 629 if (RB_RIGHT(elm, field)) { \ 630 elm = RB_RIGHT(elm, field); \ 631 while (RB_LEFT(elm, field)) \ 632 elm = RB_LEFT(elm, field); \ 633 } else { \ 634 if (RB_PARENT(elm, field) && \ 635 (elm == RB_LEFT(RB_PARENT(elm, field), field))) \ 636 elm = RB_PARENT(elm, field); \ 637 else { \ 638 while (RB_PARENT(elm, field) && \ 639 (elm == RB_RIGHT(RB_PARENT(elm, field), field)))\ 640 elm = RB_PARENT(elm, field); \ 641 elm = RB_PARENT(elm, field); \ 642 } \ 643 } \ 644 return (elm); \ 645 } \ 646 \ 647 struct type * \ 648 name##_RB_MINMAX(struct name *head, int val) \ 649 { \ 650 struct type *tmp = RB_ROOT(head); \ 651 struct type *parent = NULL; \ 652 while (tmp) { \ 653 parent = tmp; \ 654 if (val < 0) \ 655 tmp = RB_LEFT(tmp, field); \ 656 else \ 657 tmp = RB_RIGHT(tmp, field); \ 658 } \ 659 return (parent); \ 660 } 661 662 #define RB_NEGINF -1 663 #define RB_INF 1 664 665 #define RB_INSERT(name, x, y) name##_RB_INSERT(x, y) 666 #define RB_REMOVE(name, x, y) name##_RB_REMOVE(x, y) 667 #define RB_FIND(name, x, y) name##_RB_FIND(x, y) 668 #define RB_NEXT(name, x, y) name##_RB_NEXT(y) 669 #define RB_MIN(name, x) name##_RB_MINMAX(x, RB_NEGINF) 670 #define RB_MAX(name, x) name##_RB_MINMAX(x, RB_INF) 671 672 #define RB_FOREACH(x, name, head) \ 673 for ((x) = RB_MIN(name, head); \ 674 (x) != NULL; \ 675 (x) = name##_RB_NEXT(x)) 676 677 #endif /* _SYS_TREE_H_ */ 678 /* $OpenBSD: tree.h,v 1.7 2002/10/17 21:51:54 art Exp $ */ 679 /* 680 * Copyright 2002 Niels Provos <provos@citi.umich.edu> 681 * All rights reserved. 682 * 683 * Redistribution and use in source and binary forms, with or without 684 * modification, are permitted provided that the following conditions 685 * are met: 686 * 1. Redistributions of source code must retain the above copyright 687 * notice, this list of conditions and the following disclaimer. 688 * 2. Redistributions in binary form must reproduce the above copyright 689 * notice, this list of conditions and the following disclaimer in the 690 * documentation and/or other materials provided with the distribution. 691 * 692 * THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR 693 * IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES 694 * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED. 695 * IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT, 696 * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT 697 * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, 698 * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY 699 * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT 700 * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF 701 * THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. 702 */ 703 704 #ifndef _SYS_TREE_H_ 705 #define _SYS_TREE_H_ 706 707 /* 708 * This file defines data structures for different types of trees: 709 * splay trees and red-black trees. 710 * 711 * A splay tree is a self-organizing data structure. Every operation 712 * on the tree causes a splay to happen. The splay moves the requested 713 * node to the root of the tree and partly rebalances it. 714 * 715 * This has the benefit that request locality causes faster lookups as 716 * the requested nodes move to the top of the tree. On the other hand, 717 * every lookup causes memory writes. 718 * 719 * The Balance Theorem bounds the total access time for m operations 720 * and n inserts on an initially empty tree as O((m + n)lg n). The 721 * amortized cost for a sequence of m accesses to a splay tree is O(lg n); 722 * 723 * A red-black tree is a binary search tree with the node color as an 724 * extra attribute. It fulfills a set of conditions: 725 * - every search path from the root to a leaf consists of the 726 * same number of black nodes, 727 * - each red node (except for the root) has a black parent, 728 * - each leaf node is black. 729 * 730 * Every operation on a red-black tree is bounded as O(lg n). 731 * The maximum height of a red-black tree is 2lg (n+1). 732 */ 733 734 #define SPLAY_HEAD(name, type) \ 735 struct name { \ 736 struct type *sph_root; /* root of the tree */ \ 737 } 738 739 #define SPLAY_INITIALIZER(root) \ 740 { NULL } 741 742 #define SPLAY_INIT(root) do { \ 743 (root)->sph_root = NULL; \ 744 } while (0) 745 746 #define SPLAY_ENTRY(type) \ 747 struct { \ 748 struct type *spe_left; /* left element */ \ 749 struct type *spe_right; /* right element */ \ 750 } 751 752 #define SPLAY_LEFT(elm, field) (elm)->field.spe_left 753 #define SPLAY_RIGHT(elm, field) (elm)->field.spe_right 754 #define SPLAY_ROOT(head) (head)->sph_root 755 #define SPLAY_EMPTY(head) (SPLAY_ROOT(head) == NULL) 756 757 /* SPLAY_ROTATE_{LEFT,RIGHT} expect that tmp hold SPLAY_{RIGHT,LEFT} */ 758 #define SPLAY_ROTATE_RIGHT(head, tmp, field) do { \ 759 SPLAY_LEFT((head)->sph_root, field) = SPLAY_RIGHT(tmp, field); \ 760 SPLAY_RIGHT(tmp, field) = (head)->sph_root; \ 761 (head)->sph_root = tmp; \ 762 } while (0) 763 764 #define SPLAY_ROTATE_LEFT(head, tmp, field) do { \ 765 SPLAY_RIGHT((head)->sph_root, field) = SPLAY_LEFT(tmp, field); \ 766 SPLAY_LEFT(tmp, field) = (head)->sph_root; \ 767 (head)->sph_root = tmp; \ 768 } while (0) 769 770 #define SPLAY_LINKLEFT(head, tmp, field) do { \ 771 SPLAY_LEFT(tmp, field) = (head)->sph_root; \ 772 tmp = (head)->sph_root; \ 773 (head)->sph_root = SPLAY_LEFT((head)->sph_root, field); \ 774 } while (0) 775 776 #define SPLAY_LINKRIGHT(head, tmp, field) do { \ 777 SPLAY_RIGHT(tmp, field) = (head)->sph_root; \ 778 tmp = (head)->sph_root; \ 779 (head)->sph_root = SPLAY_RIGHT((head)->sph_root, field); \ 780 } while (0) 781 782 #define SPLAY_ASSEMBLE(head, node, left, right, field) do { \ 783 SPLAY_RIGHT(left, field) = SPLAY_LEFT((head)->sph_root, field); \ 784 SPLAY_LEFT(right, field) = SPLAY_RIGHT((head)->sph_root, field);\ 785 SPLAY_LEFT((head)->sph_root, field) = SPLAY_RIGHT(node, field); \ 786 SPLAY_RIGHT((head)->sph_root, field) = SPLAY_LEFT(node, field); \ 787 } while (0) 788 789 /* Generates prototypes and inline functions */ 790 791 #define SPLAY_PROTOTYPE(name, type, field, cmp) \ 792 void name##_SPLAY(struct name *, struct type *); \ 793 void name##_SPLAY_MINMAX(struct name *, int); \ 794 struct type *name##_SPLAY_INSERT(struct name *, struct type *); \ 795 struct type *name##_SPLAY_REMOVE(struct name *, struct type *); \ 796 \ 797 /* Finds the node with the same key as elm */ \ 798 static __inline struct type * \ 799 name##_SPLAY_FIND(struct name *head, struct type *elm) \ 800 { \ 801 if (SPLAY_EMPTY(head)) \ 802 return(NULL); \ 803 name##_SPLAY(head, elm); \ 804 if ((cmp)(elm, (head)->sph_root) == 0) \ 805 return (head->sph_root); \ 806 return (NULL); \ 807 } \ 808 \ 809 static __inline struct type * \ 810 name##_SPLAY_NEXT(struct name *head, struct type *elm) \ 811 { \ 812 name##_SPLAY(head, elm); \ 813 if (SPLAY_RIGHT(elm, field) != NULL) { \ 814 elm = SPLAY_RIGHT(elm, field); \ 815 while (SPLAY_LEFT(elm, field) != NULL) { \ 816 elm = SPLAY_LEFT(elm, field); \ 817 } \ 818 } else \ 819 elm = NULL; \ 820 return (elm); \ 821 } \ 822 \ 823 static __inline struct type * \ 824 name##_SPLAY_MIN_MAX(struct name *head, int val) \ 825 { \ 826 name##_SPLAY_MINMAX(head, val); \ 827 return (SPLAY_ROOT(head)); \ 828 } 829 830 /* Main splay operation. 831 * Moves node close to the key of elm to top 832 */ 833 #define SPLAY_GENERATE(name, type, field, cmp) \ 834 struct type * \ 835 name##_SPLAY_INSERT(struct name *head, struct type *elm) \ 836 { \ 837 if (SPLAY_EMPTY(head)) { \ 838 SPLAY_LEFT(elm, field) = SPLAY_RIGHT(elm, field) = NULL; \ 839 } else { \ 840 int __comp; \ 841 name##_SPLAY(head, elm); \ 842 __comp = (cmp)(elm, (head)->sph_root); \ 843 if(__comp < 0) { \ 844 SPLAY_LEFT(elm, field) = SPLAY_LEFT((head)->sph_root, field);\ 845 SPLAY_RIGHT(elm, field) = (head)->sph_root; \ 846 SPLAY_LEFT((head)->sph_root, field) = NULL; \ 847 } else if (__comp > 0) { \ 848 SPLAY_RIGHT(elm, field) = SPLAY_RIGHT((head)->sph_root, field);\ 849 SPLAY_LEFT(elm, field) = (head)->sph_root; \ 850 SPLAY_RIGHT((head)->sph_root, field) = NULL; \ 851 } else \ 852 return ((head)->sph_root); \ 853 } \ 854 (head)->sph_root = (elm); \ 855 return (NULL); \ 856 } \ 857 \ 858 struct type * \ 859 name##_SPLAY_REMOVE(struct name *head, struct type *elm) \ 860 { \ 861 struct type *__tmp; \ 862 if (SPLAY_EMPTY(head)) \ 863 return (NULL); \ 864 name##_SPLAY(head, elm); \ 865 if ((cmp)(elm, (head)->sph_root) == 0) { \ 866 if (SPLAY_LEFT((head)->sph_root, field) == NULL) { \ 867 (head)->sph_root = SPLAY_RIGHT((head)->sph_root, field);\ 868 } else { \ 869 __tmp = SPLAY_RIGHT((head)->sph_root, field); \ 870 (head)->sph_root = SPLAY_LEFT((head)->sph_root, field);\ 871 name##_SPLAY(head, elm); \ 872 SPLAY_RIGHT((head)->sph_root, field) = __tmp; \ 873 } \ 874 return (elm); \ 875 } \ 876 return (NULL); \ 877 } \ 878 \ 879 void \ 880 name##_SPLAY(struct name *head, struct type *elm) \ 881 { \ 882 struct type __node, *__left, *__right, *__tmp; \ 883 int __comp; \ 884 \ 885 SPLAY_LEFT(&__node, field) = SPLAY_RIGHT(&__node, field) = NULL;\ 886 __left = __right = &__node; \ 887 \ 888 while ((__comp = (cmp)(elm, (head)->sph_root))) { \ 889 if (__comp < 0) { \ 890 __tmp = SPLAY_LEFT((head)->sph_root, field); \ 891 if (__tmp == NULL) \ 892 break; \ 893 if ((cmp)(elm, __tmp) < 0){ \ 894 SPLAY_ROTATE_RIGHT(head, __tmp, field); \ 895 if (SPLAY_LEFT((head)->sph_root, field) == NULL)\ 896 break; \ 897 } \ 898 SPLAY_LINKLEFT(head, __right, field); \ 899 } else if (__comp > 0) { \ 900 __tmp = SPLAY_RIGHT((head)->sph_root, field); \ 901 if (__tmp == NULL) \ 902 break; \ 903 if ((cmp)(elm, __tmp) > 0){ \ 904 SPLAY_ROTATE_LEFT(head, __tmp, field); \ 905 if (SPLAY_RIGHT((head)->sph_root, field) == NULL)\ 906 break; \ 907 } \ 908 SPLAY_LINKRIGHT(head, __left, field); \ 909 } \ 910 } \ 911 SPLAY_ASSEMBLE(head, &__node, __left, __right, field); \ 912 } \ 913 \ 914 /* Splay with either the minimum or the maximum element \ 915 * Used to find minimum or maximum element in tree. \ 916 */ \ 917 void name##_SPLAY_MINMAX(struct name *head, int __comp) \ 918 { \ 919 struct type __node, *__left, *__right, *__tmp; \ 920 \ 921 SPLAY_LEFT(&__node, field) = SPLAY_RIGHT(&__node, field) = NULL;\ 922 __left = __right = &__node; \ 923 \ 924 while (1) { \ 925 if (__comp < 0) { \ 926 __tmp = SPLAY_LEFT((head)->sph_root, field); \ 927 if (__tmp == NULL) \ 928 break; \ 929 if (__comp < 0){ \ 930 SPLAY_ROTATE_RIGHT(head, __tmp, field); \ 931 if (SPLAY_LEFT((head)->sph_root, field) == NULL)\ 932 break; \ 933 } \ 934 SPLAY_LINKLEFT(head, __right, field); \ 935 } else if (__comp > 0) { \ 936 __tmp = SPLAY_RIGHT((head)->sph_root, field); \ 937 if (__tmp == NULL) \ 938 break; \ 939 if (__comp > 0) { \ 940 SPLAY_ROTATE_LEFT(head, __tmp, field); \ 941 if (SPLAY_RIGHT((head)->sph_root, field) == NULL)\ 942 break; \ 943 } \ 944 SPLAY_LINKRIGHT(head, __left, field); \ 945 } \ 946 } \ 947 SPLAY_ASSEMBLE(head, &__node, __left, __right, field); \ 948 } 949 950 #define SPLAY_NEGINF -1 951 #define SPLAY_INF 1 952 953 #define SPLAY_INSERT(name, x, y) name##_SPLAY_INSERT(x, y) 954 #define SPLAY_REMOVE(name, x, y) name##_SPLAY_REMOVE(x, y) 955 #define SPLAY_FIND(name, x, y) name##_SPLAY_FIND(x, y) 956 #define SPLAY_NEXT(name, x, y) name##_SPLAY_NEXT(x, y) 957 #define SPLAY_MIN(name, x) (SPLAY_EMPTY(x) ? NULL \ 958 : name##_SPLAY_MIN_MAX(x, SPLAY_NEGINF)) 959 #define SPLAY_MAX(name, x) (SPLAY_EMPTY(x) ? NULL \ 960 : name##_SPLAY_MIN_MAX(x, SPLAY_INF)) 961 962 #define SPLAY_FOREACH(x, name, head) \ 963 for ((x) = SPLAY_MIN(name, head); \ 964 (x) != NULL; \ 965 (x) = SPLAY_NEXT(name, head, x)) 966 967 /* Macros that define a red-back tree */ 968 #define RB_HEAD(name, type) \ 969 struct name { \ 970 struct type *rbh_root; /* root of the tree */ \ 971 } 972 973 #define RB_INITIALIZER(root) \ 974 { NULL } 975 976 #define RB_INIT(root) do { \ 977 (root)->rbh_root = NULL; \ 978 } while (0) 979 980 #define RB_BLACK 0 981 #define RB_RED 1 982 #define RB_ENTRY(type) \ 983 struct { \ 984 struct type *rbe_left; /* left element */ \ 985 struct type *rbe_right; /* right element */ \ 986 struct type *rbe_parent; /* parent element */ \ 987 int rbe_color; /* node color */ \ 988 } 989 990 #define RB_LEFT(elm, field) (elm)->field.rbe_left 991 #define RB_RIGHT(elm, field) (elm)->field.rbe_right 992 #define RB_PARENT(elm, field) (elm)->field.rbe_parent 993 #define RB_COLOR(elm, field) (elm)->field.rbe_color 994 #define RB_ROOT(head) (head)->rbh_root 995 #define RB_EMPTY(head) (RB_ROOT(head) == NULL) 996 997 #define RB_SET(elm, parent, field) do { \ 998 RB_PARENT(elm, field) = parent; \ 999 RB_LEFT(elm, field) = RB_RIGHT(elm, field) = NULL; \ 1000 RB_COLOR(elm, field) = RB_RED; \ 1001 } while (0) 1002 1003 #define RB_SET_BLACKRED(black, red, field) do { \ 1004 RB_COLOR(black, field) = RB_BLACK; \ 1005 RB_COLOR(red, field) = RB_RED; \ 1006 } while (0) 1007 1008 #ifndef RB_AUGMENT 1009 #define RB_AUGMENT(x) 1010 #endif 1011 1012 #define RB_ROTATE_LEFT(head, elm, tmp, field) do { \ 1013 (tmp) = RB_RIGHT(elm, field); \ 1014 if ((RB_RIGHT(elm, field) = RB_LEFT(tmp, field))) { \ 1015 RB_PARENT(RB_LEFT(tmp, field), field) = (elm); \ 1016 } \ 1017 RB_AUGMENT(elm); \ 1018 if ((RB_PARENT(tmp, field) = RB_PARENT(elm, field))) { \ 1019 if ((elm) == RB_LEFT(RB_PARENT(elm, field), field)) \ 1020 RB_LEFT(RB_PARENT(elm, field), field) = (tmp); \ 1021 else \ 1022 RB_RIGHT(RB_PARENT(elm, field), field) = (tmp); \ 1023 } else \ 1024 (head)->rbh_root = (tmp); \ 1025 RB_LEFT(tmp, field) = (elm); \ 1026 RB_PARENT(elm, field) = (tmp); \ 1027 RB_AUGMENT(tmp); \ 1028 if ((RB_PARENT(tmp, field))) \ 1029 RB_AUGMENT(RB_PARENT(tmp, field)); \ 1030 } while (0) 1031 1032 #define RB_ROTATE_RIGHT(head, elm, tmp, field) do { \ 1033 (tmp) = RB_LEFT(elm, field); \ 1034 if ((RB_LEFT(elm, field) = RB_RIGHT(tmp, field))) { \ 1035 RB_PARENT(RB_RIGHT(tmp, field), field) = (elm); \ 1036 } \ 1037 RB_AUGMENT(elm); \ 1038 if ((RB_PARENT(tmp, field) = RB_PARENT(elm, field))) { \ 1039 if ((elm) == RB_LEFT(RB_PARENT(elm, field), field)) \ 1040 RB_LEFT(RB_PARENT(elm, field), field) = (tmp); \ 1041 else \ 1042 RB_RIGHT(RB_PARENT(elm, field), field) = (tmp); \ 1043 } else \ 1044 (head)->rbh_root = (tmp); \ 1045 RB_RIGHT(tmp, field) = (elm); \ 1046 RB_PARENT(elm, field) = (tmp); \ 1047 RB_AUGMENT(tmp); \ 1048 if ((RB_PARENT(tmp, field))) \ 1049 RB_AUGMENT(RB_PARENT(tmp, field)); \ 1050 } while (0) 1051 1052 /* Generates prototypes and inline functions */ 1053 #define RB_PROTOTYPE(name, type, field, cmp) \ 1054 void name##_RB_INSERT_COLOR(struct name *, struct type *); \ 1055 void name##_RB_REMOVE_COLOR(struct name *, struct type *, struct type *);\ 1056 struct type *name##_RB_REMOVE(struct name *, struct type *); \ 1057 struct type *name##_RB_INSERT(struct name *, struct type *); \ 1058 struct type *name##_RB_FIND(struct name *, struct type *); \ 1059 struct type *name##_RB_NEXT(struct type *); \ 1060 struct type *name##_RB_MINMAX(struct name *, int); \ 1061 \ 1062 1063 /* Main rb operation. 1064 * Moves node close to the key of elm to top 1065 */ 1066 #define RB_GENERATE(name, type, field, cmp) \ 1067 void \ 1068 name##_RB_INSERT_COLOR(struct name *head, struct type *elm) \ 1069 { \ 1070 struct type *parent, *gparent, *tmp; \ 1071 while ((parent = RB_PARENT(elm, field)) && \ 1072 RB_COLOR(parent, field) == RB_RED) { \ 1073 gparent = RB_PARENT(parent, field); \ 1074 if (parent == RB_LEFT(gparent, field)) { \ 1075 tmp = RB_RIGHT(gparent, field); \ 1076 if (tmp && RB_COLOR(tmp, field) == RB_RED) { \ 1077 RB_COLOR(tmp, field) = RB_BLACK; \ 1078 RB_SET_BLACKRED(parent, gparent, field);\ 1079 elm = gparent; \ 1080 continue; \ 1081 } \ 1082 if (RB_RIGHT(parent, field) == elm) { \ 1083 RB_ROTATE_LEFT(head, parent, tmp, field);\ 1084 tmp = parent; \ 1085 parent = elm; \ 1086 elm = tmp; \ 1087 } \ 1088 RB_SET_BLACKRED(parent, gparent, field); \ 1089 RB_ROTATE_RIGHT(head, gparent, tmp, field); \ 1090 } else { \ 1091 tmp = RB_LEFT(gparent, field); \ 1092 if (tmp && RB_COLOR(tmp, field) == RB_RED) { \ 1093 RB_COLOR(tmp, field) = RB_BLACK; \ 1094 RB_SET_BLACKRED(parent, gparent, field);\ 1095 elm = gparent; \ 1096 continue; \ 1097 } \ 1098 if (RB_LEFT(parent, field) == elm) { \ 1099 RB_ROTATE_RIGHT(head, parent, tmp, field);\ 1100 tmp = parent; \ 1101 parent = elm; \ 1102 elm = tmp; \ 1103 } \ 1104 RB_SET_BLACKRED(parent, gparent, field); \ 1105 RB_ROTATE_LEFT(head, gparent, tmp, field); \ 1106 } \ 1107 } \ 1108 RB_COLOR(head->rbh_root, field) = RB_BLACK; \ 1109 } \ 1110 \ 1111 void \ 1112 name##_RB_REMOVE_COLOR(struct name *head, struct type *parent, struct type *elm) \ 1113 { \ 1114 struct type *tmp; \ 1115 while ((elm == NULL || RB_COLOR(elm, field) == RB_BLACK) && \ 1116 elm != RB_ROOT(head)) { \ 1117 if (RB_LEFT(parent, field) == elm) { \ 1118 tmp = RB_RIGHT(parent, field); \ 1119 if (RB_COLOR(tmp, field) == RB_RED) { \ 1120 RB_SET_BLACKRED(tmp, parent, field); \ 1121 RB_ROTATE_LEFT(head, parent, tmp, field);\ 1122 tmp = RB_RIGHT(parent, field); \ 1123 } \ 1124 if ((RB_LEFT(tmp, field) == NULL || \ 1125 RB_COLOR(RB_LEFT(tmp, field), field) == RB_BLACK) &&\ 1126 (RB_RIGHT(tmp, field) == NULL || \ 1127 RB_COLOR(RB_RIGHT(tmp, field), field) == RB_BLACK)) {\ 1128 RB_COLOR(tmp, field) = RB_RED; \ 1129 elm = parent; \ 1130 parent = RB_PARENT(elm, field); \ 1131 } else { \ 1132 if (RB_RIGHT(tmp, field) == NULL || \ 1133 RB_COLOR(RB_RIGHT(tmp, field), field) == RB_BLACK) {\ 1134 struct type *oleft; \ 1135 if ((oleft = RB_LEFT(tmp, field)))\ 1136 RB_COLOR(oleft, field) = RB_BLACK;\ 1137 RB_COLOR(tmp, field) = RB_RED; \ 1138 RB_ROTATE_RIGHT(head, tmp, oleft, field);\ 1139 tmp = RB_RIGHT(parent, field); \ 1140 } \ 1141 RB_COLOR(tmp, field) = RB_COLOR(parent, field);\ 1142 RB_COLOR(parent, field) = RB_BLACK; \ 1143 if (RB_RIGHT(tmp, field)) \ 1144 RB_COLOR(RB_RIGHT(tmp, field), field) = RB_BLACK;\ 1145 RB_ROTATE_LEFT(head, parent, tmp, field);\ 1146 elm = RB_ROOT(head); \ 1147 break; \ 1148 } \ 1149 } else { \ 1150 tmp = RB_LEFT(parent, field); \ 1151 if (RB_COLOR(tmp, field) == RB_RED) { \ 1152 RB_SET_BLACKRED(tmp, parent, field); \ 1153 RB_ROTATE_RIGHT(head, parent, tmp, field);\ 1154 tmp = RB_LEFT(parent, field); \ 1155 } \ 1156 if ((RB_LEFT(tmp, field) == NULL || \ 1157 RB_COLOR(RB_LEFT(tmp, field), field) == RB_BLACK) &&\ 1158 (RB_RIGHT(tmp, field) == NULL || \ 1159 RB_COLOR(RB_RIGHT(tmp, field), field) == RB_BLACK)) {\ 1160 RB_COLOR(tmp, field) = RB_RED; \ 1161 elm = parent; \ 1162 parent = RB_PARENT(elm, field); \ 1163 } else { \ 1164 if (RB_LEFT(tmp, field) == NULL || \ 1165 RB_COLOR(RB_LEFT(tmp, field), field) == RB_BLACK) {\ 1166 struct type *oright; \ 1167 if ((oright = RB_RIGHT(tmp, field)))\ 1168 RB_COLOR(oright, field) = RB_BLACK;\ 1169 RB_COLOR(tmp, field) = RB_RED; \ 1170 RB_ROTATE_LEFT(head, tmp, oright, field);\ 1171 tmp = RB_LEFT(parent, field); \ 1172 } \ 1173 RB_COLOR(tmp, field) = RB_COLOR(parent, field);\ 1174 RB_COLOR(parent, field) = RB_BLACK; \ 1175 if (RB_LEFT(tmp, field)) \ 1176 RB_COLOR(RB_LEFT(tmp, field), field) = RB_BLACK;\ 1177 RB_ROTATE_RIGHT(head, parent, tmp, field);\ 1178 elm = RB_ROOT(head); \ 1179 break; \ 1180 } \ 1181 } \ 1182 } \ 1183 if (elm) \ 1184 RB_COLOR(elm, field) = RB_BLACK; \ 1185 } \ 1186 \ 1187 struct type * \ 1188 name##_RB_REMOVE(struct name *head, struct type *elm) \ 1189 { \ 1190 struct type *child, *parent, *old = elm; \ 1191 int color; \ 1192 if (RB_LEFT(elm, field) == NULL) \ 1193 child = RB_RIGHT(elm, field); \ 1194 else if (RB_RIGHT(elm, field) == NULL) \ 1195 child = RB_LEFT(elm, field); \ 1196 else { \ 1197 struct type *left; \ 1198 elm = RB_RIGHT(elm, field); \ 1199 while ((left = RB_LEFT(elm, field))) \ 1200 elm = left; \ 1201 child = RB_RIGHT(elm, field); \ 1202 parent = RB_PARENT(elm, field); \ 1203 color = RB_COLOR(elm, field); \ 1204 if (child) \ 1205 RB_PARENT(child, field) = parent; \ 1206 if (parent) { \ 1207 if (RB_LEFT(parent, field) == elm) \ 1208 RB_LEFT(parent, field) = child; \ 1209 else \ 1210 RB_RIGHT(parent, field) = child; \ 1211 RB_AUGMENT(parent); \ 1212 } else \ 1213 RB_ROOT(head) = child; \ 1214 if (RB_PARENT(elm, field) == old) \ 1215 parent = elm; \ 1216 (elm)->field = (old)->field; \ 1217 if (RB_PARENT(old, field)) { \ 1218 if (RB_LEFT(RB_PARENT(old, field), field) == old)\ 1219 RB_LEFT(RB_PARENT(old, field), field) = elm;\ 1220 else \ 1221 RB_RIGHT(RB_PARENT(old, field), field) = elm;\ 1222 RB_AUGMENT(RB_PARENT(old, field)); \ 1223 } else \ 1224 RB_ROOT(head) = elm; \ 1225 RB_PARENT(RB_LEFT(old, field), field) = elm; \ 1226 if (RB_RIGHT(old, field)) \ 1227 RB_PARENT(RB_RIGHT(old, field), field) = elm; \ 1228 if (parent) { \ 1229 left = parent; \ 1230 do { \ 1231 RB_AUGMENT(left); \ 1232 } while ((left = RB_PARENT(left, field))); \ 1233 } \ 1234 goto color; \ 1235 } \ 1236 parent = RB_PARENT(elm, field); \ 1237 color = RB_COLOR(elm, field); \ 1238 if (child) \ 1239 RB_PARENT(child, field) = parent; \ 1240 if (parent) { \ 1241 if (RB_LEFT(parent, field) == elm) \ 1242 RB_LEFT(parent, field) = child; \ 1243 else \ 1244 RB_RIGHT(parent, field) = child; \ 1245 RB_AUGMENT(parent); \ 1246 } else \ 1247 RB_ROOT(head) = child; \ 1248 color: \ 1249 if (color == RB_BLACK) \ 1250 name##_RB_REMOVE_COLOR(head, parent, child); \ 1251 return (old); \ 1252 } \ 1253 \ 1254 /* Inserts a node into the RB tree */ \ 1255 struct type * \ 1256 name##_RB_INSERT(struct name *head, struct type *elm) \ 1257 { \ 1258 struct type *tmp; \ 1259 struct type *parent = NULL; \ 1260 int comp = 0; \ 1261 tmp = RB_ROOT(head); \ 1262 while (tmp) { \ 1263 parent = tmp; \ 1264 comp = (cmp)(elm, parent); \ 1265 if (comp < 0) \ 1266 tmp = RB_LEFT(tmp, field); \ 1267 else if (comp > 0) \ 1268 tmp = RB_RIGHT(tmp, field); \ 1269 else \ 1270 return (tmp); \ 1271 } \ 1272 RB_SET(elm, parent, field); \ 1273 if (parent != NULL) { \ 1274 if (comp < 0) \ 1275 RB_LEFT(parent, field) = elm; \ 1276 else \ 1277 RB_RIGHT(parent, field) = elm; \ 1278 RB_AUGMENT(parent); \ 1279 } else \ 1280 RB_ROOT(head) = elm; \ 1281 name##_RB_INSERT_COLOR(head, elm); \ 1282 return (NULL); \ 1283 } \ 1284 \ 1285 /* Finds the node with the same key as elm */ \ 1286 struct type * \ 1287 name##_RB_FIND(struct name *head, struct type *elm) \ 1288 { \ 1289 struct type *tmp = RB_ROOT(head); \ 1290 int comp; \ 1291 while (tmp) { \ 1292 comp = cmp(elm, tmp); \ 1293 if (comp < 0) \ 1294 tmp = RB_LEFT(tmp, field); \ 1295 else if (comp > 0) \ 1296 tmp = RB_RIGHT(tmp, field); \ 1297 else \ 1298 return (tmp); \ 1299 } \ 1300 return (NULL); \ 1301 } \ 1302 \ 1303 struct type * \ 1304 name##_RB_NEXT(struct type *elm) \ 1305 { \ 1306 if (RB_RIGHT(elm, field)) { \ 1307 elm = RB_RIGHT(elm, field); \ 1308 while (RB_LEFT(elm, field)) \ 1309 elm = RB_LEFT(elm, field); \ 1310 } else { \ 1311 if (RB_PARENT(elm, field) && \ 1312 (elm == RB_LEFT(RB_PARENT(elm, field), field))) \ 1313 elm = RB_PARENT(elm, field); \ 1314 else { \ 1315 while (RB_PARENT(elm, field) && \ 1316 (elm == RB_RIGHT(RB_PARENT(elm, field), field)))\ 1317 elm = RB_PARENT(elm, field); \ 1318 elm = RB_PARENT(elm, field); \ 1319 } \ 1320 } \ 1321 return (elm); \ 1322 } \ 1323 \ 1324 struct type * \ 1325 name##_RB_MINMAX(struct name *head, int val) \ 1326 { \ 1327 struct type *tmp = RB_ROOT(head); \ 1328 struct type *parent = NULL; \ 1329 while (tmp) { \ 1330 parent = tmp; \ 1331 if (val < 0) \ 1332 tmp = RB_LEFT(tmp, field); \ 1333 else \ 1334 tmp = RB_RIGHT(tmp, field); \ 1335 } \ 1336 return (parent); \ 1337 } 1338 1339 #define RB_NEGINF -1 1340 #define RB_INF 1 1341 1342 #define RB_INSERT(name, x, y) name##_RB_INSERT(x, y) 1343 #define RB_REMOVE(name, x, y) name##_RB_REMOVE(x, y) 1344 #define RB_FIND(name, x, y) name##_RB_FIND(x, y) 1345 #define RB_NEXT(name, x, y) name##_RB_NEXT(y) 1346 #define RB_MIN(name, x) name##_RB_MINMAX(x, RB_NEGINF) 1347 #define RB_MAX(name, x) name##_RB_MINMAX(x, RB_INF) 1348 1349 #define RB_FOREACH(x, name, head) \ 1350 for ((x) = RB_MIN(name, head); \ 1351 (x) != NULL; \ 1352 (x) = name##_RB_NEXT(x)) 1353 1354 #endif /* _SYS_TREE_H_ */ 1355