1 /* $NetBSD: tree.h,v 1.1.1.1 2013/04/11 16:43:33 christos 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 (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 (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 (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 (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 (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 (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 (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 (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 (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 (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 (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 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 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(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(x)) 677 678 #endif /* _SYS_TREE_H_ */ 679 /* $OpenBSD: tree.h,v 1.7 2002/10/17 21:51:54 art Exp $ */ 680 /* 681 * Copyright 2002 Niels Provos <provos@citi.umich.edu> 682 * All rights reserved. 683 * 684 * Redistribution and use in source and binary forms, with or without 685 * modification, are permitted provided that the following conditions 686 * are met: 687 * 1. Redistributions of source code must retain the above copyright 688 * notice, this list of conditions and the following disclaimer. 689 * 2. Redistributions in binary form must reproduce the above copyright 690 * notice, this list of conditions and the following disclaimer in the 691 * documentation and/or other materials provided with the distribution. 692 * 693 * THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR 694 * IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES 695 * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED. 696 * IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT, 697 * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT 698 * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, 699 * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY 700 * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT 701 * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF 702 * THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. 703 */ 704 705 #ifndef _SYS_TREE_H_ 706 #define _SYS_TREE_H_ 707 708 /* 709 * This file defines data structures for different types of trees: 710 * splay trees and red-black trees. 711 * 712 * A splay tree is a self-organizing data structure. Every operation 713 * on the tree causes a splay to happen. The splay moves the requested 714 * node to the root of the tree and partly rebalances it. 715 * 716 * This has the benefit that request locality causes faster lookups as 717 * the requested nodes move to the top of the tree. On the other hand, 718 * every lookup causes memory writes. 719 * 720 * The Balance Theorem bounds the total access time for m operations 721 * and n inserts on an initially empty tree as O((m + n)lg n). The 722 * amortized cost for a sequence of m accesses to a splay tree is O(lg n); 723 * 724 * A red-black tree is a binary search tree with the node color as an 725 * extra attribute. It fulfills a set of conditions: 726 * - every search path from the root to a leaf consists of the 727 * same number of black nodes, 728 * - each red node (except for the root) has a black parent, 729 * - each leaf node is black. 730 * 731 * Every operation on a red-black tree is bounded as O(lg n). 732 * The maximum height of a red-black tree is 2lg (n+1). 733 */ 734 735 #define SPLAY_HEAD(name, type) \ 736 struct name { \ 737 struct type *sph_root; /* root of the tree */ \ 738 } 739 740 #define SPLAY_INITIALIZER(root) \ 741 { NULL } 742 743 #define SPLAY_INIT(root) do { \ 744 (root)->sph_root = NULL; \ 745 } while (0) 746 747 #define SPLAY_ENTRY(type) \ 748 struct { \ 749 struct type *spe_left; /* left element */ \ 750 struct type *spe_right; /* right element */ \ 751 } 752 753 #define SPLAY_LEFT(elm, field) (elm)->field.spe_left 754 #define SPLAY_RIGHT(elm, field) (elm)->field.spe_right 755 #define SPLAY_ROOT(head) (head)->sph_root 756 #define SPLAY_EMPTY(head) (SPLAY_ROOT(head) == NULL) 757 758 /* SPLAY_ROTATE_{LEFT,RIGHT} expect that tmp hold SPLAY_{RIGHT,LEFT} */ 759 #define SPLAY_ROTATE_RIGHT(head, tmp, field) do { \ 760 SPLAY_LEFT((head)->sph_root, field) = SPLAY_RIGHT(tmp, field); \ 761 SPLAY_RIGHT(tmp, field) = (head)->sph_root; \ 762 (head)->sph_root = tmp; \ 763 } while (0) 764 765 #define SPLAY_ROTATE_LEFT(head, tmp, field) do { \ 766 SPLAY_RIGHT((head)->sph_root, field) = SPLAY_LEFT(tmp, field); \ 767 SPLAY_LEFT(tmp, field) = (head)->sph_root; \ 768 (head)->sph_root = tmp; \ 769 } while (0) 770 771 #define SPLAY_LINKLEFT(head, tmp, field) do { \ 772 SPLAY_LEFT(tmp, field) = (head)->sph_root; \ 773 tmp = (head)->sph_root; \ 774 (head)->sph_root = SPLAY_LEFT((head)->sph_root, field); \ 775 } while (0) 776 777 #define SPLAY_LINKRIGHT(head, tmp, field) do { \ 778 SPLAY_RIGHT(tmp, field) = (head)->sph_root; \ 779 tmp = (head)->sph_root; \ 780 (head)->sph_root = SPLAY_RIGHT((head)->sph_root, field); \ 781 } while (0) 782 783 #define SPLAY_ASSEMBLE(head, node, left, right, field) do { \ 784 SPLAY_RIGHT(left, field) = SPLAY_LEFT((head)->sph_root, field); \ 785 SPLAY_LEFT(right, field) = SPLAY_RIGHT((head)->sph_root, field);\ 786 SPLAY_LEFT((head)->sph_root, field) = SPLAY_RIGHT(node, field); \ 787 SPLAY_RIGHT((head)->sph_root, field) = SPLAY_LEFT(node, field); \ 788 } while (0) 789 790 /* Generates prototypes and inline functions */ 791 792 #define SPLAY_PROTOTYPE(name, type, field, cmp) \ 793 void name##_SPLAY(struct name *, struct type *); \ 794 void name##_SPLAY_MINMAX(struct name *, int); \ 795 struct type *name##_SPLAY_INSERT(struct name *, struct type *); \ 796 struct type *name##_SPLAY_REMOVE(struct name *, struct type *); \ 797 \ 798 /* Finds the node with the same key as elm */ \ 799 static __inline struct type * \ 800 name##_SPLAY_FIND(struct name *head, struct type *elm) \ 801 { \ 802 if (SPLAY_EMPTY(head)) \ 803 return(NULL); \ 804 name##_SPLAY(head, elm); \ 805 if ((cmp)(elm, (head)->sph_root) == 0) \ 806 return (head->sph_root); \ 807 return (NULL); \ 808 } \ 809 \ 810 static __inline struct type * \ 811 name##_SPLAY_NEXT(struct name *head, struct type *elm) \ 812 { \ 813 name##_SPLAY(head, elm); \ 814 if (SPLAY_RIGHT(elm, field) != NULL) { \ 815 elm = SPLAY_RIGHT(elm, field); \ 816 while (SPLAY_LEFT(elm, field) != NULL) { \ 817 elm = SPLAY_LEFT(elm, field); \ 818 } \ 819 } else \ 820 elm = NULL; \ 821 return (elm); \ 822 } \ 823 \ 824 static __inline struct type * \ 825 name##_SPLAY_MIN_MAX(struct name *head, int val) \ 826 { \ 827 name##_SPLAY_MINMAX(head, val); \ 828 return (SPLAY_ROOT(head)); \ 829 } 830 831 /* Main splay operation. 832 * Moves node close to the key of elm to top 833 */ 834 #define SPLAY_GENERATE(name, type, field, cmp) \ 835 struct type * \ 836 name##_SPLAY_INSERT(struct name *head, struct type *elm) \ 837 { \ 838 if (SPLAY_EMPTY(head)) { \ 839 SPLAY_LEFT(elm, field) = SPLAY_RIGHT(elm, field) = NULL; \ 840 } else { \ 841 int __comp; \ 842 name##_SPLAY(head, elm); \ 843 __comp = (cmp)(elm, (head)->sph_root); \ 844 if(__comp < 0) { \ 845 SPLAY_LEFT(elm, field) = SPLAY_LEFT((head)->sph_root, field);\ 846 SPLAY_RIGHT(elm, field) = (head)->sph_root; \ 847 SPLAY_LEFT((head)->sph_root, field) = NULL; \ 848 } else if (__comp > 0) { \ 849 SPLAY_RIGHT(elm, field) = SPLAY_RIGHT((head)->sph_root, field);\ 850 SPLAY_LEFT(elm, field) = (head)->sph_root; \ 851 SPLAY_RIGHT((head)->sph_root, field) = NULL; \ 852 } else \ 853 return ((head)->sph_root); \ 854 } \ 855 (head)->sph_root = (elm); \ 856 return (NULL); \ 857 } \ 858 \ 859 struct type * \ 860 name##_SPLAY_REMOVE(struct name *head, struct type *elm) \ 861 { \ 862 struct type *__tmp; \ 863 if (SPLAY_EMPTY(head)) \ 864 return (NULL); \ 865 name##_SPLAY(head, elm); \ 866 if ((cmp)(elm, (head)->sph_root) == 0) { \ 867 if (SPLAY_LEFT((head)->sph_root, field) == NULL) { \ 868 (head)->sph_root = SPLAY_RIGHT((head)->sph_root, field);\ 869 } else { \ 870 __tmp = SPLAY_RIGHT((head)->sph_root, field); \ 871 (head)->sph_root = SPLAY_LEFT((head)->sph_root, field);\ 872 name##_SPLAY(head, elm); \ 873 SPLAY_RIGHT((head)->sph_root, field) = __tmp; \ 874 } \ 875 return (elm); \ 876 } \ 877 return (NULL); \ 878 } \ 879 \ 880 void \ 881 name##_SPLAY(struct name *head, struct type *elm) \ 882 { \ 883 struct type __node, *__left, *__right, *__tmp; \ 884 int __comp; \ 885 \ 886 SPLAY_LEFT(&__node, field) = SPLAY_RIGHT(&__node, field) = NULL;\ 887 __left = __right = &__node; \ 888 \ 889 while ((__comp = (cmp)(elm, (head)->sph_root))) { \ 890 if (__comp < 0) { \ 891 __tmp = SPLAY_LEFT((head)->sph_root, field); \ 892 if (__tmp == NULL) \ 893 break; \ 894 if ((cmp)(elm, __tmp) < 0){ \ 895 SPLAY_ROTATE_RIGHT(head, __tmp, field); \ 896 if (SPLAY_LEFT((head)->sph_root, field) == NULL)\ 897 break; \ 898 } \ 899 SPLAY_LINKLEFT(head, __right, field); \ 900 } else if (__comp > 0) { \ 901 __tmp = SPLAY_RIGHT((head)->sph_root, field); \ 902 if (__tmp == NULL) \ 903 break; \ 904 if ((cmp)(elm, __tmp) > 0){ \ 905 SPLAY_ROTATE_LEFT(head, __tmp, field); \ 906 if (SPLAY_RIGHT((head)->sph_root, field) == NULL)\ 907 break; \ 908 } \ 909 SPLAY_LINKRIGHT(head, __left, field); \ 910 } \ 911 } \ 912 SPLAY_ASSEMBLE(head, &__node, __left, __right, field); \ 913 } \ 914 \ 915 /* Splay with either the minimum or the maximum element \ 916 * Used to find minimum or maximum element in tree. \ 917 */ \ 918 void name##_SPLAY_MINMAX(struct name *head, int __comp) \ 919 { \ 920 struct type __node, *__left, *__right, *__tmp; \ 921 \ 922 SPLAY_LEFT(&__node, field) = SPLAY_RIGHT(&__node, field) = NULL;\ 923 __left = __right = &__node; \ 924 \ 925 while (1) { \ 926 if (__comp < 0) { \ 927 __tmp = SPLAY_LEFT((head)->sph_root, field); \ 928 if (__tmp == NULL) \ 929 break; \ 930 if (__comp < 0){ \ 931 SPLAY_ROTATE_RIGHT(head, __tmp, field); \ 932 if (SPLAY_LEFT((head)->sph_root, field) == NULL)\ 933 break; \ 934 } \ 935 SPLAY_LINKLEFT(head, __right, field); \ 936 } else if (__comp > 0) { \ 937 __tmp = SPLAY_RIGHT((head)->sph_root, field); \ 938 if (__tmp == NULL) \ 939 break; \ 940 if (__comp > 0) { \ 941 SPLAY_ROTATE_LEFT(head, __tmp, field); \ 942 if (SPLAY_RIGHT((head)->sph_root, field) == NULL)\ 943 break; \ 944 } \ 945 SPLAY_LINKRIGHT(head, __left, field); \ 946 } \ 947 } \ 948 SPLAY_ASSEMBLE(head, &__node, __left, __right, field); \ 949 } 950 951 #define SPLAY_NEGINF -1 952 #define SPLAY_INF 1 953 954 #define SPLAY_INSERT(name, x, y) name##_SPLAY_INSERT(x, y) 955 #define SPLAY_REMOVE(name, x, y) name##_SPLAY_REMOVE(x, y) 956 #define SPLAY_FIND(name, x, y) name##_SPLAY_FIND(x, y) 957 #define SPLAY_NEXT(name, x, y) name##_SPLAY_NEXT(x, y) 958 #define SPLAY_MIN(name, x) (SPLAY_EMPTY(x) ? NULL \ 959 : name##_SPLAY_MIN_MAX(x, SPLAY_NEGINF)) 960 #define SPLAY_MAX(name, x) (SPLAY_EMPTY(x) ? NULL \ 961 : name##_SPLAY_MIN_MAX(x, SPLAY_INF)) 962 963 #define SPLAY_FOREACH(x, name, head) \ 964 for ((x) = SPLAY_MIN(name, head); \ 965 (x) != NULL; \ 966 (x) = SPLAY_NEXT(name, head, x)) 967 968 /* Macros that define a red-back tree */ 969 #define RB_HEAD(name, type) \ 970 struct name { \ 971 struct type *rbh_root; /* root of the tree */ \ 972 } 973 974 #define RB_INITIALIZER(root) \ 975 { NULL } 976 977 #define RB_INIT(root) do { \ 978 (root)->rbh_root = NULL; \ 979 } while (0) 980 981 #define RB_BLACK 0 982 #define RB_RED 1 983 #define RB_ENTRY(type) \ 984 struct { \ 985 struct type *rbe_left; /* left element */ \ 986 struct type *rbe_right; /* right element */ \ 987 struct type *rbe_parent; /* parent element */ \ 988 int rbe_color; /* node color */ \ 989 } 990 991 #define RB_LEFT(elm, field) (elm)->field.rbe_left 992 #define RB_RIGHT(elm, field) (elm)->field.rbe_right 993 #define RB_PARENT(elm, field) (elm)->field.rbe_parent 994 #define RB_COLOR(elm, field) (elm)->field.rbe_color 995 #define RB_ROOT(head) (head)->rbh_root 996 #define RB_EMPTY(head) (RB_ROOT(head) == NULL) 997 998 #define RB_SET(elm, parent, field) do { \ 999 RB_PARENT(elm, field) = parent; \ 1000 RB_LEFT(elm, field) = RB_RIGHT(elm, field) = NULL; \ 1001 RB_COLOR(elm, field) = RB_RED; \ 1002 } while (0) 1003 1004 #define RB_SET_BLACKRED(black, red, field) do { \ 1005 RB_COLOR(black, field) = RB_BLACK; \ 1006 RB_COLOR(red, field) = RB_RED; \ 1007 } while (0) 1008 1009 #ifndef RB_AUGMENT 1010 #define RB_AUGMENT(x) 1011 #endif 1012 1013 #define RB_ROTATE_LEFT(head, elm, tmp, field) do { \ 1014 (tmp) = RB_RIGHT(elm, field); \ 1015 if ((RB_RIGHT(elm, field) = RB_LEFT(tmp, field))) { \ 1016 RB_PARENT(RB_LEFT(tmp, field), field) = (elm); \ 1017 } \ 1018 RB_AUGMENT(elm); \ 1019 if ((RB_PARENT(tmp, field) = RB_PARENT(elm, field))) { \ 1020 if ((elm) == RB_LEFT(RB_PARENT(elm, field), field)) \ 1021 RB_LEFT(RB_PARENT(elm, field), field) = (tmp); \ 1022 else \ 1023 RB_RIGHT(RB_PARENT(elm, field), field) = (tmp); \ 1024 } else \ 1025 (head)->rbh_root = (tmp); \ 1026 RB_LEFT(tmp, field) = (elm); \ 1027 RB_PARENT(elm, field) = (tmp); \ 1028 RB_AUGMENT(tmp); \ 1029 if ((RB_PARENT(tmp, field))) \ 1030 RB_AUGMENT(RB_PARENT(tmp, field)); \ 1031 } while (0) 1032 1033 #define RB_ROTATE_RIGHT(head, elm, tmp, field) do { \ 1034 (tmp) = RB_LEFT(elm, field); \ 1035 if ((RB_LEFT(elm, field) = RB_RIGHT(tmp, field))) { \ 1036 RB_PARENT(RB_RIGHT(tmp, field), field) = (elm); \ 1037 } \ 1038 RB_AUGMENT(elm); \ 1039 if ((RB_PARENT(tmp, field) = RB_PARENT(elm, field))) { \ 1040 if ((elm) == RB_LEFT(RB_PARENT(elm, field), field)) \ 1041 RB_LEFT(RB_PARENT(elm, field), field) = (tmp); \ 1042 else \ 1043 RB_RIGHT(RB_PARENT(elm, field), field) = (tmp); \ 1044 } else \ 1045 (head)->rbh_root = (tmp); \ 1046 RB_RIGHT(tmp, field) = (elm); \ 1047 RB_PARENT(elm, field) = (tmp); \ 1048 RB_AUGMENT(tmp); \ 1049 if ((RB_PARENT(tmp, field))) \ 1050 RB_AUGMENT(RB_PARENT(tmp, field)); \ 1051 } while (0) 1052 1053 /* Generates prototypes and inline functions */ 1054 #define RB_PROTOTYPE(name, type, field, cmp) \ 1055 void name##_RB_INSERT_COLOR(struct name *, struct type *); \ 1056 void name##_RB_REMOVE_COLOR(struct name *, struct type *, struct type *);\ 1057 struct type *name##_RB_REMOVE(struct name *, struct type *); \ 1058 struct type *name##_RB_INSERT(struct name *, struct type *); \ 1059 struct type *name##_RB_FIND(struct name *, struct type *); \ 1060 struct type *name##_RB_NEXT(struct type *); \ 1061 struct type *name##_RB_MINMAX(struct name *, int); \ 1062 \ 1063 1064 /* Main rb operation. 1065 * Moves node close to the key of elm to top 1066 */ 1067 #define RB_GENERATE(name, type, field, cmp) \ 1068 void \ 1069 name##_RB_INSERT_COLOR(struct name *head, struct type *elm) \ 1070 { \ 1071 struct type *parent, *gparent, *tmp; \ 1072 while ((parent = RB_PARENT(elm, field)) && \ 1073 RB_COLOR(parent, field) == RB_RED) { \ 1074 gparent = RB_PARENT(parent, field); \ 1075 if (parent == RB_LEFT(gparent, field)) { \ 1076 tmp = RB_RIGHT(gparent, field); \ 1077 if (tmp && RB_COLOR(tmp, field) == RB_RED) { \ 1078 RB_COLOR(tmp, field) = RB_BLACK; \ 1079 RB_SET_BLACKRED(parent, gparent, field);\ 1080 elm = gparent; \ 1081 continue; \ 1082 } \ 1083 if (RB_RIGHT(parent, field) == elm) { \ 1084 RB_ROTATE_LEFT(head, parent, tmp, field);\ 1085 tmp = parent; \ 1086 parent = elm; \ 1087 elm = tmp; \ 1088 } \ 1089 RB_SET_BLACKRED(parent, gparent, field); \ 1090 RB_ROTATE_RIGHT(head, gparent, tmp, field); \ 1091 } else { \ 1092 tmp = RB_LEFT(gparent, field); \ 1093 if (tmp && RB_COLOR(tmp, field) == RB_RED) { \ 1094 RB_COLOR(tmp, field) = RB_BLACK; \ 1095 RB_SET_BLACKRED(parent, gparent, field);\ 1096 elm = gparent; \ 1097 continue; \ 1098 } \ 1099 if (RB_LEFT(parent, field) == elm) { \ 1100 RB_ROTATE_RIGHT(head, parent, tmp, field);\ 1101 tmp = parent; \ 1102 parent = elm; \ 1103 elm = tmp; \ 1104 } \ 1105 RB_SET_BLACKRED(parent, gparent, field); \ 1106 RB_ROTATE_LEFT(head, gparent, tmp, field); \ 1107 } \ 1108 } \ 1109 RB_COLOR(head->rbh_root, field) = RB_BLACK; \ 1110 } \ 1111 \ 1112 void \ 1113 name##_RB_REMOVE_COLOR(struct name *head, struct type *parent, struct type *elm) \ 1114 { \ 1115 struct type *tmp; \ 1116 while ((elm == NULL || RB_COLOR(elm, field) == RB_BLACK) && \ 1117 elm != RB_ROOT(head)) { \ 1118 if (RB_LEFT(parent, field) == elm) { \ 1119 tmp = RB_RIGHT(parent, field); \ 1120 if (RB_COLOR(tmp, field) == RB_RED) { \ 1121 RB_SET_BLACKRED(tmp, parent, field); \ 1122 RB_ROTATE_LEFT(head, parent, tmp, field);\ 1123 tmp = RB_RIGHT(parent, field); \ 1124 } \ 1125 if ((RB_LEFT(tmp, field) == NULL || \ 1126 RB_COLOR(RB_LEFT(tmp, field), field) == RB_BLACK) &&\ 1127 (RB_RIGHT(tmp, field) == NULL || \ 1128 RB_COLOR(RB_RIGHT(tmp, field), field) == RB_BLACK)) {\ 1129 RB_COLOR(tmp, field) = RB_RED; \ 1130 elm = parent; \ 1131 parent = RB_PARENT(elm, field); \ 1132 } else { \ 1133 if (RB_RIGHT(tmp, field) == NULL || \ 1134 RB_COLOR(RB_RIGHT(tmp, field), field) == RB_BLACK) {\ 1135 struct type *oleft; \ 1136 if ((oleft = RB_LEFT(tmp, field)))\ 1137 RB_COLOR(oleft, field) = RB_BLACK;\ 1138 RB_COLOR(tmp, field) = RB_RED; \ 1139 RB_ROTATE_RIGHT(head, tmp, oleft, field);\ 1140 tmp = RB_RIGHT(parent, field); \ 1141 } \ 1142 RB_COLOR(tmp, field) = RB_COLOR(parent, field);\ 1143 RB_COLOR(parent, field) = RB_BLACK; \ 1144 if (RB_RIGHT(tmp, field)) \ 1145 RB_COLOR(RB_RIGHT(tmp, field), field) = RB_BLACK;\ 1146 RB_ROTATE_LEFT(head, parent, tmp, field);\ 1147 elm = RB_ROOT(head); \ 1148 break; \ 1149 } \ 1150 } else { \ 1151 tmp = RB_LEFT(parent, field); \ 1152 if (RB_COLOR(tmp, field) == RB_RED) { \ 1153 RB_SET_BLACKRED(tmp, parent, field); \ 1154 RB_ROTATE_RIGHT(head, parent, tmp, field);\ 1155 tmp = RB_LEFT(parent, field); \ 1156 } \ 1157 if ((RB_LEFT(tmp, field) == NULL || \ 1158 RB_COLOR(RB_LEFT(tmp, field), field) == RB_BLACK) &&\ 1159 (RB_RIGHT(tmp, field) == NULL || \ 1160 RB_COLOR(RB_RIGHT(tmp, field), field) == RB_BLACK)) {\ 1161 RB_COLOR(tmp, field) = RB_RED; \ 1162 elm = parent; \ 1163 parent = RB_PARENT(elm, field); \ 1164 } else { \ 1165 if (RB_LEFT(tmp, field) == NULL || \ 1166 RB_COLOR(RB_LEFT(tmp, field), field) == RB_BLACK) {\ 1167 struct type *oright; \ 1168 if ((oright = RB_RIGHT(tmp, field)))\ 1169 RB_COLOR(oright, field) = RB_BLACK;\ 1170 RB_COLOR(tmp, field) = RB_RED; \ 1171 RB_ROTATE_LEFT(head, tmp, oright, field);\ 1172 tmp = RB_LEFT(parent, field); \ 1173 } \ 1174 RB_COLOR(tmp, field) = RB_COLOR(parent, field);\ 1175 RB_COLOR(parent, field) = RB_BLACK; \ 1176 if (RB_LEFT(tmp, field)) \ 1177 RB_COLOR(RB_LEFT(tmp, field), field) = RB_BLACK;\ 1178 RB_ROTATE_RIGHT(head, parent, tmp, field);\ 1179 elm = RB_ROOT(head); \ 1180 break; \ 1181 } \ 1182 } \ 1183 } \ 1184 if (elm) \ 1185 RB_COLOR(elm, field) = RB_BLACK; \ 1186 } \ 1187 \ 1188 struct type * \ 1189 name##_RB_REMOVE(struct name *head, struct type *elm) \ 1190 { \ 1191 struct type *child, *parent, *old = elm; \ 1192 int color; \ 1193 if (RB_LEFT(elm, field) == NULL) \ 1194 child = RB_RIGHT(elm, field); \ 1195 else if (RB_RIGHT(elm, field) == NULL) \ 1196 child = RB_LEFT(elm, field); \ 1197 else { \ 1198 struct type *left; \ 1199 elm = RB_RIGHT(elm, field); \ 1200 while ((left = RB_LEFT(elm, field))) \ 1201 elm = left; \ 1202 child = RB_RIGHT(elm, field); \ 1203 parent = RB_PARENT(elm, field); \ 1204 color = RB_COLOR(elm, field); \ 1205 if (child) \ 1206 RB_PARENT(child, field) = parent; \ 1207 if (parent) { \ 1208 if (RB_LEFT(parent, field) == elm) \ 1209 RB_LEFT(parent, field) = child; \ 1210 else \ 1211 RB_RIGHT(parent, field) = child; \ 1212 RB_AUGMENT(parent); \ 1213 } else \ 1214 RB_ROOT(head) = child; \ 1215 if (RB_PARENT(elm, field) == old) \ 1216 parent = elm; \ 1217 (elm)->field = (old)->field; \ 1218 if (RB_PARENT(old, field)) { \ 1219 if (RB_LEFT(RB_PARENT(old, field), field) == old)\ 1220 RB_LEFT(RB_PARENT(old, field), field) = elm;\ 1221 else \ 1222 RB_RIGHT(RB_PARENT(old, field), field) = elm;\ 1223 RB_AUGMENT(RB_PARENT(old, field)); \ 1224 } else \ 1225 RB_ROOT(head) = elm; \ 1226 RB_PARENT(RB_LEFT(old, field), field) = elm; \ 1227 if (RB_RIGHT(old, field)) \ 1228 RB_PARENT(RB_RIGHT(old, field), field) = elm; \ 1229 if (parent) { \ 1230 left = parent; \ 1231 do { \ 1232 RB_AUGMENT(left); \ 1233 } while ((left = RB_PARENT(left, field))); \ 1234 } \ 1235 goto color; \ 1236 } \ 1237 parent = RB_PARENT(elm, field); \ 1238 color = RB_COLOR(elm, field); \ 1239 if (child) \ 1240 RB_PARENT(child, field) = parent; \ 1241 if (parent) { \ 1242 if (RB_LEFT(parent, field) == elm) \ 1243 RB_LEFT(parent, field) = child; \ 1244 else \ 1245 RB_RIGHT(parent, field) = child; \ 1246 RB_AUGMENT(parent); \ 1247 } else \ 1248 RB_ROOT(head) = child; \ 1249 color: \ 1250 if (color == RB_BLACK) \ 1251 name##_RB_REMOVE_COLOR(head, parent, child); \ 1252 return (old); \ 1253 } \ 1254 \ 1255 /* Inserts a node into the RB tree */ \ 1256 struct type * \ 1257 name##_RB_INSERT(struct name *head, struct type *elm) \ 1258 { \ 1259 struct type *tmp; \ 1260 struct type *parent = NULL; \ 1261 int comp = 0; \ 1262 tmp = RB_ROOT(head); \ 1263 while (tmp) { \ 1264 parent = tmp; \ 1265 comp = (cmp)(elm, parent); \ 1266 if (comp < 0) \ 1267 tmp = RB_LEFT(tmp, field); \ 1268 else if (comp > 0) \ 1269 tmp = RB_RIGHT(tmp, field); \ 1270 else \ 1271 return (tmp); \ 1272 } \ 1273 RB_SET(elm, parent, field); \ 1274 if (parent != NULL) { \ 1275 if (comp < 0) \ 1276 RB_LEFT(parent, field) = elm; \ 1277 else \ 1278 RB_RIGHT(parent, field) = elm; \ 1279 RB_AUGMENT(parent); \ 1280 } else \ 1281 RB_ROOT(head) = elm; \ 1282 name##_RB_INSERT_COLOR(head, elm); \ 1283 return (NULL); \ 1284 } \ 1285 \ 1286 /* Finds the node with the same key as elm */ \ 1287 struct type * \ 1288 name##_RB_FIND(struct name *head, struct type *elm) \ 1289 { \ 1290 struct type *tmp = RB_ROOT(head); \ 1291 int comp; \ 1292 while (tmp) { \ 1293 comp = cmp(elm, tmp); \ 1294 if (comp < 0) \ 1295 tmp = RB_LEFT(tmp, field); \ 1296 else if (comp > 0) \ 1297 tmp = RB_RIGHT(tmp, field); \ 1298 else \ 1299 return (tmp); \ 1300 } \ 1301 return (NULL); \ 1302 } \ 1303 \ 1304 struct type * \ 1305 name##_RB_NEXT(struct type *elm) \ 1306 { \ 1307 if (RB_RIGHT(elm, field)) { \ 1308 elm = RB_RIGHT(elm, field); \ 1309 while (RB_LEFT(elm, field)) \ 1310 elm = RB_LEFT(elm, field); \ 1311 } else { \ 1312 if (RB_PARENT(elm, field) && \ 1313 (elm == RB_LEFT(RB_PARENT(elm, field), field))) \ 1314 elm = RB_PARENT(elm, field); \ 1315 else { \ 1316 while (RB_PARENT(elm, field) && \ 1317 (elm == RB_RIGHT(RB_PARENT(elm, field), field)))\ 1318 elm = RB_PARENT(elm, field); \ 1319 elm = RB_PARENT(elm, field); \ 1320 } \ 1321 } \ 1322 return (elm); \ 1323 } \ 1324 \ 1325 struct type * \ 1326 name##_RB_MINMAX(struct name *head, int val) \ 1327 { \ 1328 struct type *tmp = RB_ROOT(head); \ 1329 struct type *parent = NULL; \ 1330 while (tmp) { \ 1331 parent = tmp; \ 1332 if (val < 0) \ 1333 tmp = RB_LEFT(tmp, field); \ 1334 else \ 1335 tmp = RB_RIGHT(tmp, field); \ 1336 } \ 1337 return (parent); \ 1338 } 1339 1340 #define RB_NEGINF -1 1341 #define RB_INF 1 1342 1343 #define RB_INSERT(name, x, y) name##_RB_INSERT(x, y) 1344 #define RB_REMOVE(name, x, y) name##_RB_REMOVE(x, y) 1345 #define RB_FIND(name, x, y) name##_RB_FIND(x, y) 1346 #define RB_NEXT(name, x, y) name##_RB_NEXT(y) 1347 #define RB_MIN(name, x) name##_RB_MINMAX(x, RB_NEGINF) 1348 #define RB_MAX(name, x) name##_RB_MINMAX(x, RB_INF) 1349 1350 #define RB_FOREACH(x, name, head) \ 1351 for ((x) = RB_MIN(name, head); \ 1352 (x) != NULL; \ 1353 (x) = name##_RB_NEXT(x)) 1354 1355 #endif /* _SYS_TREE_H_ */ 1356