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