1

I'm trying to create a linked list within RAII spirit and I'm getting crashes inside a destructor where I call the destruct of an object of the same class. I get a stack overflow but only if the linked list is filled up to some number. Code:

struct Node
{
    static int created,deleted;

    Node* next;
    Node () : next(NULL) { created++; }

    ~Node()
    {
        deleted++;

        if(next)
            delete next;
    }
};

int Node::created = 0;
int Node::deleted = 0;

class LL
{
    Node root;
    Node* cur;

    public:

        LL() : cur(&root) { }

        void add()
        {
            this->cur = this->cur->next = new Node;
        }
};

Now, this code does NOT crash:

{
    LL l;

    for(int i=1;i<=1000;i++)
        l.add();
}

printf("Created %d, Deleted %d\n",Node::created,Node::deleted);

But this one does:

{
    LL l;

    for(int i=1;i<=5000;i++)
        l.add();
}

printf("Created %d, Deleted %d\n",Node::created,Node::deleted);

Why does it crash and how should it be fixed?

user246100
  • 670
  • 1
  • 11
  • 20
  • Both your classes are violating the [Rule of Three](http://stackoverflow.com/questions/4172722/what-is-the-rule-of-three). And `delete NULL;` is a NOP, there's no need to check for NULL. – Praetorian Jan 24 '14 at 02:57
  • 4
    By calling `delete next;` from the `Node` destructor, this call is actually recursive. When there are too many objects in the list, the recursive nature of the destructor will cause a stack overflow. – Chad Jan 24 '14 at 02:58
  • possible duplicate of [RAII-style C++ class for linked list Nodes](http://stackoverflow.com/questions/11795035/raii-style-c-class-for-linked-list-nodes) – OneOfOne Jan 24 '14 at 02:59
  • I understand the recursion potential but that's why I check if "next is null". I don't understand how it works ok for 1000 cases but not for 5000. Because it should be an infinite loop (to fail) anyway right? Also, the print of created vs deleted is correct. – user246100 Jan 24 '14 at 03:07
  • OneOfOne, I'm using a solution similar to the one in the thread you pointed, but I think still this is relevant because I would like to understand exactly the reason for the crash. – user246100 Jan 24 '14 at 03:08
  • @user246100 Stack size is finite - yours seems to be capped somewhere between 1000 and 5000 stack frames in size. – Casey Jan 24 '14 at 03:12
  • Casey, the thing is: the stack is not being filled undefinetely because otherwise the code would crash for all cases. And the code performs the exact number of deletions it should. So what is happening "behind the curtains" to provoke the stack fill? – user246100 Jan 24 '14 at 03:15

2 Answers2

2

Let's try this again.

In the destructor of Node you delete the pointer, which calls the destructor of the next Node, etc. This occurs recursively. You're simply running out of stack space.

Mark Ransom
  • 299,747
  • 42
  • 398
  • 622
  • Mark, as I said above, I understand the recursion potential (I made it on purpose), what I don't understand is: if there isn't an infinite recursion, how a finite big filling of the stack is happening? The code performs the correct number of deletions. In other words, what is the part of this recursion that is wrong? – user246100 Jan 24 '14 at 03:18
  • @user246100 the stack probably isn't as big as you think it is. There's nothing technically wrong with the recursion, you're just allowing it to get too deep. – Mark Ransom Jan 24 '14 at 03:25
  • @user246100: Because the stack is so small that a finite number of recursions are enough to overflow it. – Siyuan Ren Jan 24 '14 at 04:15
-1

Reading and writing a variable in the same statement is probably not a good idea.

Change this line:

        this->cur = this->cur->next = new Node;

Too

        cur->next = new Node;  // Add node
        cur       = cur->next; // Move end marker.

Also this is not needed.

        if(next)
            delete next;

Just do:

        delete next;
Martin York
  • 257,169
  • 86
  • 333
  • 562