Argthtjtr

I want to create my own game engine so I bought a few books one being Game Engine Architecture Second Edition by Jason Gregory and in it he suggests implementing a few custom allocators. One type of allocator the book talked about was a stack-based allocator, but I got confused when reading it. How do you store data in it? What data type do you use? For example, do you use a void*, void**, an array of char? The book says you're meant to allocate one big block of memory using malloc in the begining and free it in the end, and "allocate" memory by incrementing a pointer. If you could help explain this more, or point me to a tutorial that would be great because I can't seem to find a tutorial that doesn't use std::allocator.

This is the header file example they give in the book:

class StackAllocator

{

 public:

    // Represents the current top of the stack.

    // You can only roll back to the marker not to arbitrary locations within the stack

    typedef U32 Marker;



    explicit StackAllocator(U32 stackSize_bytes);



    void* alloc(U32 size_bytes); // Allocates a new block of the given size from stack top

    Marker getMarker(); // Returns a Marker to the current stack top

    void freeToMarker(Marker marker); // Rolls the stack back to a previous marker

    void clear(); // Clears the entire stack(rolls the stack back to zero)



private:

    // ...

}

EDIT:
After a while I got this working but I don't know if I'm doing it right

Header File

typedef std::uint32_t U32;



struct Marker {

    size_t currentSize;

};



class StackAllocator

{

private:

    void* m_buffer; // Buffer of memory

    size_t m_currSize = 0;

    size_t m_maxSize;



public:

    void init(size_t stackSize_bytes); // allocates size of memory

    void shutDown();



    void* allocUnaligned(U32 size_bytes);



    Marker getMarker();

    void freeToMarker(Marker marker);



    void clear();

};

.cpp File

void StackAllocator::init(size_t stackSize_bytes) {

    this->m_buffer = malloc(stackSize_bytes);

    this->m_maxSize = stackSize_bytes;

}



void StackAllocator::shutDown() {

    this->clear();



    free(m_buffer);

    m_buffer = nullptr;

}



void* StackAllocator::allocUnaligned(U32 size_bytes) {

    assert(m_maxSize - m_currSize >= size_bytes);



    m_buffer = static_cast<char*>(m_buffer) + size_bytes;

    m_currSize += size_bytes;

    return m_buffer;

}



Marker StackAllocator::getMarker() {

    Marker marker;

    marker.currentSize = m_currSize;

    return marker;

}



void StackAllocator::freeToMarker(Marker marker) {

    U32 difference = m_currSize - marker.currentSize;

    m_currSize -= difference;

    m_buffer = static_cast<char*>(m_buffer) - difference;

}



void StackAllocator::clear() {

    m_buffer = static_cast<char*>(m_buffer) - m_currSize;

}

Okay for simplicity let's say you're tracking a collection of MyFunClass for your engine. It could be anything, and your linear allocator doesn't necessarily have to track objects of a homogenous type, but often that's how it's done. In general, when using custom allocators you're trying to "shape" your memory allocations to separate static data from dynamic, infrequently accessed vs. frequently accessed, with a view towards optimizing your working set and achieving locality of reference.

Given the code you provided, first, you'd allocate your memory pool. For simplicity, assume you want enough space to pool 1000 objects of type MyFunClass.

StackAllocator sa;

sa.Init( 1000 * sizeof(MyFunClass) );

Then each time you need to "allocate" a new block of memory for a FunClass, you might do it like this:

void* mem = sa.allocUnaligned( sizeof(MyFunClass) );

Of course, this doesn't actually allocate anything. All the allocation already happened in Step 1. It just marks some of your already-allocated memory as in-use.

It also doesn't construct a MyFunClass. Your allocator isn't strongly typed, so the memory it returns can be interpreted however you want: as a stream of bytes; as a backing representation of a C++ class object; etc.

Now, how would you use a buffer allocated in this fashion? One common way is with placement new:

auto myObj = new (mem) MyFunClass();

So now you're constructing your C++ object in the memory space you reserved with the call to allocUnaligned.

(Note that the allocUnaligned bit gives you some insight into why we don't usually write our own custom allocators: because they're hard as heck to get right! We haven't even mentioned alignment issues yet.)

For extra credit, take a look at scope stacks which take the linear allocator approach to the next level.