Allocate space for a 3 dimensional array in C

Question

This question has been answered here but for me some things are still left open and the discussion is too old for anyone to reply to comments, besides I wanted to ask what was wrong in my implementation.

Anyway, the problem setting. I want to allocate space for a 3D array of dimensions 3, h, w. What I am doing:

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

I understand this as creating first space for three 3 int** and then allocating height int**; Then :

for (int i = 0; i < 3; i++)
{
  a[i][0] = (int *) malloc(height * width * sizeof(int *));
  for (int j = 1; j < height; j++)
   {
     a[i][j] = a[i][j-1] + width;
   }
}

So now I think that each a[i][0] is basically space for a 2D array of sizes height and width; furthermore the rest of a[i][j] for j != 0 is initialized to the j th row of a[i][0];

then I initialize values by:

for (int c = 0; c < 3; c++){
  for (int i = 0; i < height; i++){
    for (int j = 0; j < width; j++){
      a[c][i][j] = i+j+c;

This however is incorrect. I wanted to do this as an extension exercise to allocating a 2D array in the following way:

int *a[height]; 
a[0] = (int*)malloc(height * width * sizeof(int));
for (int i = 1; i < height; i++){
  a[i] = a[i-1] + widht;
}

This way a is an array of pointers of length height, a[0] is allocated for the whole 2D array and the consequent pointers point to their respective rows and I can write to them simply by calling a[i][j] = some number;

What I want to do is extend this 2D idea to the 3D case, but I am sadly failing.

Answer 1

int ***a = (int***)malloc(3 * sizeof(int*));

This doesn't allocate anything meaningful. In particular, it does not allocate a 3D array, or even a part of a 3D array. It allocates space for 3 integer pointers, which doesn't make any sense. Neither does a int*** make any sense.

Instead, allocate a 3D array:

int (*a)[y][z] = malloc( sizeof(int[x][y][z]) );

for(int i=0; i<x; i++)
  for(int j=0; j<y; j++)
    for(int k=0; k<z; k++)
      a[i][j][k] = something;

free(a);

---

EDIT (any sarcastic tone in the below text is fully intentional)

For the benefit of the three-star programmers who refuse to accept any solution with less than three levels of indirection, here is an example of how to properly do three-star programming.

Unfortunately it does not yet contain non-conditional branching upwards, memory leaks or complex pointer arithmetic. But for a three-star programmer, such joyful things are of course trivial to add later. It does however guarantee data cache misses, so that the program will run with equal performance as a system without any data cache.

One may also consider to pass the allocated pointer-to-pointer-to-pointer as a parameter, thus achieving 4 stars!!!

[As in, the pointer-to-pointer method is very bad practice, but if you for reasons unknown insist on using it, you might as well do it proper.]

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


void free_int_3d (int*** ppp, size_t X, size_t Y, size_t Z)
{
  (void)Z;

  if(ppp == NULL)
  {
    return ;
  }

  for(size_t x=0; x < X; x++)
  {
    if(ppp[x] != NULL)
    {
      for(size_t y=0; y < Y; y++)
      {
        if(ppp[x][y] != NULL)
        {
          free(ppp[x][y]);
        }
      }
      free(ppp[x]);
    }
  }
  free(ppp);
}


#define malloc_with_cleanup(ptr, size)     \
ptr = malloc(size);                        \
if(ptr == NULL)                            \
{                                          \
  free_int_3d(result, X, Y, Z);            \
  return NULL;                             \
}

int*** int_alloc_3d (size_t X, size_t Y, size_t Z)
{
  int*** result = NULL;

  malloc_with_cleanup(result, sizeof(int**[X]));
  for(size_t x=0; x<X; x++)
  {
    malloc_with_cleanup(result[x], sizeof(int*[Y]));
    for(size_t y=0; y<Y; y++)
    {
      malloc_with_cleanup(result[x][y], sizeof(int[Z]));
    }
  }
  return result;
}


int main (void)
{
  const size_t X = 5;
  const size_t Y = 3;
  const size_t Z = 4;

  int*** ppp = int_alloc_3d(X, Y, Z);

  for(size_t i=0; i<X; i++)
  {
    for(size_t j=0; j<Y; j++)
    {
      for(size_t k=0; k<Z; k++)
      {
        ppp[i][j][k] = (int)k;
        printf("%d ", ppp[i][j][k]);
      }
      printf("\n");
    }
    printf("\n");
  }

  free_int_3d(ppp, X, Y, Z);

  return 0;
}

Output:

0 1 2 3
0 1 2 3
0 1 2 3

0 1 2 3
0 1 2 3
0 1 2 3

0 1 2 3
0 1 2 3
0 1 2 3

0 1 2 3
0 1 2 3
0 1 2 3

0 1 2 3
0 1 2 3
0 1 2 3

Answer 2

To solve OP's higher goal, I suspect a pointer to a 2D array would suffice @mch

int (*a)[height][width] = malloc(sizeof *a * 3);

 a[c][i][j] = i + j + c;

---

But per OP's request....

... to allocate space for a 3D array ...

How would code typically create a 3D array?
The below code does that using a variable length array available in C99.
(VLA is optionally support in C11)

int a1[3][height][width];
// and assign it accordingly
for (int c = 0; c < 3; c++) {
  for (int i = 0; i < height; i++) {
    for (int j = 0; j < width; j++) {
      a1[c][i][j] = i + j + c;

Yet OP wants to allocate space for such an array.

malloc() returns a pointer. A pointer to allocated memory. So we need to create a pointer to such an array. Once we have done that, allocation and element assignment is easy.

int (*a2)[3][height][width] = malloc(sizeof *a2);

// 3 nested for loop as above
    (*a2)[c][i][j] = i + j + c;

---

Example code

void VT_3_dimensional_array(int height, int width) {
  assert(height > 0 && width > 0);

  int (*a2)[3][height][width] = malloc(sizeof *a2);
  printf("%p %zu\n", (void*) a2, sizeof *a2);
  if (a2 == NULL) {
    perror("Out of memory");
    exit(EXIT_FAILURE);
  }
  for (int c = 0; c < 3; c++) {
    for (int i = 0; i < height; i++) {
      for (int j = 0; j < width; j++) {
        (*a2)[c][i][j] = i + j + c;
      }
    }
  }

  // use a;
  for (int c = 0; c < 3; c++) {
    for (int i = 0; i < height; i++) {
      putchar('(');
      for (int j = 0; j < width; j++) {
        printf(" %X", (*a2)[c][i][j]);
      }
      putchar(')');
    }
    puts("");
  }

  free(a2);
}

int main() {
  VT_3_dimensional_array(5, 7);
  return 0;
}

output

0x80071980 420
( 0 1 2 3 4 5 6)( 1 2 3 4 5 6 7)( 2 3 4 5 6 7 8)( 3 4 5 6 7 8 9)( 4 5 6 7 8 9 A)
( 1 2 3 4 5 6 7)( 2 3 4 5 6 7 8)( 3 4 5 6 7 8 9)( 4 5 6 7 8 9 A)( 5 6 7 8 9 A B)
( 2 3 4 5 6 7 8)( 3 4 5 6 7 8 9)( 4 5 6 7 8 9 A)( 5 6 7 8 9 A B)( 6 7 8 9 A B C)

---

Note, technically OP's code is using the wrong size. Usually sizeof(int*) will be the same as sizeof(int**), so no great harm. Yet it does indicate confusion about the allocation.

// wrong type  -----------------------v  should be int**
int ***a = (int***)malloc(3 * sizeof(int*));

Answer 3

Let's visualize what you're trying to do first, and then I'll show the code to get there:

  int ***         int **                int *                  int 

  +---+           +---+                 +---+                  +---+
a |   | ---> a[0] |   | ------> a[0][0] |   | ----> a[0][0][0] |   |
  +---+           +---+                 +---+                  +---+
             a[1] |   | ----+   a[0][1] |   | -+    a[0][0][1] |   |
                  +---+     |           +---+  |               +---+
             a[2] |   |     |            ...   |                ...
                  +---+     |           +---+  |               +---+
                            | a[0][h-1] |   |  |  a[0][0][w-1] |   | 
                            |           +---+  |               +---+
                            |                  |
                            |           +---+  |               +---+
                            +-> a[1][0] |   |  +--> a[0][1][0] |   |
                                        +---+                  +---+
                                a[1][1] |   |       a[0][1][1] |   |
                                        +---+                  +---+
                                         ...                    ...
                                        +---+                  +---+
                              a[1][h-1] |   |     a[0][1][w-1] |   |
                                        +---+                  +---+

Types:

• Each a[i][j][k] has type int;
• Each a[i][j] points to the first element of a sequence of int objects, so it must have type int *;
• Each a[i] points to the first element of a sequence of int * objects, so it must have type int **;
• a points to the first element of a sequence of int ** objects, so it must have type int ***.

Since you're doing a piecemeal nested allocation, you need to check the result of each malloc call, and if there's an error, you will want to clean up any previously allocated memory before bailing out, otherwise you risk memory leaks. Unfortunately, there's no really clean or elegant way to do that - you either carry a flag around and do a bunch of extra tests, or you throw in a couple of gotos. I'm going to show two different approaches, neither of which is all that pretty.

First method - as we allocate each a[i], we also allocate each a[i][j] (a "depth-first" approach) and initialize each a[i][j][k]. If an allocation on a[i][j] fails, we must deallocate all of a[i][0] through a[i][j-1], then deallocate a[i], then repeat the process for each of a[0] through a[i-1]:

/**
 * Depth-first approach: allocate each a[i][j] with each a[i]
 */
int ***alloc1( size_t pages, size_t height, size_t width )
{
  size_t i, j, k;

  int ***a = malloc( sizeof *a * pages ); // allocate space for N int **
                                          // objects, where N == pages

  if ( !a )
    return NULL;

  for ( i = 0; i < pages; i++ )
  {
    a[i] = malloc( sizeof *a[i] * height );  // for each a[i], allocate space for
    if ( !a[i] )                             // N int * objects, where N == height
      goto cleanup_1;

    for ( j = 0; j < height; j++ )
    {
      a[i][j] = malloc( sizeof *a[i][j] * width ); // for each a[i][j], allocate      
      if ( !a[i][j] )                              // space for N int objects,
        goto cleanup_2;                            // where N == w

      for ( k = 0; k < width; k++ )
        a[i][j][k] = initial_value( i, j, k );
    }
  }
  goto done;

/**
 * Free all of a[i][0] through a[i][j-1], then free a[i]
 */
cleanup_2:
  while ( j-- )
    free( a[i][j] );
  free( a[i] );

/**
 * Free all of a[0] through a[i-1], then free a
 */
cleanup_1:
  while ( i-- )
  {
    j = height;
    goto cleanup_2;
  }
  free( a );
  a = NULL;

done:
  return a;  // at this point, a is either a valid pointer or NULL.
}

Yes, this code contains gotos, and it violates one of my pet rules (never branch backwards). But, there's a fairly clean separation between the allocation code and the cleanup code, and we don't repeat ourselves in the cleanup sections. cleanup_2 deallocates all the rows within a page, along with the page itself; cleanup_1 deallocates all of the pages. cleanup_2 "falls through" into cleanup_1.

Here's a second method - first we allocate all a[i] before allocating any a[i][j], then we make sure all a[i][j] were successfully allocated before initializing the array contents.

/**
 * Breadth-first approach; allocate all a[i], then all a[i][j], then initialize
 */
int ***alloc2( size_t pages, size_t height, size_t width )
{
  size_t i, j, k;

  /**
   * Allocate space for N int ** objects, where N == pages
   */
  int ***a = malloc( sizeof *a * pages );

  if ( !a )
    return NULL;                        // allocation failed for initial sequence, return NULL

  for ( i = 0; i < pages; i++ )  // For each a[i], allocate N objects of type
  {                              // int *, where N == height
    a[i] = malloc( sizeof *a[i] * height );
    if ( !a[i] )
      break;
  }

  if ( i < pages )
  {
    while ( i-- )                       // allocation of a[i] failed, free up a[0] through a[i-1]
      free( a[i] );
    free( a );                          // free a
    return NULL;
  }

  for ( i = 0; i < pages; i++ )    
  {
    for ( j = 0; j < height; j++ )
    {
      a[i][j] = malloc( sizeof *a[i][j] * width ); // for each a[i][j], allocate    
      if ( !a[i][j] )                             // space for N int objects, 
        break;                                    // where N == width
    }
  }

  if ( j < h )
  {
    do
    {
      while ( j-- )                     // allocation of a[i][j] failed, free up a[i][0] through a[i][j-1]
        free( a[i][j] );                // repeat for all of a[0] through a[i-1].
      free( a[i] );
      j = h;
    } while ( i-- );
    free( a );                          // free a
    return NULL;
  }

  /**
   * All allocations were successful, initialize array contents
   */    
  for ( i = 0; i < pages; i++ )
    for ( j = 0; j < height; j++ )
      for ( k = 0; k < width; k++ )
        a[i][j][k] = initial_value( i, j, k );

  return a;
}

No gotos! But the code doesn't "flow" as well IMO. There's not as clean a separation between allocation and cleanup code, and there's a bit of repetitiveness between the cleanup sections.

Note that for both methods, the memory is not contiguous - the element immediately following a[0][0][h-1] is not going to be a[0][1][0]. If you need all your array elements to be adjacent in memory, you will need to use the method shown by the others:

int (*a)[h][w] = malloc( sizeof *a * 3 );

with the caveat that if h and w are large, you may not have enough contiguously allocated memory to satsify the request.