/**
*
* \file Asura_Mempool.h
*
* Created by Kevin Lea - 12/09/2002 17:38:49
*
* Copyright (C) 2002 Rebellion, All Rights Reserved.
*
* \brief
*
**/
#ifdef ASURA_USE_PRAGMA_ONCE
	#pragma once
#endif

#ifndef __ASURA_MEMPOOL_H__
#define __ASURA_MEMPOOL_H__

#include "Debugging/Asura_Assert.h"

class Asura_Mempool
{
	friend class Asura_Mempool_ConstIterator;

	public:
		Asura_Mempool( int sizeOfElement, int numberOfElements )
		{
            Asura_Assert( sizeOfElement    > 0, "Invalid element size."  );
            Asura_Assert( numberOfElements > 0, "Invalid element count." );

            // The scheme of hiding the next free element ptr in the first
            // word of each element will break if they're too small.
            Asura_Assert( sizeOfElement >= static_cast<int>(sizeof(u_char*)), "Elements are too small." );

			Pool = new unsigned char[sizeOfElement*numberOfElements];

			#if _DEBUG
			AllocatedElement = new bool[numberOfElements];
			#endif 
		
			
			SizeOfElement = sizeOfElement;
			NumberOfElements = numberOfElements;


			Reset();
		}

		~Asura_Mempool(void)
		{
			#if _DEBUG
			delete [] AllocatedElement;
			#endif
			
			delete [] Pool;
		}

        bool DidAllocationSucceed( void ) const { return( NULL != Pool ); }

		void* Allocate(void)
		{
			if (NextFreeElement==NULL) return NULL;

			#if _DEBUG
			AllocatedElement[(NextFreeElement-Pool)/SizeOfElement] = true;
			#endif
			m_iNumAllocated++;

			void* p = (void*)NextFreeElement;

			NextFreeElement = *((unsigned char**)p);

			return p;
		}

		void Deallocate(void* p)
		{
			#if _DEBUG
			Asura_Assert( Pool <= p, "Pointer is off the front of the Mempool");
			Asura_Assert( p < (Pool + (SizeOfElement * NumberOfElements)), "Pointer is off the end of the Mempool");
			int elementIndex = static_cast<int>(((unsigned char*)p-Pool)/SizeOfElement);

			//Asura_Assert(elementIndex>=0 && elementIndex<NumberOfElements,"Whoa, invalid pointer");
			
			Asura_Assert(AllocatedElement[elementIndex]==true,"Deallocate called on element not allocated");
			
			AllocatedElement[elementIndex] = false;
			#endif

			m_iNumAllocated--;

			*((unsigned char**)(p)) = NextFreeElement;
			NextFreeElement = (unsigned char*)p;
		}

		void Reset(void)
		{
			NextFreeElement = Pool;
            if( !NextFreeElement ) { return; }

			for (int i=0; i<NumberOfElements-1; i++)
			{
				unsigned char* node = &Pool[i*SizeOfElement];
				unsigned char* nextNode = &Pool[(i+1)*SizeOfElement];

				*((unsigned char**)node) = nextNode;
			}

			*((unsigned char**)(&Pool[(NumberOfElements-1)*SizeOfElement])) = 0;

			#if _DEBUG
			for (int i=0; i<NumberOfElements; i++)
			{
				AllocatedElement[i] = false;
			}
			#endif

			m_iNumAllocated = 0;
		}

		int GetNumAllocated() const { return m_iNumAllocated; }

        // Returns whether this pool allocated this memory.
        bool AllocatedThisMemory( const void* const pMemory ) const
        {
//            const int iElementIndex = ( static_cast< const unsigned char* const >( pMemory ) - Pool ) / SizeOfElement;
//			return ( 0 <= iElementIndex && iElementIndex < NumberOfElements );
			const void* pPoolEnd = Pool + (SizeOfElement * NumberOfElements);
			return ( Pool <= pMemory && pMemory < pPoolEnd);
        }

