Freeing 2D array - Heap Corruption Detected

Question

EDIT: Sorry guys, I forgot to mention that this is coded in VS2013.

I have a globally declared struct:

typedef struct data //Struct for storing search & sort run-time statistics.
{
    int **a_collision;
} data;

data data1;

I then allocate my memory:

data1.a_collision = (int**)malloc(sizeof(int)*2);   //Declaring outer array size - value/key index.
for (int i = 0; i < HASH_TABLE_SIZE; i++)   
    data1.a_collision[i] = (int*)malloc(sizeof(int)*HASH_TABLE_SIZE);   //Declaring inner array size. 

I then initialize all the elements:

//Initializing 2D collision data array.
for (int i = 0; i < 2; i++)
for (int j = 0; j < HASH_TABLE_SIZE; j++)
    data1.a_collision[i][j] = NULL;

And lastly, I wish to free the memory (which FAILS). I have unsuccessfully tried following some of the answers given on SO already.

free(data1.a_collision);
for (int i = 0; i < HASH_TABLE_SIZE; i++)
    free(data1.a_collision[i]);

A heap corruption detected error is given at the first free statement. Any suggestions?

Answer 1

There are multiple mistakes in your code. logically wrong how to allocate memory for two dimension array as well as some typos.

From comment in your code "outer array size - value/key index" it looks like you wants to allocate memory for "2 * HASH_TABLE_SIZE" size 2D array, whereas from your code in for loop breaking condition "i < HASH_TABLE_SIZE;" it seems you wants to create an array of size "HASH_TABLE_SIZE * 2".

Allocate memory:

Lets I assume you wants to allocate memory for "2 * HASH_TABLE_SIZE", you can apply same concept for different dimensions.

The dimension "2 * HASH_TABLE_SIZE" means two rows and HASH_TABLE_SIZE columns. Correct allocation steps for this would be as follows:

step-1: First create an array of int pointers of lenght equals to number of rows.

data1.a_collision =  malloc(2 * sizeof(int*)); 
//                   2 rows ^             ^ you are missing `*` 

this will create an array of int pointers (int*) of two size, In your code in outer-array allocation you have allocated memory for two int objects as 2 * sizeof(int) whereas you need memory to store addresses. total memory bytes you need to allocate should be 2 * sizeof(int*) (this is poor typo mistake).

You can picture above allocation as:

                      343  347  
                     +----+----+
data1.a_collision---►| ?  | ?  |
                     +----+----+

1. ? - means garbage value, malloc don't initialize allocate memory
2. It has allocated two memory cells each can store address of int
3. In picture I have assumed that size of int* is 4 bytes.

Additionally, you should notice I didn't typecast returned address from malloc function because it is implicitly typecast void* is generic and can be assigned to any other types of pointer type (in fact in C we should avoid typecasting you should read more from Do I cast the result of malloc?).

Now step -2: Allocate memory for each rows as an array of length number of columns you need in array that is = HASH_TABLE_SIZE. So you need loop for number of rows(not for HASH_TABLE_SIZE) to allocate array for each rows, as below:

for(int i = 0; i < 2; i++)  
  //            ^^^^  notice   
  data1.a_collision[i] = malloc(HASH_TABLE_SIZE * sizeof(int)); 
  //                                                    ^^^^^

Now in each rows you are going to store int for array of ints of length HASH_TABLE_SIZE you need memory bytes = HASH_TABLE_SIZE * sizeof(int). You can picture it as:

Diagram

        data1.a_collision = 342
            |  
            ▼                       201   205   209    213  
        +--------+                +-----+-----+-----+-----+
 343    |        |                |  ?  |  ?  |  ?  | ?   |  //for i = 0
        |        |-------|        +-----+-----+-----+-----+
        | 201    |       +-----------▲
        +--------+                  502   506  510    514
        |        |                +-----+-----+-----+-----+
 347    |        |                |  ?  |  ?  |  ?  | ?   |  //for i = 1
        | 502    |-------|        +-----+-----+-----+-----+
        +--------+       +-----------▲

   data1.a_collision[0] = 201
   data1.a_collision[1] = 502

In picture I assuming HASH_TABLE_SIZE = 4 and size of int= 4 bytes, note address's valuea

Now these are correct allocation steps.

Deallocate memory:

Other then allocation your deallocation steps are wrong!

Remember once you have called free on some pointer you can't access that pointer ( pr memory via other pointer also), doing this calls undefined behavior—it is an illegal memory instruction that can be detected at runtime that may causes—a segmentation fault as well or Heap Corruption Detected.

Correct deallocation steps are reverse of allocation as below:

for(int i = 0; i < 2; i++)
    free(data1.a_collision[i]); // free memory for each rows
free(data1.a_collision); //free for address of rows.

Further more this is one way to allocate memory for two dimension array something like you were trying to do. But there is better way to allocate memory for complete 2D array continuously for this you should read "Allocate memory 2d array in function C" (to this linked answer I have also given links how to allocate memory for 3D arrays).

Answer 2

There are several issues :

1. The first allocation is not correct, you should alloc an array of (int *) :

    #define DIM_I 2
    #define DIM_J HASH_TABLE_SIZE
    data1.a_collision = (int**)malloc(sizeof(int*)*DIM_I);
   

2. The second one is not correct any more :

    for (int i = 0; i < DIM_I; i++)
      data1.a_collision[i] = (int*)malloc(sizeof(int)*DIM_J);
   

3. When you free memory, you have to free in LastInFirstOut order:

    for (int i = 0; i < DIM_I; i++)
        free(data1.a_collision[i]);
    free(data1.a_collision);
   

Answer 3

Here is a start:

Your "outer array" has space for two integers, not two pointers to integer.

Is HASH_TABLE_SIZE equal to 2? Otherwise, your first for loop will write outside the array you just allocated.