After (not) thinking about it for a couple days, I think I've actually worked it out. Skip to the end if you want to see what I came up with that's generic, typesafe, and seems to follow strict-alias rules. Or stick with the whole post to see how I came to it.
The above examples are slightly contrived, but when I look at real uses in my code, it's easy to not mix things up. This is the real list structure I'm using in my code:
typedef struct zlistnode_s
{
struct zlistnode_s* next;
struct zlistnode_s* prev;
} zlistnode_t;
typedef struct
{ zlistnode_t* head;
zlistnode_t* tail;
} zlist_t;
zerr zlist_addtail( zlist_t* list, zlistnode_t* node);
...
When I use a zlist_t, it's usually a list of a single type. Something like this:
typedef struct {
zlistnode_t zlistnode;
zchar* name;
zbool important_boolean;
zuint32 crazy_int;
} supernode_t;
I had list access macros like this:
#define zlist_head(ZLIST) ((ZLIST)->head)
#define zlist_next(ZLISTNODE) ( ((zlistnode_t*)(ZLISTNODE)) -> next )
so iterating a list looked like:
supernode_t* n = zlist_head(&my_supernode_list); // of course a warning converting from zlistnode_t* to supernode_t*
while(n)
{
//do stuff with n
n = zlist_next(n); //of course another warning here too
}
I originally put(void*) casts in the zlist_* macros to make the warnings go away. When adding an item to the list:
zlist_addtail( &mylist, (zlistnode_t*) mynode); // casting a supernode_t* to a zlistnode_t*
So instead I do this:
zlist_addtail( &mylist, &mynode->zlistnode); //take the first element of supernode_t* (it's still a zlistnode_t*, but 'safer')
Also I changes zlist_next to:
#define zlist_next(ZLISTNODE) ((ZLISTNODE)->zlistnode.next)
This macro is very safe, in that, the list item (say, a supernode_t) just needs to make sure the zlistnode_t is named
zlistnode'. And if I accidently use the macro on a non-zlistnode-ified struct, I'll get a compile error instead of run-time crash.
So what I've done is completely embedded the zlistnode's inside the structs, and the zlistnodes link to themselves to make the linked list. The zlist functions now only deal with true, bona-fide zlistnode_t pointers, with no casting or trickery. There's only 1 thing left unclean: When I store a supernode_t* in the list, I'm not really storing a supernode_t, I'm storing the zlistnode_t that's 'inside' the supernode. When I call zlist_next, I'm really getting supernode->zlistnode.next, which is a zlistnode_t*. I can cast it to a supernode_t*, and since it's the first element, it's guaranteed to be the 'same' pointer, but it still smells of aliasing.
Here, I think is the solution:
t
ypedef struct zlistnode_s
{
void* next;
void* prev;
} zlistnode_t;
typedef struct
{ void* head;
void* tail;
} zlist_t;
zerr zlist_addtail( zlist_t* list, zlistnode_t* node);
#define zlist_head(ZLIST) ((ZLIST)->head)
#define zlist_next(ZLISTNODE) ((ZLISTNODE)->zlistnode.next)
This almost 'does it all'
Typesafety:
- The zlist_addtail function only accepts zlist_t* and zlistnode_t*
- zlist_head macro only compiles on things that have a 'head'
- zlist_next macro only functions on things that a zlistnode 'inside'
But there's a nice key difference: When I store the 'next' or 'head' or 'prev' pointers in the list, they are note other listnodes, they are 'void*'. Because any struct you allocate can be cast freely back and forth to void or their actual type, this is what's happening:
supernode_t* n = mk_supernode(); //n is really a supernode_t
zlist_addtail( &mylist, &n->zlistnode ); //stores 'n' aka 'n->zlistnode' in the list as a 'void*' (totally allowed)
later:
n = zlist_next(n);
which, if you do the macro substitution is:
n = n->zlistnode.next; // You are not type-punning a zlistnode_t* into a supernode_t*. You are just turning the zlistnode_t* back into itself from a void*. (totally allowed)
If you want to get really pendantic, you can argue that I'm cheating by passing a zlistnode_t* into addhead/addtail, and I'm indirectly going from supernode_t* to zlistnode_t* to void* and then to supernode_t*, so I'm not playing completely by the rules. But to that I say, a void* that points to a struct and a void* that points to the first member of a struct are the same void*. And if I only access super_node_t specific elements from supernode_t*'s and only access listnode_t* elements (next/prev), there's no way the data of these overlapped structs can alias each other.
Unless I'm wrong is some way?
