Another useful memory algorithm is a pool allocator, which allocates lots of small blocks of memory of the same size.  Often times in programming games (and other applications) there are times where you need to allocate small chunks for same-sized items such as matrices, or multiple instances of the same object.  Obviously a pool allocator is the natural fit.  My implementation is below. 

--> Open PoolAllocator.cpp in a new window <--

The code above is hosten on Google Code, and you can comment by double clicking anywhere, or by clicking in the left hand margin on the little speech balloon plus icon. You need to be signed in with a google account.  Please comment and tell me if my code sucks!

Implementing a stack allocator isn't hard, but there is one important memory saving trick I'll discuss below:

1. When creating the pool, preallocate a large block of memory, the size of which is a multiple of the size of the separate pool elements.
2. Add each of the free elements to a linked list.
3. When someone wants to use a block, pop one off the free list and return it to the user.
4. When a block is freed, add it back to the free list.
5. When deleting the pool, assert that the number of free elements is equal to the pool size divided by the size of an individual element.

That part is easy.  But we have to consider where we will get memory for the linked list to track the free elements.  Or do we?  We have all this free space in each of the free elements, why not put it to good use?

NOTE: The one caveat here is that the size of each element in the list must be larger than sizeof(void*)

To track the free items in the free list itself we do the following.

1. When creating the pool, after allocating the memory, starting with the beggining of the list, write the address of the next free block at the start of the current block.
2. When providing a block to the user, return the start of the list, but not before setting the pointer to the start of the list to the next block.
3. When returning a block to the free list, write the address of the start of the free list into the start of the newly free block, and set the start of the free list to the newly freed block's address.

Remember that when using the memory of the free block itself as the pointer to the next block, the equivalent to 

mFreeListStart = mFreeListStart->next;

Becomes:

mFreeListStart = (u32*)*mFreeListStart;

Where mFreeListStart is a u32* to the start of memory of the first element in the list,

next is a u32* to the next element,

and  u32 is a 32-bit unsigned integer type.