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$ */ 4 5 /*- 6 * SPDX-License-Identifier: BSD-2-Clause-FreeBSD 7 * 8 * Copyright 2002 Niels Provos <[email protected]> 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 /* 38 * This file defines data structures for different types of trees: 39 * splay trees and rank-balanced trees. 40 * 41 * A splay tree is a self-organizing data structure. Every operation 42 * on the tree causes a splay to happen. The splay moves the requested 43 * node to the root of the tree and partly rebalances it. 44 * 45 * This has the benefit that request locality causes faster lookups as 46 * the requested nodes move to the top of the tree. On the other hand, 47 * every lookup causes memory writes. 48 * 49 * The Balance Theorem bounds the total access time for m operations 50 * and n inserts on an initially empty tree as O((m + n)lg n). The 51 * amortized cost for a sequence of m accesses to a splay tree is O(lg n); 52 * 53 * A rank-balanced tree is a binary search tree with an integer 54 * rank-difference as an attribute of each pointer from parent to child. 55 * The sum of the rank-differences on any path from a node down to null is 56 * the same, and defines the rank of that node. The rank of the null node 57 * is -1. 58 * 59 * Different additional conditions define different sorts of balanced 60 * trees, including "red-black" and "AVL" trees. The set of conditions 61 * applied here are the "weak-AVL" conditions of Haeupler, Sen and Tarjan: 62 * - every rank-difference is 1 or 2. 63 * - the rank of any leaf is 1. 64 * 65 * For historical reasons, rank differences that are even are associated 66 * with the color red (Rank-Even-Difference), and the child that a red edge 67 * points to is called a red child. 68 * 69 * Every operation on a rank-balanced tree is bounded as O(lg n). 70 * The maximum height of a rank-balanced 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 __unused __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 __unused __inline 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 __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 rank-balanced 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_ENTRY(type) \ 320 struct { \ 321 struct type *rbe_left; /* left element */ \ 322 struct type *rbe_right; /* right element */ \ 323 struct type *rbe_parent; /* parent element */ \ 324 } 325 326 #define RB_LEFT(elm, field) (elm)->field.rbe_left 327 #define RB_RIGHT(elm, field) (elm)->field.rbe_right 328 329 /* 330 * With the expectation that any object of struct type has an 331 * address that is a multiple of 4, and that therefore the 332 * 2 least significant bits of a pointer to struct type are 333 * always zero, this implementation sets those bits to indicate 334 * that the left or right child of the tree node is "red". 335 */ 336 #define RB_UP(elm, field) (elm)->field.rbe_parent 337 #define RB_BITS(elm, field) (*(__uintptr_t *)&RB_UP(elm, field)) 338 #define RB_RED_L ((__uintptr_t)1) 339 #define RB_RED_R ((__uintptr_t)2) 340 #define RB_RED_MASK ((__uintptr_t)3) 341 #define RB_FLIP_LEFT(elm, field) (RB_BITS(elm, field) ^= RB_RED_L) 342 #define RB_FLIP_RIGHT(elm, field) (RB_BITS(elm, field) ^= RB_RED_R) 343 #define RB_RED_LEFT(elm, field) ((RB_BITS(elm, field) & RB_RED_L) != 0) 344 #define RB_RED_RIGHT(elm, field) ((RB_BITS(elm, field) & RB_RED_R) != 0) 345 #define RB_PARENT(elm, field) ((__typeof(RB_UP(elm, field))) \ 346 (RB_BITS(elm, field) & ~RB_RED_MASK)) 347 #define RB_ROOT(head) (head)->rbh_root 348 #define RB_EMPTY(head) (RB_ROOT(head) == NULL) 349 350 #define RB_SET_PARENT(dst, src, field) do { \ 351 RB_BITS(dst, field) &= RB_RED_MASK; \ 352 RB_BITS(dst, field) |= (__uintptr_t)src; \ 353 } while (/*CONSTCOND*/ 0) 354 355 #define RB_SET(elm, parent, field) do { \ 356 RB_UP(elm, field) = parent; \ 357 RB_LEFT(elm, field) = RB_RIGHT(elm, field) = NULL; \ 358 } while (/*CONSTCOND*/ 0) 359 360 #define RB_COLOR(elm, field) (RB_PARENT(elm, field) == NULL ? 0 : \ 361 RB_LEFT(RB_PARENT(elm, field), field) == elm ? \ 362 RB_RED_LEFT(RB_PARENT(elm, field), field) : \ 363 RB_RED_RIGHT(RB_PARENT(elm, field), field)) 364 365 /* 366 * Something to be invoked in a loop at the root of every modified subtree, 367 * from the bottom up to the root, to update augmented node data. 368 */ 369 #ifndef RB_AUGMENT 370 #define RB_AUGMENT(x) break 371 #endif 372 373 #define RB_SWAP_CHILD(head, out, in, field) do { \ 374 if (RB_PARENT(out, field) == NULL) \ 375 RB_ROOT(head) = (in); \ 376 else if ((out) == RB_LEFT(RB_PARENT(out, field), field)) \ 377 RB_LEFT(RB_PARENT(out, field), field) = (in); \ 378 else \ 379 RB_RIGHT(RB_PARENT(out, field), field) = (in); \ 380 } while (/*CONSTCOND*/ 0) 381 382 #define RB_ROTATE_LEFT(head, elm, tmp, field) do { \ 383 (tmp) = RB_RIGHT(elm, field); \ 384 if ((RB_RIGHT(elm, field) = RB_LEFT(tmp, field)) != NULL) { \ 385 RB_SET_PARENT(RB_RIGHT(elm, field), elm, field); \ 386 } \ 387 RB_SET_PARENT(tmp, RB_PARENT(elm, field), field); \ 388 RB_SWAP_CHILD(head, elm, tmp, field); \ 389 RB_LEFT(tmp, field) = (elm); \ 390 RB_SET_PARENT(elm, tmp, field); \ 391 RB_AUGMENT(elm); \ 392 } while (/*CONSTCOND*/ 0) 393 394 #define RB_ROTATE_RIGHT(head, elm, tmp, field) do { \ 395 (tmp) = RB_LEFT(elm, field); \ 396 if ((RB_LEFT(elm, field) = RB_RIGHT(tmp, field)) != NULL) { \ 397 RB_SET_PARENT(RB_LEFT(elm, field), elm, field); \ 398 } \ 399 RB_SET_PARENT(tmp, RB_PARENT(elm, field), field); \ 400 RB_SWAP_CHILD(head, elm, tmp, field); \ 401 RB_RIGHT(tmp, field) = (elm); \ 402 RB_SET_PARENT(elm, tmp, field); \ 403 RB_AUGMENT(elm); \ 404 } while (/*CONSTCOND*/ 0) 405 406 /* Generates prototypes and inline functions */ 407 #define RB_PROTOTYPE(name, type, field, cmp) \ 408 RB_PROTOTYPE_INTERNAL(name, type, field, cmp,) 409 #define RB_PROTOTYPE_STATIC(name, type, field, cmp) \ 410 RB_PROTOTYPE_INTERNAL(name, type, field, cmp, __unused static) 411 #define RB_PROTOTYPE_INTERNAL(name, type, field, cmp, attr) \ 412 RB_PROTOTYPE_INSERT_COLOR(name, type, attr); \ 413 RB_PROTOTYPE_REMOVE_COLOR(name, type, attr); \ 414 RB_PROTOTYPE_INSERT(name, type, attr); \ 415 RB_PROTOTYPE_REMOVE(name, type, attr); \ 416 RB_PROTOTYPE_FIND(name, type, attr); \ 417 RB_PROTOTYPE_NFIND(name, type, attr); \ 418 RB_PROTOTYPE_NEXT(name, type, attr); \ 419 RB_PROTOTYPE_PREV(name, type, attr); \ 420 RB_PROTOTYPE_MINMAX(name, type, attr); \ 421 RB_PROTOTYPE_REINSERT(name, type, attr); 422 #define RB_PROTOTYPE_INSERT_COLOR(name, type, attr) \ 423 attr void name##_RB_INSERT_COLOR(struct name *, struct type *) 424 #define RB_PROTOTYPE_REMOVE_COLOR(name, type, attr) \ 425 attr void name##_RB_REMOVE_COLOR(struct name *, \ 426 struct type *, struct type *) 427 #define RB_PROTOTYPE_REMOVE(name, type, attr) \ 428 attr struct type *name##_RB_REMOVE(struct name *, struct type *) 429 #define RB_PROTOTYPE_INSERT(name, type, attr) \ 430 attr struct type *name##_RB_INSERT(struct name *, struct type *) 431 #define RB_PROTOTYPE_FIND(name, type, attr) \ 432 attr struct type *name##_RB_FIND(struct name *, struct type *) 433 #define RB_PROTOTYPE_NFIND(name, type, attr) \ 434 attr struct type *name##_RB_NFIND(struct name *, struct type *) 435 #define RB_PROTOTYPE_NEXT(name, type, attr) \ 436 attr struct type *name##_RB_NEXT(struct type *) 437 #define RB_PROTOTYPE_PREV(name, type, attr) \ 438 attr struct type *name##_RB_PREV(struct type *) 439 #define RB_PROTOTYPE_MINMAX(name, type, attr) \ 440 attr struct type *name##_RB_MINMAX(struct name *, int) 441 #define RB_PROTOTYPE_REINSERT(name, type, attr) \ 442 attr struct type *name##_RB_REINSERT(struct name *, struct type *) 443 444 /* Main rb operation. 445 * Moves node close to the key of elm to top 446 */ 447 #define RB_GENERATE(name, type, field, cmp) \ 448 RB_GENERATE_INTERNAL(name, type, field, cmp,) 449 #define RB_GENERATE_STATIC(name, type, field, cmp) \ 450 RB_GENERATE_INTERNAL(name, type, field, cmp, __unused static) 451 #define RB_GENERATE_INTERNAL(name, type, field, cmp, attr) \ 452 RB_GENERATE_INSERT_COLOR(name, type, field, attr) \ 453 RB_GENERATE_REMOVE_COLOR(name, type, field, attr) \ 454 RB_GENERATE_INSERT(name, type, field, cmp, attr) \ 455 RB_GENERATE_REMOVE(name, type, field, attr) \ 456 RB_GENERATE_FIND(name, type, field, cmp, attr) \ 457 RB_GENERATE_NFIND(name, type, field, cmp, attr) \ 458 RB_GENERATE_NEXT(name, type, field, attr) \ 459 RB_GENERATE_PREV(name, type, field, attr) \ 460 RB_GENERATE_MINMAX(name, type, field, attr) \ 461 RB_GENERATE_REINSERT(name, type, field, cmp, attr) 462 463 #define RB_GENERATE_INSERT_COLOR(name, type, field, attr) \ 464 attr void \ 465 name##_RB_INSERT_COLOR(struct name *head, struct type *elm) \ 466 { \ 467 struct type *child, *parent; \ 468 while ((parent = RB_PARENT(elm, field)) != NULL) { \ 469 if (RB_LEFT(parent, field) == elm) { \ 470 if (RB_RED_LEFT(parent, field)) { \ 471 RB_FLIP_LEFT(parent, field); \ 472 return; \ 473 } \ 474 RB_FLIP_RIGHT(parent, field); \ 475 if (RB_RED_RIGHT(parent, field)) { \ 476 elm = parent; \ 477 continue; \ 478 } \ 479 if (!RB_RED_RIGHT(elm, field)) { \ 480 RB_FLIP_LEFT(elm, field); \ 481 RB_ROTATE_LEFT(head, elm, child, field);\ 482 if (RB_RED_LEFT(child, field)) \ 483 RB_FLIP_RIGHT(elm, field); \ 484 else if (RB_RED_RIGHT(child, field)) \ 485 RB_FLIP_LEFT(parent, field); \ 486 elm = child; \ 487 } \ 488 RB_ROTATE_RIGHT(head, parent, elm, field); \ 489 } else { \ 490 if (RB_RED_RIGHT(parent, field)) { \ 491 RB_FLIP_RIGHT(parent, field); \ 492 return; \ 493 } \ 494 RB_FLIP_LEFT(parent, field); \ 495 if (RB_RED_LEFT(parent, field)) { \ 496 elm = parent; \ 497 continue; \ 498 } \ 499 if (!RB_RED_LEFT(elm, field)) { \ 500 RB_FLIP_RIGHT(elm, field); \ 501 RB_ROTATE_RIGHT(head, elm, child, field);\ 502 if (RB_RED_RIGHT(child, field)) \ 503 RB_FLIP_LEFT(elm, field); \ 504 else if (RB_RED_LEFT(child, field)) \ 505 RB_FLIP_RIGHT(parent, field); \ 506 elm = child; \ 507 } \ 508 RB_ROTATE_LEFT(head, parent, elm, field); \ 509 } \ 510 RB_BITS(elm, field) &= ~RB_RED_MASK; \ 511 break; \ 512 } \ 513 } 514 515 #define RB_GENERATE_REMOVE_COLOR(name, type, field, attr) \ 516 attr void \ 517 name##_RB_REMOVE_COLOR(struct name *head, \ 518 struct type *parent, struct type *elm) \ 519 { \ 520 struct type *sib; \ 521 if (RB_LEFT(parent, field) == elm && \ 522 RB_RIGHT(parent, field) == elm) { \ 523 RB_BITS(parent, field) &= ~RB_RED_MASK; \ 524 elm = parent; \ 525 parent = RB_PARENT(elm, field); \ 526 if (parent == NULL) \ 527 return; \ 528 } \ 529 do { \ 530 if (RB_LEFT(parent, field) == elm) { \ 531 if (!RB_RED_LEFT(parent, field)) { \ 532 RB_FLIP_LEFT(parent, field); \ 533 return; \ 534 } \ 535 if (RB_RED_RIGHT(parent, field)) { \ 536 RB_FLIP_RIGHT(parent, field); \ 537 elm = parent; \ 538 continue; \ 539 } \ 540 sib = RB_RIGHT(parent, field); \ 541 if ((~RB_BITS(sib, field) & RB_RED_MASK) == 0) {\ 542 RB_BITS(sib, field) &= ~RB_RED_MASK; \ 543 elm = parent; \ 544 continue; \ 545 } \ 546 RB_FLIP_RIGHT(sib, field); \ 547 if (RB_RED_LEFT(sib, field)) \ 548 RB_FLIP_LEFT(parent, field); \ 549 else if (!RB_RED_RIGHT(sib, field)) { \ 550 RB_FLIP_LEFT(parent, field); \ 551 RB_ROTATE_RIGHT(head, sib, elm, field); \ 552 if (RB_RED_RIGHT(elm, field)) \ 553 RB_FLIP_LEFT(sib, field); \ 554 if (RB_RED_LEFT(elm, field)) \ 555 RB_FLIP_RIGHT(parent, field); \ 556 RB_BITS(elm, field) |= RB_RED_MASK; \ 557 sib = elm; \ 558 } \ 559 RB_ROTATE_LEFT(head, parent, sib, field); \ 560 } else { \ 561 if (!RB_RED_RIGHT(parent, field)) { \ 562 RB_FLIP_RIGHT(parent, field); \ 563 return; \ 564 } \ 565 if (RB_RED_LEFT(parent, field)) { \ 566 RB_FLIP_LEFT(parent, field); \ 567 elm = parent; \ 568 continue; \ 569 } \ 570 sib = RB_LEFT(parent, field); \ 571 if ((~RB_BITS(sib, field) & RB_RED_MASK) == 0) {\ 572 RB_BITS(sib, field) &= ~RB_RED_MASK; \ 573 elm = parent; \ 574 continue; \ 575 } \ 576 RB_FLIP_LEFT(sib, field); \ 577 if (RB_RED_RIGHT(sib, field)) \ 578 RB_FLIP_RIGHT(parent, field); \ 579 else if (!RB_RED_LEFT(sib, field)) { \ 580 RB_FLIP_RIGHT(parent, field); \ 581 RB_ROTATE_LEFT(head, sib, elm, field); \ 582 if (RB_RED_LEFT(elm, field)) \ 583 RB_FLIP_RIGHT(sib, field); \ 584 if (RB_RED_RIGHT(elm, field)) \ 585 RB_FLIP_LEFT(parent, field); \ 586 RB_BITS(elm, field) |= RB_RED_MASK; \ 587 sib = elm; \ 588 } \ 589 RB_ROTATE_RIGHT(head, parent, sib, field); \ 590 } \ 591 break; \ 592 } while ((parent = RB_PARENT(elm, field)) != NULL); \ 593 } 594 595 #define RB_GENERATE_REMOVE(name, type, field, attr) \ 596 attr struct type * \ 597 name##_RB_REMOVE(struct name *head, struct type *elm) \ 598 { \ 599 struct type *child, *old, *parent, *right; \ 600 \ 601 old = elm; \ 602 parent = RB_PARENT(elm, field); \ 603 right = RB_RIGHT(elm, field); \ 604 if (RB_LEFT(elm, field) == NULL) \ 605 elm = child = right; \ 606 else if (right == NULL) \ 607 elm = child = RB_LEFT(elm, field); \ 608 else { \ 609 if ((child = RB_LEFT(right, field)) == NULL) { \ 610 child = RB_RIGHT(right, field); \ 611 RB_RIGHT(old, field) = child; \ 612 parent = elm = right; \ 613 } else { \ 614 do \ 615 elm = child; \ 616 while ((child = RB_LEFT(elm, field)) != NULL); \ 617 child = RB_RIGHT(elm, field); \ 618 parent = RB_PARENT(elm, field); \ 619 RB_LEFT(parent, field) = child; \ 620 RB_SET_PARENT(RB_RIGHT(old, field), elm, field);\ 621 } \ 622 RB_SET_PARENT(RB_LEFT(old, field), elm, field); \ 623 elm->field = old->field; \ 624 } \ 625 RB_SWAP_CHILD(head, old, elm, field); \ 626 if (child != NULL) \ 627 RB_SET_PARENT(child, parent, field); \ 628 if (parent != NULL) \ 629 name##_RB_REMOVE_COLOR(head, parent, child); \ 630 while (parent != NULL) { \ 631 RB_AUGMENT(parent); \ 632 parent = RB_PARENT(parent, field); \ 633 } \ 634 return (old); \ 635 } 636 637 #define RB_GENERATE_INSERT(name, type, field, cmp, attr) \ 638 /* Inserts a node into the RB tree */ \ 639 attr struct type * \ 640 name##_RB_INSERT(struct name *head, struct type *elm) \ 641 { \ 642 struct type *tmp; \ 643 struct type *parent = NULL; \ 644 int comp = 0; \ 645 tmp = RB_ROOT(head); \ 646 while (tmp) { \ 647 parent = tmp; \ 648 comp = (cmp)(elm, parent); \ 649 if (comp < 0) \ 650 tmp = RB_LEFT(tmp, field); \ 651 else if (comp > 0) \ 652 tmp = RB_RIGHT(tmp, field); \ 653 else \ 654 return (tmp); \ 655 } \ 656 RB_SET(elm, parent, field); \ 657 if (parent == NULL) \ 658 RB_ROOT(head) = elm; \ 659 else if (comp < 0) \ 660 RB_LEFT(parent, field) = elm; \ 661 else \ 662 RB_RIGHT(parent, field) = elm; \ 663 name##_RB_INSERT_COLOR(head, elm); \ 664 while (elm != NULL) { \ 665 RB_AUGMENT(elm); \ 666 elm = RB_PARENT(elm, field); \ 667 } \ 668 return (NULL); \ 669 } 670 671 #define RB_GENERATE_FIND(name, type, field, cmp, attr) \ 672 /* Finds the node with the same key as elm */ \ 673 attr struct type * \ 674 name##_RB_FIND(struct name *head, struct type *elm) \ 675 { \ 676 struct type *tmp = RB_ROOT(head); \ 677 int comp; \ 678 while (tmp) { \ 679 comp = cmp(elm, tmp); \ 680 if (comp < 0) \ 681 tmp = RB_LEFT(tmp, field); \ 682 else if (comp > 0) \ 683 tmp = RB_RIGHT(tmp, field); \ 684 else \ 685 return (tmp); \ 686 } \ 687 return (NULL); \ 688 } 689 690 #define RB_GENERATE_NFIND(name, type, field, cmp, attr) \ 691 /* Finds the first node greater than or equal to the search key */ \ 692 attr struct type * \ 693 name##_RB_NFIND(struct name *head, struct type *elm) \ 694 { \ 695 struct type *tmp = RB_ROOT(head); \ 696 struct type *res = NULL; \ 697 int comp; \ 698 while (tmp) { \ 699 comp = cmp(elm, tmp); \ 700 if (comp < 0) { \ 701 res = tmp; \ 702 tmp = RB_LEFT(tmp, field); \ 703 } \ 704 else if (comp > 0) \ 705 tmp = RB_RIGHT(tmp, field); \ 706 else \ 707 return (tmp); \ 708 } \ 709 return (res); \ 710 } 711 712 #define RB_GENERATE_NEXT(name, type, field, attr) \ 713 /* ARGSUSED */ \ 714 attr struct type * \ 715 name##_RB_NEXT(struct type *elm) \ 716 { \ 717 if (RB_RIGHT(elm, field)) { \ 718 elm = RB_RIGHT(elm, field); \ 719 while (RB_LEFT(elm, field)) \ 720 elm = RB_LEFT(elm, field); \ 721 } else { \ 722 if (RB_PARENT(elm, field) && \ 723 (elm == RB_LEFT(RB_PARENT(elm, field), field))) \ 724 elm = RB_PARENT(elm, field); \ 725 else { \ 726 while (RB_PARENT(elm, field) && \ 727 (elm == RB_RIGHT(RB_PARENT(elm, field), field)))\ 728 elm = RB_PARENT(elm, field); \ 729 elm = RB_PARENT(elm, field); \ 730 } \ 731 } \ 732 return (elm); \ 733 } 734 735 #define RB_GENERATE_PREV(name, type, field, attr) \ 736 /* ARGSUSED */ \ 737 attr struct type * \ 738 name##_RB_PREV(struct type *elm) \ 739 { \ 740 if (RB_LEFT(elm, field)) { \ 741 elm = RB_LEFT(elm, field); \ 742 while (RB_RIGHT(elm, field)) \ 743 elm = RB_RIGHT(elm, field); \ 744 } else { \ 745 if (RB_PARENT(elm, field) && \ 746 (elm == RB_RIGHT(RB_PARENT(elm, field), field))) \ 747 elm = RB_PARENT(elm, field); \ 748 else { \ 749 while (RB_PARENT(elm, field) && \ 750 (elm == RB_LEFT(RB_PARENT(elm, field), field)))\ 751 elm = RB_PARENT(elm, field); \ 752 elm = RB_PARENT(elm, field); \ 753 } \ 754 } \ 755 return (elm); \ 756 } 757 758 #define RB_GENERATE_MINMAX(name, type, field, attr) \ 759 attr struct type * \ 760 name##_RB_MINMAX(struct name *head, int val) \ 761 { \ 762 struct type *tmp = RB_ROOT(head); \ 763 struct type *parent = NULL; \ 764 while (tmp) { \ 765 parent = tmp; \ 766 if (val < 0) \ 767 tmp = RB_LEFT(tmp, field); \ 768 else \ 769 tmp = RB_RIGHT(tmp, field); \ 770 } \ 771 return (parent); \ 772 } 773 774 #define RB_GENERATE_REINSERT(name, type, field, cmp, attr) \ 775 attr struct type * \ 776 name##_RB_REINSERT(struct name *head, struct type *elm) \ 777 { \ 778 struct type *cmpelm; \ 779 if (((cmpelm = RB_PREV(name, head, elm)) != NULL && \ 780 cmp(cmpelm, elm) >= 0) || \ 781 ((cmpelm = RB_NEXT(name, head, elm)) != NULL && \ 782 cmp(elm, cmpelm) >= 0)) { \ 783 /* XXXLAS: Remove/insert is heavy handed. */ \ 784 RB_REMOVE(name, head, elm); \ 785 return (RB_INSERT(name, head, elm)); \ 786 } \ 787 return (NULL); \ 788 } \ 789 790 #define RB_NEGINF -1 791 #define RB_INF 1 792 793 #define RB_INSERT(name, x, y) name##_RB_INSERT(x, y) 794 #define RB_REMOVE(name, x, y) name##_RB_REMOVE(x, y) 795 #define RB_FIND(name, x, y) name##_RB_FIND(x, y) 796 #define RB_NFIND(name, x, y) name##_RB_NFIND(x, y) 797 #define RB_NEXT(name, x, y) name##_RB_NEXT(y) 798 #define RB_PREV(name, x, y) name##_RB_PREV(y) 799 #define RB_MIN(name, x) name##_RB_MINMAX(x, RB_NEGINF) 800 #define RB_MAX(name, x) name##_RB_MINMAX(x, RB_INF) 801 #define RB_REINSERT(name, x, y) name##_RB_REINSERT(x, y) 802 803 #define RB_FOREACH(x, name, head) \ 804 for ((x) = RB_MIN(name, head); \ 805 (x) != NULL; \ 806 (x) = name##_RB_NEXT(x)) 807 808 #define RB_FOREACH_FROM(x, name, y) \ 809 for ((x) = (y); \ 810 ((x) != NULL) && ((y) = name##_RB_NEXT(x), (x) != NULL); \ 811 (x) = (y)) 812 813 #define RB_FOREACH_SAFE(x, name, head, y) \ 814 for ((x) = RB_MIN(name, head); \ 815 ((x) != NULL) && ((y) = name##_RB_NEXT(x), (x) != NULL); \ 816 (x) = (y)) 817 818 #define RB_FOREACH_REVERSE(x, name, head) \ 819 for ((x) = RB_MAX(name, head); \ 820 (x) != NULL; \ 821 (x) = name##_RB_PREV(x)) 822 823 #define RB_FOREACH_REVERSE_FROM(x, name, y) \ 824 for ((x) = (y); \ 825 ((x) != NULL) && ((y) = name##_RB_PREV(x), (x) != NULL); \ 826 (x) = (y)) 827 828 #define RB_FOREACH_REVERSE_SAFE(x, name, head, y) \ 829 for ((x) = RB_MAX(name, head); \ 830 ((x) != NULL) && ((y) = name##_RB_PREV(x), (x) != NULL); \ 831 (x) = (y)) 832 833 #endif /* _SYS_TREE_H_ */ 834