Home

The usual heap-manager simply connects free blocks to a chain.



If there are many gaps, finding a free block can take many iterations.

My manager uses Clusters to map gaps by size and by offset.



When allocating, the smallest free block top most of the heap is returned.

The difficulty was to make the map re-enterable. Adding a free block to the map can cause an allocation, the opposite when removing. I got this done by caching releases in free blocks, and by making allocations passive without moving anything in the map.

There is still an opportunity to move internal data-structures away from the end of the heap, but i don't need this by now.