Initial version, contains TPrivateHeap and TObjectPool
///
///
/// \section license License Stuff
///
/// This library is free software; you can redistribute it and/or
/// modify it under the terms of the GNU Lesser General Public
/// License as published by the Free Software Foundation; either
/// version 2.1 of the License, or (at your option) any later version.
///
/// This library is distributed in the hope that it will be useful,
/// but WITHOUT ANY WARRANTY; without even the implied warranty of
/// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
/// Lesser General Public License for more details.
///
/// You should have received a copy of the GNU Lesser General Public
/// License along with this library; if not, write to the Free Software
/// Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA
///
/// \section Introduction
///
/// This module includes a few classes to manage memory:
/// \link Memory::TPrivateHeap TPrivateHeap \endlink and
/// \link Memory::TObjectPool TObjectPool \endlink.
/// They attempt to limit heap fragmentation by pre-allocating pages of
/// bytes and managing the memory underneath.
/// This class allocates objects of type T in a private heap to avoid heap
/// fragmentation. The private heap only grows, it never shrinks until
/// the allocator is destroyed. The private heap only holds objects of
/// type T. Some optimal number for N (the size of a heap "page")
/// should be chosen to strike a balance between an oversized heap and
/// a heap that must allocate pages frequently.
///
/// This class saves time by pre-allocating the raw memory for objects of
/// type T and then tracking available "slots" in this memory for new objects.
/// It is effective for holding objects which don't allocate heap memory
/// themselves.
///
/// Users call Alloc() to get a pointer to the raw memory for an object of
/// type T. Users must then call placement new on this address to initialize
/// the object. When the object is no longer needed, users must explicitly
/// call the destructor and then call Free() to mark the memory as free to
/// use again by the PrivateHeap.
///
/// Upon construction, this object allocates one "page" worth of raw bytes,
/// which is N * sizeof(T) bytes. The raw pointer to this "page" is stored
/// internally so that it can be deallocated upon destruction of the heap.
///
/// Each page is broken up into pointers to T objects, and each pointer is
/// stored in the heap as a deque, which will initially contains N pointers
/// to objects of type T. The allocator internally keeps track of where the
/// next available (free) pointer is in the heap. Upon construction of the
/// heap, the "next free pointer" is set to the top of the 1st page.
///
/// When alloc is called, if we're not at the bottom of the heap, then return
/// the next free pointer in the deque and bumps down to the next free pointer
/// on the heap. If we ARE at the end of the heap, then the heap allocates
/// another page of bytes, stores the raw pointer to the next page internally
/// and returns the first pointer in the new page.
///
/// When free is called, if the next free pointer is not at the beginning
/// of the heap, then the next free pointer is bumped up the heap and the
/// deleted pointer value overwrites the existing value at that position in the
/// heap. If the next free pointer is at the top of the heap (i.e. first
/// pointer in the first page), then NOTHING HAPPENS. Eventually, support
/// for a PrivateHeapEmptyException being thrown may be added to this method.
///
/// Upon destruction of the allocator, all pages of bytes are deleted. This
/// means that if the heap is destroyed there are no resource leaks from the
/// objects created from this heap. You must be careful to only destroy the
/// private heap once all objects that have pointers into it are also
/// destroyed.
template<
// type of items to be stored in the heap
typename T,
// number of pointers to store in each "page" of memory
unsigned int N = 100
>
class TPrivateHeap {
protected:
class PrivateHeapEmptyException {};
typedef unsigned char Byte;
// This vector holds the pointers to the tops of each memory "page"
std::vector m_vRawBytes;
// This deque holds the pointers to all the objects of type T
std::deque m_Heap; // deque where front/begin is where we start
// and if we reach end(), we have to allocate
// more pages to the end
// This iterator tracks the next free object pointer
typename std::deque::iterator m_sNextFreePtr;
// -------------------------------------------------------------------
// -------------------------------------------------------------------
void allocate_page(unsigned int num_pages = 1)
{
Byte* ptrPage = 0;
T* ptrNode = 0;
// ---------------------------------------------------------------
// ---------------------------------------------------------------
for(unsigned int page = 0; page < num_pages; ++page) {
// allocate the raw bytes
ptrPage = new Byte[ sizeof(T) * N ];
m_vRawBytes.push_back(ptrPage);
// -----------------------------------------------------------
// now save the node pointers to the bottom of the deque
// -----------------------------------------------------------
for(int node = 0; node < N; ++node) {
ptrNode = (T*)(ptrPage + (node * sizeof(T)));
m_Heap.push_back(ptrNode);
}
// -----------------------------------------------------------
}
// ---------------------------------------------------------------
}
// -------------------------------------------------------------------
// void log_private_heap();
public:
// -------------------------------------------------------------------
/// This constructs a private heap with (initially) one page of memory
/// allocated.
TPrivateHeap()
{
allocate_page();
m_sNextFreePtr = m_Heap.begin();
// log_private_heap();
}
// -------------------------------------------------------------------
// -------------------------------------------------------------------
/// WARNING! Before deleting, this destructor checks that the
/// next free pointer is at the top of the heap (in other words, that
/// all objects "allocated" and then constructed in this heap were then
/// destructed and then "freed" prior to the heap destructor being called).
///
/// In other words, if a resource leak is detected in the heap, a
/// debug assertion is tripped.
~TPrivateHeap()
{
assert(m_sNextFreePtr == m_Heap.begin() &&
"Error! Private heap is being destroyed but objects were not \
correctly destroyed and freed");
// delete all the raw bytes...
for(std::vector::iterator pit = m_vRawBytes.begin(); pit != m_vRawBytes.end(); ++pit) {
if(NULL != *pit) {
delete[] *pit;
*pit = 0;
}
}
m_vRawBytes.clear();
}
// -------------------------------------------------------------------
// -------------------------------------------------------------------
/// Allocates the next available T object in the heap and returns a pointer
/// to this uninitialized object. WARNING! You must still run a constructor
/// on the pointer to initialize your object.
///
/// Note: This method will cause a new page to be allocated in the heap
/// if the returned pointer was at the bottom of the last page.
T* Alloc()
{
T* ptrNode = *m_sNextFreePtr;
++m_sNextFreePtr;
// if m_sNextFreePtr now points past the bottom of the deque,
// allocate a new page and re-position the deque iterator (marker)
if(m_Heap.end() == m_sNextFreePtr) {
// back up our deque marker by one, temporarily
--m_sNextFreePtr;
// allocate a new page to the end of our deque
allocate_page();
// reposition the stack marker on the newly available pointer
++m_sNextFreePtr;
}
// log_private_heap();
return ptrNode;
}
// -------------------------------------------------------------------
// -------------------------------------------------------------------
/// De-allocates the object T that pointer pn points to and frees space
/// in the heap. WARNING! You should always explicitly run the destructor
/// on the object prior to calling Free().
///
/// TO DO: Need to put in debug assertions about the pointer to be freed and
/// ensure that it is within the proper range (I'm thinking store top and
/// bottom addresses of the heap to make this check as quick as possible).
///
/// WARNING! Never Free an object that was not allocated from this Heap. This
/// is the equivalent of deleting a pointer that was allocated using malloc and
/// could produce disastrous results.
///
/// WARNING! Never Free the same object twice!!! This is the equivalent of
/// deleting a pointer twice. The safest thing to do after Freeing a pointer
/// is to NULL that pointer.
void Free(T* pn)
{
// the returned pointer goes back in our deque at the point one
// above the deque pointer (unless we're at the beginning of the deque)
if(m_Heap.begin() == m_sNextFreePtr) {
// throw 1;
}
else {
--m_sNextFreePtr;
*m_sNextFreePtr = pn;
}
// log_private_heap();
}
// -------------------------------------------------------------------
// I DON'T THINK "Clear" IS A GOOD METHOD. THE ONLY PROPER WAY TO CLEAN
// UP ALL SPACE IN THE HEAP IS TO DESTROY EACH OBJECT IN THE HEAP AND
// THEN FREE THE MEMORY. THIS METHOD IS VERY PRONE TO RESOURCE LEAKS
// FOR ANYTHING EXCEPT OBJECTS THAT DON'T ALLOCATE HEAP MEMORY.
/*
// -------------------------------------------------------------------
// frees all space in the heap
// -------------------------------------------------------------------
void Clear()
{
std::deque::iterator pit = m_Heap.begin();
for(std::vector::iterator bit = m_vRawBytes.begin();
bit != m_vRawBytes.end(); ++bit) {
// for each page of bytes, re-assign the heap's pointers
Byte* ptrPage = *bit;
for(int ptrNum = 0; ptrNum < N; ++ptrNum) {
*pit = (T*)(ptrPage + (ptrNum * sizeof(T)));
++pit;
}
}
m_sNextFreePtr = m_Heap.begin();
}
// -------------------------------------------------------------------
*/
}; // end template class TPrivateHeap
// -------------------------------------------------------------------
/// This class uses the lower-level TPrivateHeap to allocate the memory
/// for objects of type T and default constructs them before returning
/// the pointer to the caller in New(). The Delete() calls the destructor
/// and then frees the memory in the private heap.
///
/// It is essentially a wrapper around TPrivateHeap that ensure the
/// default constructor and destructor are called during alloc and free
/// operations. If you need to call a different (non-default) constructor
/// on your created objects or do not want to call constructors on your
/// your objects, use TPrivateHeap directly.
template<
// type of objects to be stored in the private heap
typename T,
// number of objects to store in each "page" of memory
unsigned int N = 100
>
class TObjectPool
{
private:
TPrivateHeap m_heap;
public:
/// This method allocates memory on the private heap and
/// calls placement new on the memory (invoking the default
/// constructor)
T* New()
{
// get the pointer and run placement new constructor on it
return new (m_heap.Alloc()) T;
}
/// This method calls the destructor on the object and then
/// frees the memory on the private heap. If this method is
/// called with a NULL pointer, no operation is performed.
void Delete(T* pObj)
{
if(pObj) {
// explicitly call the destructor
pObj->~T();
// free the memory in the private heap
m_heap.Free(pObj);
}
}
};
}; // namespace Memory
#endif // __LD_MEMORY_H