windows-xp/Source/XPSP1/NT/base/ntsetup/win95upg/common/memdb/bintree.c

/*++

Copyright (c) 1996 Microsoft Corporation

Module Name:

    bintree.c

Abstract:

    Routines that manage the memdb binary tree structures.

Author:

    Jim Schmidt (jimschm) 8-Aug-1996

Revision History:

    jimschm     30-Dec-1998  Hacked in AVL balancing
    jimschm     23-Sep-1998  Proxy nodes, so MemDbMoveTree can replace end nodes too
    jimschm     29-May-1998  Ability to replace center nodes in key strings
    jimschm     21-Oct-1997  Split from memdb.c

--*/

#include "pch.h"
#include "memdbp.h"

#ifndef UNICODE
#error UNICODE required
#endif

#define MAX_MEMDB_SIZE  0x08000000  //128 MB
#define KSF_FLAGS_TO_COPY       (KSF_USERFLAG_MASK|KSF_ENDPOINT|KSF_BINARY|KSF_PROXY_NODE)

DWORD
pNewKey (
    IN  PCWSTR KeyStr,
    IN  PCWSTR KeyStrWithHive,
    IN  BOOL Endpoint
    );

DWORD
pAllocKeyToken (
    IN      PCWSTR KeyName,
    OUT     PINT AdjustFactor
    );

VOID
pDeallocToken (
    IN      DWORD Token
    );

DWORD
pFindPatternKeyWorker (
    IN      PCWSTR SubKey,
    IN      PCWSTR End,
    IN      DWORD RootOffset,
    IN      BOOL EndPatternAllowed
    );

#ifdef DEBUG
VOID
pDumpTree (
    IN      DWORD Root,
    IN      PCSTR Title         OPTIONAL
    );

VOID
pCheckBalanceFactors (
    IN      DWORD Root
    );

DWORD g_SingleRotations = 0;
DWORD g_DoubleRotations = 0;
DWORD g_Deletions = 0;
DWORD g_Insertions = 0;

#define INCSTAT(x)      (x++)

#else

#define pDumpTree(arg1,arg2)
#define INCSTAT(x)

#endif


#define ANTIDIRECTION(x)        ((x)^KSF_BALANCE_MASK)
#define FLAGS_TO_INT(x)         ((INT) ((x)==KSF_LEFT_HEAVY ? -1 : (x)==KSF_RIGHT_HEAVY ? 1 : 0))
#define INT_TO_FLAGS(x)         ((DWORD) ((x)==-1 ? KSF_LEFT_HEAVY : (x)==1 ? KSF_RIGHT_HEAVY : 0))

//
// Implementation
//


DWORD
pRotateOnce (
    OUT     PDWORD RootPtr,
    IN      DWORD ParentOffset,
    IN      DWORD PivotOffset,
    IN      DWORD Direction
    )
{
    PKEYSTRUCT GrandParent;
    PKEYSTRUCT Parent;
    PKEYSTRUCT Pivot;
    PKEYSTRUCT TempKey;
    DWORD Temp;
    INT OldRootBalance;
    INT NewRootBalance;
    DWORD OldDir, NewDir;

    INCSTAT(g_SingleRotations);

    MYASSERT (ParentOffset != INVALID_OFFSET);
    MYASSERT (PivotOffset != INVALID_OFFSET);

    Parent = GetKeyStruct (ParentOffset);
    Pivot = GetKeyStruct (PivotOffset);

    if (Direction == KSF_LEFT_HEAVY) {
        //
        // Perform LL rotation
        //

        Temp = Pivot->Right;

        Pivot->Right = ParentOffset;
        Pivot->Parent = Parent->Parent;
        Parent->Parent = PivotOffset;

        Parent->Left = Temp;

    } else {
        //
        // Preform RR rotation
        //

        Temp = Pivot->Left;

        Pivot->Left = ParentOffset;
        Pivot->Parent = Parent->Parent;
        Parent->Parent = PivotOffset;

        Parent->Right = Temp;
    }

    if (Temp != INVALID_OFFSET) {

        TempKey = GetKeyStruct (Temp);
        TempKey->Parent = ParentOffset;

    }

    OldDir = Parent->Flags & KSF_BALANCE_MASK;
    NewDir = Pivot->Flags & KSF_BALANCE_MASK;

    OldRootBalance  = FLAGS_TO_INT (OldDir);
    NewRootBalance  = FLAGS_TO_INT (NewDir);

    if (Direction == KSF_LEFT_HEAVY) {
        OldRootBalance = -(++NewRootBalance);
    } else {
        OldRootBalance = -(--NewRootBalance);
    }

    Pivot->Flags = (Pivot->Flags & (~KSF_BALANCE_MASK)) | INT_TO_FLAGS(NewRootBalance);
    Parent->Flags = (Parent->Flags & (~KSF_BALANCE_MASK)) | INT_TO_FLAGS(OldRootBalance);

    //
    // Fix grandparent/root to parent linkage
    //

    if (Pivot->Parent != INVALID_OFFSET) {
        GrandParent = GetKeyStruct (Pivot->Parent);

        if (GrandParent->Left == ParentOffset) {
            GrandParent->Left = PivotOffset;
        } else {
            GrandParent->Right = PivotOffset;
        }

    } else {
        *RootPtr = PivotOffset;
    }

    return PivotOffset;
}


DWORD
pRotateTwice (
    OUT     PDWORD RootPtr,
    IN      DWORD ParentOffset,
    IN      DWORD PivotOffset,
    IN      DWORD Direction
    )
{
    PKEYSTRUCT GrandParent;
    PKEYSTRUCT Parent;
    PKEYSTRUCT Pivot;
    PKEYSTRUCT Child;
    DWORD ChildOffset;
    PKEYSTRUCT GrandChildLeft;
    PKEYSTRUCT GrandChildRight;
    DWORD AntiDirection;
    DWORD Flag;
    INT ParentDir;
    INT PivotDir;
    INT ChildDir;

    INCSTAT(g_DoubleRotations);

    //
    // Initialize pointers
    //

    MYASSERT (ParentOffset != INVALID_OFFSET);
    MYASSERT (PivotOffset != INVALID_OFFSET);

    Parent = GetKeyStruct (ParentOffset);
    Pivot = GetKeyStruct (PivotOffset);

    if (Direction == KSF_LEFT_HEAVY) {
        AntiDirection = KSF_RIGHT_HEAVY;
        ChildOffset = Pivot->Right;
    } else {
        AntiDirection = KSF_LEFT_HEAVY;
        ChildOffset = Pivot->Left;
    }

    MYASSERT (ChildOffset != INVALID_OFFSET);
    Child = GetKeyStruct (ChildOffset);

    if (Child->Left != INVALID_OFFSET) {
        GrandChildLeft = GetKeyStruct (Child->Left);
    } else {
        GrandChildLeft = NULL;
    }

    if (Child->Right != INVALID_OFFSET) {
        GrandChildRight = GetKeyStruct (Child->Right);
    } else {
        GrandChildRight = NULL;
    }

    //
    // Perform the rotation
    //

    if (Direction == KSF_LEFT_HEAVY) {
        //
        // Perform LR rotation
        //

        Child->Parent = Parent->Parent;

        Parent->Left = Child->Right;
        if (GrandChildRight) {
            GrandChildRight->Parent = ParentOffset;
        }

        Pivot->Right = Child->Left;
        if (GrandChildLeft) {
            GrandChildLeft->Parent = PivotOffset;
        }

        Child->Left = PivotOffset;
        Pivot->Parent = ChildOffset;

        Child->Right = ParentOffset;
        Parent->Parent = ChildOffset;

    } else {
        //
        // Preform RL rotation
        //

        Child->Parent = Parent->Parent;

        Parent->Right = Child->Left;
        if (GrandChildLeft) {
            GrandChildLeft->Parent = ParentOffset;
        }

        Pivot->Left = Child->Right;
        if (GrandChildRight) {
            GrandChildRight->Parent = PivotOffset;
        }

        Child->Right = PivotOffset;
        Pivot->Parent = ChildOffset;

        Child->Left = ParentOffset;
        Parent->Parent = ChildOffset;


    }

    //
    // Fix balance factors
    //

    Flag = Child->Flags & KSF_BALANCE_MASK;
    ChildDir = FLAGS_TO_INT (Flag);

    if (Direction == KSF_RIGHT_HEAVY) {
        ParentDir = -max (ChildDir, 0);
        PivotDir  = -min (ChildDir, 0);
    } else {
        ParentDir = -min (ChildDir, 0);
        PivotDir  = -max (ChildDir, 0);
    }

    Parent->Flags = Parent->Flags & (~KSF_BALANCE_MASK) | INT_TO_FLAGS(ParentDir);
    Pivot->Flags  = Pivot->Flags & (~KSF_BALANCE_MASK) | INT_TO_FLAGS(PivotDir);
    Child->Flags  = Child->Flags & (~KSF_BALANCE_MASK);

    //
    // Fix grandparent/root to parent linkage
    //

    if (Child->Parent != INVALID_OFFSET) {
        GrandParent = GetKeyStruct (Child->Parent);

        if (GrandParent->Left == ParentOffset) {
            GrandParent->Left = ChildOffset;
        } else {
            GrandParent->Right = ChildOffset;
        }

    } else {
        *RootPtr = ChildOffset;
    }

    return ChildOffset;
}


VOID
pBalanceInsertion (
    OUT     PDWORD RootPtr,
    IN      DWORD ChangedNode,
    IN      DWORD PivotEnd
    )
{
    DWORD PrevPivot;
    DWORD PivotNode;
    PKEYSTRUCT KeyStruct;
    PKEYSTRUCT KeyParent;
    DWORD BalanceFlags;

    PivotNode = ChangedNode;
    MYASSERT (PivotNode != INVALID_OFFSET);

    //
    // Initialize previous pivot to be the changed node,
    // and begin balancing at its parent
    //

    PrevPivot = PivotNode;
    KeyStruct = GetKeyStruct (PivotNode);
    PivotNode = KeyStruct->Parent;

    //
    // Balance the tree starting at the changed node and going
    // up until PivotEnd is reached.  PivotEnd is the offset to
    // the deepest node with a balance of non-zero.
    //

    MYASSERT (PivotNode != INVALID_OFFSET || PivotNode == PivotEnd);

    while (PivotNode != INVALID_OFFSET) {

        KeyParent = GetKeyStruct (PivotNode);

        BalanceFlags = KeyParent->Flags & KSF_BALANCE_MASK;

        if (BalanceFlags == KSF_LEFT_HEAVY) {

            if (KeyParent->Left == PrevPivot) {

                MYASSERT (KeyStruct == GetKeyStruct (PrevPivot));

                if (KeyStruct->Flags & KSF_LEFT_HEAVY) {
                    //
                    // LL rotation
                    //

                    pRotateOnce (RootPtr, PivotNode, PrevPivot, KSF_LEFT_HEAVY);

                } else if (KeyStruct->Flags & KSF_RIGHT_HEAVY) {
                    //
                    // LR rotation
                    //

                    pRotateTwice (RootPtr, PivotNode, PrevPivot, KSF_LEFT_HEAVY);

                }

            } else {
                KeyParent->Flags = KeyParent->Flags & (~KSF_BALANCE_MASK);
            }

        } else if (BalanceFlags == KSF_RIGHT_HEAVY) {

            if (KeyParent->Right == PrevPivot) {

                MYASSERT (KeyStruct == GetKeyStruct (PrevPivot));

                if (KeyStruct->Flags & KSF_RIGHT_HEAVY) {
                    //
                    // RR rotation
                    //

                    pRotateOnce (RootPtr, PivotNode, PrevPivot, KSF_RIGHT_HEAVY);

                } else if (KeyStruct->Flags & KSF_LEFT_HEAVY) {
                    //
                    // RL rotation
                    //

                    pRotateTwice (RootPtr, PivotNode, PrevPivot, KSF_RIGHT_HEAVY);

                }

            } else {
                KeyParent->Flags = KeyParent->Flags & (~KSF_BALANCE_MASK);
            }

        } else {
            if (KeyParent->Right == PrevPivot) {
                KeyParent->Flags = (KeyParent->Flags & (~KSF_BALANCE_MASK)) | KSF_RIGHT_HEAVY;
            } else {
                KeyParent->Flags = (KeyParent->Flags & (~KSF_BALANCE_MASK)) | KSF_LEFT_HEAVY;
            }
        }

        if (PivotNode == PivotEnd) {
            break;
        }

        PrevPivot = PivotNode;
        PivotNode = KeyParent->Parent;
        KeyStruct = KeyParent;
    }
}


