37 struct rb_node {  struct
48     struct rb_node *left;  argument
51     struct rb_node *right;  argument
55 static inline struct rb_node *
56 rb_node_parent(struct rb_node *n)  in rb_node_parent()
58     return (struct rb_node *)(n->parent & ~(uintptr_t)1);  in rb_node_parent()
67     struct rb_node *root;
107 void rb_tree_insert_at(struct rb_tree *T, struct rb_node *parent,
108                        struct rb_node *node, bool insert_left);
119 rb_tree_insert(struct rb_tree *T, struct rb_node *node,  in rb_tree_insert()
120                int (*cmp)(const struct rb_node *, const struct rb_node *))  in rb_tree_insert()  argument
125     struct rb_node *y = NULL;  in rb_tree_insert()
126     struct rb_node *x = T->root;  in rb_tree_insert()
146 void rb_tree_remove(struct rb_tree *T, struct rb_node *z);
159 static inline struct rb_node *
161                int (*cmp)(const struct rb_node *, const void *))  in rb_tree_search()  argument
166     struct rb_node *x = T->root;  in rb_tree_search()
195 static inline struct rb_node *
197                       int (*cmp)(const struct rb_node *, const void *))  in rb_tree_search_sloppy()  argument
202     struct rb_node *y = NULL;  in rb_tree_search_sloppy()
203     struct rb_node *x = T->root;  in rb_tree_search_sloppy()
219 struct rb_node *rb_tree_first(struct rb_tree *T);
222 struct rb_node *rb_tree_last(struct rb_tree *T);
225 struct rb_node *rb_node_next(struct rb_node *node);
228 struct rb_node *rb_node_prev(struct rb_node *node);
247         (iter = rb_node_data(type, (struct rb_node *)__node, field), true); \
248         __node = (type *)rb_node_next((struct rb_node *)__node))
264              *__next = (type *)rb_node_next_or_null((struct rb_node *)__node); \
266         (iter = rb_node_data(type, (struct rb_node *)__node, field), true); \
268         __next = (type *)rb_node_next_or_null((struct rb_node *)__node))
284         (iter = rb_node_data(type, (struct rb_node *)__node, field), true); \
285         __node = (type *)rb_node_prev((struct rb_node *)__node))
301              *__prev = (type *)rb_node_prev_or_null((struct rb_node *)__node); \
303         (iter = rb_node_data(type, (struct rb_node *)__node, field), true); \
305         __prev = (type *)rb_node_prev_or_null((struct rb_node *)__node))