	private:
		u_char* GetElementAddress(const int iElement) const
		{
			return(Pool + (iElement * SizeOfElement));
		}

		bool IsFree(const int iElement) const
		{
			const u_char*	pucElementAddr		= GetElementAddress(iElement);
			const u_char*	pucNextFreeElement	= NextFreeElement;

			while(pucNextFreeElement != NULL)
			{
				if(pucElementAddr == pucNextFreeElement)
				{
					return(true);
				}
				else
				{
					const u_char* const* ppucNextFreeElement = (const u_char* const*)(pucNextFreeElement);
					pucNextFreeElement = *ppucNextFreeElement;
				}
			}

			return(false);
		}

		unsigned char* Pool;
		unsigned char* NextFreeElement;
		
		int SizeOfElement;
		int NumberOfElements;
		int m_iNumAllocated;


		/// Kevin Lea - 10/06/2002 16:42:17 - debugging data, not required in release builds
		/// used for sanity checks e.g. asserting something isn't deallocated twice
		#if _DEBUG
		bool* AllocatedElement;
		#endif
};

class Asura_Mempool_ConstIterator
{
public:
	Asura_Mempool_ConstIterator(Asura_Mempool& xMempool)
	: m_xMempool(xMempool)
	{
		Begin();
	}

	void Begin(void)
	{
		m_iCurrentElement	= -1;
		Next();
	}

	bool Done(void) const
	{
		return(m_iCurrentElement == m_xMempool.NumberOfElements);
	}

	const u_char* GetCurrent(void) const
	{
		if(m_iCurrentElement < m_xMempool.NumberOfElements)
		{
			return(m_xMempool.GetElementAddress(m_iCurrentElement));
		}
		else
		{
			return(NULL);
		}
	}

	void Next(void)
	{
		while((++m_iCurrentElement < m_xMempool.NumberOfElements) && m_xMempool.IsFree(m_iCurrentElement)) {}
	}

private:
	Asura_Mempool&	m_xMempool;
	int				m_iCurrentElement;
};

class Asura_ResizingMempool_Node 
{
	friend class Asura_ResizingMempool;

	private:

		static Asura_ResizingMempool_Node* Create(u_int uNumberOfElementsPerPool, u_int uSizeOfElementInBytes, const char* szFile, int iLine);

		Asura_ResizingMempool_Node(u_int uNumberOfElementsPerPool, u_int uSizeOfElementInBytes)
		{
			m_uNumberOfAllocatedBlocks = 0;
			m_pucMemoryPool = 0;
			m_pxNextNode = 0;
			m_pucNextFreeElement = 0;
		}

		~Asura_ResizingMempool_Node()
		{
			delete [] m_pucMemoryPool;
			delete m_pxNextNode;
		}

	
		void* Allocate(void)
		{
			if (m_pucNextFreeElement==NULL) return NULL;

			void* p = (void*)m_pucNextFreeElement;

			m_pucNextFreeElement = *((unsigned char**)p);

			m_uNumberOfAllocatedBlocks++;

			return p;
		}


		void Deallocate(void* pElement) 
		{
			*((unsigned char**)(pElement)) = m_pucNextFreeElement;
			m_pucNextFreeElement = (unsigned char*)pElement;

			m_uNumberOfAllocatedBlocks--;
		}
	
		void Reset(u_int uNumberOfElementsPerPool, u_int uSizeOfElementInBytes)
		{
			m_pucNextFreeElement = m_pucMemoryPool;

			for (u_int i=0; i<uNumberOfElementsPerPool-1; i++)
			{
				unsigned char* node = &m_pucMemoryPool[i*uSizeOfElementInBytes];
				unsigned char* nextNode = &m_pucMemoryPool[(i+1)*uSizeOfElementInBytes];

				*((unsigned char**)node) = nextNode;
			}

			*((unsigned char**)(&m_pucMemoryPool[(uNumberOfElementsPerPool-1)*uSizeOfElementInBytes])) = 0;

		}