VOID
pBalanceDeletion (
    OUT     PDWORD RootPtr,
    IN      DWORD NodeNeedingAdjustment,
    IN      DWORD Direction
    )
{
    PKEYSTRUCT KeyStruct;
    PKEYSTRUCT ChildStruct;
    DWORD ChildOffset;
    DWORD Node;
    DWORD AntiDirection;
    DWORD OldNode;
    DWORD OrgParent;

    Node = NodeNeedingAdjustment;
    MYASSERT (Node != INVALID_OFFSET);

    KeyStruct = GetKeyStruct (Node);

    for (;;) {

        MYASSERT (KeyStruct == GetKeyStruct (Node));
        AntiDirection = ANTIDIRECTION (Direction);
        OrgParent = KeyStruct->Parent;

        //
        // Case 1 - parent was initially balanced (terminates balancing)
        //

        if (!(KeyStruct->Flags & KSF_BALANCE_MASK)) {
            KeyStruct->Flags |= AntiDirection;
            break;
        }

        //
        // Case 2 - parent was heavy on side that was deleted
        //

        if (KeyStruct->Flags & Direction) {
            KeyStruct->Flags = KeyStruct->Flags & (~KSF_BALANCE_MASK);
        }

        //
        // Cases 3, 4 and 5 - deletion caused imbalance in parent
        //

        else {
            MYASSERT (KeyStruct->Flags & AntiDirection);

            ChildOffset = Direction == KSF_LEFT_HEAVY ?
                                KeyStruct->Right :
                                KeyStruct->Left;

            MYASSERT (ChildOffset != INVALID_OFFSET);

            ChildStruct = GetKeyStruct (ChildOffset);

            if (!(ChildStruct->Flags & KSF_BALANCE_MASK)) {
                //
                // Case 3 - single rotation needed (terminates balancing).  We
                //          don't care that Node changes during rotation.
                //

                pRotateOnce (RootPtr, Node, ChildOffset, AntiDirection);
                break;

            } else if (ChildStruct->Flags & Direction) {
                //
                // Case 4 - double rotation needed, Node is changed during rotation
                //

                Node = pRotateTwice (RootPtr, Node, ChildOffset, AntiDirection);

            } else {
                //
                // Case 5 - single rotation needed, Node is changed during rotation
                //

                Node = pRotateOnce (RootPtr, Node, ChildOffset, AntiDirection);
            }
        }

        //
        // Continue climbing the tree
        //

        OldNode = Node;
        Node = OrgParent;

        if (Node != INVALID_OFFSET) {
            KeyStruct = GetKeyStruct (Node);

            if (KeyStruct->Left == OldNode) {
                Direction = KSF_LEFT_HEAVY;
            } else {
                Direction = KSF_RIGHT_HEAVY;
            }
        } else {
            break;
        }
    }


}


#ifdef DEBUG

VOID
DumpBinTreeStats (
    VOID
    )
{
    DEBUGMSG ((
        DBG_STATS,
        "MemDb Binary Tree Stats:\n\n"
            "  Insertions: %u\n"
            "  Deletions: %u\n"
            "  Single Rotations: %u\n"
            "  Double Rotations: %u\n",
        g_Insertions,
        g_Deletions,
        g_SingleRotations,
        g_DoubleRotations
        ));
}


INT
pComputeHeight (
    IN      DWORD Offset
    )
{
    PKEYSTRUCT KeyStruct;
    INT Left, Right;

    if (Offset == INVALID_OFFSET) {
        return 0;
    }

    KeyStruct = GetKeyStruct (Offset);

    Left = pComputeHeight (KeyStruct->Left);
    Right = pComputeHeight (KeyStruct->Right);

    return 1 + max (Left, Right);
}


VOID
pMakeNum (
    OUT     PTSTR Msg,
    IN      DWORD Offset,
    IN      TCHAR LeftChar,
    IN      TCHAR RightChar
    )
{
    TCHAR Num[32];
    INT Len;
    PTSTR OrgMsg;
    INT i;

    _stprintf (Num, TEXT("%u"), Offset);
    Len = (6 - TcharCount (Num)) / 2;

    OrgMsg = Msg;

    for (i = 0 ; i < Len ; i++) {
        *Msg++ = LeftChar;
    }

    for (i = 0 ; Num[i] ; i++) {
        *Msg++ = Num[i];
    }

    OrgMsg += 6;
    while (Msg < OrgMsg) {
        *Msg++ = RightChar;
    }

    *Msg = 0;
}


VOID
pDumpTree (
    IN      DWORD Root,
    IN      PCSTR Title         OPTIONAL
    )
{
    DWORD Offset;
    PKEYSTRUCT KeyStruct;
    PKEYSTRUCT KeyParent;
    DWORD MaxLevel;
    DWORD Spaces;
    UINT u;
    TCHAR Msg[16384];
    UINT Pos;
    INT Pass;
    GROWBUFFER NodesA = GROWBUF_INIT;
    GROWBUFFER NodesB = GROWBUF_INIT;
    PGROWBUFFER Nodes;
    PGROWBUFFER NextNodes;
    PDWORD OffsetPtr;
    PDWORD EndOfList;
    INT HalfWidth;
    TCHAR LeftChar, RightChar;

    if (Root == INVALID_OFFSET) {
        return;
    }

    if (Title) {
        LOGDIRECTA (DBG_VERBOSE, "\r\n");
        LOGDIRECTA (DBG_VERBOSE, Title);
        LOGDIRECTA (DBG_VERBOSE, "\r\n\r\n");
    }

    for (Pass = 0 ; Pass < 2 ; Pass++) {

        MaxLevel = (DWORD) pComputeHeight (Root);
        MaxLevel = min (MaxLevel, 10);

        if (Pass == 0) {
            HalfWidth = 3;
            Spaces = 6;
        } else {
            HalfWidth = 1;
            Spaces = 2;
        }

        for (u = 1 ; u < MaxLevel ; u++) {
            Spaces *= 2;
        }

        NodesB.End = 0;
        Nodes = &NodesA;
        NextNodes = &NodesB;

        GrowBufAppendDword (NextNodes, Root);

        for (u = 0 ; u < MaxLevel ; u++) {

            //
            // Swap growbufs
            //

            if (Nodes == &NodesA) {
                Nodes = &NodesB;
                NextNodes = &NodesA;
            } else {
                Nodes = &NodesA;
                NextNodes = &NodesB;
            }

            NextNodes->End = 0;

            //
            // Process all nodes
            //

            EndOfList = (PDWORD) (Nodes->Buf + Nodes->End);

            for (OffsetPtr = (PDWORD) (Nodes->Buf) ; OffsetPtr < EndOfList ; OffsetPtr++) {

                //
                // Add all children as next nodes
                //

                Offset = *OffsetPtr;

                if (Offset == INVALID_OFFSET) {
                    GrowBufAppendDword (NextNodes, INVALID_OFFSET);
                    GrowBufAppendDword (NextNodes, INVALID_OFFSET);
                } else {
                    KeyStruct = GetKeyStruct (Offset);
                    GrowBufAppendDword (NextNodes, KeyStruct->Left);
                    GrowBufAppendDword (NextNodes, KeyStruct->Right);
                }

                //
                // Print current node
                //

                Pos = 0;

                LeftChar = TEXT(' ');
                RightChar = TEXT(' ');

                if (Offset != INVALID_OFFSET) {
                    KeyStruct = GetKeyStruct (Offset);

                    if (KeyStruct->Parent != INVALID_OFFSET) {

                        KeyParent = GetKeyStruct (KeyStruct->Parent);

                        if (KeyParent->Right == Offset) {
                            LeftChar = TEXT('\'');
                        } else if (KeyParent->Left == Offset) {
                            RightChar = TEXT('\'');
                        }
                    }

                    for ( ; Pos < (Spaces - HalfWidth) ; Pos++) {
                        Msg[Pos] = LeftChar;
                    }

                    if (Pass == 0) {
                        pMakeNum (Msg + Pos, Offset, LeftChar, RightChar);
                    } else {
                        _stprintf (Msg + Pos, TEXT("%2i"), FLAGS_TO_INT (KeyStruct->Flags & KSF_BALANCE_MASK));
                    }

                    Pos += TcharCount (Msg + Pos);
                }

                while (Pos < Spaces * 2) {
                    Msg[Pos] = RightChar;
                    Pos++;
                }

                Msg[Pos] = 0;

                LOGDIRECT (DBG_VERBOSE, Msg);

            }

            LOGDIRECT (DBG_VERBOSE, TEXT("\r\n"));

            for (OffsetPtr = (PDWORD) (Nodes->Buf) ; OffsetPtr < EndOfList ; OffsetPtr++) {

                Offset = *OffsetPtr;

                for (Pos = 0 ; Pos < Spaces ; Pos++) {
                    Msg[Pos] = TEXT(' ');
                }

                if (Offset != INVALID_OFFSET) {
                    KeyStruct = GetKeyStruct (*OffsetPtr);
                    if (KeyStruct->Left != INVALID_OFFSET ||
                        KeyStruct->Right != INVALID_OFFSET
                        ) {
                        Msg[Pos] = '|';
                        Pos++;
                    }
                }

                while (Pos < Spaces * 2) {
                    Msg[Pos] = TEXT(' ');
                    Pos++;
                }

                Msg[Pos] = 0;

                LOGDIRECT (DBG_VERBOSE, Msg);
            }

            Spaces /= 2;
            LOGDIRECT (DBG_VERBOSE, TEXT("\r\n"));

            Spaces = max (Spaces, 1);
        }

        LOGDIRECT (DBG_VERBOSE, TEXT("\r\n"));
    }

    FreeGrowBuffer (&NodesA);
    FreeGrowBuffer (&NodesB);
}


BOOL
pCheckTreeBalance (
    IN      DWORD Root,
    IN      BOOL Force
    )
{
    DWORD NextOffset;
    DWORD PrevOffset;
    DWORD Offset;
    PKEYSTRUCT KeyStruct;
    DWORD MinLevel = 0xFFFFFFFF;
    DWORD MaxLevel = 0;
    DWORD Level = 0;
    DWORD Nodes = 0;
    static DWORD SpotCheck = 0;

    //
    // Don't perform this check every single time
    //

    if (!Force) {
        SpotCheck++;
        if (SpotCheck == 10000) {
            SpotCheck = 0;
        } else {
            return FALSE;
        }
    }

    if (Root == INVALID_OFFSET) {
        return FALSE;
    }

    pCheckBalanceFactors (Root);

    NextOffset = Root;

    //
    // Get leftmost node
    //

    do {
        Offset = NextOffset;
        Level++;
        KeyStruct = GetKeyStruct (Offset);
        NextOffset = KeyStruct->Left;
    } while (NextOffset != INVALID_OFFSET);

    //
    // Recurse through entire tree
    //

    PrevOffset = INVALID_OFFSET;

    do {
        //
        // Visit node at Offset
        //

        Nodes++;
        KeyStruct = GetKeyStruct (Offset);

        if (KeyStruct->Left == INVALID_OFFSET ||
            KeyStruct->Right == INVALID_OFFSET
            ) {

            MinLevel = min (MinLevel, Level);
            MaxLevel = max (MaxLevel, Level);
        }

        //
        // Go to the next node
        //

        if (KeyStruct->Right != INVALID_OFFSET) {

            //
            // Go to left-most node of right
            //

            KeyStruct = GetKeyStruct (Offset);
            NextOffset = KeyStruct->Right;

            while (NextOffset != INVALID_OFFSET) {
                Offset = NextOffset;
                Level++;
                KeyStruct = GetKeyStruct (Offset);
                NextOffset = KeyStruct->Left;
            }
        }

        else {

            //
            // Go to parent, looping if its right child is the
            // previous node.
            //

            do {
                PrevOffset = Offset;
                Offset = KeyStruct->Parent;
                Level--;

                if (Offset == INVALID_OFFSET) {
                    break;
                }

                KeyStruct = GetKeyStruct (Offset);

            } while (KeyStruct->Right == PrevOffset);
        }

    } while (Offset != INVALID_OFFSET);

    DEBUGMSG_IF ((
        (MaxLevel - MinLevel) > 3,
        DBG_NAUSEA,
        "Binary tree imbalance detected: MinLevel=%u, MaxLevel=%u, Nodes=%u",
        MinLevel,
        MaxLevel,
        Nodes
        ));

    return TRUE;
}


