Re: noverlay branch

[Matt Armstrong]

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

> Matt Armstrong <matt@rfc20.org> writes:
>
>>> Clang libstd++ uses NULL, BTW, and I already wondered a little bit why.
>>
>> I believe GNU libstdc++ does not use sentinel nodes either.  I have yet
>> to see see sentinel nodes used in an optimized tree implementation.
>
> I looked it up a few days ago, out of interest, and GCC's rb-tree uses
> sentinels, in Git master at least.  Somewhere in this thread I posted
> where to look in GCC's Git repo, I can't remember ATM.

It uses a sentinel for the parent of the root node (a "header") but it
does not use a sentinel node for null at the leaves.  The easiest way to
see it is by looking at the code for GNU libstdc++ "minimum()" algorithm
on trees, which walks left ponters down to a leaf node:

https://gcc.gnu.org/git/?p=gcc.git;a=blob;f=libstdc%2B%2B-v3/include/bits/stl_tree.h;h=a4de61417652a288e361a55fcc8bb7a9838c58a5;hb=HEAD#l112
    _S_minimum(_Base_ptr __x) _GLIBCXX_NOEXCEPT
    {
      while (__x->_M_left != 0) __x = __x->_M_left;
      return __x;
    }

For the header node, see
https://gcc.gnu.org/git?p=gcc.git;a=blob;f=libstdc%2B%2B-v3/include/bits/stl_tree.h;h=a4de61417652a288e361a55fcc8bb7a9838c58a5;hb=HEAD#l89