///////////////////////////////////////////////////////////////////////////////
/// @file deMemory.cpp
///
/// @brief Destiny3D 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 Feb 2001
/// @author Lightning
/// @remarks Creation
///
/// @date Oct 2001
/// @author Hootie
/// @remarks Started Conversion to C++
///
/// @date Oct 2002
/// @author Lightning
/// @remarks Scrapped old, started from scratch
///
///////////////////////////////////////////////////////////////////////////////

#include "Functions/Functions.hpp"
#include "deMemory.hpp"
#include "deMemory_priv.hpp"
//#include "RedBlackTree\\RedBlackTree.hpp"
#include "Internal.hpp"
#include <cstdio>

//the dll main for the memory manager
BOOLEAN WINAPI IdeMemory_DllMain(HINSTANCE hDLLHandle, DWORD nReason, LPVOID /*Reserved*/)
{
	//see if we are being attached or not
	switch(nReason)
	{
		case DLL_PROCESS_ATTACH:
			//first, make things alittle faster by not having new threads contact us
			DisableThreadLibraryCalls(hDLLHandle);

			//initialize the memory manager
			deMemory = IdeMemory_GetManager(NULL);
			if(!deMemory)
				return FALSE;
			
			break;

		case DLL_PROCESS_DETACH:
			//erase the memory manager
			if(deMemory)
			{
				//let it clean up
				((deMemoryManager *)deMemory)->~deMemoryManager();

				//undo the pointer to the static variable
				deMemory = NULL;
			}

			break;
	};

	//everything is fine, say so
	return TRUE;
}


IdeMemoryManager *IdeMemory_GetManager(char *ConfigFile)
{
	//if we already have a memory manager, return it
	if(deMemory)
		return deMemory;
	
	//init the class if needed and return it
	static deMemoryManager s_deMemory(ConfigFile);

	//see if everything init'd
	if(!s_deMemory.IsInitialized())
	{
		//let the class erase itself
		s_deMemory.~deMemoryManager();
		return NULL;
	}

	//everything is fine, return the memory manager
	return &s_deMemory;
}

deMemoryManager::deMemoryManager(char* /*ConfigFile*/)
{
	DWORD			MemSize;

	//default to not init'd
	Initialized = deFALSE;
	RootFreeNode = &RedBlackNULLNode;
	RootAllocNode = &RedBlackNULLNode;
	RootRealAllocList = NULL;
	
	//initialize the internal memory functions as other areas may need them
	if(!InitializeInternalFunctions())
		return;

	//initialize internal memory
	if(!InitializeInternalMem(2))
	{
		//undo the internal functions
		ReleaseInternalFunctions();
		return;
	}

	//allocate a chunk of memory to get going with
	MemSize = 1024*1024*10;	//10MB
	RootFreeNode = AllocRealMem(&MemSize);
	if(!RootFreeNode)
	{
		//something went wrong, we didnt init
		ReleaseInternalMem();
		ReleaseInternalFunctions();
		return;
	}

	//modify the new free chain entry so everything is valid
	RootFreeNode->Left = &RedBlackNULLNode;
	RootFreeNode->Right = &RedBlackNULLNode;
	RootFreeNode->Parent = &RedBlackNULLNode;
	SetNodeBlack(RootFreeNode);
	SetNodeFree(RootFreeNode);
	RootFreeNode->Brother = NULL;

	//everything is fine, set it as such
	Initialized = deTRUE;
}

deMemoryManager::~deMemoryManager()
{
	//if we arent initialized, exit
	if(!Initialized)
		return;

	//check for memory leaks
	CheckMemoryLeaks();

	//destroy all the memory we allocated
	ReleaseAllRealAllocMem();

	//destroy internal memory
	ReleaseInternalMem();

	//destroy the internal functions
	ReleaseInternalFunctions();
}