INT
pComputeBalanceFactor (
    IN      DWORD Offset
    )
{
    PKEYSTRUCT KeyStruct;

    KeyStruct = GetKeyStruct (Offset);

    return pComputeHeight (KeyStruct->Right) - pComputeHeight (KeyStruct->Left);
}


VOID
pCheckBalanceFactors (
    IN      DWORD Root
    )
{
    DWORD Offset;
    INT Factor;
    PKEYSTRUCT KeyStruct;

    Offset = GetFirstOffset (Root);

    while (Offset != INVALID_OFFSET) {

        KeyStruct = GetKeyStruct (Offset);
        Factor = pComputeBalanceFactor (Offset);

        if ((Factor == -1 && !(KeyStruct->Flags & KSF_LEFT_HEAVY)) ||
            (Factor == 1  && !(KeyStruct->Flags & KSF_RIGHT_HEAVY)) ||
            (!Factor      &&  (KeyStruct->Flags & KSF_BALANCE_MASK))
            ) {

            pDumpTree (Root, "Tree Balance Factor Error");
            DEBUGMSG ((DBG_WHOOPS, "Tree balance factors are wrong!"));
            break;
        }

        if (Factor < -1 || Factor > 1) {

            pDumpTree (Root, "Balance Factor Out of Bounds.");
            DEBUGMSG ((DBG_WHOOPS, "Balance factors out of bounds!"));
            break;
       }



        Offset = GetNextOffset (Offset);
    }
}

#endif

PBYTE
pAllocMemoryFromDb (
    IN      UINT RequestSize,
    OUT     PDWORD Offset,
    OUT     PINT AdjustFactor
    )
{
    PBYTE result;
    PBYTE newBuf;

    //
    // Grow heap if necessary
    //

    *AdjustFactor = 0;

    if (RequestSize + g_db->End > g_db->AllocSize) {
        if (g_db->AllocSize < 0x100000) {
            g_db->AllocSize += BLOCK_SIZE;
        } else {
            g_db->AllocSize *= 2;
        }

        if (g_db->AllocSize >= MAX_MEMDB_SIZE) {
            OutOfMemory_Terminate ();
        }

        if (g_db->Buf) {
            newBuf = (PBYTE) MemReAlloc (g_hHeap, 0, g_db->Buf, g_db->AllocSize);
        } else {
            newBuf = (PBYTE) MemAlloc (g_hHeap, 0, g_db->AllocSize);
        }

        if (!newBuf) {
            // g_db->AllocSize must be bigger than 2G
            OutOfMemory_Terminate();
        }

        //
        // provide relocation difference to caller
        //

        if (g_db->Buf) {
            *AdjustFactor = (INT) ((PBYTE) newBuf - (PBYTE) g_db->Buf);
        }

        g_db->Buf = newBuf;
    }

    result = g_db->Buf + g_db->End;
    *Offset = g_db->End;
    g_db->End += RequestSize;

    return result;
}

PKEYSTRUCT
pAllocKeyStructBlock (
    OUT     PDWORD Offset,
    OUT     PINT AdjustFactor
    )
{
    DWORD delOffset;
    DWORD prevDel;
    PKEYSTRUCT keyStruct = NULL;

    //
    // Look for free block
    //

    *AdjustFactor = 0;

    prevDel = INVALID_OFFSET;
    delOffset = g_db->FirstDeleted;

    while (delOffset != INVALID_OFFSET) {
        keyStruct = GetKeyStruct (delOffset);
        prevDel = delOffset;
        delOffset = keyStruct->NextDeleted;
    }

    //
    // Alloc new block if no free space
    //

    if (delOffset == INVALID_OFFSET) {

        //
        // Calc position in block
        //

        keyStruct = (PKEYSTRUCT) pAllocMemoryFromDb (sizeof (KEYSTRUCT), Offset, AdjustFactor);

    } else {
        //
        // Delink free block if recovering free space
        //

        *Offset = delOffset;

        if (prevDel != INVALID_OFFSET) {
            GetKeyStruct (prevDel)->NextDeleted = keyStruct->NextDeleted;
        } else {
            g_db->FirstDeleted = keyStruct->NextDeleted;
        }
    }

    return keyStruct;
}


DWORD
pAllocKeyStruct (
    IN OUT PDWORD ParentOffsetPtr,
    IN     PCWSTR KeyName,
    IN     DWORD PrevLevelNode
    )

/*++

Routine Description:

  pAllocKeyStruct allocates a block of memory in the single
  heap, expanding it if necessary.

  The KeyName must not already be in the tree, and
  ParentOffsetPtr must point to a valid DWORD offset
  variable.  ParentOffsetPtr, or one of the children
  of ParentOffsetPtr, will be linked to the new struct.

Arguments:

  ParentOffsetPtr  - Address of a DWORD that holds the offset to
                     the root.  Within the function, the variable
                     will change to point to the parent of the
                     new struct.

  KeyName - The string identifying the key.  It cannot
            contain backslashes.  The new struct will
            be initialized and this name will be copied
            into the struct.

  PrevLevelNode - Specifies the previous level root offset

Return Value:

  An offset to the new structure.

--*/

{
    PKEYSTRUCT KeyStruct;
    PKEYSTRUCT KeyParent;
    DWORD Offset;
    DWORD NodeOffsetParent;
    INT cmp;
    DWORD PivotEnd;
    PDWORD RootPtr;
    INT adjustFactor;
    DWORD newToken;

    INCSTAT(g_Insertions);

#ifdef DEBUG
    pCheckTreeBalance (*ParentOffsetPtr, FALSE);
#endif

    KeyStruct = pAllocKeyStructBlock (
                    &Offset,
                    &adjustFactor
                    );

    //
    // Database might have moved. Relocate any pointers within the database now.
    //

    if (ParentOffsetPtr != &g_db->FirstLevelRoot) {
        ParentOffsetPtr = (PDWORD) ((PBYTE) ParentOffsetPtr + adjustFactor);
    }

    //
    // Init new block
    //

    KeyStruct->NextLevelRoot = INVALID_OFFSET;
    KeyStruct->PrevLevelNode = PrevLevelNode;
    KeyStruct->Left = INVALID_OFFSET;
    KeyStruct->Right = INVALID_OFFSET;
    KeyStruct->dwValue = 0;
    KeyStruct->Flags = 0;
#ifdef DEBUG
    KeyStruct->Signature = SIGNATURE;
#endif

    newToken = pAllocKeyToken (KeyName, &adjustFactor);

    //
    // Again the database might have moved
    //

    KeyStruct = (PKEYSTRUCT) ((PBYTE) KeyStruct + adjustFactor);

    if (ParentOffsetPtr != &g_db->FirstLevelRoot) {
        ParentOffsetPtr = (PDWORD) ((PBYTE) ParentOffsetPtr + adjustFactor);
    }

    //
    // finish updating keystruct
    //

    KeyStruct->KeyToken = newToken;

    //
    // Put it in the tree
    //

    NodeOffsetParent = INVALID_OFFSET;
    PivotEnd = INVALID_OFFSET;
    RootPtr = ParentOffsetPtr;

    while (*ParentOffsetPtr != INVALID_OFFSET) {

        NodeOffsetParent = *ParentOffsetPtr;

        KeyParent = GetKeyStruct (*ParentOffsetPtr);

        if (KeyParent->Flags & KSF_BALANCE_MASK) {
            PivotEnd = *ParentOffsetPtr;
        }

        cmp = StringICompareW (KeyName, GetKeyToken (KeyParent->KeyToken));

        if (cmp < 0) {
            ParentOffsetPtr = &KeyParent->Left;
        } else if (cmp > 0) {
            ParentOffsetPtr = &KeyParent->Right;
        } else {
            MYASSERT (FALSE);
        }
    }

    KeyStruct->Parent = NodeOffsetParent;
    *ParentOffsetPtr = Offset;

#ifdef DEBUG
    // If using retail structs, delete Signature from BlockPtr
    if (!g_UseDebugStructs) {
        MoveMemory (
            KeyStruct,
            (PCBYTE) KeyStruct + (sizeof (KEYSTRUCT_DEBUG) - sizeof (KEYSTRUCT_RETAIL)),
            sizeof (KEYSTRUCT_RETAIL)
            );
    }
#endif

    //
    // Balance the tree
    //

    pBalanceInsertion (RootPtr, Offset, PivotEnd);

#ifdef DEBUG
    pCheckTreeBalance (*RootPtr, FALSE);
#endif

    return Offset;
}


VOID
pDeallocKeyStruct (
    IN      DWORD Offset,
    IN OUT  PDWORD RootPtr,
    IN      BOOL DelinkFlag,
    IN      BOOL ClearFlag
    )

/*++

Routine Description:

  pDeallocKeyStruct first deletes all structures pointed to by
  NextLevelRoot.  After all items are deleted from the next
  level, pDeallocKeyStruct optionally delinks the struct from
  the binary tree.  Before exiting, the struct is given to the
  deleted block chain.

Arguments:

  Offset      - An offset to the item as provided by pAllocKeyStruct
                or any of the Find functions.
  RootPtr     - A pointer to the level tree root variable.  This value
                will be updated if delinking is involved.
  DelinkFlag  - A flag indicating TRUE to delink the struct from
                the binary tree it is in, or FALSE if the struct is
                only to be added to the deleted block chain.
  ClearFlag   - Specifies FALSE if the key struct's children are to
                be deleted, or TRUE if the current key struct should
                simply be cleaned up but left allocated.

Return Value:

  none

--*/

