</>EmbeddedInterview

Implement a Linux-style intrusive doubly linked list (list_head).

Hard"Coding: Linked Lists, Stacks & Queues"
#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.