Is this legal

[Nick]

I've been wrestling with my conscience over this one for several years
now. This is a cut down example of some code I've written to iterate
over any linked list as long as it satisfies a particular constraint.
But is it actually legal? - I can't make my mind up.

Here's roughly what it looks like. I could post the full code (it's
actually a mergesort rather than an iterator) if this has silly errors
in or doesn't explain it properly. But here goes:

I have a header file (list_header.h)
that just contains:

typedef void list_function(void *l);
void list_iterator(void *lst);

and a list code file like this:

#include "list_header.h"

struct generic_list {
struct generic_list *next;
};

void list_iterator(void *lst, list_function *lf) {
struct generic_list *p = lst;
while(*p) {
lf(p);
p = p->next;
}
}

Then, whenever you want to iterate over a list you do:
#include "list_header.h"

struct thislist {
struct thislist *next;
... lots of other fields ...
} *reallist;

void list_callback(void *l) {
struct thislist *lp = l;
... do things with all the other fields in lp ...
}

and then, deep in the bowels of the code, after reallist has been made
to point to a list of items
list_iterator(reallist,list_callback);

Now clearly if you ever use this with structures where the first item is
not a pointer to a list item you are heading for every type of error and
undefined behaviour.

But if not, is this legal? The dodgy bit is casting a pointer to one
type of list, via void, to another type of list and then dereferencing a
field within it and expecting it to point to another list of the second
type when it originally pointed to one of the first.

On the other hand, all the stuff I can read about the equivalence of
pointer suggests it just might be (it's clearly right on the border).
It works, has worked on various compilers and OSs, but I know that
proves absolutely nothing!

Thoughts?

 

[nicolas.sitbon]

I've been wrestling with my conscience over this one for several years
now.  This is a cut down example of some code I've written to iterate
over any linked list as long as it satisfies a particular constraint.
But is it actually legal? - I can't make my mind up.

Here's roughly what it looks like.  I could post the full code (it's
actually a mergesort rather than an iterator) if this has silly errors
in or doesn't explain it properly.  But here goes:

I have a header file (list_header.h)
that just contains:

typedef void list_function(void *l);
void list_iterator(void *lst);

and a list code file like this:

#include "list_header.h"

struct generic_list {
  struct generic_list *next;

};

void list_iterator(void *lst, list_function *lf) {
  struct generic_list *p = lst;
  while(*p) {
    lf(p);
    p = p->next;
  }

}

Then, whenever you want to iterate over a list you do:
#include "list_header.h"

struct thislist {
  struct thislist *next;
  ... lots of other fields ...

} *reallist;

void list_callback(void *l) {
     struct thislist *lp = l;
     ... do things with all the other fields in lp ...

}

and then, deep in the bowels of the code, after reallist has been made
to point to a list of items
list_iterator(reallist,list_callback);

Now clearly if you ever use this with structures where the first item is
not a pointer to a list item you are heading for every type of error and
undefined behaviour.

But if not, is this legal?  The dodgy bit is casting a pointer to one
type of list, via void, to another type of list and then dereferencing a
field within it and expecting it to point to another list of the second
type when it originally pointed to one of the first.

