Main Page Modules Namespace List Class Hierarchy Alphabetical List Compound List File List Namespace Members Compound Members File Members Related Pages

# RedBlackTree.hpp

Go to the documentation of this file.

    00001 ///////////////////////////////////////////////////////////////////////////////
    00002 /// @file RedBlackTree.hpp
    00003 ///
    00004 /// @brief Destiny3D Red/Black Tree Manager for Memory Manager
    00005 ///
    00006 /// @author Lightning
    00007 ///
    00008 /// This file is the intellectual property of Novus Delta, LLC.. Usage of the
    00009 /// contents of this file is subject to the Destiny3D Member License which
    00010 /// can be found at http://www.destiny3d.com.  Any other usage is prohibited.
    00011 ///
    00012 /// This file is distributed "AS IS" without warranty of any kind.  Novus
    00013 /// Delta, LLC. does not guarantee the fitness of the contents of this file
    00014 /// for any particular purpose.
    00015 ///
    00016 /// Copyright (C) 2001-2003 Novus Delta, LLC. All Rights Reserved.
    00017 ///
    00018 /// <hr>
    00019 ///                                 Change History
    00020 /// <hr>
    00021 ///
    00022 /// @date Oct 2002
    00023 /// @author Lightning
    00024 /// @remarks Creation
    00025 ///
    00026 ///////////////////////////////////////////////////////////////////////////////
    00027
    00028 #include "deGlobalTypes.hpp"
    00029 #include "deMemory_priv.hpp"
    00030
    00031 #ifndef REDBLACK_TREE_HPP
    00032 #define REDBLACK_TREE_HPP
    00033
    00034 //flags and defines for the flags for checking/setting them in the red/black tree node
    00035
    00036 //type of nodes for the red/black tree
    00037 #define REDBLACKNODE_FREE       0x0000
    00038 #define REDBLACKNODE_ALLOC      0x0001
    00039
    00040 //set a node free or alloc
    00041 #define SetNodeFree(Node) Node->Type = Node->Type & ~REDBLACKNODE_ALLOC;
    00042 #define SetNodeAlloc(Node) Node->Type = Node->Type | REDBLACKNODE_ALLOC;
    00043
    00044 //is a node free or alloc
    00045 #define IsNodeFree(Node) (!IsNodeAlloc(Node))
    00046 #define IsNodeAlloc(Node) (Node->Type & REDBLACKNODE_ALLOC)
    00047
    00048
    00049 //red or black node entry
    00050 #define REDBLACKNODE_BLACK      0x0000
    00051 #define REDBLACKNODE_RED        0x0002
    00052
    00053 //set a node black or red
    00054 #define SetNodeBlack(Node) Node->Type = Node->Type & ~REDBLACKNODE_RED;
    00055 #define SetNodeRed(Node) Node->Type = Node->Type | REDBLACKNODE_RED;
    00056
    00057 //is a node black or red
    00058 #define IsNodeBlack(Node) (!IsNodeRed(Node))
    00059 #define IsNodeRed(Node) (Node->Type & REDBLACKNODE_RED)
    00060
    00061
    00062 //define the common node data
    00063 typedef struct RedBlackNode
    00064 {
    00065     DWORD                   Type;           //type of node (free/alloc/etc) and Color (Black/Red)
    00066     struct RedBlackNode     *Left;          //node with a smaller size
    00067     struct RedBlackNode     *Right;         //node with a larger size
    00068     struct RedBlackNode     *Parent;        //the parent node
    00069
    00070     struct RedBlackNode     *LinkedLeft;    //pointer to the node entry to the left of Ptr
    00071     struct RedBlackNode     *LinkedRight;   //pointer to the node entry to the right of Ptr
    00072                                             //note, the end points in the linked list end with RedBlackNULLNode
    00073
    00074     DWORD                   Size;           //size of the memory space
    00075     void *                  Ptr;            //pointer to the memory space
    00076
    00077     union
    00078     {
    00079         void                *ExtraData;     //used for alloc nodes, pointer to extra data about the allocation
    00080         struct RedBlackNode *Brother;       //used for free nodes, the brother entry of a node
    00081     };
    00082 } RedBlackNode;
    00083
    00084 //export the redblack null node
    00085 extern RedBlackNode RedBlackNULLNode;
    00086
    00087 //information about the above structure
    00088 //The brother entry is only used for free blocks and points to the first node of the same size as the parent
    00089 //all Brother nodes use left/right to point to each other and Parent = NULL.
    00090 //LinkedLeft and LinkedRight are all the blocks (free and alloc) in order based on ptr
    00091 //Parent is set to &RedBlackNULLNode for the Root entry to distinguish from Brother nodes
    00092
    00093 //red/black tree functions
    00094
    00095 //insert and remove tree nodes
    00096 deBoolean InsertRedBlackTreeNodeAlloc(RedBlackNode **Root, RedBlackNode *AllocNode);
    00097 deBoolean InsertRedBlackTreeNodeFree(RedBlackNode **Root, RedBlackNode *FreeNode);
    00098 void DeleteRedBlackTreeNode(RedBlackNode **Root, RedBlackNode *Node);
    00099
    00100 //find a tree node
    00101 RedBlackNode *FindRedBlackTreeNodeAlloc(RedBlackNode *Root, void *Ptr);
    00102 RedBlackNode *FindClosestRedBlackTreeNodePtr(RedBlackNode *Root, void *Ptr);
    00103 RedBlackNode *FindRedBlackTreeNodeFree(RedBlackNode *Root, DWORD Size);
    00104
    00105 #endif