1 /* $OpenBSD: tree.h,v 1.13 2011/07/09 00:19:45 pirofti 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-black 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) do {} while (0) 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 RB_PROTOTYPE_INTERNAL(name, type, field, cmp,) 378 #define RB_PROTOTYPE_STATIC(name, type, field, cmp) \ 379 RB_PROTOTYPE_INTERNAL(name, type, field, cmp, __attribute__((__unused__)) static) 380 #define RB_PROTOTYPE_INTERNAL(name, type, field, cmp, attr) \ 381 attr void name##_RB_INSERT_COLOR(struct name *, struct type *); \ 382 attr void name##_RB_REMOVE_COLOR(struct name *, struct type *, struct type *);\ 383 attr struct type *name##_RB_REMOVE(struct name *, struct type *); \ 384 attr struct type *name##_RB_INSERT(struct name *, struct type *); \ 385 attr struct type *name##_RB_FIND(struct name *, struct type *); \ 386 attr struct type *name##_RB_NFIND(struct name *, struct type *); \ 387 attr struct type *name##_RB_NEXT(struct type *); \ 388 attr struct type *name##_RB_PREV(struct type *); \ 389 attr struct type *name##_RB_MINMAX(struct name *, int); \ 390 \ 391 392 /* Main rb operation. 393 * Moves node close to the key of elm to top 394 */ 395 #define RB_GENERATE(name, type, field, cmp) \ 396 RB_GENERATE_INTERNAL(name, type, field, cmp,) 397 #define RB_GENERATE_STATIC(name, type, field, cmp) \ 398 RB_GENERATE_INTERNAL(name, type, field, cmp, __attribute__((__unused__)) static) 399 #define RB_GENERATE_INTERNAL(name, type, field, cmp, attr) \ 400 attr void \ 401 name##_RB_INSERT_COLOR(struct name *head, struct type *elm) \ 402 { \ 403 struct type *parent, *gparent, *tmp; \ 404 while ((parent = RB_PARENT(elm, field)) && \ 405 RB_COLOR(parent, field) == RB_RED) { \ 406 gparent = RB_PARENT(parent, field); \ 407 if (parent == RB_LEFT(gparent, field)) { \ 408 tmp = RB_RIGHT(gparent, field); \ 409 if (tmp && RB_COLOR(tmp, field) == RB_RED) { \ 410 RB_COLOR(tmp, field) = RB_BLACK; \ 411 RB_SET_BLACKRED(parent, gparent, field);\ 412 elm = gparent; \ 413 continue; \ 414 } \ 415 if (RB_RIGHT(parent, field) == elm) { \ 416 RB_ROTATE_LEFT(head, parent, tmp, field);\ 417 tmp = parent; \ 418 parent = elm; \ 419 elm = tmp; \ 420 } \ 421 RB_SET_BLACKRED(parent, gparent, field); \ 422 RB_ROTATE_RIGHT(head, gparent, tmp, field); \ 423 } else { \ 424 tmp = RB_LEFT(gparent, field); \ 425 if (tmp && RB_COLOR(tmp, field) == RB_RED) { \ 426 RB_COLOR(tmp, field) = RB_BLACK; \ 427 RB_SET_BLACKRED(parent, gparent, field);\ 428 elm = gparent; \ 429 continue; \ 430 } \ 431 if (RB_LEFT(parent, field) == elm) { \ 432 RB_ROTATE_RIGHT(head, parent, tmp, field);\ 433 tmp = parent; \ 434 parent = elm; \ 435 elm = tmp; \ 436 } \ 437 RB_SET_BLACKRED(parent, gparent, field); \ 438 RB_ROTATE_LEFT(head, gparent, tmp, field); \ 439 } \ 440 } \ 441 RB_COLOR(head->rbh_root, field) = RB_BLACK; \ 442 } \ 443 \ 444 attr void \ 445 name##_RB_REMOVE_COLOR(struct name *head, struct type *parent, struct type *elm) \ 446 { \ 447 struct type *tmp; \ 448 while ((elm == NULL || RB_COLOR(elm, field) == RB_BLACK) && \ 449 elm != RB_ROOT(head)) { \ 450 if (RB_LEFT(parent, field) == elm) { \ 451 tmp = RB_RIGHT(parent, field); \ 452 if (RB_COLOR(tmp, field) == RB_RED) { \ 453 RB_SET_BLACKRED(tmp, parent, field); \ 454 RB_ROTATE_LEFT(head, parent, tmp, field);\ 455 tmp = RB_RIGHT(parent, field); \ 456 } \ 457 if ((RB_LEFT(tmp, field) == NULL || \ 458 RB_COLOR(RB_LEFT(tmp, field), field) == RB_BLACK) &&\ 459 (RB_RIGHT(tmp, field) == NULL || \ 460 RB_COLOR(RB_RIGHT(tmp, field), field) == RB_BLACK)) {\ 461 RB_COLOR(tmp, field) = RB_RED; \ 462 elm = parent; \ 463 parent = RB_PARENT(elm, field); \ 464 } else { \ 465 if (RB_RIGHT(tmp, field) == NULL || \ 466 RB_COLOR(RB_RIGHT(tmp, field), field) == RB_BLACK) {\ 467 struct type *oleft; \ 468 if ((oleft = RB_LEFT(tmp, field)))\ 469 RB_COLOR(oleft, field) = RB_BLACK;\ 470 RB_COLOR(tmp, field) = RB_RED; \ 471 RB_ROTATE_RIGHT(head, tmp, oleft, field);\ 472 tmp = RB_RIGHT(parent, field); \ 473 } \ 474 RB_COLOR(tmp, field) = RB_COLOR(parent, field);\ 475 RB_COLOR(parent, field) = RB_BLACK; \ 476 if (RB_RIGHT(tmp, field)) \ 477 RB_COLOR(RB_RIGHT(tmp, field), field) = RB_BLACK;\ 478 RB_ROTATE_LEFT(head, parent, tmp, field);\ 479 elm = RB_ROOT(head); \ 480 break; \ 481 } \ 482 } else { \ 483 tmp = RB_LEFT(parent, field); \ 484 if (RB_COLOR(tmp, field) == RB_RED) { \ 485 RB_SET_BLACKRED(tmp, parent, field); \ 486 RB_ROTATE_RIGHT(head, parent, tmp, field);\ 487 tmp = RB_LEFT(parent, field); \ 488 } \ 489 if ((RB_LEFT(tmp, field) == NULL || \ 490 RB_COLOR(RB_LEFT(tmp, field), field) == RB_BLACK) &&\ 491 (RB_RIGHT(tmp, field) == NULL || \ 492 RB_COLOR(RB_RIGHT(tmp, field), field) == RB_BLACK)) {\ 493 RB_COLOR(tmp, field) = RB_RED; \ 494 elm = parent; \ 495 parent = RB_PARENT(elm, field); \ 496 } else { \ 497 if (RB_LEFT(tmp, field) == NULL || \ 498 RB_COLOR(RB_LEFT(tmp, field), field) == RB_BLACK) {\ 499 struct type *oright; \ 500 if ((oright = RB_RIGHT(tmp, field)))\ 501 RB_COLOR(oright, field) = RB_BLACK;\ 502 RB_COLOR(tmp, field) = RB_RED; \ 503 RB_ROTATE_LEFT(head, tmp, oright, field);\ 504 tmp = RB_LEFT(parent, field); \ 505 } \ 506 RB_COLOR(tmp, field) = RB_COLOR(parent, field);\ 507 RB_COLOR(parent, field) = RB_BLACK; \ 508 if (RB_LEFT(tmp, field)) \ 509 RB_COLOR(RB_LEFT(tmp, field), field) = RB_BLACK;\ 510 RB_ROTATE_RIGHT(head, parent, tmp, field);\ 511 elm = RB_ROOT(head); \ 512 break; \ 513 } \ 514 } \ 515 } \ 516 if (elm) \ 517 RB_COLOR(elm, field) = RB_BLACK; \ 518 } \ 519 \ 520 attr struct type * \ 521 name##_RB_REMOVE(struct name *head, struct type *elm) \ 522 { \ 523 struct type *child, *parent, *old = elm; \ 524 int color; \ 525 if (RB_LEFT(elm, field) == NULL) \ 526 child = RB_RIGHT(elm, field); \ 527 else if (RB_RIGHT(elm, field) == NULL) \ 528 child = RB_LEFT(elm, field); \ 529 else { \ 530 struct type *left; \ 531 elm = RB_RIGHT(elm, field); \ 532 while ((left = RB_LEFT(elm, field))) \ 533 elm = left; \ 534 child = RB_RIGHT(elm, field); \ 535 parent = RB_PARENT(elm, field); \ 536 color = RB_COLOR(elm, field); \ 537 if (child) \ 538 RB_PARENT(child, field) = parent; \ 539 if (parent) { \ 540 if (RB_LEFT(parent, field) == elm) \ 541 RB_LEFT(parent, field) = child; \ 542 else \ 543 RB_RIGHT(parent, field) = child; \ 544 RB_AUGMENT(parent); \ 545 } else \ 546 RB_ROOT(head) = child; \ 547 if (RB_PARENT(elm, field) == old) \ 548 parent = elm; \ 549 (elm)->field = (old)->field; \ 550 if (RB_PARENT(old, field)) { \ 551 if (RB_LEFT(RB_PARENT(old, field), field) == old)\ 552 RB_LEFT(RB_PARENT(old, field), field) = elm;\ 553 else \ 554 RB_RIGHT(RB_PARENT(old, field), field) = elm;\ 555 RB_AUGMENT(RB_PARENT(old, field)); \ 556 } else \ 557 RB_ROOT(head) = elm; \ 558 RB_PARENT(RB_LEFT(old, field), field) = elm; \ 559 if (RB_RIGHT(old, field)) \ 560 RB_PARENT(RB_RIGHT(old, field), field) = elm; \ 561 if (parent) { \ 562 left = parent; \ 563 do { \ 564 RB_AUGMENT(left); \ 565 } while ((left = RB_PARENT(left, field))); \ 566 } \ 567 goto color; \ 568 } \ 569 parent = RB_PARENT(elm, field); \ 570 color = RB_COLOR(elm, field); \ 571 if (child) \ 572 RB_PARENT(child, field) = parent; \ 573 if (parent) { \ 574 if (RB_LEFT(parent, field) == elm) \ 575 RB_LEFT(parent, field) = child; \ 576 else \ 577 RB_RIGHT(parent, field) = child; \ 578 RB_AUGMENT(parent); \ 579 } else \ 580 RB_ROOT(head) = child; \ 581 color: \ 582 if (color == RB_BLACK) \ 583 name##_RB_REMOVE_COLOR(head, parent, child); \ 584 return (old); \ 585 } \ 586 \ 587 /* Inserts a node into the RB tree */ \ 588 attr struct type * \ 589 name##_RB_INSERT(struct name *head, struct type *elm) \ 590 { \ 591 struct type *tmp; \ 592 struct type *parent = NULL; \ 593 int comp = 0; \ 594 tmp = RB_ROOT(head); \ 595 while (tmp) { \ 596 parent = tmp; \ 597 comp = (cmp)(elm, parent); \ 598 if (comp < 0) \ 599 tmp = RB_LEFT(tmp, field); \ 600 else if (comp > 0) \ 601 tmp = RB_RIGHT(tmp, field); \ 602 else \ 603 return (tmp); \ 604 } \ 605 RB_SET(elm, parent, field); \ 606 if (parent != NULL) { \ 607 if (comp < 0) \ 608 RB_LEFT(parent, field) = elm; \ 609 else \ 610 RB_RIGHT(parent, field) = elm; \ 611 RB_AUGMENT(parent); \ 612 } else \ 613 RB_ROOT(head) = elm; \ 614 name##_RB_INSERT_COLOR(head, elm); \ 615 return (NULL); \ 616 } \ 617 \ 618 /* Finds the node with the same key as elm */ \ 619 attr struct type * \ 620 name##_RB_FIND(struct name *head, struct type *elm) \ 621 { \ 622 struct type *tmp = RB_ROOT(head); \ 623 int comp; \ 624 while (tmp) { \ 625 comp = cmp(elm, tmp); \ 626 if (comp < 0) \ 627 tmp = RB_LEFT(tmp, field); \ 628 else if (comp > 0) \ 629 tmp = RB_RIGHT(tmp, field); \ 630 else \ 631 return (tmp); \ 632 } \ 633 return (NULL); \ 634 } \ 635 \ 636 /* Finds the first node greater than or equal to the search key */ \ 637 attr struct type * \ 638 name##_RB_NFIND(struct name *head, struct type *elm) \ 639 { \ 640 struct type *tmp = RB_ROOT(head); \ 641 struct type *res = NULL; \ 642 int comp; \ 643 while (tmp) { \ 644 comp = cmp(elm, tmp); \ 645 if (comp < 0) { \ 646 res = tmp; \ 647 tmp = RB_LEFT(tmp, field); \ 648 } \ 649 else if (comp > 0) \ 650 tmp = RB_RIGHT(tmp, field); \ 651 else \ 652 return (tmp); \ 653 } \ 654 return (res); \ 655 } \ 656 \ 657 /* ARGSUSED */ \ 658 attr struct type * \ 659 name##_RB_NEXT(struct type *elm) \ 660 { \ 661 if (RB_RIGHT(elm, field)) { \ 662 elm = RB_RIGHT(elm, field); \ 663 while (RB_LEFT(elm, field)) \ 664 elm = RB_LEFT(elm, field); \ 665 } else { \ 666 if (RB_PARENT(elm, field) && \ 667 (elm == RB_LEFT(RB_PARENT(elm, field), field))) \ 668 elm = RB_PARENT(elm, field); \ 669 else { \ 670 while (RB_PARENT(elm, field) && \ 671 (elm == RB_RIGHT(RB_PARENT(elm, field), field)))\ 672 elm = RB_PARENT(elm, field); \ 673 elm = RB_PARENT(elm, field); \ 674 } \ 675 } \ 676 return (elm); \ 677 } \ 678 \ 679 /* ARGSUSED */ \ 680 attr struct type * \ 681 name##_RB_PREV(struct type *elm) \ 682 { \ 683 if (RB_LEFT(elm, field)) { \ 684 elm = RB_LEFT(elm, field); \ 685 while (RB_RIGHT(elm, field)) \ 686 elm = RB_RIGHT(elm, field); \ 687 } else { \ 688 if (RB_PARENT(elm, field) && \ 689 (elm == RB_RIGHT(RB_PARENT(elm, field), field))) \ 690 elm = RB_PARENT(elm, field); \ 691 else { \ 692 while (RB_PARENT(elm, field) && \ 693 (elm == RB_LEFT(RB_PARENT(elm, field), field)))\ 694 elm = RB_PARENT(elm, field); \ 695 elm = RB_PARENT(elm, field); \ 696 } \ 697 } \ 698 return (elm); \ 699 } \ 700 \ 701 attr struct type * \ 702 name##_RB_MINMAX(struct name *head, int val) \ 703 { \ 704 struct type *tmp = RB_ROOT(head); \ 705 struct type *parent = NULL; \ 706 while (tmp) { \ 707 parent = tmp; \ 708 if (val < 0) \ 709 tmp = RB_LEFT(tmp, field); \ 710 else \ 711 tmp = RB_RIGHT(tmp, field); \ 712 } \ 713 return (parent); \ 714 } 715 716 #define RB_NEGINF -1 717 #define RB_INF 1 718 719 #define RB_INSERT(name, x, y) name##_RB_INSERT(x, y) 720 #define RB_REMOVE(name, x, y) name##_RB_REMOVE(x, y) 721 #define RB_FIND(name, x, y) name##_RB_FIND(x, y) 722 #define RB_NFIND(name, x, y) name##_RB_NFIND(x, y) 723 #define RB_NEXT(name, x, y) name##_RB_NEXT(y) 724 #define RB_PREV(name, x, y) name##_RB_PREV(y) 725 #define RB_MIN(name, x) name##_RB_MINMAX(x, RB_NEGINF) 726 #define RB_MAX(name, x) name##_RB_MINMAX(x, RB_INF) 727 728 #define RB_FOREACH(x, name, head) \ 729 for ((x) = RB_MIN(name, head); \ 730 (x) != NULL; \ 731 (x) = name##_RB_NEXT(x)) 732 733 #define RB_FOREACH_SAFE(x, name, head, y) \ 734 for ((x) = RB_MIN(name, head); \ 735 ((x) != NULL) && ((y) = name##_RB_NEXT(x), 1); \ 736 (x) = (y)) 737 738 #define RB_FOREACH_REVERSE(x, name, head) \ 739 for ((x) = RB_MAX(name, head); \ 740 (x) != NULL; \ 741 (x) = name##_RB_PREV(x)) 742 743 #define RB_FOREACH_REVERSE_SAFE(x, name, head, y) \ 744 for ((x) = RB_MAX(name, head); \ 745 ((x) != NULL) && ((y) = name##_RB_PREV(x), 1); \ 746 (x) = (y)) 747 748 #endif /* _SYS_TREE_H_ */ 749