include/linux/rbtree.h

42 #define RB_EMPTY_NODE(node)  \
43 	((node)->__rb_parent_color == (unsigned long)(node))
44 #define RB_CLEAR_NODE(node)  \
45 	((node)->__rb_parent_color = (unsigned long)(node))
62 /* Fast replacement of a single node without remove/rebalance/add/rebalance */
66 static inline void rb_link_node(struct rb_node *node, struct rb_node *parent,
69 	node->__rb_parent_color = (unsigned long)parent;
70 	node->rb_left = node->rb_right = NULL;
72 	*rb_link = node;
112  * We do not cache the rightmost node based on footprint
129 static inline void rb_insert_color_cached(struct rb_node *node,
134 		root->rb_leftmost = node;
135 	rb_insert_color(node, &root->rb_root);
138 static inline void rb_erase_cached(struct rb_node *node,
141 	if (root->rb_leftmost == node)
142 		root->rb_leftmost = rb_next(node);
143 	rb_erase(node, &root->rb_root);
172  * rb_add_cached() - insert @node into the leftmost cached tree @tree
173  * @node: node to insert
174  * @tree: leftmost cached tree to insert @node into
175  * @less: operator defining the (partial) node order
178 rb_add_cached(struct rb_node *node, struct rb_root_cached *tree,
187 		if (less(node, parent)) {
195 	rb_link_node(node, parent, link);
196 	rb_insert_color_cached(node, tree, leftmost);
200  * rb_add() - insert @node into @tree
201  * @node: node to insert
202  * @tree: tree to insert @node into
203  * @less: operator defining the (partial) node order
206 rb_add(struct rb_node *node, struct rb_root *tree,
214 		if (less(node, parent))
220 	rb_link_node(node, parent, link);
221 	rb_insert_color(node, tree);
225  * rb_find_add() - find equivalent @node in @tree, or add @node
226  * @node: node to look-for / insert
228  * @cmp: operator defining the node order
230  * Returns the rb_node matching @node, or NULL when no match is found and @node
234 rb_find_add(struct rb_node *node, struct rb_root *tree,
243 		c = cmp(node, parent);
253 	rb_link_node(node, parent, link);
254 	rb_insert_color(node, tree);
262  * @cmp: operator defining the node order
270 	struct rb_node *node = tree->rb_node;
272 	while (node) {
273 		int c = cmp(key, node);
276 			node = node->rb_left;
278 			node = node->rb_right;
280 			return node;
290  * @cmp: operator defining node order
292  * Returns the leftmost node matching @key, or NULL.
298 	struct rb_node *node = tree->rb_node;
301 	while (node) {
302 		int c = cmp(key, node);
306 				match = node;
307 			node = node->rb_left;
309 			node = node->rb_right;
320  * @cmp: operator defining node order
322  * Returns the next node matching @key, or NULL.
325 rb_next_match(const void *key, struct rb_node *node,
328 	node = rb_next(node);
329 	if (node && cmp(key, node))
330 		node = NULL;
331 	return node;
336  * @node: iterator
339  * @cmp: operator defining node order
341 #define rb_for_each(node, key, tree, cmp) \
342 	for ((node) = rb_find_first((key), (tree), (cmp)); \
343 	     (node); (node) = rb_next_match((key), (node), (cmp)))