tools/include/linux/interval_tree_generic.h

Source file repositories/reference/linux-study-clean/tools/include/linux/interval_tree_generic.h

File Facts

System
Linux kernel
Corpus path
tools/include/linux/interval_tree_generic.h
Extension
.h
Size
6743 bytes
Lines
184
Domain
Support Tooling And Documentation
Bucket
tools
Inferred role
Support Tooling And Documentation: implementation source
Status
source implementation candidate

Why This File Exists

Repository support layer: documentation, build tooling, samples, user-space helper tools, generated initramfs support, licenses, and validation utilities.

Dependency Surface

Detected Declarations

Annotated Snippet

if (node->ITRB.rb_left) {				      \
			ITSTRUCT *left = rb_entry(node->ITRB.rb_left,	      \
						  ITSTRUCT, ITRB);	      \
			if (start <= left->ITSUBTREE) {			      \
				/*					      \
				 * Some nodes in left subtree satisfy Cond2.  \
				 * Iterate to find the leftmost such node N.  \
				 * If it also satisfies Cond1, that's the     \
				 * match we are looking for. Otherwise, there \
				 * is no matching interval as nodes to the    \
				 * right of N can't satisfy Cond1 either.     \
				 */					      \
				node = left;				      \
				continue;				      \
			}						      \
		}							      \
		if (ITSTART(node) <= last) {		/* Cond1 */	      \
			if (start <= ITLAST(node))	/* Cond2 */	      \
				return node;	/* node is leftmost match */  \
			node = rb_entry(node->ITRB.rb_right, ITSTRUCT, ITRB); \
			continue;					      \
		}							      \
		return NULL;	/* No match */				      \
	}								      \
}									      \
									      \
ITSTATIC ITSTRUCT *							      \
ITPREFIX ## _iter_first(struct rb_root_cached *root,			      \
			ITTYPE start, ITTYPE last)			      \
{									      \
	ITSTRUCT *node, *leftmost;					      \
									      \
	if (!root->rb_root.rb_node)					      \
		return NULL;						      \
									      \
	/*								      \
	 * Fastpath range intersection/overlap between A: [a0, a1] and	      \
	 * B: [b0, b1] is given by:					      \
	 *								      \
	 *         a0 <= b1 && b0 <= a1					      \
	 *								      \
	 *  ... where A holds the lock range and B holds the smallest	      \
	 * 'start' and largest 'last' in the tree. For the later, we	      \
	 * rely on the root node, which by augmented interval tree	      \
	 * property, holds the largest value in its last-in-subtree.	      \
	 * This allows mitigating some of the tree walk overhead for	      \
	 * for non-intersecting ranges, maintained and consulted in O(1).     \
	 */								      \
	node = rb_entry(root->rb_root.rb_node, ITSTRUCT, ITRB);		      \
	if (node->ITSUBTREE < start)					      \
		return NULL;						      \
									      \
	leftmost = rb_entry(root->rb_leftmost, ITSTRUCT, ITRB);		      \
	if (ITSTART(leftmost) > last)					      \
		return NULL;						      \
									      \
	return ITPREFIX ## _subtree_search(node, start, last);		      \
}									      \
									      \
ITSTATIC ITSTRUCT *							      \
ITPREFIX ## _iter_next(ITSTRUCT *node, ITTYPE start, ITTYPE last)	      \
{									      \
	struct rb_node *rb = node->ITRB.rb_right, *prev;		      \
									      \
	while (true) {							      \
		/*							      \
		 * Loop invariants:					      \
		 *   Cond1: ITSTART(node) <= last			      \
		 *   rb == node->ITRB.rb_right				      \
		 *							      \
		 * First, search right subtree if suitable		      \
		 */							      \
		if (rb) {						      \
			ITSTRUCT *right = rb_entry(rb, ITSTRUCT, ITRB);	      \
			if (start <= right->ITSUBTREE)			      \
				return ITPREFIX ## _subtree_search(right,     \
								start, last); \
		}							      \
									      \
		/* Move up the tree until we come from a node's left child */ \
		do {							      \
			rb = rb_parent(&node->ITRB);			      \
			if (!rb)					      \
				return NULL;				      \
			prev = &node->ITRB;				      \
			node = rb_entry(rb, ITSTRUCT, ITRB);		      \
			rb = node->ITRB.rb_right;			      \
		} while (prev == rb);					      \
									      \
		/* Check if the node intersects [start;last] */		      \

Annotation

Implementation Notes