Lines Matching defs:parent
55 * are left undone as of now. Nor did I check for loops involving parent
71 * - old's parent and color get assigned to new
72 * - old gets assigned new as a parent and 'color' as a color.
78 struct rb_node *parent = rb_parent(old);
81 __rb_change_child(old, new, parent, root);
88 struct rb_node *parent = rb_red_parent(node), *gparent, *tmp;
94 if (unlikely(!parent)) {
105 * If there is a black parent, we are done.
110 if(rb_is_black(parent))
113 gparent = rb_red_parent(parent);
116 if (parent != tmp) { /* parent == gparent->rb_left */
127 * However, since g's parent might be red, and
132 rb_set_parent_color(parent, gparent, RB_BLACK);
134 parent = rb_parent(node);
135 rb_set_parent_color(node, parent, RB_RED);
139 tmp = parent->rb_right;
143 * the parent's right child (left rotate at parent).
155 WRITE_ONCE(parent->rb_right, tmp);
156 WRITE_ONCE(node->rb_left, parent);
158 rb_set_parent_color(tmp, parent,
160 rb_set_parent_color(parent, node, RB_RED);
161 augment_rotate(parent, node);
162 parent = node;
168 * the parent's left child (right rotate at gparent).
176 WRITE_ONCE(gparent->rb_left, tmp); /* == parent->rb_right */
177 WRITE_ONCE(parent->rb_right, gparent);
180 __rb_rotate_set_parents(gparent, parent, root, RB_RED);
181 augment_rotate(gparent, parent);
188 rb_set_parent_color(parent, gparent, RB_BLACK);
190 parent = rb_parent(node);
191 rb_set_parent_color(node, parent, RB_RED);
195 tmp = parent->rb_left;
197 /* Case 2 - right rotate at parent */
199 WRITE_ONCE(parent->rb_left, tmp);
200 WRITE_ONCE(node->rb_right, parent);
202 rb_set_parent_color(tmp, parent,
204 rb_set_parent_color(parent, node, RB_RED);
205 augment_rotate(parent, node);
206 parent = node;
211 WRITE_ONCE(gparent->rb_right, tmp); /* == parent->rb_left */
212 WRITE_ONCE(parent->rb_left, gparent);
215 __rb_rotate_set_parents(gparent, parent, root, RB_RED);
216 augment_rotate(gparent, parent);
227 ____rb_erase_color(struct rb_node *parent, struct rb_root *root,
236 * - node is not the root (parent is not NULL)
237 * - All leaf paths going through parent and node have a
240 sibling = parent->rb_right;
241 if (node != sibling) { /* node == parent->rb_left */
244 * Case 1 - left rotate at parent
253 WRITE_ONCE(parent->rb_right, tmp1);
254 WRITE_ONCE(sibling->rb_left, parent);
255 rb_set_parent_color(tmp1, parent, RB_BLACK);
256 __rb_rotate_set_parents(parent, sibling, root,
258 augment_rotate(parent, sibling);
280 rb_set_parent_color(sibling, parent,
282 if (rb_is_red(parent))
283 rb_set_black(parent);
285 node = parent;
286 parent = rb_parent(node);
287 if (parent)
322 WRITE_ONCE(parent->rb_right, tmp2);
331 * Case 4 - left rotate at parent + color flips
343 WRITE_ONCE(parent->rb_right, tmp2);
344 WRITE_ONCE(sibling->rb_left, parent);
347 rb_set_parent(tmp2, parent);
348 __rb_rotate_set_parents(parent, sibling, root,
350 augment_rotate(parent, sibling);
353 sibling = parent->rb_left;
355 /* Case 1 - right rotate at parent */
357 WRITE_ONCE(parent->rb_left, tmp1);
358 WRITE_ONCE(sibling->rb_right, parent);
359 rb_set_parent_color(tmp1, parent, RB_BLACK);
360 __rb_rotate_set_parents(parent, sibling, root,
362 augment_rotate(parent, sibling);
370 rb_set_parent_color(sibling, parent,
372 if (rb_is_red(parent))
373 rb_set_black(parent);
375 node = parent;
376 parent = rb_parent(node);
377 if (parent)
386 WRITE_ONCE(parent->rb_left, tmp2);
394 /* Case 4 - right rotate at parent + color flips */
396 WRITE_ONCE(parent->rb_left, tmp2);
397 WRITE_ONCE(sibling->rb_right, parent);
400 rb_set_parent(tmp2, parent);
401 __rb_rotate_set_parents(parent, sibling, root,
403 augment_rotate(parent, sibling);
410 void __rb_erase_color(struct rb_node *parent, struct rb_root *root,
413 ____rb_erase_color(parent, root, augment_rotate);
488 struct rb_node *parent;
506 * so any 'next' node must be in the general direction of our parent.
508 * parent, keep going up. First time it's a left-hand child of its
509 * parent, said parent is our 'next' node.
511 while ((parent = rb_parent(node)) && node == parent->rb_right)
512 node = parent;
514 return parent;
519 struct rb_node *parent;
537 * is a right-hand child of its parent.
539 while ((parent = rb_parent(node)) && node == parent->rb_left)
540 node = parent;
542 return parent;
548 struct rb_node *parent = rb_parent(victim);
558 __rb_change_child(victim, new, parent, root);
575 const struct rb_node *parent;
578 parent = rb_parent(node);
581 if (parent && node == parent->rb_left && parent->rb_right) {
582 /* If we are the parent's left node, go to the parent's right
584 return rb_left_deepest_node(parent->rb_right);
586 /* Otherwise we are the parent's right node, and the parent
588 return (struct rb_node *)parent;