Memory leak in trivial stack implementation.

Question

I'm decently experienced with Python and Java, but I recently decided to learn C++. I decided to make a quick integer stack implementation, but it has a massive memory leak that I can't understand. When I pop the node, it doesn't seem to be releasing the memory even though I explicitly delete the old node upon poping it. When I run it, it uses 150mb of memory, but doesn't release any of it after I empty the stack. I would appreciate any help since this is my first foray into a language without garbage collection. This was compiled with gcc 4.3 on 64-bit Kubuntu.

 //a trivial linked list based stack of integers

#include <iostream>
using namespace std;

class Node
{
    private:
        int num;
        Node * next;
    public:
        Node(int data, Node * next);
        int getData();
        Node * getNext();
};
Node::Node(int data, Node * next_node)
{
    num = data;
    next = next_node;
}
inline int Node::getData()
{
    return num;
}
inline Node* Node::getNext()
{
    return next;
}


class Stack
{
    private:
        unsigned long int n;
        Node * top;
    public:
        Stack(int first);
        Stack();
        void push(int data);
        int pop();
        int peek();
        unsigned long int getSize();
        void print();
        void empty();
};
Stack::Stack(int first)
{
    Node first_top (first, NULL);
    top = &first_top;
    n = 1;
}
Stack::Stack()
{
    top = NULL;
    n = 0;
}
void Stack::push(int data)
{
    Node* old_top = top;
    Node* new_top = new Node(data,old_top);
    top = new_top;
    n++;
}
int Stack::pop()
{
    Node* old_top = top;
    int ret_num = old_top->getData();
    top = old_top->getNext();
    delete old_top;
    n--;
    return ret_num;
}
inline int Stack::peek()
{
    return top->getData();
}
inline unsigned long int Stack::getSize()
{
    return n;
}
void Stack::print()
{
    Node* current = top;
    cout << "Stack: [";
    for(unsigned long int i = 0; i<n-1; i++)
    {
        cout << current->getData() << ", ";
        current = current->getNext();
    }
    cout << current->getData() << "]" << endl;
}
void Stack::empty()
{
    unsigned long int upper = n;
    for(unsigned long int i = 0; i<upper; i++)
    {
        this->pop();
    }
}

Stack createStackRange(int start, int end, int step = 1)
{
    Stack stack = Stack();
    for(int i = start; i <= end; i+=step)
    {
        stack.push(i);
    }
    return stack;
}

int main()
{
    Stack s = createStackRange(0,5e6);
    cout << s.peek() << endl;
    sleep(1);
    cout << "emptying" <<endl;
    s.empty();
    cout << "emptied" <<endl;
    cout << "The size of the stack is " << s.getSize()<<endl;
    cout << "waiting..." << endl;
    sleep(10);
    return 0;
}

Answer 1

How do you KNOW the memory isn't being released? The runtime library will manage allocations and may not release the memory back to the OS until the program terminates. If that's the case, the memory will be available for other allocations within your program during its execution.

However.... you seem to have other problems. My C++ is really rusty since I've been doing Java for 15 years, but in your Stack::Stack constructor you're allocating a Node instance on the system stack and then storing a reference to it in your "Stack". That Node instance goes out of scope when the constructor ends, leaving a dangling pointer.

Answer 2

Stack::Stack(int first)
{
    Node first_top (first, NULL);
    top = &first_top;
    n = 1;
}

This is wrong , you cant assign address of a local object to class member( top ) , since local objects get destroyed when function returns.

Create a node on heap rather than stack , do something like this :

 Stack::Stack(int first)
    {
        top = new Node(first, NULL);
        n = 1;
    }

And Make the concept of link list clear and use pen and paper if you can do so.

Your Stack::Push(int) operation seems buggy check it out what you have forget to do.

My suggestion is try to implement generic stack with the help of template ,so it will work for all data type .

Answer 3

After poring over the code, I couldn't find the leak so I compiled it and ran it in a debugger myself. I agree with Jim Garrision - I think you're seeing an artifact of the runtime rather than an actual leak, because I'm not seeing it on my side. The issues pointed out by NickLarsen and smith are both actual issues that you want to correct, but if you trace the code through, neither should actually be causing the problem you describe. The code smith singles out is never called in your example, and the code Nick singles out would cause other issues, but not the one you're seeing.

Answer 4

When createStackRange() returns it'll return a copy of the Stack using the compiler-generated copy constructor which just makes a bitwise copy (i.e., it'll copy the pointer to the first node and the size.)

More seriously, you're missing the destructor for the Stack class. Ideally you'd have it walk the list and call delete on each Node. The Stack object created on the processor stack will automatically be cleaned up automatically when main() exits, but without a destructor, the nodes will still be allocated when the program ends. You probably want something like this for it:

Stack::~Stack()
{
    while ( top )
    {
        Next *next = top->getNext();
        delete top;
        top = next;
    }
}

The way to think of it is that the C++ compiler will automatically generate copy constructors and destructors for you, but they're normally shallow. If you need deep behavior you've got to do it implement it yourself somewhere.

Answer 5

Creat a stub to test your code and user Memory Analysis tool like "Valgrind". This will find out memory leaks and corruptions for you.

check man-pages for more information.

Answer 6

Note that you should only roll your own stack for educational purposes. For any real code, you should use the stack implementation that comes with the C++ standard library...