Index-Based Linked Lists for Relocatable and Persistent Storage

A pointer is an address, and an address is only meaningful inside the process that created it. Write a linked list to a file, or map the same file at a different base address, or share it between two processes, and the stored pointers become garbage. Replacing them with offsets relative to a known base makes the structure relocatable, and the resulting design is the basis of most on-disk and shared-memory linked structures.

The change is mechanically small, one field type, and it propagates into every operation. Free-slot management appears where the allocator used to be, dangling references become possible without any memory being freed, and the structure acquires a maximum size determined by the index width.

The representation change

Instead of storing the address of the successor, store its ordinal position in a table of fixed-size slots.

#define NIL 0xFFFFFFFFu

struct slot {
    uint32_t next;      /* index of successor, or NIL */
    uint32_t prev;      /* index of predecessor, or NIL */
    uint8_t  used;      /* 0 = free slot, 1 = live */
    uint8_t  pad[3];
    uint32_t payload;
};

struct arena {
    struct arena_hdr *hdr;   /* head, free-list head, slot count */
    struct slot *slots;      /* array of `count` slots */
};

With a 32-bit index the arena can address 4,294,967,296 slots, and each slot is 16 bytes here, so the maximum arena is 64 GiB. A 64-bit index removes the limit at the cost of 8 bytes per link. Most embedded and on-disk formats choose the narrowest index that covers the intended capacity, because the index width is paid per slot and per link.

The absolute address of slot i is base + i * sizeof(struct slot), which is one multiply or shift and one add on every access. The multiply is often folded into the addressing mode or strength-reduced to an add when the index advances by a constant, so in a traversal the arithmetic mostly disappears into the load; in random access it is a visible extra instruction on the critical path.

What relocation buys

The immediate benefit is that the arena is position-independent. Map the same file at two different addresses in two processes and both can traverse the structure, because every link is an offset. This is how memory-mapped databases share an index between readers without copying it, and how a file format can be validated on one machine and used on another.

The second benefit is persistence without serialisation. There is no encode step: the in-memory layout is the on-disk layout, and writing the arena to a file is a write of the mapped region. SQLite’s file format is built on this principle, with pages addressed by page number and b-tree cells holding offsets into the page rather than addresses. The cost is that the layout must be defined byte for byte, including padding, and that it must be endian-defined. A format that stores a native-endian uint32_t is not portable across architectures, so on-disk structures either fix an endianness or carry a marker.

The third benefit is that the structure can be moved within a process. Growing an arena means allocating a larger block, copying the slots, and updating the base pointer; every internal link remains valid because every link is relative. A pointer-based list cannot be moved at all without walking it and rewriting each link.

The free list that replaces malloc

Without an allocator, freed slots must be tracked. The standard approach is to thread a free list through the unused slots themselves: the next field of a free slot holds the index of the next free slot, and the arena header holds the head of that chain.

uint32_t alloc_slot(struct arena *a) {
    uint32_t i = a->hdr->free_head;
    if (i == NIL) return NIL;                 /* arena full */
    a->hdr->free_head = a->slots[i].next;
    a->slots[i].used = 1;
    a->slots[i].next = a->slots[i].prev = NIL;
    return i;
}

void free_slot(struct arena *a, uint32_t i) {
    a->slots[i].used = 0;
    a->slots[i].next = a->hdr->free_head;
    a->hdr->free_head = i;
}

This is the same technique a kernel uses for free pages and a file system uses for free blocks, and it is the intrusive pattern of Intrusive Linked Lists applied to slots instead of objects: the link lives inside the storage it describes, so it costs nothing beyond the header field. The hazard is that a use-after-free write to a freed slot corrupts the free list, and the corruption manifests as an allocation returning a slot that is already in use. The used flag catches the common case if every access checks it, which costs a branch per access and is skipped in the paths that have already validated the slot.

Two other policies are common. A bitmap of used slots costs one bit per slot and makes finding a free slot a scan rather than a pop, which is better for locality of allocation and worse for O(1) free. A bump allocator with no reuse is simplest and correct for append-only arenas, at the cost of unbounded growth. The choice depends on whether the workload churns slots or only appends.

Stale indices are not dangling pointers

