Using offsetof to implement linked lists

offsetof is a cute litte feature in C. What the function gives is the offset that a member has in a struct. Assume we have the given struct:

typedef struct {
   int a;
   char c;
   int b;
} s;

Offsetof would return something like this on fairly normal hardware:

offsetof(s, a); /*0 */
offsetof(s, c); /*4 */
offsetof(s, b); /*8 - no, not 5, more about that later... */

So what can this be used for? Well, a quite common use is for linked lists. A doublylinked list will often be written with two structures:

typedef struct link_t {
    struct link *next_link;
    struct link *prev_link;
} link;

typedef struct list_t {
    struct link *first_link;
    struct link *last_link;
}

Then, any structure that wants to be in a link list adds the link structure as a member:

typedef struct interesting_data {
    link_t link;
    int data;
} interesting_data;

To insert into a linked list, we then use a macro.

#define LIST_INSERT_BACK(list, link, member)\
do {\
    char *p = (char*)link;\
    link_t *l = (link_t*)((char*)link) + offsetof(typeof(link), member));\
    private_insert_back_link(list, l);\
}\ while(0)

#define LIST_GET_BACK(list, link_type, member)\
\ (link_type*) private_get_back_link(list, offsetof(link_type, member));

There are of course quite a few macros needed (to traverse the list, etc.), but they are all based on using offsetof to find the offset of the list member.

Sizeof

So, this is the first of hopefully many mini-guides on how to do cool stuff in C...

You might usually use sizeof like this:

int *a = malloc(sizeof(int));

But a for many little known fact about C is that sizeof will get the size of the resulting type the of the expression given as the argument. This means that this line will do the same thing as the previous line:

int *a = malloc(sizeof(*a));

Since the expression *a will result in an int, the size of that expression is an int.

I went too long as a C-programmer without knowing this little fact.