19. Intrusive containers: the Linux kernel's container_of trick

Every data structure so far contains its payload (Node.value). Intrusive containers flip this: the payload struct embeds the list node, and the container macro computes back from the embedded node's address to the containing struct's address. This is how the Linux kernel implements one generic doubly-linked-list type (struct list_head) reused for thousands of unrelated structs, with zero void* casts and zero per-type boilerplate.

#include <stdio.h>
#include <stddef.h>   // offsetof

// The kernel's actual technique, simplified:
#define container_of(ptr, type, member) \
    ((type *)((char *)(ptr) - offsetof(type, member)))

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

static void list_init(list_head *h) { h->next = h->prev = h; }

static void list_add(list_head *new_node, list_head *head) {
    new_node->next = head->next;
    new_node->prev = head;
    head->next->prev = new_node;
    head->next = new_node;
}

// A real payload struct that EMBEDS the generic node:
typedef struct {
    int         pid;
    char        name[32];
    list_head   node;      // <-- the intrusive part
} Task;

int main(void) {
    list_head tasks;
    list_init(&tasks);

    Task t1 = { .pid = 101, .name = "init" };
    Task t2 = { .pid = 205, .name = "sshd" };
    list_add(&t1.node, &tasks);
    list_add(&t2.node, &tasks);

    for (list_head *p = tasks.next; p != &tasks; p = p->next) {
        Task *t = container_of(p, Task, node);   // walk the generic list, recover the real struct
        printf("pid=%d name=%s\n", t->pid, t->name);
    }
    return 0;
}

container_of works because offsetof(Task, node) is a compile-time constant — the byte distance from the start of Task to its node field — so subtracting that many bytes from node's address always recovers the enclosing Task*, regardless of what type embeds node. This is literally include/linux/list.h in the Linux kernel source, used for the process list, the list of open files, wait queues, and hundreds of other kernel structures — one list implementation, zero per-type code duplication, and (unlike the void*-based generic containers in Section 16) no extra allocation or indirection: the node lives inside the struct that needs it.