Allocating multidimentional array at runtime in C

char *p;
p = malloc (sizeof (char) * n);
p[i]; /* Accessing the allocated memory normally */

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

int
main (void)
{
  char *p;
  int dim1;

  printf ("\nEnter length of 1st dimension : ");
  scanf ("%d", &dim1);

  /* Allocate 'dim1' number of char locations */
  p = malloc (sizeof (char) * dim1);
  strcpy (p, "Hello");

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

  free (p);

  return 0;
}

char arr[10];

        arr
       +------+------+------+-----     -+------+-       -----+------+
       |arr[0]|      |      |     . . . |arr[i]|  . . .      |      |
       +------+------+------+-----     -+------+-       -----+------+

`arr` itself refers to the base address. (arr+i) denotes the `i`th address



char *arr;
arr = malloc (sizeof (char) * 10);

        arr
       +------+
       |      |       < ---- here the returned value of malloc goes in
       +------+
          |
          V        
       +------+------+------+-----     -+------+-       -----+------+
       |arr[0]|      |      |     . . . |arr[i]|  . . .      |      |
       +------+------+------+-----     -+------+-       -----+------+
 
`arr` is a pointer variable, and contains the base address of the array.
`arr + i` will add `i` (pointer arithmetic) to `arr` which will point to
the `i`th location of the allocated memory block.

arr[i];

*(arr + i)

char arr[10][20];
arr[x][y];

*(*(arr + x) + y)

                                      <                L O C A T I O N S                  >


     arr                              +-------------+-------+-------+----     ----+-------+
   +------+                     +---->|*(*(arr+0)+0)|       |       |    . . .    |       |
   |      |------->+---------+  |     +-------------+-------+-------+----     ----+-------+
   +------+        |*(arr+0) |--+              
                   +---------+        +-------+-------------+-------+----     ----+-------+
   ^    arr+1      |*(arr+1) |------->|       |*(*(arr+1)+1)|       |    . . .    |       |
                   +---------+        +-------+-------------+-------+----     ----+-------+
   L    arr+2      |*(arr+2) |----+
   O               +---------+    |   +------+------+-------+----     ----+---------------+
   C    arr+3      |*(arr+3) |-+  +-->|      |      |       |    . . .    |*(*(arr+2)+m-1)|
   A               +---------+ |      +------+------+-------+----     ----+---------------+
   T               |         | |      
   I                    .      |      +-------+-------------+-------+----     ----+-------+
   O                    .      +----->|       |*(*(arr+3)+1)|       |    . . .    |       |
   N                    .             +-------+-------------+-------+----     ----+-------+
   S               |         |                              .
                   +---------+                              .
   v     arr+n     |*(arr+n) |----+                         .
                   +---------+    |   +-------+-------+-------------+----     ----+-------+
                                  +-->|       |       |*(*(arr+n)+2)|    . . .    |       |
                                      +-------+-------+-------------+----     ----+-------+

Here arr is the base address of the array (type (char **)), of which, each location is of char * type and points to a block of memory consisting of 20 char type elements. (arr + x) is the pointer to the x^th address of the 1st dimension, that is it points to the base address of the x^th 20 element char array (among the available 10). *(arr + x) dereferences the pointer and gets the base address of the x^th array. Let us name addr = *(arr + x). Fetching the second dimension now means to locate the y^th location in this dereferenced memory block which can be found by the expression *(addr + y), which simply fetches the value (contents) at y^th location of the second dimension. This makes the access *(*(arr + x) + y). The second dimension contains data of type char, so what we get at the end is a character. A similar interpretation is applicable for integer and floating point arrays. In that note the addition/subtraction to the address would follow pointer arithmetic.

The case is similar for a 3d array with arr[x][y][z], or *(*(*(arr + x) + y) + z). The first dimension is a array of pointer to a pointer to a datatype, the second dimension is an array of a pointer to a datatype and the third dimension is an array of a data type.

The very important thing to note that the lowest dimension is not a pointer, it is an array of the actual data which we want to store. The subsequent higher levels are pointers to block of locations which contains to their respective lower array dimensions.

The basic thing is think of an array of ‘n’ pointers. Each of these pointers hold an address to an array of datatype of some length ‘m’. Now if we access the array of pointers at location ‘i’ then we can access the ‘i^th‘ array datatype of length ‘m’. Now accessing this array with index ‘j’ would get us the actual value which we needed. This is the case for a 2d access. This similar idea can be extended for 3, 4, and n levels. The pointers in the arrays are resolved from the top level dimension to the bottom level dimension by using the resolved result to find the next result pointer in a chain fashion by using the appropriate specified index at each level until the last level of this retrieval gets us the stored value.

Allocation

When allocating multi dimensional array we need to allocate the higher dimensions as needed, and then for each higher dimension location, we allocate arrays for the next level and continue like this till the last level.

Deallocation

Deallocation is equally important. In the case of allocation first the higher level dimension pointers are allocated and the place for the lower dimensions were made. The deallocation process is the opposite. The deallocation process starts from the lowest dimension of the allocated array. First all the lowest level of the dimension allocated memory are freed, and then the array of pointers holding them are freed and thus the freeing process climbs up the levels and at last frees the topmost pointer which was allocated at the first when allocating. Note that simply freeing the base pointer would not free the entire array in this case. This is because only the top level pointer arrays is frees, but the allocated memory blocks pointed by these location are not deallocated. Freeing like this would result in memory leakage as the lower level dimensions are not freed.

Sourcecode

Here I show some sample codes which show how to make this allocation and deallocation process work.

The below code shows how a 2-dimensional array can be allocated and deallocated dynamically.

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

