Get the latest tech news
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”.
It’s not strictly necessary, but it makes the math nice and allows us to use fast bit shift operations for calculating indices: It makes the code less nice, but can be useful if you don’t want it to waste ~50% of its memory when used as the backing array for a power-of-two-sized hash table. I’ve found the segment array useful in situations where you are generating an unknown number of items over time and you’re using an arena allocator - like in the build profiler I’m working on.
Or read this on Hacker News