Lines Matching refs:node
26 static void __rb_rotate_left(struct rb_node *node, struct rb_root *root) in __rb_rotate_left() argument
28 struct rb_node *right = node->rb_right; in __rb_rotate_left()
29 struct rb_node *parent = rb_parent(node); in __rb_rotate_left()
31 if ((node->rb_right = right->rb_left)) in __rb_rotate_left()
32 rb_set_parent(right->rb_left, node); in __rb_rotate_left()
33 right->rb_left = node; in __rb_rotate_left()
39 if (node == parent->rb_left) in __rb_rotate_left()
46 rb_set_parent(node, right); in __rb_rotate_left()
49 static void __rb_rotate_right(struct rb_node *node, struct rb_root *root) in __rb_rotate_right() argument
51 struct rb_node *left = node->rb_left; in __rb_rotate_right()
52 struct rb_node *parent = rb_parent(node); in __rb_rotate_right()
54 if ((node->rb_left = left->rb_right)) in __rb_rotate_right()
55 rb_set_parent(left->rb_right, node); in __rb_rotate_right()
56 left->rb_right = node; in __rb_rotate_right()
62 if (node == parent->rb_right) in __rb_rotate_right()
69 rb_set_parent(node, left); in __rb_rotate_right()
72 void rb_insert_color(struct rb_node *node, struct rb_root *root) in rb_insert_color() argument
76 while ((parent = rb_parent(node)) && rb_is_red(parent)) in rb_insert_color()
89 node = gparent; in rb_insert_color()
94 if (parent->rb_right == node) in rb_insert_color()
99 parent = node; in rb_insert_color()
100 node = tmp; in rb_insert_color()
114 node = gparent; in rb_insert_color()
119 if (parent->rb_left == node) in rb_insert_color()
124 parent = node; in rb_insert_color()
125 node = tmp; in rb_insert_color()
138 static void __rb_erase_color(struct rb_node *node, struct rb_node *parent, in __rb_erase_color() argument
143 while ((!node || rb_is_black(node)) && node != root->rb_node) in __rb_erase_color()
145 if (parent->rb_left == node) in __rb_erase_color()
159 node = parent; in __rb_erase_color()
160 parent = rb_parent(node); in __rb_erase_color()
175 node = root->rb_node; in __rb_erase_color()
193 node = parent; in __rb_erase_color()
194 parent = rb_parent(node); in __rb_erase_color()
209 node = root->rb_node; in __rb_erase_color()
214 if (node) in __rb_erase_color()
215 rb_set_black(node); in __rb_erase_color()
218 void rb_erase(struct rb_node *node, struct rb_root *root) in rb_erase() argument
223 if (!node->rb_left) in rb_erase()
224 child = node->rb_right; in rb_erase()
225 else if (!node->rb_right) in rb_erase()
226 child = node->rb_left; in rb_erase()
229 struct rb_node *old = node, *left; in rb_erase()
231 node = node->rb_right; in rb_erase()
232 while ((left = node->rb_left) != NULL) in rb_erase()
233 node = left; in rb_erase()
237 rb_parent(old)->rb_left = node; in rb_erase()
239 rb_parent(old)->rb_right = node; in rb_erase()
241 root->rb_node = node; in rb_erase()
243 child = node->rb_right; in rb_erase()
244 parent = rb_parent(node); in rb_erase()
245 color = rb_color(node); in rb_erase()
248 parent = node; in rb_erase()
254 node->rb_right = old->rb_right; in rb_erase()
255 rb_set_parent(old->rb_right, node); in rb_erase()
258 node->rb_parent_color = old->rb_parent_color; in rb_erase()
259 node->rb_left = old->rb_left; in rb_erase()
260 rb_set_parent(old->rb_left, node); in rb_erase()
265 parent = rb_parent(node); in rb_erase()
266 color = rb_color(node); in rb_erase()
272 if (parent->rb_left == node) in rb_erase()
286 static void rb_augment_path(struct rb_node *node, rb_augment_f func, void *data) in rb_augment_path() argument
291 func(node, data); in rb_augment_path()
292 parent = rb_parent(node); in rb_augment_path()
296 if (node == parent->rb_left && parent->rb_right) in rb_augment_path()
301 node = parent; in rb_augment_path()
309 void rb_augment_insert(struct rb_node *node, rb_augment_f func, void *data) in rb_augment_insert() argument
311 if (node->rb_left) in rb_augment_insert()
312 node = node->rb_left; in rb_augment_insert()
313 else if (node->rb_right) in rb_augment_insert()
314 node = node->rb_right; in rb_augment_insert()
316 rb_augment_path(node, func, data); in rb_augment_insert()
323 struct rb_node *rb_augment_erase_begin(struct rb_node *node) in rb_augment_erase_begin() argument
327 if (!node->rb_right && !node->rb_left) in rb_augment_erase_begin()
328 deepest = rb_parent(node); in rb_augment_erase_begin()
329 else if (!node->rb_right) in rb_augment_erase_begin()
330 deepest = node->rb_left; in rb_augment_erase_begin()
331 else if (!node->rb_left) in rb_augment_erase_begin()
332 deepest = node->rb_right; in rb_augment_erase_begin()
334 deepest = rb_next(node); in rb_augment_erase_begin()
337 else if (rb_parent(deepest) != node) in rb_augment_erase_begin()
348 void rb_augment_erase_end(struct rb_node *node, rb_augment_f func, void *data) in rb_augment_erase_end() argument
350 if (node) in rb_augment_erase_end()
351 rb_augment_path(node, func, data); in rb_augment_erase_end()
383 struct rb_node *rb_next(const struct rb_node *node) in rb_next() argument
387 if (rb_parent(node) == node) in rb_next()
392 if (node->rb_right) { in rb_next()
393 node = node->rb_right; in rb_next()
394 while (node->rb_left) in rb_next()
395 node=node->rb_left; in rb_next()
396 return (struct rb_node *)node; in rb_next()
405 while ((parent = rb_parent(node)) && node == parent->rb_right) in rb_next()
406 node = parent; in rb_next()
412 struct rb_node *rb_prev(const struct rb_node *node) in rb_prev() argument
416 if (rb_parent(node) == node) in rb_prev()
421 if (node->rb_left) { in rb_prev()
422 node = node->rb_left; in rb_prev()
423 while (node->rb_right) in rb_prev()
424 node=node->rb_right; in rb_prev()
425 return (struct rb_node *)node; in rb_prev()
430 while ((parent = rb_parent(node)) && node == parent->rb_left) in rb_prev()
431 node = parent; in rb_prev()