		unsigned char*					m_pucMemoryPool;
		unsigned char*					m_pucNextFreeElement;
		u_int							m_uNumberOfAllocatedBlocks;
		Asura_ResizingMempool_Node*		m_pxNextNode;
};

#include "Core/Asura_MemoryManagement_DebugOff.h"
inline Asura_ResizingMempool_Node* Asura_ResizingMempool_Node::Create(	u_int uNumberOfElementsPerPool, 
																  u_int uSizeOfElementInBytes, 
																  const char* szFile, 
																  int iLine)
{
#ifdef ASURA_MEMORYMANAGEMENT_ENABLED
	// fake the alloc record file and line
	Asura_ResizingMempool_Node* pxNode = new(szFile, iLine, ASURA_PLATFORM_MEMORYMANAGEMENT_GETRETURNADDR()) 
		Asura_ResizingMempool_Node(uNumberOfElementsPerPool,uSizeOfElementInBytes);
#else
	Asura_ResizingMempool_Node* pxNode = new Asura_ResizingMempool_Node(uNumberOfElementsPerPool,uSizeOfElementInBytes);
#endif

	if (pxNode == NULL)
	{
		return NULL;
	}

#ifdef ASURA_MEMORYMANAGEMENT_ENABLED
	// fake the alloc record file and line
	pxNode->m_pucMemoryPool = new(szFile, iLine, ASURA_PLATFORM_MEMORYMANAGEMENT_GETRETURNADDR()) 
		unsigned char[uNumberOfElementsPerPool*uSizeOfElementInBytes];
#else
	pxNode->m_pucMemoryPool = new unsigned char[uNumberOfElementsPerPool*uSizeOfElementInBytes];
#endif

	if (pxNode->m_pucMemoryPool == NULL)
	{
		delete pxNode;

		return NULL;
	}

	pxNode->Reset(uNumberOfElementsPerPool,uSizeOfElementInBytes);

	return pxNode;
}
#include "Core/Asura_MemoryManagement_DebugOn.h"

class Asura_ResizingMempool
{
	public:
		Asura_ResizingMempool(	u_int uNumberOfElementsPerPool, 
								u_int uSizeOfElementInBytes, 
								const char* szFile = NULL,
								const int iLine = 0 )
#ifdef ASURA_MEMORYMANAGEMENT_ENABLED
		: m_szFile(szFile ? szFile : __FILE__)
		, m_iLine(iLine ? iLine : __LINE__)
#endif
		{
#ifdef ASURA_MEMORYMANAGEMENT_ENABLED
			Asura_Assert(szFile, "debug info for mempool missing - add __FILE__ and __LINE__ to constructor params");
#endif
			m_pxHeadOfPoolList = NULL;

			m_uNumberOfElementsPerPool = uNumberOfElementsPerPool;
			m_uSizeOfElementInBytes = uSizeOfElementInBytes;
			
			Asura_Assert( (uNumberOfElementsPerPool * uSizeOfElementInBytes) < static_cast<u_int>(~0), "This is a very large memory pool.");
		}

		~Asura_ResizingMempool()
		{
			delete m_pxHeadOfPoolList;
		}

		void* Allocate(void)
		{
			/// Kevin Lea - 11/09/2002 12:28:52 - we have four possible situations
			//
			// 1) Nothing has been allocated before (m_pxHeadOfPoolList == NULL) and
			//    so we allocated a new pool and an element from that.
			//
			// 2) The pool pointed to by m_pxHeadOfPoolList has space and we allocate
			//    an element from that.
			//
			// 3) The pool pointed to by m_pxHeadOfPoolList has no space; we carry on
			//    down to the next pool looking for a free element to use.
			//
			// 4) We find we have no space at all, and so we allocate a new pool and 
			//    place it at the head of the list (which means next time we call this
			//    function we at least point to a pool with lots of free space).

			Asura_ResizingMempool_Node* pxNode = m_pxHeadOfPoolList;

			/// Kevin Lea - 11/09/2002 15:14:55 - check for cases 2) and 3)
			while(pxNode)
			{
				void* pMemory = pxNode->Allocate();

				/// Kevin Lea - 11/09/2002 15:12:39 - did we find a free element?
				if (pMemory)
				{
					return pMemory;
				}

				/// Kevin Lea - 11/09/2002 15:14:42 - try next pool then
				pxNode = pxNode->m_pxNextNode;
			}

			/// Kevin Lea - 11/09/2002 15:15:10 - okay then, new block it is
			if (AddANewPool())
			{
				return m_pxHeadOfPoolList->Allocate();
			}
			else /// Kevin Lea - 11/09/2002 12:44:53 - operation failed
			{
				return 0;
			}
		}

