An enum describing the two block size behaviours.
</FONT><FONT color=#0000ff size=1>enum</FONT><FONT size=1> BlockSizeBehaviour { CONSTANT </FONT><FONT color=#008000 size=1>/**< Double the block size after each allocation*/
</FONT><FONT size=1>
, DOUBLE </FONT><FONT color=#008000 size=1>/**< Leave the block size constant */
</FONT><FONT size=1>
This class alocates memory more efficiently than the standard 'new' and 'delete'.
This is done by allocating large "blocks" of data at a time, and then handing out small
pieces of these blocks as data is requested. When a block runs out of free space, a new
one is allocated. Free'd space is reused in subsequent allocations.
It is recommended that classes using a MemoryPool re-implement 'operator new' and
'operator delete' using a namespace-scoped MemoryPool to handle the allocation and deallocation.
This class exploits the allocated space which hasn't been requested by the client yet to hide
the structure of a linked list of free "slots". In order for this to work each slot needs to
be at least as large as a pointer. So, the following condition must hold if you want to use
</FONT><FONT color=#0000ff size=1>template</FONT><FONT size=1> <</FONT><FONT color=#0000ff size=1>typename</FONT><FONT size=1> T>
</FONT><FONT color=#0000ff size=1>private</FONT><FONT size=1>:
</FONT><FONT color=#008000 size=1>// Pointer to the next free 'slot'.
</FONT><FONT size=1>
</FONT><FONT color=#008000 size=1>// The first sizeof(void*) bytes of this slot represents a pointer to the next slot after that, and so on.
</FONT><FONT size=1>
T *nextFree;
size_t blockSize;
BlockSizeBehaviour behaviour;
</FONT><FONT color=#0000ff size=1>void</FONT><FONT size=1> updateBlockSize()
{
</FONT><FONT color=#0000ff size=1>if</FONT><FONT size=1> (behaviour == DOUBLE)
{
blockSize *= 2;
}
}
</FONT><FONT color=#008000 size=1>// Some stats
</FONT><FONT size=1>
size_t totalAllocated;
size_t totalUsed;
</FONT><FONT color=#008000 size=1>// A simple singly-linked list.
</FONT><FONT size=1>
</FONT><FONT color=#0000ff size=1>struct</FONT><FONT size=1> node
{
T* block; </FONT><FONT color=#008000 size=1>//pointer to buffer of T's
</FONT><FONT size=1>
node * next;
};
</FONT><FONT color=#008000 size=1>// Used for storing up blocks. Needed so we can delete them in the destructor.
</FONT><FONT size=1>
node * blockList;
</FONT><FONT color=#0000ff size=1>void</FONT><FONT size=1> saveBlock(T *block)</FONT>
<FONT size=1>{
node * n = </FONT><FONT color=#0000ff size=1>new</FONT><FONT size=1> node;
n->block = block;
n->next = blockList;
blockList = n;
}
</FONT><FONT color=#008000 size=1>// Keep these private to prevent autogenerated versions being exposed
</FONT><FONT size=1>
MemoryPool(</FONT><FONT color=#0000ff size=1>void</FONT><FONT size=1>);
MemoryPool(MemoryPool &p);
MemoryPool & </FONT><FONT color=#0000ff size=1>operator</FONT><FONT size=1>=(</FONT><FONT color=#0000ff size=1>const</FONT><FONT size=1> MemoryPool & bs);
</FONT><FONT color=#0000ff size=1>public</FONT><FONT size=1>:
</FONT><FONT color=#008000 size=1>/**
Initialise the memory pool.
@param initalBlockSize the initial number of "slots" to allocate at a time
@param b the behaviour of the block size. 'CONSTANT' indicates that the same block size is
used every time, 'DOUBLE' indicates that the block size will be doubled each time a new block
is allocated.
*/
</FONT><FONT size=1>
MemoryPool(size_t initialBlockSize, BlockSizeBehaviour b = CONSTANT)
: nextFree(0),
blockSize(initialBlockSize > 0 ? initialBlockSize : 1),
behaviour(b),
totalAllocated(0),
totalUsed(0),
blockList(0)
{};
~MemoryPool(</FONT><FONT color=#0000ff size=1>void</FONT><FONT size=1>)
{
</FONT><FONT color=#008000 size=1>//Go through all allocated blocks and delete them
</FONT><FONT size=1>
node *n = blockList;
node *tmp;
</FONT><FONT color=#0000ff size=1>while</FONT><FONT size=1> (n != 0)
{
</FONT><FONT color=#0000ff size=1>operator</FONT><FONT size=1> </FONT><FONT color=#0000ff size=1>delete</FONT><FONT size=1>(n->block);
tmp = n;
n = n->next;
</FONT><FONT color=#0000ff size=1>delete</FONT><FONT size=1> tmp;
}
};
</FONT><FONT color=#008000 size=1>/**
Allocates space for a single element of type T.
@return A pointer to the allocated space, the contents of which should be considered undefined.
*/
</FONT><FONT size=1>
T* Allocate()
{
</FONT><FONT color=#0000ff size=1>if</FONT><FONT size=1> (nextFree != 0)
{
assert(totalAllocated > totalUsed);
</FONT><FONT color=#008000 size=1>// We have space left in the last block
</FONT><FONT size=1>
T *p = nextFree;
</FONT><FONT color=#008000 size=1>// The value at the location of nextFree is a pointer pointing to the next free slot
</FONT><FONT size=1>
nextFree = *(</FONT><FONT color=#0000ff size=1>reinterpret_cast</FONT><FONT size=1><T**>(nextFree));
totalUsed ++;
</FONT><FONT color=#0000ff size=1>return</FONT><FONT size=1> p;
}
</FONT><FONT color=#0000ff size=1>else
</FONT><FONT size=1>
{
</FONT><FONT color=#008000 size=1>// We need to allocate another block
</FONT><FONT size=1>
assert(totalAllocated == totalUsed);
T * block = </FONT><FONT color=#0000ff size=1>reinterpret_cast</FONT><FONT size=1><T*>(</FONT><FONT color=#0000ff size=1>operator</FONT><FONT size=1> </FONT><FONT color=#0000ff size=1>new</FONT><FONT size=1> (</FONT><FONT color=#0000ff size=1>sizeof</FONT><FONT size=1>(T) * blockSize));
saveBlock(block);
totalAllocated += blockSize;
</FONT><FONT color=#008000 size=1>// Make the first sizeof(void*) bytes of each slot
</FONT><FONT size=1>
</FONT><FONT color=#008000 size=1>// represent a pointer which points to the next slot
</FONT><FONT size=1>
</FONT><FONT color=#0000ff size=1>for</FONT><FONT size=1> (size_t i = 0; i < blockSize -1; ++i)
{
*(</FONT><FONT color=#0000ff size=1>reinterpret_cast</FONT><FONT size=1><T**>(&block[i])) = &block[i+1];
}
*(</FONT><FONT color=#0000ff size=1>reinterpret_cast</FONT><FONT size=1><T**>(&block[blockSize-1])) = 0;
nextFree = blockSize >= 2 ? &block[1] : 0;
updateBlockSize();
totalUsed++;
</FONT><FONT color=#0000ff size=1>return</FONT><FONT size=1> block;
}
}
</FONT><FONT color=#0000ff size=1>void</FONT><FONT size=1> Free(T* p)
{
</FONT><FONT color=#008000 size=1>// Hook this element on to the front of the "free list"
</FONT><FONT size=1>
*(</FONT><FONT color=#0000ff size=1>reinterpret_cast</FONT><FONT size=1><T**>(p)) = nextFree;
nextFree = p;
totalUsed--;
}
</FONT><FONT color=#008000 size=1>/**
@return total number of used 'slots'.
*/
</FONT><FONT size=1>
size_t GetTotalUsed()
{
</FONT><FONT color=#0000ff size=1>return</FONT><FONT size=1> totalUsed;
}
</FONT><FONT color=#008000 size=1>/**
@return total number of allocated 'slots'.
*/
</FONT><FONT size=1>
size_t GetTotalAllocated()
{
</FONT><FONT color=#0000ff size=1>return</FONT><FONT size=1> totalAllocated;
}
</FONT><FONT color=#008000 size=1>/**
@return the overhead fraction.
*/
</FONT><FONT size=1>
</FONT><FONT color=#0000ff size=1>float</FONT><FONT size=1> GetOverhead()
{
</FONT><FONT color=#0000ff size=1>return</FONT><FONT size=1> 1.0f - </FONT><FONT color=#0000ff size=1>static_cast</FONT><FONT size=1><</FONT><FONT color=#0000ff size=1>float</FONT><FONT size=1>> (totalUsed) / totalAllocated;
}
BlockSizeBehaviour GetBlockSizeBehaviour()
{
</FONT><FONT color=#0000ff size=1>return</FONT><FONT size=1> behaviour;
}
</FONT><FONT color=#0000ff size=1>void</FONT><FONT size=1> SetBlockSizeBehaviour(BlockSizeBehaviour b)
{
behaviour = b;
}
size_t GetBlockSize()
{
</FONT><FONT color=#0000ff size=1>return</FONT><FONT size=1> blockSize;
}
</FONT><FONT color=#0000ff size=1>void</FONT><FONT size=1> SetBlockSize(size_t sz)
{
blockSize = sz;
}