VOID FORCEINLINE RtlpInsertAvlTreeNode	(	IN PRTL_AVL_TABLE	Table,
		IN PRTL_BALANCED_LINKS	NewNode,
		IN OUT PVOID	NodeOrParent,
		IN OUT TABLE_SEARCH_RESULT	SearchResult
	)

Definition at line 208 of file avlsupp.c.

Referenced by MiInsertNode(), and RtlInsertElementGenericTableFullAvl().

{
    CHAR Balance;

    /* Initialize the new inserted element */
    MI_ASSERT(SearchResult != TableFoundNode);
    NewNode->LeftChild = NewNode->RightChild = NULL;
    RtlSetBalance(NewNode, RtlBalancedAvlTree);

    /* Increase element count */
    Table->NumberGenericTableElements++;

    /* Check where we should insert the entry */
    if (SearchResult == TableEmptyTree)
    {
        /* This is the new root node */
        RtlInsertAsRightChildAvl(&Table->BalancedRoot, NewNode);

        /* On AVL trees, we also update the depth */
        ASSERT(Table->DepthOfTree == 0);
        Table->DepthOfTree = 1;
        return;
    }
    else if (SearchResult == TableInsertAsLeft)
    {
        /* Insert it left */
        RtlInsertAsLeftChildAvl(NodeOrParent, NewNode);
    }
    else
    {
        /* Right node */
        RtlInsertAsRightChildAvl(NodeOrParent, NewNode);
    }

    /* Little cheat to save on loop processing, taken from Timo */
    RtlSetBalance(&Table->BalancedRoot, RtlLeftHeavyAvlTree);

    /*
     * This implements A6-A7 from Knuth based on http://coding.derkeiler.com
     * /pdf/Archive/C_CPP/comp.lang.c/2004-01/1812.pdf, however the algorithm
     * is slightly modified to follow the tree based on the Parent Node such
     * as the Windows algorithm does it, instead of following the nodes down.
     */
    while (TRUE)
    {
        /* Calculate which side to balance on */
        Balance = RtlIsLeftChildAvl(NewNode) ? RtlLeftHeavyAvlTree : RtlRightHeavyAvlTree;

        /* Check if the parent node was balanced */
        if (RtlBalance(NodeOrParent) == RtlBalancedAvlTree)
        {
            /* It's not balanced anymore (heavy on one side) */
            RtlSetBalance(NodeOrParent, Balance);

            /* Move up */
            NewNode = NodeOrParent;
            NodeOrParent = RtlParentAvl(NodeOrParent);
        }
        else if (RtlBalance(NodeOrParent) != Balance)
        {
            /* The parent's balance is opposite, so the tree is balanced now */
            RtlSetBalance(NodeOrParent, RtlBalancedAvlTree);

            /* Check if this is the root (the cheat applied earlier gets us here) */
            if (RtlBalance(&Table->BalancedRoot) == RtlBalancedAvlTree)
            {
                /* The depth has thus increased */
                Table->DepthOfTree++;
            }

            /* We reached the root or a balanced node, so we're done */
            break;
        }
        else
        {
            /* The tree is now unbalanced, so AVL rebalancing must happen */
            RtlpRebalanceAvlTreeNode(NodeOrParent);
            break;
        }
    }
}

ReactOS Development > Doxygen