Allocating 2-D Arrays on Heap

Introduction

We’ve seen that allocating one-dimensional arrays is pretty straightforward. To allocate one array of 15 doubles, we can write the following:

double arr = malloc(15 * sizeof(double));

Then we can use this array just like we use any other array:

arr[0] = 5.0; //to write to the array
double x = arr[1]; //to read from the array

The question is, how can we dynamically allocate arrays with higher dimensions? We’ll present a strategy called “arrays of pointers to arrays” for the two-dimensional case. This strategy can extend to three-dimensional arrays and beyond.

Matrix structure

To understand this technique, let’s inspect how a 3x4 matrix looks:

As per the image above, we can view the matrix as multiple arrays stacked on top of each other, and each array is one row. Therefore, a matrix or two-dimensional array is an array of arrays.

To dynamically allocate a matrix with n lines and m columns, imagine dynamically allocating n individual one-dimensional arrays, where each array will serve as a row. We know how to allocate one-dimensional arrays, so this is doable.

For example, if we assume a 3x4 matrix that stores integers, we can do:

malloc(4 * sizeof(int)) //allocate first row array
malloc(4 * sizeof(int)) //allocate second row array
malloc(4 * sizeof(int) //allocate third row array
malloc(4 * sizeof(int) //allocate fourth row array

See the following illustration:

To get row i, we have to access the ith array. We need to somehow store these individual arrays in a way that allows us to know which array is the first row, which array is the second row, and so on.

To glue the arrays together, we can have one more array, matrix, whose elements are pointers to the row arrays.

• matrix[0] stores a pointer to the first array, which is row 0.
• matrix[1] stores a pointer to the second array, which is row 1.
• so on…
• matrix[n - 1] stores a pointer to the nth array, which is row n - 1.

We also know how to allocate the extra matrix array, as it is a one-dimensional array of pointers to one-dimensional arrays.

For example, if we assume a 3x4 matrix that stores integers, we can do:

int** matrix = malloc(3 * sizeof(int*))

The matrix array is an array of pointers to arrays storing integers. Each row array decays into a pointer to its first element, an int*. Then, each element inside matrix will be of type int*.

Next, we should deduce the type of matrix. It’ll be a pointer to a memory block that holds elements of type int*. A pointer to int* is int**. Another way of thinking about this is from an array decaying perspective.

• An array of integers decays into a pointer to its first element, which is a pointer to an integer (int*).
• Then, an array of pointers to integers must decay into a pointer to its first element, which is a pointer to a pointer to an integer (int**).

Hence, the type of matrix is int**.

See the following illustration:

When we want to access row i and column j from the matrix, all we have to do is use matrix[i] to get the ith row. Then, inside matrix[i], we have to get the jth element for the jth column by doing matrix[i][j]. The result is that we’ll index this array precisely the same way we index stack-allocated bi-dimensional arrays.

See the following illustration:

Writing the code

All that’s left is to transpose everything in code. See the following code widget, where we use the theory to dynamically allocate a matrix.

It’s best if we correlate the theory with the code and see the comments. The comments are placed directly inside the code, as opposed to re-explaining the code again in the lesson, for better understanding.

Identifying the cause of the memory leak

The code works, but it leaks memory (see the Valgrind output). However, we don’t even need Valgrind to tell us this. We wrote an allocateMatrix function, but we never free the memory.

Therefore, we should also write a deallocateMatrix function.

Note: A good rule of thumb for deallocating memory is to do it in reverse order of the allocations.

For example, we first allocate the matrix array and then the row arrays. Therefore, for deallocating, we’ll first deallocate the row arrays and then the matrix array. If we did it the other way around, we’d lose the pointer to the row arrays, and we’d be unable to deallocate them.

The only difference in the code is that we added the deallocateMatrix function (line 31). We are calling it in line 72 after we finish using the matrix.

The deallocation procedure is simple, we first free each row array (lines 39–43), and then we free the matrix array itself (line 44).

The Valgrind output is now clean, without any reported memory leaks.

Fixing more issues

However, the code is still imperfect. It has a potential memory leak. Valgrind can only detect leaks that happen during the code execution, but if some code paths don’t get executed, then Valgrind can’t analyze them.

Let’s check the allocateMatrix function in lines 21–25.

if(matrix[i] == NULL)
{
    //the allocation of the row failed, stop
    return NULL;
}

If the allocation of one of the row arrays fails, we stop the function. However, we never free the successfully allocated matrix array. Let’s add this part:

if(matrix[i] == NULL)
{
    //the allocation of the row failed, stop
    free(matrix);
    return NULL;
}

That’s better, but let’s see what happens if we allocate 15 row arrays and the 8th allocation fails. It means that the first 7 allocations succeeded, so we have to free them.

if(matrix[i] == NULL)
{
    //free the previously allocated row arrays. 
    //if the ith allocation fails, then the allocations 0, ..., i - 1 are valid
    for(int j = 0; j < i; j++)
    {			 
        free(matrix[j]);
    }

    free(matrix);
    return NULL;
}

The fixed code is below. Notice the changes mentioned above in lines 23–31.

Now everything works correctly, and there are no chances of memory leaks. Feel free to play with the code, allocate matrices of different sizes or change the type of the elements.

Optional task

Here’s a practice idea. Can you change the code to allocate a three-dimensional array? It shouldn’t be too hard to allocate the array, but the deallocation code can be tricky.

If you can’t do it, don’t worry. We’ll present an easier way of allocating higher-dimension dynamic arrays.