On the other hand, all the stuff I can read about the equivalence of
pointer suggests it just might be (it's clearly right on the border).
It works, has worked on various compilers and OSs, but I know that
proves absolutely nothing!

Thoughts?

you probably want to write:
void list_iterator(void *lst, list_function *lf) {
struct generic_list *p = lst;
while(p) { /* <========== */
lf(p);
p = p->next;
}

}

 

[Seebs]

I've been wrestling with my conscience over this one for several years
now. This is a cut down example of some code I've written to iterate
over any linked list as long as it satisfies a particular constraint.
But is it actually legal? - I can't make my mind up.

I'm not sure about "legal", I prefer "conforming" -- legal is itself a
term of art referring to the legal system.

typedef void list_function(void *l);
void list_iterator(void *lst);

and a list code file like this:

#include "list_header.h"

struct generic_list {
struct generic_list *next;
};

void list_iterator(void *lst, list_function *lf) {

Presumably the prototype matches, though.

But if not, is this legal? The dodgy bit is casting a pointer to one
type of list, via void, to another type of list and then dereferencing a
field within it and expecting it to point to another list of the second
type when it originally pointed to one of the first.

So far as I can tell, this should be covered by "all struct pointers smell
the same". All struct pointers have the same traits, and that means that
a "struct foo *next;" as a first member is a common initial sequence, so
the conversion from one to the other should preserve that common initial
sequence.

That said, someone (I've forgotten who already) recently pointed out a
more elegant solution, using a "struct list" which is embedded in a
structure anywhere you want. You iterate over the list, and when you
have the list member you want, you then grab the pointer to the containing
structure, because you know the offset of the "struct list" within that
structure. (Note that the member of the structure is a struct list, NOT
a struct list *.)

-s

 

[Nick]

So far as I can tell, this should be covered by "all struct pointers smell
the same". All struct pointers have the same traits, and that means that
a "struct foo *next;" as a first member is a common initial sequence, so
the conversion from one to the other should preserve that common initial
sequence.

That's what I thought, but it's nice to have my opinion confirmed by a
respected authority (well, respected by a long-term lurker like me,
anyway).

That said, someone (I've forgotten who already) recently pointed out a
more elegant solution, using a "struct list" which is embedded in a
structure anywhere you want. You iterate over the list, and when you
have the list member you want, you then grab the pointer to the containing
structure, because you know the offset of the "struct list" within that
structure. (Note that the member of the structure is a struct list, NOT
a struct list *.)

That sounds interesting. There's the obvious generic list container (a
struct with a next and a void pointer in it) but we're clearly not
talking about that.

At first I thought you wouldn't know where to find it, but of course the
callback function knows what structure it's expecting, so can use
offsetof to do it.

Checking up on offsetof (I don't believe I've ever used it) I see that
the Wikipedia article on it is an example of just this technique. It
involves a particularly horrible cast to avoid the compiler subtracting
an offsetof number of sizeof(structures) rather than bytes though.

That's really rather neat indeed. I don't think I'll be rewriting my
code, but I'll keep it in mind in case I ever have to do it again - it's
clearly safer than having to put the "next" field in the right place.

 

[Phil Carmody]

That's what I thought, but it's nice to have my opinion confirmed by a
respected authority (well, respected by a long-term lurker like me,
anyway).

Alas the respected gentleman is mistaken. Confusing sprouts with onions?

Phil

 

[Barry Schwarz]

I've been wrestling with my conscience over this one for several years
now. This is a cut down example of some code I've written to iterate
over any linked list as long as it satisfies a particular constraint.
But is it actually legal? - I can't make my mind up.

Here's roughly what it looks like. I could post the full code (it's
actually a mergesort rather than an iterator) if this has silly errors
in or doesn't explain it properly. But here goes:

I have a header file (list_header.h)
that just contains:

typedef void list_function(void *l);
void list_iterator(void *lst);

and a list code file like this:

#include "list_header.h"

struct generic_list {
struct generic_list *next;
};

void list_iterator(void *lst, list_function *lf) {
struct generic_list *p = lst;
while(*p) {
lf(p);
p = p->next;
}
}

Then, whenever you want to iterate over a list you do:
#include "list_header.h"

struct thislist {
struct thislist *next;
... lots of other fields ...
} *reallist;

void list_callback(void *l) {
struct thislist *lp = l;
... do things with all the other fields in lp ...
}

and then, deep in the bowels of the code, after reallist has been made
to point to a list of items

If you mean that reallist has been assigned a value that is the
address of a struct thislist, then all the implicit conversions
between pointers to void and pointers to struct appear valid. Though
not impossible, it would be an extremely perverse implementation that
decided a struct generic_list required a more restrictive alignment
than a struct thislist. If that were to be the case, the
initialization in list_iterator could invoke undefined behavior,
depending on the value of reallist.

Similarly, if you ever set reallist to point to a struct thatlist
which had less restrictive alignment than struct thislist, the
initialization in list_callback could invoke undefined behavior.

list_iterator(reallist,list_callback);

Now clearly if you ever use this with structures where the first item is
not a pointer to a list item you are heading for every type of error and
undefined behaviour.

But if not, is this legal? The dodgy bit is casting a pointer to one
type of list, via void, to another type of list and then dereferencing a
field within it and expecting it to point to another list of the second
type when it originally pointed to one of the first.

But that does not appear to be the case you describe. While the
various pointers (both the parameter pointers to void and the local
pointers to struct) have different types, at all times the value is
the address of the "list of items" you mention.