2955 lines
60 KiB
C
2955 lines
60 KiB
C
/*++
|
|
|
|
Copyright (c) 1996-1999 Microsoft Corporation
|
|
|
|
Module Name:
|
|
|
|
bintree.c
|
|
|
|
Abstract:
|
|
|
|
Routines that manage the binary trees in the memdb database
|
|
|
|
Author:
|
|
|
|
Matthew Vanderzee (mvander) 13-Aug-1999
|
|
|
|
--*/
|
|
|
|
|
|
#include "pch.h"
|
|
|
|
// PORTBUG: Make sure to pick up latest fixes in win9xupg project
|
|
|
|
//
|
|
// Includes
|
|
//
|
|
|
|
#include "memdbp.h"
|
|
#include "bintree.h"
|
|
|
|
//
|
|
// Strings
|
|
//
|
|
|
|
// None
|
|
|
|
//
|
|
// Constants
|
|
//
|
|
|
|
#define NODESTRUCT_SIZE_MAIN (4*sizeof(UINT) + sizeof(WORD))
|
|
#define BINTREE_SIZE_MAIN sizeof(UINT)
|
|
#define LISTELEM_SIZE_MAIN (3*sizeof(UINT))
|
|
|
|
#ifdef DEBUG
|
|
|
|
#define NODESTRUCT_HEADER_SIZE (sizeof(DWORD)+sizeof(BOOL))
|
|
#define NODESTRUCT_SIZE ((WORD)(NODESTRUCT_SIZE_MAIN + (g_UseDebugStructs ? NODESTRUCT_HEADER_SIZE : 0)))
|
|
|
|
#define BINTREE_HEADER_SIZE (sizeof(DWORD)+2*sizeof(INT)+sizeof(BOOL))
|
|
#define BINTREE_SIZE ((WORD)(BINTREE_SIZE_MAIN + (g_UseDebugStructs ? BINTREE_HEADER_SIZE : 0)))
|
|
|
|
#define LISTELEM_HEADER_SIZE sizeof(DWORD)
|
|
#define LISTELEM_SIZE ((WORD)(LISTELEM_SIZE_MAIN + (g_UseDebugStructs ? LISTELEM_HEADER_SIZE : 0)))
|
|
|
|
#else
|
|
|
|
#define NODESTRUCT_SIZE ((WORD)NODESTRUCT_SIZE_MAIN)
|
|
#define BINTREE_SIZE ((WORD)BINTREE_SIZE_MAIN)
|
|
#define LISTELEM_SIZE ((WORD)LISTELEM_SIZE_MAIN)
|
|
|
|
#endif
|
|
|
|
|
|
//
|
|
// Macros
|
|
//
|
|
|
|
#define MAX(a,b) (a>b ? a : b)
|
|
#define ABS(x) (x<0 ? -x : x)
|
|
|
|
#ifdef DEBUG
|
|
|
|
//
|
|
// if BINTREECHECKTREEBALANCE is true, every addition or deletion
|
|
// or rotation checks to make sure tree is balanced and
|
|
// correct. this of course take a lot of time.
|
|
//
|
|
#define BINTREECHECKTREEBALANCE FALSE
|
|
|
|
#define INITTREENODES(tree) { if (g_UseDebugStructs) { tree->NodeAlloc=0; } }
|
|
#define INCTREENODES(tree) { if (g_UseDebugStructs) { tree->NodeAlloc++; } }
|
|
#define DECTREENODES(tree) { if (g_UseDebugStructs) { tree->NodeAlloc--; } }
|
|
#define TESTTREENODES(tree) { if (g_UseDebugStructs) { MYASSERT(tree->NodeAlloc==0); } }
|
|
#define INITTREEELEMS(tree) { if (g_UseDebugStructs) { tree->ElemAlloc=0; } }
|
|
#define INCTREEELEMS(tree) { if (g_UseDebugStructs) { tree->ElemAlloc++; } }
|
|
#define DECTREEELEMS(tree) { if (g_UseDebugStructs) { tree->ElemAlloc--; } }
|
|
#define TESTTREEELEMS(tree) { if (g_UseDebugStructs) { MYASSERT(tree->ElemAlloc==0); } }
|
|
|
|
#else
|
|
|
|
#define BINTREECHECKTREEBALANCE
|
|
|
|
#define INITTREENODES(tree)
|
|
#define INCTREENODES(tree)
|
|
#define DECTREENODES(tree)
|
|
#define TESTTREENODES(tree)
|
|
#define INITTREEELEMS(tree)
|
|
#define INCTREEELEMS(tree)
|
|
#define DECTREEELEMS(tree)
|
|
#define TESTTREEELEMS(tree)
|
|
|
|
#endif
|
|
|
|
#if defined(DEBUG)
|
|
#if BINTREECHECKTREEBALANCE
|
|
|
|
#define TESTNODETREE(node) MYASSERT(pBinTreeCheckBalance(node));
|
|
#define TESTTREE(tree) MYASSERT(pBinTreeCheck(tree));
|
|
|
|
#else
|
|
|
|
#define TESTNODETREE(node)
|
|
#define TESTTREE(tree)
|
|
|
|
#endif
|
|
|
|
#else
|
|
|
|
#define TESTNODETREE(node)
|
|
#define TESTTREE(tree)
|
|
|
|
#endif
|
|
|
|
//
|
|
// Types
|
|
//
|
|
|
|
typedef struct {
|
|
|
|
#ifdef DEBUG
|
|
DWORD Signature;
|
|
BOOL Deleted;
|
|
#endif
|
|
|
|
union {
|
|
struct { //for normal nodes
|
|
UINT Data; //offset of data structure
|
|
UINT Left; //offset of left child
|
|
UINT Right; //offset of right child
|
|
UINT Parent; //offset of parent
|
|
};//lint !e657
|
|
struct { //for the InsertionOrdered list header node (tree->Root points to this)
|
|
UINT Root; //offset of actual root of tree
|
|
UINT Head; //head of insertion ordered list
|
|
UINT Tail; //tail of insertion ordered list
|
|
};//lint !e657
|
|
UINT NextDeleted; //offset of next deleted node
|
|
};
|
|
|
|
|
|
struct {
|
|
WORD InsertionOrdered : 1; //flag, 1 if insertion-ordered (only really needed
|
|
//by enumeration methods, because to save space
|
|
//there is no tree pointer in the NODESTRUCT, but
|
|
//we need a way for enumeration methods to know if
|
|
//node->Data is the offset of the data or the
|
|
//offset of a LISTELEM (which it is when we are in
|
|
//insertion-ordered mode)).
|
|
WORD InsertionHead : 1; //flag, 1 if this node is the head of insertion
|
|
//ordered tree.
|
|
WORD LeftDepth : 7; //depths of subtrees. these can be 7 bits because
|
|
WORD RightDepth : 7; //if depth got up to near 128, the approximate
|
|
//number of nodes would be 1e35.
|
|
};//lint !e657
|
|
} NODESTRUCT, *PNODESTRUCT;
|
|
|
|
//
|
|
// normally, the BINTREE structure simply has the offset
|
|
// of the root node of the tree in its Root member. but
|
|
// when we are in insertion-ordered mode, we have an extra
|
|
// node whose offset is stored in the BINTREE->Root. this
|
|
// Header Node points to the head of the insertion-ordered
|
|
// linked list, the tail of the list, and the actual root
|
|
// of the binary tree.
|
|
//
|
|
|
|
typedef struct {
|
|
|
|
#ifdef DEBUG
|
|
|
|
DWORD Signature;
|
|
INT NodeAlloc; // counter for number of nodes allocated
|
|
INT ElemAlloc; // counter for number of elems allocated
|
|
BOOL Deleted; // flag which is TRUE if tree is deleted
|
|
|
|
#endif
|
|
|
|
union {
|
|
UINT Root; // offset of top level NODESTRUCT
|
|
UINT NextDeleted; // offset of next deleted tree
|
|
};
|
|
|
|
} BINTREE, *PBINTREE;
|
|
|
|
//
|
|
// if we are in insertion-ordered mode, that means every
|
|
// enumeration will be in the order that we added the
|
|
// data. to do this, we use a linked list with the binary
|
|
// tree. the data member of the NODESTRUCT holds the
|
|
// offset of the LISTELEM structure, and the data member
|
|
// of the LISTELEM structure holds the offset of the data.
|
|
// To enumerate, we just walk the linked list in order.
|
|
//
|
|
|
|
typedef struct {
|
|
|
|
#ifdef DEBUG
|
|
DWORD Signature;
|
|
#endif
|
|
|
|
union {
|
|
struct {
|
|
UINT Next; // offset of next element in list
|
|
UINT Data; // offset of data structure this element is for
|
|
UINT Node; // offset of NODESTRUCT this listelem corresponds to
|
|
};//lint !e657
|
|
UINT NextDeleted;
|
|
};
|
|
|
|
} LISTELEM, *PLISTELEM;
|
|
|
|
//
|
|
// Globals
|
|
//
|
|
|
|
//
|
|
// Macro expansion list
|
|
//
|
|
|
|
// None
|
|
|
|
//
|
|
// Private function prototypes
|
|
//
|
|
|
|
PNODESTRUCT
|
|
pBinTreeFindNode (
|
|
IN PBINTREE Tree,
|
|
IN PCWSTR String
|
|
);
|
|
|
|
PNODESTRUCT
|
|
pBinTreeEnumFirst (
|
|
IN PBINTREE Tree
|
|
);
|
|
|
|
PNODESTRUCT
|
|
pBinTreeEnumNext (
|
|
IN OUT PNODESTRUCT CurrentNode
|
|
);
|
|
|
|
PNODESTRUCT
|
|
pBinTreeAllocNode (
|
|
OUT PUINT Offset
|
|
);
|
|
|
|
PBINTREE
|
|
pBinTreeAllocTree (
|
|
OUT PUINT Offset
|
|
);
|
|
|
|
PLISTELEM
|
|
pBinTreeAllocListElem (
|
|
OUT PUINT Offset
|
|
);
|
|
|
|
VOID
|
|
pBinTreeFreeNode (
|
|
PNODESTRUCT Node
|
|
);
|
|
|
|
VOID
|
|
pBinTreeFreeTree (
|
|
PBINTREE Tree
|
|
);
|
|
|
|
VOID
|
|
pBinTreeFreeListElem (
|
|
PLISTELEM Elem
|
|
);
|
|
|
|
VOID
|
|
pBinTreeDestroy (
|
|
PNODESTRUCT Node,
|
|
PBINTREE Tree
|
|
);
|
|
|
|
//
|
|
// This starts at node and moves up tree balancing.
|
|
// The function stops moving up when it finds a node
|
|
// which has no change in depth values and/or no balancing
|
|
// to be done. Otherwise, it goes all the way to top.
|
|
// Carry TreeOffset through for rotate functions
|
|
//
|
|
VOID
|
|
pBinTreeBalanceUpward (
|
|
IN PNODESTRUCT Node,
|
|
IN UINT TreeOffset
|
|
);
|
|
|
|
//
|
|
// After pBinTreeNodeBalance, parent of node could have incorrect
|
|
// depth values and might need rebalancing.
|
|
// Carry TreeOffset through for rotate functions.
|
|
// Assumes children of 'node' are balanced.
|
|
// Returns true if node rebalanced or if depth values changed.
|
|
//
|
|
BOOL
|
|
pBinTreeNodeBalance (
|
|
IN PNODESTRUCT Node,
|
|
IN UINT TreeOffset
|
|
);
|
|
|
|
//
|
|
// After using the following rotate functions, the parents of node
|
|
// could have incorrect depth values, and could need rebalancing.
|
|
// We do not have double-rotate functions because that is taken
|
|
// care of inside these. Need TreeOffset just in case node is top node
|
|
//
|
|
VOID
|
|
pBinTreeRotateRight (
|
|
IN PNODESTRUCT Node,
|
|
IN UINT TreeOffset
|
|
);
|
|
|
|
VOID
|
|
pBinTreeRotateLeft (
|
|
IN PNODESTRUCT Node,
|
|
IN UINT TreeOffset
|
|
);
|
|
|
|
|
|
#ifdef DEBUG
|
|
|
|
INT
|
|
pBinTreeCheckBalance (
|
|
IN PNODESTRUCT Node
|
|
);
|
|
|
|
INT
|
|
pBinTreeCheck (
|
|
IN PBINTREE Tree
|
|
);
|
|
|
|
#endif
|
|
|
|
//
|
|
// Macro expansion definition
|
|
//
|
|
|
|
// None
|
|
|
|
//
|
|
// Code
|
|
//
|
|
|
|
//
|
|
// If we are in debug mode, these conversions
|
|
// are implemented as functions, so we can
|
|
// check for errors. If we are not in debug
|
|
// mode, the conversions are simple macros.
|
|
//
|
|
#ifdef DEBUG
|
|
|
|
UINT
|
|
GetNodeOffset (
|
|
IN PNODESTRUCT Node
|
|
)
|
|
{
|
|
if (!Node) {
|
|
return INVALID_OFFSET;
|
|
}
|
|
|
|
if (!g_UseDebugStructs) {
|
|
return PTR_TO_OFFSET(Node) + NODESTRUCT_HEADER_SIZE;
|
|
}
|
|
|
|
MYASSERT (Node->Signature == NODESTRUCT_SIGNATURE);
|
|
|
|
return PTR_TO_OFFSET(Node);
|
|
}
|
|
|
|
|
|
UINT
|
|
GetTreeOffset (
|
|
PBINTREE Tree
|
|
)
|
|
{
|
|
|
|
if (!Tree) {
|
|
return INVALID_OFFSET;
|
|
}
|
|
|
|
if (!g_UseDebugStructs) {
|
|
return PTR_TO_OFFSET(Tree) + BINTREE_HEADER_SIZE;
|
|
}
|
|
|
|
MYASSERT (Tree->Signature == BINTREE_SIGNATURE);
|
|
|
|
return PTR_TO_OFFSET(Tree);
|
|
}
|
|
|
|
|
|
UINT
|
|
GetListElemOffset (
|
|
PLISTELEM Elem
|
|
)
|
|
{
|
|
if (!Elem) {
|
|
return INVALID_OFFSET;
|
|
}
|
|
|
|
if (!g_UseDebugStructs) {
|
|
return PTR_TO_OFFSET(Elem) + LISTELEM_HEADER_SIZE;
|
|
}
|
|
|
|
MYASSERT (Elem->Signature == LISTELEM_SIGNATURE);
|
|
|
|
return PTR_TO_OFFSET(Elem);
|
|
}
|
|
|
|
|
|
PNODESTRUCT
|
|
GetNodeStruct (
|
|
UINT Offset
|
|
)
|
|
{
|
|
PNODESTRUCT node;
|
|
|
|
if (Offset == INVALID_OFFSET) {
|
|
return NULL;
|
|
}
|
|
|
|
if (!g_UseDebugStructs) {
|
|
return (PNODESTRUCT) OFFSET_TO_PTR(Offset - NODESTRUCT_HEADER_SIZE);
|
|
}
|
|
|
|
node = (PNODESTRUCT) OFFSET_TO_PTR(Offset);
|
|
|
|
MYASSERT (node->Signature == NODESTRUCT_SIGNATURE);
|
|
|
|
return node;
|
|
}
|
|
|
|
|
|
PBINTREE
|
|
GetBinTree (
|
|
UINT Offset
|
|
)
|
|
{
|
|
PBINTREE tree;
|
|
|
|
if (Offset == INVALID_OFFSET) {
|
|
return NULL;
|
|
}
|
|
|
|
if (!g_UseDebugStructs) {
|
|
return (PBINTREE) OFFSET_TO_PTR(Offset - BINTREE_HEADER_SIZE);
|
|
}
|
|
|
|
tree = (PBINTREE) OFFSET_TO_PTR(Offset);
|
|
|
|
MYASSERT (tree->Signature == BINTREE_SIGNATURE);
|
|
|
|
return tree;
|
|
}
|
|
|
|
|
|
PLISTELEM
|
|
GetListElem (
|
|
UINT Offset
|
|
)
|
|
{
|
|
PLISTELEM elem;
|
|
|
|
if (Offset == INVALID_OFFSET) {
|
|
return NULL;
|
|
}
|
|
|
|
if (!g_UseDebugStructs) {
|
|
return (PLISTELEM) OFFSET_TO_PTR(Offset - LISTELEM_HEADER_SIZE);
|
|
}
|
|
|
|
elem = (PLISTELEM) OFFSET_TO_PTR(Offset);
|
|
|
|
MYASSERT (elem->Signature == LISTELEM_SIGNATURE);
|
|
|
|
return elem;
|
|
}
|
|
|
|
#else
|
|
|
|
#define GetNodeOffset(Node) ((Node) ? \
|
|
PTR_TO_OFFSET(Node) : \
|
|
INVALID_OFFSET)
|
|
|
|
#define GetTreeOffset(Tree) ((Tree) ? \
|
|
PTR_TO_OFFSET(Tree) : \
|
|
INVALID_OFFSET)
|
|
|
|
#define GetListElemOffset(Elem) ((Elem) ? \
|
|
PTR_TO_OFFSET(Elem) : \
|
|
INVALID_OFFSET)
|
|
|
|
#define GetNodeStruct(Offset) (((Offset) == INVALID_OFFSET) ? \
|
|
NULL : \
|
|
(PNODESTRUCT) OFFSET_TO_PTR(Offset))
|
|
|
|
#define GetBinTree(Offset) (((Offset) == INVALID_OFFSET) ? \
|
|
NULL : \
|
|
(PBINTREE) OFFSET_TO_PTR(Offset))
|
|
|
|
#define GetListElem(Offset) (((Offset) == INVALID_OFFSET) ? \
|
|
NULL : \
|
|
(PLISTELEM)OFFSET_TO_PTR(Offset))
|
|
|
|
|
|
#endif
|
|
|
|
|
|
//
|
|
// GetNodeData - takes a node and gets the data
|
|
// structure offset
|
|
//
|
|
// GetNodeDataStr - takes a node and gets the
|
|
// pascal-style string in the data structure offset
|
|
//
|
|
|
|
#define GetNodeData(Node) ((Node)->InsertionOrdered ? \
|
|
GetListElem((Node)->Data)->Data : \
|
|
(Node)->Data)
|
|
|
|
#define GetNodeDataStr(Node) (GetDataStr(GetNodeData(Node)))
|
|
|
|
|
|
PNODESTRUCT
|
|
GetTreeRoot (
|
|
IN PBINTREE Tree
|
|
)
|
|
{
|
|
PNODESTRUCT cur;
|
|
|
|
if (!Tree || Tree->Root == INVALID_OFFSET) {
|
|
return NULL;
|
|
}
|
|
|
|
cur = GetNodeStruct (Tree->Root);
|
|
|
|
if (cur->InsertionHead) {
|
|
return GetNodeStruct (cur->Root);
|
|
} else {
|
|
return cur;
|
|
}
|
|
}
|
|
|
|
|
|
VOID
|
|
pSetTreeRoot (
|
|
IN PBINTREE Tree,
|
|
IN UINT Offset
|
|
)
|
|
{
|
|
PNODESTRUCT cur;
|
|
|
|
if (!Tree) {
|
|
return;
|
|
}
|
|
|
|
cur = GetNodeStruct(Tree->Root);
|
|
|
|
if (cur && cur->InsertionHead) {
|
|
cur->Root = Offset;
|
|
} else {
|
|
Tree->Root = Offset;
|
|
}
|
|
}
|
|
|
|
#define IsTreeInsertionOrdered(Tree) ((Tree) ? \
|
|
((Tree)->Root==INVALID_OFFSET ? \
|
|
FALSE : \
|
|
GetNodeStruct((Tree)->Root)->InsertionHead) : \
|
|
FALSE)
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
UINT
|
|
BinTreeNew (
|
|
VOID
|
|
)
|
|
|
|
/*++
|
|
|
|
Routine Description:
|
|
|
|
BinTreeNew creates a new binary tree data structure. This is done when a new
|
|
node is created via a set operation of some sort. Additional items are added
|
|
to the binary tree via BinTreeAddNode.
|
|
|
|
Arguments:
|
|
|
|
None.
|
|
|
|
Return Value:
|
|
|
|
The offset to the new tree.
|
|
|
|
Comments:
|
|
|
|
This function assumes that it cannot fail, because if a low-level memory
|
|
routine fails, the process will die.
|
|
|
|
The database heap might be moved by the allocation request, and could
|
|
invalidate pointers. The caller must use care not to use pointers until
|
|
after this routine returns, or it must re-convert offsets into new pointers.
|
|
|
|
--*/
|
|
|
|
{
|
|
UINT treeOffset;
|
|
PBINTREE tree;
|
|
|
|
tree = pBinTreeAllocTree (&treeOffset);
|
|
if (!tree) {
|
|
return INVALID_OFFSET;
|
|
}
|
|
|
|
tree->Root = INVALID_OFFSET;
|
|
|
|
INITTREENODES(tree);
|
|
INITTREEELEMS(tree);
|
|
|
|
return treeOffset;
|
|
}
|
|
|
|
|
|
BOOL
|
|
BinTreeAddNode (
|
|
IN UINT TreeOffset,
|
|
IN UINT Data
|
|
)
|
|
|
|
/*++
|
|
|
|
Routine Description:
|
|
|
|
BinTreeAddNode adds a new item to an existing binary tree.
|
|
|
|
Arguments:
|
|
|
|
TreeOffset - Indicates the root of the binary tree, as returned by
|
|
BinTreeNew.
|
|
Data - Specifies the offset of the data structure containing the
|
|
node to insert. The string address is computed from Data via
|
|
GetDataStr.
|
|
|
|
Return Value:
|
|
|
|
TRUE if the insertion operation succeeded, FALSE if the item is already in
|
|
the tree.
|
|
|
|
--*/
|
|
|
|
{
|
|
UINT nodeOffset;
|
|
UINT elemOffset;
|
|
UINT parentOffset;
|
|
PNODESTRUCT node;
|
|
PNODESTRUCT cur;
|
|
PNODESTRUCT parent;
|
|
PBINTREE tree;
|
|
PLISTELEM elem;
|
|
INT cmp;
|
|
PCWSTR dataStr;
|
|
|
|
if (TreeOffset == INVALID_OFFSET) {
|
|
return FALSE;
|
|
}
|
|
|
|
//
|
|
// Keep track of initial database pointer. If it changes, we need
|
|
// to readjust our pointers.
|
|
//
|
|
|
|
tree = GetBinTree (TreeOffset);
|
|
|
|
if (!GetTreeRoot (tree)) {
|
|
|
|
//
|
|
// No root case -- add this item as the root
|
|
//
|
|
|
|
node = pBinTreeAllocNode (&nodeOffset);
|
|
if (!node) {
|
|
return FALSE;
|
|
}
|
|
|
|
PTR_WAS_INVALIDATED(tree);
|
|
|
|
tree = GetBinTree (TreeOffset);
|
|
INCTREENODES (tree);
|
|
|
|
pSetTreeRoot (tree, nodeOffset);
|
|
|
|
node->Parent = INVALID_OFFSET;
|
|
parentOffset = INVALID_OFFSET;
|
|
parent = NULL;
|
|
|
|
} else {
|
|
|
|
//
|
|
// Existing root case -- try to find the item, then if it does
|
|
// not exist, add it.
|
|
//
|
|
|
|
cur = GetTreeRoot (tree);
|
|
dataStr = GetDataStr (Data);
|
|
|
|
do {
|
|
cmp = StringPasICompare (dataStr, GetNodeDataStr (cur));
|
|
|
|
if (!cmp) {
|
|
//
|
|
// Node is already in tree
|
|
//
|
|
return FALSE;
|
|
}
|
|
|
|
//
|
|
// Go to left or right node, depending on search result
|
|
//
|
|
|
|
parentOffset = GetNodeOffset (cur);
|
|
|
|
if (cmp < 0) {
|
|
cur = GetNodeStruct(cur->Left);
|
|
} else {
|
|
cur = GetNodeStruct(cur->Right);
|
|
}
|
|
|
|
} while (cur);
|
|
|
|
//
|
|
// Node is not in the tree. Add it now.
|
|
//
|
|
|
|
node = pBinTreeAllocNode(&nodeOffset);
|
|
if (!node) {
|
|
return FALSE;
|
|
}
|
|
|
|
PTR_WAS_INVALIDATED(cur);
|
|
PTR_WAS_INVALIDATED(tree);
|
|
|
|
tree = GetBinTree (TreeOffset);
|
|
INCTREENODES (tree);
|
|
|
|
node->Parent = parentOffset;
|
|
parent = GetNodeStruct (parentOffset);
|
|
|
|
if (cmp < 0) {
|
|
parent->Left = nodeOffset;
|
|
} else {
|
|
parent->Right = nodeOffset;
|
|
}
|
|
}
|
|
|
|
//
|
|
// Verify the code above restored the tree pointer if
|
|
// an allocation occurred.
|
|
//
|
|
|
|
MYASSERT (tree == GetBinTree (TreeOffset));
|
|
|
|
//
|
|
// Initialize the new node
|
|
//
|
|
|
|
node->Left = INVALID_OFFSET;
|
|
node->Right = INVALID_OFFSET;
|
|
node->LeftDepth = 0;
|
|
node->RightDepth = 0;
|
|
node->InsertionHead = 0;
|
|
|
|
if (!IsTreeInsertionOrdered (tree)) {
|
|
//
|
|
// We are in sorted-order mode
|
|
//
|
|
|
|
node->Data = Data;
|
|
node->InsertionOrdered = 0;
|
|
|
|
} else {
|
|
//
|
|
// We are in insertion-ordered mode
|
|
//
|
|
|
|
elem = pBinTreeAllocListElem (&elemOffset);
|
|
if (!elem) {
|
|
return FALSE;
|
|
}
|
|
|
|
PTR_WAS_INVALIDATED(parent);
|
|
PTR_WAS_INVALIDATED(tree);
|
|
PTR_WAS_INVALIDATED(node);
|
|
|
|
parent = GetNodeStruct (parentOffset);
|
|
tree = GetBinTree (TreeOffset);
|
|
node = GetNodeStruct (nodeOffset);
|
|
|
|
INCTREEELEMS(tree);
|
|
|
|
node->InsertionOrdered = 1;
|
|
node->Data = elemOffset; // NODESTRUCT.Data is offset of list element
|
|
elem->Data = Data; // LISTELEM holds offset of data
|
|
elem->Node = nodeOffset; // LISTELEM points back to nodestruct
|
|
elem->Next = INVALID_OFFSET; // elem will be put at end of list
|
|
|
|
//now use node to point to list header
|
|
node = GetNodeStruct (tree->Root);
|
|
MYASSERT (node->InsertionHead);
|
|
|
|
if (node->Head == INVALID_OFFSET) { // if this is true, the list is empty
|
|
node->Head = elemOffset; // put elemOffset at beginning of the list
|
|
} else { // otherwise, put the new element at end of list
|
|
MYASSERT (node->Tail != INVALID_OFFSET);
|
|
GetListElem (node->Tail)->Next = elemOffset;
|
|
}
|
|
|
|
node->Tail = elemOffset; // new element is tail of list
|
|
}
|
|
|
|
pBinTreeBalanceUpward (parent, TreeOffset);
|
|
|
|
TESTTREE (GetBinTree (TreeOffset));
|
|
|
|
return TRUE;
|
|
}
|
|
|
|
|
|
UINT
|
|
BinTreeDeleteNode (
|
|
IN UINT TreeOffset,
|
|
IN PCWSTR Str,
|
|
OUT PBOOL LastNode OPTIONAL
|
|
)
|
|
|
|
/*++
|
|
|
|
Routine Description:
|
|
|
|
BinTreeDeleteNode removes a string from a binary tree.
|
|
|
|
Arguments:
|
|
|
|
TreeOffset - Specifies the binary tree to remove the string from
|
|
Str - Specifies the string to remove
|
|
LastNode - Receives TRUE if the binary tree became empty as a result of
|
|
the delete, FALSE otherwise
|
|
|
|
Return Value:
|
|
|
|
The data offset of the string that was deleted
|
|
|
|
--*/
|
|
|
|
{
|
|
PNODESTRUCT deleteNode;
|
|
PNODESTRUCT parent;
|
|
PNODESTRUCT replace;
|
|
UINT data;
|
|
UINT replaceOffset;
|
|
UINT deleteNodeOffset;
|
|
PNODESTRUCT startBalance;
|
|
PNODESTRUCT startBalance2 = NULL;
|
|
PBINTREE tree;
|
|
UINT elemOffset;
|
|
PLISTELEM elem;
|
|
PLISTELEM cur;
|
|
PNODESTRUCT header;
|
|
|
|
//
|
|
// after we delete a node, we have to start from somewhere and
|
|
// move up the tree, fixing the balance of nodes. startBalance
|
|
// is a pointer to the nodestruct to start at. in more complicated
|
|
// deletions, like when the deleted node has two children, and the
|
|
// replacement node is way down the tree, there are two places to
|
|
// start rebalancing from.
|
|
//
|
|
|
|
if (TreeOffset == INVALID_OFFSET) {
|
|
return INVALID_OFFSET;
|
|
}
|
|
|
|
tree = GetBinTree (TreeOffset);
|
|
|
|
deleteNode = pBinTreeFindNode (tree, Str);
|
|
if (deleteNode == NULL) {
|
|
return INVALID_OFFSET;
|
|
}
|
|
|
|
if (LastNode) {
|
|
*LastNode = FALSE;
|
|
}
|
|
|
|
deleteNodeOffset = GetNodeOffset (deleteNode);
|
|
parent = GetNodeStruct (deleteNode->Parent);
|
|
|
|
data = GetNodeData (deleteNode);
|
|
|
|
if (deleteNode->Right == INVALID_OFFSET && deleteNode->Left == INVALID_OFFSET) {
|
|
|
|
//
|
|
// deleteNode has no children
|
|
//
|
|
|
|
if (parent == NULL) {
|
|
|
|
if (LastNode) {
|
|
*LastNode = TRUE;
|
|
}
|
|
|
|
pSetTreeRoot(tree, INVALID_OFFSET);
|
|
|
|
} else {
|
|
|
|
if (parent->Left == deleteNodeOffset) {
|
|
parent->Left=INVALID_OFFSET;
|
|
} else {
|
|
parent->Right=INVALID_OFFSET;
|
|
}
|
|
|
|
}
|
|
|
|
startBalance = parent;
|
|
|
|
} else {
|
|
//
|
|
// deleteNode has one or two children
|
|
//
|
|
|
|
if (deleteNode->Right == INVALID_OFFSET || deleteNode->Left == INVALID_OFFSET) {
|
|
|
|
//
|
|
// deleteNode has one child
|
|
//
|
|
|
|
if (deleteNode->Right == INVALID_OFFSET) {
|
|
replace = GetNodeStruct (deleteNode->Left);
|
|
} else {
|
|
replace = GetNodeStruct (deleteNode->Right);
|
|
}
|
|
|
|
replaceOffset = GetNodeOffset (replace);
|
|
|
|
//
|
|
// deleteNode->Parent has new child, so check balance
|
|
//
|
|
|
|
startBalance = parent;
|
|
|
|
} else {
|
|
|
|
//
|
|
// deleteNode has two children: find replacement on deeper side
|
|
//
|
|
|
|
if (deleteNode->LeftDepth > deleteNode->RightDepth) {
|
|
|
|
//
|
|
// find replacement node on left
|
|
//
|
|
|
|
replace = GetNodeStruct (deleteNode->Left);
|
|
|
|
if (replace->Right == INVALID_OFFSET) {
|
|
//
|
|
// node's left child has no right child, so replace is node->Left
|
|
//
|
|
replace->Right = deleteNode->Right; //hook up node's right child to replace
|
|
|
|
GetNodeStruct (replace->Right)->Parent = deleteNode->Left;
|
|
|
|
replaceOffset = GetNodeOffset (replace);
|
|
|
|
} else {
|
|
//
|
|
// deleteNode's left child has right child, so find the rightmost child
|
|
//
|
|
|
|
do {
|
|
//
|
|
// move right as far as possible
|
|
//
|
|
replace = GetNodeStruct (replace->Right);
|
|
|
|
} while (replace->Right != INVALID_OFFSET);
|
|
|
|
//
|
|
// child of replace->Parent changed, so balance
|
|
//
|
|
|
|
startBalance2 = GetNodeStruct (replace->Parent);
|
|
|
|
//
|
|
// replace's parent's right child is replace's left
|
|
//
|
|
|
|
startBalance2->Right = replace->Left;
|
|
|
|
if (replace->Left != INVALID_OFFSET) {
|
|
//
|
|
// hook up left children to replace->Parent
|
|
//
|
|
GetNodeStruct(replace->Left)->Parent = replace->Parent;
|
|
}
|
|
|
|
replaceOffset = GetNodeOffset (replace);
|
|
|
|
//
|
|
// hook up children of deleteNode to replace
|
|
//
|
|
|
|
replace->Left = deleteNode->Left;
|
|
GetNodeStruct (replace->Left)->Parent = replaceOffset;
|
|
|
|
replace->Right = deleteNode->Right;
|
|
GetNodeStruct (replace->Right)->Parent = replaceOffset;
|
|
}
|
|
|
|
} else {
|
|
//
|
|
// find replacement node on right
|
|
//
|
|
|
|
replace = GetNodeStruct (deleteNode->Right);
|
|
|
|
if (replace->Left == INVALID_OFFSET) {
|
|
//
|
|
// deleteNode's right child has no left child, so replace is deleteNode->Right
|
|
//
|
|
|
|
replace->Left = deleteNode->Left; // hook up node's left child to replace
|
|
|
|
GetNodeStruct (replace->Left)->Parent = deleteNode->Right;
|
|
|
|
replaceOffset = GetNodeOffset (replace);
|
|
|
|
} else {
|
|
//
|
|
// deleteNode's right child has left child, so find the leftmost child
|
|
//
|
|
|
|
do {
|
|
|
|
replace = GetNodeStruct (replace->Left);
|
|
|
|
} while (replace->Left != INVALID_OFFSET);
|
|
|
|
//
|
|
// child of replace->Parent changed, so balance
|
|
//
|
|
startBalance2 = GetNodeStruct (replace->Parent);
|
|
|
|
//
|
|
// replace's parent's left child is replace's right
|
|
//
|
|
startBalance2->Left = replace->Right;
|
|
|
|
if (replace->Right != INVALID_OFFSET) {
|
|
//
|
|
// hook up right children to replace->Parent
|
|
//
|
|
GetNodeStruct (replace->Right)->Parent = replace->Parent;
|
|
}
|
|
|
|
replaceOffset = GetNodeOffset (replace);
|
|
|
|
//
|
|
// hook up children of deleteNode to replace
|
|
//
|
|
replace->Right = deleteNode->Right;
|
|
GetNodeStruct (replace->Right)->Parent = replaceOffset;
|
|
|
|
replace->Left = deleteNode->Left;
|
|
GetNodeStruct (replace->Left)->Parent = replaceOffset;
|
|
}
|
|
}
|
|
|
|
//
|
|
// in all cases of deleted node having two children,
|
|
// the place to start (second) balancing is the node
|
|
// that replaces the deleted node, because it will
|
|
// always have at least one new child.
|
|
//
|
|
startBalance = replace;
|
|
}
|
|
|
|
//
|
|
// this is offset
|
|
//
|
|
|
|
replace->Parent = deleteNode->Parent;
|
|
|
|
if (parent == NULL) {
|
|
//
|
|
// deleting top-level node
|
|
//
|
|
pSetTreeRoot (tree, replaceOffset);
|
|
|
|
} else {
|
|
if (parent->Left == deleteNodeOffset) {
|
|
parent->Left = replaceOffset;
|
|
} else {
|
|
parent->Right = replaceOffset;
|
|
}
|
|
}
|
|
}
|
|
|
|
if (startBalance2) {
|
|
//
|
|
// startBalance2 is lower one
|
|
//
|
|
pBinTreeBalanceUpward (startBalance2, TreeOffset);
|
|
}
|
|
|
|
pBinTreeBalanceUpward (startBalance, TreeOffset);
|
|
|
|
if (deleteNode->InsertionOrdered) {
|
|
//
|
|
// We are in insertion-ordered mode
|
|
//
|
|
|
|
//
|
|
// get offset of LISTELEM for this NODESTRUCT
|
|
//
|
|
elemOffset = deleteNode->Data;
|
|
elem = GetListElem (elemOffset);
|
|
|
|
header = GetNodeStruct (tree->Root); //get the header of list
|
|
|
|
if (header->Head == elemOffset) {
|
|
//
|
|
// if elem was first in list
|
|
//
|
|
|
|
header->Head = elem->Next;
|
|
|
|
if (elem->Next == INVALID_OFFSET) { // if elem was last in list
|
|
header->Tail = INVALID_OFFSET;
|
|
}
|
|
|
|
} else {
|
|
//
|
|
// elem was not first in list
|
|
//
|
|
|
|
cur = GetListElem (header->Head);
|
|
|
|
while (cur->Next != elemOffset) {
|
|
MYASSERT (cur->Next != INVALID_OFFSET);
|
|
cur = GetListElem (cur->Next);
|
|
}
|
|
|
|
//
|
|
// now cur is the element before elem, so pull elem out of list
|
|
//
|
|
|
|
cur->Next = elem->Next;
|
|
if (elem->Next == INVALID_OFFSET) { // if elem was last in list
|
|
header->Tail = GetListElemOffset(cur); // set end pointer to new last element
|
|
}
|
|
}
|
|
|
|
pBinTreeFreeListElem (elem);
|
|
DECTREEELEMS(tree);
|
|
}
|
|
|
|
pBinTreeFreeNode (deleteNode);
|
|
DECTREENODES(tree);
|
|
|
|
TESTTREE(tree);
|
|
|
|
return data;
|
|
}
|
|
|
|
|
|
PNODESTRUCT
|
|
pBinTreeFindNode (
|
|
IN PBINTREE Tree,
|
|
IN PCWSTR Str
|
|
)
|
|
{
|
|
PNODESTRUCT cur;
|
|
INT cmp;
|
|
|
|
if (!Tree) {
|
|
return NULL;
|
|
}
|
|
|
|
cur = GetTreeRoot (Tree);
|
|
|
|
while (cur) {
|
|
|
|
cmp = StringPasICompare (Str, GetNodeDataStr (cur));
|
|
|
|
if (!cmp) {
|
|
break;
|
|
}
|
|
|
|
if (cmp < 0) {
|
|
cur = GetNodeStruct (cur->Left);
|
|
} else {
|
|
cur = GetNodeStruct (cur->Right);
|
|
}
|
|
}
|
|
|
|
return cur;
|
|
}
|
|
|
|
|
|
UINT
|
|
BinTreeFindNode (
|
|
IN UINT TreeOffset,
|
|
IN PCWSTR Str
|
|
)
|
|
|
|
/*++
|
|
|
|
Routine Description:
|
|
|
|
BinTreeFindNode searches a binary tree for a string and returns the offset
|
|
to the item data.
|
|
|
|
Arguments:
|
|
|
|
TreeOffset - Specifies the binary tree to search
|
|
Str - Specifies the string to find
|
|
|
|
Return Value:
|
|
|
|
The offset to the node data, or INVALID_OFFSET if string is not found.
|
|
|
|
--*/
|
|
|
|
{
|
|
PNODESTRUCT node;
|
|
PBINTREE tree;
|
|
|
|
tree = GetBinTree (TreeOffset);
|
|
node = pBinTreeFindNode (tree, Str);
|
|
|
|
if (!node) {
|
|
return INVALID_OFFSET;
|
|
}
|
|
|
|
return GetNodeData(node);
|
|
}
|
|
|
|
|
|
VOID
|
|
pBinTreeDestroy (
|
|
IN PNODESTRUCT Node, OPTIONAL
|
|
IN PBINTREE Tree OPTIONAL
|
|
)
|
|
|
|
/*++
|
|
|
|
Routine Description:
|
|
|
|
pBinTreeDestroy destroys a binary tree. This routine is recursive.
|
|
|
|
Arguments:
|
|
|
|
Node - Specifies the node to deallocate. All child nodes are also
|
|
deallocated.
|
|
Tree - Specifies the tree that Node belongs to
|
|
|
|
Return Value:
|
|
|
|
None.
|
|
|
|
--*/
|
|
|
|
{
|
|
if (!Node || !Tree) {
|
|
return;
|
|
}
|
|
|
|
pBinTreeDestroy (GetNodeStruct (Node->Left), Tree);
|
|
pBinTreeDestroy (GetNodeStruct (Node->Right), Tree);
|
|
|
|
if (Node->InsertionOrdered) {
|
|
pBinTreeFreeListElem (GetListElem (Node->Data));
|
|
DECTREEELEMS(Tree);
|
|
}
|
|
|
|
pBinTreeFreeNode (Node);
|
|
DECTREENODES(Tree);
|
|
}
|
|
|
|
|
|
VOID
|
|
BinTreeDestroy (
|
|
IN UINT TreeOffset
|
|
)
|
|
|
|
/*++
|
|
|
|
Routine Description:
|
|
|
|
BinTreeDestroy deallocates all nodes in a binary tree.
|
|
|
|
Arguments:
|
|
|
|
TreeOffset - Specifies the binary tree to free
|
|
|
|
Return Value:
|
|
|
|
None.
|
|
|
|
--*/
|
|
|
|
{
|
|
PBINTREE tree;
|
|
PNODESTRUCT root;
|
|
PNODESTRUCT header;
|
|
|
|
if (TreeOffset==INVALID_OFFSET) {
|
|
return;
|
|
}
|
|
|
|
tree = GetBinTree (TreeOffset);
|
|
root = GetNodeStruct (tree->Root);
|
|
|
|
if (root && root->InsertionHead) {
|
|
header = root;
|
|
root = GetNodeStruct (root->Root);
|
|
} else {
|
|
header = NULL;
|
|
}
|
|
|
|
pBinTreeDestroy (root, tree);
|
|
|
|
if (header) {
|
|
pBinTreeFreeNode(header);
|
|
DECTREENODES(tree);
|
|
}
|
|
|
|
TESTTREENODES(tree);
|
|
TESTTREEELEMS(tree);
|
|
|
|
pBinTreeFreeTree(tree);
|
|
}
|
|
|
|
|
|
PNODESTRUCT
|
|
pBinTreeEnumFirst (
|
|
IN PBINTREE Tree
|
|
)
|
|
|
|
/*++
|
|
|
|
Routine Description:
|
|
|
|
pBinTreeEnumFirst returns the first node in the specified tree.
|
|
|
|
Arguments:
|
|
|
|
Tree - Specifies the tree to begin enumerating
|
|
|
|
Return Value:
|
|
|
|
A pointer to the first node struct, or NULL if no items exist in Tree, or
|
|
if Tree is NULL.
|
|
|
|
--*/
|
|
|
|
{
|
|
PNODESTRUCT cur;
|
|
|
|
cur = GetTreeRoot (Tree);
|
|
|
|
if (cur) {
|
|
|
|
while (cur->Left != INVALID_OFFSET) {
|
|
cur = GetNodeStruct (cur->Left);
|
|
}
|
|
|
|
}
|
|
|
|
return cur;
|
|
}
|
|
|
|
|
|
PNODESTRUCT
|
|
pBinTreeEnumNext (
|
|
IN PNODESTRUCT CurrentNode
|
|
)
|
|
|
|
/*++
|
|
|
|
Routine Description:
|
|
|
|
pBinTreeEnumNext continues an enumeration of a binary tree. It walks the
|
|
tree in sorted order.
|
|
|
|
Arguments:
|
|
|
|
CurrentNode - Specifies the previous node returned by pBinTreeEnumFirst or
|
|
pBinTreeEnumNext.
|
|
|
|
Return Value:
|
|
|
|
Returns the next node in the tree, or NULL if no more items are left to
|
|
enumerate.
|
|
|
|
--*/
|
|
|
|
{
|
|
PNODESTRUCT cur;
|
|
PNODESTRUCT parent;
|
|
|
|
if (!CurrentNode) {
|
|
return NULL;
|
|
}
|
|
|
|
cur = CurrentNode;
|
|
|
|
if (cur->Right != INVALID_OFFSET) {
|
|
|
|
cur = GetNodeStruct (cur->Right);
|
|
|
|
while (cur->Left != INVALID_OFFSET) {
|
|
cur = GetNodeStruct (cur->Left);
|
|
}
|
|
|
|
return cur;
|
|
}
|
|
|
|
//
|
|
// otherwise, cur has no right child, so we have to
|
|
// move upwards until we find a parent to the right
|
|
// (or we reach top of tree, meaning we are done)
|
|
//
|
|
|
|
for (;;) {
|
|
parent = GetNodeStruct (cur->Parent);
|
|
|
|
//
|
|
// if has no parent or parent is to right
|
|
//
|
|
|
|
if (!parent || parent->Left == GetNodeOffset (cur)) {
|
|
break;
|
|
}
|
|
|
|
cur = parent;
|
|
}
|
|
|
|
return parent;
|
|
}
|
|
|
|
|
|
PLISTELEM
|
|
pBinTreeInsertionEnumFirst (
|
|
PBINTREE Tree
|
|
)
|
|
|
|
/*++
|
|
|
|
Routine Description:
|
|
|
|
pBinTreeInsertionEnumFirst begins an enumeration of the nodes inside an
|
|
insertion-ordered tree. If the tree is not insertion ordered, no items are
|
|
enumerated. If insertion order was enabled after items had been previously
|
|
added, this enumeration will not return those initial items.
|
|
|
|
Arguments:
|
|
|
|
Tree - Specifies the tree to begin enumeration of
|
|
|
|
Return Value:
|
|
|
|
A pointer to the linked list element, or NULL if no insertion-ordered nodes
|
|
exist in Tree, or NULL if Tree is NULL.
|
|
|
|
--*/
|
|
|
|
{
|
|
PNODESTRUCT header;
|
|
|
|
if (!Tree) {
|
|
return NULL;
|
|
}
|
|
|
|
header = GetNodeStruct (Tree->Root);
|
|
|
|
return header ? GetListElem (header->Head) : NULL;
|
|
}
|
|
|
|
|
|
PLISTELEM
|
|
pBinTreeInsertionEnumNext (
|
|
IN PLISTELEM Elem
|
|
)
|
|
|
|
/*++
|
|
|
|
Routine Description:
|
|
|
|
pBinTreeInsertionEnumNext continues an enumeration of the insertion-ordered
|
|
nodes in a binary tree.
|
|
|
|
Arguments:
|
|
|
|
Elem - Specifies the previously enumerated list element
|
|
|
|
Return Value:
|
|
|
|
A pointer to the next element, or NULL if no more elements exist, or if
|
|
Elem is NULL.
|
|
|
|
--*/
|
|
|
|
{
|
|
if (!Elem) {
|
|
return NULL;
|
|
}
|
|
|
|
return GetListElem (Elem->Next);
|
|
}
|
|
|
|
|
|
UINT
|
|
BinTreeEnumFirst (
|
|
IN UINT TreeOffset,
|
|
OUT PUINT Enum
|
|
)
|
|
|
|
/*++
|
|
|
|
Routine Description:
|
|
|
|
BinTreeEnumFirst begins an enumeration of the data offsets stored in a
|
|
binary tree. The enumeration is sorted order or insertion order, depending
|
|
on the insertion order setting within the tree.
|
|
|
|
Arguments:
|
|
|
|
TreeOffset - Specifies the binary tree to begin enumeration of.
|
|
Enum - Receives the offset to the binary tree node.
|
|
|
|
Return Value:
|
|
|
|
The offset to the data associated with the first node, or INVALID_OFFSET if
|
|
the tree is empty.
|
|
|
|
--*/
|
|
|
|
{
|
|
PBINTREE tree;
|
|
PNODESTRUCT node;
|
|
PLISTELEM elem;
|
|
|
|
MYASSERT (Enum);
|
|
|
|
if (TreeOffset == INVALID_OFFSET) {
|
|
return INVALID_OFFSET;
|
|
}
|
|
|
|
tree = GetBinTree (TreeOffset);
|
|
|
|
if (IsTreeInsertionOrdered (tree)) {
|
|
//
|
|
// tree is insertion-ordered, so get first element in
|
|
// linked list. enumerator is NODESTRUCT for this elem
|
|
//
|
|
|
|
elem = pBinTreeInsertionEnumFirst (tree);
|
|
|
|
if (!elem) {
|
|
|
|
if (Enum) {
|
|
*Enum = INVALID_OFFSET;
|
|
}
|
|
|
|
return INVALID_OFFSET;
|
|
|
|
} else {
|
|
|
|
if (Enum) {
|
|
*Enum = elem->Node;
|
|
}
|
|
|
|
return elem->Data;
|
|
}
|
|
|
|
} else {
|
|
|
|
//
|
|
// tree is not insertion-ordered, so get leftmost node.
|
|
// enumerator is the offset of this node.
|
|
//
|
|
|
|
node = pBinTreeEnumFirst (tree);
|
|
|
|
if (Enum) {
|
|
*Enum = GetNodeOffset (node);
|
|
}
|
|
|
|
return !node ? INVALID_OFFSET : node->Data;
|
|
}
|
|
}
|
|
|
|
|
|
UINT
|
|
BinTreeEnumNext (
|
|
IN OUT PUINT Enum
|
|
)
|
|
|
|
/*++
|
|
|
|
Routine Description:
|
|
|
|
BinTreeEnumNext continues an enumeration started by BinTreeEnumFirst.
|
|
|
|
Arguments:
|
|
|
|
Enum - Specifies the previous node offset, receivies the enumerated node
|
|
offset.
|
|
|
|
Return Value:
|
|
|
|
The offset to the data associated with the next node, or INVALID_OFFSET if
|
|
no more nodes exist in the tree.
|
|
|
|
--*/
|
|
|
|
{
|
|
PNODESTRUCT node;
|
|
PLISTELEM elem;
|
|
|
|
MYASSERT (Enum);
|
|
|
|
if (*Enum == INVALID_OFFSET) {
|
|
return INVALID_OFFSET;
|
|
}
|
|
|
|
node = GetNodeStruct (*Enum);
|
|
|
|
if (node->InsertionOrdered) {
|
|
//
|
|
// tree is insertion-ordered,
|
|
// so get next node in list.
|
|
//
|
|
|
|
elem = pBinTreeInsertionEnumNext (GetListElem (node->Data));
|
|
|
|
if (!elem) {
|
|
*Enum = INVALID_OFFSET;
|
|
return INVALID_OFFSET;
|
|
} else {
|
|
*Enum = elem->Node;
|
|
return elem->Data;
|
|
}
|
|
|
|
} else {
|
|
//
|
|
// tree is not insertion-ordered,
|
|
// so get next node in tree.
|
|
//
|
|
node = pBinTreeEnumNext (node);
|
|
|
|
*Enum = GetNodeOffset (node);
|
|
return !node ? INVALID_OFFSET : node->Data;
|
|
}
|
|
}
|
|
|
|
|
|
|
|
PNODESTRUCT
|
|
pBinTreeAllocNode (
|
|
OUT PUINT Offset
|
|
)
|
|
|
|
/*++
|
|
|
|
Routine Description:
|
|
|
|
pBinTreeAllocNode allocates a node in the current global database, and
|
|
returns the offset and pointer to that node.
|
|
|
|
Allocations can alter the location of the database, and subsequently
|
|
invalidate the caller's pointers into the database.
|
|
|
|
Arguments:
|
|
|
|
Offset - Receivies the offset to the newly created node.
|
|
|
|
Return Value:
|
|
|
|
A pointer to the newly created node.
|
|
|
|
--*/
|
|
|
|
{
|
|
PNODESTRUCT node;
|
|
UINT tempOffset;
|
|
|
|
MYASSERT (g_CurrentDatabase);
|
|
|
|
if (g_CurrentDatabase->FirstBinTreeNodeDeleted == INVALID_OFFSET) {
|
|
|
|
tempOffset = DatabaseAllocBlock (NODESTRUCT_SIZE);
|
|
if (tempOffset == INVALID_OFFSET) {
|
|
return NULL;
|
|
}
|
|
|
|
*Offset = tempOffset;
|
|
|
|
#ifdef DEBUG
|
|
if (g_UseDebugStructs) {
|
|
node = (PNODESTRUCT) OFFSET_TO_PTR(*Offset);
|
|
node->Signature = NODESTRUCT_SIGNATURE;
|
|
} else {
|
|
node = (PNODESTRUCT) OFFSET_TO_PTR(*Offset - NODESTRUCT_HEADER_SIZE);
|
|
}
|
|
#else
|
|
node = (PNODESTRUCT) OFFSET_TO_PTR(*Offset);
|
|
#endif
|
|
|
|
} else {
|
|
*Offset = g_CurrentDatabase->FirstBinTreeNodeDeleted;
|
|
node = GetNodeStruct(*Offset);
|
|
g_CurrentDatabase->FirstBinTreeNodeDeleted = node->NextDeleted;
|
|
}
|
|
|
|
#ifdef DEBUG
|
|
if (g_UseDebugStructs) {
|
|
node->Deleted = FALSE;
|
|
}
|
|
#endif
|
|
|
|
return node;
|
|
}
|
|
|
|
|
|
VOID
|
|
pBinTreeFreeNode (
|
|
IN PNODESTRUCT Node
|
|
)
|
|
|
|
/*++
|
|
|
|
Routine Description:
|
|
|
|
pBinTreeFreeNode puts an allocated node on the deleted list. It does not
|
|
adjust any other linkage.
|
|
|
|
Arguments:
|
|
|
|
Node - Specifies the node to put on the deleted list.
|
|
|
|
Return Value:
|
|
|
|
None.
|
|
|
|
--*/
|
|
|
|
{
|
|
MYASSERT(Node);
|
|
|
|
#ifdef DEBUG
|
|
if (g_UseDebugStructs) {
|
|
MYASSERT(Node->Signature == NODESTRUCT_SIGNATURE);
|
|
Node->Deleted = TRUE;
|
|
}
|
|
#endif
|
|
|
|
MYASSERT(g_CurrentDatabase);
|
|
|
|
Node->NextDeleted = g_CurrentDatabase->FirstBinTreeNodeDeleted;
|
|
g_CurrentDatabase->FirstBinTreeNodeDeleted = GetNodeOffset(Node);
|
|
}
|
|
|
|
|
|
PBINTREE
|
|
pBinTreeAllocTree (
|
|
OUT PUINT Offset
|
|
)
|
|
|
|
/*++
|
|
|
|
Routine Description:
|
|
|
|
pBinTreeAllocTree creates a binary tree data structure. If a structure
|
|
is available in the detele list, then it is used. Otherwise, the
|
|
database grows.
|
|
|
|
Allocations can alter the location of the database, and subsequently
|
|
invalidate the caller's pointers into the database.
|
|
|
|
Arguments:
|
|
|
|
Offset - Receivies the offset to the binary tree.
|
|
|
|
Return Value:
|
|
|
|
A pointer to the new binary tree structure.
|
|
|
|
--*/
|
|
|
|
{
|
|
PBINTREE tree;
|
|
UINT tempOffset;
|
|
|
|
MYASSERT(g_CurrentDatabase);
|
|
|
|
if (g_CurrentDatabase->FirstBinTreeDeleted == INVALID_OFFSET) {
|
|
|
|
tempOffset = DatabaseAllocBlock (BINTREE_SIZE);
|
|
if (tempOffset == INVALID_OFFSET) {
|
|
return NULL;
|
|
}
|
|
|
|
*Offset = tempOffset;
|
|
|
|
#ifdef DEBUG
|
|
if (g_UseDebugStructs) {
|
|
tree = (PBINTREE) OFFSET_TO_PTR(*Offset);
|
|
tree->Signature = BINTREE_SIGNATURE;
|
|
} else {
|
|
tree = (PBINTREE) OFFSET_TO_PTR(*Offset - BINTREE_HEADER_SIZE);
|
|
}
|
|
#else
|
|
tree = (PBINTREE)OFFSET_TO_PTR(*Offset);
|
|
#endif
|
|
|
|
} else {
|
|
*Offset = g_CurrentDatabase->FirstBinTreeDeleted;
|
|
tree = GetBinTree (*Offset);
|
|
g_CurrentDatabase->FirstBinTreeDeleted = tree->NextDeleted;
|
|
}
|
|
|
|
#ifdef DEBUG
|
|
if (g_UseDebugStructs) {
|
|
tree->Deleted = FALSE;
|
|
}
|
|
#endif
|
|
|
|
return tree;
|
|
}
|
|
|
|
|
|
VOID
|
|
pBinTreeFreeTree (
|
|
IN PBINTREE Tree
|
|
)
|
|
|
|
/*++
|
|
|
|
Routine Description:
|
|
|
|
pBinTreeFreeTree frees a binary tree structure. It does not free the nodes
|
|
within the structure.
|
|
|
|
Arguments:
|
|
|
|
Tree - Specifies the binary tree structure to put on the deleted list.
|
|
|
|
Return Value:
|
|
|
|
None.
|
|
|
|
--*/
|
|
|
|
{
|
|
MYASSERT (Tree);
|
|
MYASSERT (g_CurrentDatabase);
|
|
|
|
#ifdef DEBUG
|
|
if (g_UseDebugStructs) {
|
|
Tree->Deleted = TRUE;
|
|
MYASSERT (Tree->Signature == BINTREE_SIGNATURE);
|
|
}
|
|
#endif
|
|
|
|
Tree->NextDeleted = g_CurrentDatabase->FirstBinTreeDeleted;
|
|
g_CurrentDatabase->FirstBinTreeDeleted = GetTreeOffset (Tree);
|
|
}
|
|
|
|
|
|
PLISTELEM
|
|
pBinTreeAllocListElem (
|
|
OUT PUINT Offset
|
|
)
|
|
|
|
/*++
|
|
|
|
Routine Description:
|
|
|
|
pBinTreeAllocListElem allocates a list element. If an element is available
|
|
in the deleted list, it is used. Otherwise, a new element is allocated
|
|
from the database.
|
|
|
|
Allocations can alter the location of the database, and subsequently
|
|
invalidate the caller's pointers into the database.
|
|
|
|
Arguments:
|
|
|
|
Offset - Receives the offset of the newly allocated element
|
|
|
|
Return Value:
|
|
|
|
A pointer to the allocated list element
|
|
|
|
--*/
|
|
|
|
{
|
|
PLISTELEM elem;
|
|
UINT tempOffset;
|
|
|
|
MYASSERT (g_CurrentDatabase);
|
|
|
|
if (g_CurrentDatabase->FirstBinTreeListElemDeleted == INVALID_OFFSET) {
|
|
|
|
tempOffset = DatabaseAllocBlock (LISTELEM_SIZE);
|
|
if (tempOffset == INVALID_OFFSET) {
|
|
return NULL;
|
|
}
|
|
|
|
*Offset = tempOffset;
|
|
|
|
#ifdef DEBUG
|
|
|
|
if (g_UseDebugStructs) {
|
|
elem = (PLISTELEM) OFFSET_TO_PTR(*Offset);
|
|
elem->Signature = LISTELEM_SIGNATURE;
|
|
} else {
|
|
elem = (PLISTELEM) OFFSET_TO_PTR(*Offset - LISTELEM_HEADER_SIZE);
|
|
}
|
|
|
|
#else
|
|
elem = (PLISTELEM) OFFSET_TO_PTR(*Offset);
|
|
#endif
|
|
|
|
} else {
|
|
*Offset = g_CurrentDatabase->FirstBinTreeListElemDeleted;
|
|
elem = GetListElem (*Offset);
|
|
g_CurrentDatabase->FirstBinTreeListElemDeleted = elem->NextDeleted;
|
|
}
|
|
|
|
return elem;
|
|
}
|
|
|
|
|
|
VOID
|
|
pBinTreeFreeListElem (
|
|
IN PLISTELEM Elem
|
|
)
|
|
|
|
/*++
|
|
|
|
Routine Description:
|
|
|
|
pBinTreeFreeListElem puts an allocated list element on the deleted element
|
|
list, so it will be reused in a future allocation.
|
|
|
|
Arguments:
|
|
|
|
Elem - Specifies the element to put on the deleted list.
|
|
|
|
Return Value:
|
|
|
|
None.
|
|
|
|
--*/
|
|
|
|
{
|
|
MYASSERT(Elem);
|
|
MYASSERT(g_CurrentDatabase);
|
|
|
|
#ifdef DEBUG
|
|
if (g_UseDebugStructs) {
|
|
MYASSERT(Elem->Signature == LISTELEM_SIGNATURE);
|
|
}
|
|
#endif
|
|
|
|
Elem->NextDeleted = g_CurrentDatabase->FirstBinTreeListElemDeleted;
|
|
g_CurrentDatabase->FirstBinTreeListElemDeleted = GetListElemOffset(Elem);
|
|
}
|
|
|
|
|
|
VOID
|
|
pBinTreeBalanceUpward (
|
|
IN PNODESTRUCT Node,
|
|
IN UINT TreeOffset
|
|
)
|
|
|
|
/*++
|
|
|
|
Routine Description:
|
|
|
|
pBinTreeBalanceUpward makes sure that the specified node is balanced. If it
|
|
is not balanced, the nodes are rotated as necessary, and balancing
|
|
continues up the tree.
|
|
|
|
Arguments:
|
|
|
|
Node - Specifies the node to balance
|
|
|
|
TreeOffset - Specifies the offset of the binary tree containing Node
|
|
|
|
Return Value:
|
|
|
|
None.
|
|
|
|
--*/
|
|
|
|
{
|
|
PNODESTRUCT cur;
|
|
PNODESTRUCT next;
|
|
|
|
cur = Node;
|
|
|
|
//
|
|
// Move up tree. stop if:
|
|
// a) hit top of tree
|
|
// b) pBinTreeNodeBalance returns FALSE (nothing changed)
|
|
//
|
|
|
|
while (cur) {
|
|
//
|
|
// need to grab cur's parent before balancing
|
|
// cur because cur might change place in tree
|
|
//
|
|
|
|
next = GetNodeStruct (cur->Parent);
|
|
|
|
if (!pBinTreeNodeBalance (cur, TreeOffset)) {
|
|
return;
|
|
}
|
|
|
|
cur = next;
|
|
}
|
|
}
|
|
|
|
|
|
BOOL
|
|
pBinTreeNodeBalance (
|
|
IN PNODESTRUCT Node,
|
|
IN UINT TreeOffset
|
|
)
|
|
|
|
/*++
|
|
|
|
Routine Description:
|
|
|
|
pBinTreeNodeBalance checks the balance of the specified node, and if
|
|
necessary, performs a rotation to balance the node. If a rotation was
|
|
performed, the parent might become imbalanced.
|
|
|
|
Arguments:
|
|
|
|
Node - Specifies the node to balance
|
|
TreeOffset - Specifies the offset to the binary tree that contains Node
|
|
|
|
Return Value:
|
|
|
|
TRUE if a rotation was performed, FALSE if Node is already balanced
|
|
|
|
--*/
|
|
|
|
{
|
|
UINT left;
|
|
UINT right;
|
|
PNODESTRUCT leftNode;
|
|
PNODESTRUCT rightNode;
|
|
|
|
if (!Node) {
|
|
return FALSE;
|
|
}
|
|
|
|
leftNode = GetNodeStruct (Node->Left);
|
|
rightNode = GetNodeStruct (Node->Right);
|
|
|
|
if (!rightNode) {
|
|
right = 0;
|
|
} else {
|
|
right = MAX (rightNode->RightDepth, rightNode->LeftDepth) + 1;
|
|
}
|
|
|
|
if (!leftNode) {
|
|
left = 0;
|
|
} else {
|
|
left = MAX (leftNode->RightDepth, leftNode->LeftDepth) + 1;
|
|
}
|
|
|
|
if (right == Node->RightDepth && left == Node->LeftDepth) {
|
|
//
|
|
// if node values have not changed, node is balanced
|
|
//
|
|
TESTNODETREE(Node);
|
|
return FALSE;
|
|
}
|
|
|
|
MYASSERT (right < 126);
|
|
MYASSERT (left < 126);
|
|
|
|
Node->RightDepth = (WORD) right;
|
|
Node->LeftDepth = (WORD) left;
|
|
|
|
if (Node->RightDepth > (Node->LeftDepth + 1)) {
|
|
//
|
|
// right heavy
|
|
//
|
|
|
|
pBinTreeRotateLeft (Node, TreeOffset);
|
|
|
|
} else if (Node->LeftDepth > (Node->RightDepth + 1)) {
|
|
//
|
|
// left heavy
|
|
//
|
|
|
|
pBinTreeRotateRight (Node, TreeOffset);
|
|
}
|
|
|
|
return TRUE;
|
|
}
|
|
|
|
|
|
VOID
|
|
pBinTreeRotateLeft (
|
|
IN PNODESTRUCT Node,
|
|
IN UINT TreeOffset
|
|
)
|
|
|
|
/*++
|
|
|
|
Routine Description:
|
|
|
|
pBinTreeRotateLeft performs a left rotation on Node, moving one node
|
|
from the right side to the left side, in order to balance the node.
|
|
|
|
Arguments:
|
|
|
|
Node - Specifies the node to rotate left
|
|
TreeOffset - Specifies the offset of the binary tree containing Node
|
|
|
|
Return Value:
|
|
|
|
None.
|
|
|
|
--*/
|
|
|
|
{
|
|
PNODESTRUCT newRoot;
|
|
PNODESTRUCT parent;
|
|
PNODESTRUCT right;
|
|
UINT nodeOffset;
|
|
UINT newRootOffset;
|
|
|
|
if (!Node) {
|
|
return;
|
|
}
|
|
|
|
MYASSERT (Node->Right != INVALID_OFFSET);
|
|
|
|
nodeOffset = GetNodeOffset (Node);
|
|
parent = GetNodeStruct (Node->Parent);
|
|
|
|
right = GetNodeStruct (Node->Right);
|
|
|
|
//
|
|
// make sure right side is heavier on outside
|
|
//
|
|
|
|
if (right->LeftDepth > right->RightDepth) {
|
|
pBinTreeRotateRight (right, TreeOffset);
|
|
PTR_WAS_INVALIDATED(right);
|
|
}
|
|
|
|
newRootOffset = Node->Right;
|
|
newRoot = GetNodeStruct (newRootOffset);
|
|
|
|
Node->Right = newRoot->Left;
|
|
if (newRoot->Left != INVALID_OFFSET) {
|
|
GetNodeStruct (newRoot->Left)->Parent = nodeOffset;
|
|
}
|
|
|
|
newRoot->Parent = Node->Parent;
|
|
if (Node->Parent == INVALID_OFFSET) {
|
|
pSetTreeRoot (GetBinTree (TreeOffset), newRootOffset);
|
|
} else {
|
|
if (parent->Left == nodeOffset) {
|
|
parent->Left = newRootOffset;
|
|
} else {
|
|
parent->Right = newRootOffset;
|
|
}
|
|
}
|
|
|
|
newRoot->Left = nodeOffset;
|
|
Node->Parent = newRootOffset;
|
|
|
|
pBinTreeNodeBalance (Node, TreeOffset);
|
|
pBinTreeNodeBalance (newRoot, TreeOffset);
|
|
}
|
|
|
|
|
|
VOID
|
|
pBinTreeRotateRight (
|
|
IN PNODESTRUCT Node,
|
|
IN UINT TreeOffset
|
|
)
|
|
|
|
/*++
|
|
|
|
Routine Description:
|
|
|
|
pBinTreeRotateRight performs a right rotation on Node, moving one node from
|
|
the left side to the right side, in order to balance the node.
|
|
|
|
Arguments:
|
|
|
|
Node - Specifies the node to rotate left
|
|
TreeOffset - Specifies the offset of the binary tree containing Node
|
|
|
|
Return Value:
|
|
|
|
None.
|
|
|
|
--*/
|
|
|
|
{
|
|
PNODESTRUCT newRoot;
|
|
PNODESTRUCT parent;
|
|
PNODESTRUCT left;
|
|
UINT nodeOffset;
|
|
UINT newRootOffset;
|
|
|
|
if (!Node) {
|
|
return;
|
|
}
|
|
|
|
MYASSERT (Node->Left != INVALID_OFFSET);
|
|
|
|
nodeOffset = GetNodeOffset (Node);
|
|
parent = GetNodeStruct (Node->Parent);
|
|
|
|
left = GetNodeStruct (Node->Left);
|
|
|
|
//
|
|
// make sure left side is heavier on outside
|
|
//
|
|
|
|
if (left->RightDepth > left->LeftDepth) {
|
|
pBinTreeRotateLeft (left, TreeOffset);
|
|
PTR_WAS_INVALIDATED (left);
|
|
}
|
|
|
|
newRootOffset = Node->Left;
|
|
newRoot = GetNodeStruct (newRootOffset);
|
|
Node->Left = newRoot->Right;
|
|
|
|
if (newRoot->Right != INVALID_OFFSET) {
|
|
GetNodeStruct (newRoot->Right)->Parent = nodeOffset;
|
|
}
|
|
|
|
newRoot->Parent = Node->Parent;
|
|
|
|
if (Node->Parent == INVALID_OFFSET) {
|
|
pSetTreeRoot (GetBinTree (TreeOffset), newRootOffset);
|
|
} else {
|
|
if (parent->Left == nodeOffset) {
|
|
parent->Left = newRootOffset;
|
|
} else {
|
|
parent->Right = newRootOffset;
|
|
}
|
|
}
|
|
|
|
newRoot->Right = nodeOffset;
|
|
Node->Parent = newRootOffset;
|
|
|
|
pBinTreeNodeBalance (Node, TreeOffset);
|
|
pBinTreeNodeBalance (newRoot, TreeOffset);
|
|
|
|
}
|
|
|
|
|
|
BOOL
|
|
BinTreeSetInsertionOrdered (
|
|
IN UINT TreeOffset
|
|
)
|
|
|
|
/*++
|
|
|
|
Routine Description:
|
|
|
|
BinTreeSetInsertionOrdered transforms a binary tree into an
|
|
insertion-ordered link list.
|
|
|
|
Arguments:
|
|
|
|
TreeOffset - Specifies the binary tree to make insertion-ordered
|
|
|
|
Return Value:
|
|
|
|
TRUE if the tree was changed, FALSE if TreeOffset is not valid.
|
|
|
|
--*/
|
|
|
|
{
|
|
PBINTREE tree;
|
|
PNODESTRUCT node;
|
|
PNODESTRUCT root;
|
|
PNODESTRUCT header;
|
|
PLISTELEM elem;
|
|
PLISTELEM prevElem;
|
|
UINT headerOffset;
|
|
UINT offset;
|
|
UINT nodeOffset;
|
|
PBYTE buf;
|
|
|
|
MYASSERT (g_CurrentDatabase);
|
|
|
|
if (TreeOffset == INVALID_OFFSET) {
|
|
return FALSE;
|
|
}
|
|
|
|
//
|
|
// This is to test if allocations move buffer
|
|
//
|
|
buf = g_CurrentDatabase->Buf;
|
|
|
|
tree = GetBinTree (TreeOffset);
|
|
root = GetNodeStruct (tree->Root);
|
|
|
|
if (root && root->InsertionHead) {
|
|
return TRUE;
|
|
}
|
|
|
|
header = pBinTreeAllocNode (&headerOffset);
|
|
if (!header) {
|
|
return FALSE;
|
|
}
|
|
|
|
if (buf != g_CurrentDatabase->Buf) {
|
|
PTR_WAS_INVALIDATED(tree);
|
|
PTR_WAS_INVALIDATED(root);
|
|
|
|
tree = GetBinTree (TreeOffset);
|
|
root = GetNodeStruct (tree->Root);
|
|
buf = g_CurrentDatabase->Buf;
|
|
}
|
|
|
|
INCTREENODES(tree);
|
|
|
|
header->InsertionOrdered = TRUE;
|
|
header->InsertionHead = TRUE;
|
|
header->Data = tree->Root;
|
|
header->Head = INVALID_OFFSET;
|
|
header->Tail = INVALID_OFFSET;
|
|
header->Parent = INVALID_OFFSET;
|
|
tree->Root = headerOffset;
|
|
|
|
if (root) {
|
|
//
|
|
// There is at least one node in tree, so create LISTELEMs
|
|
//
|
|
|
|
node = pBinTreeEnumFirst (tree);
|
|
|
|
do {
|
|
nodeOffset = GetNodeOffset (node);
|
|
|
|
elem = pBinTreeAllocListElem (&offset);
|
|
if (!elem) {
|
|
return FALSE;
|
|
}
|
|
|
|
if (buf != g_CurrentDatabase->Buf) {
|
|
PTR_WAS_INVALIDATED(tree);
|
|
PTR_WAS_INVALIDATED(root);
|
|
PTR_WAS_INVALIDATED(header);
|
|
PTR_WAS_INVALIDATED(node);
|
|
|
|
tree = GetBinTree (TreeOffset);
|
|
header = GetNodeStruct (headerOffset);
|
|
node = GetNodeStruct (nodeOffset);
|
|
|
|
buf = g_CurrentDatabase->Buf;
|
|
}
|
|
|
|
INCTREEELEMS(tree);
|
|
|
|
//
|
|
// Update header element pointers
|
|
//
|
|
if (header->Head == INVALID_OFFSET) {
|
|
header->Head = offset;
|
|
}
|
|
|
|
if (header->Tail != INVALID_OFFSET) {
|
|
prevElem = GetListElem (header->Tail);
|
|
prevElem->Next = offset;
|
|
}
|
|
|
|
header->Tail = offset;
|
|
|
|
//
|
|
// Set new LISTELEM members, and corresponding node members
|
|
//
|
|
|
|
elem->Data = node->Data;
|
|
elem->Node = nodeOffset;
|
|
elem->Next = INVALID_OFFSET;
|
|
node->Data = offset;
|
|
|
|
node->InsertionOrdered = 1;
|
|
|
|
node = pBinTreeEnumNext (node);
|
|
|
|
} while (node);
|
|
}
|
|
|
|
return TRUE;
|
|
}
|
|
|
|
|
|
UINT
|
|
pBinTreeSize (
|
|
IN PNODESTRUCT Node
|
|
)
|
|
|
|
/*++
|
|
|
|
Routine Description:
|
|
|
|
pBinTreeSize computes the number of nodes indicated by Node and all of its
|
|
children.
|
|
|
|
Arguments:
|
|
|
|
Node - Specifies the node to find the size of.
|
|
|
|
Return Value:
|
|
|
|
The number of nodes represented by Node and its children.
|
|
|
|
--*/
|
|
|
|
{
|
|
if (!Node) {
|
|
return 0;
|
|
}
|
|
|
|
return (pBinTreeSize (GetNodeStruct (Node->Left)) ? 1 : 0) +
|
|
(pBinTreeSize (GetNodeStruct (Node->Right)) ? 1 : 0) + 1;
|
|
}
|
|
|
|
|
|
UINT
|
|
BinTreeSize (
|
|
IN UINT TreeOffset
|
|
)
|
|
|
|
/*++
|
|
|
|
Routine Description:
|
|
|
|
BinTreeSize returns the total number of nodes in the specified binary tree
|
|
|
|
Arguments:
|
|
|
|
TreeOffset - Specifies the offset to the binary tree
|
|
|
|
Return Value:
|
|
|
|
The number of nodes in the binary tree
|
|
|
|
--*/
|
|
|
|
{
|
|
PBINTREE tree;
|
|
|
|
if (TreeOffset == INVALID_OFFSET) {
|
|
return 0;
|
|
}
|
|
|
|
tree = GetBinTree (TreeOffset);
|
|
|
|
return pBinTreeSize (GetTreeRoot (tree));
|
|
}
|
|
|
|
#ifdef DEBUG
|
|
|
|
|
|
INT
|
|
pBinTreeMaxDepth (
|
|
IN PNODESTRUCT Node
|
|
)
|
|
|
|
/*++
|
|
|
|
Routine Description:
|
|
|
|
pBinTreeMaxDepth returns the number of nodes in the longest path. This
|
|
function is used to find out how deep the tree is.
|
|
|
|
This routine is recursive.
|
|
|
|
Arguments:
|
|
|
|
Node - Specifies the node to compute the depth of.
|
|
|
|
Return Value:
|
|
|
|
The number of nodes in the deepest path.
|
|
|
|
--*/
|
|
|
|
{
|
|
INT leftDepth, rightDepth;
|
|
|
|
if (Node == NULL) {
|
|
return 0;
|
|
}
|
|
|
|
leftDepth = pBinTreeMaxDepth (GetNodeStruct (Node->Left));
|
|
rightDepth = pBinTreeMaxDepth (GetNodeStruct (Node->Right));
|
|
|
|
return MAX (leftDepth, rightDepth) + 1;
|
|
}
|
|
|
|
|
|
INT
|
|
BinTreeMaxDepth (
|
|
UINT TreeOffset
|
|
)
|
|
|
|
/*++
|
|
|
|
Routine Description:
|
|
|
|
BinTreeMaxDepth returns the total depth of the specified tree
|
|
|
|
Arguments:
|
|
|
|
TreeOffset - Specifies the tree to compute the depth of
|
|
|
|
Return Value:
|
|
|
|
The depth of the tree (in levels)
|
|
|
|
--*/
|
|
|
|
{
|
|
PBINTREE tree;
|
|
|
|
if (TreeOffset == INVALID_OFFSET) {
|
|
return 0;
|
|
}
|
|
|
|
tree = GetBinTree (TreeOffset);
|
|
|
|
return pBinTreeMaxDepth (GetTreeRoot (tree));
|
|
}
|
|
|
|
|
|
BOOL
|
|
pBinTreeCheckBalanceOfNode (
|
|
IN PNODESTRUCT Node,
|
|
OUT PINT Depth
|
|
)
|
|
|
|
/*++
|
|
|
|
Routine Description:
|
|
|
|
pBinTreeCheckBalanceOfNode verifies Node is balanced, and all of its
|
|
children are also balanced.
|
|
|
|
This function is recursive.
|
|
|
|
Arguments:
|
|
|
|
Node - Specifies the node to check
|
|
Depth - Receives the depth of the node
|
|
|
|
Return Value:
|
|
|
|
TRUE if the node is balanced, FALSE otherwise
|
|
|
|
--*/
|
|
|
|
{
|
|
INT lDepth = 0;
|
|
INT rDepth = 0;
|
|
BOOL flag = TRUE;
|
|
|
|
if (!Node) {
|
|
if (Depth) {
|
|
*Depth = 0;
|
|
}
|
|
|
|
return TRUE;
|
|
}
|
|
|
|
flag = flag && pBinTreeCheckBalanceOfNode (GetNodeStruct (Node->Left), &lDepth);
|
|
MYASSERT (flag);
|
|
|
|
flag = flag && pBinTreeCheckBalanceOfNode (GetNodeStruct (Node->Right), &rDepth);
|
|
MYASSERT (flag);
|
|
|
|
flag = flag && ((INT) Node->LeftDepth == lDepth);
|
|
MYASSERT (flag);
|
|
|
|
flag = flag && ((INT) Node->RightDepth == rDepth);
|
|
MYASSERT (flag);
|
|
|
|
if (Depth != NULL) {
|
|
*Depth = MAX (lDepth, rDepth) + 1;
|
|
}
|
|
|
|
flag = flag && (ABS ((lDepth - rDepth)) <= 1);
|
|
MYASSERT (flag);
|
|
|
|
return flag;
|
|
}
|
|
|
|
|
|
BOOL
|
|
pBinTreeCheckBalance (
|
|
IN PNODESTRUCT Node
|
|
)
|
|
|
|
/*++
|
|
|
|
Routine Description:
|
|
|
|
pBinTreeCheckBalance checks the balance of Node
|
|
|
|
Arguments:
|
|
|
|
Node - Specifies the node to check the balance of
|
|
|
|
Return Value:
|
|
|
|
TRUE if Node is balanced, FALSE otherwise.
|
|
|
|
--*/
|
|
|
|
{
|
|
return pBinTreeCheckBalanceOfNode (Node, NULL);
|
|
}
|
|
|
|
|
|
BOOL
|
|
pBinTreeCheck (
|
|
IN PBINTREE Tree
|
|
)
|
|
|
|
/*++
|
|
|
|
Routine Description:
|
|
|
|
pBinTreeCheck checks if the binary tree is sorted and linked properly. It
|
|
enumerates the binary tree structure and compares the strings for proper
|
|
order. If the tree is sorted properly, then the balance is checked.
|
|
|
|
Arguments:
|
|
|
|
Tree - Specifies the tree to check
|
|
|
|
Return Value:
|
|
|
|
TRUE if the binary tree is correct, FALSE otherwise.
|
|
|
|
--*/
|
|
|
|
{
|
|
BOOL flag;
|
|
PNODESTRUCT cur;
|
|
PNODESTRUCT prev;
|
|
|
|
prev = pBinTreeEnumFirst (Tree);
|
|
|
|
if (Tree) {
|
|
|
|
cur = pBinTreeEnumNext (prev);
|
|
|
|
while (cur) {
|
|
|
|
flag = (StringPasICompare (GetNodeDataStr(prev), GetNodeDataStr(cur)) < 0);
|
|
MYASSERT(flag);
|
|
|
|
if (!flag) {
|
|
return FALSE;
|
|
}
|
|
|
|
prev = cur;
|
|
cur = pBinTreeEnumNext (prev);
|
|
}
|
|
}
|
|
|
|
return pBinTreeCheckBalance (GetTreeRoot (Tree));
|
|
}
|
|
|
|
|
|
BOOL
|
|
BinTreeCheck (
|
|
UINT TreeOffset
|
|
)
|
|
|
|
/*++
|
|
|
|
Routine Description:
|
|
|
|
BinTreeCheck makes sure the specified binary tree is sorted and balanced
|
|
properly
|
|
|
|
Arguments:
|
|
|
|
TreeOffset - Specifies the offset of the tree to check
|
|
|
|
Return Value:
|
|
|
|
TRUE if the tree is sorted properly, FALSE otherwise.
|
|
|
|
--*/
|
|
|
|
{
|
|
PBINTREE tree;
|
|
|
|
tree = GetBinTree (TreeOffset);
|
|
|
|
return pBinTreeCheck (tree);
|
|
}
|
|
|
|
|
|
|
|
|
|
|
|
#include <stdio.h>
|
|
#include <math.h>
|
|
|
|
void indent (
|
|
IN UINT size)
|
|
{
|
|
UINT i;
|
|
for (i = 0; i < size; i++)
|
|
wprintf (L" ");
|
|
}
|
|
|
|
INT turn (
|
|
IN UINT num,
|
|
IN UINT sel,
|
|
IN UINT width
|
|
)
|
|
{
|
|
UINT temp = num;
|
|
|
|
MYASSERT (width > sel);
|
|
|
|
if ((temp >> (width-sel-1)) & 1)
|
|
return 1;
|
|
else
|
|
return -1;
|
|
}
|
|
|
|
#define SCREENWIDTH 64
|
|
|
|
void BinTreePrint(UINT TreeOffset)
|
|
{
|
|
PNODESTRUCT cur;
|
|
UINT i,j;
|
|
UINT level=0;
|
|
UINT numnodes,spacing;
|
|
BOOL printed;
|
|
PBINTREE tree;
|
|
PWSTR str;
|
|
UINT strsize,stringlen;
|
|
tree = GetBinTree(TreeOffset);
|
|
|
|
if (!GetTreeRoot(tree)) return;
|
|
|
|
while (level<31)
|
|
{
|
|
printed=FALSE;
|
|
|
|
if (level == 0) {
|
|
numnodes = 1;
|
|
} else {
|
|
numnodes = (UINT)pow ((double)2, (double)level);
|
|
}
|
|
|
|
spacing=SCREENWIDTH / numnodes;
|
|
|
|
for (i=0;i<numnodes;i++)
|
|
{
|
|
cur = GetTreeRoot(tree);
|
|
j=0;
|
|
while (j<level && cur!=NULL)
|
|
{
|
|
if (turn(i,j,level)<0)
|
|
cur = GetNodeStruct(cur->Left);
|
|
else
|
|
cur = GetNodeStruct(cur->Right);
|
|
j++;
|
|
}
|
|
|
|
if (cur==NULL) {
|
|
indent(spacing);
|
|
} else {
|
|
str=GetNodeDataStr(cur);
|
|
strsize=StringPasCharCount(str);
|
|
StringPasConvertFrom(str);
|
|
printed=TRUE;
|
|
if (cur->LeftDepth==0 && cur->RightDepth==0) {
|
|
stringlen=strsize+1;
|
|
indent((spacing-stringlen)/2);
|
|
wprintf(L"%s ",str);
|
|
} else {
|
|
stringlen=strsize+2;
|
|
indent((spacing-stringlen)/2);
|
|
wprintf(L"%s%1d%1d",str,cur->LeftDepth,cur->RightDepth);
|
|
}
|
|
indent(spacing-((spacing-stringlen)/2)-stringlen);
|
|
StringPasConvertTo(str);
|
|
}
|
|
}
|
|
|
|
wprintf(L"\n");
|
|
if (!printed)
|
|
break;
|
|
level++;
|
|
}
|
|
}
|
|
|
|
|
|
|
|
UINT BinTreeGetSizeOfStruct(DWORD Signature)
|
|
{
|
|
switch (Signature)
|
|
{
|
|
case NODESTRUCT_SIGNATURE:
|
|
return NODESTRUCT_SIZE;
|
|
case BINTREE_SIGNATURE:
|
|
return BINTREE_SIZE;
|
|
case LISTELEM_SIGNATURE:
|
|
return LISTELEM_SIZE;
|
|
default:
|
|
return 0;
|
|
}
|
|
}
|
|
|
|
|
|
BOOL pBinTreeFindTreeInDatabase(UINT TreeOffset)
|
|
{
|
|
PBINTREE Tree;
|
|
|
|
if (!g_UseDebugStructs) {
|
|
return TRUE;
|
|
}
|
|
if (TreeOffset==INVALID_OFFSET)
|
|
return FALSE;
|
|
|
|
Tree=GetBinTree(TreeOffset);
|
|
|
|
if (Tree->Deleted) {
|
|
return TRUE;
|
|
}
|
|
|
|
if (!GetTreeRoot(Tree)) {
|
|
DEBUGMSG ((
|
|
DBG_ERROR,
|
|
"MemDbCheckDatabase: Binary tree at offset 0x%08lX is Empty!",
|
|
TreeOffset
|
|
));
|
|
return FALSE;
|
|
}
|
|
|
|
return BinTreeFindStructInDatabase(NODESTRUCT_SIGNATURE, GetNodeOffset(GetTreeRoot(Tree)));
|
|
}
|
|
|
|
BOOL pBinTreeFindNodeInDatabase(UINT NodeOffset)
|
|
{
|
|
UINT Index;
|
|
PNODESTRUCT Node;
|
|
|
|
if (!g_UseDebugStructs) {
|
|
return TRUE;
|
|
}
|
|
if (NodeOffset == INVALID_OFFSET)
|
|
return FALSE;
|
|
|
|
Node=GetNodeStruct(NodeOffset);
|
|
if (Node->Deleted || Node->InsertionHead) {
|
|
return TRUE;
|
|
}
|
|
|
|
Index = GetNodeData(Node);
|
|
|
|
if (Index==INVALID_OFFSET) {
|
|
|
|
DEBUGMSG ((
|
|
DBG_ERROR,
|
|
"MemDbCheckDatabase: Data of Node at offset 0x%8lX is Invalid!",
|
|
NodeOffset
|
|
));
|
|
return FALSE;
|
|
}
|
|
|
|
return FindKeyStructInDatabase(KeyIndexToOffset(Index));
|
|
}
|
|
|
|
|
|
BOOL BinTreeFindStructInDatabase(DWORD Sig, UINT Offset)
|
|
{
|
|
switch (Sig)
|
|
{
|
|
case NODESTRUCT_SIGNATURE:
|
|
return (pBinTreeFindNodeInDatabase(Offset));
|
|
case BINTREE_SIGNATURE:
|
|
return (pBinTreeFindTreeInDatabase(Offset));
|
|
case LISTELEM_SIGNATURE:
|
|
return TRUE;
|
|
default:
|
|
DEBUGMSG ((
|
|
DBG_ERROR,
|
|
"MemDbCheckDatabase: Invalid BinTree Struct!"
|
|
));
|
|
printf("Invalid BinTree struct!\n");
|
|
}
|
|
return FALSE;
|
|
}
|
|
|
|
#endif
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|