Intrusive Doubly Linked Lists

Linked lists have a somewhat sketchy reputation these days. Which is a shame, because it's a very flexible and cheap technique for keeping track of a sequence of values.

Singly linked lists are tricky to rearrange and remove items from since you always need access to the previous item, which can only be obtained by starting from the head. Doubly linked lists solve this problem, since you have direct access to both the previous and next item.

The other common objection is memory locality. Since list nodes are separate from the actual values, iterating means chasing pointers at every step. Modern computer architectures derive a lot of their speed from caching large blocks of data, as opposed to repeatedly accessing main memory; which makes ordinary linked lists slow compared to arrays.

Intrusive means that the list's infrastructure is stored inside the values. This means no extra allocations for list nodes and potentially no pointer chasing if values are allocated as a single block of memory.

At this point you may wonder: what is the point of a list of values stored in a single block of memory? The point is that the allocation strategy has little to do with what sequences we choose to put values in. One common strategy in C is to allocate a bunch of values as a single block of memory, as opposed to asking the memory allocator for one value at a time; which reduces memory fragmentation.

This is what a list node looks like; as promised there is no trace of the value, just the links.

struct hc_list {
  struct hc_list *prev, *next;
};

And this is a value which is prepared for inclusion in two lists (at a time).

struct my_item {
  struct hc_list one_list;
  struct hc_list another_list;
  int value;
};

We can now allocate as many items as we need in one block, and add them to a maximum of two lists at a time. List roots are simply nodes that are not part of any values.

  struct hc_list one_list, another_list;
  hc_list_init(&one_list);
  hc_list_init(&another_list);

  const int n = 10;
  struct my_item items[n];
  
  for (int i = 0; i < n; i++) {
    items[i].value = i;
    hc_list_push_back(&one_list, &items[i].one_list);
    hc_list_push_back(&another_list, &items[i].another_list);
  }

Iterating a list means starting from the head and stepping through the links until we reach the head again. Since this is something we'll likely do a lot, extracting the pattern as a macro makes sense. Note that simply switching links form next to prev allows iterating the list in reverse, which is sometimes useful.

#define _hc_list_do(l, i, _list, _next)				
  __auto_type _list = l;
  for (struct hc_list *i = _list->next, *_next = i->next;	
       i != _list;						
       i = _next, _next = i->next)

#define hc_list_do(l, i)				
  _hc_list_do(l, i, hc_unique(list), hc_unique(next))

Example:

  hc_list_do(&one_list, i) {
    struct my_item it = hc_baseof(i, struct my_item, one_list);
    ...
  }

We use the following macro to reach out from struct hc_list to its struct my_item-container.

#define _hc_baseof(p, t, m, _p) ({		
      uint8_t *_p = (uint8_t *)(p);		
      _p ? ((t *)(_p - offsetof(t, m))) : NULL;
    })

#define hc_baseof(p, t, m)			
  _hc_baseof(p, t, m, hc_unique(pointer))

To remove an item from a list; we don't even need access to the list root, the item is enough.

struct hc_list *hc_list_delete(struct hc_list *l) {
  l->prev->next = l->next;
  l->next->prev = l->prev;
  return l;
}

Example:

hc_list_delete(&items[0].one_list);