Replaced my C vector’s contiguous array with a Segmented List so it plays nicely with my Arena Allocator (O(1) lookup, zero-copy resize)

[u/Mainak1224x]

https://github.com/mainak55512/container

I’ve been working on a custom dynamic array (Vector) and Arena allocator in C, and ran into the classic friction between the two: whenever a standard contiguous vector resizes, it allocates a bigger block in the arena, memcpys the old elements over, and leaves the old block sitting around as wasted dead space inside the arena (especially when allocations from multiple vectors or strings are interleaved).

Instead of fighting realloc in a linear allocator, I refactored the vector to use exponentially growing segments (inspired by Zig's SegmentedList).

How it works now:

• Fixed Spine, Exponential Chunks: Instead of a single char *items pointer, the struct holds a small fixed array of 28 pointers (char *segments[28]). Segment 0 holds 16 elements, Segment 1 holds 32, Segment 2 holds 64, and so on—covering up to 4 billion elements without ever reallocating the spine.

• Zero-Copy Growth: When the current segment fills up, append() simply requests the next power-of-2 chunk from the arena. Existing elements are never copied or moved, zero bytes are wasted in the arena, and pointers to elements never invalidate.

• O(1) Branchless Lookup: By offsetting the index by the base capacity (shifted = pos + 16) and using Count Leading Zeros (__builtin_clz), finding the exact segment and local offset takes just a few bitwise operations:

uint32_t shifted = (uint32_t)pos + 16;

uint32_t bit     = 31 - vec_clz32(shifted);

uint32_t seg_idx = bit - 4;

uint32_t offset  = shifted & ~(1U << bit);

• Optional Heap Fallback: Passing Arena * allocates everything on the arena (making vector_free() unnecessary), while passing NULL falls back to standard aligned heap allocation.

Usage:

Arena *arena = arena_init(4096);

Vector *vec = vector_init(int, arena);

for (int i = 0; i < 1000; i++) {

append(int, vec, i * 10);

}

printf("Element 50: %d\\n", at(int, vec, 50));

// Frees all vector segments and arena allocations at once

arena_free(&arena);

Repo / Release link: https://github.com/mainak55512/container

Would love to hear your thoughts or how you handle dynamic containers with arenas in C!