35

I'm translating some MATLAB code into C and the script I'm converting makes heavy use of 3D arrays with 10*100*300 complex entries. The size of the array also depends on the sensor's input, ideally the array should be allocated dynamically. So far I've tried two approaches the first being a flat 1D array along the lines of

value = array[x + (y*xSize) + (z*ySize*xSize)]

Which hurts my brain to use. I've also tried an array of an array of pointers

int main () {
  int ***array = malloc(3*sizeof(int**));
  int i, j;

  for (i = 0; i < 3; i++) {
    *array[i] = malloc(3*sizeof(int*));
    for (j = 0; j < 3; j++) {
      array[i][j] = malloc(3*sizeof(int));
    }
  }

  array[1][2][1] = 10;

  return 0;
}

Which gives a seg fault when I try to assign data.

In a perfect world, I'd like to use the second method with the array notation for cleaner, easier programming. Is there a better way to dynamically allocate a three-dimensional array in C?

4
  • 1
    add #include <stdlib.h> and remove the * from *array[i] and it will run when compiled in gcc
    – Paul
    Feb 21, 2010 at 14:46
  • I am also curious on how to implement this. The 1D array solution is "cleaner" (it the one I use so far), however for number-crunching it is significantly slower than the 3D statically-allocated, due to the "offset" calculation.
    – lmount
    Feb 21, 2010 at 20:49
  • 1
    @WorldCitizeN have you actually measured this performance? When you access a statically allocated array, the same calculations are run. The only difference is, you don't write them. Jul 7, 2012 at 18:40
  • @lmount In general, indirection is a lot more expensive than integer multiplication. I would expect the 1D array to be faster.
    – Daniel H
    Mar 23, 2018 at 19:56

16 Answers 16

23

I'd go for the first option (the single 1D array) as it will give you a single block of memory to play in rather than potentially thousands of fragmented memory blocks

If accessing the correct element of the array is doing your head in though, I'd write a utility method to convert x, y, z locations into an offset into the 1D array

int offset(int x, int y, int z) { 
    return (z * xSize * ySize) + (y * xSize) + x; 
}
1
  • This general idea of the distance between array elements (whether those elements are subarrays or whatever) is called striding (for anyone who would like to learn more)
    – Him
    Sep 17, 2022 at 22:58
15

As others have said, it is probably better to allocate one contiguous chunk of memory, and then figure out the indexing yourself. You can write a function to do so if you want. But since you seem to be interested in knowing how to deal with the multiple malloc() case, here is an example:

First, I define a function free_data(), which frees an int *** with xlen and ylen as the first two dimension sizes. We don't need a zlen parameter just like free() doesn't take the length of the pointer being freed.

void free_data(int ***data, size_t xlen, size_t ylen)
{
    size_t i, j;

    for (i=0; i < xlen; ++i) {
        if (data[i] != NULL) {
            for (j=0; j < ylen; ++j)
                free(data[i][j]);
            free(data[i]);
        }
    }
    free(data);
}

The function loops over the pointer data, finds out the ith int ** pointer data[i]. Then, for a given int ** pointer, it loops over it, finding out the jth int * in data[i][j], and frees it. It also needs to free data[i] once it has freed all data[i][j], and finally, it needs to free data itself.

Now to the allocation function. The function is a bit complicated by error checking. In particular, since there are 1 + xlen + xlen*ylen malloc calls, we have to be able to handle a failure in any of those calls, and free all the memory we allocated so far. To make things easier, we rely on the fact that free(NULL) is no-op, so we set all the pointers at a given level equal to NULL before we try to allocate them, so that if an error happens, we can free all of the pointers.

Other than that, the function is simple enough. We first allocate space for xlen int ** values, then for each of those xlen pointers, we allocate space for ylen int * values, and then for each of those xlen*ylen pointers, we allocate space for zlen int values, giving us a total space for xlen*ylen*zlen int values:

int ***alloc_data(size_t xlen, size_t ylen, size_t zlen)
{
    int ***p;
    size_t i, j;

    if ((p = malloc(xlen * sizeof *p)) == NULL) {
        perror("malloc 1");
        return NULL;
    }

    for (i=0; i < xlen; ++i)
        p[i] = NULL;

    for (i=0; i < xlen; ++i)
        if ((p[i] = malloc(ylen * sizeof *p[i])) == NULL) {
            perror("malloc 2");
            free_data(p, xlen, ylen);
            return NULL;
        }

    for (i=0; i < xlen; ++i)
        for (j=0; j < ylen; ++j)
            p[i][j] = NULL;

    for (i=0; i < xlen; ++i)
        for (j=0; j < ylen; ++j)
            if ((p[i][j] = malloc(zlen * sizeof *p[i][j])) == NULL) {
                perror("malloc 3");
                free_data(p, xlen, ylen);
                return NULL;
            }

    return p;
}

