Lines Matching +full:root +full:- +full:node
1 /* SPDX-License-Identifier: GPL-2.0-or-later */
4 #include "qemu/interval-tree.h"
10 * For now, don't expose Linux Red-Black Trees separately, but retain the
18 * red-black trees properties: https://en.wikipedia.org/wiki/Rbtree
20 * 1) A node is either red or black
21 * 2) The root is black
23 * 4) Both children of every red node are black
24 * 5) Every simple path from root to leaves contains the same number
28 * consecutive red nodes in a path and every red node is therefore followed by
42 * These two requirements will allow lockless iteration of the tree -- not
47 * and that it will indeed complete -- does not get stuck in a loop.
60 void (*propagate)(RBNode *node, RBNode *stop);
67 return qatomic_read(&n->rb_parent_color); in rb_pc()
72 qatomic_set(&n->rb_parent_color, pc); in rb_set_pc()
135 static inline void rb_link_node(RBNode *node, RBNode *parent, RBNode **rb_link) in rb_link_node() argument
137 node->rb_parent_color = (uintptr_t)parent; in rb_link_node()
138 node->rb_left = node->rb_right = NULL; in rb_link_node()
141 * Ensure that node is initialized before insertion, in rb_link_node()
144 qatomic_set_mb(rb_link, node); in rb_link_node()
147 static RBNode *rb_next(RBNode *node) in rb_next() argument
151 /* OMIT: if empty node, return null. */ in rb_next()
154 * If we have a right-hand child, go down and then left as far as we can. in rb_next()
156 if (node->rb_right) { in rb_next()
157 node = node->rb_right; in rb_next()
158 while (node->rb_left) { in rb_next()
159 node = node->rb_left; in rb_next()
161 return node; in rb_next()
165 * No right-hand children. Everything down and left is smaller than us, in rb_next()
166 * so any 'next' node must be in the general direction of our parent. in rb_next()
167 * Go up the tree; any time the ancestor is a right-hand child of its in rb_next()
168 * parent, keep going up. First time it's a left-hand child of its in rb_next()
169 * parent, said parent is our 'next' node. in rb_next()
171 while ((parent = rb_parent(node)) && node == parent->rb_right) { in rb_next()
172 node = parent; in rb_next()
179 RBNode *parent, RBRoot *root) in rb_change_child() argument
182 qatomic_set(&root->rb_node, new); in rb_change_child()
183 } else if (parent->rb_left == old) { in rb_change_child()
184 qatomic_set(&parent->rb_left, new); in rb_change_child()
186 qatomic_set(&parent->rb_right, new); in rb_change_child()
191 RBRoot *root, RBColor color) in rb_rotate_set_parents() argument
198 rb_change_child(old, new, parent, root); in rb_rotate_set_parents()
201 static void rb_insert_augmented(RBNode *node, RBRoot *root, in rb_insert_augmented() argument
204 RBNode *parent = rb_red_parent(node), *gparent, *tmp; in rb_insert_augmented()
208 * Loop invariant: node is red. in rb_insert_augmented()
212 * The inserted node is root. Either this is the first node, or in rb_insert_augmented()
215 rb_set_parent_color(node, NULL, RB_BLACK); in rb_insert_augmented()
221 * corrective action as, per 4), we don't want a red root or two in rb_insert_augmented()
230 tmp = gparent->rb_right; in rb_insert_augmented()
231 if (parent != tmp) { /* parent == gparent->rb_left */ in rb_insert_augmented()
234 * Case 1 - node's uncle is red (color flips). in rb_insert_augmented()
238 * p u --> P U in rb_insert_augmented()
247 node = gparent; in rb_insert_augmented()
248 parent = rb_parent(node); in rb_insert_augmented()
249 rb_set_parent_color(node, parent, RB_RED); in rb_insert_augmented()
253 tmp = parent->rb_right; in rb_insert_augmented()
254 if (node == tmp) { in rb_insert_augmented()
256 * Case 2 - node's uncle is black and node is in rb_insert_augmented()
261 * p U --> n U in rb_insert_augmented()
268 tmp = node->rb_left; in rb_insert_augmented()
269 qatomic_set(&parent->rb_right, tmp); in rb_insert_augmented()
270 qatomic_set(&node->rb_left, parent); in rb_insert_augmented()
274 rb_set_parent_color(parent, node, RB_RED); in rb_insert_augmented()
275 augment->rotate(parent, node); in rb_insert_augmented()
276 parent = node; in rb_insert_augmented()
277 tmp = node->rb_right; in rb_insert_augmented()
281 * Case 3 - node's uncle is black and node is in rb_insert_augmented()
286 * p U --> n g in rb_insert_augmented()
290 qatomic_set(&gparent->rb_left, tmp); /* == parent->rb_right */ in rb_insert_augmented()
291 qatomic_set(&parent->rb_right, gparent); in rb_insert_augmented()
295 rb_rotate_set_parents(gparent, parent, root, RB_RED); in rb_insert_augmented()
296 augment->rotate(gparent, parent); in rb_insert_augmented()
299 tmp = gparent->rb_left; in rb_insert_augmented()
301 /* Case 1 - color flips */ in rb_insert_augmented()
304 node = gparent; in rb_insert_augmented()
305 parent = rb_parent(node); in rb_insert_augmented()
306 rb_set_parent_color(node, parent, RB_RED); in rb_insert_augmented()
310 tmp = parent->rb_left; in rb_insert_augmented()
311 if (node == tmp) { in rb_insert_augmented()
312 /* Case 2 - right rotate at parent */ in rb_insert_augmented()
313 tmp = node->rb_right; in rb_insert_augmented()
314 qatomic_set(&parent->rb_left, tmp); in rb_insert_augmented()
315 qatomic_set(&node->rb_right, parent); in rb_insert_augmented()
319 rb_set_parent_color(parent, node, RB_RED); in rb_insert_augmented()
320 augment->rotate(parent, node); in rb_insert_augmented()
321 parent = node; in rb_insert_augmented()
322 tmp = node->rb_left; in rb_insert_augmented()
325 /* Case 3 - left rotate at gparent */ in rb_insert_augmented()
326 qatomic_set(&gparent->rb_right, tmp); /* == parent->rb_left */ in rb_insert_augmented()
327 qatomic_set(&parent->rb_left, gparent); in rb_insert_augmented()
331 rb_rotate_set_parents(gparent, parent, root, RB_RED); in rb_insert_augmented()
332 augment->rotate(gparent, parent); in rb_insert_augmented()
338 static void rb_insert_augmented_cached(RBNode *node, in rb_insert_augmented_cached() argument
339 RBRootLeftCached *root, bool newleft, in rb_insert_augmented_cached() argument
343 root->rb_leftmost = node; in rb_insert_augmented_cached()
345 rb_insert_augmented(node, &root->rb_root, augment); in rb_insert_augmented_cached()
348 static void rb_erase_color(RBNode *parent, RBRoot *root, in rb_erase_color() argument
351 RBNode *node = NULL, *sibling, *tmp1, *tmp2; in rb_erase_color() local
356 * - node is black (or NULL on first iteration) in rb_erase_color()
357 * - node is not the root (parent is not NULL) in rb_erase_color()
358 * - All leaf paths going through parent and node have a in rb_erase_color()
359 * black node count that is 1 lower than other leaf paths. in rb_erase_color()
361 sibling = parent->rb_right; in rb_erase_color()
362 if (node != sibling) { /* node == parent->rb_left */ in rb_erase_color()
365 * Case 1 - left rotate at parent in rb_erase_color()
369 * N s --> p Sr in rb_erase_color()
373 tmp1 = sibling->rb_left; in rb_erase_color()
374 qatomic_set(&parent->rb_right, tmp1); in rb_erase_color()
375 qatomic_set(&sibling->rb_left, parent); in rb_erase_color()
377 rb_rotate_set_parents(parent, sibling, root, RB_RED); in rb_erase_color()
378 augment->rotate(parent, sibling); in rb_erase_color()
381 tmp1 = sibling->rb_right; in rb_erase_color()
383 tmp2 = sibling->rb_left; in rb_erase_color()
386 * Case 2 - sibling color flip in rb_erase_color()
391 * N S --> N s in rb_erase_color()
404 node = parent; in rb_erase_color()
405 parent = rb_parent(node); in rb_erase_color()
413 * Case 3 - right rotate at sibling in rb_erase_color()
418 * N S --> N sl in rb_erase_color()
433 * N sl --> P S in rb_erase_color()
439 tmp1 = tmp2->rb_right; in rb_erase_color()
440 qatomic_set(&sibling->rb_left, tmp1); in rb_erase_color()
441 qatomic_set(&tmp2->rb_right, sibling); in rb_erase_color()
442 qatomic_set(&parent->rb_right, tmp2); in rb_erase_color()
446 augment->rotate(sibling, tmp2); in rb_erase_color()
451 * Case 4 - left rotate at parent + color flips in rb_erase_color()
458 * N S --> P Sr in rb_erase_color()
462 tmp2 = sibling->rb_left; in rb_erase_color()
463 qatomic_set(&parent->rb_right, tmp2); in rb_erase_color()
464 qatomic_set(&sibling->rb_left, parent); in rb_erase_color()
469 rb_rotate_set_parents(parent, sibling, root, RB_BLACK); in rb_erase_color()
470 augment->rotate(parent, sibling); in rb_erase_color()
473 sibling = parent->rb_left; in rb_erase_color()
475 /* Case 1 - right rotate at parent */ in rb_erase_color()
476 tmp1 = sibling->rb_right; in rb_erase_color()
477 qatomic_set(&parent->rb_left, tmp1); in rb_erase_color()
478 qatomic_set(&sibling->rb_right, parent); in rb_erase_color()
480 rb_rotate_set_parents(parent, sibling, root, RB_RED); in rb_erase_color()
481 augment->rotate(parent, sibling); in rb_erase_color()
484 tmp1 = sibling->rb_left; in rb_erase_color()
486 tmp2 = sibling->rb_right; in rb_erase_color()
488 /* Case 2 - sibling color flip */ in rb_erase_color()
493 node = parent; in rb_erase_color()
494 parent = rb_parent(node); in rb_erase_color()
501 /* Case 3 - left rotate at sibling */ in rb_erase_color()
502 tmp1 = tmp2->rb_left; in rb_erase_color()
503 qatomic_set(&sibling->rb_right, tmp1); in rb_erase_color()
504 qatomic_set(&tmp2->rb_left, sibling); in rb_erase_color()
505 qatomic_set(&parent->rb_left, tmp2); in rb_erase_color()
509 augment->rotate(sibling, tmp2); in rb_erase_color()
513 /* Case 4 - right rotate at parent + color flips */ in rb_erase_color()
514 tmp2 = sibling->rb_right; in rb_erase_color()
515 qatomic_set(&parent->rb_left, tmp2); in rb_erase_color()
516 qatomic_set(&sibling->rb_right, parent); in rb_erase_color()
521 rb_rotate_set_parents(parent, sibling, root, RB_BLACK); in rb_erase_color()
522 augment->rotate(parent, sibling); in rb_erase_color()
528 static void rb_erase_augmented(RBNode *node, RBRoot *root, in rb_erase_augmented() argument
531 RBNode *child = node->rb_right; in rb_erase_augmented()
532 RBNode *tmp = node->rb_left; in rb_erase_augmented()
538 * Case 1: node to erase has no more than 1 child (easy!) in rb_erase_augmented()
541 * and node must be black due to 4). We adjust colors locally in rb_erase_augmented()
544 pc = rb_pc(node); in rb_erase_augmented()
546 rb_change_child(node, child, parent, root); in rb_erase_augmented()
555 /* Still case 1, but this time the child is node->rb_left */ in rb_erase_augmented()
556 pc = rb_pc(node); in rb_erase_augmented()
559 rb_change_child(node, tmp, parent, root); in rb_erase_augmented()
564 tmp = child->rb_left; in rb_erase_augmented()
567 * Case 2: node's successor is its right child in rb_erase_augmented()
571 * (x) (s) -> (x) (c) in rb_erase_augmented()
576 child2 = successor->rb_right; in rb_erase_augmented()
578 augment->copy(node, successor); in rb_erase_augmented()
581 * Case 3: node's successor is leftmost under in rb_erase_augmented()
582 * node's right child subtree in rb_erase_augmented()
586 * (x) (y) -> (x) (y) in rb_erase_augmented()
597 tmp = tmp->rb_left; in rb_erase_augmented()
599 child2 = successor->rb_right; in rb_erase_augmented()
600 qatomic_set(&parent->rb_left, child2); in rb_erase_augmented()
601 qatomic_set(&successor->rb_right, child); in rb_erase_augmented()
604 augment->copy(node, successor); in rb_erase_augmented()
605 augment->propagate(parent, successor); in rb_erase_augmented()
608 tmp = node->rb_left; in rb_erase_augmented()
609 qatomic_set(&successor->rb_left, tmp); in rb_erase_augmented()
612 pc = rb_pc(node); in rb_erase_augmented()
614 rb_change_child(node, successor, tmp, root); in rb_erase_augmented()
626 augment->propagate(tmp, NULL); in rb_erase_augmented()
629 rb_erase_color(rebalance, root, augment); in rb_erase_augmented()
633 static void rb_erase_augmented_cached(RBNode *node, RBRootLeftCached *root, in rb_erase_augmented_cached() argument
636 if (root->rb_leftmost == node) { in rb_erase_augmented_cached()
637 root->rb_leftmost = rb_next(node); in rb_erase_augmented_cached()
639 rb_erase_augmented(node, &root->rb_root, augment); in rb_erase_augmented_cached()
652 static bool interval_tree_compute_max(IntervalTreeNode *node, bool exit) in interval_tree_compute_max() argument
655 uint64_t max = node->last; in interval_tree_compute_max()
657 if (node->rb.rb_left) { in interval_tree_compute_max()
658 child = rb_to_itree(node->rb.rb_left); in interval_tree_compute_max()
659 if (child->subtree_last > max) { in interval_tree_compute_max()
660 max = child->subtree_last; in interval_tree_compute_max()
663 if (node->rb.rb_right) { in interval_tree_compute_max()
664 child = rb_to_itree(node->rb.rb_right); in interval_tree_compute_max()
665 if (child->subtree_last > max) { in interval_tree_compute_max()
666 max = child->subtree_last; in interval_tree_compute_max()
669 if (exit && node->subtree_last == max) { in interval_tree_compute_max()
672 node->subtree_last = max; in interval_tree_compute_max()
679 IntervalTreeNode *node = rb_to_itree(rb); in interval_tree_propagate() local
680 if (interval_tree_compute_max(node, true)) { in interval_tree_propagate()
683 rb = rb_parent(&node->rb); in interval_tree_propagate()
692 new->subtree_last = old->subtree_last; in interval_tree_copy()
700 new->subtree_last = old->subtree_last; in interval_tree_rotate()
711 void interval_tree_insert(IntervalTreeNode *node, IntervalTreeRoot *root) in interval_tree_insert() argument
713 RBNode **link = &root->rb_root.rb_node, *rb_parent = NULL; in interval_tree_insert()
714 uint64_t start = node->start, last = node->last; in interval_tree_insert()
722 if (parent->subtree_last < last) { in interval_tree_insert()
723 parent->subtree_last = last; in interval_tree_insert()
725 if (start < parent->start) { in interval_tree_insert()
726 link = &parent->rb.rb_left; in interval_tree_insert()
728 link = &parent->rb.rb_right; in interval_tree_insert()
733 node->subtree_last = last; in interval_tree_insert()
734 rb_link_node(&node->rb, rb_parent, link); in interval_tree_insert()
735 rb_insert_augmented_cached(&node->rb, root, leftmost, in interval_tree_insert()
739 void interval_tree_remove(IntervalTreeNode *node, IntervalTreeRoot *root) in interval_tree_remove() argument
741 rb_erase_augmented_cached(&node->rb, root, &interval_tree_augment); in interval_tree_remove()
747 * Note that a node's interval intersects [start;last] iff:
748 * Cond1: node->start <= last
750 * Cond2: start <= node->last
753 static IntervalTreeNode *interval_tree_subtree_search(IntervalTreeNode *node, in interval_tree_subtree_search() argument
759 * Loop invariant: start <= node->subtree_last in interval_tree_subtree_search()
762 RBNode *tmp = qatomic_read(&node->rb.rb_left); in interval_tree_subtree_search()
766 if (start <= left->subtree_last) { in interval_tree_subtree_search()
769 * Iterate to find the leftmost such node N. in interval_tree_subtree_search()
775 node = left; in interval_tree_subtree_search()
779 if (node->start <= last) { /* Cond1 */ in interval_tree_subtree_search()
780 if (start <= node->last) { /* Cond2 */ in interval_tree_subtree_search()
781 return node; /* node is leftmost match */ in interval_tree_subtree_search()
783 tmp = qatomic_read(&node->rb.rb_right); in interval_tree_subtree_search()
785 node = rb_to_itree(tmp); in interval_tree_subtree_search()
786 if (start <= node->subtree_last) { in interval_tree_subtree_search()
795 IntervalTreeNode *interval_tree_iter_first(IntervalTreeRoot *root, in interval_tree_iter_first() argument
798 IntervalTreeNode *node, *leftmost; in interval_tree_iter_first() local
800 if (!root || !root->rb_root.rb_node) { in interval_tree_iter_first()
812 * rely on the root node, which by augmented interval tree in interval_tree_iter_first()
813 * property, holds the largest value in its last-in-subtree. in interval_tree_iter_first()
815 * for non-intersecting ranges, maintained and consulted in O(1). in interval_tree_iter_first()
817 node = rb_to_itree(root->rb_root.rb_node); in interval_tree_iter_first()
818 if (node->subtree_last < start) { in interval_tree_iter_first()
822 leftmost = rb_to_itree(root->rb_leftmost); in interval_tree_iter_first()
823 if (leftmost->start > last) { in interval_tree_iter_first()
827 return interval_tree_subtree_search(node, start, last); in interval_tree_iter_first()
830 IntervalTreeNode *interval_tree_iter_next(IntervalTreeNode *node, in interval_tree_iter_next() argument
835 rb = qatomic_read(&node->rb.rb_right); in interval_tree_iter_next()
839 * Cond1: node->start <= last in interval_tree_iter_next()
840 * rb == node->rb.rb_right in interval_tree_iter_next()
847 if (start <= right->subtree_last) { in interval_tree_iter_next()
852 /* Move up the tree until we come from a node's left child */ in interval_tree_iter_next()
854 rb = rb_parent(&node->rb); in interval_tree_iter_next()
858 prev = &node->rb; in interval_tree_iter_next()
859 node = rb_to_itree(rb); in interval_tree_iter_next()
860 rb = qatomic_read(&node->rb.rb_right); in interval_tree_iter_next()
863 /* Check if the node intersects [start;last] */ in interval_tree_iter_next()
864 if (last < node->start) { /* !Cond1 */ in interval_tree_iter_next()
867 if (start <= node->last) { /* Cond2 */ in interval_tree_iter_next()
868 return node; in interval_tree_iter_next()
875 static void debug_interval_tree_int(IntervalTreeNode *node,
879 level, level + 1, dir, rb_is_red(&node->rb) ? "r" : "b",
880 node->start, node->last, node->subtree_last);
882 if (node->rb.rb_left) {
883 debug_interval_tree_int(rb_to_itree(node->rb.rb_left), "<", level + 1);
885 if (node->rb.rb_right) {
886 debug_interval_tree_int(rb_to_itree(node->rb.rb_right), ">", level + 1);
890 void debug_interval_tree(IntervalTreeNode *node);
891 void debug_interval_tree(IntervalTreeNode *node)
893 if (node) {
894 debug_interval_tree_int(node, "*", 0);