Lines Matching full:parent
67 * are left undone as of now. Nor did I check for loops involving parent
83 * - old's parent and color get assigned to new
84 * - old gets assigned new as a parent and 'color' as a color.
90 struct rb_node *parent = rb_parent(old); in __rb_rotate_set_parents() local
93 __rb_change_child(old, new, parent, root); in __rb_rotate_set_parents()
101 struct rb_node *parent = rb_red_parent(node), *gparent, *tmp; in __rb_insert() local
110 if (unlikely(!parent)) { in __rb_insert()
121 * If there is a black parent, we are done. in __rb_insert()
126 if(rb_is_black(parent)) in __rb_insert()
129 gparent = rb_red_parent(parent); in __rb_insert()
132 if (parent != tmp) { /* parent == gparent->rb_left */ in __rb_insert()
143 * However, since g's parent might be red, and in __rb_insert()
148 rb_set_parent_color(parent, gparent, RB_BLACK); in __rb_insert()
150 parent = rb_parent(node); in __rb_insert()
151 rb_set_parent_color(node, parent, RB_RED); in __rb_insert()
155 tmp = parent->rb_right; in __rb_insert()
159 * the parent's right child (left rotate at parent). in __rb_insert()
171 WRITE_ONCE(parent->rb_right, tmp); in __rb_insert()
172 WRITE_ONCE(node->rb_left, parent); in __rb_insert()
174 rb_set_parent_color(tmp, parent, in __rb_insert()
176 rb_set_parent_color(parent, node, RB_RED); in __rb_insert()
177 augment_rotate(parent, node); in __rb_insert()
178 parent = node; in __rb_insert()
184 * the parent's left child (right rotate at gparent). in __rb_insert()
192 WRITE_ONCE(gparent->rb_left, tmp); /* == parent->rb_right */ in __rb_insert()
193 WRITE_ONCE(parent->rb_right, gparent); in __rb_insert()
196 __rb_rotate_set_parents(gparent, parent, root, RB_RED); in __rb_insert()
197 augment_rotate(gparent, parent); in __rb_insert()
204 rb_set_parent_color(parent, gparent, RB_BLACK); in __rb_insert()
206 parent = rb_parent(node); in __rb_insert()
207 rb_set_parent_color(node, parent, RB_RED); in __rb_insert()
211 tmp = parent->rb_left; in __rb_insert()
213 /* Case 2 - right rotate at parent */ in __rb_insert()
215 WRITE_ONCE(parent->rb_left, tmp); in __rb_insert()
216 WRITE_ONCE(node->rb_right, parent); in __rb_insert()
218 rb_set_parent_color(tmp, parent, in __rb_insert()
220 rb_set_parent_color(parent, node, RB_RED); in __rb_insert()
221 augment_rotate(parent, node); in __rb_insert()
222 parent = node; in __rb_insert()
227 WRITE_ONCE(gparent->rb_right, tmp); /* == parent->rb_left */ in __rb_insert()
228 WRITE_ONCE(parent->rb_left, gparent); in __rb_insert()
231 __rb_rotate_set_parents(gparent, parent, root, RB_RED); in __rb_insert()
232 augment_rotate(gparent, parent); in __rb_insert()
243 ____rb_erase_color(struct rb_node *parent, struct rb_root *root, in ____rb_erase_color() argument
252 * - node is not the root (parent is not NULL) in ____rb_erase_color()
253 * - All leaf paths going through parent and node have a in ____rb_erase_color()
256 sibling = parent->rb_right; in ____rb_erase_color()
257 if (node != sibling) { /* node == parent->rb_left */ in ____rb_erase_color()
260 * Case 1 - left rotate at parent in ____rb_erase_color()
269 WRITE_ONCE(parent->rb_right, tmp1); in ____rb_erase_color()
270 WRITE_ONCE(sibling->rb_left, parent); in ____rb_erase_color()
271 rb_set_parent_color(tmp1, parent, RB_BLACK); in ____rb_erase_color()
272 __rb_rotate_set_parents(parent, sibling, root, in ____rb_erase_color()
274 augment_rotate(parent, sibling); in ____rb_erase_color()
296 rb_set_parent_color(sibling, parent, in ____rb_erase_color()
298 if (rb_is_red(parent)) in ____rb_erase_color()
299 rb_set_black(parent); in ____rb_erase_color()
301 node = parent; in ____rb_erase_color()
302 parent = rb_parent(node); in ____rb_erase_color()
303 if (parent) in ____rb_erase_color()
338 WRITE_ONCE(parent->rb_right, tmp2); in ____rb_erase_color()
347 * Case 4 - left rotate at parent + color flips in ____rb_erase_color()
359 WRITE_ONCE(parent->rb_right, tmp2); in ____rb_erase_color()
360 WRITE_ONCE(sibling->rb_left, parent); in ____rb_erase_color()
363 rb_set_parent(tmp2, parent); in ____rb_erase_color()
364 __rb_rotate_set_parents(parent, sibling, root, in ____rb_erase_color()
366 augment_rotate(parent, sibling); in ____rb_erase_color()
369 sibling = parent->rb_left; in ____rb_erase_color()
371 /* Case 1 - right rotate at parent */ in ____rb_erase_color()
373 WRITE_ONCE(parent->rb_left, tmp1); in ____rb_erase_color()
374 WRITE_ONCE(sibling->rb_right, parent); in ____rb_erase_color()
375 rb_set_parent_color(tmp1, parent, RB_BLACK); in ____rb_erase_color()
376 __rb_rotate_set_parents(parent, sibling, root, in ____rb_erase_color()
378 augment_rotate(parent, sibling); in ____rb_erase_color()
386 rb_set_parent_color(sibling, parent, in ____rb_erase_color()
388 if (rb_is_red(parent)) in ____rb_erase_color()
389 rb_set_black(parent); in ____rb_erase_color()
391 node = parent; in ____rb_erase_color()
392 parent = rb_parent(node); in ____rb_erase_color()
393 if (parent) in ____rb_erase_color()
402 WRITE_ONCE(parent->rb_left, tmp2); in ____rb_erase_color()
410 /* Case 4 - right rotate at parent + color flips */ in ____rb_erase_color()
412 WRITE_ONCE(parent->rb_left, tmp2); in ____rb_erase_color()
413 WRITE_ONCE(sibling->rb_right, parent); in ____rb_erase_color()
416 rb_set_parent(tmp2, parent); in ____rb_erase_color()
417 __rb_rotate_set_parents(parent, sibling, root, in ____rb_erase_color()
419 augment_rotate(parent, sibling); in ____rb_erase_color()
426 void __rb_erase_color(struct rb_node *parent, struct rb_root *root, in __rb_erase_color() argument
429 ____rb_erase_color(parent, root, augment_rotate); in __rb_erase_color()
530 struct rb_node *parent; in rb_next() local
548 * so any 'next' node must be in the general direction of our parent. in rb_next()
550 * parent, keep going up. First time it's a left-hand child of its in rb_next()
551 * parent, said parent is our 'next' node. in rb_next()
553 while ((parent = rb_parent(node)) && node == parent->rb_right) in rb_next()
554 node = parent; in rb_next()
556 return parent; in rb_next()
562 struct rb_node *parent; in rb_prev() local
580 * is a right-hand child of its parent. in rb_prev()
582 while ((parent = rb_parent(node)) && node == parent->rb_left) in rb_prev()
583 node = parent; in rb_prev()
585 return parent; in rb_prev()
592 struct rb_node *parent = rb_parent(victim); in rb_replace_node() local
602 __rb_change_child(victim, new, parent, root); in rb_replace_node()
619 struct rb_node *parent = rb_parent(victim); in rb_replace_node_rcu() local
630 /* Set the parent's pointer to the new node last after an RCU barrier in rb_replace_node_rcu()
634 __rb_change_child_rcu(victim, new, parent, root); in rb_replace_node_rcu()
652 const struct rb_node *parent; in rb_next_postorder() local
655 parent = rb_parent(node); in rb_next_postorder()
658 if (parent && node == parent->rb_left && parent->rb_right) { in rb_next_postorder()
659 /* If we are the parent's left node, go to the parent's right in rb_next_postorder()
661 return rb_left_deepest_node(parent->rb_right); in rb_next_postorder()
663 /* Otherwise we are the parent's right node, and the parent in rb_next_postorder()
665 return (struct rb_node *)parent; in rb_next_postorder()