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

Previous Next

Full log

Message #38 received at 58158 <at> debbugs.gnu.org (full text, mbox):

From: Eli Zaretskii <eliz <at> gnu.org>
To: Stefan Monnier <monnier <at> iro.umontreal.ca>
Cc: gerd.moellmann <at> gmail.com, 58158 <at> debbugs.gnu.org
Subject: Re: bug#58158: 29.0.50; [overlay] Interval tree iteration
 considered harmful
Date: Thu, 29 Sep 2022 16:40:10 +0300

> From: Stefan Monnier <monnier <at> iro.umontreal.ca>
> Cc: Gerd Möllmann <gerd.moellmann <at> gmail.com>,
>   58158 <at> debbugs.gnu.org
> 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?

Previous Next

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