Lines Matching refs:node
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()
144 qatomic_set_mb(rb_link, node); in rb_link_node()
147 static RBNode *rb_next(RBNode *node) in rb_next() argument
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()
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()
215 rb_set_parent_color(node, NULL, RB_BLACK); 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()
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()
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
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()
544 pc = rb_pc(node); in rb_erase_augmented()
546 rb_change_child(node, child, parent, root); 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()
578 augment->copy(node, successor); 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()
753 static IntervalTreeNode *interval_tree_subtree_search(IntervalTreeNode *node, in interval_tree_subtree_search() argument
762 RBNode *tmp = qatomic_read(&node->rb.rb_left); 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
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()
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()
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);