		void Deallocate(void *pElement)
		{
			Asura_ResizingMempool_Node* pxNode = m_pxHeadOfPoolList;
			Asura_ResizingMempool_Node** ppxPrevious = &m_pxHeadOfPoolList;

			u_int uPoolSize = m_uSizeOfElementInBytes*m_uNumberOfElementsPerPool;

			while(pxNode)
			{
				if ( (pElement >= pxNode->m_pucMemoryPool) && (pElement < (pxNode->m_pucMemoryPool + uPoolSize)) )
				{
					#if defined(_DEBUG) && defined(ASURA_ASSERT)
					
					int iElementIndex = static_cast<int>(((unsigned char*)pElement-pxNode->m_pucMemoryPool)/m_uSizeOfElementInBytes);
					Asura_Assert( (iElementIndex*m_uSizeOfElementInBytes + pxNode->m_pucMemoryPool) == ((unsigned char*)pElement),"Pointer not on element boundary!");

					#endif

					pxNode->Deallocate(pElement);
				
					if (pxNode->m_uNumberOfAllocatedBlocks == 0)
					{
						*ppxPrevious = pxNode->m_pxNextNode;
						
						pxNode->m_pxNextNode = NULL;
						
						delete pxNode;
					}
					return;
				}

				ppxPrevious = &(pxNode->m_pxNextNode);
				pxNode = pxNode->m_pxNextNode;
			}

			Asura_Assert(false,"Element not found in memory pool!");
		}

		void Reset(void)
		{
			if(!m_pxHeadOfPoolList) return;

			/// Richard May - 30/04/2004 12:59:41 - Resetting a non-empty pool is now illegal. It's the users
			/// responsibilty to clear up their allocations rather than relying on the pool to do it for them
			Asura_Assert( !m_pxHeadOfPoolList->m_uNumberOfAllocatedBlocks, "Resetting a non-empty pool! Must clear up allocations before reset!" );
			if( m_pxHeadOfPoolList->m_uNumberOfAllocatedBlocks ) return;

			delete m_pxHeadOfPoolList;
			m_pxHeadOfPoolList = 0;
		}

		// KJFL - 24 January 2007 - a "force deallocate" method like the original Reset() used to be. 
		// This will delete all memory allocated by the pool in a rapid manner, but remember any pointers 
		// returned by the pool will now be invalid. So, only use if you really know what you're doing.
		// (If you know you want to wipe the slate clean, zeroing any pointers/lists you may have and
		// calling this method is obviously a lot faster than going through all your pointers/lists and 
		// calling deallocate per element.)
		void ForceReset( void )
		{
			if (m_pxHeadOfPoolList)
			{
				// each node automatically deletes the next one, no need to recurse ourselves
				delete m_pxHeadOfPoolList;
				m_pxHeadOfPoolList = 0;
			}
		}

        bool IsEmpty( void ) const
        {
            return( NULL == m_pxHeadOfPoolList );
        }

        // Returns whether this pool allocated this memory.
        bool AllocatedThisMemory( const void* const pMemory ) const
        {
            const u_int uPoolSize = m_uSizeOfElementInBytes * m_uNumberOfElementsPerPool;

            Asura_ResizingMempool_Node* pxNode = m_pxHeadOfPoolList;
            while ( pxNode )
            {
                if ( ( pxNode->m_pucMemoryPool <= pMemory ) && ( pMemory < ( pxNode->m_pucMemoryPool + uPoolSize ) ) )
                {
					const u_int uElementIndex = static_cast< u_int>(( static_cast< const unsigned char* const >( pMemory ) - pxNode->m_pucMemoryPool ) / m_uSizeOfElementInBytes);
					return ( uElementIndex < m_uNumberOfElementsPerPool );
                }

                pxNode = pxNode->m_pxNextNode;
            }

            return false;
        }

