title: Trouble understanding libstdc++'s Red-black tree iterators
body: <p>I'm trying to implement iterators for a <a href="https://en.wikipedia.org/wiki/Ternary_search_tree" rel="nofollow noreferrer">Ternary Search Tree</a>, and because TSTs are very similar to BSTs, I thought I'd look at <code>libstdc++</code>'s implementation for said iterators. The idea is to iterate through all tree nodes without modifying the tree or saving anything aside from the current tree node in the iterators. The tree nodes have a parent pointer to allow this kind of iteration.</p>
  
  <p>Here's the code from the latest GCC, taken from the <a href="https://github.com/gcc-mirror/gcc/blob/master/libstdc%2B%2B-v3/src/c%2B%2B98/tree.cc" rel="nofollow noreferrer">GitHub mirror</a>:</p>
  
  <pre><code>static _Rb_tree_node_base*
  local_Rb_tree_increment(_Rb_tree_node_base* __x) throw ()
  {
    if (__x-&gt;_M_right != 0)
      {
        __x = __x-&gt;_M_right;
        while (__x-&gt;_M_left != 0)
          __x = __x-&gt;_M_left;
      }
    else
      {
        _Rb_tree_node_base* __y = __x-&gt;_M_parent;
        while (__x == __y-&gt;_M_right)
          {
            __x = __y;
            __y = __y-&gt;_M_parent;
          }
        if (__x-&gt;_M_right != __y)
          __x = __y;
      }
    return __x;
  }
  </code></pre>
  
  <p>It looks fairly straightforward, the increment operation either takes you to your right child and then all the way to left, or to your first non-right parent. What I don't understand is the second <code>if</code> clause:</p>
  
  <pre><code>if (__x-&gt;_M_right != __y)
    __x = __y;
  </code></pre>
  
  <p>How could this condition ever evaluate to <code>false</code>? <code>__x</code> needs to surpass <code>__y</code> for this happen, and that does not seem possible looking at the <code>while</code> loop. I think it might be <code>false</code> if the tree were a <a href="https://en.wikipedia.org/wiki/Threaded_binary_tree" rel="nofollow noreferrer">threaded tree</a>, but the <code>nullptr</code> checks at the first <code>if</code> clause seem to suggest otherwise. Also, removing the <code>if</code> clause and just writing <code>__x = __y;</code> in my code does not seem to break anything.</p>
  
  <p>What is going on here?</p>
  
  <p><strong>Edit</strong>:</p>
  
  <p>This is the code for Clang's <code>libc++</code>. It seems as though the same code is not guarded by an <code>if</code> this time:</p>
  
  <pre><code> template &lt;class _EndNodePtr, class _NodePtr&gt;
   inline _LIBCPP_INLINE_VISIBILITY
   _EndNodePtr
   __tree_next_iter(_NodePtr __x) _NOEXCEPT
   {
       if (__x-&gt;__right_ != nullptr)
           return static_cast&lt;_EndNodePtr&gt;(__tree_min(__x-&gt;__right_));
       while (!__tree_is_left_child(__x))
           __x = __x-&gt;__parent_unsafe();
       return static_cast&lt;_EndNodePtr&gt;(__x-&gt;__parent_);
   }
  </code></pre>
  
  <p>I doubt the if is redundant as it has been there for at least two decades (since the SGI days).</p>