///////////////////////////////////////////////////////////////////////////////
/// @file Internal.cpp
///
/// @brief Destiny3D Internal Memory Manager for Memory Manager
///
/// @author Lightning
///
/// This file is the intellectual property of Novus Delta, LLC.. Usage of the
/// contents of this file is subject to the Destiny3D Member License which
/// can be found at http://www.destiny3d.com.  Any other usage is prohibited.
///
/// This file is distributed "AS IS" without warranty of any kind.  Novus
/// Delta, LLC. does not guarantee the fitness of the contents of this file
/// for any particular purpose.
///
/// Copyright (C) 2001-2003 Novus Delta, LLC. All Rights Reserved.
///
/// <hr>
///                                 Change History
/// <hr>
///
/// @date Dec 2002
/// @author Lightning
/// @remarks Creation
///
///////////////////////////////////////////////////////////////////////////////

#include "Internal.hpp"
#include "stdio.h"

static InternalStruct	*InternalFreePtr;
static InternalStruct	*InternalPages;

//information about the internal memory layout
//memory is allocated in 64k chunks. the first 1024 bytes of the chunk is a lookup table
//defining the closest free block in 256 byte increments. This means the first 4 entries
//can not be used as they cover 0x0000 - 0x0400 for the table. 0x0000 is used to point to the
//next table.

//function that others shouldnt call
InternalStruct *CreateNewInternalPage();

deBoolean InitializeInternalMem(DWORD PageCount)
{
	DWORD			CurPage;
	InternalStruct	*NewPage;
	InternalStruct	*CurFreePtr;

	//Initialize the internal memory
	InternalFreePtr = NULL;
	InternalPages = NULL;

	CurFreePtr = NULL;
	for(CurPage = 0; CurPage < PageCount; CurPage++)
	{
		//allocate the 64k pages for internal mem
		NewPage = CreateNewInternalPage();
		if(!NewPage)
			break;

		//add the free page to the free chain
		NewPage->Prev = CurFreePtr;
		
		//if a current free ptr, update it
		if(CurFreePtr)
			CurFreePtr->Next = NewPage;
		else
			InternalFreePtr = NewPage;		//no free ptr currently, update the internal free ptr

		//change the free ptr
		CurFreePtr = NewPage;
	}

	//if we didnt get to the end of the pages, free what we have and bail
	if(CurPage != PageCount)
	{
		//go thru the pages we have
		while(InternalPages)
		{
			//get the page
			NewPage = InternalPages;
			InternalPages = InternalPages->Next;

			//free it
			RealFree(NewPage);
		}

		//make sure no free chain
		InternalFreePtr = NULL;
		
		//fail
		return deFALSE;
	}

	//everything went fine, tell it so
	return deTRUE;
}

void ReleaseInternalMem()
{
	InternalStruct	*CurPage;
	InternalStruct	*FreeBlockPtr;
	DWORD			PrevBlockPtr;
	BYTE			Counter;
	char			DebugMsg[256];

	//when this is called, there is nothing stopping it

	//destroy all internal memory
	while(InternalPages)
	{
		//get the current page
		CurPage = InternalPages;

		//if we do not have a ptr in the first valid index, or it's size
		//is not 0xFC00, then we have some unfree'd memory
		FreeBlockPtr = (InternalStruct *)(((DWORD *)CurPage)[4]);
		if(!FreeBlockPtr || FreeBlockPtr->Size != 0xFC00)
		{
			//set where the last block ended at
			if((DWORD)FreeBlockPtr != (DWORD)CurPage + 0x400)
				PrevBlockPtr = (DWORD)CurPage + 0x400;
			else
				PrevBlockPtr = 0;

			//go thru the pool and find the alloc'd memory
			if(!FreeBlockPtr)
			{
				//find a free block, if any
				Counter = 5;
				while(Counter && !(((DWORD *)CurPage)[Counter]))
					Counter++;

				//found an entry, set it
				if(Counter)
					FreeBlockPtr = (InternalStruct *)(((DWORD *)CurPage)[Counter]);
			}

			//go thru the free blocks we have, if any, and output any missing data between them
			while(FreeBlockPtr && (DWORD)CurPage == ((DWORD)FreeBlockPtr & 0xFFFF0000))
			{
				//if we have a previous place for the last block, then figure up the missing data
				if(PrevBlockPtr)
				{
					sprintf(DebugMsg, "deMemory: Internal memory leak, Mem - 0x%0.8X   Size - %u bytes\n", PrevBlockPtr, (DWORD)FreeBlockPtr - PrevBlockPtr);
					OutputDebugString(DebugMsg);
				}

				//set prevblockptr to the end of the current free block
				PrevBlockPtr = (DWORD)FreeBlockPtr + FreeBlockPtr->Size;

				//go to the next block
				FreeBlockPtr = FreeBlockPtr->Next;
			}

			//if no free block, but prevblockptr is within the memory, output the resulting size
			if(!FreeBlockPtr && (DWORD)CurPage == ((DWORD)PrevBlockPtr & 0xFFFF0000))
			{
					sprintf(DebugMsg, "deMemory: Internal memory leak, Mem - 0x%0.8X   Size - %u bytes\n", PrevBlockPtr, (DWORD)CurPage + 0x10000 - PrevBlockPtr);
					OutputDebugString(DebugMsg);
			}
		}
	
		//move the pointer to the next page
		InternalPages = InternalPages->Next;

		//free the page
		RealFree(CurPage);
	}
}

