Home
The heap is the dynamic memory of the application. It allows the user to allocate and free memory at runtime.
In application-development we have static memory, reserved at build-time and allocated when the application is started.
We also have a stack, which can grow and shrink but not be fragmented.
To support higher languages like C++ we need dynamic memory, that is the heap.
heap_handle_t heap_create(size_t offset, size_t size);
A small header get's stored right at the beginning:
typedef struct
{
size_t free;
size_t used;
size_t size;
size_t free_block;
size_t map_free;
}heap_t;
void* heap_alloc(heap_handle_t heap, size_t size);
If there is a gap big enough, it is found in the map. Else a new heap_block is created at the end of the heap.
The size and a flag if it is free are stored twice at the head and the foot. This is neccessary to combine free blocks next to each other.
void heap_free(heap_handle_t heap, void* buf);
The block is added to the map and marked free. If there are free blocks left or right of it, those get removed from the map and a combined block is added.
Free blocks are sorted by size and by offset.
When allocating from the map, the smallest gap top most of the heap is returned.
https://github.com/svenbieg/Clusters
Adding a free block to the map can cause an allocation, the opposite when removing. I've made it by caching releases in free blocks, and by making allocations passive without moving anything in the map.