2-D array in single malloc call

Question

int **arrayPtr; 
arrayPtr = malloc(sizeof(int) * rows *cols + sizeof(int *) * rows);

In the above code, we are trying to allocate a 2D array in a single malloc call. malloc takes a number of bytes and allocates memory for that many bytes, but in the above case, how does malloc know that first it has to allocate a array of pointers, each of which pointer points to a one-dimensional array?

How does malloc work internally in this particular case?

Answer 1

2D arrays aren't the same as arrays of pointers to arrays.

int **arrayPtr doesn't define a 2D array. 2D arrays look like this:

int array[2][3]

And a pointer to the first element of this array would look like:

int (*array)[3]

which you can point to a block of memory:

int (*array)[3] = malloc(sizeof(int)*5*3);

---

Note how that's indexed:

• array[x] would expand to *(array+x), so "x arrays of 3 ints forward".
• array[x][y] would expand to *( *(array+x) + y), so "then y ints forward".

There's no immediate array of pointers involved here, only one contignous block of memory.

If you'd have an array of arrays (not the same as 2D array, often done using int** ptr and a series of per-row mallocs), it would go like:

• ptr[x] would expand to *(array+x), so "x pointers forward"
• ptr[x][y] would expand to *( *(array+x) + y) = "y ints forward".

Mind the difference. Both are indexed with [x][y], but they are represented in a different way in memory and the indexing happens in a different manner.

Answer 2

how does malloc know that first it has to allocate a array of pointers, each of which pointer points to a one-dimensional array?

It doesn't; malloc simply allocates the number of bytes you specify, it has no working knowledge of how those bytes are structured into an aggregate data type.

If you're trying to dynamically allocate a multidimensional array, you have several choices.

If you're using a C99 or C2011 compiler that supports variable length arrays, you could simply declare the array as

int rows;
int cols;
...
rows = ...;
cols = ...;
...
int array[rows][cols];

There are a number of issues with VLAs, though; they don't work for very large arrays, they can't be declared at file scope, etc.

A secondary approach is to do something like the following:

int rows;
int cols;
...
rows = ...;
cols = ...;
...
int (*arrayPtr)[cols] = malloc(sizeof *arrayPtr * rows);

In this case, arrayPtr is declared as a pointer to an array of int with cols elements, so we're allocating rows arrays of cols elements each. Note that you can access each element simply by writing arrayPtr[i][j]; the rules of pointer arithmetic work the same way as for a regular 2D array.

If you aren't working with a C compiler that supports VLAs, you'll have to take a different approach.

You can allocate everything as a single chunk, but you'll have to access it as a 1-d array, computing the offsets like so:

int *arrayPtr = malloc(sizeof *arrayPtr * rows * cols);
...
arrayPtr[i * rows + j] = ...;

Or you can allocate it in two steps:

int **arrayPtr = malloc(sizeof *arrayPtr * rows);
if (arrayPtr)
{
  int i;
  for (i = 0; i < rows; i++)
  {
    arrayPtr[i] = malloc(sizeof *arrayPtr[i] * cols);
    if (arrayPtr[i])
    {
      int j;
      for (j = 0; j < cols; j++)
      {
        arrayPtr[i][j] = some_initial_value();
      }
    }
  }
}

Answer 3

malloc() does not know that it needs to allocate an array of pointers to arrays. It simply returns a chunk of memory of the requested size. You can certainly do the allocation this way, but you'll need to initialize the first "row" (or last, or even a column instead of a row - however you want to do it) that are to be used as pointers so that they point to the appropriate area within that chunk.

It would be better and more efficient to just do:

int *arrayPtr = malloc(sizeof(int)*rows*cols);

The downside to that is that you have to calculate the proper index on every use, but you could write a simple helper function to do that. You wouldn't have the "convenience" of using [] to reference an element, but you could have e.g. element(arrayPtr, x, y).

Answer 4

I would re-direct your attention rather to question of "what does [] operator do?".

If you plan to access elements in your array via [] operator, then you need to realize that it can only do off-setting based on element's size, unless some array geometry info is supplied.

malloc does not have provisions for dimension info, calloc - explicitly 1D. On the other hand, declared arrays (arr[3][4]) explicitly specify the dimensions to the compiler.

So to access dynamically alloc'ed multi-D arrays in a fashion arr[i][j], you in fact allocate the series of 1D-arrays of the target dimension size. You will need to loop to do that.

malloc returns plain pointer to heap memory, no information about geometry or data-type. Thus [][] won't work, you'll need to the offsetting manually.

So it's your call whether []-indexing is your priority, or the bulk allocation.

Answer 5

int **arrayPtr; does not point to a 2D array. It points to an array of pointers to int. If you want to create a 2D array, use:

int (*arrayPtr)[cols] = calloc(rows, sizeof *arrayPtr);