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()
149     RBNode *parent;  in rb_next()  local
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()
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()
224         if (rb_is_black(parent)) {  in rb_insert_augmented()
228         gparent = rb_red_parent(parent);  in rb_insert_augmented()
231         if (parent != tmp) {    /* parent == gparent->rb_left */  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()
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()
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()
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()
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()
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()
348 static void rb_erase_color(RBNode *parent, RBRoot *root,  in rb_erase_color()  argument
361         sibling = parent->rb_right;  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()
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()
442                 qatomic_set(&parent->rb_right, tmp2);  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()
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()
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()
505                 qatomic_set(&parent->rb_left, tmp2);  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()
533     RBNode *parent, *rebalance;  in rb_erase_augmented()  local
545         parent = pc_parent(pc);  in rb_erase_augmented()
546         rb_change_child(node, child, parent, root);  in rb_erase_augmented()
551             rebalance = pc_is_black(pc) ? parent : NULL;  in rb_erase_augmented()
553         tmp = parent;  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()
575             parent = successor;  in rb_erase_augmented()
595                 parent = successor;  in rb_erase_augmented()
600             qatomic_set(&parent->rb_left, child2);  in rb_erase_augmented()
605             augment->propagate(parent, successor);  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()
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()