Depends on how you structure your memory. But there are two ways to my mind of doing this.
Store the size of the allocation to both the left and right of the header along with a free bit. This works best if you have a max allocation size that allows you to bit pack.
A good example would be a 15 bits of allocations size. This would allow you to pack a 32bit field with:
- the two sizes (@15bits each),
- have 1 bit as an allocation bit for the right hand side,
- and have a checksum bit to detect memory under/overflows.
The two sizes allow you to link list forward and backwards and then check the allocation bits. If they aren't set, then you can merge the allocations.
Have two external pointers one to the first allocated slot, the next to the first unallocated slot (freelist).
The header of each block contains a pointer to the previous, and a pointer to the next block. If its allocated these point to the prior/next allocated block. If its unallocated these point to the prior/next unallocated block. It also needs the size field of the allocation.
Pick an unallocated slot, the next allocated block is
header+size to the right. Unlink the allocation from the freelist, link into the allocated list. If the allocation has to be split, split it first into two unallocated slots, just remember that where the next allocated block is first.
Freeing an allocated slot, scan the linked list to the right, the first
header+offset != next identifies the next unallocated slot at
header is relative to last confirmed allocated slot. Same story for scanning backwards, except the
header is the prior slot. If the next/prior unallocated was the first slot checked, then the free slot is adjacent and can be merged, otherwise they aren't and need to be linked.
Depends entirely on the trade off you'd like to make.