Lines Matching +full:parent +full:- +full:child
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
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.
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()
149 RBNode *parent; in rb_next() local
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()
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()
175 return parent; in rb_next()
179 RBNode *parent, RBRoot *root) in rb_change_child() argument
181 if (!parent) { in rb_change_child()
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()
194 RBNode *parent = pc_parent(pc); in rb_rotate_set_parents() local
198 rb_change_child(old, new, parent, root); in rb_rotate_set_parents()
204 RBNode *parent = rb_red_parent(node), *gparent, *tmp; in rb_insert_augmented() local
210 if (unlikely(!parent)) { in rb_insert_augmented()
220 * If there is a black parent, we are done. Otherwise, take some in rb_insert_augmented()
224 if (rb_is_black(parent)) { in rb_insert_augmented()
228 gparent = rb_red_parent(parent); 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()
242 * However, since g's parent might be red, and 4) does not in rb_insert_augmented()
246 rb_set_parent_color(parent, gparent, RB_BLACK); 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()
256 * Case 2 - node's uncle is black and node is in rb_insert_augmented()
257 * the parent's right child (left rotate at parent). 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()
272 rb_set_parent_color(tmp, parent, RB_BLACK); 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()
282 * the parent's left child (right rotate at gparent). 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()
303 rb_set_parent_color(parent, gparent, RB_BLACK); 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()
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()
317 rb_set_parent_color(tmp, parent, RB_BLACK); 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()
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
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()
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()
376 rb_set_parent_color(tmp1, parent, RB_BLACK); 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()
400 rb_set_parent_color(sibling, parent, RB_RED); in rb_erase_color()
401 if (rb_is_red(parent)) { in rb_erase_color()
402 rb_set_black(parent); in rb_erase_color()
404 node = parent; in rb_erase_color()
405 parent = rb_parent(node); in rb_erase_color()
406 if (parent) { 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()
467 rb_set_parent(tmp2, 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()
479 rb_set_parent_color(tmp1, parent, RB_BLACK); 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()
489 rb_set_parent_color(sibling, parent, RB_RED); in rb_erase_color()
490 if (rb_is_red(parent)) { in rb_erase_color()
491 rb_set_black(parent); in rb_erase_color()
493 node = parent; in rb_erase_color()
494 parent = rb_parent(node); in rb_erase_color()
495 if (parent) { 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()
519 rb_set_parent(tmp2, 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()
531 RBNode *child = node->rb_right; in rb_erase_augmented() local
532 RBNode *tmp = node->rb_left; in rb_erase_augmented()
533 RBNode *parent, *rebalance; in rb_erase_augmented() local
538 * Case 1: node to erase has no more than 1 child (easy!) in rb_erase_augmented()
540 * Note that if there is one child it must be red due to 5) in rb_erase_augmented()
545 parent = pc_parent(pc); in rb_erase_augmented()
546 rb_change_child(node, child, parent, root); in rb_erase_augmented()
547 if (child) { in rb_erase_augmented()
548 rb_set_pc(child, pc); in rb_erase_augmented()
551 rebalance = pc_is_black(pc) ? parent : NULL; in rb_erase_augmented()
553 tmp = parent; in rb_erase_augmented()
554 } else if (!child) { in rb_erase_augmented()
555 /* Still case 1, but this time the child is node->rb_left */ in rb_erase_augmented()
557 parent = pc_parent(pc); in rb_erase_augmented()
559 rb_change_child(node, tmp, parent, root); in rb_erase_augmented()
561 tmp = parent; in rb_erase_augmented()
563 RBNode *successor = child, *child2; 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()
575 parent = successor; in rb_erase_augmented()
576 child2 = successor->rb_right; in rb_erase_augmented()
578 augment->copy(node, successor); in rb_erase_augmented()
582 * node's right child subtree in rb_erase_augmented()
586 * (x) (y) -> (x) (y) in rb_erase_augmented()
595 parent = successor; 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()
602 rb_set_parent(child, successor); 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()
617 rb_set_parent_color(child2, parent, RB_BLACK); in rb_erase_augmented()
620 rebalance = rb_is_black(successor) ? parent : NULL; in rb_erase_augmented()
626 augment->propagate(tmp, NULL); in rb_erase_augmented()
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()
654 IntervalTreeNode *child; in interval_tree_compute_max() local
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()
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()
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()
715 IntervalTreeNode *parent; in interval_tree_insert() local
720 parent = rb_to_itree(rb_parent); 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()
741 rb_erase_augmented_cached(&node->rb, root, &interval_tree_augment); in interval_tree_remove()
748 * Cond1: node->start <= last
750 * Cond2: start <= node->last
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()
779 if (node->start <= last) { /* Cond1 */ in interval_tree_subtree_search()
780 if (start <= node->last) { /* Cond2 */ in interval_tree_subtree_search()
783 tmp = qatomic_read(&node->rb.rb_right); in interval_tree_subtree_search()
786 if (start <= node->subtree_last) { in interval_tree_subtree_search()
800 if (!root || !root->rb_root.rb_node) { 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()
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()
860 rb = qatomic_read(&node->rb.rb_right); 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()
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);