1 /* $NetBSD: tree.h,v 1.8 2004/03/28 19:38:30 provos Exp $ */ 2 /* $OpenBSD: tree.h,v 1.7 2002/10/17 21:51:54 art Exp $ */ 3 4 /*- 5 * SPDX-License-Identifier: BSD-2-Clause 6 * 7 * Copyright 2002 Niels Provos <provos@citi.umich.edu> 8 * All rights reserved. 9 * 10 * Redistribution and use in source and binary forms, with or without 11 * modification, are permitted provided that the following conditions 12 * are met: 13 * 1. Redistributions of source code must retain the above copyright 14 * notice, this list of conditions and the following disclaimer. 15 * 2. Redistributions in binary form must reproduce the above copyright 16 * notice, this list of conditions and the following disclaimer in the 17 * documentation and/or other materials provided with the distribution. 18 * 19 * THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR 20 * IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES 21 * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED. 22 * IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT, 23 * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT 24 * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, 25 * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY 26 * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT 27 * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF 28 * THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. 29 */ 30 31 #ifndef _SYS_TREE_H_ 32 #define _SYS_TREE_H_ 33 34 #include <sys/cdefs.h> 35 36 #ifdef __cplusplus 37 #if __cplusplus 38 extern "C" { 39 #endif /* __cplusplus */ 40 #endif /* __cplusplus */ 41 /* 42 * This file defines data structures for different types of trees: 43 * splay trees and red-black trees. 44 * 45 * A splay tree is a self-organizing data structure. Every operation 46 * on the tree causes a splay to happen. The splay moves the requested 47 * node to the root of the tree and partly rebalances it. 48 * 49 * This has the benefit that request locality causes faster lookups as 50 * the requested nodes move to the top of the tree. On the other hand, 51 * every lookup causes memory writes. 52 * 53 * The Balance Theorem bounds the total access time for m operations 54 * and n inserts on an initially empty tree as O((m + n)lg n). The 55 * amortized cost for a sequence of m accesses to a splay tree is O(lg n); 56 * 57 * A red-black tree is a binary search tree with the node color as an 58 * extra attribute. It fulfills a set of conditions: 59 * - every search path from the root to a leaf consists of the 60 * same number of black nodes, 61 * - each red node (except for the root) has a black parent, 62 * - each leaf node is black. 63 * 64 * Every operation on a red-black tree is bounded as O(lg n). 65 * The maximum height of a red-black tree is 2lg (n+1). 66 */ 67 68 #define SPLAY_HEAD(name, type) \ 69 struct name { \ 70 struct type *sph_root; /* root of the tree */ \ 71 } 72 73 #define SPLAY_INITIALIZER(root) \ 74 { NULL } 75 76 #define SPLAY_INIT(root) do { \ 77 (root)->sph_root = NULL; \ 78 } while (/*CONSTCOND*/ 0) 79 80 #define SPLAY_ENTRY(type) \ 81 struct { \ 82 struct type *spe_left; /* left element */ \ 83 struct type *spe_right; /* right element */ \ 84 } 85 86 #define SPLAY_LEFT(elm, field) (elm)->field.spe_left 87 #define SPLAY_RIGHT(elm, field) (elm)->field.spe_right 88 #define SPLAY_ROOT(head) (head)->sph_root 89 #define SPLAY_EMPTY(head) (SPLAY_ROOT(head) == NULL) 90 91 /* SPLAY_ROTATE_{LEFT,RIGHT} expect that tmp hold SPLAY_{RIGHT,LEFT} */ 92 #define SPLAY_ROTATE_RIGHT(head, tmp, field) do { \ 93 SPLAY_LEFT((head)->sph_root, field) = SPLAY_RIGHT(tmp, field); \ 94 SPLAY_RIGHT(tmp, field) = (head)->sph_root; \ 95 (head)->sph_root = tmp; \ 96 } while (/*CONSTCOND*/ 0) 97 98 #define SPLAY_ROTATE_LEFT(head, tmp, field) do { \ 99 SPLAY_RIGHT((head)->sph_root, field) = SPLAY_LEFT(tmp, field); \ 100 SPLAY_LEFT(tmp, field) = (head)->sph_root; \ 101 (head)->sph_root = tmp; \ 102 } while (/*CONSTCOND*/ 0) 103 104 #define SPLAY_LINKLEFT(head, tmp, field) do { \ 105 SPLAY_LEFT(tmp, field) = (head)->sph_root; \ 106 tmp = (head)->sph_root; \ 107 (head)->sph_root = SPLAY_LEFT((head)->sph_root, field); \ 108 } while (/*CONSTCOND*/ 0) 109 110 #define SPLAY_LINKRIGHT(head, tmp, field) do { \ 111 SPLAY_RIGHT(tmp, field) = (head)->sph_root; \ 112 tmp = (head)->sph_root; \ 113 (head)->sph_root = SPLAY_RIGHT((head)->sph_root, field); \ 114 } while (/*CONSTCOND*/ 0) 115 116 #define SPLAY_ASSEMBLE(head, node, left, right, field) do { \ 117 SPLAY_RIGHT(left, field) = SPLAY_LEFT((head)->sph_root, field); \ 118 SPLAY_LEFT(right, field) = SPLAY_RIGHT((head)->sph_root, field);\ 119 SPLAY_LEFT((head)->sph_root, field) = SPLAY_RIGHT(node, field); \ 120 SPLAY_RIGHT((head)->sph_root, field) = SPLAY_LEFT(node, field); \ 121 } while (/*CONSTCOND*/ 0) 122 123 /* Generates prototypes and inline functions */ 124 125 #define SPLAY_PROTOTYPE(name, type, field, cmp) \ 126 void name##_SPLAY(struct name *, struct type *); \ 127 void name##_SPLAY_MINMAX(struct name *, int); \ 128 struct type *name##_SPLAY_INSERT(struct name *, struct type *); \ 129 struct type *name##_SPLAY_REMOVE(struct name *, struct type *); \ 130 \ 131 /* Finds the node with the same key as elm */ \ 132 static __inline struct type * \ 133 name##_SPLAY_FIND(struct name *head, struct type *elm) \ 134 { \ 135 if (SPLAY_EMPTY(head)) \ 136 return(NULL); \ 137 name##_SPLAY(head, elm); \ 138 if ((cmp)(elm, (head)->sph_root) == 0) \ 139 return (head->sph_root); \ 140 return (NULL); \ 141 } \ 142 \ 143 static __inline struct type * \ 144 name##_SPLAY_NEXT(struct name *head, struct type *elm) \ 145 { \ 146 name##_SPLAY(head, elm); \ 147 if (SPLAY_RIGHT(elm, field) != NULL) { \ 148 elm = SPLAY_RIGHT(elm, field); \ 149 while (SPLAY_LEFT(elm, field) != NULL) { \ 150 elm = SPLAY_LEFT(elm, field); \ 151 } \ 152 } else \ 153 elm = NULL; \ 154 return (elm); \ 155 } \ 156 \ 157 static __inline struct type * \ 158 name##_SPLAY_MIN_MAX(struct name *head, int val) \ 159 { \ 160 name##_SPLAY_MINMAX(head, val); \ 161 return (SPLAY_ROOT(head)); \ 162 } 163 164 /* Main splay operation. 165 * Moves node close to the key of elm to top 166 */ 167 #define SPLAY_GENERATE(name, type, field, cmp) \ 168 struct type * \ 169 name##_SPLAY_INSERT(struct name *head, struct type *elm) \ 170 { \ 171 if (SPLAY_EMPTY(head)) { \ 172 SPLAY_LEFT(elm, field) = SPLAY_RIGHT(elm, field) = NULL; \ 173 } else { \ 174 int __comp; \ 175 name##_SPLAY(head, elm); \ 176 __comp = (cmp)(elm, (head)->sph_root); \ 177 if(__comp < 0) { \ 178 SPLAY_LEFT(elm, field) = SPLAY_LEFT((head)->sph_root, field);\ 179 SPLAY_RIGHT(elm, field) = (head)->sph_root; \ 180 SPLAY_LEFT((head)->sph_root, field) = NULL; \ 181 } else if (__comp > 0) { \ 182 SPLAY_RIGHT(elm, field) = SPLAY_RIGHT((head)->sph_root, field);\ 183 SPLAY_LEFT(elm, field) = (head)->sph_root; \ 184 SPLAY_RIGHT((head)->sph_root, field) = NULL; \ 185 } else \ 186 return ((head)->sph_root); \ 187 } \ 188 (head)->sph_root = (elm); \ 189 return (NULL); \ 190 } \ 191 \ 192 struct type * \ 193 name##_SPLAY_REMOVE(struct name *head, struct type *elm) \ 194 { \ 195 struct type *__tmp; \ 196 if (SPLAY_EMPTY(head)) \ 197 return (NULL); \ 198 name##_SPLAY(head, elm); \ 199 if ((cmp)(elm, (head)->sph_root) == 0) { \ 200 if (SPLAY_LEFT((head)->sph_root, field) == NULL) { \ 201 (head)->sph_root = SPLAY_RIGHT((head)->sph_root, field);\ 202 } else { \ 203 __tmp = SPLAY_RIGHT((head)->sph_root, field); \ 204 (head)->sph_root = SPLAY_LEFT((head)->sph_root, field);\ 205 name##_SPLAY(head, elm); \ 206 SPLAY_RIGHT((head)->sph_root, field) = __tmp; \ 207 } \ 208 return (elm); \ 209 } \ 210 return (NULL); \ 211 } \ 212 \ 213 void \ 214 name##_SPLAY(struct name *head, struct type *elm) \ 215 { \ 216 struct type __node, *__left, *__right, *__tmp; \ 217 int __comp; \ 218 \ 219 SPLAY_LEFT(&__node, field) = SPLAY_RIGHT(&__node, field) = NULL;\ 220 __left = __right = &__node; \ 221 \ 222 while ((__comp = (cmp)(elm, (head)->sph_root)) != 0) { \ 223 if (__comp < 0) { \ 224 __tmp = SPLAY_LEFT((head)->sph_root, field); \ 225 if (__tmp == NULL) \ 226 break; \ 227 if ((cmp)(elm, __tmp) < 0){ \ 228 SPLAY_ROTATE_RIGHT(head, __tmp, field); \ 229 if (SPLAY_LEFT((head)->sph_root, field) == NULL)\ 230 break; \ 231 } \ 232 SPLAY_LINKLEFT(head, __right, field); \ 233 } else if (__comp > 0) { \ 234 __tmp = SPLAY_RIGHT((head)->sph_root, field); \ 235 if (__tmp == NULL) \ 236 break; \ 237 if ((cmp)(elm, __tmp) > 0){ \ 238 SPLAY_ROTATE_LEFT(head, __tmp, field); \ 239 if (SPLAY_RIGHT((head)->sph_root, field) == NULL)\ 240 break; \ 241 } \ 242 SPLAY_LINKRIGHT(head, __left, field); \ 243 } \ 244 } \ 245 SPLAY_ASSEMBLE(head, &__node, __left, __right, field); \ 246 } \ 247 \ 248 /* Splay with either the minimum or the maximum element \ 249 * Used to find minimum or maximum element in tree. \ 250 */ \ 251 void name##_SPLAY_MINMAX(struct name *head, int __comp) \ 252 { \ 253 struct type __node, *__left, *__right, *__tmp; \ 254 \ 255 SPLAY_LEFT(&__node, field) = SPLAY_RIGHT(&__node, field) = NULL;\ 256 __left = __right = &__node; \ 257 \ 258 while (1) { \ 259 if (__comp < 0) { \ 260 __tmp = SPLAY_LEFT((head)->sph_root, field); \ 261 if (__tmp == NULL) \ 262 break; \ 263 if (__comp < 0){ \ 264 SPLAY_ROTATE_RIGHT(head, __tmp, field); \ 265 if (SPLAY_LEFT((head)->sph_root, field) == NULL)\ 266 break; \ 267 } \ 268 SPLAY_LINKLEFT(head, __right, field); \ 269 } else if (__comp > 0) { \ 270 __tmp = SPLAY_RIGHT((head)->sph_root, field); \ 271 if (__tmp == NULL) \ 272 break; \ 273 if (__comp > 0) { \ 274 SPLAY_ROTATE_LEFT(head, __tmp, field); \ 275 if (SPLAY_RIGHT((head)->sph_root, field) == NULL)\ 276 break; \ 277 } \ 278 SPLAY_LINKRIGHT(head, __left, field); \ 279 } \ 280 } \ 281 SPLAY_ASSEMBLE(head, &__node, __left, __right, field); \ 282 } 283 284 #define SPLAY_NEGINF -1 285 #define SPLAY_INF 1 286 287 #define SPLAY_INSERT(name, x, y) name##_SPLAY_INSERT(x, y) 288 #define SPLAY_REMOVE(name, x, y) name##_SPLAY_REMOVE(x, y) 289 #define SPLAY_FIND(name, x, y) name##_SPLAY_FIND(x, y) 290 #define SPLAY_NEXT(name, x, y) name##_SPLAY_NEXT(x, y) 291 #define SPLAY_MIN(name, x) (SPLAY_EMPTY(x) ? NULL \ 292 : name##_SPLAY_MIN_MAX(x, SPLAY_NEGINF)) 293 #define SPLAY_MAX(name, x) (SPLAY_EMPTY(x) ? NULL \ 294 : name##_SPLAY_MIN_MAX(x, SPLAY_INF)) 295 296 #define SPLAY_FOREACH(x, name, head) \ 297 for ((x) = SPLAY_MIN(name, head); \ 298 (x) != NULL; \ 299 (x) = SPLAY_NEXT(name, head, x)) 300 301 /* Macros that define a red-black tree */ 302 #define RB_HEAD(name, type) \ 303 struct name { \ 304 struct type *rbh_root; /* root of the tree */ \ 305 } 306 307 #define RB_INITIALIZER(root) \ 308 { NULL } 309 310 #define RB_INIT(root) do { \ 311 (root)->rbh_root = NULL; \ 312 } while (/*CONSTCOND*/ 0) 313 314 #define RB_BLACK 0 315 #define RB_RED 1 316 #define RB_ENTRY(type) \ 317 struct { \ 318 struct type *rbe_left; /* left element */ \ 319 struct type *rbe_right; /* right element */ \ 320 struct type *rbe_parent; /* parent element */ \ 321 int rbe_color; /* node color */ \ 322 } 323 324 #define RB_LEFT(elm, field) (elm)->field.rbe_left 325 #define RB_RIGHT(elm, field) (elm)->field.rbe_right 326 #define RB_PARENT(elm, field) (elm)->field.rbe_parent 327 #define RB_COLOR(elm, field) (elm)->field.rbe_color 328 #define RB_ROOT(head) (head)->rbh_root 329 #define RB_EMPTY(head) (RB_ROOT(head) == NULL) 330 331 #define RB_SET(elm, parent, field) do { \ 332 RB_PARENT(elm, field) = parent; \ 333 RB_LEFT(elm, field) = RB_RIGHT(elm, field) = NULL; \ 334 RB_COLOR(elm, field) = RB_RED; \ 335 } while (/*CONSTCOND*/ 0) 336 337 #define RB_SET_BLACKRED(black, red, field) do { \ 338 RB_COLOR(black, field) = RB_BLACK; \ 339 RB_COLOR(red, field) = RB_RED; \ 340 } while (/*CONSTCOND*/ 0) 341 342 #ifndef RB_AUGMENT 343 #define RB_AUGMENT(x) do {} while (0) 344 #endif 345 346 #define RB_ROTATE_LEFT(head, elm, tmp, field) do { \ 347 (tmp) = RB_RIGHT(elm, field); \ 348 if ((RB_RIGHT(elm, field) = RB_LEFT(tmp, field)) != NULL) { \ 349 RB_PARENT(RB_LEFT(tmp, field), field) = (elm); \ 350 } \ 351 RB_AUGMENT(elm); \ 352 if ((RB_PARENT(tmp, field) = RB_PARENT(elm, field)) != NULL) { \ 353 if ((elm) == RB_LEFT(RB_PARENT(elm, field), field)) \ 354 RB_LEFT(RB_PARENT(elm, field), field) = (tmp); \ 355 else \ 356 RB_RIGHT(RB_PARENT(elm, field), field) = (tmp); \ 357 } else \ 358 (head)->rbh_root = (tmp); \ 359 RB_LEFT(tmp, field) = (elm); \ 360 RB_PARENT(elm, field) = (tmp); \ 361 RB_AUGMENT(tmp); \ 362 if ((RB_PARENT(tmp, field))) \ 363 RB_AUGMENT(RB_PARENT(tmp, field)); \ 364 } while (/*CONSTCOND*/ 0) 365 366 #define RB_ROTATE_RIGHT(head, elm, tmp, field) do { \ 367 (tmp) = RB_LEFT(elm, field); \ 368 if ((RB_LEFT(elm, field) = RB_RIGHT(tmp, field)) != NULL) { \ 369 RB_PARENT(RB_RIGHT(tmp, field), field) = (elm); \ 370 } \ 371 RB_AUGMENT(elm); \ 372 if ((RB_PARENT(tmp, field) = RB_PARENT(elm, field)) != NULL) { \ 373 if ((elm) == RB_LEFT(RB_PARENT(elm, field), field)) \ 374 RB_LEFT(RB_PARENT(elm, field), field) = (tmp); \ 375 else \ 376 RB_RIGHT(RB_PARENT(elm, field), field) = (tmp); \ 377 } else \ 378 (head)->rbh_root = (tmp); \ 379 RB_RIGHT(tmp, field) = (elm); \ 380 RB_PARENT(elm, field) = (tmp); \ 381 RB_AUGMENT(tmp); \ 382 if ((RB_PARENT(tmp, field))) \ 383 RB_AUGMENT(RB_PARENT(tmp, field)); \ 384 } while (/*CONSTCOND*/ 0) 385 386 /* Generates prototypes and inline functions */ 387 #define RB_PROTOTYPE(name, type, field, cmp) \ 388 RB_PROTOTYPE_INTERNAL(name, type, field, cmp,) 389 #define RB_PROTOTYPE_STATIC(name, type, field, cmp) \ 390 RB_PROTOTYPE_INTERNAL(name, type, field, cmp, __unused static) 391 #define RB_PROTOTYPE_INTERNAL(name, type, field, cmp, attr) \ 392 RB_PROTOTYPE_INSERT_COLOR(name, type, attr); \ 393 RB_PROTOTYPE_REMOVE_COLOR(name, type, attr); \ 394 RB_PROTOTYPE_INSERT(name, type, attr); \ 395 RB_PROTOTYPE_REMOVE(name, type, attr); \ 396 RB_PROTOTYPE_FIND(name, type, attr); \ 397 RB_PROTOTYPE_NFIND(name, type, attr); \ 398 RB_PROTOTYPE_NEXT(name, type, attr); \ 399 RB_PROTOTYPE_PREV(name, type, attr); \ 400 RB_PROTOTYPE_MINMAX(name, type, attr); \ 401 RB_PROTOTYPE_LEFT_DEEPEST(name, type, attr); \ 402 RB_PROTOTYPE_NEXT_POSTORDER(name, type, attr); \ 403 RB_PROTOTYPE_FIRST_POSTORDER(name, type, attr); 404 405 #define RB_PROTOTYPE_INSERT_COLOR(name, type, attr) \ 406 attr void name##_RB_INSERT_COLOR(struct name *, struct type *) 407 #define RB_PROTOTYPE_REMOVE_COLOR(name, type, attr) \ 408 attr void name##_RB_REMOVE_COLOR(struct name *, struct type *, struct type *) 409 #define RB_PROTOTYPE_REMOVE(name, type, attr) \ 410 attr struct type *name##_RB_REMOVE(struct name *, struct type *) 411 #define RB_PROTOTYPE_INSERT(name, type, attr) \ 412 attr struct type *name##_RB_INSERT(struct name *, struct type *) 413 #define RB_PROTOTYPE_FIND(name, type, attr) \ 414 attr struct type *name##_RB_FIND(struct name *, struct type *) 415 #define RB_PROTOTYPE_NFIND(name, type, attr) \ 416 attr struct type *name##_RB_NFIND(struct name *, struct type *) 417 #define RB_PROTOTYPE_NEXT(name, type, attr) \ 418 attr struct type *name##_RB_NEXT(struct type *) 419 #define RB_PROTOTYPE_PREV(name, type, attr) \ 420 attr struct type *name##_RB_PREV(struct type *) 421 #define RB_PROTOTYPE_MINMAX(name, type, attr) \ 422 attr struct type *name##_RB_MINMAX(struct name *, int) 423 #define RB_PROTOTYPE_LEFT_DEEPEST(name, type, attr) \ 424 attr struct type *name##_RB_LEFT_DEEPEST(struct type *) 425 #define RB_PROTOTYPE_NEXT_POSTORDER(name, type, attr) \ 426 attr struct type *name##_RB_NEXT_POSTORDER(struct type *) 427 #define RB_PROTOTYPE_FIRST_POSTORDER(name, type, attr) \ 428 attr struct type *name##_RB_FIRST_POSTORDER(struct name *) 429 430 /* Main rb operation. 431 * Moves node close to the key of elm to top 432 */ 433 #define RB_GENERATE(name, type, field, cmp) \ 434 RB_GENERATE_INTERNAL(name, type, field, cmp,) 435 #define RB_GENERATE_STATIC(name, type, field, cmp) \ 436 RB_GENERATE_INTERNAL(name, type, field, cmp, __unused static) 437 #define RB_GENERATE_INTERNAL(name, type, field, cmp, attr) \ 438 RB_GENERATE_INSERT_COLOR(name, type, field, attr) \ 439 RB_GENERATE_REMOVE_COLOR(name, type, field, attr) \ 440 RB_GENERATE_INSERT(name, type, field, cmp, attr) \ 441 RB_GENERATE_REMOVE(name, type, field, attr) \ 442 RB_GENERATE_FIND(name, type, field, cmp, attr) \ 443 RB_GENERATE_NFIND(name, type, field, cmp, attr) \ 444 RB_GENERATE_NEXT(name, type, field, attr) \ 445 RB_GENERATE_PREV(name, type, field, attr) \ 446 RB_GENERATE_MINMAX(name, type, field, attr) \ 447 RB_GENERATE_LEFT_DEEPEST(name, type, field, attr) \ 448 RB_GENERATE_NEXT_POSTORDER(name, type, field, attr) \ 449 RB_GENERATE_FIRST_POSTORDER(name, type, field, attr) 450 451 #define RB_GENERATE_INSERT_COLOR(name, type, field, attr) \ 452 attr void \ 453 name##_RB_INSERT_COLOR(struct name *head, struct type *elm) \ 454 { \ 455 struct type *parent, *gparent, *tmp; \ 456 while ((parent = RB_PARENT(elm, field)) != NULL && \ 457 RB_COLOR(parent, field) == RB_RED) { \ 458 gparent = RB_PARENT(parent, field); \ 459 if (parent == RB_LEFT(gparent, field)) { \ 460 tmp = RB_RIGHT(gparent, field); \ 461 if (tmp && RB_COLOR(tmp, field) == RB_RED) { \ 462 RB_COLOR(tmp, field) = RB_BLACK; \ 463 RB_SET_BLACKRED(parent, gparent, field);\ 464 elm = gparent; \ 465 continue; \ 466 } \ 467 if (RB_RIGHT(parent, field) == elm) { \ 468 RB_ROTATE_LEFT(head, parent, tmp, field);\ 469 tmp = parent; \ 470 parent = elm; \ 471 elm = tmp; \ 472 } \ 473 RB_SET_BLACKRED(parent, gparent, field); \ 474 RB_ROTATE_RIGHT(head, gparent, tmp, field); \ 475 } else { \ 476 tmp = RB_LEFT(gparent, field); \ 477 if (tmp && RB_COLOR(tmp, field) == RB_RED) { \ 478 RB_COLOR(tmp, field) = RB_BLACK; \ 479 RB_SET_BLACKRED(parent, gparent, field);\ 480 elm = gparent; \ 481 continue; \ 482 } \ 483 if (RB_LEFT(parent, field) == elm) { \ 484 RB_ROTATE_RIGHT(head, parent, tmp, field);\ 485 tmp = parent; \ 486 parent = elm; \ 487 elm = tmp; \ 488 } \ 489 RB_SET_BLACKRED(parent, gparent, field); \ 490 RB_ROTATE_LEFT(head, gparent, tmp, field); \ 491 } \ 492 } \ 493 RB_COLOR(head->rbh_root, field) = RB_BLACK; \ 494 } 495 496 #define RB_GENERATE_REMOVE_COLOR(name, type, field, attr) \ 497 attr void \ 498 name##_RB_REMOVE_COLOR(struct name *head, struct type *parent, struct type *elm) \ 499 { \ 500 struct type *tmp; \ 501 while ((elm == NULL || RB_COLOR(elm, field) == RB_BLACK) && \ 502 elm != RB_ROOT(head)) { \ 503 if (RB_LEFT(parent, field) == elm) { \ 504 tmp = RB_RIGHT(parent, field); \ 505 if (RB_COLOR(tmp, field) == RB_RED) { \ 506 RB_SET_BLACKRED(tmp, parent, field); \ 507 RB_ROTATE_LEFT(head, parent, tmp, field);\ 508 tmp = RB_RIGHT(parent, field); \ 509 } \ 510 if ((RB_LEFT(tmp, field) == NULL || \ 511 RB_COLOR(RB_LEFT(tmp, field), field) == RB_BLACK) &&\ 512 (RB_RIGHT(tmp, field) == NULL || \ 513 RB_COLOR(RB_RIGHT(tmp, field), field) == RB_BLACK)) {\ 514 RB_COLOR(tmp, field) = RB_RED; \ 515 elm = parent; \ 516 parent = RB_PARENT(elm, field); \ 517 } else { \ 518 if (RB_RIGHT(tmp, field) == NULL || \ 519 RB_COLOR(RB_RIGHT(tmp, field), field) == RB_BLACK) {\ 520 struct type *oleft; \ 521 if ((oleft = RB_LEFT(tmp, field)) \ 522 != NULL) \ 523 RB_COLOR(oleft, field) = RB_BLACK;\ 524 RB_COLOR(tmp, field) = RB_RED; \ 525 RB_ROTATE_RIGHT(head, tmp, oleft, field);\ 526 tmp = RB_RIGHT(parent, field); \ 527 } \ 528 RB_COLOR(tmp, field) = RB_COLOR(parent, field);\ 529 RB_COLOR(parent, field) = RB_BLACK; \ 530 if (RB_RIGHT(tmp, field)) \ 531 RB_COLOR(RB_RIGHT(tmp, field), field) = RB_BLACK;\ 532 RB_ROTATE_LEFT(head, parent, tmp, field);\ 533 elm = RB_ROOT(head); \ 534 break; \ 535 } \ 536 } else { \ 537 tmp = RB_LEFT(parent, field); \ 538 if (RB_COLOR(tmp, field) == RB_RED) { \ 539 RB_SET_BLACKRED(tmp, parent, field); \ 540 RB_ROTATE_RIGHT(head, parent, tmp, field);\ 541 tmp = RB_LEFT(parent, field); \ 542 } \ 543 if ((RB_LEFT(tmp, field) == NULL || \ 544 RB_COLOR(RB_LEFT(tmp, field), field) == RB_BLACK) &&\ 545 (RB_RIGHT(tmp, field) == NULL || \ 546 RB_COLOR(RB_RIGHT(tmp, field), field) == RB_BLACK)) {\ 547 RB_COLOR(tmp, field) = RB_RED; \ 548 elm = parent; \ 549 parent = RB_PARENT(elm, field); \ 550 } else { \ 551 if (RB_LEFT(tmp, field) == NULL || \ 552 RB_COLOR(RB_LEFT(tmp, field), field) == RB_BLACK) {\ 553 struct type *oright; \ 554 if ((oright = RB_RIGHT(tmp, field)) \ 555 != NULL) \ 556 RB_COLOR(oright, field) = RB_BLACK;\ 557 RB_COLOR(tmp, field) = RB_RED; \ 558 RB_ROTATE_LEFT(head, tmp, oright, field);\ 559 tmp = RB_LEFT(parent, field); \ 560 } \ 561 RB_COLOR(tmp, field) = RB_COLOR(parent, field);\ 562 RB_COLOR(parent, field) = RB_BLACK; \ 563 if (RB_LEFT(tmp, field)) \ 564 RB_COLOR(RB_LEFT(tmp, field), field) = RB_BLACK;\ 565 RB_ROTATE_RIGHT(head, parent, tmp, field);\ 566 elm = RB_ROOT(head); \ 567 break; \ 568 } \ 569 } \ 570 } \ 571 if (elm) \ 572 RB_COLOR(elm, field) = RB_BLACK; \ 573 } 574 575 #define RB_GENERATE_REMOVE(name, type, field, attr) \ 576 attr struct type * \ 577 name##_RB_REMOVE(struct name *head, struct type *elm) \ 578 { \ 579 struct type *child, *parent, *old = elm; \ 580 int color; \ 581 if (RB_LEFT(elm, field) == NULL) \ 582 child = RB_RIGHT(elm, field); \ 583 else if (RB_RIGHT(elm, field) == NULL) \ 584 child = RB_LEFT(elm, field); \ 585 else { \ 586 struct type *left; \ 587 elm = RB_RIGHT(elm, field); \ 588 while ((left = RB_LEFT(elm, field)) != NULL) \ 589 elm = left; \ 590 child = RB_RIGHT(elm, field); \ 591 parent = RB_PARENT(elm, field); \ 592 color = RB_COLOR(elm, field); \ 593 if (child) \ 594 RB_PARENT(child, field) = parent; \ 595 if (parent) { \ 596 if (RB_LEFT(parent, field) == elm) \ 597 RB_LEFT(parent, field) = child; \ 598 else \ 599 RB_RIGHT(parent, field) = child; \ 600 RB_AUGMENT(parent); \ 601 } else \ 602 RB_ROOT(head) = child; \ 603 if (RB_PARENT(elm, field) == old) \ 604 parent = elm; \ 605 (elm)->field = (old)->field; \ 606 if (RB_PARENT(old, field)) { \ 607 if (RB_LEFT(RB_PARENT(old, field), field) == old)\ 608 RB_LEFT(RB_PARENT(old, field), field) = elm;\ 609 else \ 610 RB_RIGHT(RB_PARENT(old, field), field) = elm;\ 611 RB_AUGMENT(RB_PARENT(old, field)); \ 612 } else \ 613 RB_ROOT(head) = elm; \ 614 RB_PARENT(RB_LEFT(old, field), field) = elm; \ 615 if (RB_RIGHT(old, field)) \ 616 RB_PARENT(RB_RIGHT(old, field), field) = elm; \ 617 if (parent) { \ 618 left = parent; \ 619 do { \ 620 RB_AUGMENT(left); \ 621 } while ((left = RB_PARENT(left, field)) != NULL); \ 622 } \ 623 goto color; \ 624 } \ 625 parent = RB_PARENT(elm, field); \ 626 color = RB_COLOR(elm, field); \ 627 if (child) \ 628 RB_PARENT(child, field) = parent; \ 629 if (parent) { \ 630 if (RB_LEFT(parent, field) == elm) \ 631 RB_LEFT(parent, field) = child; \ 632 else \ 633 RB_RIGHT(parent, field) = child; \ 634 RB_AUGMENT(parent); \ 635 } else \ 636 RB_ROOT(head) = child; \ 637 color: \ 638 if (color == RB_BLACK) \ 639 name##_RB_REMOVE_COLOR(head, parent, child); \ 640 return (old); \ 641 } \ 642 643 #define RB_GENERATE_INSERT(name, type, field, cmp, attr) \ 644 /* Inserts a node into the RB tree */ \ 645 attr struct type * \ 646 name##_RB_INSERT(struct name *head, struct type *elm) \ 647 { \ 648 struct type *tmp; \ 649 struct type *parent = NULL; \ 650 int comp = 0; \ 651 tmp = RB_ROOT(head); \ 652 while (tmp) { \ 653 parent = tmp; \ 654 comp = (cmp)(elm, parent); \ 655 if (comp < 0) \ 656 tmp = RB_LEFT(tmp, field); \ 657 else if (comp > 0) \ 658 tmp = RB_RIGHT(tmp, field); \ 659 else \ 660 return (tmp); \ 661 } \ 662 RB_SET(elm, parent, field); \ 663 if (parent != NULL) { \ 664 if (comp < 0) \ 665 RB_LEFT(parent, field) = elm; \ 666 else \ 667 RB_RIGHT(parent, field) = elm; \ 668 RB_AUGMENT(parent); \ 669 } else \ 670 RB_ROOT(head) = elm; \ 671 name##_RB_INSERT_COLOR(head, elm); \ 672 return (NULL); \ 673 } 674 675 #define RB_GENERATE_FIND(name, type, field, cmp, attr) \ 676 /* Finds the node with the same key as elm */ \ 677 attr struct type * \ 678 name##_RB_FIND(struct name *head, struct type *elm) \ 679 { \ 680 struct type *tmp = RB_ROOT(head); \ 681 int comp; \ 682 while (tmp) { \ 683 comp = cmp(elm, tmp); \ 684 if (comp < 0) \ 685 tmp = RB_LEFT(tmp, field); \ 686 else if (comp > 0) \ 687 tmp = RB_RIGHT(tmp, field); \ 688 else \ 689 return (tmp); \ 690 } \ 691 return (NULL); \ 692 } 693 694 #define RB_GENERATE_NFIND(name, type, field, cmp, attr) \ 695 /* Finds the first node greater than or equal to the search key */ \ 696 attr struct type * \ 697 name##_RB_NFIND(struct name *head, struct type *elm) \ 698 { \ 699 struct type *tmp = RB_ROOT(head); \ 700 struct type *res = NULL; \ 701 int comp; \ 702 while (tmp) { \ 703 comp = cmp(elm, tmp); \ 704 if (comp < 0) { \ 705 res = tmp; \ 706 tmp = RB_LEFT(tmp, field); \ 707 } \ 708 else if (comp > 0) \ 709 tmp = RB_RIGHT(tmp, field); \ 710 else \ 711 return (tmp); \ 712 } \ 713 return (res); \ 714 } 715 716 #define RB_GENERATE_NEXT(name, type, field, attr) \ 717 /* ARGSUSED */ \ 718 attr struct type * \ 719 name##_RB_NEXT(struct type *elm) \ 720 { \ 721 if (RB_RIGHT(elm, field)) { \ 722 elm = RB_RIGHT(elm, field); \ 723 while (RB_LEFT(elm, field)) \ 724 elm = RB_LEFT(elm, field); \ 725 } else { \ 726 if (RB_PARENT(elm, field) && \ 727 (elm == RB_LEFT(RB_PARENT(elm, field), field))) \ 728 elm = RB_PARENT(elm, field); \ 729 else { \ 730 while (RB_PARENT(elm, field) && \ 731 (elm == RB_RIGHT(RB_PARENT(elm, field), field)))\ 732 elm = RB_PARENT(elm, field); \ 733 elm = RB_PARENT(elm, field); \ 734 } \ 735 } \ 736 return (elm); \ 737 } 738 739 #define RB_GENERATE_PREV(name, type, field, attr) \ 740 /* ARGSUSED */ \ 741 attr struct type * \ 742 name##_RB_PREV(struct type *elm) \ 743 { \ 744 if (RB_LEFT(elm, field)) { \ 745 elm = RB_LEFT(elm, field); \ 746 while (RB_RIGHT(elm, field)) \ 747 elm = RB_RIGHT(elm, field); \ 748 } else { \ 749 if (RB_PARENT(elm, field) && \ 750 (elm == RB_RIGHT(RB_PARENT(elm, field), field))) \ 751 elm = RB_PARENT(elm, field); \ 752 else { \ 753 while (RB_PARENT(elm, field) && \ 754 (elm == RB_LEFT(RB_PARENT(elm, field), field)))\ 755 elm = RB_PARENT(elm, field); \ 756 elm = RB_PARENT(elm, field); \ 757 } \ 758 } \ 759 return (elm); \ 760 } 761 762 #define RB_GENERATE_MINMAX(name, type, field, attr) \ 763 attr struct type * \ 764 name##_RB_MINMAX(struct name *head, int val) \ 765 { \ 766 struct type *tmp = RB_ROOT(head); \ 767 struct type *parent = NULL; \ 768 while (tmp) { \ 769 parent = tmp; \ 770 if (val < 0) \ 771 tmp = RB_LEFT(tmp, field); \ 772 else \ 773 tmp = RB_RIGHT(tmp, field); \ 774 } \ 775 return (parent); \ 776 } 777 778 #define RB_GENERATE_LEFT_DEEPEST(name, type, field, attr) \ 779 attr struct type * \ 780 name##_RB_LEFT_DEEPEST(struct type *node) \ 781 { \ 782 while (1) { \ 783 if (RB_LEFT(node, field) != NULL) \ 784 node = RB_LEFT(node, field); \ 785 else if(RB_RIGHT(node, field) != NULL) \ 786 node = RB_RIGHT(node, field); \ 787 else \ 788 return node; \ 789 } \ 790 } 791 792 #define RB_GENERATE_NEXT_POSTORDER(name, type, field, attr) \ 793 /* ARGSUSED */ \ 794 attr struct type * \ 795 name##_RB_NEXT_POSTORDER(struct type *elm) \ 796 { \ 797 struct type *parent = NULL; \ 798 if(elm == NULL) \ 799 return NULL; \ 800 parent = RB_PARENT(elm, field); \ 801 if (parent != NULL && elm == RB_LEFT(parent, field) && \ 802 RB_RIGHT(parent, field) != NULL) \ 803 return name##_RB_LEFT_DEEPEST(RB_RIGHT(parent, field)); \ 804 else \ 805 return parent; \ 806 } 807 808 #define RB_GENERATE_FIRST_POSTORDER(name, type, field, attr) \ 809 attr struct type * \ 810 name##_RB_FIRST_POSTORDER(struct name *head) \ 811 { \ 812 if(head == NULL || RB_ROOT(head) == NULL) \ 813 return NULL; \ 814 return(name##_RB_LEFT_DEEPEST(RB_ROOT(head))); \ 815 } 816 817 #define RB_NEGINF -1 818 #define RB_INF 1 819 820 #define RB_INSERT(name, x, y) name##_RB_INSERT(x, y) 821 #define RB_REMOVE(name, x, y) name##_RB_REMOVE(x, y) 822 #define RB_FIND(name, x, y) name##_RB_FIND(x, y) 823 #define RB_NFIND(name, x, y) name##_RB_NFIND(x, y) 824 #define RB_NEXT(name, x, y) name##_RB_NEXT(y) 825 #define RB_PREV(name, x, y) name##_RB_PREV(y) 826 #define RB_MIN(name, x) name##_RB_MINMAX(x, RB_NEGINF) 827 #define RB_MAX(name, x) name##_RB_MINMAX(x, RB_INF) 828 829 #define RB_FOREACH(x, name, head) \ 830 for ((x) = RB_MIN(name, head); \ 831 (x) != NULL; \ 832 (x) = name##_RB_NEXT(x)) 833 834 #define RB_FOREACH_FROM(x, name, y) \ 835 for ((x) = (y); \ 836 ((x) != NULL) && ((y) = name##_RB_NEXT(x), (x) != NULL); \ 837 (x) = (y)) 838 839 #define RB_FOREACH_SAFE(x, name, head, y) \ 840 for ((x) = RB_MIN(name, head); \ 841 ((x) != NULL) && ((y) = name##_RB_NEXT(x), (x) != NULL); \ 842 (x) = (y)) 843 844 #define RB_FOREACH_REVERSE(x, name, head) \ 845 for ((x) = RB_MAX(name, head); \ 846 (x) != NULL; \ 847 (x) = name##_RB_PREV(x)) 848 849 #define RB_FOREACH_REVERSE_FROM(x, name, y) \ 850 for ((x) = (y); \ 851 ((x) != NULL) && ((y) = name##_RB_PREV(x), (x) != NULL); \ 852 (x) = (y)) 853 854 #define RB_FOREACH_REVERSE_SAFE(x, name, head, y) \ 855 for ((x) = RB_MAX(name, head); \ 856 ((x) != NULL) && ((y) = name##_RB_PREV(x), (x) != NULL); \ 857 (x) = (y)) 858 859 #define RB_POSTORDER_FOREACH_SAFE(x, name, head, y) \ 860 for ((x) = name##_RB_FIRST_POSTORDER(head); \ 861 ((x) != NULL) && ({ (y) = name##_RB_NEXT_POSTORDER(x); 1; });\ 862 (x) = (y)) 863 864 #ifdef __cplusplus 865 #if __cplusplus 866 } 867 #endif /* __cplusplus */ 868 #endif /* __cplusplus */ 869 870 #endif /* _SYS_TREE_H_ */ 871