How does C allocate data items in a multidimensional array?
I would like to know how C will allocate data elements of a multidimensional array and if their distribution is consistent across machines.
I know that at the lowest level, the items are neighbors, but I don't know how they are located next.
For example, if I am allocating a 3D array as int threeD[10][5][6]
, can I guess what &(threeD[4][2][5]) + 1 == &(threeD[4][3][0])
? On all machines?
Thanks in advance for your help.
source to share
The items are preserved in the Row Major . Thus, items along the last dimension are contiguous. However, elements between lines (as pointed out by your example) do not guarantee continuity. It depends on how the original memory was allocated.
#include <malloc.h>
#include <stdio.h>
#include <stdlib.h>
// only elements in a single row are guaranteed to be
// contiguous because of the multiple mallocs
void main(void)
{
// 3 rows, 4 columns
int *a[3];
for ( int row = 0; row < 3; row++ )
a[row] = (int *)malloc(4*sizeof(int));
}
// all elements are guaranteed to be contiguous
// in a row major order.
void main(void)
{
// 3 rows, 4 columns
int *a[3];
int *buf = (int *)malloc(3*4*sizeof(int));
for ( int row = 0; row < 3; row++ )
a[row] = buf+4*row;
assert( (&a[1][3] + 1) == &a[2][0] );
}
source to share
Yes, arrays are stored in top order of strings in all C compiler implementations.
The standard says (I applied some reformatting):
6.5.2.1 Array subscripting
Constraints
3 Successive subscript operators designate an element of a multidimensional
array object.
If E is an n-dimensional array (n> = 2) with dimensions i * j *. ... ... * k,
then E (used as other than an lvalue) is converted to a pointer to an
(n - 1) -dimensional array with dimensions j *. ... ... * k.
If the unary * operator is applied to this pointer explicitly, or
implicitly as a result of subscripting, the result is the pointed-to
(n - 1) -dimensional array, which itself is converted into a pointer if
used as other than an lvalue. It follows from this that arrays are stored
in row-major order (last subscript varies fastest).
source to share
The C standard is very specific for equating subtypes of an array with pointer arithmetic, and specifies that arrays are stored in basic string order.
Consider the array object defined by the declaration
int x[3][5];
Here x
is a 3 x 5 array of int; more precisely, it x
is an array of three element elements, each of which is an array of five integers. In an expression x[i]
, which is equivalent
(*((x)+(i)))
, it is x
first converted to a pointer to an initial array of five integers. then it is
i
adjusted according to the type x
, which conceptually entails multiplying i
by the size of the object the pointer points to, namely an array of five int objects. The results are added and indirection is applied to get an array of five integers. When used in an expression, x[i][j]
this array, in turn, is converted to a pointer to the first of an int, therefore x[i][j]
giving an int.
source to share
First, In C-address arithmetic is defined only within the bounds of a given array. (I meant to say "one-dimensional (SD) array", but technically all arrays in C are SD. Multidimensional arrays are built like SD arrays of SD arrays. And this kind of arrays is the most suitable for this topic) In C, you can start with a pointer to the beginning of an array and move back and forth within that array using additive operations. You are not allowed to cross the boundaries of the array you started with, except it is legal to form a pointer to an imaginary element that follows the last element. However, when it comes to accessing elements (read and write), you are allowed access to the real, existing elements of the array you started with.
Second, in your '& threeD [4] [2] [5] + 1' example, you are constructing a pointer to an imaginary past-last element of the threeD [4] [2] array. This in itself is legal. However, the language specification does not guarantee that this pointer is equal to the address '& threeD [4] [3] [0]'. The only thing he says is that he can be equal to him. It is true that the other language specification requirements for arrays pretty much force this relationship to hold. But this is not formally guaranteed. Some pedantic (so much malicious) implementation is perfectly legal to use some kind of compiler magic to break this relationship.
Third, actually accessing '* (threeD [4] [2] [5] + 1)' is always illegal. Even if the pointer points to the next array, the compiler is allowed to perform the necessary runtime checks and generate a segmentation fault because you are using pointer arithmetic on the array "threeD [4] [2]" and trying to access something outside of its bounds.
Fourth, doing "threeD [4] [2] [5] + 2", "... + 3", etc. is always illegal for the same reasons (remember: one end, OK, but 2, 3 or more is illegal).
And finally, fifth: yes, I know that in many (if not most) (if not all) practical cases, interpreting the array "TA [2] [3] [4]" as flat "TA [2 * 3 * 4] will work. But again, from a formal language point of view, this is illegal. And don't be surprised if this perfectly working code one day raises a huge number of warnings from some static or dynamic code analysis tool, if not from the compiler itself. ...
source to share