12

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.

Derek Tu
  • 157
  • 1
  • 7

4 Answers4

17

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));
  }
Massa
  • 8,647
  • 2
  • 25
  • 26
  • Thanks a lot, Massa. I think I need to download the source code of gcc. :) – Derek Tu Jun 17 '13 at 15:52
  • For bonus points, how does the increment function fit into the red-black algorithm? – interestedparty333 Mar 29 '19 at 00:52
  • 1
    @ragerdl it seems that "increment" is c++ speak for "iterator::operator++", which would translate to "sibling" on https://en.wikipedia.org/wiki/Red%E2%80%93black_tree notice that "decrement" is the reverse operation (point to my antecessor sibling) that is not defined on the wikipedia page pointed. – Massa Mar 31 '19 at 20:04
  • 4
    Looking at the second `if` statement: how could `__x->_M_right` ever be equal to `__y` (i.e. its grandparent) ? – user2023370 Apr 16 '20 at 19:32
  • GitHub mirror: https://github.com/gcc-mirror/gcc/blob/master/libstdc%2B%2B-v3/src/c%2B%2B98/tree.cc – kevinarpe Jun 13 '20 at 11:54
  • 1
    @user2023370 I've been also complicated with this condition. I think that's some kind of cunning loophole. As you can see in the while statement above, `x` may "scramble up" to a root, but `__y = __y->_M_parent`. How come you can check `__x == __y->_M_right` if `x` is a root? It means a parent of a root isn't `nullptr`? It seems to me that a parent of a root is its left child (perhaps, I am not sure) – DisplayName Jan 11 '21 at 21:55
  • @AryatArifullin there are some invariants you are overlooking; – Massa Jan 23 '21 at 18:22
  • 2
    @user2023370 If you look at the source of the opposing function, _Rb_tree_decrement(), you actually find the following code there: `if (... __x->_M_parent->_M_parent == __x)`. So yes, towards the root, the grandparent of an element can be that element itself. This is probably to maintain special pointers to the first and last element of the tree, so that `begin()`, `end` and `std::prev(end)` are all efficient and don't need to sift through the tree to find the first or last element, respectively. – Kai Petzke May 06 '21 at 20:04
  • 2
    @user2023370 By looking at `_Rb_tree_insert_and_rebalance()`, one can see, that `__header._M_parent` actually refers the root node, while `__header._M_left` and `__header._M_right` refer to the leftmost node (= `begin()`) and the rightmost node (= `std::prev(end())`) respectively. The `__header()` node itself represents the `end()` iterator. The special condition, that you have seen, is probably there, so that `operator++` and `operator--` actually don't go past the beginning/end. – Kai Petzke May 06 '21 at 20:13
3

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.

Arne Mertz
  • 24,171
  • 3
  • 51
  • 90
  • 3
    OP is obviously using the stdlibc++ implementation shipping with GCC. – Konrad Rudolph Jun 17 '13 at 15:25
  • Great thanks, Arne, your answer hit the point ("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"). :) – Derek Tu Jun 17 '13 at 15:51
2

It will be in the library's source code, which you probably don't have.

It looks like you're looking at the GNU library's headers, so here would be a good place to start looking for the source.

Mike Seymour
  • 249,747
  • 28
  • 448
  • 644
0

as the highest score answer, the implement of the function is in 'tree.cc'. and as for the second 'if' statement, we need to notice the standard structure of an ordered binary tree in stl. we maintain rb_tree_header to manage the root, min, max of a tree. when only one node exists in rb_tree, notice that: {_header.parent = _root, _root.parent = _header, _header.left = _root, _header.right = _root}. so we can get the reason of 2nd 'if' statement.

1nchy
  • 1