Trouble understanding libstdc++'s Red-black tree iterators

Question

I'm trying to implement iterators for a Ternary Search Tree, and because TSTs are very similar to BSTs, I thought I'd look at libstdc++'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.

Here's the code from the latest GCC, taken from the GitHub mirror:

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;
}

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 if clause:

if (__x->_M_right != __y)
  __x = __y;

How could this condition ever evaluate to false? __x needs to surpass __y for this happen, and that does not seem possible looking at the while loop. I think it might be false if the tree were a threaded tree, but the nullptr checks at the first if clause seem to suggest otherwise. Also, removing the if clause and just writing __x = __y; in my code does not seem to break anything.

What is going on here?

Edit:

This is the code for Clang's libc++. It seems as though the same code is not guarded by an if this time:

 template <class _EndNodePtr, class _NodePtr>
 inline _LIBCPP_INLINE_VISIBILITY
 _EndNodePtr
 __tree_next_iter(_NodePtr __x) _NOEXCEPT
 {
     if (__x->__right_ != nullptr)
         return static_cast<_EndNodePtr>(__tree_min(__x->__right_));
     while (!__tree_is_left_child(__x))
         __x = __x->__parent_unsafe();
     return static_cast<_EndNodePtr>(__x->__parent_);
 }

I doubt the if is redundant as it has been there for at least two decades (since the SGI days).

Answer 1

EASTL uses a similar eastl::RBTreeIncrement based on the HP STL tree functions:

/// RBTreeIncrement
/// Returns the next item in a sorted red-black tree.
///
EASTL_API rbtree_node_base* RBTreeIncrement(const rbtree_node_base* pNode)
{
    if(pNode->mpNodeRight) 
    {
        pNode = pNode->mpNodeRight;

        while(pNode->mpNodeLeft)
            pNode = pNode->mpNodeLeft;
    }
    else 
    {
        rbtree_node_base* pNodeTemp = pNode->mpNodeParent;

        while(pNode == pNodeTemp->mpNodeRight) 
        {
            pNode = pNodeTemp;
            pNodeTemp = pNodeTemp->mpNodeParent;
        }

        if(pNode->mpNodeRight != pNodeTemp)
            pNode = pNodeTemp;
    }

    return const_cast<rbtree_node_base*>(pNode);
}

Here, the goal of the

while(pNode == pNodeTemp->mpNodeRight) 
{
    pNode = pNodeTemp;
    pNodeTemp = pNodeTemp->mpNodeParent;
}
    
if(pNode->mpNodeRight != pNodeTemp)
    pNode = pNodeTemp;

is to obtain the root node of the smallest subtree containing the current node, pNode, in its left branch, or the sentinel node if such subtree does not exist.

Graph/node-like containers (e.g., doubly linked list, red-black tree, etc.) use sentinel nodes for implementing (c)end member methods in such a way that end() - 1 has correct semantics, and furthermore exploit them to remove edge cases (or move the edge cases from one algorithm to another).

EASTL defines its sentinel, mAnchor, in its eastl::rbtree as follows:

We do the conventional trick of assigning begin() (left-most rbtree node) to mpNodeLeft, assigning 'end() - 1' (a.k.a. rbegin()) to mpNodeRight, and assigning the tree root node to mpNodeParent.

E.g., if there is only one node in the red-black tree the left child, right child and parent node of the sentinel node will all point to that single node.

This means that for incrementing the root node without a right child node, we will take the else branch in eastl::RBTreeIncrement and end up with pNode being equal to the sentinel node after the while-loop, which is the intended result of the increment. The condition of the following if statement will be false because pNodeTemp will be equal to the parent of the sentinel node which is the root node itself, while pNode->mpNodeRight will be equal to the right child of the sentinel node which is the root node as well.