Memory Fragment pool

Assume we need hundreds of small blocks of memory, how can we manage it efficiently? If you are thinking of calling 'new' hundreds of times, you might want to reconsider. Ideally we would allocate one big block of memory, and then divide it into small blocks, which can be requested by the user of our interface. But how can we quickly determine which block is free? A linked-list comes to mind. When we want to allocate memory, we just return the first element in the list, When we release memory, we chain it back into the list.

So first we need to find a structure to represent our Fragment Pool.
Below follows an example implementation of this design pattern. We have a fragmentpool - with a predetermined number of blocks, and blocksize (maximum size for a single allocation). We have a pointer to a big blob of memory to hold our blocks and finally a pointer to the first element of a linked list, linking our free blocks.

note: example code is provided in plain-C for portability to platforms like iPhone.
Our memory-blob (data) will be blocks * blocksize bytes large. Now we need to somehow do maintenance about which blocks are in use, and which are available. But how do we build our freelist, preferably without additional allocations?

Let's assume a minimal blocksize of a memory pointer: 'sizeof(FragmentPoolList*)'. Now if a block isn't in use, it's contents are irrelevant from a client-side of view, because it doesn't own the memory (and we all know we shouldn't write to memory which we don't own). Which is actually very convenient, it means our pool is allowed to write whatever it wants in the unused blocks - for example a freelist next-pointer. The moment the client requests a block, we remove the first block, and rechain the remaining block by changing a pointer. Since the returned block is now client-owner, he can write whatever he wants into it. When the clients frees the memory, we use the block again to rechain it into our freelist. This way we avoid any additional allocations and have quick constant-time allocations.

Below an example of the client-interface:
and here the implementation:
note1: x_free and x_alloc are simple wrappers for malloc and free
note2: this implementation is not thread-safe!

Now one disadvantage is that we have to pre-specify the number of blocks we want. But what if we don't know that in advance? The above example can be extended by creating a new FragmentPool when we run out of memory, and linking all fragmentpools together with a list...

special thanks to Bastian Rolf for his C++ memory manager examples.
JSN Teki template designed by