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