Home

Allocations and deletions are done in constant low time.
Fragmentation is no problem, the heap won't overflow.

Creation

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;
block_map_t map_free;
}heap_t;

Allocation

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.

Deletion

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.

Map

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

Internal Allocation

Adding a free block to the map can cause an internal 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.

Implementation

I've spent my whole holidays on this memory-manager last year.
A few more days on the weekend and i think it is perfect now.

Best regards,

Sven Bieg