1 /*- 2 * SPDX-License-Identifier: BSD-2-Clause-FreeBSD 3 * 4 * Copyright 2002 Niels Provos <provos@citi.umich.edu> 5 * All rights reserved. 6 * 7 * Redistribution and use in source and binary forms, with or without 8 * modification, are permitted provided that the following conditions 9 * are met: 10 * 1. Redistributions of source code must retain the above copyright 11 * notice, this list of conditions and the following disclaimer. 12 * 2. Redistributions in binary form must reproduce the above copyright 13 * notice, this list of conditions and the following disclaimer in the 14 * documentation and/or other materials provided with the distribution. 15 * 16 * THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR 17 * IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES 18 * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED. 19 * IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT, 20 * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT 21 * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, 22 * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY 23 * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT 24 * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF 25 * THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. 26 */ 27 28 #ifndef SPDK_TREE_H 29 #define SPDK_TREE_H 30 31 #include <sys/cdefs.h> 32 33 #ifdef __cplusplus 34 extern "C" { 35 #endif 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 __attribute__((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 __attribute__((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 __attribute__((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 /* 348 * _RB_ROOT starts with an underscore. This is a workaround for the issue that 349 * RB_ROOT() had a name conflict with the SPDK FIO plugin. The SPDK FIO plugin 350 * includes FIO and FIO defines RB_ROOT() itself. 351 */ 352 #define _RB_ROOT(head) (head)->rbh_root 353 #define RB_EMPTY(head) (_RB_ROOT(head) == NULL) 354 355 #define RB_SET_PARENT(dst, src, field) do { \ 356 RB_BITS(dst, field) &= RB_RED_MASK; \ 357 RB_BITS(dst, field) |= (uintptr_t)src; \ 358 } while (/* CONSTCOND */ 0) 359 360 #define RB_SET(elm, parent, field) do { \ 361 RB_UP(elm, field) = parent; \ 362 RB_LEFT(elm, field) = RB_RIGHT(elm, field) = NULL; \ 363 } while (/* CONSTCOND */ 0) 364 365 #define RB_COLOR(elm, field) (RB_PARENT(elm, field) == NULL ? 0 : \ 366 RB_LEFT(RB_PARENT(elm, field), field) == elm ? \ 367 RB_RED_LEFT(RB_PARENT(elm, field), field) : \ 368 RB_RED_RIGHT(RB_PARENT(elm, field), field)) 369 370 /* 371 * Something to be invoked in a loop at the root of every modified subtree, 372 * from the bottom up to the root, to update augmented node data. 373 */ 374 #ifndef RB_AUGMENT 375 #define RB_AUGMENT(x) break 376 #endif 377 378 #define RB_SWAP_CHILD(head, out, in, field) do { \ 379 if (RB_PARENT(out, field) == NULL) \ 380 _RB_ROOT(head) = (in); \ 381 else if ((out) == RB_LEFT(RB_PARENT(out, field), field)) \ 382 RB_LEFT(RB_PARENT(out, field), field) = (in); \ 383 else \ 384 RB_RIGHT(RB_PARENT(out, field), field) = (in); \ 385 } while (/* CONSTCOND */ 0) 386 387 #define RB_ROTATE_LEFT(head, elm, tmp, field) do { \ 388 (tmp) = RB_RIGHT(elm, field); \ 389 if ((RB_RIGHT(elm, field) = RB_LEFT(tmp, field)) != NULL) { \ 390 RB_SET_PARENT(RB_RIGHT(elm, field), elm, field); \ 391 } \ 392 RB_SET_PARENT(tmp, RB_PARENT(elm, field), field); \ 393 RB_SWAP_CHILD(head, elm, tmp, field); \ 394 RB_LEFT(tmp, field) = (elm); \ 395 RB_SET_PARENT(elm, tmp, field); \ 396 RB_AUGMENT(elm); \ 397 } while (/* CONSTCOND */ 0) 398 399 #define RB_ROTATE_RIGHT(head, elm, tmp, field) do { \ 400 (tmp) = RB_LEFT(elm, field); \ 401 if ((RB_LEFT(elm, field) = RB_RIGHT(tmp, field)) != NULL) { \ 402 RB_SET_PARENT(RB_LEFT(elm, field), elm, field); \ 403 } \ 404 RB_SET_PARENT(tmp, RB_PARENT(elm, field), field); \ 405 RB_SWAP_CHILD(head, elm, tmp, field); \ 406 RB_RIGHT(tmp, field) = (elm); \ 407 RB_SET_PARENT(elm, tmp, field); \ 408 RB_AUGMENT(elm); \ 409 } while (/* CONSTCOND */ 0) 410 411 /* Generates prototypes and inline functions */ 412 #define RB_PROTOTYPE(name, type, field, cmp) \ 413 RB_PROTOTYPE_INTERNAL(name, type, field, cmp,) 414 #define RB_PROTOTYPE_STATIC(name, type, field, cmp) \ 415 RB_PROTOTYPE_INTERNAL(name, type, field, cmp, __attribute__((unused)) static) 416 #define RB_PROTOTYPE_INTERNAL(name, type, field, cmp, attr) \ 417 RB_PROTOTYPE_INSERT_COLOR(name, type, attr); \ 418 RB_PROTOTYPE_REMOVE_COLOR(name, type, attr); \ 419 RB_PROTOTYPE_INSERT(name, type, attr); \ 420 RB_PROTOTYPE_REMOVE(name, type, attr); \ 421 RB_PROTOTYPE_FIND(name, type, attr); \ 422 RB_PROTOTYPE_NFIND(name, type, attr); \ 423 RB_PROTOTYPE_NEXT(name, type, attr); \ 424 RB_PROTOTYPE_PREV(name, type, attr); \ 425 RB_PROTOTYPE_MINMAX(name, type, attr); \ 426 RB_PROTOTYPE_REINSERT(name, type, attr); 427 #define RB_PROTOTYPE_INSERT_COLOR(name, type, attr) \ 428 attr void name##_RB_INSERT_COLOR(struct name *, struct type *) 429 #define RB_PROTOTYPE_REMOVE_COLOR(name, type, attr) \ 430 attr void name##_RB_REMOVE_COLOR(struct name *, \ 431 struct type *, struct type *) 432 #define RB_PROTOTYPE_REMOVE(name, type, attr) \ 433 attr struct type *name##_RB_REMOVE(struct name *, struct type *) 434 #define RB_PROTOTYPE_INSERT(name, type, attr) \ 435 attr struct type *name##_RB_INSERT(struct name *, struct type *) 436 #define RB_PROTOTYPE_FIND(name, type, attr) \ 437 attr struct type *name##_RB_FIND(struct name *, struct type *) 438 #define RB_PROTOTYPE_NFIND(name, type, attr) \ 439 attr struct type *name##_RB_NFIND(struct name *, struct type *) 440 #define RB_PROTOTYPE_NEXT(name, type, attr) \ 441 attr struct type *name##_RB_NEXT(struct type *) 442 #define RB_PROTOTYPE_PREV(name, type, attr) \ 443 attr struct type *name##_RB_PREV(struct type *) 444 #define RB_PROTOTYPE_MINMAX(name, type, attr) \ 445 attr struct type *name##_RB_MINMAX(struct name *, int) 446 #define RB_PROTOTYPE_REINSERT(name, type, attr) \ 447 attr struct type *name##_RB_REINSERT(struct name *, struct type *) 448 449 /* Main rb operation. 450 * Moves node close to the key of elm to top 451 */ 452 #define RB_GENERATE(name, type, field, cmp) \ 453 RB_GENERATE_INTERNAL(name, type, field, cmp,) 454 #define RB_GENERATE_STATIC(name, type, field, cmp) \ 455 RB_GENERATE_INTERNAL(name, type, field, cmp, __attribute__((unused)) static) 456 #define RB_GENERATE_INTERNAL(name, type, field, cmp, attr) \ 457 RB_GENERATE_INSERT_COLOR(name, type, field, attr) \ 458 RB_GENERATE_REMOVE_COLOR(name, type, field, attr) \ 459 RB_GENERATE_INSERT(name, type, field, cmp, attr) \ 460 RB_GENERATE_REMOVE(name, type, field, attr) \ 461 RB_GENERATE_FIND(name, type, field, cmp, attr) \ 462 RB_GENERATE_NFIND(name, type, field, cmp, attr) \ 463 RB_GENERATE_NEXT(name, type, field, attr) \ 464 RB_GENERATE_PREV(name, type, field, attr) \ 465 RB_GENERATE_MINMAX(name, type, field, attr) \ 466 RB_GENERATE_REINSERT(name, type, field, cmp, attr) 467 468 #define RB_GENERATE_INSERT_COLOR(name, type, field, attr) \ 469 attr void \ 470 name##_RB_INSERT_COLOR(struct name *head, struct type *elm) \ 471 { \ 472 struct type *child, *parent; \ 473 while ((parent = RB_PARENT(elm, field)) != NULL) { \ 474 if (RB_LEFT(parent, field) == elm) { \ 475 if (RB_RED_LEFT(parent, field)) { \ 476 RB_FLIP_LEFT(parent, field); \ 477 return; \ 478 } \ 479 RB_FLIP_RIGHT(parent, field); \ 480 if (RB_RED_RIGHT(parent, field)) { \ 481 elm = parent; \ 482 continue; \ 483 } \ 484 if (!RB_RED_RIGHT(elm, field)) { \ 485 RB_FLIP_LEFT(elm, field); \ 486 RB_ROTATE_LEFT(head, elm, child, field);\ 487 if (RB_RED_LEFT(child, field)) \ 488 RB_FLIP_RIGHT(elm, field); \ 489 else if (RB_RED_RIGHT(child, field)) \ 490 RB_FLIP_LEFT(parent, field); \ 491 elm = child; \ 492 } \ 493 RB_ROTATE_RIGHT(head, parent, elm, field); \ 494 } else { \ 495 if (RB_RED_RIGHT(parent, field)) { \ 496 RB_FLIP_RIGHT(parent, field); \ 497 return; \ 498 } \ 499 RB_FLIP_LEFT(parent, field); \ 500 if (RB_RED_LEFT(parent, field)) { \ 501 elm = parent; \ 502 continue; \ 503 } \ 504 if (!RB_RED_LEFT(elm, field)) { \ 505 RB_FLIP_RIGHT(elm, field); \ 506 RB_ROTATE_RIGHT(head, elm, child, field);\ 507 if (RB_RED_RIGHT(child, field)) \ 508 RB_FLIP_LEFT(elm, field); \ 509 else if (RB_RED_LEFT(child, field)) \ 510 RB_FLIP_RIGHT(parent, field); \ 511 elm = child; \ 512 } \ 513 RB_ROTATE_LEFT(head, parent, elm, field); \ 514 } \ 515 RB_BITS(elm, field) &= ~RB_RED_MASK; \ 516 break; \ 517 } \ 518 } 519 520 #define RB_GENERATE_REMOVE_COLOR(name, type, field, attr) \ 521 attr void \ 522 name##_RB_REMOVE_COLOR(struct name *head, \ 523 struct type *parent, struct type *elm) \ 524 { \ 525 struct type *sib; \ 526 if (RB_LEFT(parent, field) == elm && \ 527 RB_RIGHT(parent, field) == elm) { \ 528 RB_BITS(parent, field) &= ~RB_RED_MASK; \ 529 elm = parent; \ 530 parent = RB_PARENT(elm, field); \ 531 if (parent == NULL) \ 532 return; \ 533 } \ 534 do { \ 535 if (RB_LEFT(parent, field) == elm) { \ 536 if (!RB_RED_LEFT(parent, field)) { \ 537 RB_FLIP_LEFT(parent, field); \ 538 return; \ 539 } \ 540 if (RB_RED_RIGHT(parent, field)) { \ 541 RB_FLIP_RIGHT(parent, field); \ 542 elm = parent; \ 543 continue; \ 544 } \ 545 sib = RB_RIGHT(parent, field); \ 546 if ((~RB_BITS(sib, field) & RB_RED_MASK) == 0) {\ 547 RB_BITS(sib, field) &= ~RB_RED_MASK; \ 548 elm = parent; \ 549 continue; \ 550 } \ 551 RB_FLIP_RIGHT(sib, field); \ 552 if (RB_RED_LEFT(sib, field)) \ 553 RB_FLIP_LEFT(parent, field); \ 554 else if (!RB_RED_RIGHT(sib, field)) { \ 555 RB_FLIP_LEFT(parent, field); \ 556 RB_ROTATE_RIGHT(head, sib, elm, field); \ 557 if (RB_RED_RIGHT(elm, field)) \ 558 RB_FLIP_LEFT(sib, field); \ 559 if (RB_RED_LEFT(elm, field)) \ 560 RB_FLIP_RIGHT(parent, field); \ 561 RB_BITS(elm, field) |= RB_RED_MASK; \ 562 sib = elm; \ 563 } \ 564 RB_ROTATE_LEFT(head, parent, sib, field); \ 565 } else { \ 566 if (!RB_RED_RIGHT(parent, field)) { \ 567 RB_FLIP_RIGHT(parent, field); \ 568 return; \ 569 } \ 570 if (RB_RED_LEFT(parent, field)) { \ 571 RB_FLIP_LEFT(parent, field); \ 572 elm = parent; \ 573 continue; \ 574 } \ 575 sib = RB_LEFT(parent, field); \ 576 if ((~RB_BITS(sib, field) & RB_RED_MASK) == 0) {\ 577 RB_BITS(sib, field) &= ~RB_RED_MASK; \ 578 elm = parent; \ 579 continue; \ 580 } \ 581 RB_FLIP_LEFT(sib, field); \ 582 if (RB_RED_RIGHT(sib, field)) \ 583 RB_FLIP_RIGHT(parent, field); \ 584 else if (!RB_RED_LEFT(sib, field)) { \ 585 RB_FLIP_RIGHT(parent, field); \ 586 RB_ROTATE_LEFT(head, sib, elm, field); \ 587 if (RB_RED_LEFT(elm, field)) \ 588 RB_FLIP_RIGHT(sib, field); \ 589 if (RB_RED_RIGHT(elm, field)) \ 590 RB_FLIP_LEFT(parent, field); \ 591 RB_BITS(elm, field) |= RB_RED_MASK; \ 592 sib = elm; \ 593 } \ 594 RB_ROTATE_RIGHT(head, parent, sib, field); \ 595 } \ 596 break; \ 597 } while ((parent = RB_PARENT(elm, field)) != NULL); \ 598 } 599 600 #define RB_GENERATE_REMOVE(name, type, field, attr) \ 601 attr struct type * \ 602 name##_RB_REMOVE(struct name *head, struct type *elm) \ 603 { \ 604 struct type *child, *old, *parent, *right; \ 605 \ 606 old = elm; \ 607 parent = RB_PARENT(elm, field); \ 608 right = RB_RIGHT(elm, field); \ 609 if (RB_LEFT(elm, field) == NULL) \ 610 elm = child = right; \ 611 else if (right == NULL) \ 612 elm = child = RB_LEFT(elm, field); \ 613 else { \ 614 if ((child = RB_LEFT(right, field)) == NULL) { \ 615 child = RB_RIGHT(right, field); \ 616 RB_RIGHT(old, field) = child; \ 617 parent = elm = right; \ 618 } else { \ 619 do \ 620 elm = child; \ 621 while ((child = RB_LEFT(elm, field)) != NULL); \ 622 child = RB_RIGHT(elm, field); \ 623 parent = RB_PARENT(elm, field); \ 624 RB_LEFT(parent, field) = child; \ 625 RB_SET_PARENT(RB_RIGHT(old, field), elm, field);\ 626 } \ 627 RB_SET_PARENT(RB_LEFT(old, field), elm, field); \ 628 elm->field = old->field; \ 629 } \ 630 RB_SWAP_CHILD(head, old, elm, field); \ 631 if (child != NULL) \ 632 RB_SET_PARENT(child, parent, field); \ 633 if (parent != NULL) \ 634 name##_RB_REMOVE_COLOR(head, parent, child); \ 635 while (parent != NULL) { \ 636 RB_AUGMENT(parent); \ 637 parent = RB_PARENT(parent, field); \ 638 } \ 639 return (old); \ 640 } 641 642 #define RB_GENERATE_INSERT(name, type, field, cmp, attr) \ 643 /* Inserts a node into the RB tree */ \ 644 attr struct type * \ 645 name##_RB_INSERT(struct name *head, struct type *elm) \ 646 { \ 647 struct type *tmp; \ 648 struct type *parent = NULL; \ 649 int comp = 0; \ 650 tmp = _RB_ROOT(head); \ 651 while (tmp) { \ 652 parent = tmp; \ 653 comp = (cmp)(elm, parent); \ 654 if (comp < 0) \ 655 tmp = RB_LEFT(tmp, field); \ 656 else if (comp > 0) \ 657 tmp = RB_RIGHT(tmp, field); \ 658 else \ 659 return (tmp); \ 660 } \ 661 RB_SET(elm, parent, field); \ 662 if (parent == NULL) \ 663 _RB_ROOT(head) = elm; \ 664 else if (comp < 0) \ 665 RB_LEFT(parent, field) = elm; \ 666 else \ 667 RB_RIGHT(parent, field) = elm; \ 668 name##_RB_INSERT_COLOR(head, elm); \ 669 while (elm != NULL) { \ 670 RB_AUGMENT(elm); \ 671 elm = RB_PARENT(elm, field); \ 672 } \ 673 return (NULL); \ 674 } 675 676 #define RB_GENERATE_FIND(name, type, field, cmp, attr) \ 677 /* Finds the node with the same key as elm */ \ 678 attr struct type * \ 679 name##_RB_FIND(struct name *head, struct type *elm) \ 680 { \ 681 struct type *tmp = _RB_ROOT(head); \ 682 int comp; \ 683 while (tmp) { \ 684 comp = cmp(elm, tmp); \ 685 if (comp < 0) \ 686 tmp = RB_LEFT(tmp, field); \ 687 else if (comp > 0) \ 688 tmp = RB_RIGHT(tmp, field); \ 689 else \ 690 return (tmp); \ 691 } \ 692 return (NULL); \ 693 } 694 695 #define RB_GENERATE_NFIND(name, type, field, cmp, attr) \ 696 /* Finds the first node greater than or equal to the search key */ \ 697 attr struct type * \ 698 name##_RB_NFIND(struct name *head, struct type *elm) \ 699 { \ 700 struct type *tmp = _RB_ROOT(head); \ 701 struct type *res = NULL; \ 702 int comp; \ 703 while (tmp) { \ 704 comp = cmp(elm, tmp); \ 705 if (comp < 0) { \ 706 res = tmp; \ 707 tmp = RB_LEFT(tmp, field); \ 708 } \ 709 else if (comp > 0) \ 710 tmp = RB_RIGHT(tmp, field); \ 711 else \ 712 return (tmp); \ 713 } \ 714 return (res); \ 715 } 716 717 #define RB_GENERATE_NEXT(name, type, field, attr) \ 718 /* ARGSUSED */ \ 719 attr struct type * \ 720 name##_RB_NEXT(struct type *elm) \ 721 { \ 722 if (RB_RIGHT(elm, field)) { \ 723 elm = RB_RIGHT(elm, field); \ 724 while (RB_LEFT(elm, field)) \ 725 elm = RB_LEFT(elm, field); \ 726 } else { \ 727 if (RB_PARENT(elm, field) && \ 728 (elm == RB_LEFT(RB_PARENT(elm, field), field))) \ 729 elm = RB_PARENT(elm, field); \ 730 else { \ 731 while (RB_PARENT(elm, field) && \ 732 (elm == RB_RIGHT(RB_PARENT(elm, field), field)))\ 733 elm = RB_PARENT(elm, field); \ 734 elm = RB_PARENT(elm, field); \ 735 } \ 736 } \ 737 return (elm); \ 738 } 739 740 #define RB_GENERATE_PREV(name, type, field, attr) \ 741 /* ARGSUSED */ \ 742 attr struct type * \ 743 name##_RB_PREV(struct type *elm) \ 744 { \ 745 if (RB_LEFT(elm, field)) { \ 746 elm = RB_LEFT(elm, field); \ 747 while (RB_RIGHT(elm, field)) \ 748 elm = RB_RIGHT(elm, field); \ 749 } else { \ 750 if (RB_PARENT(elm, field) && \ 751 (elm == RB_RIGHT(RB_PARENT(elm, field), field))) \ 752 elm = RB_PARENT(elm, field); \ 753 else { \ 754 while (RB_PARENT(elm, field) && \ 755 (elm == RB_LEFT(RB_PARENT(elm, field), field)))\ 756 elm = RB_PARENT(elm, field); \ 757 elm = RB_PARENT(elm, field); \ 758 } \ 759 } \ 760 return (elm); \ 761 } 762 763 #define RB_GENERATE_MINMAX(name, type, field, attr) \ 764 attr struct type * \ 765 name##_RB_MINMAX(struct name *head, int val) \ 766 { \ 767 struct type *tmp = _RB_ROOT(head); \ 768 struct type *parent = NULL; \ 769 while (tmp) { \ 770 parent = tmp; \ 771 if (val < 0) \ 772 tmp = RB_LEFT(tmp, field); \ 773 else \ 774 tmp = RB_RIGHT(tmp, field); \ 775 } \ 776 return (parent); \ 777 } 778 779 #define RB_GENERATE_REINSERT(name, type, field, cmp, attr) \ 780 attr struct type * \ 781 name##_RB_REINSERT(struct name *head, struct type *elm) \ 782 { \ 783 struct type *cmpelm; \ 784 if (((cmpelm = RB_PREV(name, head, elm)) != NULL && \ 785 cmp(cmpelm, elm) >= 0) || \ 786 ((cmpelm = RB_NEXT(name, head, elm)) != NULL && \ 787 cmp(elm, cmpelm) >= 0)) { \ 788 /* XXXLAS: Remove/insert is heavy handed. */ \ 789 RB_REMOVE(name, head, elm); \ 790 return (RB_INSERT(name, head, elm)); \ 791 } \ 792 return (NULL); \ 793 } \ 794 795 #define RB_NEGINF -1 796 #define RB_INF 1 797 798 #define RB_INSERT(name, x, y) name##_RB_INSERT(x, y) 799 #define RB_REMOVE(name, x, y) name##_RB_REMOVE(x, y) 800 #define RB_FIND(name, x, y) name##_RB_FIND(x, y) 801 #define RB_NFIND(name, x, y) name##_RB_NFIND(x, y) 802 #define RB_NEXT(name, x, y) name##_RB_NEXT(y) 803 #define RB_PREV(name, x, y) name##_RB_PREV(y) 804 #define RB_MIN(name, x) name##_RB_MINMAX(x, RB_NEGINF) 805 #define RB_MAX(name, x) name##_RB_MINMAX(x, RB_INF) 806 #define RB_REINSERT(name, x, y) name##_RB_REINSERT(x, y) 807 808 #define RB_FOREACH(x, name, head) \ 809 for ((x) = RB_MIN(name, head); \ 810 (x) != NULL; \ 811 (x) = name##_RB_NEXT(x)) 812 813 #define RB_FOREACH_FROM(x, name, y) \ 814 for ((x) = (y); \ 815 ((x) != NULL) && ((y) = name##_RB_NEXT(x), (x) != NULL); \ 816 (x) = (y)) 817 818 #define RB_FOREACH_SAFE(x, name, head, y) \ 819 for ((x) = RB_MIN(name, head); \ 820 ((x) != NULL) && ((y) = name##_RB_NEXT(x), (x) != NULL); \ 821 (x) = (y)) 822 823 #define RB_FOREACH_REVERSE(x, name, head) \ 824 for ((x) = RB_MAX(name, head); \ 825 (x) != NULL; \ 826 (x) = name##_RB_PREV(x)) 827 828 #define RB_FOREACH_REVERSE_FROM(x, name, y) \ 829 for ((x) = (y); \ 830 ((x) != NULL) && ((y) = name##_RB_PREV(x), (x) != NULL); \ 831 (x) = (y)) 832 833 #define RB_FOREACH_REVERSE_SAFE(x, name, head, y) \ 834 for ((x) = RB_MAX(name, head); \ 835 ((x) != NULL) && ((y) = name##_RB_PREV(x), (x) != NULL); \ 836 (x) = (y)) 837 838 #ifdef __cplusplus 839 } 840 #endif 841 842 #endif /* SPDK_TREE_H */ 843