void deMemoryManager::OutputMemLeak(RedBlackNode *LeakAlloc)
{
	AllocStruct		*AllocInfo;
	char			Buffer[256];

	//get the info
	AllocInfo = (AllocStruct *)LeakAlloc->ExtraData;

	//output leak information for a node
	OutputDebugString("Memory Leak, (");
	OutputDebugString(AllocInfo->File);

	//output the line
	sprintf(Buffer, ", %u, ", AllocInfo->Line);
	OutputDebugString(Buffer);

	//output the type
	switch(AllocInfo->AllocType)
	{
		case RegMalloc:
			OutputDebugString("malloc");
			break;

		case Calloc:
			OutputDebugString("calloc");
			break;

		case New:
			OutputDebugString("new");
			break;

		case NewArray:
			OutputDebugString("new[]");
			break;

		default:
			OutputDebugString("Unknown Alloc");
			break;
	}

	//now, output the mem ptr and size
	sprintf(Buffer,	")  Mem - 0x%0.8X   Size - %u Bytes\n", LeakAlloc->Ptr, LeakAlloc->Size);
	OutputDebugString(Buffer);

	//all done
	return;
}

void deMemoryManager::CheckMemoryLeaks()
{
	RedBlackNode	*CurAlloc;
	

	//go thru the alloc tree for memory leaks
	CurAlloc = RootAllocNode;

	//head far left so we can go in order of memory
	while(CurAlloc->Left != &RedBlackNULLNode)
		CurAlloc = CurAlloc->Left;

	//go thru the left side of the tree
	while(CurAlloc != &RedBlackNULLNode)
	{
		//output our leak info
		OutputMemLeak(CurAlloc);

		//if anything on the right, go right
		if(CurAlloc->Right != &RedBlackNULLNode)
		{
			//go right
			CurAlloc = CurAlloc->Right;

			//go left until we hit the end of it
			while(CurAlloc->Left != &RedBlackNULLNode)
				CurAlloc = CurAlloc->Left;
		}
		else
		{
			//if we are on the right side of our parent, go up the right side of the branch
			//until we hit the very top of the current branch
			if(CurAlloc == CurAlloc->Parent->Right)
			{
				//backtrack up the right side of the tree
				while(CurAlloc == CurAlloc->Parent->Right)
					CurAlloc = CurAlloc->Parent;

				//went as high as we could go, grab the curalloc's parent so we can start on a new branch
				CurAlloc = CurAlloc->Parent;
			}
			else
			{
				//on the left, go up to the parent
				CurAlloc = CurAlloc->Parent;
			}
		}
	}

	//all done
	return;
}

void deMemoryManager::ReleaseAllRealAllocMem()
{
	RealAllocStruct	*TempAlloc;
	RedBlackNode	*AllocEntry;

	//go thru all the real memory and free it
	while(RootRealAllocList != NULL)
	{
		//store the pointer to the structure and update the chain to the next entry
		TempAlloc = RootRealAllocList;
		RootRealAllocList = RootRealAllocList->Next;

		//free the memory
		RealFree(TempAlloc->Ptr);

		//find the node in the tree
		AllocEntry = FindClosestRedBlackTreeNodePtr(RootAllocNode, TempAlloc->Ptr);

		//if we got a redblacknullnode, then point to the free list for the linked list
		if(AllocEntry == &RedBlackNULLNode)
			AllocEntry = RootFreeNode;

		//go thru the linked list to find our pointer as it may be in the free list, or
		//may be in the alloc list and never got free'd due to a mem leak
		while(AllocEntry != &RedBlackNULLNode)
		{
			//if it matches, tell internal to remove it and bail
			if(AllocEntry->Ptr == TempAlloc->Ptr)
			{
				//found it, free from internal and bail
				InternalFree(AllocEntry, sizeof(RedBlackNode));
				break;
			}

			//if too low, go right, otherwise go left
			if(AllocEntry->Ptr < TempAlloc->Ptr)
				AllocEntry = AllocEntry->Right;
			else
				AllocEntry = AllocEntry->Left;
		}

		//remove the real entry's memory from the internal memory
		InternalFree(TempAlloc, sizeof(RealAllocStruct));
	}

	//all done
	return;
}

