How to initialize a 3D contiguous array in C

Question

I know how to do a potentioal non-contiguous array in the following way:

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;
}

with the code above, the array[0][j] blocks can be not contiguous. To get contiguous, I feel that we need to malloc in this way

int* array = (int*)malloc(3*3*3*sizeof(int));
int** y = (int**)malloc(3*3*sizeof(int**));
int*** x = (int***)malloc(3*sizeof(int***));

  for(i = 0; i < 3; i++)
    {
      vals = vals + i*m*n;
      x[i] = &vals;
      for(j = 0; j < 3; j++)
    {
    x[i][j] = vals + j * n;
    }
    }

However, I got troulbe with address assignment. I am not a c programmer, can anyone correct my fault? Thanks in advance...

Answer 1

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

should be

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

Now initialization can be :

  for(i = 0; i < 3; i++)
  {
    x[i] = y + 3*i;
    for(j = 0; j < 3; j++)
    {
      x[i][j] = array + i*3*3 + j*3;
    }
  }

So that x[0] points to the first element of y, x[1] to the fourth, etc. And x[0][0]=y[0] to the first of array, x[0][1]=y[1] to the fourth of array, etc.

Answer 2

To allocate a contiguous 3D array, you only need to do the following (assumes all dimensions are known at compile time):

#define D0 ...
#define D1 ...
#define D2 ...
...
T (*arr)[D1][D2] = malloc( sizeof *arr * D0 ); // for any type T
...
arr[i][j][k] = some_value();
...

arr is declared as a pointer to a D1xD2 array. We then allocate enough space for D0 such arrays (sizeof *arr == sizeof (T [D1][D2])).

With this method, all of the memory for the array is allocated contiguously. Also, you only need one call to free to deallocate the whole thing.

If your dimensions are not known until runtime and you're using a C99 compiler or a C2011 compiler that supports variable-length arrays, you're still in luck:

size_t d0, d1, d2;
...
T (*arr)[d1][d2] = malloc( sizeof *arr * d0 );

The main issue is how to pass this as an argument to a function. Assuming that D1 and D2 are known at compile time, if you decide to pass it as

foo( arr, D0 );

then the prototype for foo will need to be

void foo( T (*aptr)[D1][D2], size_t n ) 
{
  ...
  aptr[i][j][k] = ...;
}

and it will only be useful for n x D1 x D2-sized arrays.

If you go the VLA route, you'll need to declare the dimensions and pass values for them as well:

void foo( size_t d0, size_t d1, size_t d2, T (*aptr)[d1][d2] ) // d1 and d2 *must* be 
                                                               // declared before aptr
{
  ...
  arr[i][j][k] = some_value();
}

void bar( void )
{
  size_t d0, d1, d2;
  ...
  T (*arr)[d1][d2] = malloc( sizeof *arr * d0 );
  ...
  foo( d0, d1, d2, arr );
  ...
}

If you don't have a compiler that supports VLAs, but you still want to allocate this memory contiguously, then you'll have to go the old-fashioned route - allocate it as a 1D array and compute your offsets manually:

T *arr = malloc( sizeof *arr * d0 * d1 * d2 );
...
arr[i * d0 * d1 + j * d1 + k] = some_value(); 

Answer 3

I am using some pretty neat methods for allocating multi-dimensional arrays with row pointers. The functions multi_malloc and multi_free can be used for arrays with arbitrary dimensions and arbitrary types and they work on basically all platforms and from C and C++

You can allocate, e.g. a 3-dimensional array with row-pointers recursively. E.g. a 10x20x30 dimensional array

float*** data = (float***) multi_malloc(sizeof(float),3, 10,20,20);

access elements like

data[2][3][4] = 2.0;

and free everything like (data as well as row pointers)

multi_free(data,3);

The header, which I think should be part of C is

#pragma once

#include <stdlib.h>
#include <stddef.h>
#include <stdarg.h>
#include <string.h>

#if (defined(_MSC_VER) && defined(_WIN32))
// Note when used inside a namespace, the static is superfluous
# define STATIC_INLINE_BEGIN static inline //__forceinline
# define STATIC_INLINE_END
#elif (defined(__GNUC__))
# define STATIC_INLINE_BEGIN static inline
# if defined(__CYGWIN__)
#  define STATIC_INLINE_END
# else
#  define STATIC_INLINE_END __attribute__ ((always_inline))
# endif
#endif

STATIC_INLINE_BEGIN void* multi_malloc(size_t s, size_t d, ...) STATIC_INLINE_END;

STATIC_INLINE_BEGIN void multi_free(void *r, size_t d) STATIC_INLINE_END;

/** 
 * Allocate multi-dimensional array and establish row pointers
 * 
 * @param s size of each element
 * @param d number of dimension
 * 
 * @return 
 */
