struct pointer casting

4 views
Skip to first unread message

leic...@zodiac.rutgers.edu

unread,
Mar 22, 1993, 12:10:11 PM3/22/93
to
Suppose I wish to build a tree containing three kinds of nodes. They
are:

struct a
{ int type;
...whatever...
};

struct b
{ int type;
...whatever...
};

struct c
{ int type;
...whatever...
};

Note that all the struct's have a "type" field, of the same type, as their
first fields.

I could, of course, use a union of all these struct's as a "universal"
node, but that may waste space; I'd like to allocate only as much space
as each node requires. So, I do the following:

typedef union u
{ struct a a;
struct b b;
struct c c;
} NODE;

I never actually allocate any NODE's; rather, I do something like the
following:

NODE *make_anode()
{ struct a *an;

an = (NODE *)malloc(sizeof struct a);
...fill in *an...
return((NODE *)an);
}

(and similarly to make b nodes and c nodes.)

Later, I'm given a NODE *n.

a) To determine the type, I look at (struct a *)n->type.
b) Having determined that the type is, say, a b node, I now do:

{ struct b *bn = (struct b *)n;

...access b's fields...
}

Do (a) and (b) conform with ANSI? In effect, this comes down to the degree
to which all struct pointers "small the same": If I cast a pointer to a
struct a to a pointer to NODE (union u) and then cast it back, do I recover
the original pointer? (This is (b).) If I cast the NODE pointer to some
OTHER kind of struct pointer, but one which has the same leading field, can
I use it to access that field? (This is (a).)

-- Jerry

Norman Diamond

unread,
Mar 22, 1993, 9:50:20 PM3/22/93
to
In article <1993Mar22...@zodiac.rutgers.edu> leic...@zodiac.rutgers.edu writes:
> struct a { int type; ...whatever... };
> struct b { int type; ...whatever... };
> struct c { int type; ...whatever... };
>Note that all the struct's have a "type" field, of the same type, as their
>first fields.

>I'd like to allocate only as much space as each node requires. So, I do


> typedef union u { struct a a; struct b b; struct c c; } NODE;
>I never actually allocate any NODE's; rather, I do something like

> NODE *make_anode()
> { struct a *an;
> an = (NODE *)malloc(sizeof struct a);
> ...fill in *an...
> return((NODE *)an);
> }

If you assigned the result of malloc() to an without a cast, the assignment
would work because malloc's return type is void*. However, you cast to NODE*,
which is not compatible with struct a*, so the assignment should be diagnosed.
Let's assume you delete that cast (or change it to cast to struct a*).
Although the standard does not explicitly state that all structure pointers
have identical size and alignment, someone proved it a few years ago from
other requirements in the standard. So when you cast an to NODE* and return
it, that should work, though of course you have to cast that result back to
the appropriate struct pointer type before dereferencing the pointer.

>Later, I'm given a NODE *n.
>a) To determine the type, I look at (struct a *)n->type.

You want to cast the pointer, so you need ((struct a *)n)->type.

If the actual structure (which you malloc'ed) had type struct b, and struct b
is shorter than struct a, then this can get you in trouble. (If you actually
had a NODE there, then the standard provides that you can fetch your type
field using the a or b or c member of the NODE union, but you don't actually
have a NODE there because you didn't want to use so much space.)

I think it should work if you do this:
struct z { int type; };


typedef union u { struct a a; struct b b; struct c c;

struct z z; } NODE;
and look at ((struct z *)n)->type.
Sorry, I don't have time to look up all the necessary reasoning in the
standard right now to prove it; I only think that it's possible.

>b) Having determined that the type is, say, a b node, I now do:
> { struct b *bn = (struct b *)n;
> ...access b's fields...
> }

After you've correctly determined the type, yes you can do this.
--
Norman Diamond dia...@jit.dec.com
If this were the company's opinion, I wouldn't be allowed to post it.
Beware the third sexually transmitted disease of the computer world: __STDC__

Mark Brader

unread,
Mar 26, 1993, 5:34:47 AM3/26/93
to
> > Later, I'm given a NODE *n.
> > a) To determine the type, I look at (struct a *)n->type.

> You want to cast the pointer, so you need ((struct a *)n)->type.
> If the actual structure (which you malloc'ed) had type struct b, and
> struct b is shorter than struct a, then this can get you in trouble.

> I think it should work if you do this:
> struct z { int type; };
> typedef union u { struct a a; struct b b; struct c c;
> struct z z; } NODE;
> and look at ((struct z *)n)->type.

I think these assertions are correct. Considering the rules on pointer
conversion involving unions and structs, it seems to me that

*(int *)n

would also be a correct solution, and simpler. (You could and probably
should hide it behind a suitbale macro, of course.)

> > b) Having determined that the type is, say, a b node, I now do:
> > { struct b *bn = (struct b *)n;
> > ...access b's fields...
> > }
>
> After you've correctly determined the type, yes you can do this.