InternalStruct *CreateNewInternalPage()
{
	DWORD			NewSize;
	InternalStruct	*NewAlloc;
	InternalStruct	*CurPage;
	InternalStruct	*PrevPage;
	
	//allocate and insert a new internal page

	//allocate 64k of memory for internal usage
	NewSize = 0x10000;
	NewAlloc = (InternalStruct *)RealAlloc(&NewSize);
	if(!NewAlloc)
		return NULL;

	//wipe out all entries in the table
	InternalFunctions->MemSet(NewAlloc, 0, 0x400);	//set all 256 entries to 0

	//get the last page in the chain
	CurPage = InternalPages;
	PrevPage = NULL;
	while(CurPage && (DWORD)CurPage < (DWORD)NewAlloc)
	{
		PrevPage = CurPage;
		CurPage = CurPage->Next;
	}

	//go back a page
	if(CurPage)
		CurPage = CurPage->Prev;
	else
		CurPage = PrevPage;

	//if no current page, insert at the beginning of the chain
	if(!CurPage)
	{
		//no current page, this means we go before the beginning of the list

		//setup prev/next
		NewAlloc->Prev = NULL;
		NewAlloc->Next = InternalPages;

		//if a current entry, modify it's previous
		if(InternalPages)
			InternalPages->Prev = NewAlloc;

		//change the beginning of the list to us
		InternalPages = NewAlloc;
	}
	else
	{
		//CurPage is the page right before us in the chain
		//insert the new page into the page chain

		//change the pointers
		NewAlloc->Prev = CurPage;
		NewAlloc->Next = CurPage->Next;

		//change curpage to point to us
		CurPage->Next = NewAlloc;

		//if there is a page after us, change it's previous
		if(NewAlloc->Next)
			NewAlloc->Next->Prev = NewAlloc;
	}

	//modify the index entry for the free block we have below
	//remember, 0 thru 3 is the index list
	((DWORD *)NewAlloc)[4] = (DWORD)NewAlloc + 0x400;
	
	//hack up a free insertion so we can use it below
	//move the new allocation to be after the table
	NewAlloc = (InternalStruct *)((DWORD)NewAlloc + 0x400);

	//now set up the free block entry
	NewAlloc->Size = 0xFC00;
	NewAlloc->Next = NULL;
	NewAlloc->Prev = NULL;

	//return the new page
	return NewAlloc;
}

