interval-tree: Add a utility to iterate over spans in an interval tree

The span iterator travels over the indexes of the interval_tree, not the
nodes, and classifies spans of indexes as either 'used' or 'hole'.

'used' spans are fully covered by nodes in the tree and 'hole' spans have
no node intersecting the span.

This is done greedily such that spans are maximally sized and every
iteration step switches between used/hole.

As an example a trivial allocator can be written as:

	for (interval_tree_span_iter_first(&span, itree, 0, ULONG_MAX);
	     !interval_tree_span_iter_done(&span);
	     interval_tree_span_iter_next(&span))
		if (span.is_hole &&
		    span.last_hole - span.start_hole >= allocation_size - 1)
			return span.start_hole;

With all the tricky boundary conditions handled by the library code.

The following iommufd patches have several algorithms for its overlapping
node interval trees that are significantly simplified with this kind of
iteration primitive. As it seems generally useful, put it into lib/.

Link: https://lore.kernel.org/r/[email protected]
Reviewed-by: Kevin Tian <[email protected]>
Reviewed-by: Eric Auger <[email protected]>
Tested-by: Nicolin Chen <[email protected]>
Tested-by: Yi Liu <[email protected]>
Tested-by: Lixiao Yang <[email protected]>
Tested-by: Matthew Rosato <[email protected]>
Signed-off-by: Jason Gunthorpe <[email protected]>

0 files changed, 0 insertions, 0 deletions