Malloc Error 2372 When Using Two Seperate Instances Of One Class

Question

for clarity this bug is from a program for a school assignment but the bug itself is related to problems with malloc rather than understanding the assignment. In the assignment I am only using one instance of this class so the question is mostly for future reference. The problem I am running into occurs when I utilize 2 different instances of my Heap class declared here:

a4.h

    #include <iostream>

    using namespace std; 

    /*
            Class Declarations
    ********************************************************************
    */

    // A Heap implemented with a growing array

    class Heap{

    public:
        Heap(); 
        ~Heap(); 
        void insert ( int item ); 
        int remove(); 
        void printheap(); 

    private:
        void trickleup   ( int pos ); 
        void trickledown ( int pos ); 
        void swap    ( int pos1 , int pos2 ); 

        int* A; 
        int size; 
        int capacity; 
    }; 




    /*
            Class Methods
    *********************************************************************
    */

    // For Heap

    Heap::Heap(){
        A = NULL; 
        size = 0; 
        capacity = 0; 
    }

    Heap::~Heap(){

        delete A; 
    }

    void Heap::insert ( int item ){

        if ( size == capacity ){
            int* newpointer = new int[(capacity*2)+1]; 
            for (int i = 0; i < size; i++) newpointer[i] = A[i]; 
            delete A; 
            A = newpointer; 
        }

        A[size] = item; 
        size += 1; 
        trickleup (size-1); 
        return; 
    }

    int Heap::remove(){

        size -= 1; 
        int temp = A[0]; 
        swap ( 0 , size ); 
        trickledown (0); 
        return temp; 
    }

    void Heap::printheap(){

        cout << "Root -> [ "; 
        for (int i = 0; i <  size; i++) cout << A[i] << " "; 
        cout << "]\n"; 
        return; 
    }

    void Heap::trickleup ( int pos ){

        int p0 = pos; 
        int p1 = (pos-1)/2; 

        if ( p0 == 0 ){
            trickledown (0); 
            return; 
        }
        if ( A[p0] > A[p1] ){
            swap ( p0 , p1 ); 
            trickleup ( p1 ); 
        }
        else trickledown (p0); 
        return; 
    }

    void Heap::trickledown ( int pos ){

        int p0 = pos; 
        int p1 = (2*pos)+1; 
        int p2 = (2*pos)+2; 

        if ( p1 >= size ) return; 
        if ( p2 >= size ){
            if ( A[p0] < A[p1] ) swap ( p0 , p1 ); 
            return; 
        }

        bool f1 = ( A[p0] < A[p1] );    
        bool f2 = ( A[p0] < A[p2] );    

        if ( (A[p1] >= A[p2]) && f1 ){
            swap ( p0 , p1 ); 
            trickledown ( p1 ); 
        }
        else if ( (A[p1] < A[p2]) && f2 ){
            swap ( p0 , p2 ); 
            trickledown ( p2 ); 
        }
        return; 
    }

    void Heap::swap ( int pos1 , int pos2 ){

        int temp = A[pos1]; 
        A[pos1] = A[pos2]; 
        A[pos2] = temp; 
        return; 
    }

The only time I use new to request memory is in the insert function.

The problem occurs when I run my test program compiled from htest.cpp and run both the sections for the h1 test and the h2 test. If I only run one of the two tests the problem does not occur. Here is the test program:

