🚀 go-pugleaf

seebs@solutions.solon.com (Peter Seebach) wrote:

>I recently wrote a "generic" linked list sorter.  It assumes that
>struct foo {
>	struct foo *next;
>};

>is "compatible" with any structure beginning with a pointer
>to itself.  I *believe* this is legal; there can be no initial padding, and I
>seem to recall that pointer to struct is compatible with pointer to struct.

>I am now doing a doubly-linked list sorter.  I am going to assume that, if
>the user hands me a list looking like:

>struct foo {
>	struct { struct foo *next, *prev; };
>	...
>};

>that it's compatible with my
>struct bar {
>	struct { struct bar *next, *prev; };
>};
>... I can go to "struct bar *next; struct bar *prev;" if needbe.

>Here's where it gets ugly:

>Can I assert that treating a struct bar as a struct foo will
>work?  In other wordss, can I *legally* (Screw real-world compilers; I'm
>writing for ANSI, not for a specific project) assert that a pointer to a
>struct is good for referencing a first member of that struct *or*
>for referencing the first member of a struct which is the first
>member of that struct?

I don't think you can guarantee that the pointers will be compatible
unless they point at compatible types:

($6.1.2.5) A pointer to void shall have the same representation and
alignment requirements as a pointer to a character type.  Similarly,
pointers to qualified or unqualified versions of compatible types shall
have the same representation and alignment requirements.  Pointers to
other types need not have the same representation or alignment
requirements.

As I read things, that means not only can't you depend on being able to
access a common prefix inside different structures, but in fact, you
can't even portably assign the address of one sort of structure to a
pointer to some other structure unless the structures are compatible,
which requires that they contain the same number of members, and that
all the members be of compatible types arranges in the same order.

>And if anyone can point me at a better way to say this in English,
>I'd appreciate it.

"If a number of structures all contain a common prefix, is a pointer to
a structure containing that prefix guaranteed compatible with pointers
to other structures containing the same prefix?"

>(My plan is to simply use my sorting engine, which is mergesort based, to sort
>the doubly-linked list as if it were a singly-linked list, then iterate
>through correcting the prev pointers.)

>-s
>-- 
>Peter Seebach - seebs@solon.com || seebs@intran.xerox.com --
>C/Unix proto-wizard -- C/Unix questions? Send mail for help.  No, really!
>Copyright 1995 Peter Seebach.  --  High energy particle theology
>The *other* C FAQ - ftp taniemarie.solon.com /pub/c/afq

    Later,
    Jerry.

/* I can barely express my own opinions; I certainly can't
 * express anybody else's.
 *
 * The universe is a figment of its own imagination.
 */