Background

I have created a basic linked list data structure mainly for learning purposes. One goal of the list was that it can handle different data structures. Therefore, I've tried my hand at structure composition to simulate "inheritance" in C. Here are the structures that form the basis for my linked list.

typedef struct Link {
    struct Link* next;
    struct Link* prev;
} Link;

typedef Link List;

In my implementation I have chosen to have a sentinel node that serves as both the head and the tail of the list (which is why Link == List).

To make the list actually handle data, a structure simply includes the Link structure as the first member:

typedef struct {
    Link link;
    float data;
} Node;

So the linked list looks like this.

         ┌───┬───┬───┐     ┌───┬───┐     ┌───┬───┬───┐     
... <--->│ P │ N │ D │<--->│ P │ N │<--->│ P │ N │ D │<---> ... 
         └───┴───┴───┘     └───┴───┘     └───┴───┴───┘
         End Node          myList        First Node

List myList;
Node node1 = {{}, 1.024};
....
Node nodeN = {{}, 3.14};

list_init(&myList) // myList.next = &myList; myList.prev = &myList;
list_append(&myList, &node1);
....
list_append(&myList, &nodeN);

Question

To traverse this list a Node pointer initially points to the First Node. It then traverses along the list until it points to the sentinel again then stops.

void traverse()
{
    Node* ptr;
    for(ptr = myList.next; ptr != &myList; ptr = ptr->link.next)
    {
        printf("%f ", ptr->data);
    }
}

My question is with the line ptr != &myList. Is there a pointer alignment problem with this line?

The for loop correctly produces the warnings: (warning: assignment from incompatible pointer type and warning: comparison of distinct pointer types lacks a cast) which can be silenced by doing what it says and casting to Node*. However, is this a DumbThingToDo™? I am never accessing ptr->data when it points to &myList as the loop terminates once ptr == &myList.

TLDR

In C structs, a Base* can point to a Derived if Base is the first member in Derived. Can a Derived* point to a Base if none of Derived specific members are accessed?

EDIT: replaced relevant function calls with their equivalent inline code.

Solution 1:

Kudos for your presentation.

I think your implementation should work fine, because C guarantees that the address of a struct is the address of its initial member. Put aside the statements C makes about alignment of struct-members, this guarantee should mean that, as long as your implementation always puts Link as first member, this should not cause alignment issues.

from here: C99 §6.7.2.1:

13 Within a structure object, the non-bit-field members and the units in which bit-fields reside have addresses that increase in the order in which they are declared. 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. There may be unnamed padding within a structure object, but not at its beginning

This should be what you meant to say about Base * and Derived *, although no such thing exists in pure C. They are just structs which happen to have the same memory layout.

However I think it is a bit brittle to implement it like this, because Node and Link directly depend on each other. If you were to change the structure of Node, your code would become invalid. At the moment I don't see the point in having an extra struct Link, apart from you being able to just write a new Node for a new type reusing Link.

There is actually a linked list implementation that immediately came to mind when I saw your post and works in a way very similar to the way you intend to use your list: the kernel list

It uses the same List-element (list_head):

struct list_head {
    struct list_head *next, *prev;
};

It contains this function macro:

#define list_for_each_entry(pos, head, member)                          \
      for (pos = list_first_entry(head, typeof(*pos), member);        \
           &pos->member != (head);                                    \
           pos = list_next_entry(pos, member))

If you look at the way the macro is implemented, you will see that it offers iteration over the entries of a list without knowing anything about the layout of the entries the list is contained in. Assuming I interpret your intention right, I think this is the way you would want it to be.

Solution 2:

In C structs, a Base* can point to a Derived if Base is the first member in Derived. Can a Derived* point to a Base if none of Derived specific members are accessed?

If you mean "can a Derived* point to an arbitrary Base (including one which is not a first member of a Derived object)", then: Technically, no. My understanding of Defect Report #74 is the alignment requirements can be different.

Q: If a structure has a field of type t, can the alignment requirements of the field be different from the alignment requirements of objects of the same type that are not members of structures? If the answer to (a) is ``yes,'' then where applicable the remaining questions should be assumed to have been asked for both objects within structures and objects outside structures.

A: Subclause 6.1.2.5 says, '... pointers to qualified or unqualified versions of compatible types shall have the same representation and alignment requirements.' Subclause 6.5.2.1 says, `Each non-bit-field member of a structure or union object is aligned in an implementation-defined manner appropriate to its type.' And later, 'There may therefore be unnamed padding within a structure object, ... as necessary to achieve the appropriate alignment.' a) It is possible for an implementation to state generalized requirements to satisfy sublause 6.1.2.5. These requirements may be further strengthened using the implementation-defined behavior made available in subclause 6.5.2.1. Yes, the alignment requirements can be different.

Solution 3:

I wrote this in the comments to ouah's answer, but I'll present it as an answer in its own right.

It is true as ouah writes that the code in your question could have an alignment problem in theory if you go by the C standard. However, I don't think there's a single architecture that your code is likely (or unlikely) to run on whose ABI exhibits such alignment patterns. At least none that I know of, for sure, and that includes experience with a few different desktop and embedded architectures. I can also not really imagine an architecture that would gain anything from such alignment properties.

It is also worth noting that this pattern is indeed used in practice quite commonly; it's kind of like the fact that you can always fit ints in pointers, in that it's not guaranteed by any cross-platform standard, but there's virtually no platform on which it's not true, and people do it all the time.