August 5, 2025・6 minute read
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”. In Zig’s standard library it’s “SegmentedList”. I use the name “segment array”.
You can download my single-header C implementation here: segment_array.h. The data structure is not limited to C though, you could write it in other languages like Zig, Rust, or C++.
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:
NULL NULL segments array segment 0 segment 1 segment 2
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.
The Implementation
You could implement a Segment Array just from the description above, but there are a few details worth discussing further. Here’s the above diagram as a C struct:
typedef struct { size_t count ; size_t used_segments ; u8 * segments [ 26 ]; } SegmentArrayInternal ;
You might be surprised that the segments array has such a low fixed size. Today’s computers use only 48 bits of the 64 bits in a pointer. That means 49 segments would hold more items than a pointer could even point to, so anything above 48 is out. If you don’t need more than 4 billion items, you can to reduce the segment count to 32. This has the added benefit that you can use a u32 to index the array. Finally, I shave off 6 more segments because the smallest segments sizes (1, 2, 4, 8, 16, 32) aren’t worth their overhead, so the 64 item segment becomes the first segment. 26 segments can hold 4,294,967,232 items (just under UINT32_MAX ).
... continue reading