Lines Matching refs:rb_node
59 static inline void rb_set_black(struct rb_node *rb) in rb_set_black()
64 static inline struct rb_node *rb_red_parent(struct rb_node *red) in rb_red_parent()
66 return (struct rb_node *)red->__rb_parent_color; in rb_red_parent()
75 __rb_rotate_set_parents(struct rb_node *old, struct rb_node *new, in __rb_rotate_set_parents()
78 struct rb_node *parent = rb_parent(old); in __rb_rotate_set_parents()
85 __rb_insert(struct rb_node *node, struct rb_root *root, in __rb_insert()
86 void (*augment_rotate)(struct rb_node *old, struct rb_node *new)) in __rb_insert()
88 struct rb_node *parent = rb_red_parent(node), *gparent, *tmp; in __rb_insert()
227 ____rb_erase_color(struct rb_node *parent, struct rb_root *root, in ____rb_erase_color()
228 void (*augment_rotate)(struct rb_node *old, struct rb_node *new)) in ____rb_erase_color()
230 struct rb_node *node = NULL, *sibling, *tmp1, *tmp2; in ____rb_erase_color()
410 void __rb_erase_color(struct rb_node *parent, struct rb_root *root, in __rb_erase_color()
411 void (*augment_rotate)(struct rb_node *old, struct rb_node *new)) in __rb_erase_color()
424 static inline void dummy_propagate(struct rb_node *node, struct rb_node *stop) {} in dummy_propagate()
425 static inline void dummy_copy(struct rb_node *old, struct rb_node *new) {} in dummy_copy()
426 static inline void dummy_rotate(struct rb_node *old, struct rb_node *new) {} in dummy_rotate()
434 void rb_insert_color(struct rb_node *node, struct rb_root *root) in rb_insert_color()
440 void rb_erase(struct rb_node *node, struct rb_root *root) in rb_erase()
442 struct rb_node *rebalance; in rb_erase()
456 void __rb_insert_augmented(struct rb_node *node, struct rb_root *root, in __rb_insert_augmented()
457 void (*augment_rotate)(struct rb_node *old, struct rb_node *new)) in __rb_insert_augmented()
466 struct rb_node *rb_first(const struct rb_root *root) in rb_first()
468 struct rb_node *n; in rb_first()
470 n = root->rb_node; in rb_first()
479 struct rb_node *rb_last(const struct rb_root *root) in rb_last()
481 struct rb_node *n; in rb_last()
483 n = root->rb_node; in rb_last()
492 struct rb_node *rb_next(const struct rb_node *node) in rb_next()
494 struct rb_node *parent; in rb_next()
507 return (struct rb_node *)node; in rb_next()
524 struct rb_node *rb_prev(const struct rb_node *node) in rb_prev()
526 struct rb_node *parent; in rb_prev()
539 return (struct rb_node *)node; in rb_prev()
553 void rb_replace_node(struct rb_node *victim, struct rb_node *new, in rb_replace_node()
556 struct rb_node *parent = rb_parent(victim); in rb_replace_node()
570 void rb_replace_node_rcu(struct rb_node *victim, struct rb_node *new, in rb_replace_node_rcu()
573 struct rb_node *parent = rb_parent(victim); in rb_replace_node_rcu()
592 static struct rb_node *rb_left_deepest_node(const struct rb_node *node) in rb_left_deepest_node()
600 return (struct rb_node *)node; in rb_left_deepest_node()
604 struct rb_node *rb_next_postorder(const struct rb_node *node) in rb_next_postorder()
606 const struct rb_node *parent; in rb_next_postorder()
619 return (struct rb_node *)parent; in rb_next_postorder()
623 struct rb_node *rb_first_postorder(const struct rb_root *root) in rb_first_postorder()
625 if (!root->rb_node) in rb_first_postorder()
628 return rb_left_deepest_node(root->rb_node); in rb_first_postorder()