Subject: bug#58158: 29.0.50; [overlay] Interval tree iteration considered harmful

From: Eli Zaretskii <[email-masked]>
Date: Thu, 29 Sep 2022 16:40:10 +0300

> From: Stefan Monnier <[email-masked]>
> Cc: Gerd Möllmann <[email-masked]>,
>   [email-masked]
> Date: Thu, 29 Sep 2022 09:10:19 -0400
> 
> Another is the need to update the begin/end fields (these need updating
> because of insertions/deletions but they're updated lazily while
> traversing the tree to avoid an O(N) complexity during the
> insertions/deletions).  Hiding that behind 'some kind of "next node"
> function keeps the code more readable.

Btw, couldn't we handle this by having a flag in the node that tells
us whether the begin/end fields can be trusted?  Then the first caller
who need them would run the update and reset the flags, and we still
have lazy update, albeit somewhat less lazy, but without the need for
guarding the iteration with start/finish calls.  Would that work?