// Copyright (C) 2004-2009 Christoph Kubisch & Eike Decker
// This file is part of the "Luxinia Engine".
// For conditions of distribution and use, see copyright notice in luxiniapublicsdk.txt

#include <luxcore/memorylist.h>
#include <luxplatform/debug.h>

#include "memory_defs.h"

LUX_INLINE size_t alignValue(size_t val, size_t alignin)
{
	size_t align = 	alignin ? alignin : 1;
	size_t offset = val % align;
	offset = offset ? align-offset : 0;
	return val + offset;
}


void MemoryList_addPage (lxMemoryList_t* self, uint size)
{
	uint alignSize = self->alignSize;
	lxMemoryPage_t* oldchunk = (lxMemoryPage_t*)self->pagelist;
	lxMemoryPage_t* newchunk = (lxMemoryPage_t*)MEMORY_LOCAL_MALLOC(size+sizeof(lxMemoryPage_t)+self->alignSize);
	LUX_DEBUGASSERT(newchunk);

	newchunk->next = oldchunk;
	newchunk->size = size;
	self->pagelist = newchunk;

	if (oldchunk){
		// to prevent wasting old memory lets throw it in the first 
		// largest fitting size (could use better heuristic here)

		uint chunksize = self->chunksize;
		uint chunkpos = self->chunkpos;
		int cnt = self->cnt;
		uint left = chunksize-chunkpos;
		int i;

		if (left){
			for (i = cnt-1 ; i >= 0; i--){
				lxMemorySizeSlot_t	*cursl = &self->slots[i];
				while (left >= cursl->size){
					lxMemoryNode_t*	block = (lxMemoryNode_t*)&self->chunk[chunkpos];
					block->next = cursl->freelist;
					cursl->freelist = block;

					chunkpos += cursl->size;
					left -= cursl->size;
				}
			}
		}
	}

	self->chunk = (byte*)alignValue((size_t)(newchunk+1),self->alignSize);
	self->chunksize = size;
	self->chunkpos = 0;

#ifdef LUX_PROFILING
	LUX_PROFILING_OP( self->memAllocatedPages += size);
#endif
}

void MemoryList_init (lxMemoryList_t* self, uint numSizes, const uint* sizes, uint startsize, uint alignSize)
{
	uint i,n;
	uint cnt = numSizes;
	memset(self,0,sizeof(lxMemoryList_t));
	self->alignSize = alignSize;

	LUX_ASSERT(self->cnt <= MEMORY_LIST_MAXSLOTS);

	// correct sizs for alignment
	for (i = 0; i < numSizes; i++){
		self->slots[i].size = alignValue(sizes[i],alignSize);
	}

	// remove double entries
	for (i = 1, n = 1; i < numSizes; i++,n++){
		while (self->slots[i-1].size == self->slots[i].size && i < numSizes){
			cnt--;
			i++;
		}
		if (i < numSizes){
			self->slots[n].size = self->slots[i].size;
		}
	}

	self->cnt = cnt;
	MemoryList_addPage(self,startsize);
}

void MemoryList_deinit (lxMemoryList_t* self)
{
	lxMemoryPage_t* page = self->pagelist;
	uint alignSize = self->alignSize;

	while (page){
		lxMemoryPage_t* cur = page;
		page = cur->next;
		MEMORY_LOCAL_FREE(cur,cur->size+sizeof(lxMemoryPage_t)+alignSize);
	}
	self->memAllocatedPages = 0;
}

void lxMemoryList_freeItem (lxMemoryList_t* self, void* old, uint oldsize)
{
	int i;
	lxMemoryNode_t *block = (lxMemoryNode_t*)old;
	uint alignSize = self->alignSize;

	if (old==NULL || oldsize==0) return;

#ifdef LUX_PROFILING
	LUX_PROFILING_OP(self->numItems--);
#endif

	for (i = 0; i < self->cnt; i++) {
		lxMemorySizeSlot_t	*cursl = &self->slots[i];
		if (oldsize <= cursl->size) {
			block->next = cursl->freelist;
			cursl->freelist = block;
#ifdef MEMORY_STATS
			cursl->cnt--;
#endif
			return;
		}
	}

	// outside of managed sized
	if (!alignSize){
		MEMORY_LOCAL_FREE(old,oldsize);
	}
	else{
		MEMORY_LOCAL_FREEALIGNED(old,oldsize);
	}
	

#ifdef LUX_PROFILING
	LUX_PROFILING_OP( self->memAllocatedOuter -= oldsize);
#endif
}