{
    PKEYSTRUCT KeyStruct;
    PKEYSTRUCT KeyParent;
    PKEYSTRUCT KeyChild;
    PKEYSTRUCT KeyLeftmost;
    PKEYSTRUCT KeyLeftChild;
    PKEYSTRUCT KeyRightChild;
    DWORD Leftmost;
    DWORD NodeOffset;
    PDWORD ParentOffsetPtr;
    WCHAR TempStr[MEMDB_MAX];
    DWORD Direction = 0;
    DWORD RebalanceOffset;

    KeyStruct = GetKeyStruct (Offset);

    //
    // Remove endpoints from hash table
    //

    if (KeyStruct->Flags & KSF_ENDPOINT) {
        PrivateBuildKeyFromOffset (0, Offset, TempStr, NULL, NULL, NULL);
        RemoveHashTableEntry (TempStr);

        //
        // Free binary value on key
        //

        FreeKeyStructBinaryBlock (KeyStruct);
        KeyStruct->Flags &= ~KSF_ENDPOINT;
    }

    //
    // Call recursively if there are sublevels to this key
    //

    if (!ClearFlag) {
        if (KeyStruct->NextLevelRoot != INVALID_OFFSET) {

            NodeOffset = GetFirstOffset (KeyStruct->NextLevelRoot);

            while (NodeOffset != INVALID_OFFSET) {
                pDeallocKeyStruct (NodeOffset, &KeyStruct->NextLevelRoot, FALSE, FALSE);
                NodeOffset = GetNextOffset (NodeOffset);
            }
        }

        //
        // Remove the item from its binary tree
        //

        if (DelinkFlag) {
            //
            // Find parent-to-child pointer
            //

            if (KeyStruct->Parent != INVALID_OFFSET) {

                KeyParent = GetKeyStruct (KeyStruct->Parent);

                if (KeyParent->Left == Offset) {
                    ParentOffsetPtr = &KeyParent->Left;
                    Direction = KSF_LEFT_HEAVY;
                } else {
                    ParentOffsetPtr = &KeyParent->Right;
                    Direction = KSF_RIGHT_HEAVY;
                }

            } else {
                ParentOffsetPtr = RootPtr;
            }

            if (KeyStruct->Left == INVALID_OFFSET &&
                KeyStruct->Right == INVALID_OFFSET
                ) {
                //
                // No children; reset parent, then rebalance tree
                //

                *ParentOffsetPtr = INVALID_OFFSET;
                RebalanceOffset = KeyStruct->Parent;

            } else if (KeyStruct->Left == INVALID_OFFSET) {
                //
                // Only a right child; bring it up a level and rebalance
                //

                *ParentOffsetPtr = KeyStruct->Right;
                KeyChild = GetKeyStruct (*ParentOffsetPtr);
                KeyChild->Parent = KeyStruct->Parent;

                //
                // The moved node's balance factor must be set the same as the
                // node we are deleting.  The rebalancing will correct it.
                //

                KeyChild->Flags = (KeyChild->Flags & (~KSF_BALANCE_MASK)) |
                                  (KeyStruct->Flags & KSF_BALANCE_MASK);

                Direction = KSF_RIGHT_HEAVY;
                RebalanceOffset = KeyStruct->Right;

            } else if (KeyStruct->Right == INVALID_OFFSET) {

                //
                // Only a left child; bring it up a level and rebalance
                //

                *ParentOffsetPtr = KeyStruct->Left;
                KeyChild = GetKeyStruct (*ParentOffsetPtr);
                KeyChild->Parent = KeyStruct->Parent;

                //
                // The moved node's balance factor must be set the same as the
                // node we are deleting.  The rebalancing will correct it.
                //

                KeyChild->Flags = (KeyChild->Flags & (~KSF_BALANCE_MASK)) |
                                  (KeyStruct->Flags & KSF_BALANCE_MASK);

                Direction = KSF_LEFT_HEAVY;
                RebalanceOffset = KeyStruct->Left;

            } else {

                //
                // Two children - find min val of right subtree (the leftmost node
                // of the right child).
                //

                Leftmost = KeyStruct->Right;

                KeyLeftmost = GetKeyStruct (Leftmost);

                while (KeyLeftmost->Left != INVALID_OFFSET) {
                    Leftmost = KeyLeftmost->Left;
                    KeyLeftmost = GetKeyStruct (Leftmost);
                }

                //
                // If Leftmost has right children, and it is not the
                // right child of the node we are deleting, then
                // hook right subtree to parent.
                //
                // If Leftmost does not have right children, then
                // remove its parent's linkage
                //

                if (Leftmost != KeyStruct->Right) {

                    KeyParent = GetKeyStruct (KeyLeftmost->Parent);

                    if (KeyLeftmost->Right != INVALID_OFFSET) {

                        //
                        // Because of the balance properties, we know that
                        // we have a single leaf node to the right.  Its
                        // balance factor is zero, and we move it to a
                        // position where it remains zero.
                        //

                        KeyRightChild = GetKeyStruct (KeyLeftmost->Right);
                        MYASSERT (KeyRightChild->Left == INVALID_OFFSET);
                        MYASSERT (KeyRightChild->Right == INVALID_OFFSET);

                        KeyParent->Left = KeyLeftmost->Right;
                        KeyRightChild->Parent = KeyLeftmost->Parent;

                    } else {

                        KeyParent->Left = INVALID_OFFSET;
                    }

                    //
                    // We are affecting the balance factor of the
                    // parent.  Rebalancing must start at the leftmost
                    // node's parent.
                    //

                    RebalanceOffset = KeyLeftmost->Parent;
                    Direction = KSF_LEFT_HEAVY;     // we deleted from the left side

                } else {
                    //
                    // In this case there is no leftmost node of the right child.
                    // Therefore, we reduced the height of the right side.
                    //

                    RebalanceOffset = Leftmost;
                    Direction = KSF_RIGHT_HEAVY;
                }

                //
                // Now leftmost is available to replace the deleted
                // node
                //

                KeyLeftmost->Parent = KeyStruct->Parent;
                *ParentOffsetPtr = Leftmost;

                KeyLeftmost->Left = KeyStruct->Left;
                KeyLeftChild = GetKeyStruct (KeyStruct->Left);
                KeyLeftChild->Parent = Leftmost;

                if (Leftmost != KeyStruct->Right) {

                    KeyLeftmost->Right = KeyStruct->Right;
                    MYASSERT (KeyStruct->Right != INVALID_OFFSET);

                    KeyRightChild = GetKeyStruct (KeyStruct->Right);
                    KeyRightChild->Parent = Leftmost;
                }

                //
                // We need to copy the balance factor of what we are deleting to the
                // replacement node.
                //

                KeyLeftmost->Flags = (KeyLeftmost->Flags & (~KSF_BALANCE_MASK)) |
                                     (KeyStruct->Flags & KSF_BALANCE_MASK);

            }

            //
            // Rebalance the tree
            //

            if (RebalanceOffset != INVALID_OFFSET) {
                MYASSERT (Direction);

                if (Direction) {
                    //pDumpTree (*RootPtr, "Before rebalance");
                    pBalanceDeletion (RootPtr, RebalanceOffset, Direction);
                    //pDumpTree (*RootPtr, "Final tree");
                }
            }

#ifdef DEBUG
            pCheckTreeBalance (*RootPtr, FALSE);
#endif

        }

        //
        // Donate block to free space unless caller does not
        // want child structs freed.
        //

        pDeallocToken (KeyStruct->KeyToken);
        KeyStruct->NextDeleted = g_db->FirstDeleted;

        g_db->FirstDeleted = Offset;
    }
}


VOID
pRemoveHashEntriesForNode (
    IN      PCWSTR Root,
    IN      DWORD Offset
    )

/*++

Routine Description:

  pRemoveHashEntriesFromNode removes all hash table entries from all children
  of the specified node.  This function is called recursively.

Arguments:

  Root   - Specifies the root string that corresponds with Offset.  This must
           also contain the temporary hive root.
  Offset - Specifies the offset of the node to process.  The node and all of
           its children will be removed from the hash table.

Return Value:

  None.

--*/

{
    DWORD ChildOffset;
    PKEYSTRUCT KeyStruct;
    WCHAR ChildRoot[MEMDB_MAX];
    PWSTR End;

    //
    // Remove hash entry if this root is an endpoint
    //

    KeyStruct = GetKeyStruct (Offset);

    if (KeyStruct->Flags & KSF_ENDPOINT) {
        RemoveHashTableEntry (Root);

#ifdef DEBUG
        {
            DWORD HashOffset;

            HashOffset = FindStringInHashTable (Root, NULL);
            if (HashOffset != INVALID_OFFSET) {
                DEBUGMSG ((DBG_WARNING, "Memdb move duplicate: %s", Root));
            }
        }
#endif
    }

    //
    // Recurse for all children, removing hash entries for all endpoints found
    //

    StringCopyW (ChildRoot, Root);
    End = GetEndOfStringW (ChildRoot);
    *End = L'\\';
    End++;
    *End = 0;

    ChildOffset = GetFirstOffset (KeyStruct->NextLevelRoot);

    while (ChildOffset != INVALID_OFFSET) {
        KeyStruct = GetKeyStruct (ChildOffset);
        StringCopyW (End, GetKeyToken (KeyStruct->KeyToken));
        pRemoveHashEntriesForNode (ChildRoot, ChildOffset);

        ChildOffset = GetNextOffset (ChildOffset);
    }
}


VOID
pAddHashEntriesForNode (
    IN      PCWSTR Root,
    IN      DWORD Offset,
    IN      BOOL AddRoot
    )

/*++

Routine Description:

  pAddHashEntriesForNode adds hash table entries for the specified root and
  all of its children.

Arguments:

  Root    - Specifies the root string that corresponds to Offset.  This string
            must also include the temporary hive root.
  Offset  - Specifies the node offset to begin processing.  The node and all
            of its children are added to the hash table.
  AddRoot - Specifies TRUE if the root should be added to the hash table,
            FALSE otherwise.


Return Value:

  None.

--*/

{
    DWORD ChildOffset;
    PKEYSTRUCT KeyStruct;
    WCHAR ChildRoot[MEMDB_MAX];
    PWSTR End;
    DWORD HashOffset;

    //
    // Add hash entry if this root is an endpoint
    //

    KeyStruct = GetKeyStruct (Offset);

    if (AddRoot && KeyStruct->Flags & KSF_ENDPOINT) {

        HashOffset = FindStringInHashTable (Root, NULL);

        if (HashOffset != Offset) {

#ifdef DEBUG
            if (HashOffset != INVALID_OFFSET) {
                DEBUGMSG ((DBG_WARNING, "Memdb duplicate: %s", Root));
            }
#endif

            AddHashTableEntry (Root, Offset);
        }
    }

    //
    // Recurse for all children, adding hash entries for all endpoints found
    //

    StringCopyW (ChildRoot, Root);
    End = GetEndOfStringW (ChildRoot);
    *End = L'\\';
    End++;
    *End = 0;

    ChildOffset = GetFirstOffset (KeyStruct->NextLevelRoot);

    while (ChildOffset != INVALID_OFFSET) {
        KeyStruct = GetKeyStruct (ChildOffset);
        StringCopyW (End, GetKeyToken (KeyStruct->KeyToken));
        pAddHashEntriesForNode (ChildRoot, ChildOffset, TRUE);

        ChildOffset = GetNextOffset (ChildOffset);
    }
}


BOOL
pFindPlaceForNewNode (
    IN      PKEYSTRUCT InsertNode,
    IN      PDWORD TreeRootPtr,
    OUT     PDWORD ParentOffsetPtr,
    OUT     PDWORD *ParentToChildOffsetPtr,
    OUT     PDWORD PivotEnd
    )

/*++

Routine Description:

  pFindPlaceForNewNode searches a level for the position within the tree.
  This is used to insert new unique keys in the tree.

Arguments:

  InsertNode             - Specifies the allocated but unlinked node.  Its
                           Key member must be valid.
  TreeRootPtr            - Specifies a pointer to the memory that holds the
                           root offset.  This is used to walk the tree.  It
                           can be INVALID_OFFSET.
  ParentOffsetPtr        - Receives the offset to the parent node
  ParentToChildOffsetPtr - Recieves the address of the left or right child
                           pointer within the parent struct
  PivotEnd               - Receives the offset of the tree node that should
                           stop balancing

Return Value:

  TRUE if a spot was found in the tree for InsertNode, or FALSE if a spot was
  not found (because the key name is already in the tree).

--*/

{
    PDWORD ParentPtr;
    PKEYSTRUCT Parent;
    INT cmp;

    ParentPtr = TreeRootPtr;
    *ParentOffsetPtr = INVALID_OFFSET;
    *PivotEnd = INVALID_OFFSET;

    while (*ParentPtr != INVALID_OFFSET) {

        *ParentOffsetPtr = *ParentPtr;
        Parent = GetKeyStruct (*ParentPtr);

        if (Parent->Flags & KSF_BALANCE_MASK) {
            *PivotEnd = *ParentPtr;
        }

        cmp = StringICompareW (GetKeyToken (InsertNode->KeyToken), GetKeyToken (Parent->KeyToken));

        if (cmp < 0) {
            ParentPtr = &Parent->Left;
        } else if (cmp > 0) {
            ParentPtr = &Parent->Right;
        } else {
            return FALSE;
        }
    }

    *ParentToChildOffsetPtr = ParentPtr;

    return TRUE;
}


VOID
pMergeFamilies (
    IN      PDWORD DestTreeRootPtr,
    IN      DWORD MergeSrcOffset,
    IN      DWORD MergeDestPrevLevelOffset
    )

