#include "memorypool.h"

#define MIN_ALIGNMENT_SIZE 8

#define UT_MAX(a,b) (a>b?a:b)
#define UT_CALC_ALIGN(n,m) (( n + ((m) - 1) ) & ~( (m) - 1 ))
#define UT_IS_POW2(n) ( (n & (n-1)) == 0 )

// We need a MemoryArea object to monitor memory area status,
// this may take extra size.
#define MEM_AREA_EXTRA_SIZE UT_CALC_ALIGN(sizeof(MemoryArea), MIN_ALIGNMENT_SIZE)

// A memory area should at least be capacable to store two MemoryArea object
// In that it may be splitted into two parts
#define MEM_AREA_MIN_SIZE (2 * MEM_AREA_EXTRA_SIZE)

/**
 * @brief log2
 * calculate ceil value of log2(n)
 * @param num
 * @return value>=1
 */
inline int ceilLog2(size_t num)
{
 num -= 1;
 int exp = 0;
 for( ;num!=0; num>>=1) {
 exp++;
 }

 return exp;
}

/**
 * @brief MEM_AREA_EXTRA_SIZE
 * Why it's using double size of MemoryArea as extra size of a pool?
 * An area can be divided into two areas at a lower level, with half the original size
 * respectively.
 */


MemoryPool::MemoryPool(size_t blockSize)
{
 BLOCK_SIZE = blockSize;
 addBlock( BLOCK_SIZE );

#ifndef NDBG
 requestSum = 0;
 allocSum = 0;
 recycleSize = 0;
 recycleAlloc = 0;
#endif

}

MemoryPool::~MemoryPool()
{
 destroy();
}

void MemoryPool::addBlock(size_t size)
{
 byte* newBlock = (byte*)malloc( size );
 if( !newBlock )
 {
 MemoryException me( "MemoryPool:No enough memory for new block" );
 throw me;
 }

 currentPosition = newBlock;
 remainSizeInCurBlock = size;
 blocks.push_back( newBlock );
}

void* MemoryPool::allocate(size_t size)
{
 size_t toAlloc = UT_CALC_ALIGN( (size+sizeof(MemoryArea)), MIN_ALIGNMENT_SIZE );

#ifndef NDBG
 requestSum += size;
 allocSum += toAlloc;
#endif

 ASSERT_MSG( toAlloc <= BLOCK_SIZE, "Can not allocate memory for size bigger than single block" );

 byte* ret = 0;
 MemoryArea* area = 0;

 if( remainSizeInCurBlock >= toAlloc ) // We happen to have enough size in blocks
 {
 ret = currentPosition + sizeof(MemoryArea);
 area = (MemoryArea*)currentPosition;
 area->setSize(toAlloc);
 //cout<<"Request="<<size<<" Alloc="<<toAlloc<<"Area Size="<<area->getSize()<< "sizeofMemArea:"<<sizeof(MemoryArea)<<endl;
 remainSizeInCurBlock -= toAlloc;
 currentPosition += toAlloc;
 }
 else
 {
 int index = ceilLog2(toAlloc);
 //cout<<"Alloc index="<<index<<endl;
 for( int i=index; i<RECYCLE_MAX_INDEX; i++ )
 {
 if( recycleList[i].empty() ) continue;
 area = recycleList[i].front();
 if( i != index )
 {
 area->setSize(toAlloc);
 size_t remainSize = area->getSize() - toAlloc;
 MemoryArea* area2 = (MemoryArea*)((byte*)area + toAlloc );
 area2->setSize(remainSize);
 area2->setFree(true);
 int index2 = ceilLog2( remainSize ) - 1;
 if( UT_IS_POW2(remainSize) )
 {
 index2++;
 }
 recycleList[index2].push_front(area2);
 }

#ifndef NDBG
 recycleAlloc += area->getSize();
#endif
 recycleList[i].erase(recycleList[i].begin());
 ret = (byte*)area;
 break;
 }

 if( !ret ) //Cannot find available space from block/recycleList, expand block
 {
 addBlock(BLOCK_SIZE);
 ret = currentPosition + sizeof(MemoryArea);
 area = (MemoryArea*)currentPosition;
 area->setSize(toAlloc);

 remainSizeInCurBlock -= toAlloc;
 currentPosition += toAlloc;
 }
 }

 ASSERT( ret && area );

 area->magicNumber = MEM_AREA_MAGIC_N;
 area->setFree(false);
 //printf("area=%x, ret=%x, free=%d\n", (unsigned int)area, (unsigned int)ret, area->isFree());
 return (void*)ret;
}

void MemoryPool::recycle(void *ptr)
{
 //printf("Recycle=%x\n",(unsigned int)ptr );
 MemoryArea* area = (MemoryArea*)((byte*)ptr - sizeof(MemoryArea));

 // Check memory leak / illegal release
 ASSERT( area->isFree() == false );
 ASSERT( area->magicNumber == MEM_AREA_MAGIC_N );

 size_t size = area->getSize();

#ifndef NDBG
 recycleSize += size;
#endif
 int index = ceilLog2(size) - 1;
 if( UT_IS_POW2(size) )
 {
 index ++; // Put 2^n to a higher index
 }
 ASSERT(index < RECYCLE_MAX_INDEX);
 area->setFree(true);
 recycleList[index].push_front(area);
}

/**
 * @brief MemoryPool::destroy
 * Destroy all blocks allocated for this pool
 */
void MemoryPool::destroy()
{
 for( vector<byte*>::iterator i = blocks.begin();
 i != blocks.end();
 i++ )
 {
 free(*i);
 }

 blocks.clear();

 for( int i = 0; i< RECYCLE_MAX_INDEX; i++ )
 {
 if( recycleList[i].empty() ) continue;
 recycleList[i].clear();
 }

 currentBlock = 0;
 currentPosition = 0;
 remainSizeInCurBlock = 0;

#ifndef NDBG
 requestSum = 0;
 allocSum = 0;
 recycleSize = 0;
 recycleAlloc = 0;
#endif

}

void MemoryPool::report()
{
 cout<<"\n======MemoryPool report======"<<endl;
#ifndef NDBG
 cout<<"Requested = "<<requestSum<<" bytes. Allocated = "<<allocSum<<" bytes";
 double ratio = 0.0;
 if( allocSum )
 {
 ratio = 1.0*requestSum/allocSum;
 }
 cout<<" ratio="<<ratio<<endl;
 cout<<"Recycled = "<<recycleSize<<" bytes. Allocated From Recycle = "<< recycleAlloc<<" bytes";
 ratio = 0.0;
 if( recycleSize )
 {
 ratio = 1.0 * recycleAlloc / recycleSize;
 }
 cout<<" ratio="<<ratio<<endl;
#endif
 cout<<"#### Blocks"<<endl;
 for( size_t i=0; i<blocks.size(); i++ )
 {
 printf("#%d:\taddr:%x\tfree=%d\n", i, blocks[i],remainSizeInCurBlock);
 }
 cout<<"#### Recycle List";
 for( int i=0; i< RECYCLE_MAX_INDEX; i++ )
 {
 if( recycleList[i].empty() ) continue;
 cout<<"\n#Index: "<<i<<"\t----"<<endl;
 for(list<MemoryArea*>::iterator iter = recycleList[i].begin();
 iter != recycleList[i].end(); iter++ )
 {
 cout<<(*iter)->getSize()<<"\t";
 }
 }
 cout<<"\n-------------------"<<endl;
}