///////////////////////////////////////////////////////////////////////////////
/// @file RedBlackTree.hpp
///
/// @brief Destiny3D Red/Black Tree 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 Oct 2002
/// @author Lightning
/// @remarks Creation
///
///////////////////////////////////////////////////////////////////////////////

#include "deGlobalTypes.hpp"
#include "deMemory_priv.hpp"

#ifndef REDBLACK_TREE_HPP
#define REDBLACK_TREE_HPP

//flags and defines for the flags for checking/setting them in the red/black tree node

//type of nodes for the red/black tree
#define REDBLACKNODE_FREE		0x0000
#define REDBLACKNODE_ALLOC		0x0001

//set a node free or alloc
#define SetNodeFree(Node) Node->Type = Node->Type & ~REDBLACKNODE_ALLOC;
#define SetNodeAlloc(Node) Node->Type = Node->Type | REDBLACKNODE_ALLOC;

//is a node free or alloc
#define IsNodeFree(Node) (!IsNodeAlloc(Node))
#define IsNodeAlloc(Node) (Node->Type & REDBLACKNODE_ALLOC)


//red or black node entry
#define REDBLACKNODE_BLACK		0x0000
#define REDBLACKNODE_RED		0x0002

//set a node black or red
#define SetNodeBlack(Node) Node->Type = Node->Type & ~REDBLACKNODE_RED;
#define SetNodeRed(Node) Node->Type = Node->Type | REDBLACKNODE_RED;

//is a node black or red
#define IsNodeBlack(Node) (!IsNodeRed(Node))
#define IsNodeRed(Node) (Node->Type & REDBLACKNODE_RED)


//define the common node data
typedef struct RedBlackNode
{
	DWORD					Type;			//type of node (free/alloc/etc) and Color (Black/Red)
	struct RedBlackNode		*Left;			//node with a smaller size
	struct RedBlackNode		*Right;			//node with a larger size
	struct RedBlackNode		*Parent;		//the parent node

	struct RedBlackNode		*LinkedLeft;	//pointer to the node entry to the left of Ptr
	struct RedBlackNode		*LinkedRight;	//pointer to the node entry to the right of Ptr
											//note, the end points in the linked list end with RedBlackNULLNode
	
	DWORD					Size;			//size of the memory space
	void *					Ptr;			//pointer to the memory space

	union
	{
		void				*ExtraData;		//used for alloc nodes, pointer to extra data about the allocation
		struct RedBlackNode *Brother;		//used for free nodes, the brother entry of a node
	};
} RedBlackNode;

//export the redblack null node
extern RedBlackNode RedBlackNULLNode;

//information about the above structure
//The brother entry is only used for free blocks and points to the first node of the same size as the parent
//all Brother nodes use left/right to point to each other and Parent = NULL.
//LinkedLeft and LinkedRight are all the blocks (free and alloc) in order based on ptr
//Parent is set to &RedBlackNULLNode for the Root entry to distinguish from Brother nodes

//red/black tree functions

//insert and remove tree nodes
deBoolean InsertRedBlackTreeNodeAlloc(RedBlackNode **Root, RedBlackNode *AllocNode);
deBoolean InsertRedBlackTreeNodeFree(RedBlackNode **Root, RedBlackNode *FreeNode);
void DeleteRedBlackTreeNode(RedBlackNode **Root, RedBlackNode *Node);

//find a tree node
RedBlackNode *FindRedBlackTreeNodeAlloc(RedBlackNode *Root, void *Ptr);
RedBlackNode *FindClosestRedBlackTreeNodePtr(RedBlackNode *Root, void *Ptr);
RedBlackNode *FindRedBlackTreeNodeFree(RedBlackNode *Root, DWORD Size);

#endif