htest.cpp

    #include <cstdlib>
    #include <iostream> 
    #include "a4.h"

    using namespace std; 

    int main(){

        cout << "\nCreating h1 And h2\n\n"; 

        Heap* h1 = new Heap(); 
        Heap* h2 = new Heap(); 

        cout << "\nAdding 0-6 To h1\n\n"; 

        h1->insert ( 0 ); cout << "h1: "; h1->printheap(); 
        h1->insert ( 1 ); cout << "h1: "; h1->printheap(); 
        h1->insert ( 2 ); cout << "h1: "; h1->printheap(); 
        h1->insert ( 3 ); cout << "h1: "; h1->printheap(); 
        h1->insert ( 4 ); cout << "h1: "; h1->printheap(); 
        h1->insert ( 5 ); cout << "h1: "; h1->printheap(); 
        h1->insert ( 6 ); cout << "h1: "; h1->printheap(); 

        cout << "\nRemoving All Elements From h1\n\n"; 

        cout << "Removed: " << h1->remove(); 
        cout << "  h1: "; h1->printheap(); 
        cout << "Removed: " << h1->remove(); 
        cout << "  h1: "; h1->printheap(); 
        cout << "Removed: " << h1->remove(); 
        cout << "  h1: "; h1->printheap(); 
        cout << "Removed: " << h1->remove(); 
        cout << "  h1: "; h1->printheap(); 
        cout << "Removed: " << h1->remove(); 
        cout << "  h1: "; h1->printheap(); 
        cout << "Removed: " << h1->remove(); 
        cout << "  h1: "; h1->printheap(); 
        cout << "Removed: " << h1->remove(); 
        cout << "  h1: "; h1->printheap(); 

        cout << "\nAdding 6-0 To h2\n\n"; 

        h2->insert ( 6 ); cout << "h2: "; h2->printheap(); 
        h2->insert ( 5 ); cout << "h2: "; h2->printheap(); 
        h2->insert ( 4 ); cout << "h2: "; h2->printheap(); 
        h2->insert ( 3 ); cout << "h2: "; h2->printheap(); 
        h2->insert ( 2 ); cout << "h2: "; h2->printheap(); 
        h2->insert ( 1 ); cout << "h2: "; h2->printheap(); 
        h2->insert ( 0 ); cout << "h2: "; h2->printheap(); 

        cout << "\nRemoving All Elements From h2\n\n"; 

        cout << "Removed: " << h2->remove(); 
        cout << "  h2: "; h2->printheap(); 
        cout << "Removed: " << h2->remove(); 
        cout << "  h2: "; h2->printheap(); 
        cout << "Removed: " << h2->remove(); 
        cout << "  h2: "; h2->printheap(); 
        cout << "Removed: " << h2->remove(); 
        cout << "  h2: "; h2->printheap(); 
        cout << "Removed: " << h2->remove(); 
        cout << "  h2: "; h2->printheap(); 
        cout << "Removed: " << h2->remove(); 
        cout << "  h2: "; h2->printheap(); 
        cout << "Removed: " << h2->remove(); 
        cout << "  h2: "; h2->printheap(); 

        cout << "\n"; 

        return 0; 
    }

After compiling this program and running it (with the GNU C++ compiler) I get the following output:

Output

    Creating h1 And h2


    Adding 0-6 To h1

    h1: Root -> [ 0 ]
    h1: Root -> [ 1 0 ]
    h1: Root -> [ 2 0 1 ]
    h1: Root -> [ 3 2 1 0 ]
    h1: Root -> [ 4 3 1 0 2 ]
    h1: Root -> [ 5 3 4 0 2 1 ]
    h1: Root -> [ 6 3 5 0 2 1 4 ]

    Removing All Elements From h1

    Removed: 6  h1: Root -> [ 5 3 4 0 2 1 ]
    Removed: 5  h1: Root -> [ 4 3 1 0 2 ]
    Removed: 4  h1: Root -> [ 3 2 1 0 ]
    Removed: 3  h1: Root -> [ 2 0 1 ]
    Removed: 2  h1: Root -> [ 1 0 ]
    Removed: 1  h1: Root -> [ 0 ]
    Removed: 0  h1: Root -> [ ]

    Adding 6-0 To h2

    htest: malloc.c:2372: sysmalloc: Assertion `(old_top == (((mbinptr) (((char *) &((av)->bins[((1) - 1) * 2])) - __builtin_offsetof (struct malloc_chunk, fd)))) && old_size == 0) || ((unsigned long) (old_size) >= (unsigned long)((((__builtin_offsetof (struct malloc_chunk, fd_nextsize))+((2 *(sizeof(size_t))) - 1)) & ~((2 *(sizeof(size_t))) - 1))) && ((old_top)->size & 0x1) && ((unsigned long) old_end & pagemask) == 0)' failed.
    Aborted (core dumped)

I am wondering why the error appears as it doesn't seem like I am doing anything illegal with requesting memory. I would really appreciate it if someone could try to explain the problem clearly as I only have about one year of C++ experience.

*Edit: Changed the destructor Function to not delete size and capacity and added a delete A line to the insert function before re-sizing the array.

Answer 1

Sad that I didn't spot this one before. I'll throw myself onto my sword after answering.

Heap::insert never sets capacity. It stays 0, so inserts after the first do not trigger if (size == capacity) and do not resize A. As a result, A is run out of bounds and trashes the heap (the the memory heap, not the class Heap).

I recommend a small edit:

void Heap::insert(int item)
{
    if (size == capacity)
    {
        capacity = (capacity * 2) + 1; // Note: many tests have shown that 1.5 is a 
                                       // better expansion factor than 2.
        int* newpointer = new int[capacity];
        for (int i = 0; i < size; i++)
            newpointer[i] = A[i];
        delete A;
        A = newpointer;
    }

    A[size] = item;
    size += 1;
    trickleup(size - 1);
    return;
}

In addition

Heap* h1 = new Heap();
Heap* h2 = new Heap();

do not need to be dynamically allocated and can be defined as

Heap h1;
Heap h2;

Among other advantages temporary allocation brings, such as improved spacial locality, this does not require the programmer to delete h1 and h2, something that is currently not done.

Now if you will excuse me, I must find where I left my sword.