A circular doubly linked list (cdlist in brief) is a doubly linked list where the last node connects the first node. An intrusive cdlist doesn’t invoke heap allocation (aka malloc) in the library code. The Linux kernel famously implements an intrusive cdlist. That implementation is quite long, which hides the rationale behind the code and might be hard to understand even with well-written explanations (e.g. this).
This article gives a much simpler implementation of a basic intrusive cdlist with only push() and pop() operations. The library code only consists of <30 coding lines (named “cdlist.h”):
#pragma once // or use the #ifndef guard
#include <stddef.h> // for offsetof()
typedef struct cl_head_s {
struct cl_head_s *prev, *next;
} cl_head_t;
static inline void cl_push(cl_head_t **h, cl_head_t *p, int push_back) {
if (*h) p->prev = *h, p->next = (*h)->next, (*h)->next = p, p->next->prev = p;
else *h = p, p->prev = p->next = p;
if (push_back) *h = p;
}
static inline cl_head_t *cl_pop(cl_head_t **h, int pop_back) {
cl_head_t *p, *q;
if (*h == 0) return 0;
p = pop_back? *h : (*h)->next, q = p->prev;
if (p == q) *h = 0;
else q->next = p->next, q->next->prev = q, *h = q;
return p;
}
// Given a pointer to a struct member, get the pointer to the struct
#define cl_container_of(ptr, type, mb) ((type*)((char*)(ptr) - offsetof(type, mb)))
This header only implements the topology of a cdlist, but doesn’t specify how to store data. The following “test.c” shows how to use this library:
#include <stdlib.h> // for malloc()
#include <stdio.h> // for printf()
#include "cdlist.h"
typedef struct { int x; cl_head_t head; } my_elem_t;
static inline my_elem_t *my_elem_create(int x) {
my_elem_t *p = (my_elem_t*)malloc(sizeof(*p));
p->x = x;
return p;
}
int main(void) {
cl_head_t *head = 0;
cl_push(&head, &my_elem_create(3)->head, 1);
cl_push(&head, &my_elem_create(4)->head, 1);
cl_push(&head, &my_elem_create(2)->head, 0);
cl_push(&head, &my_elem_create(5)->head, 1);
cl_push(&head, &my_elem_create(1)->head, 0);
while (head) {
cl_head_t *p = cl_pop(&head, 1);
my_elem_t *q = cl_container_of(p, my_elem_t, head);
printf("out: %d\n", q->x);
free(q); // use code manages memory
}
return 0;
}
Line 5 defines the struct that holds data. It has a “cl_head_t” member variable – the cdlist library “intrudes” the definition of user data types. Line 14 initializes an empty cdlist, which is simply a NULL pointer. Line 15–19 adds data to the list. Notably, we are adding pointers to the “cl_head_t” member variable, not pointers to the data. Then we have a list of “cl_head_t” objects. Line 22 gets a pointer to “my_elem_t” from a pointer to “cl_head_t”. The trick here is that the offset between a struct pointer and a pointer to its member is fixed and can be computed by the offsetof macro.
With this intrusive list, users have to take care of memory allocation. The advantage is this is more flexible. Users may allocate “my_elem_t” objects from heap or stack or freely choose their own allocators. The downside is intrusive lists are harder to use, as users have to manage memory by themselves. To me, this flexibility is more important than convenience. I generally recommend intrusive lists over non-intrusive ones.
Attractive Chaos 
