Arrays in C language are static in nature, and cannot be resized at runtime. The effect of runtime allocation of an array could be achieved by hierarchically allocating blocks of memory at runtime. Below we discuss the mechanism to allocate multidimensional arrays.

One Dimension

Allocation of a one-dimension array dynamically is simple. We declare a char *p that is, a character type pointer (or a pointer of some other type), and then used malloc () to allocate 'n' locations to it (in this case which is sizeof (char) = 1 byte). Now we can use p as in normal array notation.

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

A sample code is shown the common practice of allocating a block of memory in runtime which acts like an array.

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

Although it might seem that the one-dimensional array and this allocated pointer access is the same thing, but it is not. The address of a statically defined array arr is itself the address of the first location of the array. Where as in the above case the pointer p contains an address which is the first location of the array. The below diagram would help make this clear.


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.


Understanding the access method

When allocating multidimensional array with the above technique some understanding of the array internal storage and pointer notations have to be understood.

A one-Dimension array, say char arr[10], is stored in the contiguous memory location. When we do the below operation

arr[i];

It first gets the base address of arr , say it is addr then seeks upto the ith location of the array by adding i * scale_factor bytes with addr and fetches the contents of (addr + i * scale_factor) . So arr[i] is equivalent of the expression *(addr + i + scale_factor). scale factor here is the size of the type of the array for a certain system. The scale_factor needs to be included because arr[i] will access the ith location and not the ith byte. For example char it is 1 byte, for integer it is 4 bytes. Generally it is sizeof (type) like sizeof (char), or sizeof (int). This array expression could also be written as follows:

*(arr + i)

Note that we do not need to include the scale_factor in the pointer equivalent expression, because depending on the type of arr the increment i will be automatically scaled by the compiler, following the rules of pointer arithmetic. For example if the pointer variable is a pointer to an integer and we do addr + i then this expression would point to the memory byte addr + i * sizeof (int). If addr = 0x20 then addr + 2 = 0x08 as each integer occupies 4 bytes, and so adding 2 to a pointer to an integer would result in skipping two integer locations, which is actually an 8 byte skip.

Consider the following definition of a 2 dimension character array:

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

The second line shows how to access the x,y th element from the array. This 2 dimensional array could be thought of an array of 10 locations with each location pointing to a 20 element char array. arr[x] will point to base address of the xth 20 element array among the 10 locations. This first dimension gets us the entire list. Within this 20 element list, we fetch the yth location using the second dimension arr[x][y]. The pointer notation for this access is shown below:

*(*(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 xth address of the 1st dimension, that is it points to the base address of the xth 20 element char array (among the available 10). *(arr + x) dereferences the pointer and gets the base address of the xth array. Let us name addr = *(arr + x). Fetching the second dimension now means to locate the yth location in this dereferenced memory block which can be found by the expression *(addr + y), which simply fetches the value (contents) at yth 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 ‘ith‘ 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

Advertisements