Data Destruction In C++

Question

So, for class I'm (constantly re-inventing the wheel) writing a bunch of standard data structures, like Linked Lists and Maps. I've got everything working fine, sort of. Insertion and removal of data works like a charm.

But then main ends, my list is deleted, it calls it's dtor and attempts to delete all data inside of it. For some reason, this results in a double free event.

All data is inserted into the list by these methods:

/*
Adds the specified data to the back of the list.
*/
template<typename T, class COMPFUNCTOR>
void List<T, COMPFUNCTOR>::append(T* d)
{
    if(tail != NULL)
    {//If not an empty list, simply alter the tail.
        tail->setNext(new ListNode<T>(d));
        tail = tail->getNext();
    }
    else
    {//If an empty list, alter both tail and head.
        head = tail = new ListNode<T>(d);
    }
    size++;
};

/*
Adds a copy of the specified data to the back of the list.
*/
template<typename T, class COMPFUNCTOR>
void List<T, COMPFUNCTOR>::append(const T& d)
{
    this->append(new T(d));
};

The first method assumes that it owns the data passed into it; the second copies data passed into it. Now, for main:

int main(int argc, char** argv)
{
    parser = new Arguments(argc, argv); //Uses a map<char, list<string>>; no direct  bugs, insertion works fine.
    if(parser->flagSet('f'))
    {
        printf("%s\n", parser->getArg('f').getFirst().str.c_str());
    }
    return 0;
}

This results in a stack dump, for a double free event. The list destructor is defined as follows:

/*
Destroys the List and all data inside it.
*/
template<typename T, class COMPFUNCTOR>
List<T, COMPFUNCTOR>::~List()
{
    while(head != NULL)
    {
        ListNode<T>* tmp = head; //Set up for iteration.
        head = head->getNext();
        if(tmp->getData() != NULL) //Delete this node's data then the node itself.
            delete tmp->getData();
        delete tmp;
    }
};

If I comment out either the list destructor or the code in main's if statement, the program runs fine. Now, I'm not sure where this double delete is coming from.

List is destroyed on the end of main, which results in it deleting the data inside of it; which is either owned or copied into it, and only copies ever come out of it (the only time list passes out pointers of it's data is when you remove it from the list).

Obviously, something is created on the stack in main, when parser->getArg('f').getFirst(); is called.

I read this as, (de-ref pointer to parser)->(get a reference of the linked list).(acquire a copy of the first element in list [an std::string]);

Deleting a pointer to parser is no big deal (In fact, I should probably delete that, oops); deleting a reference shouldn't be a big deal either (just a candied up pointer); and deleting a copy of the first element should be a non-issue. Where have I gone wrong? EDIT The code for ListNode is as follows:

    /*
    Create a ListNode with the specified neighbor.
    */
    template<typename T>
    ListNode<T>::ListNode(T* d, ListNode<T>::ListNode* neighbor)
    {
        data = d;
        next = neighbor;
    }

    /*
    Deletes the ListNode.
    */
    template<typename T>
    ListNode<T>::~ListNode()
    {
        next = NULL;
        if(data != NULL)
            delete data;
        data = NULL; 
    }

ListNodes only ever take pointers to their data, they only ever delete their data when they die with non-null data pointers. The List itself also only ever deletes stuff if it is non-null. All deleted data is set to NULL.

Oh, and the data right now is std::string, I have no control over it's copy constructor, but I would assume it's properly implemented.

Answer 1

You haven't posted the code for it, but my guess would be that ListNode's destructor is deleting its data, after you've already deleted it in List's destructor.

Answer 2

Check your copy ctor. If an argument is being copied by value, it would have to use the no-arg ctor and that call would be inserted by the compiler so you wouldn't know it was happening.

Try putting log statements in the copy contructor to see if it's being called when it shouldn't be.

Answer 3

Does the ListNode destructor also delete its data?

Edit: ah, now that you've posted your source - note that delete does not set to null... so your null test will still yield false.

Answer 4

It's not the source of your problem, but you don't have to check if something is NULL or not before you delete it. Calling delete on NULL is a no-op. I don't think you've made this error, but I've seen people write

if(data != NULL)
  delete data;

and think that the behavior is

if(data is properly allocated)
  delete data;

which is, of course, not true.

Answer 5

Did you honor the rule of three? Double deletion often happens when an object that is supposed to "manage a pointee" is copied. Either make your nodes noncopiable and nonassignable or define your own copy ctor and assignment operator "properly".

Answer 6

Looking at your ListNode class it is obvious that there is an ownership mismatch. It is a good rule of thumb for design that not only should every allocation be matched by a matching de-allocation but that these should be performed by at the same layer in the code or ideally by the same object. The same applies to any resource whose acquisition needs to be paired with a release.

It's obvious that this guideline isn't being followed here and that is a root of a lot of your issues.

    template<typename T>
    ListNode<T>::ListNode(T* d, ListNode<T>::ListNode* neighbor)
    {
        data = d;
        next = neighbor;
    }

    template<typename T>
    ListNode<T>::~ListNode()
    {
        next = NULL;
        if(data != NULL)
            delete data;
        data = NULL; 
    }

ListNode deletes something that it didn't allocate. While you allow for the possibility of a null data member, you are going to make things simpler if you don't allow this. If you want a list of optional items you can always use you're template with a smart pointer type or a boost::optional.

If you do this, and then make sure that your ListNode class always allocates and deallocates the copy of the item, you can then make the data member a T instead of a T*. This means that you can make your class something like this:

template<typename T>
class ListNode
{
public:

    explicit ListNode( const T& d )
        : data(d), next()
    {
    }

    T& getData()              { return data; }
    const T& getData() const  { return data; }
    ListNode* getNext() const { return next; }
    void setNext(ListNode* p) { next = p; }

private:
    ListNode* next;
    T data;
}

I've moved to using references for things which can't now be null. Also, everything that's owned is now a data member and things that that class doesn own (next) are referred to by pointer.

Of these two functions, I hope that the second was a private function because your destructor always assumes that the List (via a ListNode) owns the data pointer so having a public function which takes a raw pointer that doesn't take a copy is potentially dangerous.

template<typename T, class COMPFUNCTOR>
void List<T, COMPFUNCTOR>::append(T* d);

template<typename T, class COMPFUNCTOR>
void List<T, COMPFUNCTOR>::append(const T& d);

With the change to ListNode above we can implement the second of these without needing the help of the first quite simply.

template<typename T, class COMPFUNCTOR?
void List<T, COMPFUNCTOR>::append(const T& d)
{
    ListNode<T>* newNode = new ListNode<T>(d);

    if (!tail)
        tail->setNext( newNode );
    else
        head = newNode;

    tail = newNode;
    size++;
}

The destructor 'walk' for the List remains similar to what you have except there should be no attempt to manually delete the owned data of the ListNode, that happens automatically when you delete the ListNode itself.

Note: all my code is untested, it's for exposition only!