C++ Debug Assertion Failed

Question

I've written my own list class for practice, here it is:

#pragma once

#include <iostream>

using namespace std;

// A linked node structure.
template <typename T>
struct LinkedNode
{
    T data;
    LinkedNode<T>* next;
    LinkedNode<T>* prev;
};

// Class linked list.
template <typename T>
class LinkedList
{
public:

    // Constructor
    LinkedList()
    {
        mFirst = 0;
        mLast = 0;
    }

    LinkedList(const LinkedList& rhs)
    {
        mFirst = 0;
        mLast = 0;

        // Get a pointer to the first node of rhs.
        LinkedNode<T>* current = rhs.mFirst;

        // While not at the end of the rhs linked list.
        while( current != 0 )
        {
            insertLast( current->data );
            current = current->next;
        }
    }

    // Destructor
    ~LinkedList()
    {
        destroy();
    }

    // Overload
    LinkedList& operator=(const LinkedList& rhs)
    {
        // Check for self assignment
        if ( this == &rhs )
            return *this;

        // Get a pointer to the first node of rhs.
        LinkedNode<T>* current = rhs.mFirst;

        // While not at the end of the rhs linked list.
        while( current != 0 )
        {
            insertLast( current->data );
            current = current->next;
        }

        // Chain assignments a = b = c = d
        return *this;
    }

    // Check if list is empty.
    bool isEmpty()
    {
        if( mFirst == 0 && mLast == 0 )
            return true;
        else
            return false;
    }

    // Return first and last nodes.
    LinkedNode<T>* getFirst() { return mFirst; };
    LinkedNode<T>* getLast()  { return mLast;  };

    void insertFirst(T tData);
    void insertLast(T tData);
    bool insertAfter(T tKey, T tData);
    void removeFirst();
    void removeLast();
    void remove(T removalCandidate);
    void destroy();

private:

    LinkedNode<T>* mFirst;
    LinkedNode<T>* mLast;
};

template <typename T>
bool LinkedList<T>::insertAfter(T tKey, T tData)
{
    if( isEmpty() ) return false;

    // Get a pointer to the front of the list
    LinkedNode<T>* current = mFirst;

    // Loop until we find the tKey (the value of the node to insert after)
    while( current->data != tKey )
    {
        // Hop to the next node.
        current = current->next;

        // Test if we reached the end, if we did we didn't find the node to insert after (tKey)
        if( current == 0 )
            return false;
    }

    // Allocate memory for the new node to insert.
    LinkedNode<T>* newNode = new LinkedNode<T>();
    newNode->data = tData;

    // Special case: Are we inserting after the last node?
    if( current == mLast )
    {
        newNode->next = 0;
        mLast = newNode;
    }
    // No, else link in new node after the current node.
    else
    {
        newNode->next = current->next;
        newNode->next->prev = newNode;
    }

    newNode->prev = current;
    current->next = newNode;

    return true;
}

template <typename T>
void LinkedList<T>::insertFirst(T tData)
{
    LinkedNode<T>* newNode = new LinkedNode<T>();
    newNode->data = tData;

    // If the list is empty, then this is the first and last node and doesn't have a previous pointer.
    if( isEmpty() )
        mLast = newNode;
    // If the list is not empty, the new node becomes the previous node of the current first node.
    else
        mFirst->prev = newNode;

    // The new node's next pointer is the old first pointer. May be null if this is the first node being added to the list.
    newNode->next = mFirst;

    //The new node becomes the first node.
    mFirst = newNode;   
}

template <typename T>
void LinkedList<T>::insertLast(T tData)
{
    LinkedNode<T>* newNode = new LinkedNode<T>();
    newNode->data = tData;

    if( isEmpty() )
        mFirst = newNode;
    else
        mLast->next = newNode;

    newNode->prev = mLast;

    mLast = newNode;
}

template <typename T>
void LinkedList<T>::removeFirst()
{

    if( !isEmpty() )
    {
        LinkedNode<T>* current = mFirst;

        if( mFirst == mLast )
        {
            mFirst->next = 0;
            mLast->prev = 0;
        }
        else
        {
            mFirst = current->next;
            mFirst->prev = 0;
        }

        delete current;
        current = 0;
    }   
}

template <typename T>
void LinkedList<T>::removeLast()
{
    if( !isEmpty() )
    {
        LinkedNode<T>* current = mLast;

        if( mFirst == mLast )
        {
            mFirst = 0;
            mLast = 0;
        }
        else
        {
            mLast = current->prev;
            mLast->next = 0;
        }

        delete current;
        current = 0;
    }
}

template <typename T>
void LinkedList<T>::remove(T removalCandidate)
{
    LinkedNode<T>* current = mFirst;

    if( isEmpty() )
    {
        cout << "List is empty!" << endl;
    }
    else
    {
        while( current->data != removalCandidate )
        {
            if( current->data == removalCandidate )
            {
                break;
            }
            current = current->next;
        }
    }

    if( current == mFirst )
        removeFirst();
    else if ( current == mLast )
        removeLast();
    else
    {
        // Create two linked nodes to access the next and prev nodes.
        LinkedNode<T>* left  = current->prev;
        LinkedNode<T>* right = current->next;

        left->next = right;
        right->prev = left;
    }

    delete current;
    current = 0;
}

template <typename T>
void LinkedList<T>::destroy()
{
    // Is there at least one node in the list?
    if( mFirst != 0 )
    {
        // Get a pointer to the first node.
        LinkedNode<T>* current = mFirst;

        // Loop until we reach the end of list.
        while( current != 0 )
        {
            // Save the current node.
            LinkedNode<T>* oldNode = current;

            // Move to next node.
            current = current->next;

            // Delete saved node.
            delete oldNode;
            oldNode = 0;
        }
    }

    mFirst = 0;
}

