include/linux/interval_tree_generic.h

1 /* SPDX-License-Identifier: GPL-2.0-or-later */
18  * ITSUBTREE:  name of ITTYPE field within ITSTRUCT holding last-in-subtree
19  * ITSTART(n): start endpoint of ITSTRUCT node n
20  * ITLAST(n):  last endpoint of ITSTRUCT node n
24  * Note - before using this, please consider if generic version
38 ITSTATIC void ITPREFIX ## _insert(ITSTRUCT *node,			      \
39 				  struct rb_root_cached *root)	 	      \
41 	struct rb_node **link = &root->rb_root.rb_node, *rb_parent = NULL;    \
42 	ITTYPE start = ITSTART(node), last = ITLAST(node);		      \
49 		if (parent->ITSUBTREE < last)				      \
50 			parent->ITSUBTREE = last;			      \
52 			link = &parent->ITRB.rb_left;			      \
54 			link = &parent->ITRB.rb_right;			      \
59 	node->ITSUBTREE = last;						      \
60 	rb_link_node(&node->ITRB, rb_parent, link);			      \
61 	rb_insert_augmented_cached(&node->ITRB, root,			      \
65 ITSTATIC void ITPREFIX ## _remove(ITSTRUCT *node,			      \
66 				  struct rb_root_cached *root)		      \
68 	rb_erase_augmented_cached(&node->ITRB, root, &ITPREFIX ## _augment);  \
74  * Note that a node's interval intersects [start;last] iff:		      \
75  *   Cond1: ITSTART(node) <= last					      \
77  *   Cond2: start <= ITLAST(node)					      \
81 ITPREFIX ## _subtree_search(ITSTRUCT *node, ITTYPE start, ITTYPE last)	      \
85 		 * Loop invariant: start <= node->ITSUBTREE		      \
88 		if (node->ITRB.rb_left) {				      \
89 			ITSTRUCT *left = rb_entry(node->ITRB.rb_left,	      \
91 			if (start <= left->ITSUBTREE) {			      \
94 				 * Iterate to find the leftmost such node N.  \
100 				node = left;				      \
104 		if (ITSTART(node) <= last) {		/* Cond1 */	      \
105 			if (start <= ITLAST(node))	/* Cond2 */	      \
106 				return node;	/* node is leftmost match */  \
107 			if (node->ITRB.rb_right) {			      \
108 				node = rb_entry(node->ITRB.rb_right,	      \
110 				if (start <= node->ITSUBTREE)		      \
119 ITPREFIX ## _iter_first(struct rb_root_cached *root,			      \
122 	ITSTRUCT *node, *leftmost;					      \
124 	if (!root->rb_root.rb_node)					      \
135 	 * rely on the root node, which by augmented interval tree	      \
136 	 * property, holds the largest value in its last-in-subtree.	      \
138 	 * for non-intersecting ranges, maintained and consulted in O(1).     \
140 	node = rb_entry(root->rb_root.rb_node, ITSTRUCT, ITRB);		      \
141 	if (node->ITSUBTREE < start)					      \
144 	leftmost = rb_entry(root->rb_leftmost, ITSTRUCT, ITRB);		      \
148 	return ITPREFIX ## _subtree_search(node, start, last);		      \
152 ITPREFIX ## _iter_next(ITSTRUCT *node, ITTYPE start, ITTYPE last)	      \
154 	struct rb_node *rb = node->ITRB.rb_right, *prev;		      \
159 		 *   Cond1: ITSTART(node) <= last			      \
160 		 *   rb == node->ITRB.rb_right				      \
166 			if (start <= right->ITSUBTREE)			      \
171 		/* Move up the tree until we come from a node's left child */ \
173 			rb = rb_parent(&node->ITRB);			      \
176 			prev = &node->ITRB;				      \
177 			node = rb_entry(rb, ITSTRUCT, ITRB);		      \
178 			rb = node->ITRB.rb_right;			      \
181 		/* Check if the node intersects [start;last] */		      \
182 		if (last < ITSTART(node))		/* !Cond1 */	      \
184 		else if (start <= ITLAST(node))		/* Cond2 */	      \
185 			return node;					      \