c++ pointer being freed was not allocated error

Question

I am practcing c++'s new/delete, hashfunction and linked.

I made a practice by myself.

I have a struct which is

typedef struct student
{
    int id;
    string fName;
    string lName;
    student * nextStudent;
}Student;

Then in main function, I define an array of student

Student * table = new Student [10];

I have my own hash function which takes the id, and change to 0-9. I want to add a student I do following

void addStudent(int studentId, string firstName, string lastName, Student  *table)
{
    // using hash function, convert the id into hashed id
    int hashedID = hashFunction( studentId );   

        Student * pointer = &table[hashedID];

        while(pointer->nextStudent !=NULL){
            pointer = pointer->nextStudent;
        }

        // once we reach to the student who has NULL in nextStudent
        // add student
        Student *tmp = new Student;
        tmp->id = studentId;
        tmp->fName = firstName;
        tmp->lName = lastName;
        tmp->nextStudent = NULL;

        // link
        pointer->nextStudent = tmp;

}

I tested it, it seems fine.

The problem is deletion. Since student variables are stored in dynamic memeory, I need to use delete.

The following is my code.

void deleteAll(Student *table, int len)
{
    for (int i = 0; i < len; i++)
    {
        Student* tmp = &table[i];

        // delete student info except the last one
        while ( tmp -> nextStudent !=NULL){
            Student* tmp2;
            tmp2 = tmp;
            tmp = tmp->nextStudent;
            delete tmp2;
         }
    }
}

I visited every student varialbes ane do the deletion. I cannot find any probelm in my deletion funtion...

This is what I got after run..

malloc: *** error for object 0x7f85f1404b18: pointer being freed was not allocated

I have no clue what I have done wrong.. Can you help me?

EDIT...

As you guys metion I added "delete [] table" in the main funtion.. Also, I remove "delete tmp" in deleteAll function; i think "delete [] table" will handle that part.

Still does not work..

By the way I forgot to added initTable function in the initial post. initTable initialize the table...

void initTable (Student *table, int len)
{
    for (int i = 0; i < len; ++i)
    {
        table[i].nextStudent = NULL;
    }
}

Thank you.

table[i] wasn't allocated individually, it was allocated as part of an array. All subsequent students in the linked list can be deleted with delete, but table[i] must only be deleted by deleting the whole array (delete[] table;). — Jonathan Potter
@JonathanPotter I edited my post to cover your very valid point, which I overlooked at first reading. Let me know if you think I "borrowed" too much since that was never my intention. — dxiv
@dxiv That's fine, in fact +1 for taking the time to make it an answer. — Jonathan Potter

dxiv dxiv · Accepted Answer · 2015-11-20T07:27:22

The nextStudent field is never initialized, so all 10 elements created here have it pointing to unknown values.

Student * table = new Student [10];

This causes addStudent to loop until some pointer->nextStudent hits a NULL value by chance, then overwrite memory it doesn't own (unless it hits the lucky NULL on the first iteration).

while(pointer->nextStudent !=NULL) { ... }

The 'student` struct (btw, why the typedef?) should have a constructor to at least do this.

student::student() : nextStudent(NULL) { }

[ EDIT ] The other issue that @JonathanPotter duly pointed in a comment is that the head of each of the 10 student lists is a member of the table array. It is not dynamically allocated, and should not be individually deleted.

The qucik/easy fix would be to add a student destructor to recursively delete child nodes:

student::~student() { if(nextStudent) delete nextStudent; }

Then deleteAll would reduce to:

void deleteAll(student *table, int len)
{
    for (int i = 0; i < len; i++)
    {
        student *tmp = &table[i];
        if(tmp->nextStudent) delete tmp->nextStudent;
    }
    // this leaves the dynamically allocated table[] in place
    // to delete it as well, just `delete [] table;`
}

However, such recursion may become impracticable once the lists grow large, and should better be rewritten as an iteration (without the recursive destructor).

student::~student() { }

// ...

void deleteAll(student *table, int len)
{
    for(int i = 0; i < len; i++)
    {
        student *tmp = &table[i];

        // delete student info except the *first* one
        for(student *tmp2; tmp2 = tmp->nextStudent; )
        {
            tmp->nextStudent = tmp2->nextStudent;
            delete tmp2;
        }
    }
    // this leaves the dynamically allocated table[] in place
    // to delete it as well, just `delete [] table;`
}

c++ pointer being freed was not allocated error

2 Answers