Note that I have simplified malloc calls quite a bit: in general, you shouldn't cast the return value of malloc, and specify the object you're allocating for as the operand to sizeof operator instead of its type. That makes malloc calls simpler to write and less error-prone. You need to include stdlib.h for malloc.

Here is a test program using the above two functions:

#include <stdlib.h>
#include <errno.h>
#include <stdio.h>
#include <time.h>

int main(void)
{
    int ***data;
    size_t xlen = 10;
    size_t ylen = 100;
    size_t zlen = 300;
    size_t i, j, k;

    srand((unsigned int)time(NULL));
    if ((data = alloc_data(xlen, ylen, zlen)) == NULL)
        return EXIT_FAILURE;

    for (i=0; i < xlen; ++i)
        for (j=0; j < ylen; ++j)
            for (k=0; k < zlen; ++k)
                data[i][j][k] = rand();

    printf("%d\n", data[1][2][1]);
    free_data(data, xlen, ylen);
    return EXIT_SUCCESS;
}

By all means use this approach if you find it easier to use it. In general, this will be slower than using a contiguous chunk of memory, but if you find that the speed is OK with the above scheme, and if it makes your life easier, you can keep using it. Even if you don't use it, it is nice to know how to make such a scheme work.

1
  • Hi, this is probably very old, but I wanted to ask: Is this p = malloc(xlen * sizeof *p)) equivalent to p = (int**)malloc(xlen * sizeof(int*)); ? Jan 18, 2017 at 14:47
15

Are you sure you need to use malloc? C allows creating of multidimentional arrays natively:

int a2[57][13][7];

Or you can use malloc in the following way:

int (*a)[13][7]; // imitates 3d array with unset 3rd dimension
                 // actually it is a pointer to 2d arrays

a = malloc(57 * sizeof *a);    // allocates 57 rows

a[35][7][3] = 12; // accessing element is conventional

free(a); // freeing memory
5
  • Also I think it is possible to cast from malloc, but not sure, need to check...
    – Dims
    Dec 2, 2012 at 18:39
  • native multidimensional arrays often run up against memory constraints Nov 18, 2015 at 16:49
  • @polyphant C allocates exact space for elements, no extra data
    – Dims
    Nov 19, 2015 at 7:17
  • 1
    Variables on the stack are size limited, not on the heap. See here gribblelab.org/CBootcamp/7_Memory_Stack_vs_Heap.html Nov 19, 2015 at 10:54
  • Sorry, misunderstood you, you are correct of course.
    – Dims
    Nov 19, 2015 at 20:24
13

There is no way in C89 to do what you desire, because an array type in C can only be specified with compile time known values. So in order to avoid the mad dynamic allocation, you will have to stick to the one dimensional way. You may use a function to ease this process

int index(int x, int y, int z) {
  return x + (y*xSize) + (z*ySize*xSize);
}

int value = array[index(a, b, c)];

In C99 you can use an ordinary array syntax even if the dimensions are runtime values:

int (*array)[X][Y][Z] = (int(*)[X][Y][Z])malloc(sizeof *p); 
// fill...
int value = (*array)[a][b][c];

However, it only works with local non-static arrays.

1
  • no need to cast from malloc()
    – tstanisl
    Mar 8, 2023 at 11:57
9

Oh do I hate malloc array allocation ^^

Here's a correct version, basically it was just one incorrect line:

int main () {
  int ***array = (int***)malloc(3*sizeof(int**));
  int i, j;

  for (i = 0; i < 3; i++) {
    // Assign to array[i], not *array[i] (that would dereference an uninitialized pointer)
    array[i] = (int**)malloc(3*sizeof(int*));
    for (j = 0; j < 3; j++) {
      array[i][j] = (int*)malloc(3*sizeof(int));
    }
  }

  array[1][2][1] = 10;

  return 0;
}
1
  • 1
    Right, I'm just used to do it because C++ will throw errors if you don't.
    – AndiDog
    Feb 21, 2010 at 19:01
3

You are forcing yourself into perceiving this as two fundamentally different ways to allocate a 3D array. This perception is reinforced by two definitive differentiating details: 1) the second method uses several levels of indirection to access the actual elements, 2) the second method allocates the lower-level 1D arrays independently.

But why exactly do you insist on allocating the lower-level 1D arrays independently? You don't have to do that. And once you take it into account, you should realize that there's a third method of building your 3D array

int ***array3d = malloc(3 * sizeof(int **));
int **array2d = malloc(3 * 3 * sizeof(int *));
int *array1d = malloc(3 * 3 * 3 * sizeof(int));

