Proper layout for an an mempool/memory allocator? (which algorithm)

Hello, I'm thinking about trying to expand my skills by trying some things I've never done before. One 开发者_如何学Cthing that has always mystified me a bit is memory allocators and memory pools. What I want to do is take a block of memory and only allocate the memory from the system once. I have that currently set up, the memory is an array of bytes (or chars) that is 65535 for my testing purpose.

I have two algorithms that I've considered using.

First is an algorithm where the entire block of data is appended with the amount of memory left over, and a pointer (or rather an offset) to the first allocated block (or the header of the block), then each allocation is preceded by the size of the allocation, and the previous and next allocation, so I can release the allocation easily. I then can generate the largest and smallest blocks by looking at the space after the current allocations.

The other option I have is to add an second offset before the allocated memory and make that point to the first unallocated block, then each unallocated block also has the Previous and Next allocation, along with a size so that I can easily find a place where my next allocation can be placed.

The issue is I can't tell which is "proper". Assume we'll have variable size allocations (but most will be at a size that this isn't that much overhead.) The first will be slower to get the largest and smallest possible blocks, but I can store those and manipulate them if necessary to avoid regenerating them. However the second would take a longer time to deallocate (due to having to find which deallocator is next to which allocator) and not necessarily give any benefits to allocation. In fact it will require more specialized code for the case where I have less than 6 bytes left over (2 bytes for size, 2 for prev offset, 2 for next offset).

My gut tells me the first would be far superior, but something about the second is enticing. Any opinions? Or is there a far easier solution?

The problem with this type of approach is handling fragmentation (and hence how to coalesce adjoining free chunks of memory). Look at this question: Designing and coding a non-fragmentizing static memory pool, discusses a different approach...