1 /* SPDX-License-Identifier: GPL-2.0-or-later */ 2 3 #include "qemu/osdep.h" 4 #include "qemu/interval-tree.h" 5 #include "qemu/atomic.h" 6 7 /* 8 * Red Black Trees. 9 * 10 * For now, don't expose Linux Red-Black Trees separately, but retain the 11 * separate type definitions to keep the implementation sane, and allow 12 * the possibility of separating them later. 13 * 14 * Derived from include/linux/rbtree_augmented.h and its dependencies. 15 */ 16 17 /* 18 * red-black trees properties: https://en.wikipedia.org/wiki/Rbtree 19 * 20 * 1) A node is either red or black 21 * 2) The root is black 22 * 3) All leaves (NULL) are black 23 * 4) Both children of every red node are black 24 * 5) Every simple path from root to leaves contains the same number 25 * of black nodes. 26 * 27 * 4 and 5 give the O(log n) guarantee, since 4 implies you cannot have two 28 * consecutive red nodes in a path and every red node is therefore followed by 29 * a black. So if B is the number of black nodes on every simple path (as per 30 * 5), then the longest possible path due to 4 is 2B. 31 * 32 * We shall indicate color with case, where black nodes are uppercase and red 33 * nodes will be lowercase. Unknown color nodes shall be drawn as red within 34 * parentheses and have some accompanying text comment. 35 * 36 * Notes on lockless lookups: 37 * 38 * All stores to the tree structure (rb_left and rb_right) must be done using 39 * WRITE_ONCE [qatomic_set for QEMU]. And we must not inadvertently cause 40 * (temporary) loops in the tree structure as seen in program order. 41 * 42 * These two requirements will allow lockless iteration of the tree -- not 43 * correct iteration mind you, tree rotations are not atomic so a lookup might 44 * miss entire subtrees. 45 * 46 * But they do guarantee that any such traversal will only see valid elements 47 * and that it will indeed complete -- does not get stuck in a loop. 48 * 49 * It also guarantees that if the lookup returns an element it is the 'correct' 50 * one. But not returning an element does _NOT_ mean it's not present. 51 * 52 * NOTE: 53 * 54 * Stores to __rb_parent_color are not important for simple lookups so those 55 * are left undone as of now. Nor did I check for loops involving parent 56 * pointers. 57 */ 58 59 typedef enum RBColor 60 { 61 RB_RED, 62 RB_BLACK, 63 } RBColor; 64 65 typedef struct RBAugmentCallbacks { 66 void (*propagate)(RBNode *node, RBNode *stop); 67 void (*copy)(RBNode *old, RBNode *new); 68 void (*rotate)(RBNode *old, RBNode *new); 69 } RBAugmentCallbacks; 70 71 static inline RBNode *rb_parent(const RBNode *n) 72 { 73 return (RBNode *)(n->rb_parent_color & ~1); 74 } 75 76 static inline RBNode *rb_red_parent(const RBNode *n) 77 { 78 return (RBNode *)n->rb_parent_color; 79 } 80 81 static inline RBColor pc_color(uintptr_t pc) 82 { 83 return (RBColor)(pc & 1); 84 } 85 86 static inline bool pc_is_red(uintptr_t pc) 87 { 88 return pc_color(pc) == RB_RED; 89 } 90 91 static inline bool pc_is_black(uintptr_t pc) 92 { 93 return !pc_is_red(pc); 94 } 95 96 static inline RBColor rb_color(const RBNode *n) 97 { 98 return pc_color(n->rb_parent_color); 99 } 100 101 static inline bool rb_is_red(const RBNode *n) 102 { 103 return pc_is_red(n->rb_parent_color); 104 } 105 106 static inline bool rb_is_black(const RBNode *n) 107 { 108 return pc_is_black(n->rb_parent_color); 109 } 110 111 static inline void rb_set_black(RBNode *n) 112 { 113 n->rb_parent_color |= RB_BLACK; 114 } 115 116 static inline void rb_set_parent_color(RBNode *n, RBNode *p, RBColor color) 117 { 118 n->rb_parent_color = (uintptr_t)p | color; 119 } 120 121 static inline void rb_set_parent(RBNode *n, RBNode *p) 122 { 123 rb_set_parent_color(n, p, rb_color(n)); 124 } 125 126 static inline void rb_link_node(RBNode *node, RBNode *parent, RBNode **rb_link) 127 { 128 node->rb_parent_color = (uintptr_t)parent; 129 node->rb_left = node->rb_right = NULL; 130 131 qatomic_set(rb_link, node); 132 } 133 134 static RBNode *rb_next(RBNode *node) 135 { 136 RBNode *parent; 137 138 /* OMIT: if empty node, return null. */ 139 140 /* 141 * If we have a right-hand child, go down and then left as far as we can. 142 */ 143 if (node->rb_right) { 144 node = node->rb_right; 145 while (node->rb_left) { 146 node = node->rb_left; 147 } 148 return node; 149 } 150 151 /* 152 * No right-hand children. Everything down and left is smaller than us, 153 * so any 'next' node must be in the general direction of our parent. 154 * Go up the tree; any time the ancestor is a right-hand child of its 155 * parent, keep going up. First time it's a left-hand child of its 156 * parent, said parent is our 'next' node. 157 */ 158 while ((parent = rb_parent(node)) && node == parent->rb_right) { 159 node = parent; 160 } 161 162 return parent; 163 } 164 165 static inline void rb_change_child(RBNode *old, RBNode *new, 166 RBNode *parent, RBRoot *root) 167 { 168 if (!parent) { 169 qatomic_set(&root->rb_node, new); 170 } else if (parent->rb_left == old) { 171 qatomic_set(&parent->rb_left, new); 172 } else { 173 qatomic_set(&parent->rb_right, new); 174 } 175 } 176 177 static inline void rb_rotate_set_parents(RBNode *old, RBNode *new, 178 RBRoot *root, RBColor color) 179 { 180 RBNode *parent = rb_parent(old); 181 182 new->rb_parent_color = old->rb_parent_color; 183 rb_set_parent_color(old, new, color); 184 rb_change_child(old, new, parent, root); 185 } 186 187 static void rb_insert_augmented(RBNode *node, RBRoot *root, 188 const RBAugmentCallbacks *augment) 189 { 190 RBNode *parent = rb_red_parent(node), *gparent, *tmp; 191 192 while (true) { 193 /* 194 * Loop invariant: node is red. 195 */ 196 if (unlikely(!parent)) { 197 /* 198 * The inserted node is root. Either this is the first node, or 199 * we recursed at Case 1 below and are no longer violating 4). 200 */ 201 rb_set_parent_color(node, NULL, RB_BLACK); 202 break; 203 } 204 205 /* 206 * If there is a black parent, we are done. Otherwise, take some 207 * corrective action as, per 4), we don't want a red root or two 208 * consecutive red nodes. 209 */ 210 if (rb_is_black(parent)) { 211 break; 212 } 213 214 gparent = rb_red_parent(parent); 215 216 tmp = gparent->rb_right; 217 if (parent != tmp) { /* parent == gparent->rb_left */ 218 if (tmp && rb_is_red(tmp)) { 219 /* 220 * Case 1 - node's uncle is red (color flips). 221 * 222 * G g 223 * / \ / \ 224 * p u --> P U 225 * / / 226 * n n 227 * 228 * However, since g's parent might be red, and 4) does not 229 * allow this, we need to recurse at g. 230 */ 231 rb_set_parent_color(tmp, gparent, RB_BLACK); 232 rb_set_parent_color(parent, gparent, RB_BLACK); 233 node = gparent; 234 parent = rb_parent(node); 235 rb_set_parent_color(node, parent, RB_RED); 236 continue; 237 } 238 239 tmp = parent->rb_right; 240 if (node == tmp) { 241 /* 242 * Case 2 - node's uncle is black and node is 243 * the parent's right child (left rotate at parent). 244 * 245 * G G 246 * / \ / \ 247 * p U --> n U 248 * \ / 249 * n p 250 * 251 * This still leaves us in violation of 4), the 252 * continuation into Case 3 will fix that. 253 */ 254 tmp = node->rb_left; 255 qatomic_set(&parent->rb_right, tmp); 256 qatomic_set(&node->rb_left, parent); 257 if (tmp) { 258 rb_set_parent_color(tmp, parent, RB_BLACK); 259 } 260 rb_set_parent_color(parent, node, RB_RED); 261 augment->rotate(parent, node); 262 parent = node; 263 tmp = node->rb_right; 264 } 265 266 /* 267 * Case 3 - node's uncle is black and node is 268 * the parent's left child (right rotate at gparent). 269 * 270 * G P 271 * / \ / \ 272 * p U --> n g 273 * / \ 274 * n U 275 */ 276 qatomic_set(&gparent->rb_left, tmp); /* == parent->rb_right */ 277 qatomic_set(&parent->rb_right, gparent); 278 if (tmp) { 279 rb_set_parent_color(tmp, gparent, RB_BLACK); 280 } 281 rb_rotate_set_parents(gparent, parent, root, RB_RED); 282 augment->rotate(gparent, parent); 283 break; 284 } else { 285 tmp = gparent->rb_left; 286 if (tmp && rb_is_red(tmp)) { 287 /* Case 1 - color flips */ 288 rb_set_parent_color(tmp, gparent, RB_BLACK); 289 rb_set_parent_color(parent, gparent, RB_BLACK); 290 node = gparent; 291 parent = rb_parent(node); 292 rb_set_parent_color(node, parent, RB_RED); 293 continue; 294 } 295 296 tmp = parent->rb_left; 297 if (node == tmp) { 298 /* Case 2 - right rotate at parent */ 299 tmp = node->rb_right; 300 qatomic_set(&parent->rb_left, tmp); 301 qatomic_set(&node->rb_right, parent); 302 if (tmp) { 303 rb_set_parent_color(tmp, parent, RB_BLACK); 304 } 305 rb_set_parent_color(parent, node, RB_RED); 306 augment->rotate(parent, node); 307 parent = node; 308 tmp = node->rb_left; 309 } 310 311 /* Case 3 - left rotate at gparent */ 312 qatomic_set(&gparent->rb_right, tmp); /* == parent->rb_left */ 313 qatomic_set(&parent->rb_left, gparent); 314 if (tmp) { 315 rb_set_parent_color(tmp, gparent, RB_BLACK); 316 } 317 rb_rotate_set_parents(gparent, parent, root, RB_RED); 318 augment->rotate(gparent, parent); 319 break; 320 } 321 } 322 } 323 324 static void rb_insert_augmented_cached(RBNode *node, 325 RBRootLeftCached *root, bool newleft, 326 const RBAugmentCallbacks *augment) 327 { 328 if (newleft) { 329 root->rb_leftmost = node; 330 } 331 rb_insert_augmented(node, &root->rb_root, augment); 332 } 333 334 static void rb_erase_color(RBNode *parent, RBRoot *root, 335 const RBAugmentCallbacks *augment) 336 { 337 RBNode *node = NULL, *sibling, *tmp1, *tmp2; 338 339 while (true) { 340 /* 341 * Loop invariants: 342 * - node is black (or NULL on first iteration) 343 * - node is not the root (parent is not NULL) 344 * - All leaf paths going through parent and node have a 345 * black node count that is 1 lower than other leaf paths. 346 */ 347 sibling = parent->rb_right; 348 if (node != sibling) { /* node == parent->rb_left */ 349 if (rb_is_red(sibling)) { 350 /* 351 * Case 1 - left rotate at parent 352 * 353 * P S 354 * / \ / \ 355 * N s --> p Sr 356 * / \ / \ 357 * Sl Sr N Sl 358 */ 359 tmp1 = sibling->rb_left; 360 qatomic_set(&parent->rb_right, tmp1); 361 qatomic_set(&sibling->rb_left, parent); 362 rb_set_parent_color(tmp1, parent, RB_BLACK); 363 rb_rotate_set_parents(parent, sibling, root, RB_RED); 364 augment->rotate(parent, sibling); 365 sibling = tmp1; 366 } 367 tmp1 = sibling->rb_right; 368 if (!tmp1 || rb_is_black(tmp1)) { 369 tmp2 = sibling->rb_left; 370 if (!tmp2 || rb_is_black(tmp2)) { 371 /* 372 * Case 2 - sibling color flip 373 * (p could be either color here) 374 * 375 * (p) (p) 376 * / \ / \ 377 * N S --> N s 378 * / \ / \ 379 * Sl Sr Sl Sr 380 * 381 * This leaves us violating 5) which 382 * can be fixed by flipping p to black 383 * if it was red, or by recursing at p. 384 * p is red when coming from Case 1. 385 */ 386 rb_set_parent_color(sibling, parent, RB_RED); 387 if (rb_is_red(parent)) { 388 rb_set_black(parent); 389 } else { 390 node = parent; 391 parent = rb_parent(node); 392 if (parent) { 393 continue; 394 } 395 } 396 break; 397 } 398 /* 399 * Case 3 - right rotate at sibling 400 * (p could be either color here) 401 * 402 * (p) (p) 403 * / \ / \ 404 * N S --> N sl 405 * / \ \ 406 * sl Sr S 407 * \ 408 * Sr 409 * 410 * Note: p might be red, and then bot 411 * p and sl are red after rotation (which 412 * breaks property 4). This is fixed in 413 * Case 4 (in rb_rotate_set_parents() 414 * which set sl the color of p 415 * and set p RB_BLACK) 416 * 417 * (p) (sl) 418 * / \ / \ 419 * N sl --> P S 420 * \ / \ 421 * S N Sr 422 * \ 423 * Sr 424 */ 425 tmp1 = tmp2->rb_right; 426 qatomic_set(&sibling->rb_left, tmp1); 427 qatomic_set(&tmp2->rb_right, sibling); 428 qatomic_set(&parent->rb_right, tmp2); 429 if (tmp1) { 430 rb_set_parent_color(tmp1, sibling, RB_BLACK); 431 } 432 augment->rotate(sibling, tmp2); 433 tmp1 = sibling; 434 sibling = tmp2; 435 } 436 /* 437 * Case 4 - left rotate at parent + color flips 438 * (p and sl could be either color here. 439 * After rotation, p becomes black, s acquires 440 * p's color, and sl keeps its color) 441 * 442 * (p) (s) 443 * / \ / \ 444 * N S --> P Sr 445 * / \ / \ 446 * (sl) sr N (sl) 447 */ 448 tmp2 = sibling->rb_left; 449 qatomic_set(&parent->rb_right, tmp2); 450 qatomic_set(&sibling->rb_left, parent); 451 rb_set_parent_color(tmp1, sibling, RB_BLACK); 452 if (tmp2) { 453 rb_set_parent(tmp2, parent); 454 } 455 rb_rotate_set_parents(parent, sibling, root, RB_BLACK); 456 augment->rotate(parent, sibling); 457 break; 458 } else { 459 sibling = parent->rb_left; 460 if (rb_is_red(sibling)) { 461 /* Case 1 - right rotate at parent */ 462 tmp1 = sibling->rb_right; 463 qatomic_set(&parent->rb_left, tmp1); 464 qatomic_set(&sibling->rb_right, parent); 465 rb_set_parent_color(tmp1, parent, RB_BLACK); 466 rb_rotate_set_parents(parent, sibling, root, RB_RED); 467 augment->rotate(parent, sibling); 468 sibling = tmp1; 469 } 470 tmp1 = sibling->rb_left; 471 if (!tmp1 || rb_is_black(tmp1)) { 472 tmp2 = sibling->rb_right; 473 if (!tmp2 || rb_is_black(tmp2)) { 474 /* Case 2 - sibling color flip */ 475 rb_set_parent_color(sibling, parent, RB_RED); 476 if (rb_is_red(parent)) { 477 rb_set_black(parent); 478 } else { 479 node = parent; 480 parent = rb_parent(node); 481 if (parent) { 482 continue; 483 } 484 } 485 break; 486 } 487 /* Case 3 - left rotate at sibling */ 488 tmp1 = tmp2->rb_left; 489 qatomic_set(&sibling->rb_right, tmp1); 490 qatomic_set(&tmp2->rb_left, sibling); 491 qatomic_set(&parent->rb_left, tmp2); 492 if (tmp1) { 493 rb_set_parent_color(tmp1, sibling, RB_BLACK); 494 } 495 augment->rotate(sibling, tmp2); 496 tmp1 = sibling; 497 sibling = tmp2; 498 } 499 /* Case 4 - right rotate at parent + color flips */ 500 tmp2 = sibling->rb_right; 501 qatomic_set(&parent->rb_left, tmp2); 502 qatomic_set(&sibling->rb_right, parent); 503 rb_set_parent_color(tmp1, sibling, RB_BLACK); 504 if (tmp2) { 505 rb_set_parent(tmp2, parent); 506 } 507 rb_rotate_set_parents(parent, sibling, root, RB_BLACK); 508 augment->rotate(parent, sibling); 509 break; 510 } 511 } 512 } 513 514 static void rb_erase_augmented(RBNode *node, RBRoot *root, 515 const RBAugmentCallbacks *augment) 516 { 517 RBNode *child = node->rb_right; 518 RBNode *tmp = node->rb_left; 519 RBNode *parent, *rebalance; 520 uintptr_t pc; 521 522 if (!tmp) { 523 /* 524 * Case 1: node to erase has no more than 1 child (easy!) 525 * 526 * Note that if there is one child it must be red due to 5) 527 * and node must be black due to 4). We adjust colors locally 528 * so as to bypass rb_erase_color() later on. 529 */ 530 pc = node->rb_parent_color; 531 parent = rb_parent(node); 532 rb_change_child(node, child, parent, root); 533 if (child) { 534 child->rb_parent_color = pc; 535 rebalance = NULL; 536 } else { 537 rebalance = pc_is_black(pc) ? parent : NULL; 538 } 539 tmp = parent; 540 } else if (!child) { 541 /* Still case 1, but this time the child is node->rb_left */ 542 pc = node->rb_parent_color; 543 parent = rb_parent(node); 544 tmp->rb_parent_color = pc; 545 rb_change_child(node, tmp, parent, root); 546 rebalance = NULL; 547 tmp = parent; 548 } else { 549 RBNode *successor = child, *child2; 550 tmp = child->rb_left; 551 if (!tmp) { 552 /* 553 * Case 2: node's successor is its right child 554 * 555 * (n) (s) 556 * / \ / \ 557 * (x) (s) -> (x) (c) 558 * \ 559 * (c) 560 */ 561 parent = successor; 562 child2 = successor->rb_right; 563 564 augment->copy(node, successor); 565 } else { 566 /* 567 * Case 3: node's successor is leftmost under 568 * node's right child subtree 569 * 570 * (n) (s) 571 * / \ / \ 572 * (x) (y) -> (x) (y) 573 * / / 574 * (p) (p) 575 * / / 576 * (s) (c) 577 * \ 578 * (c) 579 */ 580 do { 581 parent = successor; 582 successor = tmp; 583 tmp = tmp->rb_left; 584 } while (tmp); 585 child2 = successor->rb_right; 586 qatomic_set(&parent->rb_left, child2); 587 qatomic_set(&successor->rb_right, child); 588 rb_set_parent(child, successor); 589 590 augment->copy(node, successor); 591 augment->propagate(parent, successor); 592 } 593 594 tmp = node->rb_left; 595 qatomic_set(&successor->rb_left, tmp); 596 rb_set_parent(tmp, successor); 597 598 pc = node->rb_parent_color; 599 tmp = rb_parent(node); 600 rb_change_child(node, successor, tmp, root); 601 602 if (child2) { 603 rb_set_parent_color(child2, parent, RB_BLACK); 604 rebalance = NULL; 605 } else { 606 rebalance = rb_is_black(successor) ? parent : NULL; 607 } 608 successor->rb_parent_color = pc; 609 tmp = successor; 610 } 611 612 augment->propagate(tmp, NULL); 613 614 if (rebalance) { 615 rb_erase_color(rebalance, root, augment); 616 } 617 } 618 619 static void rb_erase_augmented_cached(RBNode *node, RBRootLeftCached *root, 620 const RBAugmentCallbacks *augment) 621 { 622 if (root->rb_leftmost == node) { 623 root->rb_leftmost = rb_next(node); 624 } 625 rb_erase_augmented(node, &root->rb_root, augment); 626 } 627 628 629 /* 630 * Interval trees. 631 * 632 * Derived from lib/interval_tree.c and its dependencies, 633 * especially include/linux/interval_tree_generic.h. 634 */ 635 636 #define rb_to_itree(N) container_of(N, IntervalTreeNode, rb) 637 638 static bool interval_tree_compute_max(IntervalTreeNode *node, bool exit) 639 { 640 IntervalTreeNode *child; 641 uint64_t max = node->last; 642 643 if (node->rb.rb_left) { 644 child = rb_to_itree(node->rb.rb_left); 645 if (child->subtree_last > max) { 646 max = child->subtree_last; 647 } 648 } 649 if (node->rb.rb_right) { 650 child = rb_to_itree(node->rb.rb_right); 651 if (child->subtree_last > max) { 652 max = child->subtree_last; 653 } 654 } 655 if (exit && node->subtree_last == max) { 656 return true; 657 } 658 node->subtree_last = max; 659 return false; 660 } 661 662 static void interval_tree_propagate(RBNode *rb, RBNode *stop) 663 { 664 while (rb != stop) { 665 IntervalTreeNode *node = rb_to_itree(rb); 666 if (interval_tree_compute_max(node, true)) { 667 break; 668 } 669 rb = rb_parent(&node->rb); 670 } 671 } 672 673 static void interval_tree_copy(RBNode *rb_old, RBNode *rb_new) 674 { 675 IntervalTreeNode *old = rb_to_itree(rb_old); 676 IntervalTreeNode *new = rb_to_itree(rb_new); 677 678 new->subtree_last = old->subtree_last; 679 } 680 681 static void interval_tree_rotate(RBNode *rb_old, RBNode *rb_new) 682 { 683 IntervalTreeNode *old = rb_to_itree(rb_old); 684 IntervalTreeNode *new = rb_to_itree(rb_new); 685 686 new->subtree_last = old->subtree_last; 687 interval_tree_compute_max(old, false); 688 } 689 690 static const RBAugmentCallbacks interval_tree_augment = { 691 .propagate = interval_tree_propagate, 692 .copy = interval_tree_copy, 693 .rotate = interval_tree_rotate, 694 }; 695 696 /* Insert / remove interval nodes from the tree */ 697 void interval_tree_insert(IntervalTreeNode *node, IntervalTreeRoot *root) 698 { 699 RBNode **link = &root->rb_root.rb_node, *rb_parent = NULL; 700 uint64_t start = node->start, last = node->last; 701 IntervalTreeNode *parent; 702 bool leftmost = true; 703 704 while (*link) { 705 rb_parent = *link; 706 parent = rb_to_itree(rb_parent); 707 708 if (parent->subtree_last < last) { 709 parent->subtree_last = last; 710 } 711 if (start < parent->start) { 712 link = &parent->rb.rb_left; 713 } else { 714 link = &parent->rb.rb_right; 715 leftmost = false; 716 } 717 } 718 719 node->subtree_last = last; 720 rb_link_node(&node->rb, rb_parent, link); 721 rb_insert_augmented_cached(&node->rb, root, leftmost, 722 &interval_tree_augment); 723 } 724 725 void interval_tree_remove(IntervalTreeNode *node, IntervalTreeRoot *root) 726 { 727 rb_erase_augmented_cached(&node->rb, root, &interval_tree_augment); 728 } 729 730 /* 731 * Iterate over intervals intersecting [start;last] 732 * 733 * Note that a node's interval intersects [start;last] iff: 734 * Cond1: node->start <= last 735 * and 736 * Cond2: start <= node->last 737 */ 738 739 static IntervalTreeNode *interval_tree_subtree_search(IntervalTreeNode *node, 740 uint64_t start, 741 uint64_t last) 742 { 743 while (true) { 744 /* 745 * Loop invariant: start <= node->subtree_last 746 * (Cond2 is satisfied by one of the subtree nodes) 747 */ 748 if (node->rb.rb_left) { 749 IntervalTreeNode *left = rb_to_itree(node->rb.rb_left); 750 751 if (start <= left->subtree_last) { 752 /* 753 * Some nodes in left subtree satisfy Cond2. 754 * Iterate to find the leftmost such node N. 755 * If it also satisfies Cond1, that's the 756 * match we are looking for. Otherwise, there 757 * is no matching interval as nodes to the 758 * right of N can't satisfy Cond1 either. 759 */ 760 node = left; 761 continue; 762 } 763 } 764 if (node->start <= last) { /* Cond1 */ 765 if (start <= node->last) { /* Cond2 */ 766 return node; /* node is leftmost match */ 767 } 768 if (node->rb.rb_right) { 769 node = rb_to_itree(node->rb.rb_right); 770 if (start <= node->subtree_last) { 771 continue; 772 } 773 } 774 } 775 return NULL; /* no match */ 776 } 777 } 778 779 IntervalTreeNode *interval_tree_iter_first(IntervalTreeRoot *root, 780 uint64_t start, uint64_t last) 781 { 782 IntervalTreeNode *node, *leftmost; 783 784 if (!root->rb_root.rb_node) { 785 return NULL; 786 } 787 788 /* 789 * Fastpath range intersection/overlap between A: [a0, a1] and 790 * B: [b0, b1] is given by: 791 * 792 * a0 <= b1 && b0 <= a1 793 * 794 * ... where A holds the lock range and B holds the smallest 795 * 'start' and largest 'last' in the tree. For the later, we 796 * rely on the root node, which by augmented interval tree 797 * property, holds the largest value in its last-in-subtree. 798 * This allows mitigating some of the tree walk overhead for 799 * for non-intersecting ranges, maintained and consulted in O(1). 800 */ 801 node = rb_to_itree(root->rb_root.rb_node); 802 if (node->subtree_last < start) { 803 return NULL; 804 } 805 806 leftmost = rb_to_itree(root->rb_leftmost); 807 if (leftmost->start > last) { 808 return NULL; 809 } 810 811 return interval_tree_subtree_search(node, start, last); 812 } 813 814 IntervalTreeNode *interval_tree_iter_next(IntervalTreeNode *node, 815 uint64_t start, uint64_t last) 816 { 817 RBNode *rb = node->rb.rb_right, *prev; 818 819 while (true) { 820 /* 821 * Loop invariants: 822 * Cond1: node->start <= last 823 * rb == node->rb.rb_right 824 * 825 * First, search right subtree if suitable 826 */ 827 if (rb) { 828 IntervalTreeNode *right = rb_to_itree(rb); 829 830 if (start <= right->subtree_last) { 831 return interval_tree_subtree_search(right, start, last); 832 } 833 } 834 835 /* Move up the tree until we come from a node's left child */ 836 do { 837 rb = rb_parent(&node->rb); 838 if (!rb) { 839 return NULL; 840 } 841 prev = &node->rb; 842 node = rb_to_itree(rb); 843 rb = node->rb.rb_right; 844 } while (prev == rb); 845 846 /* Check if the node intersects [start;last] */ 847 if (last < node->start) { /* !Cond1 */ 848 return NULL; 849 } 850 if (start <= node->last) { /* Cond2 */ 851 return node; 852 } 853 } 854 } 855 856 /* Occasionally useful for calling from within the debugger. */ 857 #if 0 858 static void debug_interval_tree_int(IntervalTreeNode *node, 859 const char *dir, int level) 860 { 861 printf("%4d %*s %s [%" PRIu64 ",%" PRIu64 "] subtree_last:%" PRIu64 "\n", 862 level, level + 1, dir, rb_is_red(&node->rb) ? "r" : "b", 863 node->start, node->last, node->subtree_last); 864 865 if (node->rb.rb_left) { 866 debug_interval_tree_int(rb_to_itree(node->rb.rb_left), "<", level + 1); 867 } 868 if (node->rb.rb_right) { 869 debug_interval_tree_int(rb_to_itree(node->rb.rb_right), ">", level + 1); 870 } 871 } 872 873 void debug_interval_tree(IntervalTreeNode *node); 874 void debug_interval_tree(IntervalTreeNode *node) 875 { 876 if (node) { 877 debug_interval_tree_int(node, "*", 0); 878 } else { 879 printf("null\n"); 880 } 881 } 882 #endif 883