How do you use malloc to allocate memory for a multidimensional array?
For example, you would like to use arr[6][9].
You may have tried the following:
// Warning: broken example
int **arr = malloc(50 * sizeof(int));
arr[6][9] = 42; // dangerous! Segmentation fault (core dumped)
This is obviously wrong. But what is the correct way to allocate (and free) memory for multidimensional arrays?
The most basic multidimensional array is of course the 2D-array.
It has two dimensions, in this example I'll use an array of size x by y.
For simplicity I used the integer type to store data. The storage type is not relevant to the general technique to use.
Any error checking is skipped in the first few examples, for clarity.
Later examples include some basic forms of error checking.
The size_t type is used for index offsets, to avoid confusion with the type (integer) stored in the multidimensional array.
/*
* Warning: no error checks!
*/
int **create_2d(size_t x, size_t y)
{
int *values = malloc(x * y * sizeof *values);
int **index_x = malloc(x * sizeof *index_x);
for (size_t i = 0; i < x; i++)
index_x[i] = &values[i * y];
return index_x;
}
You can now read and write all locations within the 2D-array using as long as you don't go below 0 or over x and y as that would be accessing the array out-of-bounds.
int **arr = create_2d[20][24];
arr[6][9] = 42; // perfectly fine!
Maybe you are satisfied with this code, and you copy/paste this into your project. That is completely fine, yet at your own risk. I'll provide further explanation and some words of warning.
Some explanation of what this all means. In the end the multidimensional array needs to store x rows and y columns of type int. This means that the required storage size is x * y * sizeof(int) at the very least.
In this example all of that required storage is allocated in a single go. However instead of sizeof(int) is used sizeof *values, since that is easier to maintain, should e.g. the storage type change. It is less error prone this way.
Now, all of the memory is "contiguous", and accessible as an offset from values[0] to values[x * y]. This is actually often already usable as a faux 2-dimensional array by using some simple arithmetic. For example, you could say that index (i,j) is already accessible via values[i * y + j];. The first y values are row 0, the next y values are row 1, etc.
To make it truely accessible via index [i][j] that index needs to actually be allocated as well. In this case I called it index_x. It will have to be able to point to x different memory locations, specifically the "first" y value every "row".
Often times you will see people perform the allocation in a loop. That is actually not necessary and makes things a bit more complicated in terms of error checking and deallocation. Nonetheless, assigning the memory locations for the start of the y-rows needs to be done in a loop, where I used i as an iterator value to range from 0 to x. Because index_x needs to point to pointers, we put the address of values[i * y] in the index_x.
It should be noted that it is also index_x that is returned, not values. If you would in fact need to access values, that can still be done via index_x[0]. This will be handy when we need to free the memory.
The following function will free up the allocated memory:
/*
* Warning: no error checks!
*/
void destroy_2d(int **ptr)
{
free(ptr[0]);
free(ptr);
}
As you can see, no loops are required here.
Now it may not be apparent why with is preferable over using malloc within the loop. It should become apparent once you start adding error-checking code, or when you need to allocate a lot of items or have a lot of nesting. The same principle applies to a 3-dimensional array. Let me demonstrate the 3D array for clarity:
int ***create_3d(size_t x, size_t y, size_t z)
{
int *values = malloc(x * y * z * sizeof *values);
int **index_y = malloc(x * y * sizeof *index_y);
int ***index_x = malloc(x * sizeof *index_x);
for (size_t i = 0; i < x; i++) {
index_x[i] = &index_y[i * y];
for (size_t j = 0; j < y; j++) {
// remove ONE of the following two lines
index_x[i][j] = &values[(i * y + j) * z]; // or, alternatively:
index_y[i * y + j] = &values[(i * y + j) * z]; // this is exactly the same
}
}
return index_x;
}
void destroy_3d(int ***ptr)
{
free(ptr[0][0]);
free(ptr[0]);
free(ptr);
}
This is the same principle, albeit with a bit more complex arithmetic.
Let me show you why this matters by adding very basic error checking:
int ***create_3d_e(size_t x, size_t y, size_t z)
{
int *values = malloc(x * y * z * sizeof *values);
if (!values)
return NULL;
int **index_y = malloc(x * y * sizeof *index_y);
if (!index_y) {
free(values);
return NULL;
}
int ***index_x = malloc(x * sizeof *index_x);
if (!index_x) {
free(index_y);
free(values);
return NULL;
}
for (size_t i = 0; i < x; i++) {
index_x[i] = &index_y[i * y];
for (size_t j = 0; j < y; j++) {
index_y[i * y + j] = &values[(i * y + j) * z];
}
}
return index_x;
}
Or, alternatively, if you prefer a different code style:
int ***create_3d_g(size_t x, size_t y, size_t z)
{
int *values;
int **index_y;
int ***index_x;
size_t i, j;
values = malloc(x * y * z * sizeof *values);
if (!values)
goto err;
index_y = malloc(x * y * sizeof *index_y);
if (!index_y)
goto err_y;
index_x = malloc(x * sizeof *index_x);
if (!index_x)
goto err_x;
for (i = 0; i < x; i++) {
index_x[i] = &index_y[i * y];
for (j = 0; j < y; j++) {
index_y[i * y + j] = &values[(i * y + j) * z];
}
}
return index_x;
err_x:
free(index);
err_y:
free(values);
err:
return NULL;
}
And then some basic error preventing logic when freeing:
void destroy_3d_e(int ***ptr)
{
if (ptr) {
if (ptr[0]) {
free(ptr[0][0]);
free(ptr[0]);
}
free(ptr);
}
}
This is another advantage of not allocating memory within the loop! In that case, the "destroy" function should also know about the dimensions and free all allocations in a loop. Added complexity when some allocation fails halfway in a loop of a nested multidimensional array. Crashing your program is not always an option, you might want or need to deallocate the memory to prevent nasty bugs. That is when the freeing of "contiguous" memory is so much easier than the "loop-malloc" method. I didn't provide example for that, because I don't think that will be helpful. If other people want to provide that as a separate answer, please do so, with the appropriate reservations.
As an exercise for the reader: try to implement that for a 3-dimensional array. Checking for failure halfway of building up the array, and gracefully tearing everything down without memory leaks.
HEAP SUMMARY:
in use at exit: 0 bytes in 0 blocks
total heap usage: 3 allocs, 3 frees, 96,481,600 bytes allocated
All heap blocks were freed -- no leaks are possible
ERROR SUMMARY: 0 errors from 0 contexts (suppressed: 0 from 0)
I hope to see far fewer people asking for that method in the future. And I hope these examples provided you with a better understanding of the internal workings of multidimensional arrays.