How one malloc call for all rows work for 2D array?

Question

I know that we can achieve dynamic multi-dimensional arrays using pointers and there are many ways to do it, with single pointers and double pointers as well. But while exploring on this topic, came across this piece of code in which I am not able to understand the head and tail. Can anyone please explain me how the below piece of code works?

Also please explain,

1) Why it is necessary to allocate r*sizeof(int*) to arr when we are anyways going to allocate memory to arr[i] as r*c*sizeof(int). 2) Why it is necessary to do arr[i] = *arr+c*i.

Since I am very new to this dynamic memory allocation and so much eager to dig little deeper, arised these questions. Sorry if it is basic but still I have no idea about it. Thanks,

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

int main()
{
    int r=3, c=4;
    int **arr;
    int count = 0,i,j;

    arr  = (int **)malloc(sizeof(int *) * r);
    arr[0] = (int *)malloc(sizeof(int) * c * r);

    for(i = 0; i < r; i++)
        arr[i] = (*arr + c * i);

    for (i = 0; i < r; i++)
        for (j = 0; j < c; j++)
            arr[i][j] = ++count;  // OR *(*(arr+i)+j) = ++count

    for (i = 0; i <  r; i++)
        for (j = 0; j < c; j++)
        {
            printf("%d, %p, %p\n", arr[i][j], &arr[i][j], arr[i]);
        }

    return 0;
}

Output:

1, 21100, 21100
2, 21104, 21100
3, 21108, 21100
4, 2110c, 21100
5, 21110, 21110
6, 21114, 21110
7, 21118, 21110
8, 2111c, 21110
9, 21120, 21120
10, 21124, 21120
11, 21128, 21120
12, 2112c, 21120

Answer 1

Instead of allocating for each of the r pointers allocated in arr, only the first one is used to allocate memory for an rxc array. And rest of the pointers points to chunk of this memory.

Benefit can be that it is possible to use single memset to initialize the array. Freeing is much more easier (just free the first pointer's allocated memory).

arr[i] = (*arr + c * i); this is basically initializing the pointer arr[i] with the relevant section to which it should point to.

And from the start of the allocated memory where will that be? There arr[0],arr[1]..arr[i-1] pointers which points to their rows which contains c elements each. So c elements each for i pointers - i*c elements all together is being addressed already. So the next one to be pointed by arr[i] will (*arr+c*i).

After OP edited the question:

OP asked why we need to do arr = (int **)malloc(sizeof(int *) * r) ?

I guess this picture explains a lot than words.

arr --> [0]  [1]  [2]   [3]  .....[r-2] [r-1]
         |    |    |     |           |    |
         V    |    |     |           |    |
        [0] <-+    |     |           |    |
        [1]        |     |           |    |
        [2]        |     |           |    |
        [3]        |     |           |    |
        [4]        |     |           |    |
         .         |     |           |    |
                   |     |           |    |
        [c-1]      |     |           |    |
        [c]   <----+     |           |    |
        [c+1]            |           |    |
        [c+2]            |           |    |
         .               |           |    |
         .               |           |    |
         .               |           |    |
        [2c]  <----------+           |    |
        [2c+1]                       |    |
        [2c+2]                       |    |
         .                           |    |
         .                           |    |
         .                           |    |
        [(r-2)*c] <------------------+    |
        [(r-2)*c+1]                       |
         .                                |
         .                                |
        [(r-2)*c+(c-1)]                   |
        [(r-1)*c]  <----------------------+
        [(r-1)*c+1]
        [(r-1)*c+2]
        [(r-1)*c+3]


        [(r-1)*c+(c-1)]~[rc-1] 

Those first row explains arr = malloc(sizeof(int *) * r);

You can see all allocated memory in the soingle column. Because that's what you did arr[0] = (int *)malloc(sizeof(int) * c * r);

And then the links explain arr[i] = (*arr + c * i);.

Check the thing, the links point to (*arr) also in pic [0]

and (*arr+c) in pic [c] and (*arr+2c) in pic [2c].

We need them because it is basically letting us get to the beginning of the correct address of the starting of each of the r rows.

The address are being calculated as offset from the beginning of the *arr.

If you didn't assign the addresses to arr[i] then you couldn't access the array like this arr[row][col] then you had to do arr[0][row*c+col] (You can see that image also says that thing).

Answer 2

This piece of code allocates two memory areas

• arr able to contain r pointers to int
• arr[0] area, for r * c int
• (*arr + c * i) is same as &arr[0][c*i]

then each r (row) is assigned a pointer to a location in arr[0] spaced by c (column) int (to store c int)

for(i = 0; i < r; i++)
    arr[i] = (*arr + c * i); 

graphically (with r == 3, and c == 4), P pointer, I integer

   arr: 0:P 1:P 2:P
        |   |   |
        v   v   v
arr[0]: IIIIIIIIIIII

then it just treats the array as a arr[row][col]

for (i = 0; i < r; i++)
        for (j = 0; j < c; j++)
            arr[i][j] = ++count; 

Answer 3

In C, arrays are stored in "row major" order in memory. That means in a two dimensional array elements in the same row are adjacent to I've another in memory, and so elements in the same column are spaced apart by the number of columns (i.e the row width).

*arr gives you back a pointer to an int because it is dereferencing a pointer to a pointer to an int. Specifically it is the pointer pointed to by the name arr. That is the base address of the array.

arr[i] is also a pointer to an int. Now remember what I said about row major. Where should i-th row pointer point? The answer is, at the base of the array (*arr) plus i times the number of columns (c). The loop that confuses you is merely making the others point at the right places so that implied pointer arithmetic works when it comes time to use arr[r][c] notation.

Voila.