The most important difference from pointer-based lists is in the failure mode. A freed pointer that is dereferenced reads memory the allocator may have reused; a freed index that is followed reads a slot the arena may have reassigned. Both are use-after-free, and both are undefined. The index version has an advantage: the slot number remains a valid array index, so a stale reference usually lands inside the mapped arena and returns some slot’s contents rather than faulting. It also has a disadvantage: nothing distinguishes a valid slot from a recycled one, and a fault would at least have told the program something had gone wrong.

Formats that need to detect stale references add a generation counter: each slot carries a small integer incremented on free, and a reference is a pair of index and generation. A reference whose generation does not match the slot’s is stale. This is the same technique as a generational handle in a resource manager, and it doubles the size of every reference. It is worth the cost in formats where corruption is unacceptable and not worth it in transient in-memory structures.

Traversal cost

An index-based traversal is a pointer chase with extra arithmetic. The dependency chain is the same: read slots[i].next, compute the address of slot j, read it, and so on. The processor cannot start the next load until the index has arrived, so the latency per hop is the same as for a pointer-based list, plus the multiply.

The compensating factor is density. A slot of 16 bytes with two 4-byte links and a 4-byte payload packs four slots per 64-byte line, so a traversal that touches one slot per hop wastes three quarters of the line, same as the plain node layout. Making the slot 8 bytes (two 16-bit indices and a 32-bit payload) packs eight per line, and making it 4 bytes packs sixteen. The narrow index is therefore not only a capacity decision but a locality decision: smaller slots mean more of each fetched line is useful.

For read-only mapped data, the operating system’s page cache holds the arena, and the traversal is a sequence of page-cache hits after the first fault per page. The 4 KiB page granularity means a cold traversal faults every 4096 bytes, which at 16 bytes per slot is every 256 hops. That is why persistent structures benefit from clustering related nodes into the same page, and why on-disk formats group records into pages rather than laying them out in a flat table. The same reasoning about lines per hop drives the block sizing in Unrolled Linked Lists, with a page substituted for a cache line.

Ordering and crash consistency

A persistent linked structure has an additional failure mode that an in-memory one does not: a crash between two writes leaves a partially updated link. If an insertion writes new->next = old->next and then old->next = new, a crash between the two leaves a node that is not in the list, which is harmless. If the order is reversed, a crash leaves old->next pointing at a node whose next field is uninitialised, which is corruption.

The rule is to write the new node’s fields before publishing it, and to publish it with a single write to a single aligned field. A store within one sector is not torn by the device, so on a medium that writes a 512-byte or 4 KiB sector as a unit, a single aligned pointer-sized store either lands or does not. That does not make it durable: the write may still be sitting in a cache when the power fails, so the ordering that matters is the one the storage stack enforces, and it has to be requested explicitly with a flush or a barrier. Writing a single sector is a weaker property than ordering two writes, and formats that need the second property use a journal or a copy-on-write scheme, which is the point at which the linked structure becomes a file system problem rather than a data structure problem. Copy-on-write formats sidestep it entirely: a modified node is written to a new slot, the parent’s link is updated to point at the new slot, and the old slot is freed only after the new root is committed.

When the index layout is the wrong choice

The overhead is real and the pattern is not free. Three conditions argue against it.

Small structures in a process. A 32-bit index and a multiply per access is strictly worse than a pointer when the structure lives in one process and never moves. The pointer version is one load with no arithmetic and no arena header.

Frequent growth. An arena that must grow by copying every slot is O(n) per growth, and unlike a dynamic array there is no simple geometric policy that amortises it if the arena is mapped from a file. Preallocating the maximum size is the usual answer, which trades the growth cost for a fixed reservation and address-space pressure.

Interoperability with existing pointer-based code. Passing an index where a pointer is expected forces a conversion at every boundary, and the conversion needs the base address, so the base becomes a global or a threaded parameter. In a large codebase this is a pervasive change rather than a local one.

The pattern pays when the structure crosses a boundary that pointers cannot: a file, a shared mapping, a network message, or a process boundary. That is precisely the set of cases where the alternative is serialisation, and serialisation of a pointer graph requires either a full walk with address translation or a format that stores indices anyway. Choosing indices from the start avoids the translation layer.