/*++

Routine Description:

  pMergeFamilies takes two tree families and merges them together.  When
  duplicates are found, their linkage is abandoned, but they are not
  deallocated.  This allows MemDbBuildKeyFromOffset to continue to work.

Arguments:

  DestTreeRootPtr          - Specifies the address of the destination level's
                             root variable.  This is potentially altered with
                             insertion and balancing.
  MergeSrcOffset           - Specifies the offset to the source tree family
                             (STF).  The STF is merged into the destination
                             tree indicated by DestTreeRootPtr.
  MergeDestPrevLevelOffset - Specifies the offset to the previous level node.
                             This value cannot be INVALID_OFFSET.

Return Value:

  None.

--*/

{
    PKEYSTRUCT MergeSrc;
    PKEYSTRUCT MergeDest;
    PDWORD ParentToChildOffsetPtr;
    DWORD ParentOffset;
    DWORD DestCollisionOffset;
    DWORD PivotEnd;
    GROWBUFFER NextLevelMerge = GROWBUF_INIT;
    DWORD NodeOffset;
    PDWORD NextLevelOffsetPtr;
    UINT Pos;
    BOOL FoundPlaceForNode;

    //
    // Look for a place within the tree indicated by the offset
    // stored in DestTreeRootPtr.  If one is found, we can simply
    // relink the node at MergeSrcOffset.  Otherwise, we have to
    // recursively merge the next level of MergeSrcOffset, and
    // we have to abandon MergeSrcOffset.
    //

    MergeSrc = GetKeyStruct (MergeSrcOffset);
    MYASSERT (MergeSrc);

    FoundPlaceForNode = pFindPlaceForNewNode (
                            MergeSrc,
                            DestTreeRootPtr,
                            &ParentOffset,
                            &ParentToChildOffsetPtr,
                            &PivotEnd
                            );

    if (FoundPlaceForNode) {
        //
        // Since we found a place to put the src family, it is
        // easy to hook it and its next level into the dest
        // family.
        //

        MergeSrc->Parent = ParentOffset;
        *ParentToChildOffsetPtr = MergeSrcOffset;

        MergeSrc->Flags = MergeSrc->Flags & (~KSF_BALANCE_MASK);
        MergeSrc->Left = INVALID_OFFSET;
        MergeSrc->Right = INVALID_OFFSET;
        MergeSrc->PrevLevelNode = MergeDestPrevLevelOffset;

        pBalanceInsertion (DestTreeRootPtr, MergeSrcOffset, PivotEnd);

#ifdef DEBUG
        pCheckTreeBalance (*DestTreeRootPtr, FALSE);
#endif

    } else {
        //
        // We found a collision, then we have to abandon MergeSrc,
        // removing linkage to the parent and children -- but preserving
        // the linkage to the previous level.  Finally, we have to call
        // this function recursively to hook up all the next level nodes.
        //

        DestCollisionOffset = ParentOffset;      // renamed to be more accurate

        MergeDest = GetKeyStruct (DestCollisionOffset);
        MYASSERT (MergeDest);

        MergeSrc->Parent = INVALID_OFFSET;
        MergeSrc->Left = INVALID_OFFSET;
        MergeSrc->Right = INVALID_OFFSET;
        MergeSrc->PrevLevelNode = MergeDestPrevLevelOffset;

        //
        // If this is an end point, then try to preserve value and flags
        //

        if (MergeSrc->Flags & KSF_ENDPOINT) {

            if (MergeDest->Flags & KSF_ENDPOINT) {
                DEBUGMSG ((
                    DBG_WARNING,
                    "MemDb: Loss of value and flags in %s",
                    GetKeyToken (MergeSrc->KeyToken)
                    ));

            } else {
                MergeDest->Flags = MergeDest->Flags & ~KSF_FLAGS_TO_COPY;
                MergeDest->Flags |= MergeSrc->Flags & KSF_FLAGS_TO_COPY;
                MergeDest->dwValue = MergeSrc->dwValue;
            }
        }

        //
        // Save away all entries in the next src level into a grow buffer,
        // then call pMergeFamilies recursively.
        //

        NodeOffset = GetFirstOffset (MergeSrc->NextLevelRoot);

        while (NodeOffset != INVALID_OFFSET) {

            NextLevelOffsetPtr = (PDWORD) GrowBuffer (&NextLevelMerge, sizeof (DWORD));
            MYASSERT (NextLevelOffsetPtr);

            *NextLevelOffsetPtr = NodeOffset;
            NodeOffset = GetNextOffset (NodeOffset);
        }

        NextLevelOffsetPtr = (PDWORD) NextLevelMerge.Buf;

        for (Pos = 0 ; Pos < NextLevelMerge.End ; Pos += sizeof (DWORD)) {

            pMergeFamilies (
                &MergeDest->NextLevelRoot,
                *NextLevelOffsetPtr,
                DestCollisionOffset
                );

            NextLevelOffsetPtr++;

        }

        FreeGrowBuffer (&NextLevelMerge);
    }
}


DWORD
pMoveKey (
    IN      DWORD OriginalKey,
    IN      PCWSTR NewKeyRoot,
    IN      PCWSTR NewKeyRootWithHive
    )

/*++

Routine Description:

  pMoveKey moves a key (and all of its children) to a new root.  If the
  caller specifies a source key that has no children, a proxy node is created
  to maintain offsets.  The proxy node is not listed in the hash table.

Arguments:

  OriginalKey        - Specifies the offset to the original key that needs to
                       be moved.  It does not need to be an endpoint, and may
                       have children.
  NewKeyRoot         - Specifies the new root for OriginalKey.  It may have
                       multiple levels (separated by backslashes).
  NewKeyRootWithHive - Different from NewKeyRoot only when the node is in a
                       temporary hive.  This is used for the hash table only.

Return Value:

  TRUE if successful, FALSE otherwise.

--*/

{
    DWORD ReplacementKey;
    PKEYSTRUCT SrcKey, DestKey, ChildKey;
    PKEYSTRUCT KeyParent;
    DWORD NodeOffset;
    GROWBUFFER Children = GROWBUF_INIT;
    PDWORD ChildOffsetPtr;
    DWORD Pos;
    WCHAR OriginalRoot[MEMDB_MAX];
    BOOL Endpoint;

    //
    // Check requirements
    //

    SrcKey = GetKeyStruct (OriginalKey);
    if (!SrcKey) {
        DEBUGMSG ((DBG_WHOOPS, "MemDb: pMoveKey can't find original key %s", OriginalKey));
        return INVALID_OFFSET;
    }

    if (SrcKey->Flags & KSF_PROXY_NODE) {
        DEBUGMSG ((DBG_WHOOPS, "MemDb: pMoveKey can't move proxy node %s", OriginalKey));
        return INVALID_OFFSET;
    }

    Endpoint = SrcKey->Flags & KSF_ENDPOINT;

    if (!PrivateBuildKeyFromOffset (0, OriginalKey, OriginalRoot, NULL, NULL, NULL)) {
        return INVALID_OFFSET;
    }

    //
    // Allocate new key
    //

    ReplacementKey = pNewKey (NewKeyRoot, NewKeyRootWithHive, FALSE);

    if (ReplacementKey == INVALID_OFFSET) {
        return INVALID_OFFSET;
    }

    SrcKey = GetKeyStruct (OriginalKey);
    DestKey = GetKeyStruct (ReplacementKey);

    if (!SrcKey || !DestKey) {
        return INVALID_OFFSET;
    }

    DEBUGMSG ((DBG_NAUSEA, "Moving %s to %s", OriginalRoot, NewKeyRootWithHive));

    //
    // Remove all hash entries for all children
    //

    pRemoveHashEntriesForNode (OriginalRoot, OriginalKey);

    //
    // Record all children in an array
    //

    NodeOffset = GetFirstOffset (SrcKey->NextLevelRoot);

    while (NodeOffset != INVALID_OFFSET) {
        ChildOffsetPtr = (PDWORD) GrowBuffer (&Children, sizeof (DWORD));
        if (!ChildOffsetPtr) {
            return INVALID_OFFSET;
        }

        *ChildOffsetPtr = NodeOffset;

        NodeOffset = GetNextOffset (NodeOffset);
    }

    //
    // Move next level pointer to new node.  There are two cases
    // to handle:
    //
    //  1. Destination exists and has children.  Here the source
    //     needs to be merged into the destination.
    //
    //  2. Destination is brand new and has no children.  Here we
    //     simply move the source children to the destination.
    //
    // During this process, the hash table is updated accordingly.
    //

    if (DestKey->NextLevelRoot != INVALID_OFFSET) {
        //
        // Hard case, merge children to new parent's family
        //

        ChildOffsetPtr = (PDWORD) Children.Buf;

        for (Pos = 0 ; Pos < Children.End ; Pos += sizeof (DWORD)) {

            pMergeFamilies (
                &DestKey->NextLevelRoot,
                *ChildOffsetPtr,
                ReplacementKey
                );

            ChildOffsetPtr++;

        }

    } else {
        //
        // Easy case, link children to new parent
        //

        DestKey->NextLevelRoot = SrcKey->NextLevelRoot;
        SrcKey->NextLevelRoot = INVALID_OFFSET;

        if (DestKey->Flags & KSF_ENDPOINT) {
            DEBUGMSG ((
                DBG_WARNING,
                "MemDb: Loss of value and flags in %s",
                GetKeyToken (SrcKey->KeyToken)
                ));

        } else {
            DestKey->Flags = DestKey->Flags & ~KSF_FLAGS_TO_COPY;
            DestKey->Flags |= SrcKey->Flags & KSF_FLAGS_TO_COPY;
            DestKey->dwValue = SrcKey->dwValue;
        }

        ChildOffsetPtr = (PDWORD) Children.Buf;

        for (Pos = 0 ; Pos < Children.End ; Pos += sizeof (DWORD)) {
            NodeOffset = *ChildOffsetPtr;
            ChildOffsetPtr++;

            ChildKey = GetKeyStruct (NodeOffset);
            ChildKey->PrevLevelNode = ReplacementKey;
        }
    }

    //
    // Add all new entries to hash table
    //

    pAddHashEntriesForNode (NewKeyRootWithHive, ReplacementKey, FALSE);

    //
    // Free the original key node, or if an endpoint, make the
    // node a proxy to the new node (to maintain offsets).
    //

    if (!Endpoint) {

        SrcKey->NextLevelRoot = INVALID_OFFSET;
        KeyParent = GetKeyStruct (SrcKey->PrevLevelNode);
        pDeallocKeyStruct (OriginalKey, &KeyParent->NextLevelRoot, TRUE, FALSE);

    } else {

        DestKey->Flags   = (DestKey->Flags & KSF_BALANCE_MASK) | (SrcKey->Flags & (~KSF_BALANCE_MASK));
        DestKey->dwValue = SrcKey->dwValue;

        SrcKey->Flags = KSF_PROXY_NODE | (SrcKey->Flags & KSF_BALANCE_MASK);
        SrcKey->dwValue = ReplacementKey;
        SrcKey->NextLevelRoot = INVALID_OFFSET;
    }

    FreeGrowBuffer (&Children);

    return ReplacementKey;
}


BOOL
MemDbMoveTreeA (
    IN      PCSTR RootNode,
    IN      PCSTR NewRoot
    )

/*++

Routine Description:

  MemDbMoveTree is the external interface to pMoveKey.  See description in
  pMoveKey for details.

Arguments:

  RootNode - Specifies the node to move.

  NewRoot - Specifies the new root for RootNode.

Return Value:

  TRUE if successful, FALSE otherwise.

--*/

{
    PCWSTR UnicodeRootNode;
    PCWSTR UnicodeNewRoot;
    BOOL b = FALSE;

    UnicodeRootNode = ConvertAtoW (RootNode);
    UnicodeNewRoot = ConvertAtoW (NewRoot);

    if (UnicodeRootNode && UnicodeNewRoot) {
        b = MemDbMoveTreeW (UnicodeRootNode, UnicodeNewRoot);
    }

    FreeConvertedStr (UnicodeRootNode);
    FreeConvertedStr (UnicodeNewRoot);

    return b;
}