//the internal alloc/free functions
void *InternalAlloc(DWORD Size)
{
	InternalStruct	*NewAlloc;
	InternalStruct	*PrevAlloc;
	InternalStruct	*TempAlloc;
	DWORD			*PageData;
	DWORD			NewSize;

	//if the size is too large, fail
	if(Size > 0xFC00)
		return NULL;

	//make sure size is a multiple of 4
	Size = Round4(Size);

	//if the size is smaller than the internal struct, bump it up to the internal struct size
	//otherwise we risk overwriting data between blocks when free goes to put the internal
	//struct in place
	if(Size < sizeof(InternalStruct))
		Size = sizeof(InternalStruct);

	//find an allocation to use
	NewAlloc = InternalFreePtr;

	//loop until no more entries or we find an entry that is the exact size we need or we find
	//an entry large enough to return part of it and still have a free area
	PrevAlloc = NULL;
	while(NewAlloc && NewAlloc->Size != Size && NewAlloc->Size < Size+sizeof(InternalStruct))
	{
		PrevAlloc = NewAlloc;
		NewAlloc = NewAlloc->Next;
	}

	//if no entry, we need to allocate another chunk of memory
	if(!NewAlloc)
	{
		//create a new page
		NewAlloc = CreateNewInternalPage();
		if(!NewAlloc)
			return NULL;

		NewAlloc->Prev = PrevAlloc;
	}

	//we should now have an entry, new or old, for the allocation, allocate it
	if(NewAlloc->Size == Size)
	{
		//a complete match, just remove it and return it
		if(PrevAlloc)
			PrevAlloc->Next = NewAlloc->Next;
		if(NewAlloc->Next)
			NewAlloc->Next->Prev = PrevAlloc;

		//if no previous entry, then update the free ptr as it is the first in the list
		if(!PrevAlloc)
			InternalFreePtr = NewAlloc->Next;
	}
	else
	{
		//move tempalloc to the place the extra free space will be
		TempAlloc = (InternalStruct *)((DWORD)NewAlloc + Size);

		//setup the new entry
		TempAlloc->Size = NewAlloc->Size - Size;
		TempAlloc->Prev = PrevAlloc;
		TempAlloc->Next = NewAlloc->Next;

		//update the previous entry if it exists and the next entry if it exists
		if(PrevAlloc)
			PrevAlloc->Next = TempAlloc;
		if(NewAlloc->Next)
			NewAlloc->Next->Prev = TempAlloc;

		//now the chain is modified, we update the chain below for new alloc
		//however, if tempalloc is too far ahead then we need to update it too

		//update the next ptr for newalloc so the code below works correctly if
		//tempalloc is within the same block
		NewAlloc->Next = TempAlloc;

		//if tempalloc is outside of the block, we need a 2nd index update
		if(((DWORD)NewAlloc & 0xFFFFFF00) != ((DWORD)TempAlloc & 0xFFFFFF00))
		{
			//update the index for tempalloc

			//get the info needed to update the index list on the page
			NewSize = ((DWORD)TempAlloc >> 8) & 0xFF;
			PageData = (DWORD *)((DWORD)TempAlloc & 0xFFFF0000);

			//override the index entry as any entry has to be larger than us
			PageData[NewSize] = (DWORD)TempAlloc;
		}

		//if the internal pointer is the one we just took, then change it
		if(InternalFreePtr == NewAlloc)
			InternalFreePtr = TempAlloc;

	}

	//get the info needed to update the index list on the page
	NewSize = ((DWORD)NewAlloc >> 8) & 0xFF;
	PageData = (DWORD *)((DWORD)NewAlloc & 0xFFFF0000);

	//if we are the entry in the list, then change the entry
	if((DWORD)NewAlloc == PageData[NewSize])
	{
		//update the index list. If the next entry goes past our 256 byte boundary,
		//then wipe it out
		if(((DWORD)NewAlloc & 0xFFFFFF00) != ((DWORD)(NewAlloc->Next) & 0xFFFFFF00))
			PageData[NewSize] = NULL;
		else
			PageData[NewSize] = (DWORD)(NewAlloc->Next);	//put the next entry in
	}
	
	//now return it
	return NewAlloc;

}

