If you combine a dynamic array with an arena allocator, you get a dynamically growing buffer on top of a dynamically growing buffer. The easiest way to implement realloc is as malloc + memcpy + free, but that behaves sub-optimally here. Unfortunately the standard realloc interface prevents you from doing any better. You could fix that by storing extra metadata, specifically the allocation size, along with your allocations to determine if a given pointer is the topmost allocation, but arenas are meant to be very simple and that isn't. Instead, we can rely on realloc users necessarily tracking the allocation size anyway and make it part of the interface.
Let's start with a general allocator interface:
struct Allocator {
virtual void * allocate( size_t size, size_t alignment ) = 0;
void * reallocate( void * old_ptr, size_t new_size, size_t alignment ) {
// allocate memcpy deallocate
}
virtual void deallocate( void * ptr ) = 0;
};
struct ArenaAllocator : public Allocator {
u8 * memory;
u8 * memory_end; // memory + size
u8 * top;
void * allocate( size_t size, size_t alignment ) {
Assert( IsPowerOf2( alignment ) );
u8 * aligned = ( u8 * ) ( size_t( top + alignment - 1 ) & ~( alignment - 1 ) );
if( aligned + size > memory_end ) {
abort();
}
top = aligned + size;
return aligned;
}
void free( void * ptr ) { }
};
And DynamicArray:
template< typename T >
struct DynamicArray {
Allocator * a;
size_t n = 0;
size_t capacity = 0;
T * elems = NULL;
DynamicArray( Allocator * a_ ) { a = a_; }
void add( const T & x ) {
if( n == capacity ) {
grow();
}
elems[ n ] = x;
n++;
}
void grow() {
capacity = Max2( 1, capacity * 2 );
elems = ReallocMany< T >( a, elems, capacity );
}
};
(Production ready code might use static dispatch instead of dynamic dispatch/split allocate into
try_allocate that can return NULL and allocate that aborts/ASAN_(UN)POISON_MEMORY_REGION
in both classes/SourceLocation/anything but 1 as the initial array size/etc but let's
ignore all that.)
Now let's see what happens when we put these together. Say we have an arena big enough to hold eight
ints, and add 1 2 3 to the array. I'll use . to denote uninitialised memory and underlined text
for the memory currently owned by the array.
array = [], arena = [. . . . . . . .] add(1) -> realloc(1), array = [1], arena = [1 . . . . . . .] add(2) -> realloc(2), array = [1 2], arena = [1 1 2 . . . . .] add(3) -> realloc(4), array = [1 2 3], arena = [1 1 2 1 2 3 . .]
So we used 7 slots in the underlying buffer to represent an array with 3 out of 4 elements in use.
If we instead modify our realloc to take the old allocation size, we can check to see if we're reallocating the topmost allocation and grow it in place. Implementing that looks like this:
void * ArenaAllocator::reallocate( void * old_ptr, size_t old_size, size_t new_size, size_t alignment ) {
if( old_ptr == NULL ) {
return allocate( new_size, alignment );
}
// are we the topmost allocation and sufficiently aligned?
if( old_ptr == top - old_size && size_t( ptr ) % alignment == 0 ) {
u8 * new_top = top - old_size + new_size;
if( new_top > memory_end ) {
abort();
}
top = new_top;
return old_ptr;
}
// allocate memcpy (deallocate is noop)
}
void DynamicArrray::grow() {
size_t new_capacity = Max2( 1, capacity * 2 );
elems = ReallocMany< T >( a, elems, old_capacity, new_capacity );
capacity = new_capacity;
}
Which exhibits "just" O(1) instead of amortised O(1) behaviour:
array = [], arena = [. . . . . . . .] add(1) -> realloc(0, 1), array = [1], arena = [1 . . . . . . .] add(2) -> realloc(1, 2), array = [1 2], arena = [1 2 . . . . . .] add(3) -> realloc(2, 4), array = [1 2 3], arena = [1 2 3 . . . . .]
This all obviously breaks down and reverts to the old behaviour if you allocate anything after the array, but I've found that in practice it doesn't happen very often, and the change is simple and non-intrusive enough to be a win.