	u_int GetSizeOfElement() const {return m_uSizeOfElementInBytes;}

	private:
		
		bool AddANewPool()
		{
#ifdef ASURA_MEMORYMANAGEMENT_ENABLED
			Asura_ResizingMempool_Node* pxNode = Asura_ResizingMempool_Node::Create(m_uNumberOfElementsPerPool, m_uSizeOfElementInBytes, m_szFile, m_iLine);
#else
			Asura_ResizingMempool_Node* pxNode = Asura_ResizingMempool_Node::Create(m_uNumberOfElementsPerPool, m_uSizeOfElementInBytes, NULL, 0);
#endif

			if (pxNode == NULL)
			{
				/// Kevin Lea - 11/09/2002 12:41:55 - uh-oh, we're out of memory
				Asura_Assert(false, "Out of memory!");

				return false;
			}
			
			/// Kevin Lea - 11/09/2002 12:43:50 - pop the new pool onto the head of the list
			pxNode->m_pxNextNode = m_pxHeadOfPoolList;
			m_pxHeadOfPoolList = pxNode;

			return true;
		}

		Asura_ResizingMempool_Node*	m_pxHeadOfPoolList;

		u_int						m_uNumberOfElementsPerPool;
		u_int						m_uSizeOfElementInBytes;

#ifdef ASURA_MEMORYMANAGEMENT_ENABLED
		const char* 				m_szFile;
		const int					m_iLine;
#endif
};

#include "Asura_Handle.h"

template <class T> class Asura_TrackingHandlePool_Node
{
	public:

		static Asura_TrackingHandlePool_Node<T>* Create(u_int uNumberOfElementsPerPool, int iStartHandle)
		{
			Asura_TrackingHandlePool_Node<T>* pxNode = new Asura_TrackingHandlePool_Node<T>;

			if (pxNode == NULL)
			{
				return NULL;
			}

			pxNode->m_pxElementPool = new T[uNumberOfElementsPerPool];
			pxNode->m_pxHandleList = new Asura_Tracking_Handle_List(uNumberOfElementsPerPool);

			if (pxNode->m_pxElementPool == NULL || pxNode->m_pxHandleList == NULL)
			{
				delete pxNode;

				return NULL;
			}

			pxNode->m_iLowestHandle  = iStartHandle;

			return pxNode;
		}

		Asura_TrackingHandlePool_Node<T>()
		{
			m_pxElementPool = NULL;
			m_pxHandleList = NULL;
			m_pxNextNode = NULL;
		}

		~Asura_TrackingHandlePool_Node()
		{
			delete [] m_pxElementPool;
			delete m_pxHandleList;
			delete m_pxNextNode;
		}

		Asura_Handle Allocate(void)
		{
			Asura_Handle iHandle = ASURA_INVALID_HANDLE;
			
			if(m_pxHandleList->GetNewHandle(iHandle))
			{
				iHandle += m_iLowestHandle;
			}
		
			return iHandle;
		}

		void Deallocate(Asura_Handle iHandle)
		{
			m_pxHandleList->ReleaseHandle(iHandle - m_iLowestHandle);
		}

		T* GetPointer(Asura_Handle iHandle)
		{
            iHandle -= m_iLowestHandle;
            Asura_Assert( m_pxHandleList->IsValidHandle(iHandle), "Bad handle in tracking handle pool!");

            return( m_pxHandleList->IsActiveHandle(iHandle) ? &m_pxElementPool[iHandle] : NULL );
		}

		void Traverse(void(*pfnCallback)(T* pxElement))
		{
			Asura_Tracking_Handle_List::Iterator xTraversePosition = m_pxHandleList->GetIterator();
			xTraversePosition.Begin();

            while (!xTraversePosition.End())
            {
                pfnCallback( &m_pxElementPool[xTraversePosition.GetCurrentHandle()] );
                xTraversePosition.Next();
            }
		}

		void Traverse(void(*pfnCallback)(T* pxElement, void* pData), void* pData)
		{
			Asura_Tracking_Handle_List::Iterator xTraversePosition = m_pxHandleList->GetIterator();
			xTraversePosition.Begin();

            while (!xTraversePosition.End())
            {
                pfnCallback( &m_pxElementPool[xTraversePosition.GetCurrentHandle()], pData);
                xTraversePosition.Next();
            }
		}


		T*									m_pxElementPool;
		Asura_Tracking_Handle_List*			m_pxHandleList;
		int									m_iLowestHandle;

		Asura_TrackingHandlePool_Node<T>*	m_pxNextNode;
};


