GNU bug report logs - #58158
29.0.50; [overlay] Interval tree iteration considered harmful

Previous Next

Full log

View this message in rfc822 format

From: Gerd Möllmann <gerd.moellmann <at> gmail.com>
To: Stefan Monnier <monnier <at> iro.umontreal.ca>
Cc: Eli Zaretskii <eliz <at> gnu.org>, Andreas Politz <mail <at> andreas-politz.de>, 58158 <at> debbugs.gnu.org
Subject: bug#58158: 29.0.50; [overlay] Interval tree iteration considered harmful
Date: Sat, 01 Oct 2022 12:55:42 +0200

Gerd Möllmann <gerd.moellmann <at> gmail.com> writes:

> I have to look at std::multimap, they manage to do this somehow.

Well, I should have thought of that, because it's obvious from the fact
they are able to use successor/predecessor functions :-/.

The equivalent in our code would go like below, which is just written
down in a hurry, so please bear with me.  It's just about the idea.  So:

Insert a new interval_node only if overlay start is not in the tree
already.  If the contains a node for the start, make the node's value a
list of overlays, and add the new one to it in an order that's
convenient (The STL uses insertion order).


As a consequence, keys is the rb-tree are unique, and it is always
strictly ordered, rotations don't change that.  The min node is the
left-most node in a tree, and so on.

So far so good.


An iterator in the order min->max would have to record the interval_node
in the tree plus information where in the list of overlays it is, if it
is in any.  Finding the next node is implemented with a successor
function like the one I've shown from libstdc++.

To find all overlays containing a given position POS, find the node
whose start is <= POS.  Start at the root of the tree, and walk the left
link until we find the ndoes's start is <= POS.  Then iterate forward
until start > POS, returning only overlapping overlays.

Finding overlays intersecting an interval [BEG, END] is not as nice, but
we can exclude intervals starting after END.  So we have to iterate over
all overlays from the minimum of the tree, and iterate forward until we
reach the first excluded one.

That's so "easy" that even I can understand how it works :-).

What am I overlooking?

Previous Next

GNU bug tracking system
Copyright (C) 1999 Darren O. Benham, 1997,2003 nCipher Corporation Ltd, 1994-97 Ian Jackson.