However, it might be considered more readable to say

struct b *bn = &n->b;

which I think is equivalent.


There is one potential problem. Section 4.10.3/7.10.3 restricts the
alignment of pointers returned by malloc as follows:

# The pointer returned ... is suitably aligned so that it may be
# assigned to a pointer to any type of object and then used to
# access such an object or an array of such objects IN THE SPACE
# ALLOCATED ...

My emphasis added. It has been argued that this means that a call
to malloc(N) does not require the result to be aligned more strictly
than on multiples of N bytes, even if some types larger than N bytes
require stricter alignment. Maybe.

Suppose that this interpretation is correct, and that we have

struct a { int type; char toast; };
struct b { int type; int handwrite; };
struct c { int type; long double take; };

where int and long double are 2 and 8 bytes respectively, and are
required to be aligned on multiples of their own size. Then the
alignment requirement for struct c and for NODE is also 8 bytes,
these objects necessarily being 16 bytes long, while for struct a
and b, the alignment requirement is probably 2 bytes and the size
is 4 bytes.

Now when you do
malloc (sizeof (struct a));

you may get a pointer that cannot be legitimately converted to a
NODE *, because the alignment is wrong. And what is more, I don't
see any way around this problem -- IF the interpretation described
above is correct -- other than always malloc()ing the whole NODE
after all.

For this reason, I hope that the interpretation is wrong; indeed, the
Standard seems to imply that its writers intended the construct described
to work. But I haven't heard of an official ruling on the point I'm raising
about malloc().
--
Mark Brader "This is Programming as a True Art Form,
SoftQuad Inc., Toronto where style is more important
utzoo!sq!msb, m...@sq.com than correctness..." -- Pontus Hedman

This article is in the public domain.

Norman Diamond

unread,
Mar 28, 1993, 10:48:13 PM3/28/93
to
In article <1993Mar26.1...@sq.sq.com> m...@sq.sq.com (Mark Brader) writes:
>There is one potential problem. Section 4.10.3/7.10.3 restricts the
>alignment of pointers returned by malloc as follows:
># The pointer returned ... is suitably aligned so that it may be
># assigned to a pointer to any type of object and then used to
># access such an object or an array of such objects IN THE SPACE
># ALLOCATED ...
>My emphasis added. It has been argued that this means that a call
>to malloc(N) does not require the result to be aligned more strictly
>than on multiples of N bytes, even if some types larger than N bytes
>require stricter alignment. Maybe.

It has been argued that this means that a call to malloc(N) does not
require the result to be aligned more strictly than on multiples of

M, where M is the strictest alignment requirement of all types whose
sizes are N or less. Maybe.

The opposite has also been argued, since two separate operations are
permitted by that clause, and the program might not do the second one,
but should still be allowed to do the first one. But this might be a
moot point, because if an implementation can align some structs at less
strict boundaries, then in that implementation ALL struct pointers must
be capable of pointing at such less strict boundaries, though they would
not have to be capable of dereferencing while pointing there.

>Suppose that this interpretation is correct, and that we have
> struct a { int type; char toast; };
> struct b { int type; int handwrite; };
> struct c { int type; long double take; };

typedef union { struct a a; struct b b; struct c c; } NODE;


>Now when you do
> malloc (sizeof (struct a));
>you may get a pointer that cannot be legitimately converted to a
>NODE *, because the alignment is wrong.

I think that is not possible, because it has previously been proven that
all struct pointers (and union pointers, I believe) must have identical
representations. The problem for the original poster was in dereferencing.
Say if the original poster did
struct a { int type; long double take; };


struct b { int type; int handwrite; };

struct c { int type; char toast; };
typedef union { struct a a; struct b b; struct c c; } NODE;
malloc (sizeof (struct c));
and converted the pointer to NODE* and then to struct a*, then tried to
dereference as in a->type, then there could be a problem. Maybe.

Intuitively I think there should be a problem, but actually the wording of
the standard contradicts my intuition (as posted recently on a different
problem), and I would like to see a defect report on that.

Mark Brader

unread,
Apr 2, 1993, 3:27:26 AM4/2/93
to
> > There is one potential problem. Section 4.10.3/7.10.3 restricts the
> > alignment of pointers returned by malloc as follows:
> > # The pointer returned ... is suitably aligned so that it may be
> > # assigned to a pointer to any type of object and then used to
> > # access such an object or an array of such objects IN THE SPACE
> > # ALLOCATED ...
> > My emphasis added. It has been argued that this means that a call
> > to malloc(N) does not require the result to be aligned more strictly
> > than on multiples of N bytes, even if some types larger than N bytes
> > require stricter alignment.
> > ... Suppose that this interpretation is correct, and that we have

