// Problem: Allocating all the memory on the 360 then deallocating it over and over can lead to memory fragementation
// if we're not careful.

// Solution: We will allocate write a custom allocator for small blocks of memory, but leave big stuff to the regular allocator.
// Going off a whiteboard discussion that I had with John Pollard based on discussions he had with Charles Bloom.
// To me it seems like a good twist on buddy memory allocation as described by Knuth.

// 32k is going to be our biggest "small" block, everything larger will be passed onto the default allocator.
// We have 128b, 256b, 512b, 1kb, 2kb, 4kb, 8kb, 16kb, and 32kb blocks.

// Whenever we get a request for a small block, we first examine our pool and give out free memory already available.
// If our pool has no space, we ask the standard allocator for another 64k.
// We take that new 64k chunk and subdivide it up into usable small blocks 
// depending on the desired allocation and return one of the blocks to the caller.

// Things to do once we're done:
// We can examine what our pool looks like in the middle of the game.
// On next run we can pre-fill the pool with blocks similar to the usage pattern.

// How to handle each pool of small blocks:
// In a normal memory pool, you maintain a free list. I'll use a free list for each size of small blocks in this case.

#include <exception>
#include <new>
#include <cstdlib>
#include <iostream>
#include <cmath>
#include <algorithm>

using namespace std;

const int POOLMAX = 1024*32;
const int POOLMIN = 128;
//const int POOLCOUNT = log(POOLMAX) / log(2) - log(POOLMIN) / log(2);
const int POOLCOUNT = 9;

struct MemoryTag
{
	char bInPool:1;             // identifier so delete knows how to handle us
	char BlockBucket:7;         // which subdivision are we in e.g. 128b, 256b ... 32kb
	MemoryTag* NextInFreeList;  // now we're a linked list node
};

MemoryTag *FreeLists[POOLCOUNT];

void PoolInit()
{
	for (int i = 0; i < POOLCOUNT; i++)
	{
		FreeLists[i] = NULL;
	}
}

void* PoolAllocate(size_t size)
{
	void *p = NULL;

	static int BucketPoolMin = log10((float)POOLMIN) / log10(2.0f);
	int BucketCurrentSize = log10((float)size) / log10(2.0f);

	int BlockBucket = max(BucketCurrentSize - BucketPoolMin, 0);

	if (FreeLists[BlockBucket] == NULL)
	{
		int NumBlocks = 64*1024/BucketCurrentSize;
		// allocate 64k + all the memorytag headers
		FreeLists[BlockBucket] = (MemoryTag*)malloc(64*1024 + NumBlocks*sizeof(MemoryTag));

		// prep the new blockset
		for (int i = 0; i < NumBlocks; i++)
		{
			MemoryTag* CurrentBlock = (MemoryTag*)((char*)FreeLists[BlockBucket] + i * (sizeof(MemoryTag) + BucketCurrentSize));
			CurrentBlock->bInPool = 1;
			CurrentBlock->BlockBucket = BlockBucket;
			CurrentBlock->NextInFreeList = (MemoryTag*)((char*)FreeLists[BlockBucket] + (i + 1) * (sizeof(MemoryTag) + BucketCurrentSize));
		}

		MemoryTag* LastBlock = (MemoryTag*)((char*)FreeLists[BlockBucket] + (NumBlocks - 1) * (sizeof(MemoryTag) + BucketCurrentSize));
		LastBlock->NextInFreeList = NULL;

		// give out the first block in the free list
		p = FreeLists[BlockBucket]->NextInFreeList;
	}
	else
	{
		p = FreeLists[BlockBucket];
	}
		
	FreeLists[BlockBucket] = ((MemoryTag*)p)->NextInFreeList;

	return (char*)p + sizeof(MemoryTag);
}

void PoolDeallocate(void *p)
{
	// put us back on the free list for our block bucket.
	MemoryTag* CurrentBlock = (MemoryTag*)((char*)p - sizeof(MemoryTag)); 
	CurrentBlock->NextInFreeList = FreeLists[CurrentBlock->BlockBucket];
	FreeLists[CurrentBlock->BlockBucket] = CurrentBlock;
}

void* operator new (size_t size)
{
	void *p = NULL;
	
	if (size == 0)
		return p;

	if (size > POOLMAX)
	{
		p = malloc(size + sizeof(MemoryTag));
		if (p == NULL)
			return p;

		((MemoryTag*)p)->bInPool = 0;
		return (char*)p + sizeof(MemoryTag);
	}

	return PoolAllocate(size);
}

void operator delete (void *p)
{
	if (p == NULL)
		return;

	MemoryTag *MemTag = (MemoryTag*)((char*)p - sizeof(MemoryTag));

	if (MemTag->bInPool == 0)
	{
		free(MemTag); 
	}
	else
	{
		PoolDeallocate(MemTag); 
	}
}

int main()
{
	PoolInit();

	char *p = NULL;

	char *c = NULL;
	char *c2 = NULL;
	
	delete p;
	p = new char[POOLMAX + 1]; 
	delete p;
	p = NULL;

	c = new char; 
	c2 = new char[1024*2]; 
	delete c2;
	delete c;
}