for (size_t i = 0; i < 3; i++) 
{
  array3d[i] = array2d + i * 3;
  for (size_t j = 0; j < 3; j++)
    array3d[i][j] = array1d + i * 3 * 3 + j * 3;
}

array[1][2][1] = 10;

If you look at this allocation method closely, you should see that in the end this is pretty much the same thing as your second method: it builds a three-level array structure by using intermediate pointers at each level of indirection. The only difference is that it pre-allocates memory for each level of indirection contiguously, "in one shot", beforehand, instead of making multiple repetitive malloc calls. The subsequent cycle simply distributes that pre-allocated memory among the sub-arrays (i.e. it simply initializes the pointers).

However, if you look even closer, you'll also notice that the actual array element memory (the ints that store actual the values) are allocated in exactly the same way as they would be in your first method: malloc(3 * 3 * 3 * sizeof(int)); - as a plain flat contiguous array.

Now, if you think about it, you should realize that this third method is not much different from your first. They both use a flat array of size xSize * ySize * zSize to store the data. The only real difference here is the method we use to calculate the index to access that flat data. In the first method we'd calculate the index on-the-fly as

array1d[z * ySize * xSize + y * xSize + x]

in the third method we pre-calculate the pointers to array elements in advance, using essentially the same formula, store the pre-calculated results in additional arrays and retrieve them later using the "natural" array access syntax

array3d[x][y][x]

The question here is whether this pre-calculation is worth the extra effort and extra memory. The answer is: generally no, it is not. By spending this extra memory you will not reap any appreciable performance benefits (chances are it will make your code slower).

The only situation where your second method might be worth considering is when you are dealing with genuinely jagged/ragged array: a sparse multi-dimensional array with some sub-arrays parts missing/unused or having reduced size. For example, if some 1D or 2D sub-arrays of your 3D array are known to contain just zeros, you might decide not to store them in memory at all and set the corresponding pointers to null. This would imply using your second method, where the sub-arrays are allocated (or not allocated) independently. If the data is large the resultant memory savings could be well worth it.

Also note that when we are talking about arrays with 3 and more dimensions, the first/second/third allocation methods can be used together, simultaneously for different levels of indirection. You might decide to implement 2D arrays using the first method and then combine them into a 3D array using the second method.

2

In this way you can allocate only just 1 block of memory and the dynamic array behaves like the static one (i.e. same memory contiguity). You can also free memory with a single free(array) like ordinary 1-D arrays.

double*** arr3dAlloc(const int ind1, const int ind2, const int ind3)
{
  int i;
  int j;
  double*** array = (double***) malloc( (ind1 * sizeof(double*)) + (ind1*ind2 * sizeof(double**)) + (ind1*ind2*ind3 * sizeof(double)) );
  for(i = 0; i < ind1; ++i) {
    array[i] = (double**)(array + ind1) + i * ind2;
    for(j = 0; j < ind2; ++j) {
      array[i][j] = (double*)(array + ind1 + ind1*ind2) + i*ind2*ind3 + j*ind3;
    }
  }
  return array;
}
2

About the segfault, I am pretty sure someone else has pointed this out but just in case, there is a extra '*' in the first line of the first for loop

for (i = 0; i < 3; i++) {
    *array[i] = malloc(3*sizeof(int*));
//  ^ we dont want to deference array twice
    for (j = 0; j < 3; j++) {
        array[i][j] = malloc(3*sizeof(int));
    }
}

try the following:

    for (i = 0; i < 3; i++) {
        array[i] = malloc(3*sizeof(int*));
        for (j = 0; j < 3; j++) {
            array[i][j] = malloc(3*sizeof(int));
        }
    }
2

Hope this will help you!!!!

While allocating memory for 2D array inside 3D array, assign the allocated memory to array[i] and not *array[i] and this will work without seg fault.

Here is your program

int main () 
{
    int ***array = malloc(3*sizeof(int**));
    int i, j;

    for (i = 0; i < 3; i++) {
       array[i] = malloc(3*sizeof(int*));
       for (j = 0; j < 3; j++) {
          array[i][j] = malloc(3*sizeof(int));
       }
    }

    array[1][2][1] = 10;

    return 0;
}
2

Here is the same thing, but it has only one call to malloc.

void* allocate_3d_matrix(size_t size, size_t r1, size_t r2, size_t r3) {
    size_t malloc_size = r1 * sizeof(char**) + r1 * r2 * sizeof(char*) + r1 * r2 * r3 * size;
    char*** p = malloc(malloc_size);

    char** r2_start = (char**) p + r1;  

    for (int i = 0; i < r1; i++) {
        p[i] = r2_start + i * r2;
    }

    char* r3_start = (char*) r2_start + (r1 * r2 * sizeof(char*));

    for (int i = 0; i < r1; i++) {
        for (int j = 0; j < r2; j++) {
            p[i][j] = r3_start + size * (j + i * r2) * r3;
        }
    }

    return p;
}

