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 <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 /* 38 * This file defines data structures for different types of trees: 39 * splay trees and red-black 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 red-black tree is a binary search tree with the node color as an 54 * extra attribute. It fulfills a set of conditions: 55 * - every search path from the root to a leaf consists of the 56 * same number of black nodes, 57 * - each red node (except for the root) has a black parent, 58 * - each leaf node is black. 59 * 60 * Every operation on a red-black tree is bounded as O(lg n). 61 * The maximum height of a red-black tree is 2lg (n+1). 62 */ 63 64 #define SPLAY_HEAD(name, type) \ 65 struct name { \ 66 struct type *sph_root; /* root of the tree */ \ 67 } 68 69 #define SPLAY_INITIALIZER(root) \ 70 { NULL } 71 72 #define SPLAY_INIT(root) do { \ 73 (root)->sph_root = NULL; \ 74 } while (/*CONSTCOND*/ 0) 75 76 #define SPLAY_ENTRY(type) \ 77 struct { \ 78 struct type *spe_left; /* left element */ \ 79 struct type *spe_right; /* right element */ \ 80 } 81 82 #define SPLAY_LEFT(elm, field) (elm)->field.spe_left 83 #define SPLAY_RIGHT(elm, field) (elm)->field.spe_right 84 #define SPLAY_ROOT(head) (head)->sph_root 85 #define SPLAY_EMPTY(head) (SPLAY_ROOT(head) == NULL) 86 87 /* SPLAY_ROTATE_{LEFT,RIGHT} expect that tmp hold SPLAY_{RIGHT,LEFT} */ 88 #define SPLAY_ROTATE_RIGHT(head, tmp, field) do { \ 89 SPLAY_LEFT((head)->sph_root, field) = SPLAY_RIGHT(tmp, field); \ 90 SPLAY_RIGHT(tmp, field) = (head)->sph_root; \ 91 (head)->sph_root = tmp; \ 92 } while (/*CONSTCOND*/ 0) 93 94 #define SPLAY_ROTATE_LEFT(head, tmp, field) do { \ 95 SPLAY_RIGHT((head)->sph_root, field) = SPLAY_LEFT(tmp, field); \ 96 SPLAY_LEFT(tmp, field) = (head)->sph_root; \ 97 (head)->sph_root = tmp; \ 98 } while (/*CONSTCOND*/ 0) 99 100 #define SPLAY_LINKLEFT(head, tmp, field) do { \ 101 SPLAY_LEFT(tmp, field) = (head)->sph_root; \ 102 tmp = (head)->sph_root; \ 103 (head)->sph_root = SPLAY_LEFT((head)->sph_root, field); \ 104 } while (/*CONSTCOND*/ 0) 105 106 #define SPLAY_LINKRIGHT(head, tmp, field) do { \ 107 SPLAY_RIGHT(tmp, field) = (head)->sph_root; \ 108 tmp = (head)->sph_root; \ 109 (head)->sph_root = SPLAY_RIGHT((head)->sph_root, field); \ 110 } while (/*CONSTCOND*/ 0) 111 112 #define SPLAY_ASSEMBLE(head, node, left, right, field) do { \ 113 SPLAY_RIGHT(left, field) = SPLAY_LEFT((head)->sph_root, field); \ 114 SPLAY_LEFT(right, field) = SPLAY_RIGHT((head)->sph_root, field);\ 115 SPLAY_LEFT((head)->sph_root, field) = SPLAY_RIGHT(node, field); \ 116 SPLAY_RIGHT((head)->sph_root, field) = SPLAY_LEFT(node, field); \ 117 } while (/*CONSTCOND*/ 0) 118 119 /* Generates prototypes and inline functions */ 120 121 #define SPLAY_PROTOTYPE(name, type, field, cmp) \ 122 void name##_SPLAY(struct name *, struct type *); \ 123 void name##_SPLAY_MINMAX(struct name *, int); \ 124 struct type *name##_SPLAY_INSERT(struct name *, struct type *); \ 125 struct type *name##_SPLAY_REMOVE(struct name *, struct type *); \ 126 \ 127 /* Finds the node with the same key as elm */ \ 128 static __unused __inline struct type * \ 129 name##_SPLAY_FIND(struct name *head, struct type *elm) \ 130 { \ 131 if (SPLAY_EMPTY(head)) \ 132 return(NULL); \ 133 name##_SPLAY(head, elm); \ 134 if ((cmp)(elm, (head)->sph_root) == 0) \ 135 return (head->sph_root); \ 136 return (NULL); \ 137 } \ 138 \ 139 static __unused __inline struct type * \ 140 name##_SPLAY_NEXT(struct name *head, struct type *elm) \ 141 { \ 142 name##_SPLAY(head, elm); \ 143 if (SPLAY_RIGHT(elm, field) != NULL) { \ 144 elm = SPLAY_RIGHT(elm, field); \ 145 while (SPLAY_LEFT(elm, field) != NULL) { \ 146 elm = SPLAY_LEFT(elm, field); \ 147 } \ 148 } else \ 149 elm = NULL; \ 150 return (elm); \ 151 } \ 152 \ 153 static __unused __inline struct type * \ 154 name##_SPLAY_MIN_MAX(struct name *head, int val) \ 155 { \ 156 name##_SPLAY_MINMAX(head, val); \ 157 return (SPLAY_ROOT(head)); \ 158 } 159 160 /* Main splay operation. 161 * Moves node close to the key of elm to top 162 */ 163 #define SPLAY_GENERATE(name, type, field, cmp) \ 164 struct type * \ 165 name##_SPLAY_INSERT(struct name *head, struct type *elm) \ 166 { \ 167 if (SPLAY_EMPTY(head)) { \ 168 SPLAY_LEFT(elm, field) = SPLAY_RIGHT(elm, field) = NULL; \ 169 } else { \ 170 int __comp; \ 171 name##_SPLAY(head, elm); \ 172 __comp = (cmp)(elm, (head)->sph_root); \ 173 if(__comp < 0) { \ 174 SPLAY_LEFT(elm, field) = SPLAY_LEFT((head)->sph_root, field);\ 175 SPLAY_RIGHT(elm, field) = (head)->sph_root; \ 176 SPLAY_LEFT((head)->sph_root, field) = NULL; \ 177 } else if (__comp > 0) { \ 178 SPLAY_RIGHT(elm, field) = SPLAY_RIGHT((head)->sph_root, field);\ 179 SPLAY_LEFT(elm, field) = (head)->sph_root; \ 180 SPLAY_RIGHT((head)->sph_root, field) = NULL; \ 181 } else \ 182 return ((head)->sph_root); \ 183 } \ 184 (head)->sph_root = (elm); \ 185 return (NULL); \ 186 } \ 187 \ 188 struct type * \ 189 name##_SPLAY_REMOVE(struct name *head, struct type *elm) \ 190 { \ 191 struct type *__tmp; \ 192 if (SPLAY_EMPTY(head)) \ 193 return (NULL); \ 194 name##_SPLAY(head, elm); \ 195 if ((cmp)(elm, (head)->sph_root) == 0) { \ 196 if (SPLAY_LEFT((head)->sph_root, field) == NULL) { \ 197 (head)->sph_root = SPLAY_RIGHT((head)->sph_root, field);\ 198 } else { \ 199 __tmp = SPLAY_RIGHT((head)->sph_root, field); \ 200 (head)->sph_root = SPLAY_LEFT((head)->sph_root, field);\ 201 name##_SPLAY(head, elm); \ 202 SPLAY_RIGHT((head)->sph_root, field) = __tmp; \ 203 } \ 204 return (elm); \ 205 } \ 206 return (NULL); \ 207 } \ 208 \ 209 void \ 210 name##_SPLAY(struct name *head, struct type *elm) \ 211 { \ 212 struct type __node, *__left, *__right, *__tmp; \ 213 int __comp; \ 214 \ 215 SPLAY_LEFT(&__node, field) = SPLAY_RIGHT(&__node, field) = NULL;\ 216 __left = __right = &__node; \ 217 \ 218 while ((__comp = (cmp)(elm, (head)->sph_root)) != 0) { \ 219 if (__comp < 0) { \ 220 __tmp = SPLAY_LEFT((head)->sph_root, field); \ 221 if (__tmp == NULL) \ 222 break; \ 223 if ((cmp)(elm, __tmp) < 0){ \ 224 SPLAY_ROTATE_RIGHT(head, __tmp, field); \ 225 if (SPLAY_LEFT((head)->sph_root, field) == NULL)\ 226 break; \ 227 } \ 228 SPLAY_LINKLEFT(head, __right, field); \ 229 } else if (__comp > 0) { \ 230 __tmp = SPLAY_RIGHT((head)->sph_root, field); \ 231 if (__tmp == NULL) \ 232 break; \ 233 if ((cmp)(elm, __tmp) > 0){ \ 234 SPLAY_ROTATE_LEFT(head, __tmp, field); \ 235 if (SPLAY_RIGHT((head)->sph_root, field) == NULL)\ 236 break; \ 237 } \ 238 SPLAY_LINKRIGHT(head, __left, field); \ 239 } \ 240 } \ 241 SPLAY_ASSEMBLE(head, &__node, __left, __right, field); \ 242 } \ 243 \ 244 /* Splay with either the minimum or the maximum element \ 245 * Used to find minimum or maximum element in tree. \ 246 */ \ 247 void name##_SPLAY_MINMAX(struct name *head, int __comp) \ 248 { \ 249 struct type __node, *__left, *__right, *__tmp; \ 250 \ 251 SPLAY_LEFT(&__node, field) = SPLAY_RIGHT(&__node, field) = NULL;\ 252 __left = __right = &__node; \ 253 \ 254 while (1) { \ 255 if (__comp < 0) { \ 256 __tmp = SPLAY_LEFT((head)->sph_root, field); \ 257 if (__tmp == NULL) \ 258 break; \ 259 if (__comp < 0){ \ 260 SPLAY_ROTATE_RIGHT(head, __tmp, field); \ 261 if (SPLAY_LEFT((head)->sph_root, field) == NULL)\ 262 break; \ 263 } \ 264 SPLAY_LINKLEFT(head, __right, field); \ 265 } else if (__comp > 0) { \ 266 __tmp = SPLAY_RIGHT((head)->sph_root, field); \ 267 if (__tmp == NULL) \ 268 break; \ 269 if (__comp > 0) { \ 270 SPLAY_ROTATE_LEFT(head, __tmp, field); \ 271 if (SPLAY_RIGHT((head)->sph_root, field) == NULL)\ 272 break; \ 273 } \ 274 SPLAY_LINKRIGHT(head, __left, field); \ 275 } \ 276 } \ 277 SPLAY_ASSEMBLE(head, &__node, __left, __right, field); \ 278 } 279 280 #define SPLAY_NEGINF -1 281 #define SPLAY_INF 1 282 283 #define SPLAY_INSERT(name, x, y) name##_SPLAY_INSERT(x, y) 284 #define SPLAY_REMOVE(name, x, y) name##_SPLAY_REMOVE(x, y) 285 #define SPLAY_FIND(name, x, y) name##_SPLAY_FIND(x, y) 286 #define SPLAY_NEXT(name, x, y) name##_SPLAY_NEXT(x, y) 287 #define SPLAY_MIN(name, x) (SPLAY_EMPTY(x) ? NULL \ 288 : name##_SPLAY_MIN_MAX(x, SPLAY_NEGINF)) 289 #define SPLAY_MAX(name, x) (SPLAY_EMPTY(x) ? NULL \ 290 : name##_SPLAY_MIN_MAX(x, SPLAY_INF)) 291 292 #define SPLAY_FOREACH(x, name, head) \ 293 for ((x) = SPLAY_MIN(name, head); \ 294 (x) != NULL; \ 295 (x) = SPLAY_NEXT(name, head, x)) 296 297 /* Macros that define a red-black tree */ 298 #define RB_HEAD(name, type) \ 299 struct name { \ 300 struct type *rbh_root; /* root of the tree */ \ 301 } 302 303 #define RB_INITIALIZER(root) \ 304 { NULL } 305 306 #define RB_INIT(root) do { \ 307 (root)->rbh_root = NULL; \ 308 } while (/*CONSTCOND*/ 0) 309 310 #define RB_ENTRY(type) \ 311 struct { \ 312 struct type *rbe_left; /* left element */ \ 313 struct type *rbe_right; /* right element */ \ 314 struct type *rbe_parent; /* parent element */ \ 315 } 316 317 #define RB_LEFT(elm, field) (elm)->field.rbe_left 318 #define RB_RIGHT(elm, field) (elm)->field.rbe_right 319 320 /* 321 * With the expectation that any object of struct type has an 322 * address that is a multiple of 4, and that therefore the 323 * 2 least significant bits of a pointer to struct type are 324 * always zero, this implementation sets those bits to indicate 325 * that the left or right child of the tree node is "red". 326 */ 327 #define RB_UP(elm, field) (elm)->field.rbe_parent 328 #define RB_BITS(elm, field) *(__uintptr_t *)&RB_UP(elm, field) 329 #define RB_RED_L (__uintptr_t)1 330 #define RB_RED_R (__uintptr_t)2 331 #define RB_RED_MASK (__uintptr_t)3 332 #define RB_FLIP_LEFT(elm, field) (RB_BITS(elm, field) ^= RB_RED_L) 333 #define RB_FLIP_RIGHT(elm, field) (RB_BITS(elm, field) ^= RB_RED_R) 334 #define RB_RED_LEFT(elm, field) ((RB_BITS(elm, field) & RB_RED_L) != 0) 335 #define RB_RED_RIGHT(elm, field) ((RB_BITS(elm, field) & RB_RED_R) != 0) 336 #define RB_PARENT(elm, field) ((__typeof(RB_UP(elm, field))) \ 337 (RB_BITS(elm, field) & ~RB_RED_MASK)) 338 339 /* 340 * This header may appear in user code where 'bool' is not defined, 341 * so it defines its own boolean type to avoid breaking that code. 342 */ 343 #define RB_BOOL int 344 #define RB_TRUE 1 345 #define RB_FALSE 0 346 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 ? RB_FALSE : \ 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 *, struct type *) 426 #define RB_PROTOTYPE_REMOVE(name, type, attr) \ 427 attr struct type *name##_RB_REMOVE(struct name *, struct type *) 428 #define RB_PROTOTYPE_INSERT(name, type, attr) \ 429 attr struct type *name##_RB_INSERT(struct name *, struct type *) 430 #define RB_PROTOTYPE_FIND(name, type, attr) \ 431 attr struct type *name##_RB_FIND(struct name *, struct type *) 432 #define RB_PROTOTYPE_NFIND(name, type, attr) \ 433 attr struct type *name##_RB_NFIND(struct name *, struct type *) 434 #define RB_PROTOTYPE_NEXT(name, type, attr) \ 435 attr struct type *name##_RB_NEXT(struct type *) 436 #define RB_PROTOTYPE_PREV(name, type, attr) \ 437 attr struct type *name##_RB_PREV(struct type *) 438 #define RB_PROTOTYPE_MINMAX(name, type, attr) \ 439 attr struct type *name##_RB_MINMAX(struct name *, int) 440 #define RB_PROTOTYPE_REINSERT(name, type, attr) \ 441 attr struct type *name##_RB_REINSERT(struct name *, struct type *) 442 443 /* Main rb operation. 444 * Moves node close to the key of elm to top 445 */ 446 #define RB_GENERATE(name, type, field, cmp) \ 447 RB_GENERATE_INTERNAL(name, type, field, cmp,) 448 #define RB_GENERATE_STATIC(name, type, field, cmp) \ 449 RB_GENERATE_INTERNAL(name, type, field, cmp, __unused static) 450 #define RB_GENERATE_INTERNAL(name, type, field, cmp, attr) \ 451 RB_GENERATE_INSERT_COLOR(name, type, field, attr) \ 452 RB_GENERATE_REMOVE_COLOR(name, type, field, attr) \ 453 RB_GENERATE_INSERT(name, type, field, cmp, attr) \ 454 RB_GENERATE_REMOVE(name, type, field, attr) \ 455 RB_GENERATE_FIND(name, type, field, cmp, attr) \ 456 RB_GENERATE_NFIND(name, type, field, cmp, attr) \ 457 RB_GENERATE_NEXT(name, type, field, attr) \ 458 RB_GENERATE_PREV(name, type, field, attr) \ 459 RB_GENERATE_MINMAX(name, type, field, attr) \ 460 RB_GENERATE_REINSERT(name, type, field, cmp, attr) 461 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 *gparent, *parent; \ 468 while ((parent = RB_PARENT(elm, field)) != NULL) { \ 469 if (RB_LEFT(parent, field) == elm) \ 470 RB_FLIP_LEFT(parent, field); \ 471 else \ 472 RB_FLIP_RIGHT(parent, field); \ 473 if ((gparent = RB_PARENT(parent, field)) == NULL) \ 474 break; \ 475 if (RB_RED_LEFT(gparent, field) && \ 476 RB_RED_RIGHT(gparent, field)) { \ 477 RB_FLIP_LEFT(gparent, field); \ 478 RB_FLIP_RIGHT(gparent, field); \ 479 elm = gparent; \ 480 continue; \ 481 } \ 482 if (RB_RED_LEFT(gparent, field) && \ 483 parent == RB_LEFT(gparent, field)) { \ 484 if (RB_RIGHT(parent, field) == elm) { \ 485 RB_ROTATE_LEFT(head, parent, elm, field);\ 486 RB_FLIP_RIGHT(parent, field); \ 487 RB_FLIP_LEFT(elm, field); \ 488 parent = elm; \ 489 } \ 490 RB_ROTATE_RIGHT(head, gparent, parent, field); \ 491 RB_FLIP_LEFT(gparent, field); \ 492 RB_FLIP_RIGHT(parent, field); \ 493 } else if (RB_RED_RIGHT(gparent, field) && \ 494 parent == RB_RIGHT(gparent, field)) { \ 495 if (RB_LEFT(parent, field) == elm) { \ 496 RB_ROTATE_RIGHT(head, parent, elm, field);\ 497 RB_FLIP_LEFT(parent, field); \ 498 RB_FLIP_RIGHT(elm, field); \ 499 parent = elm; \ 500 } \ 501 RB_ROTATE_LEFT(head, gparent, parent, field); \ 502 RB_FLIP_RIGHT(gparent, field); \ 503 RB_FLIP_LEFT(parent, field); \ 504 } \ 505 break; \ 506 } \ 507 } 508 509 #define RB_GENERATE_REMOVE_COLOR(name, type, field, attr) \ 510 attr void \ 511 name##_RB_REMOVE_COLOR(struct name *head, struct type *par) \ 512 { \ 513 struct type *gpr, *sib, *nec; \ 514 RB_BOOL left_elm, left_par, red_gpr; \ 515 left_par = (RB_LEFT(par, field) == NULL); \ 516 do { \ 517 left_elm = left_par; \ 518 if (left_elm ? \ 519 !RB_RED_RIGHT(par, field) : \ 520 !RB_RED_LEFT(par, field)) { \ 521 gpr = RB_PARENT(par, field); \ 522 left_par = gpr != NULL && \ 523 RB_LEFT(gpr, field) == par; \ 524 red_gpr = gpr == NULL ? \ 525 RB_TRUE: RB_COLOR(par, field); \ 526 } \ 527 if (left_elm) { \ 528 if (RB_RED_RIGHT(par, field)) { \ 529 red_gpr = RB_TRUE; \ 530 RB_ROTATE_LEFT(head, par, gpr, field); \ 531 RB_FLIP_RIGHT(par, field); \ 532 RB_FLIP_LEFT(gpr, field); \ 533 } \ 534 sib = RB_RIGHT(par, field); \ 535 if (RB_RED_RIGHT(sib, field)) { \ 536 if (RB_RED_LEFT(sib, field)) { \ 537 RB_FLIP_LEFT(sib, field); \ 538 RB_FLIP_RIGHT(par, field); \ 539 } \ 540 RB_FLIP_RIGHT(sib, field); \ 541 } else if (RB_RED_LEFT(sib, field)) { \ 542 RB_ROTATE_RIGHT(head, sib, nec, field); \ 543 RB_FLIP_LEFT(sib, field); \ 544 sib = nec; \ 545 } else { \ 546 RB_FLIP_RIGHT(par, field); \ 547 par = gpr; \ 548 continue; \ 549 } \ 550 RB_ROTATE_LEFT(head, par, sib, field); \ 551 return; \ 552 } else { \ 553 if (RB_RED_LEFT(par, field)) { \ 554 red_gpr = RB_TRUE; \ 555 RB_ROTATE_RIGHT(head, par, gpr, field); \ 556 RB_FLIP_LEFT(par, field); \ 557 RB_FLIP_RIGHT(gpr, field); \ 558 } \ 559 sib = RB_LEFT(par, field); \ 560 if (RB_RED_LEFT(sib, field)) { \ 561 if (RB_RED_RIGHT(sib, field)) { \ 562 RB_FLIP_RIGHT(sib, field); \ 563 RB_FLIP_LEFT(par, field); \ 564 } \ 565 RB_FLIP_LEFT(sib, field); \ 566 } else if (RB_RED_RIGHT(sib, field)) { \ 567 RB_ROTATE_LEFT(head, sib, nec, field); \ 568 RB_FLIP_RIGHT(sib, field); \ 569 sib = nec; \ 570 } else { \ 571 RB_FLIP_LEFT(par, field); \ 572 par = gpr; \ 573 continue; \ 574 } \ 575 RB_ROTATE_RIGHT(head, par, sib, field); \ 576 return; \ 577 } \ 578 } while (!red_gpr); \ 579 if (gpr == NULL); \ 580 else if (left_par) \ 581 RB_FLIP_LEFT(gpr, field); \ 582 else \ 583 RB_FLIP_RIGHT(gpr, field); \ 584 } 585 586 #define RB_GENERATE_REMOVE(name, type, field, attr) \ 587 attr struct type * \ 588 name##_RB_REMOVE(struct name *head, struct type *elm) \ 589 { \ 590 struct type *child, *old, *parent, *right; \ 591 RB_BOOL red; \ 592 \ 593 old = elm; \ 594 parent = RB_PARENT(elm, field); \ 595 right = RB_RIGHT(elm, field); \ 596 if (RB_LEFT(elm, field) == NULL) \ 597 elm = child = right; \ 598 else if (right == NULL) \ 599 elm = child = RB_LEFT(elm, field); \ 600 else { \ 601 if ((child = RB_LEFT(right, field)) == NULL) { \ 602 child = RB_RIGHT(right, field); \ 603 red = RB_RED_RIGHT(old, field); \ 604 if (red) \ 605 RB_FLIP_RIGHT(old, field); \ 606 RB_RIGHT(old, field) = child; \ 607 parent = elm = right; \ 608 } else { \ 609 do \ 610 elm = child; \ 611 while ((child = RB_LEFT(elm, field)) != NULL); \ 612 child = RB_RIGHT(elm, field); \ 613 parent = RB_PARENT(elm, field); \ 614 red = RB_RED_LEFT(parent, field); \ 615 if (red) \ 616 RB_FLIP_LEFT(parent, field); \ 617 RB_LEFT(parent, field) = child; \ 618 RB_SET_PARENT(RB_RIGHT(old, field), elm, field); \ 619 } \ 620 RB_SET_PARENT(RB_LEFT(old, field), elm, field); \ 621 elm->field = old->field; \ 622 } \ 623 if (elm == child) { \ 624 red = RB_COLOR(old, field); \ 625 if (!red); \ 626 else if (RB_LEFT(parent, field) == old) \ 627 RB_FLIP_LEFT(parent, field); \ 628 else \ 629 RB_FLIP_RIGHT(parent, field); \ 630 } \ 631 RB_SWAP_CHILD(head, old, elm, field); \ 632 if (child != NULL) \ 633 RB_SET_PARENT(child, parent, field); \ 634 else if (!red && parent != NULL) \ 635 name##_RB_REMOVE_COLOR(head, parent); \ 636 while (parent != NULL) { \ 637 RB_AUGMENT(parent); \ 638 parent = RB_PARENT(parent, field); \ 639 } \ 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 RB_ROOT(head) = elm; \ 665 else if (comp < 0) \ 666 RB_LEFT(parent, field) = elm; \ 667 else \ 668 RB_RIGHT(parent, field) = elm; \ 669 name##_RB_INSERT_COLOR(head, elm); \ 670 while (elm != NULL) { \ 671 RB_AUGMENT(elm); \ 672 elm = RB_PARENT(elm, field); \ 673 } \ 674 return (NULL); \ 675 } 676 677 #define RB_GENERATE_FIND(name, type, field, cmp, attr) \ 678 /* Finds the node with the same key as elm */ \ 679 attr struct type * \ 680 name##_RB_FIND(struct name *head, struct type *elm) \ 681 { \ 682 struct type *tmp = RB_ROOT(head); \ 683 int comp; \ 684 while (tmp) { \ 685 comp = cmp(elm, tmp); \ 686 if (comp < 0) \ 687 tmp = RB_LEFT(tmp, field); \ 688 else if (comp > 0) \ 689 tmp = RB_RIGHT(tmp, field); \ 690 else \ 691 return (tmp); \ 692 } \ 693 return (NULL); \ 694 } 695 696 #define RB_GENERATE_NFIND(name, type, field, cmp, attr) \ 697 /* Finds the first node greater than or equal to the search key */ \ 698 attr struct type * \ 699 name##_RB_NFIND(struct name *head, struct type *elm) \ 700 { \ 701 struct type *tmp = RB_ROOT(head); \ 702 struct type *res = NULL; \ 703 int comp; \ 704 while (tmp) { \ 705 comp = cmp(elm, tmp); \ 706 if (comp < 0) { \ 707 res = tmp; \ 708 tmp = RB_LEFT(tmp, field); \ 709 } \ 710 else if (comp > 0) \ 711 tmp = RB_RIGHT(tmp, field); \ 712 else \ 713 return (tmp); \ 714 } \ 715 return (res); \ 716 } 717 718 #define RB_GENERATE_NEXT(name, type, field, attr) \ 719 /* ARGSUSED */ \ 720 attr struct type * \ 721 name##_RB_NEXT(struct type *elm) \ 722 { \ 723 if (RB_RIGHT(elm, field)) { \ 724 elm = RB_RIGHT(elm, field); \ 725 while (RB_LEFT(elm, field)) \ 726 elm = RB_LEFT(elm, field); \ 727 } else { \ 728 if (RB_PARENT(elm, field) && \ 729 (elm == RB_LEFT(RB_PARENT(elm, field), field))) \ 730 elm = RB_PARENT(elm, field); \ 731 else { \ 732 while (RB_PARENT(elm, field) && \ 733 (elm == RB_RIGHT(RB_PARENT(elm, field), field)))\ 734 elm = RB_PARENT(elm, field); \ 735 elm = RB_PARENT(elm, field); \ 736 } \ 737 } \ 738 return (elm); \ 739 } 740 741 #define RB_GENERATE_PREV(name, type, field, attr) \ 742 /* ARGSUSED */ \ 743 attr struct type * \ 744 name##_RB_PREV(struct type *elm) \ 745 { \ 746 if (RB_LEFT(elm, field)) { \ 747 elm = RB_LEFT(elm, field); \ 748 while (RB_RIGHT(elm, field)) \ 749 elm = RB_RIGHT(elm, field); \ 750 } else { \ 751 if (RB_PARENT(elm, field) && \ 752 (elm == RB_RIGHT(RB_PARENT(elm, field), field))) \ 753 elm = RB_PARENT(elm, field); \ 754 else { \ 755 while (RB_PARENT(elm, field) && \ 756 (elm == RB_LEFT(RB_PARENT(elm, field), field)))\ 757 elm = RB_PARENT(elm, field); \ 758 elm = RB_PARENT(elm, field); \ 759 } \ 760 } \ 761 return (elm); \ 762 } 763 764 #define RB_GENERATE_MINMAX(name, type, field, attr) \ 765 attr struct type * \ 766 name##_RB_MINMAX(struct name *head, int val) \ 767 { \ 768 struct type *tmp = RB_ROOT(head); \ 769 struct type *parent = NULL; \ 770 while (tmp) { \ 771 parent = tmp; \ 772 if (val < 0) \ 773 tmp = RB_LEFT(tmp, field); \ 774 else \ 775 tmp = RB_RIGHT(tmp, field); \ 776 } \ 777 return (parent); \ 778 } 779 780 #define RB_GENERATE_REINSERT(name, type, field, cmp, attr) \ 781 attr struct type * \ 782 name##_RB_REINSERT(struct name *head, struct type *elm) \ 783 { \ 784 struct type *cmpelm; \ 785 if (((cmpelm = RB_PREV(name, head, elm)) != NULL && \ 786 cmp(cmpelm, elm) >= 0) || \ 787 ((cmpelm = RB_NEXT(name, head, elm)) != NULL && \ 788 cmp(elm, cmpelm) >= 0)) { \ 789 /* XXXLAS: Remove/insert is heavy handed. */ \ 790 RB_REMOVE(name, head, elm); \ 791 return (RB_INSERT(name, head, elm)); \ 792 } \ 793 return (NULL); \ 794 } \ 795 796 #define RB_NEGINF -1 797 #define RB_INF 1 798 799 #define RB_INSERT(name, x, y) name##_RB_INSERT(x, y) 800 #define RB_REMOVE(name, x, y) name##_RB_REMOVE(x, y) 801 #define RB_FIND(name, x, y) name##_RB_FIND(x, y) 802 #define RB_NFIND(name, x, y) name##_RB_NFIND(x, y) 803 #define RB_NEXT(name, x, y) name##_RB_NEXT(y) 804 #define RB_PREV(name, x, y) name##_RB_PREV(y) 805 #define RB_MIN(name, x) name##_RB_MINMAX(x, RB_NEGINF) 806 #define RB_MAX(name, x) name##_RB_MINMAX(x, RB_INF) 807 #define RB_REINSERT(name, x, y) name##_RB_REINSERT(x, y) 808 809 #define RB_FOREACH(x, name, head) \ 810 for ((x) = RB_MIN(name, head); \ 811 (x) != NULL; \ 812 (x) = name##_RB_NEXT(x)) 813 814 #define RB_FOREACH_FROM(x, name, y) \ 815 for ((x) = (y); \ 816 ((x) != NULL) && ((y) = name##_RB_NEXT(x), (x) != NULL); \ 817 (x) = (y)) 818 819 #define RB_FOREACH_SAFE(x, name, head, y) \ 820 for ((x) = RB_MIN(name, head); \ 821 ((x) != NULL) && ((y) = name##_RB_NEXT(x), (x) != NULL); \ 822 (x) = (y)) 823 824 #define RB_FOREACH_REVERSE(x, name, head) \ 825 for ((x) = RB_MAX(name, head); \ 826 (x) != NULL; \ 827 (x) = name##_RB_PREV(x)) 828 829 #define RB_FOREACH_REVERSE_FROM(x, name, y) \ 830 for ((x) = (y); \ 831 ((x) != NULL) && ((y) = name##_RB_PREV(x), (x) != NULL); \ 832 (x) = (y)) 833 834 #define RB_FOREACH_REVERSE_SAFE(x, name, head, y) \ 835 for ((x) = RB_MAX(name, head); \ 836 ((x) != NULL) && ((y) = name##_RB_PREV(x), (x) != NULL); \ 837 (x) = (y)) 838 839 #endif /* _SYS_TREE_H_ */ 840