Burning Rope puzzle
June 13, 2012
How to swap 2 variables witout using third
June 13, 2012

Allocating memory to n-dim Array on heap

Dynamic arrays are on heap. If an array is stored on heap, its address must be stored in pointer variables, else there will be no way to access the array.
Let us assume the Array to hold integers. Write a code to allocate memory to a 2-dim array and then generalize it to allocate memory to an n-dim array on heap.
Solution:

A one dimension array of N integers is allocated memory on the heap as below:

    int *p = (int*) malloc(N*sizeof(int));

sizeof(int) will make it portable because the size of integer may not be same on all environments. The element at i’th index can be accessed either like arrays or like pointers

a[i] or [a]i - Array way of accessing the i'th element
*(a + i) or *(i + a) - Pointer way of accessing the i'th element

If N = 10, the memory will look something similar to the below diagram:

In the above diagram, it is assumed that:

 1. Compiler allocated 2-bytes to integer.
    The actual amount of memory allocated to int depends on the compiler (sizeof(int))
    is normally equal to the word size of the machine on which the program is executing.
 2. word size of the machine is a byte (i.e each byte has an address).
 3. The malloc statement allocates 10 contiguous Integer memories (2-bytes) with starting address 1000.

Please note few interesting things:

1. The array is allocated memory on heap, but, Pointer p is resides on Stack
   (or data area, if it is declared in the global scope).
2. sizeof was a compile-time operator in C prior to C99. Some compilers may not have
   upgraded to the new standard. You should know this because if a program is compiled
   on one machine and is executed on different, incompatible platform, then your program
   may not give desired results, because the sizeof(int) may be different for different machines.

2-dimensional array:

a 2-dim array can be thought of as a 1-dim array whose individual elements are one-dimensional arrays. Even if you don’t think it this way, the memory allocation to a 2-dim array on heap will have to be like this only.

To accommodate a 2-dim array you need a pointer to int array (or a pointer-to-pointer-to-integer).

    int **p;

If the matrix is of 5*10 dimension (5 rows with 10 columns each). The memory allocation will be in two steps:

1. Allocate one dimensional memory of 5 int* and store its address in p.
2. Allocate one dimensional memory of 10 int five times and store their addresses
   in p[0], p[1], p[2], p[3] and p[4].

The below code demonstrates this:

    p = (int**)malloc(5 * sizeof (int*));
    for(int i=0; i<5; i++)
        p[i] = (int*) malloc(10 * sizeof(int));

After the memory allocation the picture of above allocated memory looks like below (I have skipped the addresses but shown the index of individual elements)

You can imagine that in case of pointers the array on the left side (blue) is an extra amount of memory allocated so that each element can be accessed. Had it been a 2-dim array on stack (int arr[5][10]) only 50 contiguous integers blocks of memory will be allocated. In the above case it is

 - 50 blocks of int memory location
 - 5 blocks of int* memory location
 - 1 int** memory location

each element (i,j)’th element of the matrix can be accessed using any of the below methods:

p[i][j], *(p+i)[j], *(p[i] + j), *(*(p+i)+j)

Basically we have to dereference both the levels of pointers to reach the actual element.

The advantage of this type of memory location is when we want each row of a matrix to have different number of columns, for example, consider the below picture:

A static matrix does not allow you to specify number of columns at each row level, so the static matrix, in above case has to be declared as arr[5][10] only and the unused memory locations will be a waste of space. But such requirements to declare matrix of variable length rows are very minimal in real life.

N-dim Array

Arrays of dimensions higher than 2 are difficult to visualize, but the process remains the same with one more added level of abstraction. For example: The address of a three-dimension array will be int *** and you need multiple loops as shown below.

C language code to allocate a 3-dim array of order A*B*C

    int *** p = (int***)malloc(A * sizeof(int**);
    for(int i=0; i<A; i++)
        p[i] = (int**) malloc( B* sizeof(int*));
    for(int i =0; i<A; i++)
        for(int j=0; j<B; j++)
            p[i][j] = (int*) malloc( C * sizeof(int));

and each element (i,j,k)’th element will be accessed like p[i][j][k] or *(*(*(p + i) + j) + k).

The above can be generalized to any dimension.

1 Comment

  1. […] Yesterday we learned about how to allocate memory on heap for an n-dim array using Malloc. […]

Leave a Reply

Your email address will not be published. Required fields are marked *