Implement a Linux-style intrusive doubly linked list (list_head).
#include <stddef.h>
struct list_head { struct list_head *next, *prev; };
#define LIST_HEAD_INIT(name) { &(name), &(name) }
static inline void INIT_LIST_HEAD(struct list_head *h) { h->next = h; h->prev = h; }
static inline void __list_add(struct list_head *n, struct list_head *prev, struct list_head *next)
{
next->prev = n; n->next = next; n->prev = prev; prev->next = n;
}
static inline void list_add(struct list_head *n, struct list_head *head) { __list_add(n, head, head->next); } /* at front */
static inline void list_add_tail(struct list_head *n, struct list_head *head) { __list_add(n, head->prev, head); } /* at back */
static inline void list_del(struct list_head *e)
{
e->next->prev = e->prev;
e->prev->next = e->next;
e->next = e->prev = NULL; /* the kernel poisons these instead */
}
static inline int list_empty(const struct list_head *h) { return h->next == h; }
#define container_of(ptr, type, member) ((type *)((char *)(ptr) - offsetof(type, member)))
#define list_entry(ptr, type, member) container_of(ptr, type, member)
#define list_for_each(pos, head) for (pos = (head)->next; pos != (head); pos = pos->next)
#define list_for_each_safe(pos, n, head) \
for (pos = (head)->next, n = pos->next; pos != (head); pos = n, n = pos->next)
/* usage */
struct task { int id; struct list_head node; };
/* struct list_head ready = LIST_HEAD_INIT(ready);
list_add_tail(&t->node, &ready);
struct list_head *p; list_for_each(p, &ready) { struct task *t = list_entry(p, struct task, node); } */
Points: the list node is embedded inside the object, so no separate allocation per list entry, one object can be on several lists (several list_head members), and the same list code works for every type. The head is a sentinel in a circular list, so there are no NULL checks. container_of recovers the object. Use the _safe iterator when deleting while iterating.