Lines Matching full:node
20 * 1) A node is either red or black
23 * 4) Both children of every red node are black
28 * consecutive red nodes in a path and every red node is therefore followed by
60 void (*propagate)(RBNode *node, RBNode *stop);
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()
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()
166 * so any 'next' node must be in the general direction of our parent. 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()
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()
234 * Case 1 - node's uncle is red (color flips). 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()
254 if (node == tmp) { in rb_insert_augmented()
256 * Case 2 - node's uncle is black and node is in rb_insert_augmented()
268 tmp = node->rb_left; 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()
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()
311 if (node == tmp) { in rb_insert_augmented()
313 tmp = node->rb_right; 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()
338 static void rb_insert_augmented_cached(RBNode *node, 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()
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()
362 if (node != sibling) { /* node == parent->rb_left */ in rb_erase_color()
404 node = parent; in rb_erase_color()
405 parent = rb_parent(node); in rb_erase_color()
493 node = parent; in rb_erase_color()
494 parent = rb_parent(node); 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()
567 * Case 2: node's successor is its right child 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()
604 augment->copy(node, successor); in rb_erase_augmented()
608 tmp = node->rb_left; 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()
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()
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()
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()
711 void interval_tree_insert(IntervalTreeNode *node, IntervalTreeRoot *root) in interval_tree_insert() argument
714 uint64_t start = node->start, last = node->last; 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()
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()
798 IntervalTreeNode *node, *leftmost; in interval_tree_iter_first() local
812 * rely on the root node, which by augmented interval tree 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()
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()
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);