Improvements for this C++ stack allocator?

Question

Any suggestions for my stack based allocator? (Except for suggestions to use a class with private/public members)

struct Heap
{
    void* heap_start;
    void* heap_end;
    size_t max_end;

    Heap(size_t size)
    {
        heap_start = malloc(size);
        heap_end = heap_start;
        max_end = size + (size_t) heap_start;
    }

    ~Heap()
    {
        ::free(heap_start);
    }

    void* allocate(size_t bytes)
    {

        size_t new_end = ((size_t) heap_end) + bytes;

        if( new_end > max_end )
            throw std::bad_alloc();

        void* output = heap_end;
        heap_end = (void*) new_end;
        return output;
    }

}

Answer 1

You've implemented a stack based allocator. You can't free up without leaving gaps. Usually a pool refers to a block of contiguous memory with fixed sized slots, which are doubly linked to allow constant time add and delete.

Here's one you can use as a guide. It's along the same lines as yours but includes basic iterators over allocated nodes, and uses templates to be type aware.

Answer 2

size_t new_end = ((size_t) heap_end) + bytes;

Not good, never do things like that, you assume that sizeof(size_t)==sizeof(void*), also what happens if bytes==(size_t)(-1) this would not work

Additionally, you need make sure that pointers that you are return are aligned. Otherwise you would have problems. So you need to make sure that bytes are multiple of 4 or 8 according to your platform.

class {...
char *max_end,*head_end,*heap_start;
};

...
max_end=heap_start+size;
...
bytes=align_to_platform_specific_value(bytes);
if(max_end-heap_end >= bytes) {
   void* output = (void*)heap_end;
   heap_end+=bytes;
   return output;
}
throw std::bad_alloc();

Suggestion? Do not reinvent the wheel. There are many and good pool libraries.

Answer 3

Two obvious problems:

1/ You don't have a deallocate().

2/ A deallocate() will be very hard to write with your current strategy unless you're always going to deallocate in the exact reverse order of allocating. You'll need to cater for the case where a client wants to deallocate memory in the middle of your used section.

Of course, if you do deallocate in reverse order, (2) is not a problem. And if you never free memory at all, (1) is also not a problem.

It depends on what you want it to do.

Answer 4

Your heap doesn't allow deallocation. How will you use it for objects allocated with new in C++?