BOOL
MemDbMoveTreeW (
    IN      PCWSTR RootNode,
    IN      PCWSTR NewRoot
    )
{
    DWORD Offset;
    WCHAR Temp[MEMDB_MAX];
    WCHAR NewRootWithHive[MEMDB_MAX];
    PWSTR p, q;
    PCWSTR SubKey;
    BOOL b = FALSE;
    INT HiveLen;

    if (StringIMatch (RootNode, NewRoot)) {
        DEBUGMSG ((DBG_WHOOPS, "Cannot move tree because source and dest are the same"));
        return FALSE;
    }

    EnterCriticalSection (&g_MemDbCs);

    __try {
        SubKey = SelectHive (RootNode);

        //
        // Copy key to temp buffer
        //

        StringCopyW (Temp, SubKey);

        if (*Temp == 0) {
            DEBUGMSG ((DBG_WHOOPS, "MemDbMoveTree requires a root"));
            __leave;
        }

        //
        // Compute the new root with the original hive
        //

        if (StringIMatchW (Temp, RootNode)) {
            // no hive case
            StringCopyW (NewRootWithHive, NewRoot);
        } else {
            HiveLen = wcslen (RootNode) - wcslen (SubKey);
            StringCopyTcharCountW (NewRootWithHive, RootNode, HiveLen);
            StringCopyW (AppendWackW (NewRootWithHive), NewRoot);
        }

        //
        // Find the last offset of the root key
        //

        q = Temp;
        Offset = INVALID_OFFSET;

        do {

            if (Offset == INVALID_OFFSET) {
                Offset = g_db->FirstLevelRoot;
            } else {
                Offset = GetKeyStruct (Offset)->NextLevelRoot;
            }

            if (Offset == INVALID_OFFSET) {
                DEBUGMSGW ((DBG_VERBOSE, "MemDbMoveTree root %s not found", RootNode));
                __leave;
            }

            p = wcschr (q, L'\\');
            if (p) {
                *p = 0;
            }

            Offset = FindKeyStruct (Offset, q);

            if (Offset == INVALID_OFFSET) {
                DEBUGMSGW ((DBG_VERBOSE, "MemDbMoveTree root %s not found", RootNode));
                __leave;
            }

            q = p + 1;

        } while (p);

        //
        // Now move the key
        //

        Offset = pMoveKey (Offset, NewRoot, NewRootWithHive);

        if (Offset != INVALID_OFFSET) {
            b = TRUE;
        } else {
            DEBUGMSGW ((DBG_WHOOPS, "Can't move %s to %s", RootNode, NewRoot));
        }
    }
    __finally {
        LeaveCriticalSection (&g_MemDbCs);
    }

    return b;
}


PKEYSTRUCT
pGetKeyStructWithProxy (
    IN DWORD Offset
    )

/*++

Routine Description:

  pGetKeyStructWithProxy returns a pointer given an offset.  It also implements proxy
  nodes, transparent to the rest of memdb.  The debug version checks the
  signature and validity of each offset.  It is assumed that Offset is always
  valid.

Arguments:

  Offset - Specifies the offset to the node

Return Value:

  The pointer to the node.

--*/

{
    PKEYSTRUCT KeyStruct;

#ifdef DEBUG

    if (Offset == INVALID_OFFSET) {
        DEBUGMSG ((DBG_ERROR, "Invalid root accessed in pGetKeyStructWithProxy at offset %u", Offset));
        return NULL;
    }

    if (!g_db->Buf) {
        DEBUGMSG ((DBG_ERROR, "Attempt to access non-existent buffer at %u", Offset));
        return NULL;
    }

    if (Offset > g_db->End) {
        DEBUGMSG ((DBG_ERROR, "Access beyond length of buffer in pGetKeyStructWithProxy (offset %u)", Offset));
        return NULL;
    }
#endif

    KeyStruct = (PKEYSTRUCT) (g_db->Buf + Offset);


#ifdef DEBUG

    if (!g_UseDebugStructs) {

        KeyStruct = (PKEYSTRUCT) (g_db->Buf + Offset - sizeof (DWORD));

    } else if (KeyStruct->Signature != SIGNATURE) {
        DEBUGMSG ((DBG_ERROR, "Signature does not match in pGetKeyStructWithProxy at offset %u!", Offset));
        return NULL;
    }

#endif

    if (KeyStruct->Flags & KSF_PROXY_NODE) {
        return pGetKeyStructWithProxy (KeyStruct->dwValue);
    }

    return KeyStruct;
}


PKEYSTRUCT
GetKeyStruct (
    IN DWORD Offset
    )

/*++

Routine Description:

  GetKeyStruct returns a pointer given an offset.  It does not support proxy
  nodes, so the rest of memdb accesses the unaltered tree.  The debug version
  checks the signature and validity of each offset.  It is assumed that Offset
  is always valid.

Arguments:

  Offset - Specifies the offset to the node

Return Value:

  The pointer to the node.

--*/

{
    PKEYSTRUCT KeyStruct;

#ifdef DEBUG

    if (Offset == INVALID_OFFSET) {
        DEBUGMSG ((DBG_ERROR, "Invalid root accessed in GetKeyStruct at offset %u", Offset));
        return NULL;
    }

    if (!g_db->Buf) {
        DEBUGMSG ((DBG_ERROR, "Attempt to access non-existent buffer at %u", Offset));
        return NULL;
    }

    if (Offset > g_db->End) {
        DEBUGMSG ((DBG_ERROR, "Access beyond length of buffer in GetKeyStruct (offset %u)", Offset));
        return NULL;
    }
#endif

    KeyStruct = (PKEYSTRUCT) (g_db->Buf + Offset);


#ifdef DEBUG

    if (!g_UseDebugStructs) {

        KeyStruct = (PKEYSTRUCT) (g_db->Buf + Offset - sizeof (DWORD));

    } else if (KeyStruct->Signature != SIGNATURE) {
        DEBUGMSG ((DBG_ERROR, "Signature does not match in GetKeyStruct at offset %u!", Offset));
        return NULL;
    }

#endif

    return KeyStruct;
}


DWORD
FindKeyStruct (
    IN DWORD RootOffset,
    IN PCWSTR KeyName
    )

/*++

Routine Description:

  FindKeyStruct takes a key name and looks for the
  offset in the tree specified by RootOffset.  The key
  name must not contain backslashes.

Arguments:

  RootOffset - An offset to the root of the level

  KeyName - The name of the key to find in the binary tree

Return Value:

  An offset to the structure, or INVALID_OFFSET if the key
  was not found.

--*/

{
    PKEYSTRUCT KeyStruct;
    int cmp;

    //
    // Walk the binary tree looking for KeyName
    //

    while (RootOffset != INVALID_OFFSET) {
        KeyStruct = GetKeyStruct (RootOffset);
        cmp = StringICompareW (KeyName, GetKeyToken (KeyStruct->KeyToken));
        if (!cmp) {
            break;
        }

        if (cmp < 0) {
            RootOffset = KeyStruct->Left;
        } else {
            RootOffset = KeyStruct->Right;
        }
    }

    return RootOffset;
}


DWORD
GetFirstOffset (
    IN  DWORD RootOffset
    )

/*++

Routine Description:

  GetFirstOffset walks down the left side of the binary tree
  pointed to by RootOffset, and returns the left-most node.

Arguments:

  RootOffset    - An offset to the root of the level

Return Value:

  An offset to the leftmost structure, or INVALID_OFFSET if the
  root was invalid.

--*/


{
    PKEYSTRUCT KeyStruct;

    if (RootOffset == INVALID_OFFSET) {
        return INVALID_OFFSET;
    }

    //
    // Go to leftmost node of root
    //

    KeyStruct = GetKeyStruct (RootOffset);
    while (KeyStruct->Left != INVALID_OFFSET) {
        RootOffset = KeyStruct->Left;
        KeyStruct = GetKeyStruct (RootOffset);
    }

    return RootOffset;
}


DWORD
GetNextOffset (
    IN  DWORD NodeOffset
    )

/*++

Routine Description:

  GetNextOffset traverses the binary tree in order.  This
  technique relies on parent links to traverse without a
  stack or recursion.

Arguments:

  NodeOffset  - Offset to a node in the tree, usually the
            return value from GetFirstOffset or GetNextOffset.

Return Value:

  An offset to the next structure, or INVALID_OFFSET if the
  end is reached.

--*/

{
    PKEYSTRUCT KeyStruct;
    DWORD Last;

    KeyStruct = GetKeyStruct (NodeOffset);

    //
    // If right child exist, go to leftmost node of right child
    //

    if (KeyStruct->Right != INVALID_OFFSET) {

        //
        // Go to right child
        //

        NodeOffset = KeyStruct->Right;

        //
        // Go to left-most of right child
        //

        KeyStruct = GetKeyStruct (NodeOffset);
        while (KeyStruct->Left != INVALID_OFFSET) {
            NodeOffset = KeyStruct->Left;
            KeyStruct = GetKeyStruct (NodeOffset);
        }
    }

    //
    // Else move up to parent
    //

    else {
        //
        // Climb to top of processed nodes
        //

        do {
            Last = NodeOffset;
            NodeOffset = KeyStruct->Parent;

            if (NodeOffset != INVALID_OFFSET) {
                KeyStruct = GetKeyStruct (NodeOffset);
            } else {
                break;  // reached the root of tree
            }
        } while (Last == KeyStruct->Right);
    }

    return NodeOffset;
}


DWORD
pFindPatternKeyStruct (
    IN  DWORD RootOffset,
    IN  DWORD NodeOffset,
    IN  PCWSTR KeyName
    )

/*++

Routine Description:

  pFindPatternKeyStruct takes a key name and looks for the
  offset in the tree specified by RootOffset.  The key name must
  not contain backslashes, and the stored key name is
  treated as a pattern.

Arguments:

  RootOffset - An offset to the root of the level
  NodeOffset - The previous return value from pFindPatternKeyStruct
               (for enumeration) or INVALID_OFFSET for the first
               call.
  KeyName - The name of the key to find in the binary tree

Return Value:

  An offset to the structure, or INVALID_OFFSET if the key
  was not found.

--*/

{
    PKEYSTRUCT KeyStruct;

    //
    // if NodeOffset is invalid, this is the first search item
    //

    if (NodeOffset == INVALID_OFFSET) {
        NodeOffset = GetFirstOffset (RootOffset);
    }

    //
    // otherwise advance NodeOffset
    //

    else {
        NodeOffset = GetNextOffset (NodeOffset);
    }


    //
    // Examine key as a pattern, then go to next node
    //

    while (NodeOffset != INVALID_OFFSET) {
        KeyStruct = GetKeyStruct (NodeOffset);

        // Compare key (string in KeyStruct->KeyToken is the pattern)
        if (IsPatternMatchW (GetKeyToken (KeyStruct->KeyToken), KeyName)) {
            return NodeOffset;
        }

        // No match yet - go to next node
        NodeOffset = GetNextOffset (NodeOffset);
    }

    return INVALID_OFFSET;
}


DWORD
pFindKeyStructUsingPattern (
    IN  DWORD RootOffset,
    IN  DWORD NodeOffset,
    IN  PCWSTR PatternStr
    )

/*++

Routine Description:

  pFindKeyStructUsingPattern takes a key pattern and looks
  for the offset in the tree specified by RootOffset.  The key
  name must not contain backslashes, but can contain wildcards.

Arguments:

  RootOffset - An offset to the root of the level

  NodeOffset - The previous return value from pFindPatternKeyStruct
               (for enumeration) or INVALID_OFFSET for the first
               call.

  KeyName - The name of the key to find in the binary tree

Return Value:

  An offset to the structure, or INVALID_OFFSET if the key
  was not found.

--*/

