How are multi-dimensional arrays formatted in memory?

Question

In C, I know I can dynamically allocate a two-dimensional array on the heap using the following code:

int** someNumbers = malloc(arrayRows*sizeof(int*));

for (i = 0; i < arrayRows; i++) {
    someNumbers[i] = malloc(arrayColumns*sizeof(int));
}

Clearly, this actually creates a one-dimensional array of pointers to a bunch of separate one-dimensional arrays of integers, and "The System" can figure out what I mean when I ask for:

someNumbers[4][2];

But when I statically declare a 2D array, as in the following line...:

int someNumbers[ARRAY_ROWS][ARRAY_COLUMNS];

...does a similar structure get created on the stack, or is it of another form completely? (i.e. is it a 1D array of pointers? If not, what is it, and how do references to it get figured out?)

Also, when I said, "The System," what is actually responsible for figuring that out? The kernel? Or does the C compiler sort it out while compiling?

Answer 1

A static two-dimensional array looks like an array of arrays - it's just laid out contiguously in memory. Arrays are not the same thing as pointers, but because you can often use them pretty much interchangeably it can get confusing sometimes. The compiler keeps track properly, though, which makes everything line up nicely. You do have to be careful with static 2D arrays like you mention, since if you try to pass one to a function taking an int ** parameter, bad things are going to happen. Here's a quick example:

int array1[3][2] = {{0, 1}, {2, 3}, {4, 5}};

In memory looks like this:

0 1 2 3 4 5

exactly the same as:

int array2[6] = { 0, 1, 2, 3, 4, 5 };

But if you try to pass array1 to this function:

void function1(int **a);

you'll get a warning (and the app will fail to access the array correctly):

warning: passing argument 1 of ‘function1’ from incompatible pointer type

Because a 2D array is not the same as int **. The automatic decaying of an array into a pointer only goes "one level deep" so to speak. You need to declare the function as:

void function2(int a[][2]);

or

void function2(int a[3][2]);

To make everything happy.

This same concept extends to n-dimensional arrays. Taking advantage of this kind of funny business in your application generally only makes it harder to understand, though. So be careful out there.