Intrusive lists

An intrusive list is not a container. It stores nothing, owns nothing and allocates nothing. IntrusiveList.h gives you a set of macros that link and unlink nodes through pointer fields that already live inside your own structs. It is the fourth answer to the question Choosing a container asks — who owns the storage — and the answer here is nobody.

The list lives in your data. You keep the nodes, the first and last pointers, and the count if you want one — the macros only ever assign through them.

The problem it solves

Removing a node from a doubly-linked list has four cases, and each one moves a different set of pointers.

The node is	What has to change
The only element	first and last both become null
The first of several	first moves on; the new first’s back link is nulled
The last of several	last moves back; the new last’s forward link is nulled
In the middle	The two neighbours are joined; first and last are untouched

Three of those four are rare enough at runtime to survive casual testing, and a version that gets one wrong corrupts the list silently — the stale pointer still points at mapped, readable memory. Every hand-rolled linked list in a codebase is an independent chance to get one of the four wrong.

DllRemove handles all four, in one place, once.

The model

A node is any struct with self-typed pointer fields. There is no hook type, no base class, and no container_of: the link is already a Node*, so recovering the element from a link is nothing at all.

A list is wherever you keep the ends.

struct Entry
{
    Entry*  next;
    Entry*  previous;
    String8 key;
};

struct Cache
{
    Entry* first;
    Entry* last;
    usize  count;      // yours to keep, or to leave out
};

Cache cache = {};

DllPushBack(cache.first, cache.last, entry);
++cache.count;

DllRemove(cache.first, cache.last, entry);   // O(1), from the entry alone
--cache.count;

The unsuffixed macros assume the fields are literally named next and previous. The _NP and _N forms take the field names as arguments, which is what makes the next section possible — including a node whose backward link is named prev, or anything else.

One node, several lists

This is the reason the macros take field names rather than a typed hook. A node can be a list element, a hash-table entry and a tree node at the same time, and each membership is just another pointer field.

struct Symbol
{
    Symbol* next;          // its module's symbol list  (doubly-linked)
    Symbol* previous;
    Symbol* hash_next;     // a symbol-table bucket     (stack)
    Symbol* next_sibling;  // its parent's child list   (queue)
    String8 name;
};

struct SymbolList { Symbol* first; Symbol* last; };

SymbolList module = {};
SymbolList bucket = {};
SymbolList parent = {};
Symbol*    symbol = arena.Push<Symbol>().data;   // the caller owns the node's storage

DllPushBack(module.first, module.last, symbol);
SllStackPush_N(bucket.first, symbol, hash_next); // a stack has no back, so bucket.last stays null
SllQueuePush_N(parent.first, parent.last, symbol, next_sibling);

With a typed hook each of those memberships would be a hook member and a template instantiation. Here they are three pointer fields and the same macros drive all of them.

A zeroed struct is an empty list

The lists are null-terminated, never circular: the first node’s previous and the last node’s next are null, and an empty list is first == last == nullptr.

That is the property being bought. Arena::Push<T> zeroes, so a struct holding list ends comes out of an arena ready to use, with no initialisation pass.

The classic alternative — a circular list with a sentinel head, as the Linux kernel does — does strictly less work per operation: its insert is four stores and no branch, because previous and next are always dereferenceable and there are no end cases to branch on. (Less work, not a measured speed-up: nothing here was benchmarked, and the choice below was not made on the branch count.) But its empty state is head->next == head->prev == head, so a zeroed one is a null-pointer landmine that looks initialised, and a non-empty one cannot be copied by value: the copy’s nodes still point at the original’s sentinel.

Basalt pays a handful of branches per operation to keep zeroed memory valid.

Nothing is checked

These macros check nothing, so there is a class of mistake they cannot catch and deliberately do not pretend to.

Removing a node from the wrong list corrupts both

DllRemove(other.first, other.last, entry) compiles and runs, and it will happily splice entry’s neighbours together inside the list it is in while moving the ends of the list it is not.

Nothing detects it — verifying membership means walking the list, which would turn the O(1) removal that justifies the whole doubly-linked form into O(N). Keep track of which list a node is in.

The same applies to inserting a node that is already linked through the same field, and to removing the same node twice.

