tree.h (26161B)
1 /* $NetBSD: tree.h,v 1.20 2013/09/14 13:20:45 joerg Exp $ */ 2 /* $OpenBSD: tree.h,v 1.13 2011/07/09 00:19:45 pirofti Exp $ */ 3 /* Modified by Void Linux. */ 4 /* 5 * Copyright 2002 Niels Provos <provos@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 #ifdef __GNUC__ 33 #define __GNUC_PREREQ__(x, y) \ 34 ((__GNUC__ == (x) && __GNUC_MINOR__ >= (y)) || \ 35 (__GNUC__ > (x))) 36 #else 37 #define __GNUC_PREREQ__(x, y) 0 38 #endif 39 40 #if __GNUC_PREREQ__(2, 7) || defined(__lint__) 41 #define _sys_tree_h_unused __attribute__((__unused__)) 42 #else 43 #define _sys_tree_h_unused /* delete */ 44 #endif 45 46 /* 47 * This file defines data structures for different types of trees: 48 * splay trees and red-black trees. 49 * 50 * A splay tree is a self-organizing data structure. Every operation 51 * on the tree causes a splay to happen. The splay moves the requested 52 * node to the root of the tree and partly rebalances it. 53 * 54 * This has the benefit that request locality causes faster lookups as 55 * the requested nodes move to the top of the tree. On the other hand, 56 * every lookup causes memory writes. 57 * 58 * The Balance Theorem bounds the total access time for m operations 59 * and n inserts on an initially empty tree as O((m + n)lg n). The 60 * amortized cost for a sequence of m accesses to a splay tree is O(lg n); 61 * 62 * A red-black tree is a binary search tree with the node color as an 63 * extra attribute. It fulfills a set of conditions: 64 * - every search path from the root to a leaf consists of the 65 * same number of black nodes, 66 * - each red node (except for the root) has a black parent, 67 * - each leaf node is black. 68 * 69 * Every operation on a red-black tree is bounded as O(lg n). 70 * The maximum height of a red-black tree is 2lg (n+1). 71 */ 72 73 #define SPLAY_HEAD(name, type) \ 74 struct name { \ 75 struct type *sph_root; /* root of the tree */ \ 76 } 77 78 #define SPLAY_INITIALIZER(root) \ 79 { NULL } 80 81 #define SPLAY_INIT(root) do { \ 82 (root)->sph_root = NULL; \ 83 } while (/*CONSTCOND*/ 0) 84 85 #define SPLAY_ENTRY(type) \ 86 struct { \ 87 struct type *spe_left; /* left element */ \ 88 struct type *spe_right; /* right element */ \ 89 } 90 91 #define SPLAY_LEFT(elm, field) (elm)->field.spe_left 92 #define SPLAY_RIGHT(elm, field) (elm)->field.spe_right 93 #define SPLAY_ROOT(head) (head)->sph_root 94 #define SPLAY_EMPTY(head) (SPLAY_ROOT(head) == NULL) 95 96 /* SPLAY_ROTATE_{LEFT,RIGHT} expect that tmp hold SPLAY_{RIGHT,LEFT} */ 97 #define SPLAY_ROTATE_RIGHT(head, tmp, field) do { \ 98 SPLAY_LEFT((head)->sph_root, field) = SPLAY_RIGHT(tmp, field); \ 99 SPLAY_RIGHT(tmp, field) = (head)->sph_root; \ 100 (head)->sph_root = tmp; \ 101 } while (/*CONSTCOND*/ 0) 102 103 #define SPLAY_ROTATE_LEFT(head, tmp, field) do { \ 104 SPLAY_RIGHT((head)->sph_root, field) = SPLAY_LEFT(tmp, field); \ 105 SPLAY_LEFT(tmp, field) = (head)->sph_root; \ 106 (head)->sph_root = tmp; \ 107 } while (/*CONSTCOND*/ 0) 108 109 #define SPLAY_LINKLEFT(head, tmp, field) do { \ 110 SPLAY_LEFT(tmp, field) = (head)->sph_root; \ 111 tmp = (head)->sph_root; \ 112 (head)->sph_root = SPLAY_LEFT((head)->sph_root, field); \ 113 } while (/*CONSTCOND*/ 0) 114 115 #define SPLAY_LINKRIGHT(head, tmp, field) do { \ 116 SPLAY_RIGHT(tmp, field) = (head)->sph_root; \ 117 tmp = (head)->sph_root; \ 118 (head)->sph_root = SPLAY_RIGHT((head)->sph_root, field); \ 119 } while (/*CONSTCOND*/ 0) 120 121 #define SPLAY_ASSEMBLE(head, node, left, right, field) do { \ 122 SPLAY_RIGHT(left, field) = SPLAY_LEFT((head)->sph_root, field); \ 123 SPLAY_LEFT(right, field) = SPLAY_RIGHT((head)->sph_root, field);\ 124 SPLAY_LEFT((head)->sph_root, field) = SPLAY_RIGHT(node, field); \ 125 SPLAY_RIGHT((head)->sph_root, field) = SPLAY_LEFT(node, field); \ 126 } while (/*CONSTCOND*/ 0) 127 128 /* Generates prototypes and inline functions */ 129 130 #define SPLAY_PROTOTYPE(name, type, field, cmp) \ 131 void name##_SPLAY(struct name *, struct type *); \ 132 void name##_SPLAY_MINMAX(struct name *, int); \ 133 struct type *name##_SPLAY_INSERT(struct name *, struct type *); \ 134 struct type *name##_SPLAY_REMOVE(struct name *, struct type *); \ 135 \ 136 /* Finds the node with the same key as elm */ \ 137 static __inline struct type * \ 138 name##_SPLAY_FIND(struct name *head, struct type *elm) \ 139 { \ 140 if (SPLAY_EMPTY(head)) \ 141 return(NULL); \ 142 name##_SPLAY(head, elm); \ 143 if ((cmp)(elm, (head)->sph_root) == 0) \ 144 return (head->sph_root); \ 145 return (NULL); \ 146 } \ 147 \ 148 static __inline _sys_tree_h_unused struct type * \ 149 name##_SPLAY_NEXT(struct name *head, struct type *elm) \ 150 { \ 151 name##_SPLAY(head, elm); \ 152 if (SPLAY_RIGHT(elm, field) != NULL) { \ 153 elm = SPLAY_RIGHT(elm, field); \ 154 while (SPLAY_LEFT(elm, field) != NULL) { \ 155 elm = SPLAY_LEFT(elm, field); \ 156 } \ 157 } else \ 158 elm = NULL; \ 159 return (elm); \ 160 } \ 161 \ 162 static _sys_tree_h_unused __inline struct type * \ 163 name##_SPLAY_MIN_MAX(struct name *head, int val) \ 164 { \ 165 name##_SPLAY_MINMAX(head, val); \ 166 return (SPLAY_ROOT(head)); \ 167 } 168 169 /* Main splay operation. 170 * Moves node close to the key of elm to top 171 */ 172 #define SPLAY_GENERATE(name, type, field, cmp) \ 173 struct type * \ 174 name##_SPLAY_INSERT(struct name *head, struct type *elm) \ 175 { \ 176 if (SPLAY_EMPTY(head)) { \ 177 SPLAY_LEFT(elm, field) = SPLAY_RIGHT(elm, field) = NULL; \ 178 } else { \ 179 int __comp; \ 180 name##_SPLAY(head, elm); \ 181 __comp = (cmp)(elm, (head)->sph_root); \ 182 if(__comp < 0) { \ 183 SPLAY_LEFT(elm, field) = SPLAY_LEFT((head)->sph_root, field);\ 184 SPLAY_RIGHT(elm, field) = (head)->sph_root; \ 185 SPLAY_LEFT((head)->sph_root, field) = NULL; \ 186 } else if (__comp > 0) { \ 187 SPLAY_RIGHT(elm, field) = SPLAY_RIGHT((head)->sph_root, field);\ 188 SPLAY_LEFT(elm, field) = (head)->sph_root; \ 189 SPLAY_RIGHT((head)->sph_root, field) = NULL; \ 190 } else \ 191 return ((head)->sph_root); \ 192 } \ 193 (head)->sph_root = (elm); \ 194 return (NULL); \ 195 } \ 196 \ 197 struct type * \ 198 name##_SPLAY_REMOVE(struct name *head, struct type *elm) \ 199 { \ 200 struct type *__tmp; \ 201 if (SPLAY_EMPTY(head)) \ 202 return (NULL); \ 203 name##_SPLAY(head, elm); \ 204 if ((cmp)(elm, (head)->sph_root) == 0) { \ 205 if (SPLAY_LEFT((head)->sph_root, field) == NULL) { \ 206 (head)->sph_root = SPLAY_RIGHT((head)->sph_root, field);\ 207 } else { \ 208 __tmp = SPLAY_RIGHT((head)->sph_root, field); \ 209 (head)->sph_root = SPLAY_LEFT((head)->sph_root, field);\ 210 name##_SPLAY(head, elm); \ 211 SPLAY_RIGHT((head)->sph_root, field) = __tmp; \ 212 } \ 213 return (elm); \ 214 } \ 215 return (NULL); \ 216 } \ 217 \ 218 void \ 219 name##_SPLAY(struct name *head, struct type *elm) \ 220 { \ 221 struct type __node, *__left, *__right, *__tmp; \ 222 int __comp; \ 223 \ 224 SPLAY_LEFT(&__node, field) = SPLAY_RIGHT(&__node, field) = NULL;\ 225 __left = __right = &__node; \ 226 \ 227 while ((__comp = (cmp)(elm, (head)->sph_root)) != 0) { \ 228 if (__comp < 0) { \ 229 __tmp = SPLAY_LEFT((head)->sph_root, field); \ 230 if (__tmp == NULL) \ 231 break; \ 232 if ((cmp)(elm, __tmp) < 0){ \ 233 SPLAY_ROTATE_RIGHT(head, __tmp, field); \ 234 if (SPLAY_LEFT((head)->sph_root, field) == NULL)\ 235 break; \ 236 } \ 237 SPLAY_LINKLEFT(head, __right, field); \ 238 } else if (__comp > 0) { \ 239 __tmp = SPLAY_RIGHT((head)->sph_root, field); \ 240 if (__tmp == NULL) \ 241 break; \ 242 if ((cmp)(elm, __tmp) > 0){ \ 243 SPLAY_ROTATE_LEFT(head, __tmp, field); \ 244 if (SPLAY_RIGHT((head)->sph_root, field) == NULL)\ 245 break; \ 246 } \ 247 SPLAY_LINKRIGHT(head, __left, field); \ 248 } \ 249 } \ 250 SPLAY_ASSEMBLE(head, &__node, __left, __right, field); \ 251 } \ 252 \ 253 /* Splay with either the minimum or the maximum element \ 254 * Used to find minimum or maximum element in tree. \ 255 */ \ 256 void name##_SPLAY_MINMAX(struct name *head, int __comp) \ 257 { \ 258 struct type __node, *__left, *__right, *__tmp; \ 259 \ 260 SPLAY_LEFT(&__node, field) = SPLAY_RIGHT(&__node, field) = NULL;\ 261 __left = __right = &__node; \ 262 \ 263 while (1) { \ 264 if (__comp < 0) { \ 265 __tmp = SPLAY_LEFT((head)->sph_root, field); \ 266 if (__tmp == NULL) \ 267 break; \ 268 if (__comp < 0){ \ 269 SPLAY_ROTATE_RIGHT(head, __tmp, field); \ 270 if (SPLAY_LEFT((head)->sph_root, field) == NULL)\ 271 break; \ 272 } \ 273 SPLAY_LINKLEFT(head, __right, field); \ 274 } else if (__comp > 0) { \ 275 __tmp = SPLAY_RIGHT((head)->sph_root, field); \ 276 if (__tmp == NULL) \ 277 break; \ 278 if (__comp > 0) { \ 279 SPLAY_ROTATE_LEFT(head, __tmp, field); \ 280 if (SPLAY_RIGHT((head)->sph_root, field) == NULL)\ 281 break; \ 282 } \ 283 SPLAY_LINKRIGHT(head, __left, field); \ 284 } \ 285 } \ 286 SPLAY_ASSEMBLE(head, &__node, __left, __right, field); \ 287 } 288 289 #define SPLAY_NEGINF -1 290 #define SPLAY_INF 1 291 292 #define SPLAY_INSERT(name, x, y) name##_SPLAY_INSERT(x, y) 293 #define SPLAY_REMOVE(name, x, y) name##_SPLAY_REMOVE(x, y) 294 #define SPLAY_FIND(name, x, y) name##_SPLAY_FIND(x, y) 295 #define SPLAY_NEXT(name, x, y) name##_SPLAY_NEXT(x, y) 296 #define SPLAY_MIN(name, x) (SPLAY_EMPTY(x) ? NULL \ 297 : name##_SPLAY_MIN_MAX(x, SPLAY_NEGINF)) 298 #define SPLAY_MAX(name, x) (SPLAY_EMPTY(x) ? NULL \ 299 : name##_SPLAY_MIN_MAX(x, SPLAY_INF)) 300 301 #define SPLAY_FOREACH(x, name, head) \ 302 for ((x) = SPLAY_MIN(name, head); \ 303 (x) != NULL; \ 304 (x) = SPLAY_NEXT(name, head, x)) 305 306 /* Macros that define a red-black tree */ 307 #define RB_HEAD(name, type) \ 308 struct name { \ 309 struct type *rbh_root; /* root of the tree */ \ 310 } 311 312 #define RB_INITIALIZER(root) \ 313 { NULL } 314 315 #define RB_INIT(root) do { \ 316 (root)->rbh_root = NULL; \ 317 } while (/*CONSTCOND*/ 0) 318 319 #define RB_BLACK 0 320 #define RB_RED 1 321 #define RB_ENTRY(type) \ 322 struct { \ 323 struct type *rbe_left; /* left element */ \ 324 struct type *rbe_right; /* right element */ \ 325 struct type *rbe_parent; /* parent element */ \ 326 int rbe_color; /* node color */ \ 327 } 328 329 #define RB_LEFT(elm, field) (elm)->field.rbe_left 330 #define RB_RIGHT(elm, field) (elm)->field.rbe_right 331 #define RB_PARENT(elm, field) (elm)->field.rbe_parent 332 #define RB_COLOR(elm, field) (elm)->field.rbe_color 333 #define RB_ROOT(head) (head)->rbh_root 334 #define RB_EMPTY(head) (RB_ROOT(head) == NULL) 335 336 #define RB_SET(elm, parent, field) do { \ 337 RB_PARENT(elm, field) = parent; \ 338 RB_LEFT(elm, field) = RB_RIGHT(elm, field) = NULL; \ 339 RB_COLOR(elm, field) = RB_RED; \ 340 } while (/*CONSTCOND*/ 0) 341 342 #define RB_SET_BLACKRED(black, red, field) do { \ 343 RB_COLOR(black, field) = RB_BLACK; \ 344 RB_COLOR(red, field) = RB_RED; \ 345 } while (/*CONSTCOND*/ 0) 346 347 #ifndef RB_AUGMENT 348 #define RB_AUGMENT(x) do {} while (/*CONSTCOND*/ 0) 349 #endif 350 351 #define RB_ROTATE_LEFT(head, elm, tmp, field) do { \ 352 (tmp) = RB_RIGHT(elm, field); \ 353 if ((RB_RIGHT(elm, field) = RB_LEFT(tmp, field)) != NULL) { \ 354 RB_PARENT(RB_LEFT(tmp, field), field) = (elm); \ 355 } \ 356 RB_AUGMENT(elm); \ 357 if ((RB_PARENT(tmp, field) = RB_PARENT(elm, field)) != NULL) { \ 358 if ((elm) == RB_LEFT(RB_PARENT(elm, field), field)) \ 359 RB_LEFT(RB_PARENT(elm, field), field) = (tmp); \ 360 else \ 361 RB_RIGHT(RB_PARENT(elm, field), field) = (tmp); \ 362 } else \ 363 (head)->rbh_root = (tmp); \ 364 RB_LEFT(tmp, field) = (elm); \ 365 RB_PARENT(elm, field) = (tmp); \ 366 RB_AUGMENT(tmp); \ 367 if ((RB_PARENT(tmp, field))) \ 368 RB_AUGMENT(RB_PARENT(tmp, field)); \ 369 } while (/*CONSTCOND*/ 0) 370 371 #define RB_ROTATE_RIGHT(head, elm, tmp, field) do { \ 372 (tmp) = RB_LEFT(elm, field); \ 373 if ((RB_LEFT(elm, field) = RB_RIGHT(tmp, field)) != NULL) { \ 374 RB_PARENT(RB_RIGHT(tmp, field), field) = (elm); \ 375 } \ 376 RB_AUGMENT(elm); \ 377 if ((RB_PARENT(tmp, field) = RB_PARENT(elm, field)) != NULL) { \ 378 if ((elm) == RB_LEFT(RB_PARENT(elm, field), field)) \ 379 RB_LEFT(RB_PARENT(elm, field), field) = (tmp); \ 380 else \ 381 RB_RIGHT(RB_PARENT(elm, field), field) = (tmp); \ 382 } else \ 383 (head)->rbh_root = (tmp); \ 384 RB_RIGHT(tmp, field) = (elm); \ 385 RB_PARENT(elm, field) = (tmp); \ 386 RB_AUGMENT(tmp); \ 387 if ((RB_PARENT(tmp, field))) \ 388 RB_AUGMENT(RB_PARENT(tmp, field)); \ 389 } while (/*CONSTCOND*/ 0) 390 391 /* Generates prototypes and inline functions */ 392 #define RB_PROTOTYPE(name, type, field, cmp) \ 393 RB_PROTOTYPE_INTERNAL(name, type, field, cmp,) 394 #define RB_PROTOTYPE_STATIC(name, type, field, cmp) \ 395 RB_PROTOTYPE_INTERNAL(name, type, field, cmp, _sys_tree_h_unused static) 396 #define RB_PROTOTYPE_INTERNAL(name, type, field, cmp, attr) \ 397 attr void name##_RB_INSERT_COLOR(struct name *, struct type *); \ 398 attr void name##_RB_REMOVE_COLOR(struct name *, struct type *, struct type *);\ 399 attr struct type *name##_RB_REMOVE(struct name *, struct type *); \ 400 attr struct type *name##_RB_INSERT(struct name *, struct type *); \ 401 attr struct type *name##_RB_FIND(struct name *, struct type *); \ 402 attr struct type *name##_RB_NFIND(struct name *, struct type *); \ 403 attr struct type *name##_RB_NEXT(struct type *); \ 404 attr struct type *name##_RB_PREV(struct type *); \ 405 attr struct type *name##_RB_MINMAX(struct name *, int); \ 406 \ 407 408 /* Main rb operation. 409 * Moves node close to the key of elm to top 410 */ 411 #define RB_GENERATE(name, type, field, cmp) \ 412 RB_GENERATE_INTERNAL(name, type, field, cmp,) 413 #define RB_GENERATE_STATIC(name, type, field, cmp) \ 414 RB_GENERATE_INTERNAL(name, type, field, cmp, _sys_tree_h_unused static) 415 #define RB_GENERATE_INTERNAL(name, type, field, cmp, attr) \ 416 attr void \ 417 name##_RB_INSERT_COLOR(struct name *head, struct type *elm) \ 418 { \ 419 struct type *parent, *gparent, *tmp; \ 420 while ((parent = RB_PARENT(elm, field)) != NULL && \ 421 RB_COLOR(parent, field) == RB_RED) { \ 422 gparent = RB_PARENT(parent, field); \ 423 if (parent == RB_LEFT(gparent, field)) { \ 424 tmp = RB_RIGHT(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_RIGHT(parent, field) == elm) { \ 432 RB_ROTATE_LEFT(head, parent, tmp, field);\ 433 tmp = parent; \ 434 parent = elm; \ 435 elm = tmp; \ 436 } \ 437 RB_SET_BLACKRED(parent, gparent, field); \ 438 RB_ROTATE_RIGHT(head, gparent, tmp, field); \ 439 } else { \ 440 tmp = RB_LEFT(gparent, field); \ 441 if (tmp && RB_COLOR(tmp, field) == RB_RED) { \ 442 RB_COLOR(tmp, field) = RB_BLACK; \ 443 RB_SET_BLACKRED(parent, gparent, field);\ 444 elm = gparent; \ 445 continue; \ 446 } \ 447 if (RB_LEFT(parent, field) == elm) { \ 448 RB_ROTATE_RIGHT(head, parent, tmp, field);\ 449 tmp = parent; \ 450 parent = elm; \ 451 elm = tmp; \ 452 } \ 453 RB_SET_BLACKRED(parent, gparent, field); \ 454 RB_ROTATE_LEFT(head, gparent, tmp, field); \ 455 } \ 456 } \ 457 RB_COLOR(head->rbh_root, field) = RB_BLACK; \ 458 } \ 459 \ 460 attr void \ 461 name##_RB_REMOVE_COLOR(struct name *head, struct type *parent, struct type *elm) \ 462 { \ 463 struct type *tmp; \ 464 while ((elm == NULL || RB_COLOR(elm, field) == RB_BLACK) && \ 465 elm != RB_ROOT(head)) { \ 466 if (RB_LEFT(parent, field) == elm) { \ 467 tmp = RB_RIGHT(parent, field); \ 468 if (RB_COLOR(tmp, field) == RB_RED) { \ 469 RB_SET_BLACKRED(tmp, parent, field); \ 470 RB_ROTATE_LEFT(head, parent, tmp, field);\ 471 tmp = RB_RIGHT(parent, field); \ 472 } \ 473 if ((RB_LEFT(tmp, field) == NULL || \ 474 RB_COLOR(RB_LEFT(tmp, field), field) == RB_BLACK) &&\ 475 (RB_RIGHT(tmp, field) == NULL || \ 476 RB_COLOR(RB_RIGHT(tmp, field), field) == RB_BLACK)) {\ 477 RB_COLOR(tmp, field) = RB_RED; \ 478 elm = parent; \ 479 parent = RB_PARENT(elm, field); \ 480 } else { \ 481 if (RB_RIGHT(tmp, field) == NULL || \ 482 RB_COLOR(RB_RIGHT(tmp, field), field) == RB_BLACK) {\ 483 struct type *oleft; \ 484 if ((oleft = RB_LEFT(tmp, field)) \ 485 != NULL) \ 486 RB_COLOR(oleft, field) = RB_BLACK;\ 487 RB_COLOR(tmp, field) = RB_RED; \ 488 RB_ROTATE_RIGHT(head, tmp, oleft, field);\ 489 tmp = RB_RIGHT(parent, field); \ 490 } \ 491 RB_COLOR(tmp, field) = RB_COLOR(parent, field);\ 492 RB_COLOR(parent, field) = RB_BLACK; \ 493 if (RB_RIGHT(tmp, field)) \ 494 RB_COLOR(RB_RIGHT(tmp, field), field) = RB_BLACK;\ 495 RB_ROTATE_LEFT(head, parent, tmp, field);\ 496 elm = RB_ROOT(head); \ 497 break; \ 498 } \ 499 } else { \ 500 tmp = RB_LEFT(parent, field); \ 501 if (RB_COLOR(tmp, field) == RB_RED) { \ 502 RB_SET_BLACKRED(tmp, parent, field); \ 503 RB_ROTATE_RIGHT(head, parent, tmp, field);\ 504 tmp = RB_LEFT(parent, field); \ 505 } \ 506 if ((RB_LEFT(tmp, field) == NULL || \ 507 RB_COLOR(RB_LEFT(tmp, field), field) == RB_BLACK) &&\ 508 (RB_RIGHT(tmp, field) == NULL || \ 509 RB_COLOR(RB_RIGHT(tmp, field), field) == RB_BLACK)) {\ 510 RB_COLOR(tmp, field) = RB_RED; \ 511 elm = parent; \ 512 parent = RB_PARENT(elm, field); \ 513 } else { \ 514 if (RB_LEFT(tmp, field) == NULL || \ 515 RB_COLOR(RB_LEFT(tmp, field), field) == RB_BLACK) {\ 516 struct type *oright; \ 517 if ((oright = RB_RIGHT(tmp, field)) \ 518 != NULL) \ 519 RB_COLOR(oright, field) = RB_BLACK;\ 520 RB_COLOR(tmp, field) = RB_RED; \ 521 RB_ROTATE_LEFT(head, tmp, oright, field);\ 522 tmp = RB_LEFT(parent, field); \ 523 } \ 524 RB_COLOR(tmp, field) = RB_COLOR(parent, field);\ 525 RB_COLOR(parent, field) = RB_BLACK; \ 526 if (RB_LEFT(tmp, field)) \ 527 RB_COLOR(RB_LEFT(tmp, field), field) = RB_BLACK;\ 528 RB_ROTATE_RIGHT(head, parent, tmp, field);\ 529 elm = RB_ROOT(head); \ 530 break; \ 531 } \ 532 } \ 533 } \ 534 if (elm) \ 535 RB_COLOR(elm, field) = RB_BLACK; \ 536 } \ 537 \ 538 attr struct type * \ 539 name##_RB_REMOVE(struct name *head, struct type *elm) \ 540 { \ 541 struct type *child, *parent, *old = elm; \ 542 int color; \ 543 if (RB_LEFT(elm, field) == NULL) \ 544 child = RB_RIGHT(elm, field); \ 545 else if (RB_RIGHT(elm, field) == NULL) \ 546 child = RB_LEFT(elm, field); \ 547 else { \ 548 struct type *left; \ 549 elm = RB_RIGHT(elm, field); \ 550 while ((left = RB_LEFT(elm, field)) != NULL) \ 551 elm = left; \ 552 child = RB_RIGHT(elm, field); \ 553 parent = RB_PARENT(elm, field); \ 554 color = RB_COLOR(elm, field); \ 555 if (child) \ 556 RB_PARENT(child, field) = parent; \ 557 if (parent) { \ 558 if (RB_LEFT(parent, field) == elm) \ 559 RB_LEFT(parent, field) = child; \ 560 else \ 561 RB_RIGHT(parent, field) = child; \ 562 RB_AUGMENT(parent); \ 563 } else \ 564 RB_ROOT(head) = child; \ 565 if (RB_PARENT(elm, field) == old) \ 566 parent = elm; \ 567 (elm)->field = (old)->field; \ 568 if (RB_PARENT(old, field)) { \ 569 if (RB_LEFT(RB_PARENT(old, field), field) == old)\ 570 RB_LEFT(RB_PARENT(old, field), field) = elm;\ 571 else \ 572 RB_RIGHT(RB_PARENT(old, field), field) = elm;\ 573 RB_AUGMENT(RB_PARENT(old, field)); \ 574 } else \ 575 RB_ROOT(head) = elm; \ 576 RB_PARENT(RB_LEFT(old, field), field) = elm; \ 577 if (RB_RIGHT(old, field)) \ 578 RB_PARENT(RB_RIGHT(old, field), field) = elm; \ 579 if (parent) { \ 580 left = parent; \ 581 do { \ 582 RB_AUGMENT(left); \ 583 } while ((left = RB_PARENT(left, field)) != NULL); \ 584 } \ 585 goto color; \ 586 } \ 587 parent = RB_PARENT(elm, field); \ 588 color = RB_COLOR(elm, field); \ 589 if (child) \ 590 RB_PARENT(child, field) = parent; \ 591 if (parent) { \ 592 if (RB_LEFT(parent, field) == elm) \ 593 RB_LEFT(parent, field) = child; \ 594 else \ 595 RB_RIGHT(parent, field) = child; \ 596 RB_AUGMENT(parent); \ 597 } else \ 598 RB_ROOT(head) = child; \ 599 color: \ 600 if (color == RB_BLACK) \ 601 name##_RB_REMOVE_COLOR(head, parent, child); \ 602 return (old); \ 603 } \ 604 \ 605 /* Inserts a node into the RB tree */ \ 606 attr struct type * \ 607 name##_RB_INSERT(struct name *head, struct type *elm) \ 608 { \ 609 struct type *tmp; \ 610 struct type *parent = NULL; \ 611 int comp = 0; \ 612 tmp = RB_ROOT(head); \ 613 while (tmp) { \ 614 parent = tmp; \ 615 comp = (cmp)(elm, parent); \ 616 if (comp < 0) \ 617 tmp = RB_LEFT(tmp, field); \ 618 else if (comp > 0) \ 619 tmp = RB_RIGHT(tmp, field); \ 620 else \ 621 return (tmp); \ 622 } \ 623 RB_SET(elm, parent, field); \ 624 if (parent != NULL) { \ 625 if (comp < 0) \ 626 RB_LEFT(parent, field) = elm; \ 627 else \ 628 RB_RIGHT(parent, field) = elm; \ 629 RB_AUGMENT(parent); \ 630 } else \ 631 RB_ROOT(head) = elm; \ 632 name##_RB_INSERT_COLOR(head, elm); \ 633 return (NULL); \ 634 } \ 635 \ 636 /* Finds the node with the same key as elm */ \ 637 attr struct type * \ 638 name##_RB_FIND(struct name *head, struct type *elm) \ 639 { \ 640 struct type *tmp = RB_ROOT(head); \ 641 int comp; \ 642 while (tmp) { \ 643 comp = cmp(elm, tmp); \ 644 if (comp < 0) \ 645 tmp = RB_LEFT(tmp, field); \ 646 else if (comp > 0) \ 647 tmp = RB_RIGHT(tmp, field); \ 648 else \ 649 return (tmp); \ 650 } \ 651 return (NULL); \ 652 } \ 653 \ 654 /* Finds the first node greater than or equal to the search key */ \ 655 attr struct type * \ 656 name##_RB_NFIND(struct name *head, struct type *elm) \ 657 { \ 658 struct type *tmp = RB_ROOT(head); \ 659 struct type *res = NULL; \ 660 int comp; \ 661 while (tmp) { \ 662 comp = cmp(elm, tmp); \ 663 if (comp < 0) { \ 664 res = tmp; \ 665 tmp = RB_LEFT(tmp, field); \ 666 } \ 667 else if (comp > 0) \ 668 tmp = RB_RIGHT(tmp, field); \ 669 else \ 670 return (tmp); \ 671 } \ 672 return (res); \ 673 } \ 674 \ 675 /* ARGSUSED */ \ 676 attr struct type * \ 677 name##_RB_NEXT(struct type *elm) \ 678 { \ 679 if (RB_RIGHT(elm, field)) { \ 680 elm = RB_RIGHT(elm, field); \ 681 while (RB_LEFT(elm, field)) \ 682 elm = RB_LEFT(elm, field); \ 683 } else { \ 684 if (RB_PARENT(elm, field) && \ 685 (elm == RB_LEFT(RB_PARENT(elm, field), field))) \ 686 elm = RB_PARENT(elm, field); \ 687 else { \ 688 while (RB_PARENT(elm, field) && \ 689 (elm == RB_RIGHT(RB_PARENT(elm, field), field)))\ 690 elm = RB_PARENT(elm, field); \ 691 elm = RB_PARENT(elm, field); \ 692 } \ 693 } \ 694 return (elm); \ 695 } \ 696 \ 697 /* ARGSUSED */ \ 698 attr struct type * \ 699 name##_RB_PREV(struct type *elm) \ 700 { \ 701 if (RB_LEFT(elm, field)) { \ 702 elm = RB_LEFT(elm, field); \ 703 while (RB_RIGHT(elm, field)) \ 704 elm = RB_RIGHT(elm, field); \ 705 } else { \ 706 if (RB_PARENT(elm, field) && \ 707 (elm == RB_RIGHT(RB_PARENT(elm, field), field))) \ 708 elm = RB_PARENT(elm, field); \ 709 else { \ 710 while (RB_PARENT(elm, field) && \ 711 (elm == RB_LEFT(RB_PARENT(elm, field), field)))\ 712 elm = RB_PARENT(elm, field); \ 713 elm = RB_PARENT(elm, field); \ 714 } \ 715 } \ 716 return (elm); \ 717 } \ 718 \ 719 attr struct type * \ 720 name##_RB_MINMAX(struct name *head, int val) \ 721 { \ 722 struct type *tmp = RB_ROOT(head); \ 723 struct type *parent = NULL; \ 724 while (tmp) { \ 725 parent = tmp; \ 726 if (val < 0) \ 727 tmp = RB_LEFT(tmp, field); \ 728 else \ 729 tmp = RB_RIGHT(tmp, field); \ 730 } \ 731 return (parent); \ 732 } 733 734 #define RB_NEGINF -1 735 #define RB_INF 1 736 737 #define RB_INSERT(name, x, y) name##_RB_INSERT(x, y) 738 #define RB_REMOVE(name, x, y) name##_RB_REMOVE(x, y) 739 #define RB_FIND(name, x, y) name##_RB_FIND(x, y) 740 #define RB_NFIND(name, x, y) name##_RB_NFIND(x, y) 741 #define RB_NEXT(name, x, y) name##_RB_NEXT(y) 742 #define RB_PREV(name, x, y) name##_RB_PREV(y) 743 #define RB_MIN(name, x) name##_RB_MINMAX(x, RB_NEGINF) 744 #define RB_MAX(name, x) name##_RB_MINMAX(x, RB_INF) 745 746 #define RB_FOREACH(x, name, head) \ 747 for ((x) = RB_MIN(name, head); \ 748 (x) != NULL; \ 749 (x) = name##_RB_NEXT(x)) 750 751 #define RB_FOREACH_FROM(x, name, y) \ 752 for ((x) = (y); \ 753 ((x) != NULL) && ((y) = name##_RB_NEXT(x), (x) != NULL); \ 754 (x) = (y)) 755 756 #define RB_FOREACH_SAFE(x, name, head, y) \ 757 for ((x) = RB_MIN(name, head); \ 758 ((x) != NULL) && ((y) = name##_RB_NEXT(x), (x) != NULL); \ 759 (x) = (y)) 760 761 #define RB_FOREACH_REVERSE(x, name, head) \ 762 for ((x) = RB_MAX(name, head); \ 763 (x) != NULL; \ 764 (x) = name##_RB_PREV(x)) 765 766 #define RB_FOREACH_REVERSE_FROM(x, name, y) \ 767 for ((x) = (y); \ 768 ((x) != NULL) && ((y) = name##_RB_PREV(x), (x) != NULL); \ 769 (x) = (y)) 770 771 #define RB_FOREACH_REVERSE_SAFE(x, name, head, y) \ 772 for ((x) = RB_MAX(name, head); \ 773 ((x) != NULL) && ((y) = name##_RB_PREV(x), (x) != NULL); \ 774 (x) = (y)) 775 776 #endif /* _SYS_TREE_H_ */