int
main (void)
{
  char **p;
  int i, dim1, dim2;

  printf ("\nEnter length of 1st dimension : ");
  scanf ("%d", &dim1);

  printf ("\nEnter length of 2nd dimension : ");
  scanf ("%d", &dim2);

  /* Allocate the first dimension, which is actually a pointer to pointer to char   */
  p = malloc (sizeof (char *) * dim1);

  /* Then allocate each of the pointers allocated in previous step arrays of pointer to chars 
   * within each of these arrays are chars
   */
  for (i = 0; i < dim1; i++)
    {
      *(p + i) = malloc (sizeof (char) * dim2);
     /* or p[i] =  malloc (sizeof (char) * dim2); */
      strcpy (p[i], "Hello");
    }

  for (i = 0; i < dim1; i++)
    printf ("%d = %s\n", i, p[i]);

  /* Deallocate the allocated array. Start deallocation from the lowest level.
   * that is in the reverse order of which we did the allocation
   */
  for (i = 0; i < dim1; i++)
  {
    free (p[i]);
  }
  free (p);
  
  printf ("\n");
  return 0;
}

Because we are going to allocate a 2d array, the first dimension will contain an array of pointer to char (or whatever datatype), we allocate it with sizeof (char *) . Now, for each of the dim1 locations just allocated, malloc () is used to allocate a list of type char and size dim2 and assigned to the location. Note this time it is sizeof (char) as we define an array of datatypes. The deallocation is done in the reverse manner. The allocation process allocated dim1 number of lists of size dim2 the base address of these allocated memory blocks are held in the 1st dimension, these are freed first. At last we are left with the array of char * which we deallocate next.

A 3d dimensional address can be allocated and deallocated like this. As in the below example:

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

int
main (void)
{
  char ***p;
  int i, j, dim1, dim2, dim3;

  printf ("\nEnter length of 1st dimension : ");
  scanf ("%d", &dim1);

  printf ("\nEnter length of 2nd dimension : ");
  scanf ("%d", &dim2);

  printf ("\nEnter length of 3rd dimension : ");
  scanf ("%d", &dim3);

  /* Allocate the first dimension 'dim1' elements, which is actually 
   * a pointer to pointer a pointer to a char 
   */
  p = malloc (sizeof (char **) * dim1);

  /* Then allocate each of 'dim1' pointers allocated in previous step, 
   * arrays of length 'dim2' each of which contains pointer to a pointer to a char 
   */
  for (i = 0; i < dim1; i++)
    {
      *(p + i) = malloc (sizeof (char *) * dim2);

      /* Then allocate arrays of length of 'dim3' to each of which contains pointer to a char, 
       * to each pointer allocated in 2nd dimension previous step, allocate
       * Each of these pointer locations points to the characters 
       */
      for (j = 0; j < dim2; j++)
	{
	  *(*(p + i) + j) = malloc (sizeof (char) * dim3);
	  strcpy (p[i][j], "Hello");
	}
    }

  for (i = 0; i < dim1; i++)
    {
      for (j = 0; j < dim2; j++)
	printf ("(%d,%d) = %s\n", i, j, p[i][j]);
    }
    
  for (i = 0; i < dim1; i++)
  {
    /* free all the lowest level memory */
    for (j = 0; j < dim2; j++)
    {
      free (p[i][j]);
    }
    /* Now free the memory that was holding the above pointers */
    free (p[i]);
  }
  /* Now we can free the topmost level array */
  free (p);

  return 0;
}

First p is declared as a pointer to a pointer to a pointer to a char (char **). Then the first dimension is allocated, this will point ‘dim1’ number of arrays of pointer to a pointer to a char. Next each of the ‘dim1’ are assigned arrays of length ‘dim2’ each of whose elements are pointer to a char (char *). Next for each ‘dim1’ elements of 1st dimension, each ‘dim2’ elements of 2nd dimension are assigned character pointers of length ‘dim3’ (char). The deallocation is done in the reverse manner as I have already discussed.

To add more dimension first an appropriate level of pointer variable is defined and the allocations are done level-by-level, like a hierarchical fashion.

Others

Instead of doing the above if we know the size of the array before running the code but we want to dynamically allocate the array in the heap, instead of keeping it in stack or in data section (declaring as global) we can also do the below:

Here we have declared char (*p)[20]. This means p is a pointer to a character array of length 20. Whenever we want to allocate ‘n’ such array to p, we just do: p = malloc (sizeof (char[20]) * n) . This fixes the second dimension. Same in applicable with 3 or more dimension.

char (*p)[10][20];
p = malloc (sizeof (char[10][20]) * n);

Or even the below which mixes both:

char (**p)[20];
p = malloc (sizeof (char *) * n);
for (i=0; i < n; i++)
  *(p+i) = malloc (sizeof (char[20]) * m);

Some notes

I would like you make you aware that it is very important to free the memory which you have allocated with malloc (). In small codes like above the resources would be released automatically, but in real coding situation if the not-needed allocated memory area are not freed, and we keep on allocating such arrays, then the program would keep on allocating memory but never freeing. This is a memory leak situation, which will make the memory grow on the RAM, and at some point will crash or killed.

Another point which i should say here is that it is important to check the if the memory was really allocated or it has failed. malloc () will return NULL if no memory was allocated. For each malloc () usage we should check if the returned value from malloc () was NULL. If it was NULL then we should stop at there, retry or or break out of the program.

Sometimes we may require to allocate a multidimensional array while keeping all the rows of the array adjacent. This case is discussed here in this post: “Dynamically allocating 2d array with adjacent rows in memory”

More

• The New C:Why Variable Length Arrays?: http://drdobbs.com/cpp/184401444
• Dynamically allocating 2d array with adjacent rows in memory”