include/linux/rbtree.h

23 struct rb_node {
25 	struct rb_node *rb_right;
26 	struct rb_node *rb_left;
31 	struct rb_node *rb_node;
34 #define rb_parent(r)   ((struct rb_node *)((r)->__rb_parent_color & ~3))
39 #define RB_EMPTY_ROOT(root)  (READ_ONCE((root)->rb_node) == NULL)
48 extern void rb_insert_color(struct rb_node *, struct rb_root *);
49 extern void rb_erase(struct rb_node *, struct rb_root *);
53 extern struct rb_node *rb_next(const struct rb_node *);
54 extern struct rb_node *rb_prev(const struct rb_node *);
55 extern struct rb_node *rb_first(const struct rb_root *);
56 extern struct rb_node *rb_last(const struct rb_root *);
59 extern struct rb_node *rb_first_postorder(const struct rb_root *);
60 extern struct rb_node *rb_next_postorder(const struct rb_node *);
63 extern void rb_replace_node(struct rb_node *victim, struct rb_node *new,
66 static inline void rb_link_node(struct rb_node *node, struct rb_node *parent,
67 				struct rb_node **rb_link)
87  * @field:	the name of the rb_node field within 'type'.
103 static inline void rb_erase_init(struct rb_node *n, struct rb_root *root)
121 	struct rb_node *rb_leftmost;
129 static inline void rb_insert_color_cached(struct rb_node *node,
138 static inline void rb_erase_cached(struct rb_node *node,
146 static inline void rb_replace_node_cached(struct rb_node *victim,
147 					  struct rb_node *new,
178 rb_add_cached(struct rb_node *node, struct rb_root_cached *tree,
179 	      bool (*less)(struct rb_node *, const struct rb_node *))
181 	struct rb_node **link = &tree->rb_root.rb_node;
182 	struct rb_node *parent = NULL;
206 rb_add(struct rb_node *node, struct rb_root *tree,
207        bool (*less)(struct rb_node *, const struct rb_node *))
209 	struct rb_node **link = &tree->rb_node;
210 	struct rb_node *parent = NULL;
230  * Returns the rb_node matching @node, or NULL when no match is found and @node
233 static __always_inline struct rb_node *
234 rb_find_add(struct rb_node *node, struct rb_root *tree,
235 	    int (*cmp)(struct rb_node *, const struct rb_node *))
237 	struct rb_node **link = &tree->rb_node;
238 	struct rb_node *parent = NULL;
264  * Returns the rb_node matching @key or NULL.
266 static __always_inline struct rb_node *
268 	int (*cmp)(const void *key, const struct rb_node *))
270 	struct rb_node *node = tree->rb_node;
294 static __always_inline struct rb_node *
296 	      int (*cmp)(const void *key, const struct rb_node *))
298 	struct rb_node *node = tree->rb_node;
299 	struct rb_node *match = NULL;
324 static __always_inline struct rb_node *
325 rb_next_match(const void *key, struct rb_node *node,
326 	      int (*cmp)(const void *key, const struct rb_node *))