42 #define RB_EMPTY_NODE(node)  \  argument
43 	((node)->__rb_parent_color == (unsigned long)(node))
44 #define RB_CLEAR_NODE(node)  \  argument
45 	((node)->__rb_parent_color = (unsigned long)(node))
66 static inline void rb_link_node(struct rb_node *node, struct rb_node *parent,  in rb_link_node()  argument
69 	node->__rb_parent_color = (unsigned long)parent;  in rb_link_node()
70 	node->rb_left = node->rb_right = NULL;  in rb_link_node()
72 	*rb_link = node;  in rb_link_node()
129 static inline void rb_insert_color_cached(struct rb_node *node,  in rb_insert_color_cached()  argument
134 		root->rb_leftmost = node;  in rb_insert_color_cached()
135 	rb_insert_color(node, &root->rb_root);  in rb_insert_color_cached()
138 static inline void rb_erase_cached(struct rb_node *node,  in rb_erase_cached()  argument
141 	if (root->rb_leftmost == node)  in rb_erase_cached()
142 		root->rb_leftmost = rb_next(node);  in rb_erase_cached()
143 	rb_erase(node, &root->rb_root);  in rb_erase_cached()
178 rb_add_cached(struct rb_node *node, struct rb_root_cached *tree,  in rb_add_cached()  argument
187 		if (less(node, parent)) {  in rb_add_cached()
195 	rb_link_node(node, parent, link);  in rb_add_cached()
196 	rb_insert_color_cached(node, tree, leftmost);  in rb_add_cached()
206 rb_add(struct rb_node *node, struct rb_root *tree,  in rb_add()  argument
214 		if (less(node, parent))  in rb_add()
220 	rb_link_node(node, parent, link);  in rb_add()
221 	rb_insert_color(node, tree);  in rb_add()
234 rb_find_add(struct rb_node *node, struct rb_root *tree,  in rb_find_add()  argument
243 		c = cmp(node, parent);  in rb_find_add()
253 	rb_link_node(node, parent, link);  in rb_find_add()
254 	rb_insert_color(node, tree);  in rb_find_add()
270 	struct rb_node *node = tree->rb_node;  in rb_find()  local
272 	while (node) {  in rb_find()
273 		int c = cmp(key, node);  in rb_find()
276 			node = node->rb_left;  in rb_find()
278 			node = node->rb_right;  in rb_find()
280 			return node;  in rb_find()
298 	struct rb_node *node = tree->rb_node;  in rb_find_first()  local
301 	while (node) {  in rb_find_first()
302 		int c = cmp(key, node);  in rb_find_first()
306 				match = node;  in rb_find_first()
307 			node = node->rb_left;  in rb_find_first()
309 			node = node->rb_right;  in rb_find_first()
325 rb_next_match(const void *key, struct rb_node *node,  in rb_next_match()  argument
328 	node = rb_next(node);  in rb_next_match()
329 	if (node && cmp(key, node))  in rb_next_match()
330 		node = NULL;  in rb_next_match()
331 	return node;  in rb_next_match()
341 #define rb_for_each(node, key, tree, cmp) \  argument
342 	for ((node) = rb_find_first((key), (tree), (cmp)); \
343 	     (node); (node) = rb_next_match((key), (node), (cmp)))