herndon@umn-cs.UUCP (Robert Herndon) (06/09/87)
I have an application where I want to represent nodes with
a finite, fixed number of possible fields, e.g., applications
equivalent to pascal's variant records. 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?
E.g., I have nodes which look like:
struct node {
struct this_stuff x;
struct that_stuff y;
struct othr_stuff z;
union var_part {
struct childrenA a[27];
struct childrenB b[3];
struct childrenC c[42];
} c;
};
I would like to be able to make a call something like
nodeptr = malloc(sizeof(node)-sizeof(node.c)+sizeof(node.c.b))
to reserve just enough space to hold fields x, y, z, and c.b[3].
It seems that the above expression might allocate more space than
necessary (due to packing considerations), but should work. It
is also a kluge. Is there a more elegant method? Besides using
pascal?
--
Robert Herndon Dept. of Computer Science,
...!ihnp4!umn-cs!herndon Univ. of Minnesota,
herndon@umn-cs.ARPA 136 Lind Hall, 207 Church St. SE
herndon.umn-cs@csnet-relay.ARPA Minneapolis, MN 55455chris@mimsy.UUCP (Chris Torek) (06/09/87)
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
chris@mimsy.UUCP (Chris Torek) (06/09/87)
In article <6973@mimsy.UUCP> I wrote: >... or if you are an optomist, [see] the dpANS. An optometrist, perhaps? Make that `optimist'. It is late, and I should be sleeping; I must get up early tomorrow to track down those plane tickets so I can get to Usenix: B gave them to J; J is on vacation ... a pretty problem. (With luck, I will even have time to work out before I must leave. An unhackerly activity, I know; but then, I believe in breaking images. But what has any of this to do with C?) -- In-Real-Life: Chris Torek, Univ of MD Comp Sci Dept (+1 301 454 7690) Domain: chris@mimsy.umd.edu Path: seismo!mimsy!chris
jfjr@mitre-bedford.arpa (06/09/87)
If you want to allocate nodes oof various sizes efficiently
use an extra level of indirection
struct{
int constant_part
int type_tag
union{
char * pointer_to_one_thing
char * pointer_to_another_thing
char * pointer_to_still_another}
}
I've used this a couple of times in Pascal and C - as long
as you are careful especially in C to keep your types straight
it works fine
Jerry Freedman,Jr
jfjr@mitre-bedford.arp3/