From: scs@adam.mit.edu (Steve Summit)
Subject: Re: multidimensional arrays as parameters
Organization: none, at the moment
Date: Fri, 16 Oct 1992 20:59:29 GMT

In article <454@ulogic.UUCP>, Richard M. Hartman (hartman@ulogic.UUCP) writes:
> [in a distressingly long thread, various people had written:]
>>> Now for a 2D array if I do the following:
>>>	int array2d[10][20];
>>>	void fun2d( int * );
>>
>> I've seen two responses to this, both claiming the correct declaration is:
>>	void fun2d( int ** );
>> This is incorrect.  array2d is not an array of pointers to arrays, but an
>> array of arrays.  Thus, the automatic conversion yields a pointer to an
>> array.  Thus fun2d should be:
>>	void fun2d( int * [20]);
> 
> Which begs the question, since the next array I pass may be [40][50],
> is there a more general approach?

Unfortunately, not a good one.

I am occasionally too weary of issues which I've tried to deal
with in the FAQ list to follow them in detail when they come up
again, so by not commenting on any of the other articles in the
foregoing "distressingly long thread" I am not implying consent
with all that has been said.  I trust that Chris was his
customary definitive self in his article of a day or two ago.

[Richard Hartman again:]
> I think that you might be stuck adding dimension params to the function
> and doing the math yourself.  It might not be the ONLY way, and it is
> certainly inconvenient, but it should work.  e.g.:
> 
>     void fun2d(int *arr, int xsiz, int ysiz)
>     {
>         *(arr+(ysiz*ycoord)+xcoord) = value;    /* arr[xcoord][ycoord]=value; */
> 
> Note: the order in which your machine (row-major or column-major) stores
> it's array-of-arrays will affect the math involved...

(It should probably be "arr+(ysiz*xcoord)+ycoord", but never mind.)

The "order in which the subscripts vary" (i.e. array layout) in C
is well-defined, although I'm not going to say whether it's
"row-major" or "column-major" (partly because it depends upon
your assignment of "row" and "column," and partly because I can't
really remember how those terms are conventionally used).

I've come to the conclusion that attempting to pass
multidimensional arrays to subroutines does point out some sort
of deficiency in C.  People are always bitching about all kinds
of other alleged shortcomings, particularly for numerical work
and with respect to FORTRAN, yet this one is rarely mentioned and
is to my mind considerably more serious (more fundamental, and
without a single really good workaround).

Part one of the deficiency is that you can't write a function
that accepts statically allocated, two- (or more) dimensional
arrays with arbitrary dimensions.  Using a straightforward
declaration, all but the first (i.e. in the first set of
brackets) dimension must be compile-time constants:

	extern f2d(int a2[][3]);
	extern f3d(int a3[][3][5]);

One of the most oft-cited deficiencies in Pascal is that you
cannot write a routine which accepts even an arbitrary-sized
one-dimensional array (the canonical example is a routine which
sorts an array of N numbers).  Yet C has the same problem for two
or more dimensions: you cannot (at least in the straightforward
and obvious way) write a routine to invert an arbitrary matrix,
or to perform arbitrary matrix multiplication [note 1].
(I believe gcc fixes this problem, but of course none of gcc's
extensions are yet standard.)

Part two of the deficiency is that it is very hard to write a
single function which accepts either conventional, statically
allocated multidimensional arrays or dynamically allocated
simulated multidimensional arrays.  There are several ways of
writing functions which accept variations on the theme of
multidimensional arrays, and several ways of dynamically
allocating simulated multidimensional arrays; if you pick just
the right combination(s), I think you can get everything to work,
but you have to be careful, and the function will almost
certainly have to do array subscripting "by hand," and the actual
array arguments will have to be passed carefully and perhaps
non-obviously at each function call.

Richard was definitely on the right track: the function will
probably have to accept a pointer-to-number (a pointer-to-double
or pointer-to-int, not a pointer-to-pointer or pointer-to-array),
and a number of explicit dimension arguments.  The two-
dimensional case would look like:

	f2dx(ary, dim1, dim2)
	int *ary;			/* ary[dim1][dim2] */
	int dim1, dim2;
	{
	...*(ary + i * dim2 + j)...	/* ary[i][j] */

(note that I have switched to an "array" of ints, and that I am
avoiding "x" and "y", because the correspondence is problematical).
The three-dimensional case would look like:

	f3dx(ary, dim1, dim2, dim3)
	int *ary;			/* ary[dim1][dim2][dim3] */
	int dim1, dim2, dim3;
	{
	...*(ary + (i * dim2 + j) * dim3 + k)...	/* ary[i][j][k] */

, and we could also write an n-dimensional case:

	fndx(ary, dims, ndims)
	int *ary;
	int dims[];
	int ndims;
	{
	int ia[MAXDIM];
	int ii, iii;

	iii = 0;
	for(ii = 0; ii < ndims; ii++)
		iii = dims[ii] * iii + ia[ii];
	...*(ary + iii)...		/* ary[ia[0]][ia[1]][ia[2]]... */

(Note: it is tricky to do subscripts "by hand" correctly, which
is one reason these aren't entirely adequate solutions to the
problem at hand.  Before using any of these code fragments, you'd
want to double check that my uses of dimensions and subscripts
agree with yours.)

The other tricky thing is calling these beasts correctly.
If we have conventional, statically-allocated multidimensional
arrays, we must pass the address of the first cell:

	int a2[2][3];
	int a3[2][3][5];
	f2dx(&a2[0][0], 2, 3);
	f3dx(&a3[0][0][0], 2, 3, 5);

	int dims[] = {2, 3, 5};
	fndx(&a2[0][0], dims, 2);
	fndx(&a3[0][0][0], dims, 3);

It would *not* be correct to attempt to "pass" the entire array:

	f2dx(a2, 2, 3);
	f3dx(a3, 2, 3, 5);

These would pass a pointer-to-array as the first argument, rather
than the required pointer-to-int.  They might appear to work
(because the numerical addresses passed, if you cared to examine
them, would probably be the same), but they would be incorrect.
(I am not going to belabor this point; if you are at all unsure
about this, reread section 2 in the FAQ list, or one of Chris's
excellent postings.)

Contrariwise, you *would* pass a2 or a3 to a function which
accepted a conventional multidimensional array (such as f2d and
f3d from farther back in this article) in the obvious way:

	f2d(a2);
	f3d(a3);

The fact that f2dx() and f3dx(), though they attempt to be
generic, have to be called non-obviously, indicates that they are
still not perfect solutions.  (You should not have to know this
much about a function's implementation in order to call it
correctly.)

Finally, let's see how we might pass dynamically allocated,
simulated multidimensional arrays to f2dx() and f3dx().  As I
mentioned, there are several ways of dynamically allocating
simulated multidimensional arrays, and not all of them will work
here.  Four of the ways, as extracted from the FAQ list, are
exemplified by the following code fragments:

	int **array1 = (int **)malloc(nrows * sizeof(int *));
	for(i = 0; i < nrows; i++)
		array1[i] = (int *)malloc(ncolumns * sizeof(int));

	int **array2 = (int **)malloc(nrows * sizeof(int *));
	array2[0] = (int *)malloc(nrows * ncolumns * sizeof(int));
	for(i = 1; i < nrows; i++)
		array2[i] = array2[0] + i * ncolumns;

	int *array3 = (int *)malloc(nrows * ncolumns * sizeof(int));

	int (*array4)[NCOLUMNS] =
		(int (*)[NCOLUMNS])malloc(nrows * sizeof(*array4));

array1, although it is in many ways the preferred method of
dynamically allocating multidimensional arrays, can *not* be
passed to f2dx (or, for that matter, f2d), because its contents
are not contiguous.

The others can be passed as follows:

	f2dx(array2[0], nrows, ncolumns);
	f2dx(array3, nrows, ncolumns);
	f2dx(&array4[0][0], nrows, NCOLUMNS);

Note the mysterious irregularities in the manner of passing the
first argument.  (Alternate forms could be correctly used for
all three "arrays," but they would still be irregular.)

Richard concluded his article with:
> q: would |void fun2d(int a[][])| be of any use (I don't *think* so...)

No; if you try it, you'll get a compilation error.

					Steve Summit
					scs@adam.mit.edu

Note 1.  In fairness to dmr, one of the great strengths of C (and
Unix) is that it attempts to solve 95% of the problems, rather
than 99%.  In doing so it remains small and (relatively) clean;
attacking the last few percent inevitably leads to huge expenses
in bulk and ugliness.  Particularly for what C was initially
designed for (sorry for dragging out the tired "systems work" vs.
"numerical work" excuse again), consigning truly general
multidimensional array handling to that last 5% may have been a
wise choice, particularly since it still isn't intractable (it
merely trades off ugliness in user code for potential ugliness in
the language).
Newsgroups: comp.lang.c,comp.os.msdos.programmer,comp.programming