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

Previous Next

Full log

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

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

Stefan Monnier <monnier <at> iro.umontreal.ca> writes:

> One reason is that traversing a binary tree usually requires something
> like recursion, but that wouldn't fit very conveniently with the current
> code (nor with C in general since you can't make a local recursive
> closure which accesses local variables from the surrounding function).

Ok, usually, but not necessarily.  The alternative is to implement an
iterator that starts with a node N, and an implementation of a successor
function, which return the successor of N in a given order.  This
requires a parent pointer in nodes, but that we have.

(Something like this is used for ordered containers like "map" and "set"
in C++ STL, for instance, which are based on rb-trees in GCC's
libstdc++.)

> 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.

Is this for buffer text changes, something akin to a delayed update of
marker positions?  I already wondered where that was.

> But yes, the current restriction to have a single iteration at a time is
> a bit of a problem, especially because it's very "global".  I added
> a comment yesterday describing how we could make it non-global (hence
> getting rid of the `visited` flag in the nodes).

BTW, and related to iteration directly, did you notice this in
interval_tree_insert?

      /* This suggests that nodes in the right subtree are strictly
         greater.  But this is not true due to later rotations. */
      child = node->begin <= child->begin ? child->left : child->right;

Previous Next

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