{
    PKEYSTRUCT KeyStruct;

    // if NodeOffset is invalid, this is the first search item
    if (NodeOffset == INVALID_OFFSET) {
        NodeOffset = GetFirstOffset (RootOffset);
    }

    // otherwise advance NodeOffset
    else {
        NodeOffset = GetNextOffset (NodeOffset);
    }

    //
    // Examine key as a pattern, then go to next node
    //

    while (NodeOffset != INVALID_OFFSET) {
        KeyStruct = GetKeyStruct (NodeOffset);

        // Compare key
        if (IsPatternMatchW (PatternStr, GetKeyToken (KeyStruct->KeyToken))) {
            return NodeOffset;
        }

        // No match yet - go to next node
        NodeOffset = GetNextOffset (NodeOffset);
    }

    return INVALID_OFFSET;
}


DWORD
pFindPatternKeyStructUsingPattern (
    IN  DWORD RootOffset,
    IN  DWORD NodeOffset,
    IN  PCWSTR PatternStr
    )

/*++

Routine Description:

  pFindPatternKeyStructUsingPattern takes a key pattern and looks
  for the offset in the tree specified by RootOffset.  The key name
  must not contain backslashes, but can contain wildcards.  The
  wildcards in the stored key are processed as well.

Arguments:

  RootOffset      - An offset to the root of the level
  NodeOffset      - The previous return value from pFindPatternKeyStruct
                (for enumeration) or INVALID_OFFSET for the first
                call.
  KeyName - The name of the key to find in the binary tree

Return Value:

  An offset to the structure, or INVALID_OFFSET if the key
  was not found.

--*/

{
    PKEYSTRUCT KeyStruct;

    // if NodeOffset is invalid, this is the first search item
    if (NodeOffset == INVALID_OFFSET) {
        NodeOffset = GetFirstOffset (RootOffset);
    }

    // otherwise advance NodeOffset
    else {
        NodeOffset = GetNextOffset (NodeOffset);
    }


    //
    // Examine key as a pattern, then go to next node
    //

    while (NodeOffset != INVALID_OFFSET) {
        KeyStruct = GetKeyStruct (NodeOffset);

        // Compare key (PatternStr is the pattern)
        if (IsPatternMatchW (PatternStr, GetKeyToken (KeyStruct->KeyToken))) {
            return NodeOffset;
        }

        // Compare key (string in KeyStruct->KeyToken is the pattern)
        if (IsPatternMatchW (GetKeyToken (KeyStruct->KeyToken), PatternStr)) {
            return NodeOffset;
        }

        // No match yet - go to next node
        NodeOffset = GetNextOffset (NodeOffset);
    }

    return INVALID_OFFSET;
}


DWORD
FindKey (
    IN  PCWSTR FullKeyPath
    )

/*++

Routine Description:

  FindKey locates a complete key string and returns
  the offset to the KEYSTRUCT, or INVALID_OFFSET if
  the key path does not exist.  The FullKeyPath
  must supply the complete path to the KEYSTRUCT.

Arguments:

  FullKeyPath - A backslash-delimited key path to a value

Return Value:

  An offset to the structure, or INVALID_OFFSET if the key
  was not found.

--*/

{
    return FindStringInHashTable (FullKeyPath, NULL);
}


DWORD
FindPatternKey (
    IN  DWORD RootOffset,
    IN  PCWSTR FullKeyPath,
    IN  BOOL EndPatternAllowed
    )

/*++

Routine Description:

  FindPatternKey locates a complete key string and returns
  the offset to the KEYSTRUCT, or INVALID_OFFSET if the
  key path does not exist.  Each stored part of the key is
  treated as a pattern, and FullKeyPath must supply the
  complete path to the KEYSTRUCT without wildcards.

Arguments:

  RootOffset        - An offset to the level's binary tree root
  FullKeyPath       - A backslash-delimited key path to a value
                      without wildcards.
  EndPatternAllowed - Specifies TRUE if the stored pattern can
                      have an asterisk at the end, to indicate
                      any subkeys, or FALSE if the pattern matches
                      on the same level only.

Return Value:

  An offset to the structure, or INVALID_OFFSET if the key
  was not found.

--*/

{
    WCHAR Path[MEMDB_MAX + 1];
    PWSTR p;
    PCWSTR End;

    //
    // Divide the string into a multi-sz
    //

    StringCopyW (Path, FullKeyPath);

    for (p = Path ; *p ; p++) {
        if (*p == L'\\') {
            *p = 0;
        }
    }

    End = p;
    if (End > Path && *(End - 1) == 0) {
        //
        // Special case: the wack was at the end of the string.
        // Therefore, inc End so we test that final empty value.
        //

        End++;
    }

    if (End == Path) {
        DEBUGMSG ((DBG_ERROR, "FindPatternKey: Empty key not allowed"));
        return INVALID_OFFSET;
    }

    //
    // Now test the key against all stored patterns
    //

    return pFindPatternKeyWorker (Path, End, RootOffset, EndPatternAllowed);
}


DWORD
pFindPatternKeyWorker (
    IN      PCWSTR SubKey,
    IN      PCWSTR End,
    IN      DWORD RootOffset,
    IN      BOOL EndPatternAllowed
    )
{
    DWORD Offset;
    PCWSTR NextSubKey;
    DWORD MatchOffset;
    PKEYSTRUCT KeyStruct;

    NextSubKey = GetEndOfString (SubKey) + 1;

    // Begin an enumeration of the matches
    Offset = pFindPatternKeyStruct (RootOffset, INVALID_OFFSET, SubKey);

    while (Offset != INVALID_OFFSET) {
        //
        // Is there more in the caller's key string to test?
        //

        if (NextSubKey < End) {
            //
            // Yes, call pFindPatternKeyWorker recursively
            //

            MatchOffset = pFindPatternKeyWorker (
                                NextSubKey,
                                End,
                                GetKeyStruct (Offset)->NextLevelRoot,
                                EndPatternAllowed
                                );

            if (MatchOffset != INVALID_OFFSET) {
                //
                // We found one match.  There may be others, but
                // we return this one.
                //

                return MatchOffset;
            }

        } else {
            //
            // No, if this is an endpoint, return the match.
            //

            KeyStruct = GetKeyStruct (Offset);

            if (KeyStruct->Flags & KSF_ENDPOINT) {
                return Offset;
            }
        }

        // Continue enumeration
        Offset = pFindPatternKeyStruct (RootOffset, Offset, SubKey);
    }

    //
    // The normal search failed.  Now we test for an endpoint that has
    // just an asterisk.  If we find one, we return it as our match.
    // This only applies when we have more subkeys, and EndPatternAllowed
    // is TRUE.
    //

    if (NextSubKey < End && EndPatternAllowed) {
        // Begin another enumeration of the matches
        Offset = pFindPatternKeyStruct (RootOffset, INVALID_OFFSET, SubKey);

        while (Offset != INVALID_OFFSET) {
            //
            // If EndPatternAllowed is TRUE, then test this offset
            // for an exact match with an asterisk.
            //

            KeyStruct = GetKeyStruct (Offset);

            if (KeyStruct->Flags & KSF_ENDPOINT) {
                if (StringMatchW (GetKeyToken (KeyStruct->KeyToken), L"*")) {
                    return Offset;
                }
            }

            // Continue enumeration
            Offset = pFindPatternKeyStruct (RootOffset, Offset, SubKey);
        }
    }


    //
    // No match was found
    //

    return INVALID_OFFSET;
}



DWORD
FindKeyUsingPattern (
    IN  DWORD RootOffset,
    IN  PCWSTR FullKeyPath
    )

/*++

Routine Description:

  FindKeyUsingPattern locates a key string using a pattern
  and returns the offset to the KEYSTRUCT, or INVALID_OFFSET
  if the key path does not exist.  Each part of the stored key
  is treated as a literal string.

Arguments:

  RootOffset  - An offset to the level's binary tree root

  FullKeyPath - A backslash-delimited key path to a value
                with optional wildcards.

Return Value:

  An offset to the structure, or INVALID_OFFSET if the key
  was not found.

--*/

{
    WCHAR Path[MEMDB_MAX];
    PWSTR p;
    PWSTR Start, End;
    DWORD Offset, NextLevelOffset;

    StringCopyW (Path, FullKeyPath);
    End = Path;

    //
    // Split string at backslash
    //

    Start = End;
    p = wcschr (End, '\\');
    if (p) {
        End = _wcsinc (p);
        *p = 0;
    } else {
        End = NULL;
    }

    //
    // Look at this level for the very first key
    //

    Offset = pFindKeyStructUsingPattern (RootOffset, INVALID_OFFSET, Start);

    //
    // If this is the last level, we may have found the key!
    //

    if (!End) {
        while (Offset != INVALID_OFFSET) {
            if (GetKeyStruct (Offset)->Flags & KSF_ENDPOINT) {
                return Offset;
            }

            Offset = pFindKeyStructUsingPattern (RootOffset, Offset, Start);
        }
    }

    //
    // Otherwise recursively examine next level
    //

    while (Offset != INVALID_OFFSET) {

        //
        // Look at all subkeys for a match
        //

        NextLevelOffset = GetKeyStruct (Offset)->NextLevelRoot;
        NextLevelOffset = FindKeyUsingPattern (NextLevelOffset, End);

        //
        // When the recursive search succeeded, propagate the return value
        //

        if (NextLevelOffset != INVALID_OFFSET) {
            return NextLevelOffset;
        }

        //
        // No match, continue looking in this level for another match
        //

        Offset = pFindKeyStructUsingPattern (RootOffset, Offset, Start);
    }

    return INVALID_OFFSET;
}


DWORD
FindPatternKeyUsingPattern (
    IN  DWORD RootOffset,
    IN  PCWSTR FullKeyPath
    )

/*++

Routine Description:

  pFindPatternKeyUsingPattern locates a patterned key string
  using a pattern and returns the offset to the KEYSTRUCT,
  or INVALID_OFFSET if the key path does not exist.  Each
  part of the key is treated as a pattern.

Arguments:

  RootOffset          - An offset to the level's binary tree root
  FullKeyPath - A backslash-delimited key path to a value
                    with optional wildcards.

Return Value:

  An offset to the structure, or INVALID_OFFSET if the key
  was not found.

--*/

{
    WCHAR Path[MEMDB_MAX];
    PWSTR p;
    PWSTR Start, End;
    DWORD Offset, NextLevelOffset;

    StringCopyW (Path, FullKeyPath);
    End = Path;

    // Split string at backslash
    Start = End;
    p = wcschr (End, L'\\');
    if (p) {
        End = p + 1;
        *p = 0;
    }
    else
        End = NULL;

    // Look at this level for the very first key
    Offset = pFindPatternKeyStructUsingPattern (RootOffset, INVALID_OFFSET, Start);

    // If this is the last level, we may have found the key!
    if (!End) {
        while (Offset != INVALID_OFFSET) {
            if (GetKeyStruct (Offset)->Flags & KSF_ENDPOINT)
                return Offset;

            Offset = pFindPatternKeyStructUsingPattern (RootOffset, Offset, Start);
        }
    }

    // Otherwise recursively examine next level
    while (Offset != INVALID_OFFSET) {

        // Look at all subkeys for a match
        NextLevelOffset = GetKeyStruct (Offset)->NextLevelRoot;
        NextLevelOffset = FindPatternKeyUsingPattern (NextLevelOffset, End);

        // When the recursive search succeeded, propagate the return value
        if (NextLevelOffset != INVALID_OFFSET)
            return NextLevelOffset;

        // No match, continue looking in this level for another match
        Offset = pFindPatternKeyStructUsingPattern (RootOffset, Offset, Start);
    }

    return INVALID_OFFSET;
}


DWORD
pNewKey (
    IN  PCWSTR KeyStr,
    IN  PCWSTR KeyStrWithHive,
    IN  BOOL Endpoint
    )