RedBlackNode *deMemoryManager::AllocRealMem(DWORD *Size)
{
	RealAllocStruct *	NewAlloc;			//new alloc entry for real alloc chain
	RealAllocStruct *	CurAlloc;			//current alloc entry we are on in real alloc chain
	RealAllocStruct *	PrevAlloc;			//prev alloc entry we were on in real alloc chain

	RedBlackNode *		NewNode;			//new node ready to be added to an alloc or free tree
	RedBlackNode *		ClosestNode;		//closest node in the tree to the new node
	RedBlackNode *		PrevClosestNode;	//previously closest node in the tree to the new node


	//allocate real memory for the memory manager

	//first, allocate memory for the struct
	NewAlloc = (RealAllocStruct *)InternalAlloc(sizeof(RealAllocStruct));
	if(!NewAlloc)
		return NULL;

	//now, setup a new node for the allocation as the only reason
	//to allocate the memory is to use it in the alloc tree
	//of course part of it may go to the free so we dont worry about
	//inserting it here
	NewNode = (RedBlackNode *)InternalAlloc(sizeof(RedBlackNode));
	if(!NewNode)
	{
		InternalFree(NewAlloc, sizeof(RealAllocStruct));
		return NULL;
	}

	//allocate real memory based on a certain size
	NewAlloc->Ptr = RealAlloc(Size);
	if(!NewAlloc->Ptr)
	{
		InternalFree(NewAlloc, sizeof(RealAllocStruct));
		InternalFree(NewNode, sizeof(RedBlackNode));
		return NULL;
	}

	NewAlloc->Size = *Size;

	//find where in the chain to insert it. it is ordered by ptr to help in removal
	CurAlloc = RootRealAllocList;
	PrevAlloc = NULL;
	while(CurAlloc && CurAlloc->Ptr < NewAlloc->Ptr)
	{
		PrevAlloc = CurAlloc;
		CurAlloc = CurAlloc->Next;
	}

	//add the new allocation to the alloc chain
	NewAlloc->Next = CurAlloc;
	if(PrevAlloc)
		PrevAlloc->Next = NewAlloc;
	else
		RootRealAllocList = NewAlloc;


	//setup the red/black node

	//what node data we do not set here will be set upon insert so no need to clear out the node
	//of course, i'm assuming this, i could end up making an ass outta myself (ASS Union ME)

	//set the size and pointer
	NewNode->Size = *Size;
	NewNode->Ptr = NewAlloc->Ptr;

	//find the closest pointer for the alloc tree
	ClosestNode = FindClosestRedBlackTreeNodePtr(RootAllocNode, NewNode->Ptr);
	
	//if ClosestNode is null (not the null node), then we are allocating memory but there is no
	//entry in the alloc node tree. Set ClosestNode to the free tree and walk the free tree's
	//linked list
	if(ClosestNode == &RedBlackNULLNode)
	{
		//get the top node in the free tree
		ClosestNode = RootFreeNode;

		//walk the free tree's linked list. We may be before or after the node we need to insert
		//so we have to walk both directions until closestnode and prevclosestnode contain
		//both sides of the new node
		PrevClosestNode = ClosestNode->LinkedLeft;
		while(ClosestNode != &RedBlackNULLNode)
		{
			//if closest is on the left of the new node, head right in the linked list
			if(ClosestNode->Ptr < NewNode->Ptr)
			{
				PrevClosestNode = ClosestNode;
				ClosestNode = ClosestNode->LinkedRight;
			}
			else
			{
				//if previous fell off the left side of the linked list, exit as we
				//dont want to go any farther
				if(PrevClosestNode == &RedBlackNULLNode)
					break;
				
				//closest is on the right, if previous is not on the left then head left as
				//we are too far
				if(PrevClosestNode->Ptr > NewNode->Ptr)
				{
					//we want to keep PrevClosestNode to the left of Closest node so we
					//have to change how we move from normal mentality
					ClosestNode = PrevClosestNode;
					PrevClosestNode = PrevClosestNode->LinkedLeft;
				}
				else
				{
					//we found our position, exit
					break;
				}
			}
		}

		//we either exited due to hitting the end of the linked list on the right side
		//or PrevClosestNode went off the left side
		//or we found a center in the list to add us
	}
	else
	{
		//we have a closestnode in the alloc tree, walk the rest of the chain as there may
		//be a free node to skip

		//now, walk the chain until we get to the end or past us as we may have a free
		//block to go past
		PrevClosestNode = NULL;
		while((ClosestNode != &RedBlackNULLNode) && (ClosestNode->Ptr < NewNode->Ptr))
		{
			PrevClosestNode = ClosestNode;
			ClosestNode = ClosestNode->LinkedRight;
		}
	}

	//ok, prevclosestnode is now the node before us in the linked list, setup the
	//linked list for the new node
	NewNode->LinkedLeft = PrevClosestNode;
	NewNode->LinkedRight = ClosestNode;

	//modify the original chain
	if(PrevClosestNode != &RedBlackNULLNode)
		PrevClosestNode->LinkedRight = NewNode;
	if(ClosestNode != &RedBlackNULLNode)
		ClosestNode->LinkedLeft = NewNode;

	//wipe out the type setting to make sure it doesnt have invalid values
	NewNode->Type = 0;
	
	//return the new allocation
	return NewNode;
}

