Path: utzoo!attcan!uunet!lll-winken!lll-lcc!ames!haven!mimsy!chris
From: chris@mimsy.UUCP (Chris Torek)
Newsgroups: comp.lang.c
Subject: computing &arr[negative_offset]
Message-ID: <13596@mimsy.UUCP>
Date: 17 Sep 88 11:30:04 GMT
References: <867@osupyr.mast.ohio-state.edu> <3200@geac.UUCP> <1430@ficc.uu.net> <16041@ism780c.isc.com>
Organization: U of Maryland, Dept. of Computer Science, Coll. Pk., MD 20742
Lines: 89

In article <16041@ism780c.isc.com> news@ism780c.isc.com (News system)
[really Marv Rubinstein in disguise] writes:
>But consider what might have happened had dpANS mandated that the compution
>of a pointer to x[-1] be a valid operation.  Then machines for which the
>mandated behavior is slow would be not used by people interested in high
>performance.  The net effect could be salubrious for the computer industry
>in the long run.

Perhaps.  I, for one, would find it useful to be Officially Allowed to
compute &arr[negative_offset].  I already make use of this (nonportably) in
existing code.  There is a second pitfall, however.

Consider the following (not strictly conforming) code:

	struct array_descriptor {
		int	low;		/* lower bound */
		int	bound;		/* upper bound - lower bound */
		int	*data;		/* pointer to &data[0] */
	};

	/*
	 * Allocate a new array whose subscripts range from [low..high)
	 */
	struct array_descriptor *new_array(int low, int high) {
		struct array_descriptor *p;
		int bound, *dp;

		/* first get a descriptor */
		if ((p = (struct array_descriptor *)malloc(sizeof(*p))) == NULL)
			return (NULL);

		/* then check for degenerate arrays (no data) */
		p->low = low;
		if ((bound = high - low) <= 0) {
			p->bound = 0;
			p->data = NULL;
		} else {
			/* allocate data */
			if ((dp = (int *)malloc(bound * sizeof(*dp))) == NULL) {
				free((char *)p);
				return (NULL);
			}
			p->bound = bound;
			p->data = &dp[-low];	/* virtual zero point */
		}
		return (p);
	}

If the computation `&dp[-low]' does not over- or under-flow, it
produces some pointer.  If `low' is positive, it produces a pointer
that does not point to valid data, but as long as that pointer is
used by adding a value in [low..high) before indirecting, things
should work out.

Now consider the free routine:

	void free_array(struct array descriptor *p) {

		if (p->data != NULL)
			free((char *)(&p->data[p->low]));
		free((char *)p);
	}

Do you see the hidden assumption here?

		if (p->data != NULL)

but p->data is not a `valid' pointer.  Maybe we had best write

		if (&p->data[p->low] != NULL)

but this is no good either (look again at new_array).  At least

		if (p->bound)

seems safe.  But what *really* happens if, in new_array, &p->data[-low]
turns out to `just happen' to equal NULL?

The approach I used in my own (nonportable) code was to keep the
original pointer around, just in case (and because there was no
p->bound available: allocation of data objects is deferred until they
are needed).  This also `just happens' to keep happy some garbage
collecting C runtime systems.  The above code, run on such a system,
might fail mysteriously after the garbage collector runs---because the
data pointer computed by &p->data[-100] is outside the region allocated
by malloc.  The GC routine would assume it was free, and cheerfully
release it for another malloc().
-- 
In-Real-Life: Chris Torek, Univ of MD Comp Sci Dept (+1 301 454 7163)
Domain:	chris@mimsy.umd.edu	Path:	uunet!mimsy!chris