Relay-Version: version B 2.10 5/3/83; site utzoo.UUCP
Posting-Version: version B 2.10.2 8/7/84; site ucbvax.ARPA
Path: utzoo!watmath!clyde!cbosgd!ihnp4!ucbvax!wildbill
From: wildbill@ucbvax.ARPA (William J. Laubenheimer)
Newsgroups: net.lang.c
Subject: Re: help converting multi-dim arrays
Message-ID: <6131@ucbvax.ARPA>
Date: Wed, 10-Apr-85 04:06:27 EST
Article-I.D.: ucbvax.6131
Posted: Wed Apr 10 04:06:27 1985
Date-Received: Wed, 10-Apr-85 23:39:02 EST
References: <569@utcs.UUCP>
Reply-To: wildbill@ucbvax.UUCP (William J. Laubenheimer)
Organization: University of California at Berkeley
Lines: 176
Summary: Implementation of n-d dynamic arrays (WARNING: kinda hefty)

>From utfyzx!harrison Thu Apr  4 19:53:50 1985
>Received: by utcs.UUCP (4.24/4.7) id AA12979; Thu, 4 Apr 85 19:53:46 est
>Date: Thu, 4 Apr 85 19:53:46 est
>From: utfyzx!harrison
>Apparently-To: physics
>[]
>The problem: a large piece of code with a number of arrays, some 
>2 dimensional and a few 3 dimensional, accessed with lines like:
>    for(row=0; row<numrows; row++)
>        for(col=0; col<numcols; col++)
>            ...data[row][col] ...
>The declaration of the matrices, such as
>    static double data[MAXROWS][MAXCOLS]; /* just like FORTRAN */
>is larger than any conceivable set of data it will be asked to 
>deal with, and wastes scads of memory.  So, we want to convert 
>the code to use malloc(3C) to dynamically allocate memory and 
>save all that wasted space. But, we still want to access the 
>matrices as:
>           ...data[row][col] ...
>because: 1) we don't want to change all the code, and 
>2)  the application makes one think in matrices and so this way 
>of writing the code will be much easier to maintain.  Thus, we 
>are trying to avoid:
>    static double *data;
>with access via stuff like:
>            ... *(data + row*numcols + col) ...
>Any ideas?
>Dave Harrison, Dept. of Physics, Univ. of Toronto: ..utzoo!utcs!physics

Yes. Essentially, you replace the "block of storage" concept with a
"array of arrays of smaller dimension" concept. Thus, a 3-d array
is an array of 2-d arrays, and a 2-d array is an array of 1-d arrays.
The interesting thing about C is that it lets you do this without having
to place the subarrays contiguously in memory or even knowing how big they
are. A good example of this is provided by the declaration of argv in

main (argc, argv) int a; char **argv; (or char *argv[])

You can access individual characters of the arguments by argv[argn][cpos],
and the individual elements are of different lengths. All this is brought
to you by the partial equivalence of pointers and arrays.

The general form for an n-dimensional array represented as a 1-dimensional
array of (n-1)-dimensional arrays is:

<object> ** ... * arrayName;
         (n *'s)

where <object> is the type being stored in the array.

Now for the details of implementation. A simple implementation which
isn't too bad if you have a small number of types and don't go too
high in the dimension hierarchy consists of the functions arr_2dOfObject,
... arr_ndOfObject, where "Object" is replaced by the particular type
you are generating arrays for, and n tops out at the highest dimension
you need for that type. The procedures are:

char	*calloc();

/*
	Getting things started - the 2-d case.
	Replace Object by the element type.
*/

Object
**arr_2dOfObject(dim1, dim2)
	int	dim1, dim2;
{
	Object	**array;
	int	index;

	array = (Object **)calloc(dim1, sizeof (Object *));
	for (index = 0; index < dim1; index++)
		array[index] = (Object *)calloc(dim2, sizeof (Object));
	return array;
}

/*
	Continuing along - the general case.
	Replace Object by the element type.
	Replace _n_ by the number of dimensions the function is being
	defined for. Similarly for _n-1_, etc.
*/

Object
** ... *arr__n_dOfObject(dim1, ..., dim_n_)
/* _n_ *'s,		 _n_ dim's */
	int	dim1, ..., dim_n_;
{
	Object	** ... *array;
/*		_n_ *'s */
	int	index;

	array = (Object ** ... *)calloc(dim1, sizeof (Object ** ... *));
/*			_n_ *'s				     _n-1_ *'s */
	for (index = 0; index < dim1; index++)
		array[index] = arr__n-1_dOfObject(dim2, ..., dim_n_);
	return array;
}

***** END OF SIMPLE-MINDED IMPLEMENTATION *****

The following changes need to be made to convert a program using Object[][]-
style arrays to **Object-style arrays:

For each type Object which will use the pointer format, the array
initializing functions arr_2dOfObject, ..., arr__n_dOfObject must be
defined up to the maximum n for which the pointer format will be used
on this object;

The declaration of each array using the pointer format is changed, with one
prefix * being added for each postfix [] which is removed;

*VERY IMPORTANT*: Each array using the pointer format *MUST BE INITIALIZED*
before it can be used. To initialize an array of size d1 x d2 x ... x dn,
use array__n_dOfObject(d1, ..., dn). The return value is an array of the
appropriate dimensions.


OK. That's how the simple model works. Now, here's a tricky one that
purports to do all of the above with just one procedure, but assumes that
you have a reasonable pointer mode (all pointers are the same size, pointer
conversion is the identity, calloc() handles potential alignment
problems (if they exist) satisfactorily) and you don't mind
weird-looking casts:

/*
	Initialize an n-dimensional array of size-byte objects.
	The array dim[] is an n-element array where dim[i] is the
	number of elements along dimension n.
*/

char	*calloc();

char
*arr_nD(n, dim, size)
	int	n;
	int	*dim;
	int	size;
{
	char	*array;

	if (n == 1)
		array = calloc(dim[0], size);
	else {
		array = calloc(dim[0], sizeof (char *));
		for(index = 0; index < dim[0]; index++)
			array[index] = arr_nD(n - 1, dim + 1, size);
	}
}

***** END OF BETTER VERSION FOR WELL-BEHAVED ARCHITECTURES *****

A sample initialization which shows how the initialization changes here
(everything else remains the same as the previous version) is for
a 3-dimensional length x width x depth array of doubles:

int	d[3];
double	***arr;

d[0] = length;
d[1] = width;
d[2] = depth;
arr = (double ***)arr_nD(3, d, sizeof(double));

--------------------------------------------------------------------

No guarantees on any of this stuff, unfortunately. I have used some
variants of the simple case, but have never had large numbers of these
beasts running around in the same program. If it doesn't work, show
it to your best approximation to a local C wizard and see if he can
get it to fly for you.

                                        Bill Laubenheimer
----------------------------------------UC-Berkeley Computer Science
     ...Killjoy went that-a-way--->     ucbvax!wildbill