template <class T> class Asura_TrackingHandlePool;

template <class T> class Asura_TrackingHandlePool_Iterator
{
	public:
		Asura_TrackingHandlePool_Iterator<T>(void)
		{
			m_pxObjectToIterate = NULL;
			m_pxCurrentNode		= NULL;
			m_iCurrentHandle	= ASURA_INVALID_HANDLE;
		}

		Asura_TrackingHandlePool_Iterator<T>(Asura_TrackingHandlePool<T>* pxObjectToIterate)
		{
			m_pxObjectToIterate = pxObjectToIterate;
			m_pxCurrentNode		= m_pxObjectToIterate->m_pxHeadOfPoolList;
			m_iCurrentHandle	= ASURA_INVALID_HANDLE;
		}

		Asura_TrackingHandlePool_Iterator<T>(const Asura_TrackingHandlePool_Iterator<T>& xFrom)
		{
			m_pxObjectToIterate = xFrom.m_pxObjectToIterate;
			m_pxCurrentNode		= xFrom.m_pxCurrentNode;
			m_iCurrentHandle	= xFrom.m_iCurrentHandle;
		}

		inline void Begin(void)
		{
			m_pxCurrentNode = NULL;
			m_pxCurrentPointer = NULL;
			if(!m_pxObjectToIterate->m_pxHeadOfPoolList)
			{
				return;
			}
			m_pxCurrentNode = m_pxObjectToIterate->m_pxHeadOfPoolList;
            // Check through all nodes - some that have been deallocated may occur before those with
            // viable data members
            while(m_pxCurrentNode)
            {
			    m_xHandleListIterator  = m_pxCurrentNode->m_pxHandleList->GetIterator();
			    m_xHandleListIterator.Begin();
                if(!m_xHandleListIterator.End())
                {
			        m_iCurrentHandle = m_xHandleListIterator.GetCurrentHandle();
                    m_pxCurrentPointer = &(m_pxCurrentNode->m_pxElementPool[m_iCurrentHandle]);
                    return;                    
                }
                else
                {
                    m_pxCurrentNode = m_pxCurrentNode->m_pxNextNode;
                }
            }
		}

		inline bool End( void ) const
		{
			return (m_pxCurrentNode == NULL || m_xHandleListIterator.End());
		}

		inline void Next(void)
		{
			m_xHandleListIterator.Next();
			while (m_xHandleListIterator.End())
			{
				m_pxCurrentNode = m_pxCurrentNode->m_pxNextNode;
				if(!m_pxCurrentNode)
				{
					return;
				}

				m_xHandleListIterator = m_pxCurrentNode->m_pxHandleList->GetIterator();
				m_xHandleListIterator.Begin();
			}
			
			m_iCurrentHandle = m_xHandleListIterator.GetCurrentHandle();
            m_pxCurrentPointer = &(m_pxCurrentNode->m_pxElementPool[m_iCurrentHandle]);			
		}

		inline Asura_Handle GetCurrentHandle(void) const
		{
			return m_iCurrentHandle + m_pxCurrentNode->m_iLowestHandle;
		}

        inline T* GetCurrentPointer( void ) const
        {
            return m_pxCurrentPointer;
        }

        // Alternative method names for compatibility with other iterators.
        inline bool Done( void ) const { return End(); }
        inline T* GetCurrent( void ) const { return GetCurrentPointer(); }
        inline void Restart( void ) { Begin(); }

	private:
		Asura_TrackingHandlePool<T>*			m_pxObjectToIterate;
		Asura_TrackingHandlePool_Node<T>*		m_pxCurrentNode;
		Asura_Tracking_Handle_List::Iterator	m_xHandleListIterator;
		Asura_Handle							m_iCurrentHandle;
        T*                                      m_pxCurrentPointer;		
};

