include/linux/rbtree.h

26 #define rb_parent(r)   ((struct rb_node *)((r)->__rb_parent_color & ~3))
30 #define RB_EMPTY_ROOT(root)  (READ_ONCE((root)->rb_node) == NULL)
39 extern void rb_insert_color(struct rb_node *, struct rb_root *);
40 extern void rb_erase(struct rb_node *, struct rb_root *);
44 extern struct rb_node *rb_next(const struct rb_node *);
45 extern struct rb_node *rb_prev(const struct rb_node *);
46 extern struct rb_node *rb_first(const struct rb_root *);
47 extern struct rb_node *rb_last(const struct rb_root *);
50 extern struct rb_node *rb_first_postorder(const struct rb_root *);
51 extern struct rb_node *rb_next_postorder(const struct rb_node *);
54 extern void rb_replace_node(struct rb_node *victim, struct rb_node *new,
56 extern void rb_replace_node_rcu(struct rb_node *victim, struct rb_node *new,
59 static inline void rb_link_node(struct rb_node *node, struct rb_node *parent,
60 				struct rb_node **rb_link)
68 static inline void rb_link_node_rcu(struct rb_node *node, struct rb_node *parent,
69 				    struct rb_node **rb_link)
89  * @field:	the name of the rb_node field within 'type'.
108 static inline void rb_insert_color_cached(struct rb_node *node,
118 static inline struct rb_node *
119 rb_erase_cached(struct rb_node *node, struct rb_root_cached *root)
121 	struct rb_node *leftmost = NULL;
131 static inline void rb_replace_node_cached(struct rb_node *victim,
132 					  struct rb_node *new,
164 static __always_inline struct rb_node *
165 rb_add_cached(struct rb_node *node, struct rb_root_cached *tree,
166 	      bool (*less)(struct rb_node *, const struct rb_node *))
168 	struct rb_node **link = &tree->rb_root.rb_node;
169 	struct rb_node *parent = NULL;
195 rb_add(struct rb_node *node, struct rb_root *tree,
196        bool (*less)(struct rb_node *, const struct rb_node *))
198 	struct rb_node **link = &tree->rb_node;
199 	struct rb_node *parent = NULL;
219  * Returns the rb_node matching @node, or NULL when no match is found and @node
222 static __always_inline struct rb_node *
223 rb_find_add(struct rb_node *node, struct rb_root *tree,
224 	    int (*cmp)(struct rb_node *, const struct rb_node *))
226 	struct rb_node **link = &tree->rb_node;
227 	struct rb_node *parent = NULL;
253  * Returns the rb_node matching @key or NULL.
255 static __always_inline struct rb_node *
257 	int (*cmp)(const void *key, const struct rb_node *))
259 	struct rb_node *node = tree->rb_node;
283 static __always_inline struct rb_node *
285 	      int (*cmp)(const void *key, const struct rb_node *))
287 	struct rb_node *node = tree->rb_node;
288 	struct rb_node *match = NULL;
313 static __always_inline struct rb_node *
314 rb_next_match(const void *key, struct rb_node *node,
315 	      int (*cmp)(const void *key, const struct rb_node *))