Lines Matching refs:parent
82 struct rb_node *parent, struct rb_root *root) in __rb_change_child() argument
84 if (parent) { in __rb_change_child()
85 if (parent->rb_left == old) in __rb_change_child()
86 parent->rb_left = new; in __rb_change_child()
88 parent->rb_right = new; in __rb_change_child()
102 struct rb_node *parent = rb_parent(old); in __rb_rotate_set_parents() local
105 __rb_change_child(old, new, parent, root); in __rb_rotate_set_parents()
110 struct rb_node *parent = rb_red_parent(node), *gparent, *tmp; in rb_insert_color() local
120 if (!parent) { in rb_insert_color()
123 } else if (rb_is_black(parent)) in rb_insert_color()
126 gparent = rb_red_parent(parent); in rb_insert_color()
129 if (parent != tmp) { /* parent == gparent->rb_left */ in rb_insert_color()
145 rb_set_parent_color(parent, gparent, RB_BLACK); in rb_insert_color()
147 parent = rb_parent(node); in rb_insert_color()
148 rb_set_parent_color(node, parent, RB_RED); in rb_insert_color()
152 tmp = parent->rb_right; in rb_insert_color()
166 parent->rb_right = tmp = node->rb_left; in rb_insert_color()
167 node->rb_left = parent; in rb_insert_color()
169 rb_set_parent_color(tmp, parent, in rb_insert_color()
171 rb_set_parent_color(parent, node, RB_RED); in rb_insert_color()
172 parent = node; in rb_insert_color()
186 parent->rb_right = gparent; in rb_insert_color()
189 __rb_rotate_set_parents(gparent, parent, root, RB_RED); in rb_insert_color()
196 rb_set_parent_color(parent, gparent, RB_BLACK); in rb_insert_color()
198 parent = rb_parent(node); in rb_insert_color()
199 rb_set_parent_color(node, parent, RB_RED); in rb_insert_color()
203 tmp = parent->rb_left; in rb_insert_color()
206 parent->rb_left = tmp = node->rb_right; in rb_insert_color()
207 node->rb_right = parent; in rb_insert_color()
209 rb_set_parent_color(tmp, parent, in rb_insert_color()
211 rb_set_parent_color(parent, node, RB_RED); in rb_insert_color()
212 parent = node; in rb_insert_color()
218 parent->rb_left = gparent; in rb_insert_color()
221 __rb_rotate_set_parents(gparent, parent, root, RB_RED); in rb_insert_color()
228 static void __rb_erase_color(struct rb_node *parent, struct rb_root *root) in __rb_erase_color() argument
240 sibling = parent->rb_right; in __rb_erase_color()
252 parent->rb_right = tmp1 = sibling->rb_left; in __rb_erase_color()
253 sibling->rb_left = parent; in __rb_erase_color()
254 rb_set_parent_color(tmp1, parent, RB_BLACK); in __rb_erase_color()
255 __rb_rotate_set_parents(parent, sibling, root, in __rb_erase_color()
278 rb_set_parent_color(sibling, parent, in __rb_erase_color()
280 if (rb_is_red(parent)) in __rb_erase_color()
281 rb_set_black(parent); in __rb_erase_color()
283 node = parent; in __rb_erase_color()
284 parent = rb_parent(node); in __rb_erase_color()
285 if (parent) in __rb_erase_color()
304 parent->rb_right = tmp2; in __rb_erase_color()
323 parent->rb_right = tmp2 = sibling->rb_left; in __rb_erase_color()
324 sibling->rb_left = parent; in __rb_erase_color()
327 rb_set_parent(tmp2, parent); in __rb_erase_color()
328 __rb_rotate_set_parents(parent, sibling, root, in __rb_erase_color()
332 sibling = parent->rb_left; in __rb_erase_color()
335 parent->rb_left = tmp1 = sibling->rb_right; in __rb_erase_color()
336 sibling->rb_right = parent; in __rb_erase_color()
337 rb_set_parent_color(tmp1, parent, RB_BLACK); in __rb_erase_color()
338 __rb_rotate_set_parents(parent, sibling, root, in __rb_erase_color()
347 rb_set_parent_color(sibling, parent, in __rb_erase_color()
349 if (rb_is_red(parent)) in __rb_erase_color()
350 rb_set_black(parent); in __rb_erase_color()
352 node = parent; in __rb_erase_color()
353 parent = rb_parent(node); in __rb_erase_color()
354 if (parent) in __rb_erase_color()
362 parent->rb_left = tmp2; in __rb_erase_color()
370 parent->rb_left = tmp2 = sibling->rb_right; in __rb_erase_color()
371 sibling->rb_right = parent; in __rb_erase_color()
374 rb_set_parent(tmp2, parent); in __rb_erase_color()
375 __rb_rotate_set_parents(parent, sibling, root, in __rb_erase_color()
385 struct rb_node *parent, *rebalance; in rb_erase() local
397 parent = __rb_parent(pc); in rb_erase()
398 __rb_change_child(node, child, parent, root); in rb_erase()
403 rebalance = __rb_is_black(pc) ? parent : NULL; in rb_erase()
407 parent = __rb_parent(pc); in rb_erase()
408 __rb_change_child(node, tmp, parent, root); in rb_erase()
423 parent = child; in rb_erase()
441 parent = successor; in rb_erase()
445 parent->rb_left = child2 = successor->rb_right; in rb_erase()
458 rb_set_parent_color(child2, parent, RB_BLACK); in rb_erase()
463 rebalance = __rb_is_black(pc2) ? parent : NULL; in rb_erase()
503 struct rb_node *parent; in rb_next() local
526 while ((parent = rb_parent(node)) && node == parent->rb_right) in rb_next()
527 node = parent; in rb_next()
529 return parent; in rb_next()
535 struct rb_node *parent; in rb_prev() local
555 while ((parent = rb_parent(node)) && node == parent->rb_left) in rb_prev()
556 node = parent; in rb_prev()
558 return parent; in rb_prev()
565 struct rb_node *parent = rb_parent(victim); in rb_replace_node() local
568 __rb_change_child(victim, new, parent, root); in rb_replace_node()