STATIC_INLINE_BEGIN void* multi_malloc(size_t s, size_t d, ...) {

  char* tree;

  va_list ap;             /* varargs list traverser */
  size_t max,             /* size of array to be declared */
    *q;                   /* pointer to dimension list */
  char **r,               /* pointer to beginning of the array of the
                           * pointers for a dimension */
    **s1, *t;             /* base pointer to beginning of first array */
  size_t i, j;            /* loop counters */
  size_t *d1;             /* dimension list */

  va_start(ap,d);
  d1 = (size_t *) malloc(d*sizeof(size_t));

  for(i=0;i<d;i++)
    d1[i] = va_arg(ap,size_t);

  r = &tree;
  q = d1;                 /* first dimension */

  if (d==1) {
    max = *q;
    free(d1);
    return malloc(max*d);
  }

  max = 1;
  for (i = 0; i < d - 1; i++, q++) {      /* for each of the dimensions
                                           * but the last */
    max *= (*q);
    r[0]=(char *)malloc(max * sizeof(char **));
    r = (char **) r[0];     /* step through to beginning of next
                             * dimension array */
  }
  max *= s * (size_t) (*q);        /* grab actual array memory */
  r[0] = (char *)malloc(max * sizeof(char));

  /*
   * r is now set to point to the beginning of each array so that we can
   * use it to scan down each array rather than having to go across and
   * then down
   */
  r = (char **) tree;     /* back to the beginning of list of arrays */
  q = d1;                 /* back to the first dimension */
  max = 1;
  for (i = 0; i < d - 2; i++, q++) {    /* we deal with the last
                                         * array of pointers later on */
    max *= (*q);                        /* number of elements in this dimension */
    for (j=1, s1=r+1, t=r[0]; j<max; j++) { /* scans down array for
                                             * first and subsequent
                                             * elements */

      /*  modify each of the pointers so that it points to
       * the correct position (sub-array) of the next
       * dimension array. s1 is the current position in the
       * current array. t is the current position in the
       * next array. t is incremented before s1 is, but it
       * starts off one behind. *(q+1) is the dimension of
       * the next array. */

      *s1 = (t += sizeof (char **) * *(q + 1));
      s1++;
    }
    r = (char **) r[0];     /* step through to begining of next
                             * dimension array */
  }
  max *= (*q);              /* max is total number of elements in the
                             * last pointer array */

  /* same as previous loop, but different size factor */
  for (j = 1, s1 = r + 1, t = r[0]; j < max; j++)
    *s1++ = (t += s * *(q + 1));

  va_end(ap);
  free(d1);

  return((void *)tree);              /* return base pointer */
}

/** 
 * Free multi-dimensional array and corresponding row pointers
 * 
 * @param r data
 * @param d number of dimensions
 */
STATIC_INLINE_BEGIN void multi_free(void *r, size_t d) {

  void **p;
  void *next=NULL;
  size_t i;

  for (p = (void **)r, i = 0; i < d; p = (void **) next,i++)
    if (p != NULL) {
      next = *p;
      free(p);
      p = NULL;
    }
}

Answer 4

Although I think a normal array, created on the stack would be best:

int array[3][3][3];//can avoid a lot of free() calls later on

Here is a way to create a 3D array dynamically:
(I use calloc here instead of malloc as it creates initialized memory space)

int *** Create3D(int p, int c, int r) 
{
    int ***arr;
    int    x,y;

    arr = calloc(p, sizeof(arr)); //memory for int
    for(x = 0; x < p; x++)
    {
        arr[x] = calloc(c ,sizeof(arr)); //memory for pointers
        for(y = 0; y < c; y++)
        {
            arr[x][y] = calloc(r, sizeof(int));
        }
    }
    return arr;
}

Usage could be:

int ***array = Create3D(3,3,3);
for(i=0;i<3;i++)
        for(j=0;j<3;j++)
                for(k=0;k<3;k++)
                    array[i][j][k] = (i+1)*(j+1)*(k+1);

Note that the return of [c][m][re]alloc() is not cast in this example. Although not strictly forbidden in C, it is not recommended. (this is not the case in C++, where it is required)
Keep in mind, everything allocated, must be freed. Notice freeing is done in reverse order of allocating:

void free3D(int ***arr, int p, int c)
{
    int i,j;
    for(i=0;i<p;i++)
    {
        for(j=0;j<c;j++)
        {
            if(arr[i][j]) free(arr[i][j]);
        }
        if(arr[i]) free(arr[i]);
    }
    if(arr) free(arr);
}

Usage could be:

free3D(array,3,3);

Answer 5

You can allocate memory for buffer of items where each item is a two dimensional array. So it is effectively is a three dimensional array:

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

#define N 3

int main()
{
    int (*array)[N][N] = malloc(N * N * N * sizeof(int));

    /* set 0 to all values */
    memset(array, 0, N * N * N * sizeof(int));

    /* use as 3D array */
    array[0][0][0] = 1;
    array[1][1][1] = 2;
    array[2][2][2] = 3;

    int i;
    /* print array as contiguous buffer */
    for (i = 0; i < N * N * N; ++i)
        printf("i: %d\n", ((int*) array)[i]);

    free(array);

    return 0;
}

So, in memory the array is placed as regular int array[N][N][N].