Simple Allocator Pattern for C

Nov 25 2023

When I first made the switch from C# to C++, I was excited to be diving into the world of handling my own memory (I'll forgo the rant about C# memory management and garbage collection). The transition was a feeling of being simultaneously unshackled and lost. A wide world of possibility. Think: exiting the vault in Fallout 3.

The main thing I wanted to do was easily change where newly allocated memory came from for a given procedure or data structure. For example, a dynamic array. In my game projects, I'm mostly just using Arenas. Refer to Ryan Fleury's excellent article on Arenas for memory management.

But I didn't want to have every function take an Arena pointer in its parameters and pass it down the call stack all the time. Also, what if I don't want to use an Arena, but maybe just the system heap? What if I have some other allocator I want to implement?

I understand your frustration.

I made some attempts of my own; abusing preprocessor macros and templates, but I found a much more elegant solution to this problem in Jonathan Blow's jai language. He defines an Allocator as a struct with just two fields: a function pointer and a data pointer. The function does all the different allocation operations you might want to do, alloc realloc free etc, and just switches on an enum to decide which to do.

I went ahead and adopted this pattern in my codebase and have been happy with the results. While jai does some smart things with an implicit context with regards to allocation, mine just lets me assign an allocator to a data structure or pass it as an argument. Here's an example:

List list = make_list(sizeof(int64)); // just sets the element_size list.allocator = temporary_allocator; // allocate to temp storage *(int64*)add(&list) = 10; *(int64*)add(&list) = 15; *(int64*)add(&list) = 20; *(int64*)add(&list) = 25; *(int64*)add(&list) = 30; do_something_with_the_list(&list); reset_temporary_storage(); list = make_list(sizeof(char)); list.allocator = system_allocator; // allocate to system heap *(char*)add(&list) = 'c'; *(char*)add(&list) = 'o'; *(char*)add(&list) = 'o'; *(char*)add(&list) = 'l'; do_something_with_the_list(&list); reset(&list); // free the memory

Pretty convenient right? The List is just a dynamic array that maintains contiguous memory but forgoes pointer stability. Passing it an allocator lets you decide where it's getting that memory when it resizes.

Here's how the allocator is implemented:

struct Allocation_Parameters { enum Mode { ALLOC, REALLOC, FREE }; Mode mode; void *ptr = nullptr; size_t request = 0; size_t original_size = 0; void *heap_data = nullptr; }; typedef void*(*allocation_function)(Allocation_Parameters); struct Allocator { allocation_function fn; void *heap_data; }; void *system_allocation(Allocation_Parameters p) { // wraps VirtualAlloc, VirtualFree, malloc, free, etc. switch(p.mode) { case Allocation_Parameters::ALLOC: { return platform_alloc(p.request); } break; case Allocation_Parameters::REALLOC: { return platform_realloc(p.ptr, p.original_size, p.request); } break; case Allocation_Parameters::FREE: { platform_free(p.ptr); return nullptr; } break; } return nullptr; } void *arena_allocation(Allocation_Parameters p) { Arena *arena = (Arena*)p.heap_data; switch(p.mode) { case Allocation_Parameters::ALLOC: { return arena_alloc(arena, p.request); } break; case Allocation_Parameters::REALLOC: { return arena_realloc(arena, p.ptr, p.original_size, p.request); } break; case Allocation_Parameters::FREE: { // noop - free is not supported in arenas return nullptr; } break; } return nullptr; }

While Jon uses a function with all of the parameters right in the prototype, I went for a parameters struct which allows me to more easily extend it (I added alignment, for example).

Now you just have to use it. Here's what the List's resize function might look like:

// convenience function, just fills the parameter struct void *realloc( Allocator allocator, void* ptr, size_t original_size, size_t new_size) { Allocation_Parameters p; p.mode = Allocation_Parameters::REALLOC; p.original_size = original_size; p.request = new_size; p.ptr = ptr; p.heap_data = allocator.heap_data; return allocator.fn(p); } void resize(List* list, int64 new_size) { if (list->buffer.length >= new_size * list->element_size) return; void *new_buffer = realloc( list->allocator, list->, list->element_size * list->count, list->element_size * new_size); assert(new_buffer); list-> = (byte*)new_buffer; list->buffer.length = new_size * list->element_size; }