deBoolean deMemoryManager::IsInitialized()
{
	//return if we initialized
	return Initialized;
}

void * deMemoryManager::Malloc(unsigned int Size, MallocType Type, const char *File, long Line)
{
	DWORD			NewSize;
	RedBlackNode	*CurFreeNode;
	RedBlackNode	*NewAllocNode;

	//allocate a chunk of memory

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

	//find a free node to use
	CurFreeNode = FindRedBlackTreeNodeFree(RootFreeNode, Size);

	//if no current free node, go get a new node
	NewSize = Size;
	if(CurFreeNode == &RedBlackNULLNode)
	{
		//no free node, allocate a new node
		CurFreeNode = AllocRealMem(&NewSize);
	}
	else
	{
		//remove the node from the tree
		DeleteRedBlackTreeNode(&RootFreeNode, CurFreeNode);
	}

	//if the node's size does not exactly match, we need to allocate a new node
	if(CurFreeNode->Size != Size)
	{
		//allocate a new node that we will actually allocate with
		NewAllocNode = (RedBlackNode *)InternalAlloc(sizeof(RedBlackNode));
		if(!NewAllocNode)
			return NULL;	//something is seriously wrong

		//setup the new alloc node
		NewAllocNode->Type = 0;
		NewAllocNode->ExtraData = NULL;
		NewAllocNode->Size = Size;
		NewAllocNode->Ptr = CurFreeNode->Ptr;

		//modify the free node for it's size and pointer
		CurFreeNode->Size = CurFreeNode->Size - Size;
		CurFreeNode->Ptr = (void *)((DWORD)CurFreeNode->Ptr + Size);

		//change the linked left/right
		NewAllocNode->LinkedLeft = CurFreeNode->LinkedLeft;
		NewAllocNode->LinkedRight = CurFreeNode;
		CurFreeNode->LinkedLeft = NewAllocNode;

		//if there is a linked left value, tell it it's new linked right
		if(NewAllocNode->LinkedLeft != &RedBlackNULLNode)
			NewAllocNode->LinkedLeft->LinkedRight = NewAllocNode;
	}
	else
	{
		//setup the actual allocate node
		NewAllocNode = CurFreeNode;
		CurFreeNode = NULL;
	}

	//insert our alloc node
	InsertRedBlackTreeNodeAlloc(&RootAllocNode, NewAllocNode);

	if(CurFreeNode == &RedBlackNULLNode)
		return NULL;

	//if we have a current free node, insert it into the free tree
	if(CurFreeNode)
		InsertRedBlackTreeNodeFree(&RootFreeNode, CurFreeNode);

	//if this is calloc, wipe out the memory
	if(Type == deMemoryManager::Calloc)
		InternalFunctions->MemSet(NewAllocNode->Ptr, 0, NewAllocNode->Size);

	//return a pointer to the data
	return NewAllocNode->Ptr;
}

void deMemoryManager::Free(void *Ptr, FreeType Type, const char *File, long Line)
{
	RedBlackNode	*AllocNode;

	//take memory and put it into the free chain
	AllocNode = FindRedBlackTreeNodeAlloc(RootAllocNode, Ptr);
	if(AllocNode == &RedBlackNULLNode)
		return;		//something is wrong

	//remove it from the alloc tree
	DeleteRedBlackTreeNode(&RootAllocNode, AllocNode);
	
	//add it to the free tree
	InsertRedBlackTreeNodeFree(&RootFreeNode, AllocNode);

	//all done
	return;
}

void *deMemoryManager::MemCpy(void *To, const void *From, unsigned int Size, const char *File, long Line)
{
	return InternalFunctions->MemCpy(To, From, Size);
}

void *deMemoryManager::MemSet(void *To, int Value, unsigned int Size, const char *File, long Line)
{
	return InternalFunctions->MemSet(To, Value, Size);
}