I'm trying to implement a linked list like this:
typedef struct SLnode
{
void* item;
void* next;
} SLnode;
typedef struct DLnode
{
void* item;
void* next;
struct DLnode* prev;
} DLnode;
typedef struct LinkedList
{
void* head; /*SLnode if doubly_linked is false, otherwise DLnode*/
void* tail; /* here too */
bool doubly_linked;
} LinkedList;
And I want to access it like this:
void* llnode_at(const LinkedList* ll, size_t index)
{
size_t i;
SLnode* current;
current = ll->head;
for(i = 0; i < index; i++)
{
current = current->next;
}
return current;
}
So my question is:
- Am I allowed to cast between these structs as long as I only access the common members? I read differing opinions on this.
- Could I also make the next-pointer of the respective types? Or would it be UB then to use it in my example function in case it really is DLnode?
In case this doesn't work, are there any other ways of doing something like this? I read that unions might work, but this code should also run in C89, and afaik reading a different union member than last written to is UB there.
So you are trying to build subclasses in C. A possible way is to make the base struct to be the first element of the child struct, because in that case C standard explicitely allows casting back and forth between those 2 types:
6.7.2.1 Structure and union specifiers
§ 13 ... A pointer to a
structure object, suitably converted, points to its initial member (or if that member is a
bit-field, then to the unit in which it resides), and vice versa...
The downside is that you need a cast to the base class to access its members:
Example code:
typedef struct SLnode
{
void* item;
void* next;
} SLnode;
typedef struct DLnode
{
struct SLnode base;
struct DLnode* prev;
} DLnode;
You can then use it that way:
DLnode *node = malloc(sizeof(DLnode));
((SLnode*) node)->next = NULL; // or node->base.next = NULL
((SLnode *)node)->item = val;
node->prev = NULL;
You can do this safely provided you use a union to contain the two structures:
union Lnode {
struct SLnode slnode;
struct DLnode dlnode;
};
Section 6.5.2.3 of the current C standard, as well as section 6.3.2.3 of the C89 standard, states the following:
6 One special guarantee is made in order to simplify the use of unions: if a union contains several structures that share a common
initial sequence (see below), and if the union object currently
contains one of these structures, it is permitted to inspect the
common initial part of any of them anywhere that a declaration of the
completed type of the union is visible. Two structures share a common
initial sequence if corresponding members have compatible types (and,
for bit-fields, the same widths) for a sequence of one or more initial
members.
Because the first two members of both structures are of the same type, you can freely access those members using either union member.
What you describe should be allowed under the C Standard. The confusion of the Common Initial Sequence rule stems from a bigger problem: the Standard fails to specify when the use of a pointer or lvalue which is visibly derived from another is considered to have be a use of the original. If the answer is "never", then any struct or union member of a non-character type would be pretty much useless, since the member would be an lvalue whose type isn't valid for accessing the struct or union. Such a view would clearly be absurd. If the answer is "only when it is formed by directly applying "." or "->" on the struct or union type, or a pointer to such a type, that would make the ability to use "&" on struct and union members rather useless. I'd regard that view as only slightly less absurd.
I think it's clear that in order to be useful the C language must be viewed as allowing derived lvalues to be used in at least some circumstances. Whether your code, or most code relying upon the Common Initial Sequence rule, is usable depends upon what those circumstances are.
The language would be rather silly if code couldn't reliably use derived lvalues to access structure members. Unfortunately, even though this problem was apparent in 1992 (it forms the underlying basis of Defect Report #028, published in that year) the Committee didn't address the fundamental issue but instead reached a correct conclusion based upon totally nonsensical logic, and has since gone and added needless complexity in the form of "Effective Types" without ever bothering to actually define the behavior of someStruct.member.
Consequently, there is no way to write any code which does much of anything with structs or unions without relying upon more behaviors than would actually be guaranteed by a literal reading of the Standard, whether such accesses are done by coercing void* or pointers to proper member types.
If one reads the intention of 6.5p7 as being to somehow allow actions which use an lvalue which is derived from one of a particular type to access objects of that type, at least in cases that don't involve actual aliasing (note a huge stretch, given footnote #88 "The intent of this list is to specify those circumstances in which an object may or may not be aliased."), and recognizes that aliasing requires that a region of storage be accessed using a reference X at a time when there exists another reference from which X was not visibly derived that will in future be used to access the storage in conflicting fashion, then compilers that honor that intention should be able to handle code like yours without difficulty.
Unfortunately, both gcc and clang seem to interpret p6.5p7 as saying that an lvalue which is derived from one of another type should often be presumed incapable of actually identifying objects of that former type even in cases where the derivation is fully visible.
Given something like:
struct s1 {int x;};
struct s2 {int x;};
union u {struct s1 v1; struct s2 v2;};
int test(union u arr[], int i1, int i2)
{
struct s1 *p1 = &arr[i1].v1;
if (p1->x)
{
struct s2 *p2 = &arr[i2].v2;
p2->x=23;
}
struct s1 *p3 = &arr[i1].v1;
return p3->x;
}
At the time p1->x is accessed, p1 is clearly derived from an lvalue of union type, and should thus be capable of accessing such an object, and the only other existing references that will ever be used to access the storage are references to that union type. Likewise when p2->x and p3->x are accessed. Unfortunately, both gcc and clang interpret N1570 6.5p7 as an indication that they should ignore the relationships between the union and the pointers to its members. If gcc and clang can't be relied upon to usefully allow code like the above to access the Common Initial Sequence of identical structures, I wouldn't trust them to reliably handle structures like yours either.
Unless or until the Standard is corrected to say under what cases a derived lvalue may be used to access a member of a struct or union, it's unclear that any code that does anything remotely unusual with structures or unions should be particularly expected to work under the -fstrict-aliasing dialects of gcc and clang. On the other hand, if one recognizes the concept of lvalue derivation as working both ways, a compiler might be justified in assuming that a pointer which is of one structure type won't be used in ways that would alias a reference to another, even if the pointer is cast to the second type before use. I'd therefore suggest that using void* would be less likely to run into trouble if the Standard ever fixes the rules.
