What is the definition of _Rb_tree_increment in bits/stl_tree.h?

Question

I want to learn codes of the red-black tree in stl. And I found a function named _Rb_tree_increment in the file bits/stl_tree.h

it writes:

 143   _GLIBCXX_PURE _Rb_tree_node_base*
 144   _Rb_tree_increment(_Rb_tree_node_base* __x) throw ();

But I can not find the definition of this function. Anyone can help?

Thank you very much.

Answer 1

Like @Mike Seymour said, I found the definition on the library's source path, more precisely inside gcc-4.8.1/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;
  }

  _Rb_tree_node_base*
  _Rb_tree_increment(_Rb_tree_node_base* __x) throw ()
  {
    return local_Rb_tree_increment(__x);
  }

  const _Rb_tree_node_base*
  _Rb_tree_increment(const _Rb_tree_node_base* __x) throw ()
  {
    return local_Rb_tree_increment(const_cast<_Rb_tree_node_base*>(__x));
  }

Answer 2

That definition depends on what standard library you have. Differenc compiler vendors provide different implementations of the standard library with their compilers. It seems you have found a nontemplate function. That should be defined in some cpp and it will be shipped with the compiler in the lib file, so you can't access the code directly, because it won't be shipped with your compiler - it's simply not necessary.

If your compiler is a propietary compiler, e.g. from Microsoft or Borland, that's all you will get. If you have a gcc however, you got lucky: gcc is open source, and you can find the sources for the gcc implementation of the standard library online.