Lines Matching refs:node
63 __rb_insert(struct rb_node *node, struct rb_root *root, in __rb_insert() argument
66 struct rb_node *parent = rb_red_parent(node), *gparent, *tmp; in __rb_insert()
77 rb_set_parent_color(node, NULL, RB_BLACK); in __rb_insert()
102 node = gparent; in __rb_insert()
103 parent = rb_parent(node); in __rb_insert()
104 rb_set_parent_color(node, parent, RB_RED); in __rb_insert()
109 if (node == tmp) { in __rb_insert()
122 parent->rb_right = tmp = node->rb_left; in __rb_insert()
123 node->rb_left = parent; in __rb_insert()
127 rb_set_parent_color(parent, node, RB_RED); in __rb_insert()
128 augment_rotate(parent, node); in __rb_insert()
129 parent = node; in __rb_insert()
130 tmp = node->rb_right; in __rb_insert()
155 node = gparent; in __rb_insert()
156 parent = rb_parent(node); in __rb_insert()
157 rb_set_parent_color(node, parent, RB_RED); in __rb_insert()
162 if (node == tmp) { in __rb_insert()
164 parent->rb_left = tmp = node->rb_right; in __rb_insert()
165 node->rb_right = parent; in __rb_insert()
169 rb_set_parent_color(parent, node, RB_RED); in __rb_insert()
170 augment_rotate(parent, node); in __rb_insert()
171 parent = node; in __rb_insert()
172 tmp = node->rb_left; in __rb_insert()
195 struct rb_node *node = NULL, *sibling, *tmp1, *tmp2; in ____rb_erase_color() local
206 if (node != sibling) { /* node == parent->rb_left */ in ____rb_erase_color()
249 node = parent; in ____rb_erase_color()
250 parent = rb_parent(node); in ____rb_erase_color()
321 node = parent; in ____rb_erase_color()
322 parent = rb_parent(node); in ____rb_erase_color()
368 static inline void dummy_propagate(struct rb_node *node, struct rb_node *stop) {} in dummy_propagate() argument
376 void rb_insert_color(struct rb_node *node, struct rb_root *root) in rb_insert_color() argument
378 __rb_insert(node, root, dummy_rotate); in rb_insert_color()
382 void rb_erase(struct rb_node *node, struct rb_root *root) in rb_erase() argument
385 rebalance = __rb_erase_augmented(node, root, &dummy_callbacks); in rb_erase()
398 void __rb_insert_augmented(struct rb_node *node, struct rb_root *root, in __rb_insert_augmented() argument
401 __rb_insert(node, root, augment_rotate); in __rb_insert_augmented()
434 struct rb_node *rb_next(const struct rb_node *node) in rb_next() argument
438 if (RB_EMPTY_NODE(node)) in rb_next()
445 if (node->rb_right) { in rb_next()
446 node = node->rb_right; in rb_next()
447 while (node->rb_left) in rb_next()
448 node=node->rb_left; in rb_next()
449 return (struct rb_node *)node; in rb_next()
459 while ((parent = rb_parent(node)) && node == parent->rb_right) in rb_next()
460 node = parent; in rb_next()
466 struct rb_node *rb_prev(const struct rb_node *node) in rb_prev() argument
470 if (RB_EMPTY_NODE(node)) in rb_prev()
477 if (node->rb_left) { in rb_prev()
478 node = node->rb_left; in rb_prev()
479 while (node->rb_right) in rb_prev()
480 node=node->rb_right; in rb_prev()
481 return (struct rb_node *)node; in rb_prev()
488 while ((parent = rb_parent(node)) && node == parent->rb_left) in rb_prev()
489 node = parent; in rb_prev()
512 static struct rb_node *rb_left_deepest_node(const struct rb_node *node) in rb_left_deepest_node() argument
515 if (node->rb_left) in rb_left_deepest_node()
516 node = node->rb_left; in rb_left_deepest_node()
517 else if (node->rb_right) in rb_left_deepest_node()
518 node = node->rb_right; in rb_left_deepest_node()
520 return (struct rb_node *)node; in rb_left_deepest_node()
524 struct rb_node *rb_next_postorder(const struct rb_node *node) in rb_next_postorder() argument
527 if (!node) in rb_next_postorder()
529 parent = rb_parent(node); in rb_next_postorder()
532 if (parent && node == parent->rb_left && parent->rb_right) { in rb_next_postorder()