What the macros do guarantee is that nothing is left undefined that a check could have defined: popping an empty list is a defined no-op, and inserting after a null predecessor inserts at the front. A drain loop needs no guard beyond its own test.

while (queue.first != nullptr)
{
    Job* job = queue.first;
    SllQueuePop(queue.first, queue.last);
    Run(job);
}

Debug builds poison a removed node

DllRemove and both pops overwrite the removed node’s own links, in a debug build only, with an address that cannot be mapped. Walking on from a node that is no longer in a list therefore faults immediately instead of following a stale pointer into whatever the list has since become.

A removed node is still re-insertable

Every insert overwrites both of a node’s links without reading either, so you may remove a node and push it straight back — into the same list or another one — in either build. That is the ordinary shape of an LRU touch and of a free-list recycle, and it is a deliberate difference from the Linux kernel, whose poisoning is unconditional and whose removed nodes are not re-insertable.

In a release build the links are simply left as they were, still pointing at the node’s former neighbours. Reading them is a bug either way; debug turns it into a crash.

Arguments are evaluated once

Each macro binds its arguments to local aliases before touching any pointer, so an argument with a side effect happens exactly once.

DllPushBack(GetList().first, GetList().last, node);   // GetList() runs twice, not four times

Every macro is a statement: it takes a trailing semicolon and cannot be used inside an expression.

What you keep

No count is maintained for you. That is not an omission — a list that maintains one counter cannot maintain a different one, and String8List keeps two (node_count and total_size). Keep whichever counters you need, next to the ends.

Nothing is allocated and nothing is freed. Nodes usually live in an arena, and the arena is rewound when they die — no hook is ever reset on the way out, which is exactly the cost that makes Boost.Intrusive’s default link mode slower than its fastest one.

Which storage is safe to link from

A node’s neighbours store its address. Anything that moves the element leaves them pointing at the old location, and the list is silently wrong.

Storage	Safe to link from
Arena	Yes — the arena never moves what it returned
Array<T>	Yes — fixed capacity, it never grows and never relocates
VirtualArray<T>	Yes — committing more never relocates what is already there
HashTrie<K, V>	Yes — an insert links a node; it never moves an entry
DenseHashMap<K, V>	Its values only, and only until an erase moves them
HashMap<K, V>	No — any insert may rehash, and a rehash moves every entry

Two operations do move an element

Array<T>::RemoveSwap copies the last element into the removed slot, so that element’s address changes even though the storage did not move. Unlink it before you swap it away.

ChunkListFlatten copies every element into fresh storage, so every element in the flat result has a new address. Do not link elements that will be flattened, or rebuild the links afterwards.

For anything that will be copied, the pattern that always works is the one String8List uses: keep the nodes in an arena and put pointers — or indices, which survive any relocation — in the sequence container.

Not synchronised

These are plain stores, with no atomics and no barriers. A concurrent reader may observe a partially linked list, so any sharing needs external synchronisation.

Worth stating because the best-known implementation differs: the Linux kernel’s list uses release stores and ships a whole RCU variant, because lock-free readers are a design goal there. None of that is here. A lock-free intrusive list would be a different primitive with a different name.

API summary

Parameters, end cases and the poisoning contract are documented in basalt/core/IntrusiveList.h.

Every operation comes in two forms: an unsuffixed one that assumes the fields are named next and previous, and a suffixed one that takes the field names (_NP for the doubly-linked pair, _N for the single link).

Doubly-linked

Signature	Purpose
DllPushBack(first, last, node)	Appends a node. Works on an empty list.
DllPushFront(first, last, node)	Prepends a node.
DllInsert(first, last, position, node)	Inserts after position; a null position inserts at the front.
DllRemove(first, last, node)	Removes a node in O(1), from the node alone.

Singly-linked queue

Needs first and last, and one link per node. This is the shape String8List has.

Signature	Purpose
SllQueuePush(first, last, node)	Appends a node.
SllQueuePushFront(first, last, node)	Prepends a node.
SllQueuePop(first, last)	Removes the front node. A no-op when empty.

Singly-linked stack

One link, one head, no last: two stores to push and one to pop.

Signature	Purpose
SllStackPush(first, node)	Pushes a node onto the top.
SllStackPop(first)	Removes the top node. A no-op when empty.

Neither pop hands the node back. Read first before popping.