Relay-Version: version B 2.10 5/3/83; site utzoo.UUCP
Path: utzoo!mnetor!seismo!mimsy!chris
From: chris@mimsy.UUCP (Chris Torek)
Newsgroups: comp.lang.c
Subject: Re: Portable Memory Allocation
Message-ID: <6973@mimsy.UUCP>
Date: Tue, 9-Jun-87 03:06:43 EDT
Article-I.D.: mimsy.6973
Posted: Tue Jun  9 03:06:43 1987
Date-Received: Thu, 11-Jun-87 06:30:40 EDT
References: <1645@umn-cs.UUCP>
Distribution: comp.lang.c
Organization: U of Maryland, Dept. of Computer Science, Coll. Pk., MD 20742
Lines: 110
Keywords: variant records

In article <1645@umn-cs.UUCP> herndon@umn-cs.UUCP (Robert Herndon) writes:
>... I want to represent nodes with a finite, fixed number of possible
>fields....  Some of these nodes will be relatively small, others large.
>I would like to allocate only enough memory for the union to hold the
>info necessary.  Is there any portable, COMPACT way to do this in C?

There is, but it relies upon an escape clause in K&R which may not
exist in the dpANS.  In the distant past (circa Research Version
6 Unix C) there were no unions; instead, one wrote

	/* example 1 */
	struct node {
		int	fixed_int;
		char	*fixed_str;
	};

	struct Anode {
		int	fixed_int;
		char	*fixed_str;
		struct	A a_part;
	};

	struct Bnode {
		int	fixed_int;
		char	*fixed_str;
		struct	B b_part;
	};

in place of

	struct node {
		int	fixed_int;
		char	*fixed_str;
		union {
			struct	A a_part;
			struct	B b_part;
		} u;
	};

In order for this to work, the compiler guarantees that in any two
structure declarations, if the `first part' of one structure matches
the `first part' of the second (here `fixed_int' and `fixed_str'),
those elements must lie at the same offsets and be addressed in
the same way in both structures.  This means that a `struct Anode'
and a `struct Bnode' can be treated as a `struct node' with impunity
(although in modern compilers it takes a type cast to change a
pointer from one kind to another).

Of course, the allocation

	struct Anode *p = (struct Anode *) malloc(sizeof (*p));

is perfectly legal; the assignment

	struct node *cathode = (struct node *) p;

is questionable, but (according to the escape clause) legal.  The
conversion back:

	struct Anode *Ap = (struct Anode *) cathode;

is then legal since `cathode' came from a cast from an Anode.

Assuming the compiler meets this requirement, and further (and
perhaps naively) assuming that it is required to begin all members
of a union at the same machine address, whatever `machine address'
`means', we can show that it must `do the right thing' with the
following:

	/* example 2 */
	struct node {
		int	fixed_int;
		char	*fixed_str;
		union {
			struct	A a;
			struct	B b;
		} u;
	};

	struct Anode {
		int	fixed_int;
		char	*fixed_str;
		struct	A a;
	};

	struct node *new_A_node()
	{
		struct node *p;

		p = (struct node *) malloc(sizeof (struct Anode));
		if (p == NULL)
			out_of_memory_abort();
		p->fixed_int = NODE_TYPE_A;
		p->fixed_str = NULL;
		p->u.a.i = 0;		/* whatever, etc. */
		return (p);
	}

The second assumption may not be correct; for certainty, see K&R or
Harbison & Steele, or if you are an optomist, the dpANS.

As to structure packing, if the second assumption does not hold,
proper massaging of the size of a `struct node' may save a few
bytes over example 2, but whatever arithmetic is required will be
entirely unportable.  Moreover, if this is the case, the original
`V6-style' declarations in example 1 will save the same amount of
memory, portably.  Three cheers for Version 6!
-- 
In-Real-Life: Chris Torek, Univ of MD Comp Sci Dept (+1 301 454 7690)
Domain:	chris@mimsy.umd.edu	Path:	seismo!mimsy!chris