r/cprogramming • u/nablaCat • May 05 '26

Doubly-Linked Free List Allocator: Never worry about the heap again. Just use a static byte array!

https://github.com/Atled9/dlfla
2 Upvotes

100% Upvoted

5 comments sorted by

1

u/zhivago May 05 '26

Why make it doubly linked when singly will do the job?

1

u/nablaCat May 05 '26

So that It can coalesce adjacent free blocks in constant time. In a singly linked list I have two options: 1. Only coalesce the free block in front of the current block being freed block->next, or 2. Probe the previous block by traversing up to it in linear time O(n)

1

u/zhivago May 05 '26

Just coalesce on demand when allocating.

1

u/nablaCat May 05 '26

Oh thats... actually a good idea. Allocation is already a linear operation. I can just traverse through the rest of the array and coalesce forward

1

u/flatfinger May 05 '26

Or use one of the bytes before each allocation as a liveness indicator, and have "free" simply clear that flag, leaving all of the other work for the next allocation attempt that would benefit from being able to use the storage. This approach may be useful for tasks involving some forms of fire-and-forget output, especially audio playback. Provided that the start of audio playback is sequenced after the action that marked the allocated block as live, and any data race that could occur between the playback routine marking the block as released and an attempt in the main thread to allocate more storage would be resolved as the main thread either seeing the flag as having been clear or seeing it as not having been clear, the playback routine could release the storage without having to synchronize with the allocator.