Lines Matching full:parent
50 * - old's parent and color get assigned to new
51 * - old gets assigned new as a parent and 'color' as a color.
57 struct rb_node *parent = rb_parent(old); in __rb_rotate_set_parents() local
60 __rb_change_child(old, new, parent, root); in __rb_rotate_set_parents()
67 struct rb_node *parent = rb_red_parent(node), *gparent, *tmp; in __rb_insert() local
73 * If there is a black parent, we are done. in __rb_insert()
77 if (!parent) { in __rb_insert()
80 } else if (rb_is_black(parent)) in __rb_insert()
83 gparent = rb_red_parent(parent); in __rb_insert()
86 if (parent != tmp) { /* parent == gparent->rb_left */ in __rb_insert()
97 * However, since g's parent might be red, and in __rb_insert()
102 rb_set_parent_color(parent, gparent, RB_BLACK); in __rb_insert()
104 parent = rb_parent(node); in __rb_insert()
105 rb_set_parent_color(node, parent, RB_RED); in __rb_insert()
109 tmp = parent->rb_right; in __rb_insert()
112 * Case 2 - left rotate at parent in __rb_insert()
123 parent->rb_right = tmp = node->rb_left; in __rb_insert()
124 node->rb_left = parent; in __rb_insert()
126 rb_set_parent_color(tmp, parent, in __rb_insert()
128 rb_set_parent_color(parent, node, RB_RED); in __rb_insert()
129 augment_rotate(parent, node); in __rb_insert()
130 parent = node; in __rb_insert()
143 gparent->rb_left = tmp; /* == parent->rb_right */ in __rb_insert()
144 parent->rb_right = gparent; in __rb_insert()
147 __rb_rotate_set_parents(gparent, parent, root, RB_RED); in __rb_insert()
148 augment_rotate(gparent, parent); in __rb_insert()
155 rb_set_parent_color(parent, gparent, RB_BLACK); in __rb_insert()
157 parent = rb_parent(node); in __rb_insert()
158 rb_set_parent_color(node, parent, RB_RED); in __rb_insert()
162 tmp = parent->rb_left; in __rb_insert()
164 /* Case 2 - right rotate at parent */ in __rb_insert()
165 parent->rb_left = tmp = node->rb_right; in __rb_insert()
166 node->rb_right = parent; in __rb_insert()
168 rb_set_parent_color(tmp, parent, in __rb_insert()
170 rb_set_parent_color(parent, node, RB_RED); in __rb_insert()
171 augment_rotate(parent, node); in __rb_insert()
172 parent = node; in __rb_insert()
177 gparent->rb_right = tmp; /* == parent->rb_left */ in __rb_insert()
178 parent->rb_left = gparent; in __rb_insert()
181 __rb_rotate_set_parents(gparent, parent, root, RB_RED); in __rb_insert()
182 augment_rotate(gparent, parent); in __rb_insert()
193 ____rb_erase_color(struct rb_node *parent, struct rb_root *root, in ____rb_erase_color() argument
202 * - node is not the root (parent is not NULL) in ____rb_erase_color()
203 * - All leaf paths going through parent and node have a in ____rb_erase_color()
206 sibling = parent->rb_right; in ____rb_erase_color()
207 if (node != sibling) { /* node == parent->rb_left */ in ____rb_erase_color()
210 * Case 1 - left rotate at parent in ____rb_erase_color()
218 parent->rb_right = tmp1 = sibling->rb_left; in ____rb_erase_color()
219 sibling->rb_left = parent; in ____rb_erase_color()
220 rb_set_parent_color(tmp1, parent, RB_BLACK); in ____rb_erase_color()
221 __rb_rotate_set_parents(parent, sibling, root, in ____rb_erase_color()
223 augment_rotate(parent, sibling); in ____rb_erase_color()
245 rb_set_parent_color(sibling, parent, in ____rb_erase_color()
247 if (rb_is_red(parent)) in ____rb_erase_color()
248 rb_set_black(parent); in ____rb_erase_color()
250 node = parent; in ____rb_erase_color()
251 parent = rb_parent(node); in ____rb_erase_color()
252 if (parent) in ____rb_erase_color()
271 parent->rb_right = tmp2; in ____rb_erase_color()
280 * Case 4 - left rotate at parent + color flips in ____rb_erase_color()
291 parent->rb_right = tmp2 = sibling->rb_left; in ____rb_erase_color()
292 sibling->rb_left = parent; in ____rb_erase_color()
295 rb_set_parent(tmp2, parent); in ____rb_erase_color()
296 __rb_rotate_set_parents(parent, sibling, root, in ____rb_erase_color()
298 augment_rotate(parent, sibling); in ____rb_erase_color()
301 sibling = parent->rb_left; in ____rb_erase_color()
303 /* Case 1 - right rotate at parent */ in ____rb_erase_color()
304 parent->rb_left = tmp1 = sibling->rb_right; in ____rb_erase_color()
305 sibling->rb_right = parent; in ____rb_erase_color()
306 rb_set_parent_color(tmp1, parent, RB_BLACK); in ____rb_erase_color()
307 __rb_rotate_set_parents(parent, sibling, root, in ____rb_erase_color()
309 augment_rotate(parent, sibling); in ____rb_erase_color()
317 rb_set_parent_color(sibling, parent, in ____rb_erase_color()
319 if (rb_is_red(parent)) in ____rb_erase_color()
320 rb_set_black(parent); in ____rb_erase_color()
322 node = parent; in ____rb_erase_color()
323 parent = rb_parent(node); in ____rb_erase_color()
324 if (parent) in ____rb_erase_color()
332 parent->rb_left = tmp2; in ____rb_erase_color()
340 /* Case 4 - left rotate at parent + color flips */ in ____rb_erase_color()
341 parent->rb_left = tmp2 = sibling->rb_right; in ____rb_erase_color()
342 sibling->rb_right = parent; in ____rb_erase_color()
345 rb_set_parent(tmp2, parent); in ____rb_erase_color()
346 __rb_rotate_set_parents(parent, sibling, root, in ____rb_erase_color()
348 augment_rotate(parent, sibling); in ____rb_erase_color()
355 void __rb_erase_color(struct rb_node *parent, struct rb_root *root, in __rb_erase_color() argument
358 ____rb_erase_color(parent, root, augment_rotate); in __rb_erase_color()
437 struct rb_node *parent; in rb_next() local
455 * so any 'next' node must be in the general direction of our parent. in rb_next()
457 * parent, keep going up. First time it's a left-hand child of its in rb_next()
458 * parent, said parent is our 'next' node. in rb_next()
460 while ((parent = rb_parent(node)) && node == parent->rb_right) in rb_next()
461 node = parent; in rb_next()
463 return parent; in rb_next()
469 struct rb_node *parent; in rb_prev() local
487 * is a right-hand child of its parent. in rb_prev()
489 while ((parent = rb_parent(node)) && node == parent->rb_left) in rb_prev()
490 node = parent; in rb_prev()
492 return parent; in rb_prev()
499 struct rb_node *parent = rb_parent(victim); in rb_replace_node() local
502 __rb_change_child(victim, new, parent, root); in rb_replace_node()
527 const struct rb_node *parent; in rb_next_postorder() local
530 parent = rb_parent(node); in rb_next_postorder()
533 if (parent && node == parent->rb_left && parent->rb_right) { in rb_next_postorder()
534 /* If we are the parent's left node, go to the parent's right in rb_next_postorder()
536 return rb_left_deepest_node(parent->rb_right); in rb_next_postorder()
538 /* Otherwise we are the parent's right node, and the parent in rb_next_postorder()
540 return (struct rb_node *)parent; in rb_next_postorder()