void* lxMemoryList_allocItem (lxMemoryList_t* self, uint size)
{
	byte *mem;
	int i;
	int cnt = self->cnt;

#ifdef LUX_PROFILING
	LUX_PROFILING_OP(self->numItems++);
#endif

	// outside of managed sizes
	if (size > self->slots[cnt-1].size) {
		uint alignSize = self->alignSize;
#ifdef LUX_PROFILING
		LUX_PROFILING_OP( self->memAllocatedOuter += size);
#endif
		if (!alignSize){
			return MEMORY_LOCAL_MALLOC(size);
		}
		else{
			return MEMORY_LOCAL_MALLOCALIGNED(size,alignSize);
		}
	}

	// find next best slot / reuse
	for (i = 0; i < cnt; i++) {
		lxMemorySizeSlot_t	*cursl = &self->slots[i];

		if (size <= cursl->size) {
			size  = cursl->size;
#ifdef LUX_PROFILING
			cursl->cnt++;
#endif
			// reuse
			if (mem = (byte*)cursl->freelist){
				cursl->freelist = cursl->freelist->next;
				return mem;
			}
#if 1
			//else if (self->chunkpos + size >= self->chunksize){
			else{
				// steal from next
				int n = i+1;
				while (n < cnt){
					cursl = &self->slots[n];
					if (mem = (byte*)cursl->freelist){
						// split among lower
						uint spread = cursl->size - size;
						void* outmem = (void*)mem;
						lxMemoryNode_t* node = (lxMemoryNode_t*)mem;
						cursl->freelist = node->next;
						mem += size;

						i = n-1;
						for (;i >= 0; --i){
							cursl = &self->slots[i];
							size = cursl->size;
							while (spread >= size){
								spread -= size;
								node = (lxMemoryNode_t*)(mem);
								node->next = cursl->freelist;
								cursl->freelist = node;
								mem += size;
							}
						}
#ifdef LUX_PROFILING
						self->memWasted += spread;
#endif

						return outmem;
					}
					n++;
				}
			}
#endif
			
			break;
		}
	}

	// pool is full
	if (self->chunkpos + size >= self->chunksize) {
		uint nsize = (self->chunksize);
		nsize = nsize < size*2 ? size*2 : nsize;

		MemoryList_addPage(self,nsize);
	}

	mem = &self->chunk[self->chunkpos];
	self->chunkpos += size;


	return mem;
}

void* lxMemoryList_reallocItem (lxMemoryList_t* self, void* old, uint oldsize, uint newsize)
{
	void *ptr;
	int i;
	int cnt = self->cnt;

	// already within same slotted size
	for (i=1; i < cnt; i++) {
		lxMemorySizeSlot_t	*prevsl = &self->slots[i-1];
		lxMemorySizeSlot_t	*cursl = &self->slots[i];

		if (oldsize <= cursl->size && newsize <= cursl->size &&
			oldsize > prevsl->size && newsize > prevsl->size)
			return old;
	}

	// find best fit / reuse 
	for (i=0; i < cnt; i++) {
		lxMemorySizeSlot_t	*cursl = &self->slots[i];

		if (newsize <= cursl->size) {
			if (cursl->freelist == NULL) {
				ptr = (void*)lxMemoryList_allocItem(self,cursl->size);
				break;
			}
#ifdef LUX_PROFILING
			cursl->cnt++;
			self->numItems++;
#endif
			ptr = (void*)cursl->freelist;
			cursl->freelist = cursl->freelist->next;
			break;
		}
	}

	// out of managed sizes
	if (i == cnt) {
		ptr = (void*)lxMemoryList_allocItem(self,newsize);
	}

	if (old) {
		memcpy(ptr,old,LX_MIN(oldsize,newsize));
		lxMemoryList_freeItem(self,old,oldsize);
	}
	return ptr;
}

void lxMemoryList_stats(lxMemoryListPTR self, uint *allocTotal, uint *allocPaged, float *pageratio)
{
#ifdef LUX_PROFILING
	int i;
	uint inpages = 0;
	for (i=0; i < self->cnt; i++){
		inpages += self->slots[i].size * self->slots[i].cnt;
	}
	*allocTotal = self->memAllocatedPages+self->memAllocatedOuter;
	*allocPaged = self->memAllocatedPages;
	*pageratio  = ((float)inpages)/((float)self->memAllocatedPages);
#else
	*allocTotal = 0;
	*allocPaged = 0;
	*ratio = 0;
#endif
}

void MemoryList_initBits(lxMemoryListPTR self,uint sizeminbit, uint sizemaxbit, uint startsize, uint alignSize)
{
	uint sizes[MEMORY_LIST_MAXSLOTS];
	int i;
	int numSizes = sizemaxbit-sizeminbit+1;
	LUX_ASSERT(numSizes <= MEMORY_LIST_MAXSLOTS);

	for (i=0; i < numSizes; i++){
		sizes[i] =  1<<(i+sizeminbit);
	}

	MemoryList_init(self,numSizes,sizes,startsize,alignSize);
}

lxMemoryListPTR lxMemoryList_newBits(uint sizeminbit, uint sizemaxbit, uint startsize, uint alignSize)
{
	lxMemoryListPTR self;
	if (sizemaxbit-sizeminbit+1 > MEMORY_LIST_MAXSLOTS) return NULL;
	
	self = MEMORY_LOCAL_MALLOC(sizeof(lxMemoryList_t));
	MemoryList_initBits(self,sizeminbit,sizemaxbit,startsize,alignSize);
	return self;
}

lxMemoryListPTR lxMemoryList_new(uint numSizes, uint* sizes, uint startsize, uint alignSize)
{
	lxMemoryListPTR self = MEMORY_LOCAL_MALLOC(sizeof(lxMemoryList_t));
	MemoryList_init(self,numSizes,sizes,startsize,alignSize);
	return self;
}

void lxMemoryList_delete(lxMemoryListPTR self)
{
	MemoryList_deinit(self);
	MEMORY_LOCAL_FREE(self,sizeof(lxMemoryList_t));
}
