Lines Matching full:parent
28 struct rb_node *parent = rb_parent(node); in __rb_rotate_left() local
34 rb_set_parent(right, parent); in __rb_rotate_left()
36 if (parent) in __rb_rotate_left()
38 if (node == parent->rb_left) in __rb_rotate_left()
39 parent->rb_left = right; in __rb_rotate_left()
41 parent->rb_right = right; in __rb_rotate_left()
51 struct rb_node *parent = rb_parent(node); in __rb_rotate_right() local
57 rb_set_parent(left, parent); in __rb_rotate_right()
59 if (parent) in __rb_rotate_right()
61 if (node == parent->rb_right) in __rb_rotate_right()
62 parent->rb_right = left; in __rb_rotate_right()
64 parent->rb_left = left; in __rb_rotate_right()
73 struct rb_node *parent, *gparent; in rb_insert_color() local
75 while ((parent = rb_parent(node)) && rb_is_red(parent)) in rb_insert_color()
77 gparent = rb_parent(parent); in rb_insert_color()
79 if (parent == gparent->rb_left) in rb_insert_color()
86 rb_set_black(parent); in rb_insert_color()
93 if (parent->rb_right == node) in rb_insert_color()
96 __rb_rotate_left(parent, root); in rb_insert_color()
97 tmp = parent; in rb_insert_color()
98 parent = node; in rb_insert_color()
102 rb_set_black(parent); in rb_insert_color()
111 rb_set_black(parent); in rb_insert_color()
118 if (parent->rb_left == node) in rb_insert_color()
121 __rb_rotate_right(parent, root); in rb_insert_color()
122 tmp = parent; in rb_insert_color()
123 parent = node; in rb_insert_color()
127 rb_set_black(parent); in rb_insert_color()
136 static void __rb_erase_color(struct rb_node *node, struct rb_node *parent, in __rb_erase_color() argument
143 if (parent->rb_left == node) in __rb_erase_color()
145 other = parent->rb_right; in __rb_erase_color()
149 rb_set_red(parent); in __rb_erase_color()
150 __rb_rotate_left(parent, root); in __rb_erase_color()
151 other = parent->rb_right; in __rb_erase_color()
157 node = parent; in __rb_erase_color()
158 parent = rb_parent(node); in __rb_erase_color()
169 other = parent->rb_right; in __rb_erase_color()
171 rb_set_color(other, rb_color(parent)); in __rb_erase_color()
172 rb_set_black(parent); in __rb_erase_color()
175 __rb_rotate_left(parent, root); in __rb_erase_color()
182 other = parent->rb_left; in __rb_erase_color()
186 rb_set_red(parent); in __rb_erase_color()
187 __rb_rotate_right(parent, root); in __rb_erase_color()
188 other = parent->rb_left; in __rb_erase_color()
194 node = parent; in __rb_erase_color()
195 parent = rb_parent(node); in __rb_erase_color()
206 other = parent->rb_left; in __rb_erase_color()
208 rb_set_color(other, rb_color(parent)); in __rb_erase_color()
209 rb_set_black(parent); in __rb_erase_color()
212 __rb_rotate_right(parent, root); in __rb_erase_color()
224 struct rb_node *child, *parent; in rb_erase() local
239 parent = rb_parent(node); in rb_erase()
243 rb_set_parent(child, parent); in rb_erase()
244 if (parent == old) { in rb_erase()
245 parent->rb_right = child; in rb_erase()
246 parent = node; in rb_erase()
248 parent->rb_left = child; in rb_erase()
269 parent = rb_parent(node); in rb_erase()
273 rb_set_parent(child, parent); in rb_erase()
274 if (parent) in rb_erase()
276 if (parent->rb_left == node) in rb_erase()
277 parent->rb_left = child; in rb_erase()
279 parent->rb_right = child; in rb_erase()
286 __rb_erase_color(child, parent, root); in rb_erase()
318 struct rb_node *parent; in rb_next() local
334 direction of our parent. Go up the tree; any time the in rb_next()
335 ancestor is a right-hand child of its parent, keep going in rb_next()
336 up. First time it's a left-hand child of its parent, said in rb_next()
337 parent is our 'next' node. */ in rb_next()
338 while ((parent = rb_parent(node)) && node == parent->rb_right) in rb_next()
339 node = parent; in rb_next()
341 return parent; in rb_next()
346 struct rb_node *parent; in rb_prev() local
361 is a right-hand child of its parent */ in rb_prev()
362 while ((parent = rb_parent(node)) && node == parent->rb_left) in rb_prev()
363 node = parent; in rb_prev()
365 return parent; in rb_prev()
371 struct rb_node *parent = rb_parent(victim); in rb_replace_node() local
374 if (parent) { in rb_replace_node()
375 if (victim == parent->rb_left) in rb_replace_node()
376 parent->rb_left = new; in rb_replace_node()
378 parent->rb_right = new; in rb_replace_node()