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

Previous Next

Full log

Message #44 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:37:51 +0200

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

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

The code from libstdc++ is this (from libstdc++-v3/src/c++98/tree.cc):

  static _Rb_tree_node_base*
  local_Rb_tree_increment(_Rb_tree_node_base* __x) throw ()
  {
    if (__x->_M_right != 0)
      {
        __x = __x->_M_right;
        while (__x->_M_left != 0)
          __x = __x->_M_left;
      }
    else
      {
        _Rb_tree_node_base* __y = __x->_M_parent;
        while (__x == __y->_M_right)
          {
            __x = __y;
            __y = __y->_M_parent;
          }
        if (__x->_M_right != __y)
          __x = __y;
      }
    return __x;
  }

I hope one can read that.

The idea is to find the root of the smallest subtree containing the
current node, and proceed from there.  That's why the parent pointer is
needed.

Symmmetrical for max->min ordering.  And finding min/max is trivial.

Previous Next

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