Relay-Version: version B 2.10 5/3/83; site utzoo.UUCP
Posting-Version: version B 2.10.1 6/24/83; site umcp-cs.UUCP
Path: utzoo!watmath!clyde!burl!ulysses!mhuxl!ihnp4!zehntel!hplabs!hao!seismo!umcp-cs!chris
From: chris@umcp-cs.UUCP (Chris Torek)
Newsgroups: net.lang.c
Subject: Re: Array Access / Re: ... datum ** and [i][j]
Message-ID: <8156@umcp-cs.UUCP>
Date: Thu, 23-Aug-84 23:00:56 EDT
Article-I.D.: umcp-cs.8156
Posted: Thu Aug 23 23:00:56 1984
Date-Received: Sun, 26-Aug-84 01:42:18 EDT
References: <8131@umcp-cs.UUCP> <4040@fortune.UUCP>
Organization: U of Maryland, Computer Science Dept., College Park, MD
Lines: 75

Oops.  Clay Phipps' corrections are definitely in order.  For some
reason when I wrote that I thought of the indicies being stored in the
sub[] guys in backwards order.  I never did specify that (obviously I
wasn't thinking clearly there).  Oh well, at least I got the pointers
part right.  (Well, that is, I *assume* I got it right, or someone
would have pointed out any errors there, too, right? :-) )

``array_index'' *was* a lousy name, wasn't it?

By the way, (just to get revenge (-: ) this wasn't quite precise:

> Note that the code above takes advantage of the fact
> that C array declarations, like old-style FORTRAN (IV, 66),
> specify a size, instead of lower and upper bounds.
> With other languages like PL/I, Pascal, and Full FORTRAN 77,
> the dimension size t be calculated, usually at compilation time.

Actually, in the case of FORTRAN IV and FORTRAN 66, you'd also have to
subtract one from the given indicies, since the legal index values are
1 to ``size'' instead of C's 0 to ``size''-1.  In languages with
compiler support for arbitrary subscript ranges (in F77, stuff like
``INTEGER I(-10:10)'') the lower bounds have to be saved, too, along
with the sizes (or the upper bounds).  If the compiler is to do bounds
checking, then the upper bounds are required (and it's up to the
compiler writer to decide whether to compute the sizes once and save
them, or once for each array reference).

A complete row-major order implementation (that worked only with
constants for subscripts) might look like this:

/* a single array dimension, i.e., the -10:10 part of an F77 array */
struct arydim {
	int	ad_low;		/* lower bound */
	int	ad_high;	/* upper bound */
	int	ad_size;	/* high-low+1 */
};

#define MAXDIM 7		/* good enough for FORTRAN anyway */
				/* or have they changed it again? */

/* an array */
struct ary_descriptor {
	char	*a_name;	/* name of the array, for the assembler */
	int	a_ndims;	/* number of dimensions */
	struct arydim a_dim[MAXDIM];/* the dimensions themselves */
};

/* Compute the offset in the array described by `d' given the indicies
   in `sub'.  The number of subscripts has already been verified.
   The subscripts are stored such that sub[0] == leftmost,
   sub[MAXDIM-1] == rightmost possible. */
int
compute_offset (d, sub)
struct ary_descriptor *d;
int sub[MAXDIM];
{
	int i, off, t;

	off = 0;
	for (i = 0; i < d -> a_ndims; i++) {
		off *= d -> a_dim[i].ad_size;
		t = sub[i];
		if (t < d->a_dim[i].ad_low || t > d->a_dim[i].ad_high)
			uerror("array index out of range");
		off += t - d -> a_dim[i].ad_low;
	}
	return off;
}

One can generalize even further, to arrays whose sizes are computed
at run time, to extensible arrays, and so forth.
-- 
In-Real-Life: Chris Torek, Univ of MD Comp Sci (301) 454-7690
UUCP:	{seismo,allegra,brl-bmd}!umcp-cs!chris
CSNet:	chris@umcp-cs		ARPA:	chris@maryland