template <class T> class Asura_TrackingHandlePool
{
	friend  class Asura_TrackingHandlePool_Iterator<T>;
	public:	
		typedef Asura_TrackingHandlePool_Iterator<T> Iterator;

		Asura_TrackingHandlePool<T>( u_int uNumberOfElementsPerPool, int iStartHandle = 0 )
		{
			m_pxHeadOfPoolList = NULL;
			m_uNumberOfElementsPerPool = uNumberOfElementsPerPool;

			m_iHandleOfLastUsedElement = ASURA_INVALID_HANDLE;
			/// Kevin Lea - 27/01/2003 11:56:38 - no need to set m_pxLastUsedElement
			/// since we check against handle only

			m_iStartHandle = iStartHandle;
		}

		~Asura_TrackingHandlePool<T>()
		{
			delete m_pxHeadOfPoolList;
		}

		Asura_TrackingHandlePool_Iterator<T> GetIterator(void)
		{
			return Asura_TrackingHandlePool_Iterator<T>(this);
		}

        void Reset()
        {
            delete m_pxHeadOfPoolList;
            m_pxHeadOfPoolList = NULL;

			m_iHandleOfLastUsedElement = ASURA_INVALID_HANDLE;
			/// Kevin Lea - 27/01/2003 11:56:38 - no need to set m_pxLastUsedElement
			/// since we check against handle only
	    }

		Asura_Handle Allocate(void)
		{
			Asura_TrackingHandlePool_Node<T>* pxNode = m_pxHeadOfPoolList;

			/// Kevin Lea - 11/09/2002 15:14:55 - check for cases 2) and 3)
			while(pxNode)
			{
				const Asura_Handle iHandle = pxNode->Allocate();

				/// Kevin Lea - 11/09/2002 15:12:39 - did we find a free element?
				if (iHandle!=ASURA_INVALID_HANDLE)
				{
					return iHandle;
				}

				/// Kevin Lea - 11/09/2002 15:14:42 - try next pool then
				pxNode = pxNode->m_pxNextNode;
			}

			/// Kevin Lea - 11/09/2002 15:15:10 - okay then, new block it is
			if (AddANewPool())
			{
				return m_pxHeadOfPoolList->Allocate();
			}
			else /// Kevin Lea - 11/09/2002 12:44:53 - operation failed
			{
				return ASURA_INVALID_HANDLE;
			}
		}

		void Deallocate(const Asura_Handle iHandle)
		{
			if (iHandle == ASURA_INVALID_HANDLE)
			{
				Asura_Assert( false, "Invalid handle" );
				return;
			}
			else if (iHandle == m_iHandleOfLastUsedElement)
			{
				/// Kevin Lea - 27/01/2003 11:48:50 - invalid cache; no need to
				/// set the last used pointer since we check against handle
				m_iHandleOfLastUsedElement = ASURA_INVALID_HANDLE;

			}
			
			Asura_TrackingHandlePool_Node<T>* pxNode = FindNodeWithHandle( iHandle );
			if( pxNode )
			{
				pxNode->Deallocate(iHandle);
			}
            else
            {
			    Asura_Assert( false, "Handle does not correspond to any in list" );
            }
		}

		T* GetPointer(const Asura_Handle iHandle) 
		{
			if (iHandle == ASURA_INVALID_HANDLE)
			{
				Asura_Assert( false, "Invalid handle" );
				return NULL;
			}
			else if (iHandle == m_iHandleOfLastUsedElement)
			{
				/// Kevin Lea - 27/01/2003 11:54:16 - good, the element is in the cache
				return m_pxLastUsedElement;
			}
			
			Asura_TrackingHandlePool_Node<T>* pxNode = FindNodeWithHandle( iHandle );
			if(pxNode)
			{
				T* pxElement = pxNode->GetPointer( iHandle );
                if( pxElement )
                {
				    /// Kevin Lea - 27/01/2003 11:52:44 - cache result for later calls
				    m_iHandleOfLastUsedElement = iHandle;
				    m_pxLastUsedElement = pxElement;

				    return pxElement;
                }
			}
            else
            {
    			Asura_Assert( false, "Handle does not correspond to any in list" );
            }

			return NULL;
		}

		void Traverse(void(*pfnCallback)(T* pxElement))
		{
			Asura_TrackingHandlePool_Node<T>* pxNode = m_pxHeadOfPoolList;

			while(pxNode)
			{
				pxNode->Traverse(pfnCallback);

				pxNode = pxNode->m_pxNextNode;
			}
		}

		void Traverse(void(*pfnCallback)(T* pxElement, void* pData), void* pData)
		{
			Asura_TrackingHandlePool_Node<T>* pxNode = m_pxHeadOfPoolList;

			while(pxNode)
			{
				pxNode->Traverse(pfnCallback, pData);

				pxNode = pxNode->m_pxNextNode;
			}
		}

		bool ContainsHandle( int iHandle )
		{
			Asura_TrackingHandlePool_Node<T>* pxNode = FindNodeWithHandle( iHandle );
			return (pxNode != NULL);
		}

	private:

		bool AddANewPool(void)
		{
	
			int iLowestHandle = m_iStartHandle;
	
			Asura_TrackingHandlePool_Node<T>* pxNode = m_pxHeadOfPoolList;
	
			while(pxNode)
			{
				if (pxNode->m_iLowestHandle == iLowestHandle)
				{
					iLowestHandle += m_uNumberOfElementsPerPool;
					pxNode = m_pxHeadOfPoolList;
				}
				else
				{
					pxNode = pxNode->m_pxNextNode;
				}
			}
		
		

			pxNode = Asura_TrackingHandlePool_Node<T>::Create(m_uNumberOfElementsPerPool, iLowestHandle);

			if (pxNode == NULL)
			{
				/// Kevin Lea - 11/09/2002 12:41:55 - uh-oh, we're out of memory
				Asura_Assert(false, "Out of memory!");

				return false;
			}
			
			/// Kevin Lea - 11/09/2002 12:43:50 - pop the new pool onto the head of the list
			pxNode->m_pxNextNode = m_pxHeadOfPoolList;
			m_pxHeadOfPoolList = pxNode;

			return true;
		}

		inline Asura_TrackingHandlePool_Node<T>* FindNodeWithHandle(const Asura_Handle iHandle) const
		{
			// NRM - find the node that contains the handle passed in
			Asura_TrackingHandlePool_Node<T>* pxNode = m_pxHeadOfPoolList;
			while(pxNode)
			{
				if ( (pxNode->m_iLowestHandle <= iHandle) && (iHandle < pxNode->m_iLowestHandle + (int)m_uNumberOfElementsPerPool) )
				{
					return pxNode;
				}
				pxNode = pxNode->m_pxNextNode;
			}
			return NULL;
		}

		Asura_TrackingHandlePool_Node<T>*	m_pxHeadOfPoolList;
//		Asura_TrackingHandlePool_Node<T>*	m_pxTailOfPoolList;
		u_int								m_uNumberOfElementsPerPool;
		
		T*									m_pxLastUsedElement;
		Asura_Handle						m_iHandleOfLastUsedElement;

		int									m_iStartHandle;
};

#endif//__ASURA_MEMPOOL_H__