/*++

Routine Description:

  NewKey allocates a key struct off our heap, and links it into the binary
  tree.  KeyStr must be a full key path, and any part of the path that does
  not exist will be created.  KeyStr must not already exist (though parts
  of it can exist).

Arguments:

  KeyStr - The full path to the value, separated by backslashes.
           Each string between backslashes will cause a key
           struct to be allocated and linked.  Some of the
           structs may already have been allocated.

  KeyStrWithHive - The full path to the value, plus the hive
                   prefix (if any).  Can be the same as KeyStr
                   if there is no hive prefix.

  Endpoint - Specifies TRUE if new node is an endpoint, or FALSE if
             it is not.

Return Value:

  An offset to the last node of the new structure, or
  INVALID_OFFSET if the key could not be allocated.

--*/

{
    WCHAR Path[MEMDB_MAX];
    PWSTR p;
    PWSTR Start, End;
    DWORD Offset, ThisLevelRoot;
    PDWORD ParentOffsetPtr;
    PKEYSTRUCT KeyStruct;
    DWORD LastLevel;
    BOOL NewNodeCreated = FALSE;

    StringCopyW (Path, KeyStr);
    End = Path;
    ThisLevelRoot = g_db->FirstLevelRoot;
    ParentOffsetPtr = &g_db->FirstLevelRoot;
    LastLevel = INVALID_OFFSET;

    do  {
        // Split string at backslash
        Start = End;
        p = wcschr (End, L'\\');
        if (p) {
            End = p + 1;
            *p = 0;
        }
        else
            End = NULL;

        // Look in tree for key
        if (!NewNodeCreated) {
            Offset = FindKeyStruct (ThisLevelRoot, Start);
        } else {
            Offset = INVALID_OFFSET;
        }

        if (Offset == INVALID_OFFSET) {
            // Add a new key if it was not found
            Offset = pAllocKeyStruct (ParentOffsetPtr, Start, LastLevel);
            if (Offset == INVALID_OFFSET) {
                return Offset;
            }

            NewNodeCreated = TRUE;
        }

        // Continue to next level
        KeyStruct = GetKeyStruct (Offset);
        LastLevel = Offset;
        ThisLevelRoot = KeyStruct->NextLevelRoot;
        ParentOffsetPtr = &KeyStruct->NextLevelRoot;
    } while (End);

    if (Endpoint) {
        if (!(KeyStruct->Flags & KSF_ENDPOINT)) {
            NewNodeCreated = TRUE;
        }

        KeyStruct->Flags |= KSF_ENDPOINT;

        if (NewNodeCreated) {
            AddHashTableEntry (KeyStr, Offset);
        }
    }

    return Offset;
}


DWORD
NewKey (
    IN  PCWSTR KeyStr,
    IN  PCWSTR KeyStrWithHive
    )
{
    return pNewKey (KeyStr, KeyStrWithHive, TRUE);
}


VOID
DeleteKey (
    IN      PCWSTR KeyStr,
    IN OUT  PDWORD RootPtr,
    IN      BOOL MustMatch
    )

/*++

Routine Description:

  DeleteKey takes a key path and puts the key struct in the deleted
  block chain.  Any sub-levels are deleted as well.  Optionally,
  the binary tree in which the key participates in may be updated.

Arguments:

  KeyStr     - The full path to the value, separated by backslashes.
  RootPtr    - A pointer to the level's binary tree root variable.
               If necessary, the variable is updated.
  MustMatch  - A flag indicating if the delete only applies to
               end points or if any matching struct is to be deleted.
               TRUE indicates only endpoints can be deleted.

Return Value:

  none

--*/

{
    WCHAR Path[MEMDB_MAX];
    PWSTR p;
    PWSTR Start, End;
    DWORD Offset;
    DWORD NextOffset;
    PKEYSTRUCT KeyStruct;

    INCSTAT(g_Deletions);

    StringCopyW (Path, KeyStr);
    End = Path;

    //
    // Split string at backslash
    //

    Start = End;
    p = wcschr (End, L'\\');
    if (p) {
        End = _wcsinc (p);
        *p = 0;

    } else {
        End = NULL;
    }

    //
    // Look at this level for the very first key
    //

    Offset = pFindKeyStructUsingPattern (*RootPtr, INVALID_OFFSET, Start);

    //
    // If this is the last level, delete the matching keys
    // (may need to be endpoints if MustMatch is TRUE)
    //

    if (!End) {
        while (Offset != INVALID_OFFSET) {
            KeyStruct = GetKeyStruct (Offset);
            NextOffset = pFindKeyStructUsingPattern (*RootPtr, Offset, Start);

            //
            // If must match and lower levels exist, don't delete, just turn
            // off the endpoint flag
            //

            if (MustMatch && KeyStruct->NextLevelRoot != INVALID_OFFSET) {
                // Call to clean up, not to delink or recurse
                pDeallocKeyStruct (Offset, RootPtr, FALSE, TRUE);
            }

            //
            // Else delete the struct if an endpoint or don't care about
            // endpoints
            //

            else if (!MustMatch || (KeyStruct->Flags & KSF_ENDPOINT)) {
                // Call to free the entire key struct and all children
                pDeallocKeyStruct (Offset, RootPtr, TRUE, FALSE);
            }

            Offset = NextOffset;
        }
    }

    //
    // Otherwise recursively examine next level for each match
    //

    else {
        while (Offset != INVALID_OFFSET) {
            //
            // Delete all matching subkeys
            //

            NextOffset = pFindKeyStructUsingPattern (*RootPtr, Offset, Start);
            DeleteKey (End, &GetKeyStruct (Offset)->NextLevelRoot, MustMatch);

            //
            // If this is not an endpoint and has no children, delete it
            //

            KeyStruct = GetKeyStruct (Offset);
            if (KeyStruct->NextLevelRoot == INVALID_OFFSET &&
                !(KeyStruct->Flags & KSF_ENDPOINT)
                ) {
                // Call to free the entire key struct
                pDeallocKeyStruct (Offset, RootPtr, TRUE, FALSE);
            }

            //
            // Continue looking in this level for another match
            //

            Offset = NextOffset;
        }
    }
}


VOID
CopyValToPtr (
    PKEYSTRUCT KeyStruct,
    PDWORD ValPtr
    )
{
    if (ValPtr) {
        if (!(KeyStruct->Flags & KSF_BINARY)) {
            *ValPtr = KeyStruct->dwValue;
        } else {
            *ValPtr = 0;
        }
    }
}


VOID
CopyFlagsToPtr (
    PKEYSTRUCT KeyStruct,
    PDWORD ValPtr
    )
{
    if (ValPtr) {
        *ValPtr = KeyStruct->Flags & KSF_USERFLAG_MASK;
    }
}


BOOL
PrivateBuildKeyFromOffset (
    IN      DWORD StartLevel,               // zero-based
    IN      DWORD TailOffset,
    OUT     PWSTR Buffer,                   OPTIONAL
    OUT     PDWORD ValPtr,                  OPTIONAL
    OUT     PDWORD UserFlagsPtr,            OPTIONAL
    OUT     PDWORD Chars                    OPTIONAL
    )

/*++

Routine Description:

  PrivateBuildKeyFromOffset generates the key string given an offset.  The
  caller can specify the start level to skip root nodes.  It is assumed that
  TailOffset is always valid.

Arguments:

  StartLevel   - Specifies the zero-based level to begin building the key
                 string.  This is used to skip the root portion of the key
                 string.
  TailOffset   - Specifies the offset to the last level of the key string.
  Buffer       - Receives the key string, must be able to hold MEMDB_MAX
                 characters.
  ValPtr       - Receives the key's value
  UserFlagsPtr - Receives the user flags
  Chars        - Receives the number of characters in Buffer

Return Value:

  TRUE if the key was build properly, FALSE otherwise.

--*/

{
    static DWORD Offsets[MEMDB_MAX];
    PKEYSTRUCT KeyStruct;
    DWORD CurrentOffset;
    DWORD OffsetEnd;
    DWORD OffsetStart;
    register PWSTR p;
    register PCWSTR s;

    //
    // Build string
    //

    OffsetEnd = MEMDB_MAX;
    OffsetStart = OffsetEnd;

    CurrentOffset = TailOffset;
    while (CurrentOffset != INVALID_OFFSET) {
        //
        // Record offset
        //
        OffsetStart--;
        Offsets[OffsetStart] = CurrentOffset;

        //
        // Dec for start level and go to parent
        //
        CurrentOffset = pGetKeyStructWithProxy (CurrentOffset)->PrevLevelNode;
    }

    //
    // Filter for "string is not long enough"
    //
    OffsetStart += StartLevel;
    if (OffsetStart >= OffsetEnd) {
        return FALSE;
    }

    //
    // Transfer node's value and flags to caller's variables
    //
    CopyValToPtr (pGetKeyStructWithProxy (TailOffset), ValPtr);
    CopyFlagsToPtr (pGetKeyStructWithProxy (TailOffset), UserFlagsPtr);

    //
    // Copy each piece of the string to Buffer and calculate character count
    //
    if (Buffer) {
        p = Buffer;
        for (CurrentOffset = OffsetStart ; CurrentOffset < OffsetEnd ; CurrentOffset++) {
            KeyStruct = pGetKeyStructWithProxy (Offsets[CurrentOffset]);
            s = GetKeyToken (KeyStruct->KeyToken);
            while (*s) {
                *p++ = *s++;
            }
            *p++ = L'\\';
        }
        p--;
        *p = 0;

        if (Chars) {
            *Chars = (p - Buffer) / sizeof (WCHAR);
        }

    } else if (Chars) {
        *Chars = 0;

        for (CurrentOffset = OffsetStart ; CurrentOffset < OffsetEnd ; CurrentOffset++) {
            KeyStruct = pGetKeyStructWithProxy (Offsets[CurrentOffset]);
            *Chars += wcslen(GetKeyToken (KeyStruct->KeyToken)) + 1;
        }

        *Chars -= 1;
    }

    return TRUE;
}


UINT
pComputeTokenHash (
    IN      PCWSTR KeyName
    )
{
    UINT hash;

    hash = 0;
    while (*KeyName) {
        hash = (hash << 1) ^ (*KeyName++);
    }

    return hash % TOKENBUCKETS;
}


DWORD
pFindKeyToken (
    IN      PCWSTR KeyName,
    OUT     PUINT Hash
    )
{
    DWORD offset;
    PTOKENSTRUCT tokenStruct;
    INT cmp;

    *Hash = pComputeTokenHash (KeyName);

    offset = g_db->TokenBuckets[*Hash];

    while (offset != INVALID_OFFSET) {
        tokenStruct = (PTOKENSTRUCT) (g_db->Buf + offset);
        if (StringMatchW (tokenStruct->String, KeyName)) {
            break;
        }

        offset = tokenStruct->Right;
    }

    return offset;
}


DWORD
pAllocKeyToken (
    IN      PCWSTR KeyName,
    OUT     PINT AdjustFactor
    )
{
    PTOKENSTRUCT tokenStruct;
    PTOKENSTRUCT tokenParent;
    DWORD tokenOffset;
    UINT size;
    PDWORD parentToChildLink;
    DWORD newNodeParentOffset;
    DWORD pivotPoint;
    INT cmp;
    UINT hash;

    //
    // Use existing token first
    //

    tokenOffset = pFindKeyToken (KeyName, &hash);
    if (tokenOffset != INVALID_OFFSET) {
        *AdjustFactor = 0;
        return tokenOffset;
    }

    //
    // Existing token does not exist -- allocate a new one
    //

    size = sizeof (TOKENSTRUCT) + SizeOfStringW (KeyName);

    tokenStruct = (PTOKENSTRUCT) pAllocMemoryFromDb (
                                        size,
                                        &tokenOffset,
                                        AdjustFactor
                                        );

    tokenStruct->Right = g_db->TokenBuckets[hash];
    StringCopyW (tokenStruct->String, KeyName);
    g_db->TokenBuckets[hash] = tokenOffset;

    return tokenOffset;
}


VOID
pDeallocToken (
    IN      DWORD Token
    )
{
    return;
}


PCWSTR
GetKeyToken (
    IN      DWORD Token
    )
{
    PTOKENSTRUCT tokenStruct;

    tokenStruct = (PTOKENSTRUCT) (g_db->Buf + Token);
    return tokenStruct->String;
}