A Fast, Growable Array With Stable Pointers in C
My last article about generic data structures in C was written to set the stage for today’s topic: A data structure that can be used in place of dynamic arrays, has stable pointers, and works well with arena allocators. It’s been independently discovered by different programmers over the years and so goes by different names. A 2001 paper called it a “levelwise-allocated pile” (bleh). Others call it an “exponential array”. I use the name “segment array”.
I use C in this article, but its concepts work in other languages like Zig, Rust, or C++. You can download my single-header implementation here: segment_array.h.
The core concept is straight forward: items are stored in multiple contiguous segments, and each segment is double the length of its predecessor. New segments are allocated only when needed, and their pointers are kept in a fixed sized array. Here’s how that looks:
Unlike standard arrays, pointers to a segment array’s items are always valid because items are never moved. Leaving items in place also means it never leaves “holes” of abandoned memory in arena allocators. The layout also allows us to access any index in constant time.