void InternalFree(void *Ptr, DWORD Size)
{
	InternalStruct	*PtrData;
	InternalStruct	*PrevData;
	InternalStruct	*NewData;
	DWORD			*PageData;
	BYTE			PageIndex;

	//if no pointer, exit
	if(!Ptr)
		return;

	//make sure size is a multiple of 4
	Size = Round4(Size);

	//if the size is smaller than the internal struct, bump it up to the internal struct size
	//as alloc forces a minimum of the internal struct size to keep from destroying memory
	if(Size < sizeof(InternalStruct))
		Size = sizeof(InternalStruct);

	//go thru the allocated pages until we find the one it goes in
	//each page's data is allocated inside it's own page so we can just look
	//where PageData sits to get the page
	PageData = (DWORD *)InternalPages;
	while(PageData && ((DWORD)PageData != ((DWORD)Ptr & 0xFFFF0000)))
		PageData = (DWORD *)((InternalStruct *)PageData)->Next;

	//if no page entry, exit as we dont own it
	if(!PageData)
		return;

	//get the index entry for the ptr
	PageIndex = (BYTE)(((DWORD)Ptr >> 8) & 0xFF);

	//if no free ptr, just fill it
	if(!InternalFreePtr)
	{
		//free ptr is blank, fill in it's values
		InternalFreePtr = (InternalStruct *)Ptr;
		InternalFreePtr->Next = NULL;
		InternalFreePtr->Prev = NULL;
		InternalFreePtr->Size = Size;

		//update the lookup entry
		PageData[PageIndex] = (DWORD)InternalFreePtr;

		//all done
		return;
	}

	//setup the new data
	NewData = (InternalStruct *)Ptr;

	//see if we got an entry, if no entry, check and see if the table has an entry after us
	//or before us
	if(PageData[PageIndex])
	{
		//lookup the closest free block in the ptr table
		PtrData = (InternalStruct *)(PageData[PageIndex]);
	}
	else if((PageIndex < 0xFF) && PageData[PageIndex + 1])
	{
		//PageIndex < 255 and the lookup table has an entry after the one we started on

		//if our table doesnt have an entry, then the first entry returned here we just append to
		PtrData = (InternalStruct *)(PageData[PageIndex + 1]);
	}
	else if(PageIndex > 3 && PageData[PageIndex - 1])
	{
		//PageIndex valid (0 thru 3 will never be used) and the lookup table has an entry before the one we started on
		PtrData = (InternalStruct *)PageData[PageIndex - 1];
	}
	else
	{
		//no entry before or after us, or the pageindex isnt in the right place to check
		//so, start at the beginning of the list
		PtrData = InternalFreePtr;
	}

	//go thru until we pass our ptr
	PrevData = PtrData->Prev;
	while(PtrData && ((DWORD)PtrData < (DWORD)Ptr))
	{
		PrevData = PtrData;
		PtrData = PtrData->Next;
	}

	//see if a previous entry exists and they run into each other, if they do, combine
	if(PrevData && (DWORD)PrevData + PrevData->Size == (DWORD)NewData)
	{
		//can combine, do so
		PrevData->Size = PrevData->Size + Size;
		NewData = PrevData;
	}
	else
	{
		//cant combine, update the lookup table for the new data, if needed
		if(!PageData[PageIndex] || (PageData[PageIndex] > (DWORD)NewData))
			PageData[PageIndex] = (DWORD)NewData;

		//update the new data's info on size incase we can combine below
		NewData->Size = Size;
		
		//could not combine with the previous block, change the previous pointer
		NewData->Prev = PrevData;
		if(PrevData)
			PrevData->Next = NewData;
	}
	
	//see if the entry after us can be combined
	if(PtrData && ((DWORD)PtrData == (DWORD)NewData + NewData->Size))
	{
		//can combine, do so
		NewData->Size = NewData->Size + PtrData->Size;

		//update the pointers
		NewData->Next = PtrData->Next;
		if(NewData->Next)
			NewData->Next->Prev = NewData;

		//check the lookup table for PtrData to see if it needs to be changed
		PageIndex = (BYTE)(((DWORD)PtrData >> 8) & 0xFF);
		if(PageData[PageIndex] == (DWORD)PtrData)
		{
			//see if it needs to be null or not
			if(((DWORD)PtrData & 0xFFFFFF00) != ((DWORD)PtrData->Next & 0xFFFFFF00))
				PageData[PageIndex] = NULL;
			else
				PageData[PageIndex] = (DWORD)(PtrData->Next);
		}

		//a flag showing we combined
		PtrData = NewData;
	}
	else
	{
		//could not combine with the next block, adjust the next pointer if needed
		//if newdata is not set to the previous entry, then it needs to be changed
		if(NewData != PrevData)
		{
			NewData->Next = PtrData;
			if(PtrData)
				PtrData->Prev = NewData;
		}
	}

	//see if the free ptr needs an update. Easy way is if no previous exists
	if(!PrevData)
		InternalFreePtr = NewData;

	//all done, return
	return;
}
