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 /* 37 * This file defines data structures for different types of trees: 38 * splay trees and rank-balanced trees. 39 * 40 * A splay tree is a self-organizing data structure. Every operation 41 * on the tree causes a splay to happen. The splay moves the requested 42 * node to the root of the tree and partly rebalances it. 43 * 44 * This has the benefit that request locality causes faster lookups as 45 * the requested nodes move to the top of the tree. On the other hand, 46 * every lookup causes memory writes. 47 * 48 * The Balance Theorem bounds the total access time for m operations 49 * and n inserts on an initially empty tree as O((m + n)lg n). The 50 * amortized cost for a sequence of m accesses to a splay tree is O(lg n); 51 * 52 * A rank-balanced tree is a binary search tree with an integer 53 * rank-difference as an attribute of each pointer from parent to child. 54 * The sum of the rank-differences on any path from a node down to null is 55 * the same, and defines the rank of that node. The rank of the null node 56 * is -1. 57 * 58 * Different additional conditions define different sorts of balanced trees, 59 * including "red-black" and "AVL" trees. The set of conditions applied here 60 * are the "weak-AVL" conditions of Haeupler, Sen and Tarjan presented in in 61 * "Rank Balanced Trees", ACM Transactions on Algorithms Volume 11 Issue 4 June 62 * 2015 Article No.: 30pp 1–26 https://doi.org/10.1145/2689412 (the HST paper): 63 * - every rank-difference is 1 or 2. 64 * - the rank of any leaf is 1. 65 * 66 * For historical reasons, rank differences that are even are associated 67 * with the color red (Rank-Even-Difference), and the child that a red edge 68 * points to is called a red child. 69 * 70 * Every operation on a rank-balanced tree is bounded as O(lg n). 71 * The maximum height of a rank-balanced tree is 2lg (n+1). 72 */ 73 74 #define SPLAY_HEAD(name, type) \ 75 struct name { \ 76 struct type *sph_root; /* root of the tree */ \ 77 } 78 79 #define SPLAY_INITIALIZER(root) \ 80 { NULL } 81 82 #define SPLAY_INIT(root) do { \ 83 (root)->sph_root = NULL; \ 84 } while (/*CONSTCOND*/ 0) 85 86 #define SPLAY_ENTRY(type) \ 87 struct { \ 88 struct type *spe_left; /* left element */ \ 89 struct type *spe_right; /* right element */ \ 90 } 91 92 #define SPLAY_LEFT(elm, field) (elm)->field.spe_left 93 #define SPLAY_RIGHT(elm, field) (elm)->field.spe_right 94 #define SPLAY_ROOT(head) (head)->sph_root 95 #define SPLAY_EMPTY(head) (SPLAY_ROOT(head) == NULL) 96 97 /* SPLAY_ROTATE_{LEFT,RIGHT} expect that tmp hold SPLAY_{RIGHT,LEFT} */ 98 #define SPLAY_ROTATE_RIGHT(head, tmp, field) do { \ 99 SPLAY_LEFT((head)->sph_root, field) = SPLAY_RIGHT(tmp, field); \ 100 SPLAY_RIGHT(tmp, field) = (head)->sph_root; \ 101 (head)->sph_root = tmp; \ 102 } while (/*CONSTCOND*/ 0) 103 104 #define SPLAY_ROTATE_LEFT(head, tmp, field) do { \ 105 SPLAY_RIGHT((head)->sph_root, field) = SPLAY_LEFT(tmp, field); \ 106 SPLAY_LEFT(tmp, field) = (head)->sph_root; \ 107 (head)->sph_root = tmp; \ 108 } while (/*CONSTCOND*/ 0) 109 110 #define SPLAY_LINKLEFT(head, tmp, field) do { \ 111 SPLAY_LEFT(tmp, field) = (head)->sph_root; \ 112 tmp = (head)->sph_root; \ 113 (head)->sph_root = SPLAY_LEFT((head)->sph_root, field); \ 114 } while (/*CONSTCOND*/ 0) 115 116 #define SPLAY_LINKRIGHT(head, tmp, field) do { \ 117 SPLAY_RIGHT(tmp, field) = (head)->sph_root; \ 118 tmp = (head)->sph_root; \ 119 (head)->sph_root = SPLAY_RIGHT((head)->sph_root, field); \ 120 } while (/*CONSTCOND*/ 0) 121 122 #define SPLAY_ASSEMBLE(head, node, left, right, field) do { \ 123 SPLAY_RIGHT(left, field) = SPLAY_LEFT((head)->sph_root, field); \ 124 SPLAY_LEFT(right, field) = SPLAY_RIGHT((head)->sph_root, field);\ 125 SPLAY_LEFT((head)->sph_root, field) = SPLAY_RIGHT(node, field); \ 126 SPLAY_RIGHT((head)->sph_root, field) = SPLAY_LEFT(node, field); \ 127 } while (/*CONSTCOND*/ 0) 128 129 /* Generates prototypes and inline functions */ 130 131 #define SPLAY_PROTOTYPE(name, type, field, cmp) \ 132 void name##_SPLAY(struct name *, struct type *); \ 133 void name##_SPLAY_MINMAX(struct name *, int); \ 134 struct type *name##_SPLAY_INSERT(struct name *, struct type *); \ 135 struct type *name##_SPLAY_REMOVE(struct name *, struct type *); \ 136 \ 137 /* Finds the node with the same key as elm */ \ 138 static __unused __inline struct type * \ 139 name##_SPLAY_FIND(struct name *head, struct type *elm) \ 140 { \ 141 if (SPLAY_EMPTY(head)) \ 142 return(NULL); \ 143 name##_SPLAY(head, elm); \ 144 if ((cmp)(elm, (head)->sph_root) == 0) \ 145 return (head->sph_root); \ 146 return (NULL); \ 147 } \ 148 \ 149 static __unused __inline struct type * \ 150 name##_SPLAY_NEXT(struct name *head, struct type *elm) \ 151 { \ 152 name##_SPLAY(head, elm); \ 153 if (SPLAY_RIGHT(elm, field) != NULL) { \ 154 elm = SPLAY_RIGHT(elm, field); \ 155 while (SPLAY_LEFT(elm, field) != NULL) { \ 156 elm = SPLAY_LEFT(elm, field); \ 157 } \ 158 } else \ 159 elm = NULL; \ 160 return (elm); \ 161 } \ 162 \ 163 static __unused __inline struct type * \ 164 name##_SPLAY_MIN_MAX(struct name *head, int val) \ 165 { \ 166 name##_SPLAY_MINMAX(head, val); \ 167 return (SPLAY_ROOT(head)); \ 168 } 169 170 /* Main splay operation. 171 * Moves node close to the key of elm to top 172 */ 173 #define SPLAY_GENERATE(name, type, field, cmp) \ 174 struct type * \ 175 name##_SPLAY_INSERT(struct name *head, struct type *elm) \ 176 { \ 177 if (SPLAY_EMPTY(head)) { \ 178 SPLAY_LEFT(elm, field) = SPLAY_RIGHT(elm, field) = NULL; \ 179 } else { \ 180 __typeof(cmp(NULL, NULL)) __comp; \ 181 name##_SPLAY(head, elm); \ 182 __comp = (cmp)(elm, (head)->sph_root); \ 183 if(__comp < 0) { \ 184 SPLAY_LEFT(elm, field) = SPLAY_LEFT((head)->sph_root, field);\ 185 SPLAY_RIGHT(elm, field) = (head)->sph_root; \ 186 SPLAY_LEFT((head)->sph_root, field) = NULL; \ 187 } else if (__comp > 0) { \ 188 SPLAY_RIGHT(elm, field) = SPLAY_RIGHT((head)->sph_root, field);\ 189 SPLAY_LEFT(elm, field) = (head)->sph_root; \ 190 SPLAY_RIGHT((head)->sph_root, field) = NULL; \ 191 } else \ 192 return ((head)->sph_root); \ 193 } \ 194 (head)->sph_root = (elm); \ 195 return (NULL); \ 196 } \ 197 \ 198 struct type * \ 199 name##_SPLAY_REMOVE(struct name *head, struct type *elm) \ 200 { \ 201 struct type *__tmp; \ 202 if (SPLAY_EMPTY(head)) \ 203 return (NULL); \ 204 name##_SPLAY(head, elm); \ 205 if ((cmp)(elm, (head)->sph_root) == 0) { \ 206 if (SPLAY_LEFT((head)->sph_root, field) == NULL) { \ 207 (head)->sph_root = SPLAY_RIGHT((head)->sph_root, field);\ 208 } else { \ 209 __tmp = SPLAY_RIGHT((head)->sph_root, field); \ 210 (head)->sph_root = SPLAY_LEFT((head)->sph_root, field);\ 211 name##_SPLAY(head, elm); \ 212 SPLAY_RIGHT((head)->sph_root, field) = __tmp; \ 213 } \ 214 return (elm); \ 215 } \ 216 return (NULL); \ 217 } \ 218 \ 219 void \ 220 name##_SPLAY(struct name *head, struct type *elm) \ 221 { \ 222 struct type __node, *__left, *__right, *__tmp; \ 223 __typeof(cmp(NULL, NULL)) __comp; \ 224 \ 225 SPLAY_LEFT(&__node, field) = SPLAY_RIGHT(&__node, field) = NULL;\ 226 __left = __right = &__node; \ 227 \ 228 while ((__comp = (cmp)(elm, (head)->sph_root)) != 0) { \ 229 if (__comp < 0) { \ 230 __tmp = SPLAY_LEFT((head)->sph_root, field); \ 231 if (__tmp == NULL) \ 232 break; \ 233 if ((cmp)(elm, __tmp) < 0){ \ 234 SPLAY_ROTATE_RIGHT(head, __tmp, field); \ 235 if (SPLAY_LEFT((head)->sph_root, field) == NULL)\ 236 break; \ 237 } \ 238 SPLAY_LINKLEFT(head, __right, field); \ 239 } else if (__comp > 0) { \ 240 __tmp = SPLAY_RIGHT((head)->sph_root, field); \ 241 if (__tmp == NULL) \ 242 break; \ 243 if ((cmp)(elm, __tmp) > 0){ \ 244 SPLAY_ROTATE_LEFT(head, __tmp, field); \ 245 if (SPLAY_RIGHT((head)->sph_root, field) == NULL)\ 246 break; \ 247 } \ 248 SPLAY_LINKRIGHT(head, __left, field); \ 249 } \ 250 } \ 251 SPLAY_ASSEMBLE(head, &__node, __left, __right, field); \ 252 } \ 253 \ 254 /* Splay with either the minimum or the maximum element \ 255 * Used to find minimum or maximum element in tree. \ 256 */ \ 257 void name##_SPLAY_MINMAX(struct name *head, int __comp) \ 258 { \ 259 struct type __node, *__left, *__right, *__tmp; \ 260 \ 261 SPLAY_LEFT(&__node, field) = SPLAY_RIGHT(&__node, field) = NULL;\ 262 __left = __right = &__node; \ 263 \ 264 while (1) { \ 265 if (__comp < 0) { \ 266 __tmp = SPLAY_LEFT((head)->sph_root, field); \ 267 if (__tmp == NULL) \ 268 break; \ 269 if (__comp < 0){ \ 270 SPLAY_ROTATE_RIGHT(head, __tmp, field); \ 271 if (SPLAY_LEFT((head)->sph_root, field) == NULL)\ 272 break; \ 273 } \ 274 SPLAY_LINKLEFT(head, __right, field); \ 275 } else if (__comp > 0) { \ 276 __tmp = SPLAY_RIGHT((head)->sph_root, field); \ 277 if (__tmp == NULL) \ 278 break; \ 279 if (__comp > 0) { \ 280 SPLAY_ROTATE_LEFT(head, __tmp, field); \ 281 if (SPLAY_RIGHT((head)->sph_root, field) == NULL)\ 282 break; \ 283 } \ 284 SPLAY_LINKRIGHT(head, __left, field); \ 285 } \ 286 } \ 287 SPLAY_ASSEMBLE(head, &__node, __left, __right, field); \ 288 } 289 290 #define SPLAY_NEGINF -1 291 #define SPLAY_INF 1 292 293 #define SPLAY_INSERT(name, x, y) name##_SPLAY_INSERT(x, y) 294 #define SPLAY_REMOVE(name, x, y) name##_SPLAY_REMOVE(x, y) 295 #define SPLAY_FIND(name, x, y) name##_SPLAY_FIND(x, y) 296 #define SPLAY_NEXT(name, x, y) name##_SPLAY_NEXT(x, y) 297 #define SPLAY_MIN(name, x) (SPLAY_EMPTY(x) ? NULL \ 298 : name##_SPLAY_MIN_MAX(x, SPLAY_NEGINF)) 299 #define SPLAY_MAX(name, x) (SPLAY_EMPTY(x) ? NULL \ 300 : name##_SPLAY_MIN_MAX(x, SPLAY_INF)) 301 302 #define SPLAY_FOREACH(x, name, head) \ 303 for ((x) = SPLAY_MIN(name, head); \ 304 (x) != NULL; \ 305 (x) = SPLAY_NEXT(name, head, x)) 306 307 /* Macros that define a rank-balanced tree */ 308 #define RB_HEAD(name, type) \ 309 struct name { \ 310 struct type *rbh_root; /* root of the tree */ \ 311 } 312 313 #define RB_INITIALIZER(root) \ 314 { NULL } 315 316 #define RB_INIT(root) do { \ 317 (root)->rbh_root = NULL; \ 318 } while (/*CONSTCOND*/ 0) 319 320 #define RB_ENTRY(type) \ 321 struct { \ 322 struct type *rbe_link[3]; \ 323 } 324 325 /* 326 * With the expectation that any object of struct type has an 327 * address that is a multiple of 4, and that therefore the 328 * 2 least significant bits of a pointer to struct type are 329 * always zero, this implementation sets those bits to indicate 330 * that the left or right child of the tree node is "red". 331 */ 332 #define _RB_LINK(elm, dir, field) (elm)->field.rbe_link[dir] 333 #define _RB_UP(elm, field) _RB_LINK(elm, 2, field) 334 #define _RB_L ((__uintptr_t)1) 335 #define _RB_R ((__uintptr_t)2) 336 #define _RB_LR ((__uintptr_t)3) 337 #define _RB_BITS(elm) (*(__uintptr_t *)&elm) 338 #define _RB_BITSUP(elm, field) _RB_BITS(_RB_UP(elm, field)) 339 #define _RB_PTR(elm) (__typeof(elm)) \ 340 ((__uintptr_t)elm & ~_RB_LR) 341 342 #define RB_PARENT(elm, field) _RB_PTR(_RB_UP(elm, field)) 343 #define RB_LEFT(elm, field) _RB_LINK(elm, _RB_L-1, field) 344 #define RB_RIGHT(elm, field) _RB_LINK(elm, _RB_R-1, field) 345 #define RB_ROOT(head) (head)->rbh_root 346 #define RB_EMPTY(head) (RB_ROOT(head) == NULL) 347 348 #define RB_SET_PARENT(dst, src, field) do { \ 349 _RB_BITSUP(dst, field) = (__uintptr_t)src | \ 350 (_RB_BITSUP(dst, field) & _RB_LR); \ 351 } while (/*CONSTCOND*/ 0) 352 353 #define RB_SET(elm, parent, field) do { \ 354 _RB_UP(elm, field) = parent; \ 355 RB_LEFT(elm, field) = RB_RIGHT(elm, field) = NULL; \ 356 } while (/*CONSTCOND*/ 0) 357 358 /* 359 * Either RB_AUGMENT or RB_AUGMENT_CHECK is invoked in a loop at the root of 360 * every modified subtree, from the bottom up to the root, to update augmented 361 * node data. RB_AUGMENT_CHECK returns true only when the update changes the 362 * node data, so that updating can be stopped short of the root when it returns 363 * false. 364 */ 365 #ifndef RB_AUGMENT_CHECK 366 #ifndef RB_AUGMENT 367 #define RB_AUGMENT_CHECK(x) 0 368 #else 369 #define RB_AUGMENT_CHECK(x) (RB_AUGMENT(x), 1) 370 #endif 371 #endif 372 373 #define RB_UPDATE_AUGMENT(elm, field) do { \ 374 __typeof(elm) rb_update_tmp = (elm); \ 375 while (RB_AUGMENT_CHECK(rb_update_tmp) && \ 376 (rb_update_tmp = RB_PARENT(rb_update_tmp, field)) != NULL) \ 377 ; \ 378 } while (0) 379 380 #define RB_SWAP_CHILD(head, par, out, in, field) do { \ 381 if (par == NULL) \ 382 RB_ROOT(head) = (in); \ 383 else if ((out) == RB_LEFT(par, field)) \ 384 RB_LEFT(par, field) = (in); \ 385 else \ 386 RB_RIGHT(par, field) = (in); \ 387 } while (/*CONSTCOND*/ 0) 388 389 /* 390 * RB_ROTATE macro partially restructures the tree to improve balance. In the 391 * case when dir is _RB_L, tmp is a right child of elm. After rotation, elm 392 * is a left child of tmp, and the subtree that represented the items between 393 * them, which formerly hung to the left of tmp now hangs to the right of elm. 394 * The parent-child relationship between elm and its former parent is not 395 * changed; where this macro once updated those fields, that is now left to the 396 * caller of RB_ROTATE to clean up, so that a pair of rotations does not twice 397 * update the same pair of pointer fields with distinct values. 398 */ 399 #define RB_ROTATE(elm, tmp, dir, field) do { \ 400 if ((_RB_LINK(elm, (dir ^ _RB_LR)-1, field) = \ 401 _RB_LINK(tmp, dir-1, field)) != NULL) \ 402 RB_SET_PARENT(_RB_LINK(tmp, dir-1, field), elm, field); \ 403 _RB_LINK(tmp, dir-1, field) = (elm); \ 404 RB_SET_PARENT(elm, tmp, field); \ 405 } while (/*CONSTCOND*/ 0) 406 407 /* Generates prototypes and inline functions */ 408 #define RB_PROTOTYPE(name, type, field, cmp) \ 409 RB_PROTOTYPE_INTERNAL(name, type, field, cmp,) 410 #define RB_PROTOTYPE_STATIC(name, type, field, cmp) \ 411 RB_PROTOTYPE_INTERNAL(name, type, field, cmp, __unused static) 412 #define RB_PROTOTYPE_INTERNAL(name, type, field, cmp, attr) \ 413 RB_PROTOTYPE_RANK(name, type, attr) \ 414 RB_PROTOTYPE_DO_INSERT_COLOR(name, type, attr); \ 415 RB_PROTOTYPE_INSERT_COLOR(name, type, attr); \ 416 RB_PROTOTYPE_REMOVE_COLOR(name, type, attr); \ 417 RB_PROTOTYPE_INSERT_FINISH(name, type, attr); \ 418 RB_PROTOTYPE_INSERT(name, type, attr); \ 419 RB_PROTOTYPE_REMOVE(name, type, attr); \ 420 RB_PROTOTYPE_FIND(name, type, attr); \ 421 RB_PROTOTYPE_NFIND(name, type, attr); \ 422 RB_PROTOTYPE_NEXT(name, type, attr); \ 423 RB_PROTOTYPE_INSERT_NEXT(name, type, attr); \ 424 RB_PROTOTYPE_PREV(name, type, attr); \ 425 RB_PROTOTYPE_INSERT_PREV(name, type, attr); \ 426 RB_PROTOTYPE_MINMAX(name, type, attr); \ 427 RB_PROTOTYPE_REINSERT(name, type, attr); 428 #ifdef _RB_DIAGNOSTIC 429 #define RB_PROTOTYPE_RANK(name, type, attr) \ 430 attr int name##_RB_RANK(struct type *); 431 #else 432 #define RB_PROTOTYPE_RANK(name, type, attr) 433 #endif 434 #define RB_PROTOTYPE_DO_INSERT_COLOR(name, type, attr) \ 435 attr struct type *name##_RB_DO_INSERT_COLOR(struct name *, \ 436 struct type *, struct type *) 437 #define RB_PROTOTYPE_INSERT_COLOR(name, type, attr) \ 438 attr struct type *name##_RB_INSERT_COLOR(struct name *, struct type *) 439 #define RB_PROTOTYPE_REMOVE_COLOR(name, type, attr) \ 440 attr struct type *name##_RB_REMOVE_COLOR(struct name *, \ 441 struct type *, struct type *) 442 #define RB_PROTOTYPE_REMOVE(name, type, attr) \ 443 attr struct type *name##_RB_REMOVE(struct name *, struct type *) 444 #define RB_PROTOTYPE_INSERT_FINISH(name, type, attr) \ 445 attr struct type *name##_RB_INSERT_FINISH(struct name *, \ 446 struct type *, struct type **, struct type *) 447 #define RB_PROTOTYPE_INSERT(name, type, attr) \ 448 attr struct type *name##_RB_INSERT(struct name *, struct type *) 449 #define RB_PROTOTYPE_FIND(name, type, attr) \ 450 attr struct type *name##_RB_FIND(struct name *, struct type *) 451 #define RB_PROTOTYPE_NFIND(name, type, attr) \ 452 attr struct type *name##_RB_NFIND(struct name *, struct type *) 453 #define RB_PROTOTYPE_NEXT(name, type, attr) \ 454 attr struct type *name##_RB_NEXT(struct type *) 455 #define RB_PROTOTYPE_INSERT_NEXT(name, type, attr) \ 456 attr struct type *name##_RB_INSERT_NEXT(struct name *, \ 457 struct type *, struct type *) 458 #define RB_PROTOTYPE_PREV(name, type, attr) \ 459 attr struct type *name##_RB_PREV(struct type *) 460 #define RB_PROTOTYPE_INSERT_PREV(name, type, attr) \ 461 attr struct type *name##_RB_INSERT_PREV(struct name *, \ 462 struct type *, struct type *) 463 #define RB_PROTOTYPE_MINMAX(name, type, attr) \ 464 attr struct type *name##_RB_MINMAX(struct name *, int) 465 #define RB_PROTOTYPE_REINSERT(name, type, attr) \ 466 attr struct type *name##_RB_REINSERT(struct name *, struct type *) 467 468 /* Main rb operation. 469 * Moves node close to the key of elm to top 470 */ 471 #define RB_GENERATE(name, type, field, cmp) \ 472 RB_GENERATE_INTERNAL(name, type, field, cmp,) 473 #define RB_GENERATE_STATIC(name, type, field, cmp) \ 474 RB_GENERATE_INTERNAL(name, type, field, cmp, __unused static) 475 #define RB_GENERATE_INTERNAL(name, type, field, cmp, attr) \ 476 RB_GENERATE_RANK(name, type, field, attr) \ 477 RB_GENERATE_DO_INSERT_COLOR(name, type, field, attr) \ 478 RB_GENERATE_INSERT_COLOR(name, type, field, attr) \ 479 RB_GENERATE_REMOVE_COLOR(name, type, field, attr) \ 480 RB_GENERATE_INSERT_FINISH(name, type, field, attr) \ 481 RB_GENERATE_INSERT(name, type, field, cmp, attr) \ 482 RB_GENERATE_REMOVE(name, type, field, attr) \ 483 RB_GENERATE_FIND(name, type, field, cmp, attr) \ 484 RB_GENERATE_NFIND(name, type, field, cmp, attr) \ 485 RB_GENERATE_NEXT(name, type, field, attr) \ 486 RB_GENERATE_INSERT_NEXT(name, type, field, cmp, attr) \ 487 RB_GENERATE_PREV(name, type, field, attr) \ 488 RB_GENERATE_INSERT_PREV(name, type, field, cmp, attr) \ 489 RB_GENERATE_MINMAX(name, type, field, attr) \ 490 RB_GENERATE_REINSERT(name, type, field, cmp, attr) 491 492 #ifdef _RB_DIAGNOSTIC 493 #ifndef RB_AUGMENT 494 #define _RB_AUGMENT_VERIFY(x) RB_AUGMENT_CHECK(x) 495 #else 496 #define _RB_AUGMENT_VERIFY(x) 0 497 #endif 498 #define RB_GENERATE_RANK(name, type, field, attr) \ 499 /* \ 500 * Return the rank of the subtree rooted at elm, or -1 if the subtree \ 501 * is not rank-balanced, or has inconsistent augmentation data. 502 */ \ 503 attr int \ 504 name##_RB_RANK(struct type *elm) \ 505 { \ 506 struct type *left, *right, *up; \ 507 int left_rank, right_rank; \ 508 \ 509 if (elm == NULL) \ 510 return (0); \ 511 up = _RB_UP(elm, field); \ 512 left = RB_LEFT(elm, field); \ 513 left_rank = ((_RB_BITS(up) & _RB_L) ? 2 : 1) + \ 514 name##_RB_RANK(left); \ 515 right = RB_RIGHT(elm, field); \ 516 right_rank = ((_RB_BITS(up) & _RB_R) ? 2 : 1) + \ 517 name##_RB_RANK(right); \ 518 if (left_rank != right_rank || \ 519 (left_rank == 2 && left == NULL && right == NULL) || \ 520 _RB_AUGMENT_VERIFY(elm)) \ 521 return (-1); \ 522 return (left_rank); \ 523 } 524 #else 525 #define RB_GENERATE_RANK(name, type, field, attr) 526 #endif 527 528 #define RB_GENERATE_DO_INSERT_COLOR(name, type, field, attr) \ 529 attr struct type * \ 530 name##_RB_DO_INSERT_COLOR(struct name *head, \ 531 struct type *parent, struct type *elm) \ 532 { \ 533 /* \ 534 * Initially, elm is a leaf. Either its parent was previously \ 535 * a leaf, with two black null children, or an interior node \ 536 * with a black non-null child and a red null child. The \ 537 * balance criterion "the rank of any leaf is 1" precludes the \ 538 * possibility of two red null children for the initial parent. \ 539 * So the first loop iteration cannot lead to accessing an \ 540 * uninitialized 'child', and a later iteration can only happen \ 541 * when a value has been assigned to 'child' in the previous \ 542 * one. \ 543 */ \ 544 struct type *child, *child_up, *gpar; \ 545 __uintptr_t elmdir, sibdir; \ 546 \ 547 do { \ 548 /* the rank of the tree rooted at elm grew */ \ 549 gpar = _RB_UP(parent, field); \ 550 elmdir = RB_RIGHT(parent, field) == elm ? _RB_R : _RB_L; \ 551 if (_RB_BITS(gpar) & elmdir) { \ 552 /* shorten the parent-elm edge to rebalance */ \ 553 _RB_BITSUP(parent, field) ^= elmdir; \ 554 return (NULL); \ 555 } \ 556 sibdir = elmdir ^ _RB_LR; \ 557 /* the other edge must change length */ \ 558 _RB_BITSUP(parent, field) ^= sibdir; \ 559 if ((_RB_BITS(gpar) & _RB_LR) == 0) { \ 560 /* both edges now short, retry from parent */ \ 561 child = elm; \ 562 elm = parent; \ 563 continue; \ 564 } \ 565 _RB_UP(parent, field) = gpar = _RB_PTR(gpar); \ 566 if (_RB_BITSUP(elm, field) & elmdir) { \ 567 /* \ 568 * Exactly one of the edges descending from elm \ 569 * is long. The long one is in the same \ 570 * direction as the edge from parent to elm, \ 571 * so change that by rotation. The edge from \ 572 * parent to z was shortened above. Shorten \ 573 * the long edge down from elm, and adjust \ 574 * other edge lengths based on the downward \ 575 * edges from 'child'. \ 576 * \ 577 * par par \ 578 * / \ / \ \ 579 * elm z / z \ 580 * / \ child \ 581 * / child / \ \ 582 * / / \ elm \ \ 583 * w / \ / \ y \ 584 * x y w \ \ 585 * x \ 586 */ \ 587 RB_ROTATE(elm, child, elmdir, field); \ 588 child_up = _RB_UP(child, field); \ 589 if (_RB_BITS(child_up) & sibdir) \ 590 _RB_BITSUP(parent, field) ^= elmdir; \ 591 if (_RB_BITS(child_up) & elmdir) \ 592 _RB_BITSUP(elm, field) ^= _RB_LR; \ 593 else \ 594 _RB_BITSUP(elm, field) ^= elmdir; \ 595 /* if child is a leaf, don't augment elm, \ 596 * since it is restored to be a leaf again. */ \ 597 if ((_RB_BITS(child_up) & _RB_LR) == 0) \ 598 elm = child; \ 599 } else \ 600 child = elm; \ 601 \ 602 /* \ 603 * The long edge descending from 'child' points back \ 604 * in the direction of 'parent'. Rotate to make \ 605 * 'parent' a child of 'child', then make both edges \ 606 * of 'child' short to rebalance. \ 607 * \ 608 * par child \ 609 * / \ / \ \ 610 * / z x par \ 611 * child / \ \ 612 * / \ / z \ 613 * x \ y \ 614 * y \ 615 */ \ 616 RB_ROTATE(parent, child, sibdir, field); \ 617 _RB_UP(child, field) = gpar; \ 618 RB_SWAP_CHILD(head, gpar, parent, child, field); \ 619 /* \ 620 * Elements rotated down have new, smaller subtrees, \ 621 * so update augmentation for them. \ 622 */ \ 623 if (elm != child) \ 624 (void)RB_AUGMENT_CHECK(elm); \ 625 (void)RB_AUGMENT_CHECK(parent); \ 626 return (child); \ 627 } while ((parent = gpar) != NULL); \ 628 return (NULL); \ 629 } 630 631 #define RB_GENERATE_INSERT_COLOR(name, type, field, attr) \ 632 attr struct type * \ 633 name##_RB_INSERT_COLOR(struct name *head, struct type *elm) \ 634 { \ 635 struct type *parent, *tmp; \ 636 \ 637 parent = RB_PARENT(elm, field); \ 638 if (parent != NULL) \ 639 tmp = name##_RB_DO_INSERT_COLOR(head, parent, elm); \ 640 else \ 641 tmp = NULL; \ 642 return (tmp); \ 643 } 644 645 #ifndef RB_STRICT_HST 646 /* 647 * In REMOVE_COLOR, the HST paper, in figure 3, in the single-rotate case, has 648 * 'parent' with one higher rank, and then reduces its rank if 'parent' has 649 * become a leaf. This implementation always has the parent in its new position 650 * with lower rank, to avoid the leaf check. Define RB_STRICT_HST to 1 to get 651 * the behavior that HST describes. 652 */ 653 #define RB_STRICT_HST 0 654 #endif 655 656 #define RB_GENERATE_REMOVE_COLOR(name, type, field, attr) \ 657 attr struct type * \ 658 name##_RB_REMOVE_COLOR(struct name *head, \ 659 struct type *parent, struct type *elm) \ 660 { \ 661 struct type *gpar, *sib, *up; \ 662 __uintptr_t elmdir, sibdir; \ 663 \ 664 if (RB_RIGHT(parent, field) == elm && \ 665 RB_LEFT(parent, field) == elm) { \ 666 /* Deleting a leaf that is an only-child creates a \ 667 * rank-2 leaf. Demote that leaf. */ \ 668 _RB_UP(parent, field) = _RB_PTR(_RB_UP(parent, field)); \ 669 elm = parent; \ 670 if ((parent = _RB_UP(elm, field)) == NULL) \ 671 return (NULL); \ 672 } \ 673 do { \ 674 /* the rank of the tree rooted at elm shrank */ \ 675 gpar = _RB_UP(parent, field); \ 676 elmdir = RB_RIGHT(parent, field) == elm ? _RB_R : _RB_L; \ 677 _RB_BITS(gpar) ^= elmdir; \ 678 if (_RB_BITS(gpar) & elmdir) { \ 679 /* lengthen the parent-elm edge to rebalance */ \ 680 _RB_UP(parent, field) = gpar; \ 681 return (NULL); \ 682 } \ 683 if (_RB_BITS(gpar) & _RB_LR) { \ 684 /* shorten other edge, retry from parent */ \ 685 _RB_BITS(gpar) ^= _RB_LR; \ 686 _RB_UP(parent, field) = gpar; \ 687 gpar = _RB_PTR(gpar); \ 688 continue; \ 689 } \ 690 sibdir = elmdir ^ _RB_LR; \ 691 sib = _RB_LINK(parent, sibdir-1, field); \ 692 up = _RB_UP(sib, field); \ 693 _RB_BITS(up) ^= _RB_LR; \ 694 if ((_RB_BITS(up) & _RB_LR) == 0) { \ 695 /* shorten edges descending from sib, retry */ \ 696 _RB_UP(sib, field) = up; \ 697 continue; \ 698 } \ 699 if ((_RB_BITS(up) & sibdir) == 0) { \ 700 /* \ 701 * The edge descending from 'sib' away from \ 702 * 'parent' is long. The short edge descending \ 703 * from 'sib' toward 'parent' points to 'elm*' \ 704 * Rotate to make 'sib' a child of 'elm*' \ 705 * then adjust the lengths of the edges \ 706 * descending from 'sib' and 'elm*'. \ 707 * \ 708 * par par \ 709 * / \ / \ \ 710 * / sib elm \ \ 711 * / / \ elm* \ 712 * elm elm* \ / \ \ 713 * / \ \ / \ \ 714 * / \ z / \ \ 715 * x y x sib \ 716 * / \ \ 717 * / z \ 718 * y \ 719 */ \ 720 elm = _RB_LINK(sib, elmdir-1, field); \ 721 /* elm is a 1-child. First rotate at elm. */ \ 722 RB_ROTATE(sib, elm, sibdir, field); \ 723 up = _RB_UP(elm, field); \ 724 _RB_BITSUP(parent, field) ^= \ 725 (_RB_BITS(up) & elmdir) ? _RB_LR : elmdir; \ 726 _RB_BITSUP(sib, field) ^= \ 727 (_RB_BITS(up) & sibdir) ? _RB_LR : sibdir; \ 728 _RB_BITSUP(elm, field) |= _RB_LR; \ 729 } else { \ 730 if ((_RB_BITS(up) & elmdir) == 0 && \ 731 RB_STRICT_HST && elm != NULL) { \ 732 /* if parent does not become a leaf, \ 733 do not demote parent yet. */ \ 734 _RB_BITSUP(parent, field) ^= sibdir; \ 735 _RB_BITSUP(sib, field) ^= _RB_LR; \ 736 } else if ((_RB_BITS(up) & elmdir) == 0) { \ 737 /* demote parent. */ \ 738 _RB_BITSUP(parent, field) ^= elmdir; \ 739 _RB_BITSUP(sib, field) ^= sibdir; \ 740 } else \ 741 _RB_BITSUP(sib, field) ^= sibdir; \ 742 elm = sib; \ 743 } \ 744 \ 745 /* \ 746 * The edge descending from 'elm' away from 'parent' \ 747 * is short. Rotate to make 'parent' a child of 'elm', \ 748 * then lengthen the short edges descending from \ 749 * 'parent' and 'elm' to rebalance. \ 750 * \ 751 * par elm \ 752 * / \ / \ \ 753 * e \ / \ \ 754 * elm / \ \ 755 * / \ par s \ 756 * / \ / \ \ 757 * / \ e \ \ 758 * x s x \ 759 */ \ 760 RB_ROTATE(parent, elm, elmdir, field); \ 761 RB_SET_PARENT(elm, gpar, field); \ 762 RB_SWAP_CHILD(head, gpar, parent, elm, field); \ 763 /* \ 764 * An element rotated down, but not into the search \ 765 * path has a new, smaller subtree, so update \ 766 * augmentation for it. \ 767 */ \ 768 if (sib != elm) \ 769 (void)RB_AUGMENT_CHECK(sib); \ 770 return (parent); \ 771 } while (elm = parent, (parent = gpar) != NULL); \ 772 return (NULL); \ 773 } 774 775 #define _RB_AUGMENT_WALK(elm, match, field) \ 776 do { \ 777 if (match == elm) \ 778 match = NULL; \ 779 } while (RB_AUGMENT_CHECK(elm) && \ 780 (elm = RB_PARENT(elm, field)) != NULL) 781 782 #define RB_GENERATE_REMOVE(name, type, field, attr) \ 783 attr struct type * \ 784 name##_RB_REMOVE(struct name *head, struct type *out) \ 785 { \ 786 struct type *child, *in, *opar, *parent; \ 787 \ 788 child = RB_LEFT(out, field); \ 789 in = RB_RIGHT(out, field); \ 790 opar = _RB_UP(out, field); \ 791 if (in == NULL || child == NULL) { \ 792 in = child = in == NULL ? child : in; \ 793 parent = opar = _RB_PTR(opar); \ 794 } else { \ 795 parent = in; \ 796 while (RB_LEFT(in, field)) \ 797 in = RB_LEFT(in, field); \ 798 RB_SET_PARENT(child, in, field); \ 799 RB_LEFT(in, field) = child; \ 800 child = RB_RIGHT(in, field); \ 801 if (parent != in) { \ 802 RB_SET_PARENT(parent, in, field); \ 803 RB_RIGHT(in, field) = parent; \ 804 parent = RB_PARENT(in, field); \ 805 RB_LEFT(parent, field) = child; \ 806 } \ 807 _RB_UP(in, field) = opar; \ 808 opar = _RB_PTR(opar); \ 809 } \ 810 RB_SWAP_CHILD(head, opar, out, in, field); \ 811 if (child != NULL) \ 812 _RB_UP(child, field) = parent; \ 813 if (parent != NULL) { \ 814 opar = name##_RB_REMOVE_COLOR(head, parent, child); \ 815 /* if rotation has made 'parent' the root of the same \ 816 * subtree as before, don't re-augment it. */ \ 817 if (parent == in && RB_LEFT(parent, field) == NULL) { \ 818 opar = NULL; \ 819 parent = RB_PARENT(parent, field); \ 820 } \ 821 _RB_AUGMENT_WALK(parent, opar, field); \ 822 if (opar != NULL) { \ 823 /* \ 824 * Elements rotated into the search path have \ 825 * changed subtrees, so update augmentation for \ 826 * them if AUGMENT_WALK didn't. \ 827 */ \ 828 (void)RB_AUGMENT_CHECK(opar); \ 829 (void)RB_AUGMENT_CHECK(RB_PARENT(opar, field)); \ 830 } \ 831 } \ 832 return (out); \ 833 } 834 835 #define RB_GENERATE_INSERT_FINISH(name, type, field, attr) \ 836 /* Inserts a node into the RB tree */ \ 837 attr struct type * \ 838 name##_RB_INSERT_FINISH(struct name *head, struct type *parent, \ 839 struct type **pptr, struct type *elm) \ 840 { \ 841 struct type *tmp = NULL; \ 842 \ 843 RB_SET(elm, parent, field); \ 844 *pptr = elm; \ 845 if (parent != NULL) \ 846 tmp = name##_RB_DO_INSERT_COLOR(head, parent, elm); \ 847 _RB_AUGMENT_WALK(elm, tmp, field); \ 848 if (tmp != NULL) \ 849 /* \ 850 * An element rotated into the search path has a \ 851 * changed subtree, so update augmentation for it if \ 852 * AUGMENT_WALK didn't. \ 853 */ \ 854 (void)RB_AUGMENT_CHECK(tmp); \ 855 return (NULL); \ 856 } 857 858 #define RB_GENERATE_INSERT(name, type, field, cmp, attr) \ 859 /* Inserts a node into the RB tree */ \ 860 attr struct type * \ 861 name##_RB_INSERT(struct name *head, struct type *elm) \ 862 { \ 863 struct type *tmp; \ 864 struct type **tmpp = &RB_ROOT(head); \ 865 struct type *parent = NULL; \ 866 \ 867 while ((tmp = *tmpp) != NULL) { \ 868 parent = tmp; \ 869 __typeof(cmp(NULL, NULL)) comp = (cmp)(elm, parent); \ 870 if (comp < 0) \ 871 tmpp = &RB_LEFT(parent, field); \ 872 else if (comp > 0) \ 873 tmpp = &RB_RIGHT(parent, field); \ 874 else \ 875 return (parent); \ 876 } \ 877 return (name##_RB_INSERT_FINISH(head, parent, tmpp, elm)); \ 878 } 879 880 #define RB_GENERATE_FIND(name, type, field, cmp, attr) \ 881 /* Finds the node with the same key as elm */ \ 882 attr struct type * \ 883 name##_RB_FIND(struct name *head, struct type *elm) \ 884 { \ 885 struct type *tmp = RB_ROOT(head); \ 886 __typeof(cmp(NULL, NULL)) comp; \ 887 while (tmp) { \ 888 comp = cmp(elm, tmp); \ 889 if (comp < 0) \ 890 tmp = RB_LEFT(tmp, field); \ 891 else if (comp > 0) \ 892 tmp = RB_RIGHT(tmp, field); \ 893 else \ 894 return (tmp); \ 895 } \ 896 return (NULL); \ 897 } 898 899 #define RB_GENERATE_NFIND(name, type, field, cmp, attr) \ 900 /* Finds the first node greater than or equal to the search key */ \ 901 attr struct type * \ 902 name##_RB_NFIND(struct name *head, struct type *elm) \ 903 { \ 904 struct type *tmp = RB_ROOT(head); \ 905 struct type *res = NULL; \ 906 __typeof(cmp(NULL, NULL)) comp; \ 907 while (tmp) { \ 908 comp = cmp(elm, tmp); \ 909 if (comp < 0) { \ 910 res = tmp; \ 911 tmp = RB_LEFT(tmp, field); \ 912 } \ 913 else if (comp > 0) \ 914 tmp = RB_RIGHT(tmp, field); \ 915 else \ 916 return (tmp); \ 917 } \ 918 return (res); \ 919 } 920 921 #define RB_GENERATE_NEXT(name, type, field, attr) \ 922 /* ARGSUSED */ \ 923 attr struct type * \ 924 name##_RB_NEXT(struct type *elm) \ 925 { \ 926 if (RB_RIGHT(elm, field)) { \ 927 elm = RB_RIGHT(elm, field); \ 928 while (RB_LEFT(elm, field)) \ 929 elm = RB_LEFT(elm, field); \ 930 } else { \ 931 while (RB_PARENT(elm, field) && \ 932 (elm == RB_RIGHT(RB_PARENT(elm, field), field))) \ 933 elm = RB_PARENT(elm, field); \ 934 elm = RB_PARENT(elm, field); \ 935 } \ 936 return (elm); \ 937 } 938 939 #if defined(_KERNEL) && defined(DIAGNOSTIC) 940 #define _RB_ORDER_CHECK(cmp, lo, hi) do { \ 941 KASSERT((cmp)(lo, hi) < 0, ("out of order insertion")); \ 942 } while (0) 943 #else 944 #define _RB_ORDER_CHECK(cmp, lo, hi) do {} while (0) 945 #endif 946 947 #define RB_GENERATE_INSERT_NEXT(name, type, field, cmp, attr) \ 948 /* Inserts a node into the next position in the RB tree */ \ 949 attr struct type * \ 950 name##_RB_INSERT_NEXT(struct name *head, \ 951 struct type *elm, struct type *next) \ 952 { \ 953 struct type *tmp; \ 954 struct type **tmpp = &RB_RIGHT(elm, field); \ 955 \ 956 _RB_ORDER_CHECK(cmp, elm, next); \ 957 if (name##_RB_NEXT(elm) != NULL) \ 958 _RB_ORDER_CHECK(cmp, next, name##_RB_NEXT(elm)); \ 959 while ((tmp = *tmpp) != NULL) { \ 960 elm = tmp; \ 961 tmpp = &RB_LEFT(elm, field); \ 962 } \ 963 return (name##_RB_INSERT_FINISH(head, elm, tmpp, next)); \ 964 } 965 966 #define RB_GENERATE_PREV(name, type, field, attr) \ 967 /* ARGSUSED */ \ 968 attr struct type * \ 969 name##_RB_PREV(struct type *elm) \ 970 { \ 971 if (RB_LEFT(elm, field)) { \ 972 elm = RB_LEFT(elm, field); \ 973 while (RB_RIGHT(elm, field)) \ 974 elm = RB_RIGHT(elm, field); \ 975 } else { \ 976 while (RB_PARENT(elm, field) && \ 977 (elm == RB_LEFT(RB_PARENT(elm, field), field))) \ 978 elm = RB_PARENT(elm, field); \ 979 elm = RB_PARENT(elm, field); \ 980 } \ 981 return (elm); \ 982 } 983 984 #define RB_GENERATE_INSERT_PREV(name, type, field, cmp, attr) \ 985 /* Inserts a node into the prev position in the RB tree */ \ 986 attr struct type * \ 987 name##_RB_INSERT_PREV(struct name *head, \ 988 struct type *elm, struct type *prev) \ 989 { \ 990 struct type *tmp; \ 991 struct type **tmpp = &RB_LEFT(elm, field); \ 992 \ 993 _RB_ORDER_CHECK(cmp, prev, elm); \ 994 if (name##_RB_PREV(elm) != NULL) \ 995 _RB_ORDER_CHECK(cmp, name##_RB_PREV(elm), prev); \ 996 while ((tmp = *tmpp) != NULL) { \ 997 elm = tmp; \ 998 tmpp = &RB_RIGHT(elm, field); \ 999 } \ 1000 return (name##_RB_INSERT_FINISH(head, elm, tmpp, prev)); \ 1001 } 1002 1003 #define RB_GENERATE_MINMAX(name, type, field, attr) \ 1004 attr struct type * \ 1005 name##_RB_MINMAX(struct name *head, int val) \ 1006 { \ 1007 struct type *tmp = RB_ROOT(head); \ 1008 struct type *parent = NULL; \ 1009 while (tmp) { \ 1010 parent = tmp; \ 1011 if (val < 0) \ 1012 tmp = RB_LEFT(tmp, field); \ 1013 else \ 1014 tmp = RB_RIGHT(tmp, field); \ 1015 } \ 1016 return (parent); \ 1017 } 1018 1019 #define RB_GENERATE_REINSERT(name, type, field, cmp, attr) \ 1020 attr struct type * \ 1021 name##_RB_REINSERT(struct name *head, struct type *elm) \ 1022 { \ 1023 struct type *cmpelm; \ 1024 if (((cmpelm = RB_PREV(name, head, elm)) != NULL && \ 1025 cmp(cmpelm, elm) >= 0) || \ 1026 ((cmpelm = RB_NEXT(name, head, elm)) != NULL && \ 1027 cmp(elm, cmpelm) >= 0)) { \ 1028 /* XXXLAS: Remove/insert is heavy handed. */ \ 1029 RB_REMOVE(name, head, elm); \ 1030 return (RB_INSERT(name, head, elm)); \ 1031 } \ 1032 return (NULL); \ 1033 } \ 1034 1035 #define RB_NEGINF -1 1036 #define RB_INF 1 1037 1038 #define RB_INSERT(name, x, y) name##_RB_INSERT(x, y) 1039 #define RB_INSERT_NEXT(name, x, y, z) name##_RB_INSERT_NEXT(x, y, z) 1040 #define RB_INSERT_PREV(name, x, y, z) name##_RB_INSERT_PREV(x, y, z) 1041 #define RB_REMOVE(name, x, y) name##_RB_REMOVE(x, y) 1042 #define RB_FIND(name, x, y) name##_RB_FIND(x, y) 1043 #define RB_NFIND(name, x, y) name##_RB_NFIND(x, y) 1044 #define RB_NEXT(name, x, y) name##_RB_NEXT(y) 1045 #define RB_PREV(name, x, y) name##_RB_PREV(y) 1046 #define RB_MIN(name, x) name##_RB_MINMAX(x, RB_NEGINF) 1047 #define RB_MAX(name, x) name##_RB_MINMAX(x, RB_INF) 1048 #define RB_REINSERT(name, x, y) name##_RB_REINSERT(x, y) 1049 1050 #define RB_FOREACH(x, name, head) \ 1051 for ((x) = RB_MIN(name, head); \ 1052 (x) != NULL; \ 1053 (x) = name##_RB_NEXT(x)) 1054 1055 #define RB_FOREACH_FROM(x, name, y) \ 1056 for ((x) = (y); \ 1057 ((x) != NULL) && ((y) = name##_RB_NEXT(x), (x) != NULL); \ 1058 (x) = (y)) 1059 1060 #define RB_FOREACH_SAFE(x, name, head, y) \ 1061 for ((x) = RB_MIN(name, head); \ 1062 ((x) != NULL) && ((y) = name##_RB_NEXT(x), (x) != NULL); \ 1063 (x) = (y)) 1064 1065 #define RB_FOREACH_REVERSE(x, name, head) \ 1066 for ((x) = RB_MAX(name, head); \ 1067 (x) != NULL; \ 1068 (x) = name##_RB_PREV(x)) 1069 1070 #define RB_FOREACH_REVERSE_FROM(x, name, y) \ 1071 for ((x) = (y); \ 1072 ((x) != NULL) && ((y) = name##_RB_PREV(x), (x) != NULL); \ 1073 (x) = (y)) 1074 1075 #define RB_FOREACH_REVERSE_SAFE(x, name, head, y) \ 1076 for ((x) = RB_MAX(name, head); \ 1077 ((x) != NULL) && ((y) = name##_RB_PREV(x), (x) != NULL); \ 1078 (x) = (y)) 1079 1080 #endif /* _SYS_TREE_H_ */ 1081