Deleting the matrix is just free(p), since everything is allocated in a single block. From the performance perspective, it should be the fastest, since the block of memory is the smallest possible, it has only one call to malloc (less memory fragmentation).

1
  • 1
    Thank you so much! I could do this easily with 2D arrays, but the pointer math with 3D arrays was eluding me. Your syntax of "r1 * r2 * r3 * sizeof" for each "layer" of the array really helped make it clear. This is the ONLY place on the internet I could find with the solution to this!
    – suprjami
    Jan 29, 2023 at 4:55
1

Below the Code for 3d memory allocations:

int row3d = 4;
int column3d = 4;
int height3d =4;
int val3d =10;

int ***arr3d = (int***)malloc (row3d*sizeof(int**));
for (int i =0 ; i<column3d;i++)
{
    arr3d[i] = (int**)malloc (column3d*sizeof(int*));
    for (int j = 0;j<height3d;j++)
    {
        arr3d[i][j] = (int*)malloc (height3d*sizeof(int));

        for (int z =0;z<height3d;z++,val3d++)
        {
            arr3d[i][j][z]   = val3d;
        }
    }

}
// De allocation.
for (int i=0;i<row3d;i++)
{
    for(int j=0;j<column3d;j++)
    {
        free(arr3d[i][j]);
    }
}
free(arr3d);
arr3d = 0;
1
#include<stdio.h>
#include<stdlib.h>

#define MAXX 3
#define MAXY 4
#define MAXZ 5

main()
{
    int ***p,i,j;
    p=(int ***) malloc(MAXX * sizeof(int **));

    for(i=0;i < MAXX;i++)
    {
        p[i]=(int **)malloc(MAXY * sizeof(int *));
        for(j=0;j < MAXY;j++)
            p[i][j]=(int *)malloc(MAXZ * sizeof(int));
    }

    for(k=0;k < MAXZ;k++)
        for(i=0;i < MAXX;i++)
            for(j=0;j < MAXY;j++)
                p[i][j][k]= < something >;

}
0

add #include "stdlib.h" and remove the * from *array[i] and it will run when compiled in gcc 4.4.1 on Ubuntu

also if you add print statements you can find your bugs quicker

#include <stdio.h>
#include <stdlib.h>

int main () {
  int ***array = malloc(3*sizeof(int**));
  int i, j;

  printf("%s\n","OK");

  for (i = 0; i < 3; i++) {
    printf("i = %i \n",i);
    array[i] = malloc(3*sizeof(int*));
    for (j = 0; j < 3; j++) {
      printf("i,j = %i,%i \n",i,j);
      array[i][j] = malloc(3*sizeof(int));
    }
  }

  array[1][2][1] = 10;

  return 0;
}
1
  • printf() statements can be useful, but they're not a good habit to get into. GDB is really not that hard to learn and gives you printing and variable introspection for free all wrapped up in one little package. And you don't even have to decide where to put the printf()s beforehand.
    – semisight
    Nov 29, 2011 at 8:09
0

To understand The process I suggest that you allocate the memory for p then p[0] and finally p[0][0], this is a simple example:

   int ***a;
     a  = (int***)malloc(sizeof(int**));
    *a  = (int**)malloc(sizeof(int*));
   **a  = (int*)malloc(sizeof(int));
0
#include <stdio.h>
#include <stdlib.h>

int*** allocate_memory(int rows, int columns, int heigth) {
    int ***array = (int***) malloc(rows * sizeof(int**));

    for (int i = 0; i < rows; i++) {
        array[i] = (int**) malloc(columns * sizeof(int*));
        for (int j = 0; j < columns; j++) {
            array[i][j] = (int*) malloc(heigth * sizeof(int));
        }
    }

    array[1][2][1] = 10;
    return array;
}

int main() {
    int ***cube = allocate_memory(3, 3, 3);
    printf("%d\n", cube[1][2][1]);
    return 0;
}
1
  • Your answer could be improved with additional supporting information. Please edit to add further details, such as citations or documentation, so that others can confirm that your answer is correct. You can find more information on how to write good answers in the help center.
    – Community Bot
    Sep 22, 2022 at 2:39
-1

This should work, you are not typecasting the return value of malloc

#include <stdio.h>

int main () {
  int ***array = (int ***) malloc(3*sizeof(int**));
  int i, j;

  for (i = 0; i < 3; i++) {
    array[i] = (int **)malloc(3*sizeof(int*));
    for (j = 0; j < 3; j++) {
      array[i][j] = (int *)malloc(3*sizeof(int));
    }
  }

  array[1][2][1] = 10;
  printf("%d\n", array[1][2][1]);
  return 0;
}

Working Link: http://ideone.com/X2mcb8

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.