allocate memory for 2d array c

Question

I've been reading a lot of the posts about allocating memory, and I think that I understand the concept, but I have been told that I have to use an approach that looks something like this:

double ** malloc_array2d(size_t m, size_t n)
{
    double **A;
    size_t i;

    A = malloc(m * sizeof(double *));      
    if (A == NULL) 
        return NULL;
    A[0] = (double *) malloc(m * n * sizeof(double));   
    if (A[0] == NULL) 
    {
        free(A); 
        return NULL;
    }

    for (i = 1 ; i < m ; i++) 
        A[i] = A[0] + i  *n; 
    return A;
}

And then of course I will have to free the memory later - but I just don't quite understand this kind of approach and more specifically I can't really see what happens in the last line where the remaining pointers are set into the block of memory (have i been told. And I am not sure how I will insert elements in the matrix/array when I am done allocating.

Answer 1

With this form of allocation, you start by allocating an array of pointers to other arrays, like so:

T **a = malloc( sizeof *a * N ); // N is the number of rows

sizeof *a is equivalent to sizeof (T *); each element of the array is going to be a pointer to T. When we're done, we have something like the following in memory:

   +---+
a: |   | a[0]
   +---+
   |   | a[1]
   +---+
   |   | a[2]
   +---+
    ...
   +---+
   |   | a[N-1]
   +---+

Now, for each of those elements, we allocate another chunk of memory to hold each element of type T:

a[i] = malloc( sizeof *a[i] * M ); // M is the number of columns

Each a[i] has type T *, so sizeof *a[i] is equivalent to sizeof (T).

After that's done, we have something that looks like this in memory:

   +---+           +---------+---------+   +-----------+
a: |   | a[0] ---> | a[0][0] | a[0][1] |...| a[0][M-1] |
   +---+           +---------+---------+   +-----------+
   |   | a[1] ---> | a[1][0] | a[1][1] |...| a[1][M-1] |
   +---+           +---------+---------+   +-----------+
   |   | a[2] ---> | a[2][0] | a[2][1] |...| a[2][M-1] |
   +---+           +---------+---------+   +-----------+
    ... 
   +---+           +-----------+-----------+   +-------------+
   |   | a[N-1]--> | a[N-1][0] | a[N-1][1] |...| a[N-1][M-1] |
   +---+           +-----------+-----------+   +-------------+

So basically what you've done here is allocate N separate M-element arrays of T, and then you collect the pointers to those arrays in an N-element array of T *.

You can access each element as a[i][j], like any normal 2D array; remember that the expression a[i] is defined as *(a + i); we offset i elements (not bytes!) from the address in a and then dereference the result. So a[i][j] is evaluated as *(*(a + i) + j ).

So, several things to remember with this form of allocation:

1. The "rows" of the array are not going to be contiguous in memory; the object in memory following a[i][M-1] is (most likely) not going to be a[i+1][0].

2. Since each "row" a[i] was allocated with a call to malloc, it must also be explicitly deallocated with a corresponding call to free before you deallocate a (always free in the reverse order that you malloc).

3. Even though we can treat a as a 2D-array, it does not have an array type, so you can't determine the size of the array using the sizeof a trick; you'll only get the size of the pointer type, not the total size of the array. So you'll want to keep track of the array size yourself.

Answer 2

double ** malloc_array2d(size_t m, size_t n){

    double **A;
    size_t i;

    A = malloc(m*sizeof(double *));      
    if (A == NULL) return NULL;
    A[0]=(double *)malloc(m*n*sizeof(double));   
    if ( A[0] == NULL) {free(A); return NULL;}
    for(i=1; i<m; i++) A[i]=A[0]+i*n; 

    return A;
}

Let's go Line by line:

A = malloc(m*sizeof(double *));

This line allocates space for m double pointers.

A[0] = (double *) malloc(m*n*sizeof(double));

A[0] is now a block of memory for m*n doubles, which is all the doubles we need for the 2d array.

for (int i = 1; i < m; i++) {A[i] = A[0] + i * n;}

because each A[i] is a block of n doubles, we want A[i] to start i*n doubles away from A[0].

Because all of this is in a solid block of memory, we can do some interesting things. For example, A[0][n] is the exact same double as A[1][0].

Furthermore, because everything is in one big block of memory, to access A[i][j] for any i < m, j < n, we just have to access the double at A[0] + i*j + j. This is much faster than going to A[i] which points to a double* B, and finding B[j].

Memory management is a difficult topic to understand and it takes some time. Hopefully this makes a bit more sense, and I hope I didn't confuse you even more :)

Answer 3

You have to make each pointer of the pointer of poitners to point to valid malloc()ed data.

for (int i = 0 ; i < n ; ++i)
    A[i] = (double *) malloc(m * sizeof(double)); 

You could also allocate it all at once, but then the notation A[i][j] will not work.