Question about segmentation fault on std::stack push

Question

I am working on a octree traversal algorithm. The current implementation uses a std::queue for such purpose, working flawlessly. However, I would like to use for such traversal a std::stack, as a depth first search will give better performance, avoiding testing non needed nodes.

However, when changing from one structure to another, I start getting segmentation faults on the push() function. Here is the stack report from gdb:

0x00005555555ae28d in __gnu_cxx::new_allocator<voxelizer::Node*>::construct<voxelizer::Node*, voxelizer::Node* const&> (this=0x7fffffffd7f0, __p=0x5555559abde8, __args#0=<error reading variable>)
    at /usr/include/c++/7/ext/new_allocator.h:136
136     { ::new((void *)__p) _Up(std::forward<_Args>(__args)...); }
(gdb) up
#1  0x00005555555acd1c in std::allocator_traits<std::allocator<voxelizer::Node*> >::construct<voxelizer::Node*, voxelizer::Node* const&> (__a=..., __p=0x5555559abde8, __args#0=<error reading variable>)
    at /usr/include/c++/7/bits/alloc_traits.h:475
475     { __a.construct(__p, std::forward<_Args>(__args)...); }
(gdb) up
#2  0x00005555555ab63e in std::deque<voxelizer::Node*, std::allocator<voxelizer::Node*> >::push_back (this=0x7fffffffd7f0, __x=<error reading variable>) at /usr/include/c++/7/bits/stl_deque.h:1547
1547            _Alloc_traits::construct(this->_M_impl,
(gdb) up
#3  0x00005555555aa29f in std::stack<voxelizer::Node*, std::deque<voxelizer::Node*, std::allocator<voxelizer::Node*> > >::push (this=0x7fffffffd7f0, __x=<error reading variable>)
    at /usr/include/c++/7/bits/stl_stack.h:226
226       { c.push_back(__x); }

I could not get my head around why, so I created a minimal, verifiable example where I could get rid of possible errors caused by any other part of the system. I reproduced the cotree Node structure, and created a small tree to traverse:

#include <iostream>
#include <stack>
#include <utility>

using namespace std;

// ==============================================================

class TestClass
{
  public:
    // Default constructor
    TestClass()
      : d(0)
      , children(nullptr)
    {
    }

    // Depth based constructor
    TestClass(int d_)
     : d(d_)
     , children(nullptr)
    {
      if(d > 0)
      {
        children = new TestClass*[8];
        for(int i = 0; i < 8; i++)
        {
          children[i] = new TestClass(d - 1);
        }
      }
    }

    // Copy  constructor
    TestClass(const TestClass & other_)
     : d(0)
     , children(nullptr)
    {
      _copy(other_);
    }

    // Move constructor
    TestClass(TestClass && other_)
      : d(0)
      , children(nullptr)
    {
      _move(std::move(other_));
    }

    // Destructor
    ~TestClass()
    {
      _clearChildren();
    }

    // Copy assignment operator
    TestClass & operator= (const TestClass & other_)
    {
      _copy(other_);
      return *this;
    }

    // Move assignment operator
    TestClass & operator= (TestClass && other_)
    {
      _move(std::move(other_));
      return *this;
    }

    int depth()
    {
      return d;
    }

    TestClass ** getChildren()
    {
      return children;
    }

  private:
    void _clearChildren()
    {
      if(children != nullptr)
      {
        for(int i = 0; i < 8; i++)
        {
          delete children[i];
        }

        delete[] children;
        children = nullptr;
      }
    }

    void _copy(const TestClass & other_)
    {
      d = other_.d;

      _clearChildren();
      if(other_.children != nullptr)
      {
        children = new TestClass*[8];
        for(int i = 0; i < 8; i++)
        {
          children[i] = new TestClass(*(other_.children[i]));
        }
      }
    }

    void _move(TestClass && other_)
    {
      d = other_.d;

      _clearChildren();
      children = std::move(other_.children);
    }

  private:
    int d;
    TestClass ** children;
};

// ==============================================================

typedef TestClass * TestClassPtr;

// ==============================================================

int main(int argc, char ** argv)
{

  TestClassPtr test = new TestClass(5);

  stack<TestClassPtr> s;
  s.push(test);

  while(!s.empty())
  {
    TestClassPtr & next = s.top();
    s.pop();

    cout << "On depth " << next->depth() << endl;

    if(next->getChildren() != nullptr)
    {
      std::cout << "Adding children" << std::endl;
      for(int i = 0; i < 8; i++)
      {
        if(next->getChildren()[i]->getChildren() != nullptr)
        {
          s.push(next->getChildren()[i]);
        }
      }
    }
  }

  cout << "Done" << endl;

  return 0;
}

By running it I was able to reproduce the problem, in the push() method as well:

On depth 5
Adding children
On depth 3
Adding children
On depth 1
Adding children
Segmentation fault

So I went on to revising the documentation. Note that I'm using C++11. The requirements for a default std::stack can be inherited from the requirements of using a std::deque, as it is the default container used. Since C++11, the main requirement is to be a complete type and Erasable I made sure the destructor was accessible. Also, for the sake of safe proofing, I implemented a default constructor, copy constructor, move constructor, copy assignment, and move assignment.

So I believe my class is Erasable, but perhaps not complete. By modifying the traverse loop in the example and adding the "SAFE PROOF LINE" if:

if(next->getChildren() != nullptr)
{
  std::cout << "Adding children" << std::endl;
  for(int i = 0; i < 8; i++)
  {
    // SAFE PROOF LINE
    if(next->getChildren()[i]->getChildren() != nullptr)
    {
      s.push(next->getChildren()[i]);
    }
  }
}

I was able to get rid of the segmentation fault. The nodes which this line discard are the leaf nodes, which does not have children and, thus, their children variable is a nullptr.

My questions:

• Does this means a nullptr pointer makes a type incomplete?

• The point of using this raw memory double pointer is to safe as much memory as possible, is there anyway I can make it work without having to substitute it for a stack array or a std::vector?

Thanks.

Answer 1

gdb says that the push argument is invalid:

push (this=0x7fffffffd7f0, __x=<error reading variable>)

Answer 2

Seems to go wrong right from the start

while(!s.empty())
{
    TestClassPtr & next = s.top();
    s.pop();

next is a reference to the object on the top of the stack, but the very next line removes that object, so the reference becomes invalid.

Simple answer is to not use a reference and just copy the top of the stack.

while(!s.empty())
{
    TestClassPtr next = s.top();
    s.pop();