CODEWITHSUNDEEP
c++pointersmemory-managementstl
intrigued_66
intrigued_66

Reputation: 17248

Where is the data of this struct located in memory?

I am looking at the GCC source code of std::set in stl_tree.h and there is this:

  enum _Rb_tree_color { _S_red = false, _S_black = true };

  struct _Rb_tree_node_base
  {
    typedef _Rb_tree_node_base* _Base_ptr;
    typedef const _Rb_tree_node_base* _Const_Base_ptr;

    _Rb_tree_color  _M_color;
    _Base_ptr       _M_parent;
    _Base_ptr       _M_left;
    _Base_ptr       _M_right;

    static _Base_ptr
    _S_minimum(_Base_ptr __x)
    {
      while (__x->_M_left != 0) __x = __x->_M_left;
      return __x;
    }

    static _Const_Base_ptr
    _S_minimum(_Const_Base_ptr __x)
    {
      while (__x->_M_left != 0) __x = __x->_M_left;
      return __x;
    }

    static _Base_ptr
    _S_maximum(_Base_ptr __x)
    {
      while (__x->_M_right != 0) __x = __x->_M_right;
      return __x;
    }

    static _Const_Base_ptr
    _S_maximum(_Const_Base_ptr __x)
    {
      while (__x->_M_right != 0) __x = __x->_M_right;
      return __x;
    }
  };

The three pointer data members:

    _Base_ptr       _M_parent;
    _Base_ptr       _M_left;
    _Base_ptr       _M_right;

assuming the default allocator, would the data pointed to by these pointers be randomly allocated on the heap?

UPDATE:

@Jeff I am trying to figure out, looking at this code:

struct _Rb_tree_impl : public _Node_allocator
        {
      _Key_compare      _M_key_compare;
      _Rb_tree_node_base    _M_header;
      size_type         _M_node_count; // Keeps track of size of tree.
           .
           .
           .

Would _M_node_count and _M_header._M_left be in separate cache lines? They are referenced here:

const_iterator begin() const _GLIBCXX_NOEXCEPT
{ 
   return const_iterator(static_cast<_Const_Link_type>(this->_M_impl._M_header._M_left));
}

  size_type size() const _GLIBCXX_NOEXCEPT 
  { 
      return _M_impl._M_node_count; 
  }

Upvotes: 1

Views: 959

Answers (1)

aschepler
aschepler

Reputation: 72376

The g++ library actually uses that _Rb_tree_node_base type for two different purposes:

  1. The nodes of the red-black tree. One object of a type derived from _Rb_tree_node_base is allocated on the heap for each element in the container.

    a. _M_color is an enum declaring the node red or black for red-black tree algorithms.

    b. _M_parent points at the parent node, or if the node is the root, points at the tree's "header" (see below).

    c. _M_left points at the left child node, or null if there is none.

    d. _M_right points at the right child node, or null if there is none.

    e. Another member in the derived class contains the actual container element.

  2. The "header", which is the subobject _M_header inside the actual container object.

    a. _M_color is always red (which helps some iterator algorithms).

    b. _M_parent points at the root node, or is null if the container is empty.

    c. _M_left points at the first node in sort order, or at the header itself if the container is empty.

    d. _M_right points at the last node in sort order, or at the header itself if the container is empty.

An iterator which is "past-the-end" also points at the container's header.

So to (almost) answer your question, c._M_node_count and c._M_header._M_left are both subobjects of c. But if c is not empty, the data pointed to by c._M_header._M_left is outside of c and was allocated by c's allocator.

Upvotes: 3

Related Questions