text: #ifndef __MEMORY_POOL_H
  #define __MEMORY_POOL_H
  
  #ifndef __APPLE__
  // Use stdlib and not malloc for compatibility
  #include <stdlib.h>
  #endif
  #include <assert.h>
  
  // DS_MEMORY_POOL_MAX_FREE_PAGES must be > 1
  #define DS_MEMORY_POOL_MAX_FREE_PAGES 4
  
  // #define _DISABLE_MEMORY_POOL
  
  namespace DataStructures
  {
  	/// Very fast memory pool for allocating and deallocating structures that don't have constructors or destructors.
  	/// Contains a list of pages, each of which has an array of the user structures
  	template <class MemoryBlockType>
  	class MemoryPool
  	{
  	public:
  		struct Page;
  		struct MemoryWithPage
  		{
  			MemoryBlockType userMemory;
  			Page *parentPage;
  		};
  
  		struct Page
  		{
  			MemoryWithPage** availableStack;
  			int availableStackSize;
  			MemoryWithPage* block;
  			Page *next, *prev;
  		};
  
  		MemoryPool();
  		~MemoryPool();
  		void SetPageSize(int size); // Defaults to 16384
  		MemoryBlockType *Allocate(void);
  		void Release(MemoryBlockType *m);
  		void Clear(void);
  	protected:
  		int BlocksPerPage(void) const;
  		void AllocateFirst(void);
  		bool InitPage(Page *page, Page *prev);
  
  		// availablePages contains pages which have room to give the user new blocks.  We return these blocks from the head of the list
  		// unavailablePages are pages which are totally full, and from which we do not return new blocks.
  		// Pages move from the head of unavailablePages to the tail of availablePages, and from the head of availablePages to the tail of unavailablePages
  		Page *availablePages, *unavailablePages;
  		int availablePagesSize, unavailablePagesSize;
  		int memoryPoolPageSize;
  	};
  
  	template<class MemoryBlockType>
  	MemoryPool<MemoryBlockType>::MemoryPool()
  	{
  #ifndef _DISABLE_MEMORY_POOL
  		//AllocateFirst();
  		availablePagesSize=0;
  		unavailablePagesSize=0;
  		memoryPoolPageSize=16384;
  #endif
  	}
  	template<class MemoryBlockType>
  	MemoryPool<MemoryBlockType>::~MemoryPool()
  	{
  #ifndef _DISABLE_MEMORY_POOL
  		Clear();
  #endif
  	}
  
  	template<class MemoryBlockType>
  	void MemoryPool<MemoryBlockType>::SetPageSize(int size)
  	{
  		memoryPoolPageSize=size;
  	}
  
  	template<class MemoryBlockType>
  	MemoryBlockType* MemoryPool<MemoryBlockType>::Allocate(void)
  	{
  #ifdef _DISABLE_MEMORY_POOL
  		return new MemoryBlockType;
  #endif
  
  		if (availablePagesSize>0)
  		{
  			MemoryBlockType *retVal;
  			Page *curPage;
  			curPage=availablePages;
  			retVal = (MemoryBlockType*) curPage->availableStack[--(curPage->availableStackSize)];
  			if (curPage->availableStackSize==0)
  			{
  				--availablePagesSize;
  				availablePages=curPage->next;
  				assert(availablePagesSize==0 || availablePages->availableStackSize>0);
  				curPage->next->prev=curPage->prev;
  				curPage->prev->next=curPage->next;
  
  				if (unavailablePagesSize++==0)
  				{
  					unavailablePages=curPage;
  					curPage->next=curPage;
  					curPage->prev=curPage;	
  				}
  				else
  				{
  					curPage->next=unavailablePages;
  					curPage->prev=unavailablePages->prev;
  					unavailablePages->prev->next=curPage;
  					unavailablePages->prev=curPage;
  				}			
  			}
  
  			assert(availablePagesSize==0 || availablePages->availableStackSize>0);
  			return retVal;
  		}
  
  		availablePages = (Page *) malloc(sizeof(Page));
  		if (availablePages==0)
  			return 0;
  		availablePagesSize=1;
  		if (InitPage(availablePages, availablePages)==false)
  			return 0;
  		assert(availablePages->availableStackSize>1);
  		return (MemoryBlockType *) availablePages->availableStack[--availablePages->availableStackSize];
  	}
  	template<class MemoryBlockType>
  	void MemoryPool<MemoryBlockType>::Release(MemoryBlockType *m)
  	{
  #ifdef _DISABLE_MEMORY_POOL
  		delete m;
  		return;
  #endif
  
  		// Find the page this block is in and return it.
  		Page *curPage;
  		MemoryWithPage *memoryWithPage = (MemoryWithPage*)m;
  		curPage=memoryWithPage->parentPage;
  
  		if (curPage->availableStackSize==0)
  		{
  			// The page is in the unavailable list so move it to the available list
  			curPage->availableStack[curPage->availableStackSize++]=memoryWithPage;
  			unavailablePagesSize--;
  
  			// As this page is no longer totally empty, move it to the end of available pages
  			curPage->next->prev=curPage->prev;
  			curPage->prev->next=curPage->next;
  			
  			if (unavailablePagesSize>0 && curPage==unavailablePages)
  				unavailablePages=unavailablePages->next;
  			
  			if (availablePagesSize++==0)
  			{
  				availablePages=curPage;
  				curPage->next=curPage;
  				curPage->prev=curPage;
  			}
  			else
  			{
  				curPage->next=availablePages;
  				curPage->prev=availablePages->prev;
  				availablePages->prev->next=curPage;
  				availablePages->prev=curPage;	
  			}
  		}
  		else
  		{
  			curPage->availableStack[curPage->availableStackSize++]=memoryWithPage;
  
  			if (curPage->availableStackSize==BlocksPerPage() &&
  				availablePagesSize>=DS_MEMORY_POOL_MAX_FREE_PAGES)
  			{
  				// After a certain point, just deallocate empty pages rather than keep them around
  				if (curPage==availablePages)
  				{
  					availablePages=curPage->next;
  					assert(availablePages->availableStackSize>0);
  				}
  				curPage->prev->next=curPage->next;
  				curPage->next->prev=curPage->prev;
  				availablePagesSize--;
  				free(curPage->availableStack);
  				free(curPage->block);
  				free(curPage);
  			}
  		}
  	}
  	template<class MemoryBlockType>
  	void MemoryPool<MemoryBlockType>::Clear(void)
  	{
  #ifdef _DISABLE_MEMORY_POOL
  		return;
  #endif
  		Page *cur, *freed;
  
  		if (availablePagesSize>0)
  		{
  			cur = availablePages;
  #ifdef _MSC_VER
  #pragma warning(disable:4127)   // conditional expression is constant
  #endif
  			while (true) 
  			// do
  			{
  				free(cur->availableStack);
  				free(cur->block);
  				freed=cur;
  				cur=cur->next;
  				if (cur==availablePages)
  				{
  					free(freed);
  					break;
  				}
  				free(freed);
  			}// while(cur!=availablePages);
  		}
  		
  		if (unavailablePagesSize>0)
  		{
  			cur = unavailablePages;
  			while (1)
  			//do 
  			{
  				free(cur->availableStack);
  				free(cur->block);
  				freed=cur;
  				cur=cur->next;
  				if (cur==unavailablePages)
  				{
  					free(freed);
  					break;
  				}
  				free(freed);
  			} // while(cur!=unavailablePages);
  		}
  
  		availablePagesSize=0;
  		unavailablePagesSize=0;
  	}
  	template<class MemoryBlockType>
  	int MemoryPool<MemoryBlockType>::BlocksPerPage(void) const
  	{
  		return memoryPoolPageSize / sizeof(MemoryWithPage);
  	}
  	template<class MemoryBlockType>
  	bool MemoryPool<MemoryBlockType>::InitPage(Page *page, Page *prev)
  	{
  		int i=0;
  		const int bpp = BlocksPerPage();
  		page->block=(MemoryWithPage*) malloc(memoryPoolPageSize);
  		if (page->block==0)
  			return false;
  		page->availableStack=(MemoryWithPage**)malloc(sizeof(MemoryWithPage*)*bpp);
  		if (page->availableStack==0)
  		{
  			free(page->block);
  			return false;
  		}
  		MemoryWithPage *curBlock = page->block;
  		MemoryWithPage **curStack = page->availableStack;
  		while (i < bpp)
  		{
  			curBlock->parentPage=page;
  			curStack[i]=curBlock++;
  			i++;
  		}
  		page->availableStackSize=bpp;
  		page->next=availablePages;
  		page->prev=prev;
  		return true;
  	}
  }
  
  #endif
  