Re: [Qemu-devel] [PATCH 07/10] util: implement simple interval tree logic

[Peter Xu <peterx@redhat.com>]

On Fri, Apr 27, 2018 at 01:53:35PM +0800, Jason Wang wrote:

[...]

> > +int it_tree_remove(ITTree *tree, ITValue start, ITValue end)
> > +{
> > +    ITRange range = { .start = start, .end = end }, *overlap, and;
> > +    GTree *gtree;
> > +
> > +    g_assert(tree);
> > +
> > +    gtree = tree->tree;
> > +    while ((overlap = g_tree_lookup(gtree, &range))) {
> > +        if (it_range_equal(overlap, &range)) {
> > +            /* Exactly what we want to remove; done */

[1]

> > +            g_tree_remove(gtree, overlap);
> > +            break;
> > +        } else if (it_range_cover(overlap, &range)) {

[2]

> > +            /* Split existing range into two; done */
> > +            it_tree_remove_subset(gtree, overlap, &range);
> > +            break;
> > +        } else if (it_range_cover(&range, overlap)) {

[3]

> > +            /* Drop this range and continue */
> > +            g_tree_remove(gtree, overlap);
> > +        } else {

[4]

> > +            /*
> > +             * The range to remove has intersection with existing
> > +             * ranges.  Remove part of the range and continue
> > +             */
> > +            it_range_and(&and, overlap, &range);
> > +            g_assert(and.start <= and.end);
> > +            it_tree_remove_subset(gtree, overlap, &and);
> > +        }
> > +    }
> > +
> 
> Looks like what we need here is just calculate the intersection part the
> remove it.

Here after a second thought, I am thining whether it'll be good I use
a general routine in [4] to replace all [1-4].

The problem is that if we do that we'll depend on the next
g_tree_lookup() to detect case [1-2] (in that case we'll find nothing
in the lookup, but still we'll need to walk the tree) to break the
loop, while IMHO that sometimes can be more expensive than the if
clauses, especially when the tree is a bit large (each branch needs a
if clause actually) and also note that in our use case we really have
lots of cases for [1] and [2].

I think I can merge [3] into [4], but I might consider keeping [1] and
[2] since I don't really know whether merging them would be better.
Anyway we can do that as follow up enhancement after the series
merged.  But I think we'll need some performance benchmarks.

Jason, what do you think?

Regards,

-- 
Peter Xu