Then I have also written a stack and queue class, and I test them both to see whether a string is a palindrome. That all works. However when it runs the destroy method in the list class, it throws a: block type is valid(pHead->nBlockUse) error on the

delete oldNode;

line.

Queue code:

#pragma once

#include <iostream>
#include "LinkedList.h"

#include <cassert>

template <typename T>
class Queue
{
public:
    Queue(){};

    ~Queue()
    {
        mList.destroy();
    }

    T& getFirst()
    {
        assert( !isEmpty() );
        return mList.getFirst()->data;
    }

    bool isEmpty( void )
    {
        return mList.isEmpty();
    }

    void push( T newElement )
    {
        mList.insertLast( newElement );
    }

    void pop()
    {
        mList.removeFirst();
    }

private:
    LinkedList<T> mList;
};

Stack code:

#pragma once

#include <iostream>
#include "LinkedList.h"

#include <cassert>

template <typename T>
class Stack
{
public:
    Stack(){};

    ~Stack()
    {
        mList.destroy();    
    }

    T& getTopItem()
    {
        // Throw error if list is empty.
        assert( !isEmpty() );

        return mList.getLast()->data;
    }

    bool isEmpty( void )
    {
        return mList.isEmpty(); 
    }

    void push( T newElement )
    {
        mList.insertLast( newElement );
    }

    void pop()
    {
        mList.removeLast();
    }

private:
    LinkedList<T> mList;
};

Main code:

#include "Stack.h"
#include "Queue.h"
#include <iostream>
#include <string>
using namespace std;

int main()
{

    Stack<char> strStack;
    Queue<char> strQueue;

    cout << "Enter a string: ";
    string input = "";
    getline(cin, input);

    for( unsigned int i = 0; i < input.length(); ++i )
    {
        strStack.push( input[i] );
        strQueue.push( input[i] );
    }

    bool isPalindrome = true;

    // FIX PALINDROME AND ASSERTION FAIL

    for( unsigned int j = 0; j < input.length(); ++j )
    {
        if( strStack.getTopItem() != strQueue.getFirst() )
        {
            isPalindrome = false;
            break; // Exit for loop early.
        }

        // Get rid of next element out.
        strStack.pop();
        strQueue.pop();
    }

    cout << input << " is palindrome: " << isPalindrome << endl;
}

I'm not sure why, any help would be appreciated.

There is nothing inherently wrong with the function you posted. Please post a complete example that lets us reproduce the problem. — Bart van Ingen Schenau, Nov 13 '12 at 09:22
@Cypras Can't do anything more than guess unless you post the code that has the error. I would guess you are not following the rule of three, http://stackoverflow.com/questions/4172722/what-is-the-rule-of-three — john, Nov 13 '12 at 09:28
This error occurs when you `delete` something which is allocated on the stack instead of heap. Can you show how are you adding new nodes into the list? — sgarizvi, Nov 13 '12 at 09:29
Check [THIS](http://stackoverflow.com/questions/6397545/block-type-is-valid-phead-nblockuse-error) and [THIS](http://stackoverflow.com/questions/9460352/block-type-is-valid-phead-nblockuse-on-delete-command) I think you haven't created the destructor of the class `LinkedNode` — sgarizvi, Nov 13 '12 at 09:31

score 3 · Accepted Answer · answered Nov 13 '12 at 09:43

3

The problem is in the removeFirst function: When you remove the last node in the list (i.e. mFirst == mLast is true) you set the node link pointers to 0, and then you delete the node. Now both mFirst and mLast points to a deleted node!

Instead of setting the next and prev links to 0, you should set mFirst and mLast to 0. Just like you already do in removeLast.

answered Nov 13 '12 at 09:43

Some programmer dude

400,186
35
402
621

Thank you! I don't know why I did that..damnit! – Cypras Nov 13 '12 at 09:47

selbie · Answer 2 · 2012-11-13T09:41:41.477

2

Because you are not setting mFirst to NULL (0) right before the destroy() method returns. If you call destroy() more than once, you'll hit this kind of crt assertion as a result of attempting to delete a pointer twice. The queue class calls mList.destroy in its destructor, but the destructor of mList will call destroy again.

edited Nov 13 '12 at 09:41

answered Nov 13 '12 at 09:23

selbie

100,020
15
103
173

Destroy is called twice, once to delete the stacks list, and again to delete the queues list. – Cypras Nov 13 '12 at 09:25
1

If you are calling destroy more than once on the same instance of your class, then that is your bug. Set mFirst to NULL right before destroy returns. – selbie Nov 13 '12 at 09:27
Note - it almost always a good idea to assign a variable or class member to null if it has been deleted. – selbie Nov 13 '12 at 09:29
I am right. You are explicitly calling destroy in your queue class. But the linked list destructor also calls destroy. – selbie Nov 13 '12 at 09:40
So what do I need to do? Because I do the same in stack and that doesn't throw an error if I comment out all the queue code in main. – Cypras Nov 13 '12 at 09:42
The last line of destroy needs to set both mFirst and mLast to NULL. – selbie Nov 13 '12 at 09:44
@selbie Are you sure the code isn't already doing what you suggested? I see `mFirst = 0;` on the last line of the destroy method. – ChrisW Nov 13 '12 at 09:50
And I'm not sure why you say that mLast needs to be zeroed: just setting mFirst = 0 looks like it's sufficient to ensure the any next call to destroy will do nothing. – ChrisW Nov 13 '12 at 09:53
I added that after selbie suggested it, so do I even need queue and stack to call list destroy to delete mList or not? – Cypras Nov 13 '12 at 09:56

C++ Debug Assertion Failed

2 Answers2