33 #define RB_EMPTY_NODE(node)  \  argument
34 	((node)->__rb_parent_color == (unsigned long)(node))
35 #define RB_CLEAR_NODE(node)  \  argument
36 	((node)->__rb_parent_color = (unsigned long)(node))
53 /* Fast replacement of a single node without remove/rebalance/add/rebalance */
59 static inline void rb_link_node(struct rb_node *node, struct rb_node *parent,  in rb_link_node()  argument
62 	node->__rb_parent_color = (unsigned long)parent;  in rb_link_node()
63 	node->rb_left = node->rb_right = NULL;  in rb_link_node()
65 	*rb_link = node;  in rb_link_node()
68 static inline void rb_link_node_rcu(struct rb_node *node, struct rb_node *parent,  in rb_link_node_rcu()  argument
71 	node->__rb_parent_color = (unsigned long)parent;  in rb_link_node_rcu()
72 	node->rb_left = node->rb_right = NULL;  in rb_link_node_rcu()
74 	rcu_assign_pointer(*rb_link, node);  in rb_link_node_rcu()
108 static inline void rb_insert_color_cached(struct rb_node *node,  in rb_insert_color_cached()  argument
113 		root->rb_leftmost = node;  in rb_insert_color_cached()
114 	rb_insert_color(node, &root->rb_root);  in rb_insert_color_cached()
119 rb_erase_cached(struct rb_node *node, struct rb_root_cached *root)  in rb_erase_cached()  argument
123 	if (root->rb_leftmost == node)  in rb_erase_cached()
124 		leftmost = root->rb_leftmost = rb_next(node);  in rb_erase_cached()
126 	rb_erase(node, &root->rb_root);  in rb_erase_cached()
157  * rb_add_cached() - insert @node into the leftmost cached tree @tree
158  * @node: node to insert
159  * @tree: leftmost cached tree to insert @node into
160  * @less: operator defining the (partial) node order
162  * Returns @node when it is the new leftmost, or NULL.
165 rb_add_cached(struct rb_node *node, struct rb_root_cached *tree,  in rb_add_cached()  argument
174 		if (less(node, parent)) {  in rb_add_cached()
182 	rb_link_node(node, parent, link);  in rb_add_cached()
183 	rb_insert_color_cached(node, tree, leftmost);  in rb_add_cached()
185 	return leftmost ? node : NULL;  in rb_add_cached()
189  * rb_add() - insert @node into @tree
190  * @node: node to insert
191  * @tree: tree to insert @node into
192  * @less: operator defining the (partial) node order
195 rb_add(struct rb_node *node, struct rb_root *tree,  in rb_add()  argument
203 		if (less(node, parent))  in rb_add()
209 	rb_link_node(node, parent, link);  in rb_add()
210 	rb_insert_color(node, tree);  in rb_add()
214  * rb_find_add_cached() - find equivalent @node in @tree, or add @node
215  * @node: node to look-for / insert
217  * @cmp: operator defining the node order
219  * Returns the rb_node matching @node, or NULL when no match is found and @node
223 rb_find_add_cached(struct rb_node *node, struct rb_root_cached *tree,  in rb_find_add_cached()  argument
233 		c = cmp(node, parent);  in rb_find_add_cached()
245 	rb_link_node(node, parent, link);  in rb_find_add_cached()
246 	rb_insert_color_cached(node, tree, leftmost);  in rb_find_add_cached()
251  * rb_find_add() - find equivalent @node in @tree, or add @node
252  * @node: node to look-for / insert
254  * @cmp: operator defining the node order
256  * Returns the rb_node matching @node, or NULL when no match is found and @node
260 rb_find_add(struct rb_node *node, struct rb_root *tree,  in rb_find_add()  argument
269 		c = cmp(node, parent);  in rb_find_add()
279 	rb_link_node(node, parent, link);  in rb_find_add()
280 	rb_insert_color(node, tree);  in rb_find_add()
285  * rb_find_add_rcu() - find equivalent @node in @tree, or add @node
286  * @node: node to look-for / insert
288  * @cmp: operator defining the node order
292  * Returns the rb_node matching @node, or NULL when no match is found and @node
296 rb_find_add_rcu(struct rb_node *node, struct rb_root *tree,  in rb_find_add_rcu()  argument
305 		c = cmp(node, parent);  in rb_find_add_rcu()
315 	rb_link_node_rcu(node, parent, link);  in rb_find_add_rcu()
316 	rb_insert_color(node, tree);  in rb_find_add_rcu()
324  * @cmp: operator defining the node order
332 	struct rb_node *node = tree->rb_node;  in rb_find()  local
334 	while (node) {  in rb_find()
335 		int c = cmp(key, node);  in rb_find()
338 			node = node->rb_left;  in rb_find()
340 			node = node->rb_right;  in rb_find()
342 			return node;  in rb_find()
352  * @cmp: operator defining the node order
363 	struct rb_node *node = tree->rb_node;  in rb_find_rcu()  local
365 	while (node) {  in rb_find_rcu()
366 		int c = cmp(key, node);  in rb_find_rcu()
369 			node = rcu_dereference_raw(node->rb_left);  in rb_find_rcu()
371 			node = rcu_dereference_raw(node->rb_right);  in rb_find_rcu()
373 			return node;  in rb_find_rcu()
383  * @cmp: operator defining node order
385  * Returns the leftmost node matching @key, or NULL.
391 	struct rb_node *node = tree->rb_node;  in rb_find_first()  local
394 	while (node) {  in rb_find_first()
395 		int c = cmp(key, node);  in rb_find_first()
399 				match = node;  in rb_find_first()
400 			node = node->rb_left;  in rb_find_first()
402 			node = node->rb_right;  in rb_find_first()
413  * @cmp: operator defining node order
415  * Returns the next node matching @key, or NULL.
418 rb_next_match(const void *key, struct rb_node *node,  in rb_next_match()  argument
421 	node = rb_next(node);  in rb_next_match()
422 	if (node && cmp(key, node))  in rb_next_match()
423 		node = NULL;  in rb_next_match()
424 	return node;  in rb_next_match()
429  * @node: iterator
432  * @cmp: operator defining node order
434 #define rb_for_each(node, key, tree, cmp) \  argument
435 	for ((node) = rb_find_first((key), (tree), (cmp)); \
436 	     (node); (node) = rb_next_match((key), (node), (cmp)))