> > struct a { int type; char toast; };
> > struct b { int type; int handwrite; };
> > struct c { int type; long double take; };
> typedef union { struct a a; struct b b; struct c c; } NODE;
> > Now when you do
> > malloc (sizeof (struct a));
> > you may get a pointer that cannot be legitimately converted to a
> > NODE *, because the alignment is wrong.
>
> I think that is not possible, because it has previously been proven that
> all struct pointers (and union pointers, I believe) must have identical
> representations.

Just because "struct a *" and "struct c *" must have identical repre-
sentations, it doesn't mean that "struct a" and "struct c" must have
identical alignment requirements. However, it now occurs to me that a
proof similar to the one that requires them to have identical repre-
sentations *does* lead to the alignment requirements being identical:
namely, that code such as

void func()
{
extern void *vp;
extern struct a *ap;
ap = vp;
}

must, as I understand it, be compilable with no definition of "struct a"
in scope. And *that* implies that all struct types require the same
alignment, and answers my objection to the original code.

Good.
--
Mark Brader "It is impractical for the standard to attempt to
SoftQuad Inc., Toronto constrain the behavior of code that does not obey
utzoo!sq!msb, m...@sq.com the constraints of the standard." -- Doug Gwyn

John F Carr

unread,
Apr 2, 1993, 4:27:28 AM4/2/93
to
In article <1993Apr2.0...@sq.sq.com> m...@sq.sq.com (Mark Brader) writes:

>namely, that code such as [example using pointer to undeclared struct deleted]


>must, as I understand it, be compilable with no definition of "struct a"
>in scope. And *that* implies that all struct types require the same
>alignment, and answers my objection to the original code.

What if your C implementation just runs lint and preprocesses the file at
compile time, and does code generation and linking later?

I don't know of a compiler that does this. The Plan 9 C compiler does some
optimization during linking, but as far as I know this optimization doesn't
have any surprising side effects.

--
John Carr (j...@athena.mit.edu)

Paul Zimmerman

unread,
Apr 2, 1993, 3:18:41 PM4/2/93
to
In article <1993Apr2.0...@sq.sq.com>, m...@sq.sq.com (Mark Brader) writes:
|>
|> void func()
|> {
|> extern void *vp;
|> extern struct a *ap;
|> ap = vp;
|> }
|>
|> must, as I understand it, be compilable with no definition of "struct a"
|> in scope. And *that* implies that all struct types require the same
|> alignment, and answers my objection to the original code.

Not so. A void pointer *may* contain a pointer to any type, but when the assignment of
vp to ap is made, it *must* contain a pointer to type struct a. When the (unseen here)
assignment to vp is made, the definition of struct a will be in scope, and so vp will
have the required alignment.

--
Paul Zimmerman | "I toast, therefore I am."
pa...@bertha.convergent.com | - AI toaster from _Red Dwarf_

Norman Diamond

unread,
Apr 4, 1993, 9:44:18 PM4/4/93
to
In article <13...@risky.Convergent.COM> pa...@bertha.convergent.com writes:
>In article <1993Apr2.0...@sq.sq.com>, m...@sq.sq.com (Mark Brader) writes:
>> void func()
>> {
>> extern void *vp;
>> extern struct a *ap;
>> ap = vp;
>> }
>> must, as I understand it, be compilable with no definition of "struct a"
>> in scope. And *that* implies that all struct types require the same
>> alignment, and answers my objection to the original code.

>Not so. A void pointer *may* contain a pointer to any type, but when the
>assignment of vp to ap is made, it *must* contain a pointer to type struct a.
>When the (unseen here) assignment to vp is made, the definition of struct a
>will be in scope, and so vp will have the required alignment.

The value in vp must have the required alignment (though the definition of
struct a didn't have to be in scope at that particular time, but no matter).
However, when the C implementation is translating func(), it doesn't know
what that alignment is. The C implementation must still generate a coversion
of the value in vp to a valid representation in ap. So all incomplete struct
types must have identical representations.

This has been assumed to mean that all struct types must have identical
representations. However, one more step is necessary, as was observed in
the controversy over a similar case, where struct a was an incomplete
struct type inside a function prototype. When an incomplete struct type is
never completed in one translation unit, is it compatible with a complete
struct type in another translation unit, or not?

Reply all
Reply to author
Forward
0 new messages