Paged List

A cache-friendly, pointer-stable dynamic array.

Concept & Motivation

The Problem: Standard Vectors grow by realloc, which copies all data to a new location. This invalidates pointers and thrashes the cache.

The Solution: A Paged List. We allocate fixed-size blocks ("Pages"). When one fills, we simply allocate a new one. Old data never moves.

Architecture

• Page Size: 256 Items.

• Growth: $O(1)$.

• Access: $O(1)$ (calculated via index / 256).

Pointer Stability: Because pages are never reallocated, pointers to items inside a List remain valid for the entire lifetime of the list. You can safely store pointers to list elements.

---

API Reference

list.create

Initializes the list directory on the Arena.

List nums = list.create(&arena, sizeof(int));

list.push

Copies data into the next available slot.

int val = 42;
list.push(&nums, &val);