Lines Matching full:parent
28 struct rb_node *parent = ext2fs_rb_parent(node); in __rb_rotate_left() local
34 ext2fs_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 = ext2fs_rb_parent(node); in __rb_rotate_right() local
57 ext2fs_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 ext2fs_rb_insert_color() local
75 while ((parent = ext2fs_rb_parent(node)) && ext2fs_rb_is_red(parent)) in ext2fs_rb_insert_color()
77 gparent = ext2fs_rb_parent(parent); in ext2fs_rb_insert_color()
79 if (parent == gparent->rb_left) in ext2fs_rb_insert_color()
86 ext2fs_rb_set_black(parent); in ext2fs_rb_insert_color()
93 if (parent->rb_right == node) in ext2fs_rb_insert_color()
96 __rb_rotate_left(parent, root); in ext2fs_rb_insert_color()
97 tmp = parent; in ext2fs_rb_insert_color()
98 parent = node; in ext2fs_rb_insert_color()
102 ext2fs_rb_set_black(parent); in ext2fs_rb_insert_color()
111 ext2fs_rb_set_black(parent); in ext2fs_rb_insert_color()
118 if (parent->rb_left == node) in ext2fs_rb_insert_color()
121 __rb_rotate_right(parent, root); in ext2fs_rb_insert_color()
122 tmp = parent; in ext2fs_rb_insert_color()
123 parent = node; in ext2fs_rb_insert_color()
127 ext2fs_rb_set_black(parent); in ext2fs_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 ext2fs_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 = ext2fs_rb_parent(node); in __rb_erase_color()
167 other = parent->rb_right; in __rb_erase_color()
169 ext2fs_rb_set_color(other, ext2fs_rb_color(parent)); in __rb_erase_color()
170 ext2fs_rb_set_black(parent); in __rb_erase_color()
172 __rb_rotate_left(parent, root); in __rb_erase_color()
179 other = parent->rb_left; in __rb_erase_color()
183 ext2fs_rb_set_red(parent); in __rb_erase_color()
184 __rb_rotate_right(parent, root); in __rb_erase_color()
185 other = parent->rb_left; in __rb_erase_color()
191 node = parent; in __rb_erase_color()
192 parent = ext2fs_rb_parent(node); in __rb_erase_color()
201 other = parent->rb_left; in __rb_erase_color()
203 ext2fs_rb_set_color(other, ext2fs_rb_color(parent)); in __rb_erase_color()
204 ext2fs_rb_set_black(parent); in __rb_erase_color()
206 __rb_rotate_right(parent, root); in __rb_erase_color()
218 struct rb_node *child, *parent; in ext2fs_rb_erase() local
242 parent = ext2fs_rb_parent(node); in ext2fs_rb_erase()
245 if (parent == old) { in ext2fs_rb_erase()
246 parent = node; in ext2fs_rb_erase()
249 ext2fs_rb_set_parent(child, parent); in ext2fs_rb_erase()
250 parent->rb_left = child; in ext2fs_rb_erase()
263 parent = ext2fs_rb_parent(node); in ext2fs_rb_erase()
267 ext2fs_rb_set_parent(child, parent); in ext2fs_rb_erase()
268 if (parent) in ext2fs_rb_erase()
270 if (parent->rb_left == node) in ext2fs_rb_erase()
271 parent->rb_left = child; in ext2fs_rb_erase()
273 parent->rb_right = child; in ext2fs_rb_erase()
280 __rb_erase_color(child, parent, root); in ext2fs_rb_erase()
285 struct rb_node *parent; in ext2fs_rb_augment_path() local
289 parent = ext2fs_rb_parent(node); in ext2fs_rb_augment_path()
290 if (!parent) in ext2fs_rb_augment_path()
293 if (node == parent->rb_left && parent->rb_right) in ext2fs_rb_augment_path()
294 func(parent->rb_right, data); in ext2fs_rb_augment_path()
295 else if (parent->rb_left) in ext2fs_rb_augment_path()
296 func(parent->rb_left, data); in ext2fs_rb_augment_path()
298 node = parent; in ext2fs_rb_augment_path()
380 struct rb_node *parent; in ext2fs_rb_next() local
396 direction of our parent. Go up the tree; any time the in ext2fs_rb_next()
397 ancestor is a right-hand child of its parent, keep going in ext2fs_rb_next()
398 up. First time it's a left-hand child of its parent, said in ext2fs_rb_next()
399 parent is our 'next' node. */ in ext2fs_rb_next()
400 while ((parent = ext2fs_rb_parent(node)) && node == parent->rb_right) in ext2fs_rb_next()
401 node = parent; in ext2fs_rb_next()
403 return parent; in ext2fs_rb_next()
408 struct rb_node *parent; in ext2fs_rb_prev() local
423 is a right-hand child of its parent */ in ext2fs_rb_prev()
424 while ((parent = ext2fs_rb_parent(node)) && node == parent->rb_left) in ext2fs_rb_prev()
425 node = parent; in ext2fs_rb_prev()
427 return parent; in ext2fs_rb_prev()
433 struct rb_node *parent = ext2fs_rb_parent(victim); in ext2fs_rb_replace_node() local
436 if (parent) { in ext2fs_rb_replace_node()
437 if (victim == parent->rb_left) in ext2fs_rb_replace_node()
438 parent->rb_left = new; in ext2fs_rb_replace_node()
440 parent->rb_right = new; in ext2fs_rb_replace_node()