On Tue, Nov 15, 2022 at 03:14:00PM +0100, Eric Auger wrote:
> > diff --git a/lib/interval_tree.c b/lib/interval_tree.c
> > index 593ce56ece5050..d2882db8fa2a07 100644
> > --- a/lib/interval_tree.c
> > +++ b/lib/interval_tree.c
> > @@ -15,3 +15,135 @@ EXPORT_SYMBOL_GPL(interval_tree_insert);
> > EXPORT_SYMBOL_GPL(interval_tree_remove);
> > EXPORT_SYMBOL_GPL(interval_tree_iter_first);
> > EXPORT_SYMBOL_GPL(interval_tree_iter_next);
> > +
> > +#ifdef CONFIG_INTERVAL_TREE_SPAN_ITER
> Maybe add in a kernel doc that a prerequisite is state.nodes[1] must be
> populated
Sure, lets just move the below comment up a bit:
/*
* Roll nodes[1] into nodes[0] by advancing nodes[1] to the end of a contiguous
* span of nodes. This makes nodes[0]->last the end of that contiguous used span
* indexes that started at the original nodes[1]->start. nodes[1] is now the
* first node starting the next used span. A hole span is between nodes[0]->last
* and nodes[1]->start. nodes[1] must be !NULL.
*/
> > +/*
> > + * Advance the iterator index to a specific position. The returned used/hole is
> > + * updated to start at new_index. This is faster than calling
> > + * interval_tree_span_iter_first() as it can avoid full searches in several
> > + * cases where the iterator is already set.
> > + */
> > +void interval_tree_span_iter_advance(struct interval_tree_span_iter *iter,
> > + struct rb_root_cached *itree,
> > + unsigned long new_index)
> > +{
> > + if (iter->is_hole == -1)
> > + return;
> > +
> > + iter->first_index = new_index;
> check new_index > iter->first_index?
It is odd but it actually works out OK if that is violated. I guess a
WARN_ON would be appropriate but I've avoided adding assertions to
this code..
> > + if (new_index > iter->last_index) {
> > + iter->is_hole = -1;
> > + return;
> > + }
> > +
> > + /* Rely on the union aliasing hole/used */
> > + if (iter->start_hole <= new_index && new_index <= iter->last_hole) {
> > + iter->start_hole = new_index;
> > + return;
> > + }
> > + if (new_index == iter->last_hole + 1)
> > + interval_tree_span_iter_next(iter);
> > + else
> > + interval_tree_span_iter_first(iter, itree, new_index,
> > + iter->last_index);
This call will reset iter->first_index to new_index and even if it is
outside the original bounds everything will work. Of course if the
caller does some 'backwards' advance then they are going to probably
be very sad and likely hit an infinite loop, but that applies to all
kinds of backwards advances, not just going before the original
bounds.
Thanks,
Jason
