Intrusive Linked List (C)
Topics: intrusive data structures, doubly-linked list, container_of
Problem
Implement an intrusive doubly-linked list — the Linux-kernel list_head pattern. The link node
is embedded inside the element struct, so the list itself allocates nothing and one element can
sit on several lists. head is a circular sentinel: an empty list points to itself.
typedef struct list_node { struct list_node *prev, *next; } list_node;
#define container_of(ptr, type, member) ... // recover the element from its node (provided)
void list_init(list_node *head);
void list_push_back(list_node *head, list_node *n);
void list_push_front(list_node *head, list_node *n);
void list_remove(list_node *n); // unlink; leave n safe to re-insert
bool list_empty(const list_node *head);
size_t list_len(const list_node *head);
Iterate with for (p = head->next; p != head; p = p->next) and recover each element via
container_of(p, MyType, link).
Key concepts
- Circular sentinel:
head->next == head means empty; every real node has valid prev/next,
so insert/remove are branchless four-pointer splices (no NULL special-casing).
container_of: ((char*)ptr - offsetof(type, member)) walks back from the embedded node to
the struct — how intrusive containers avoid storing a separate payload pointer.- Self-link on remove: point a removed node at itself so a later re-insert is safe.
Run
cc -std=c11 -O2 -Wall tests.c -o /tmp/list && /tmp/list
Sign in to submit your solution.