[NTOS]: Implement an AVL node deletion algorithm (RtlpDeleteAvlTreeNode). Use it...

svn path=/trunk/; revision=48223

diff --git a/reactos/lib/rtl/avlsupp.c b/reactos/lib/rtl/avlsupp.c
index b5546b7..74d5163 100644 (file)
--- a/reactos/lib/rtl/avlsupp.c
+++ b/reactos/lib/rtl/avlsupp.c
@@ -292,4 +292,102 @@ RtlpInsertAvlTreeNode(IN PRTL_AVL_TABLE Table,
     }
 }
 
+VOID
+FORCEINLINE
+RtlpDeleteAvlTreeNode(IN PRTL_AVL_TABLE Table,
+                      IN PRTL_BALANCED_LINKS Node)
+{
+    PRTL_BALANCED_LINKS DeleteNode, ParentNode;
+    PRTL_BALANCED_LINKS *Node1, *Node2;
+    CHAR Balance;
+    
+    /* Take one of the children if possible */
+    if (!(RtlLeftChildAvl(Node)) || !(RtlRightChildAvl(Node))) DeleteNode = Node;
+    
+    /* Otherwise, check if one side is longer */
+    if (!(DeleteNode) && (RtlBalance(Node) >= RtlBalancedAvlTree))
+    {
+        /* Pick the successor which will be the longest side in this case */
+        DeleteNode = RtlRightChildAvl(Node);
+        while (RtlLeftChildAvl(DeleteNode)) DeleteNode = RtlLeftChildAvl(DeleteNode);
+    }
+    else if (!DeleteNode)
+    {
+        /* Pick the predecessor which will be the longest side in this case */
+        DeleteNode = RtlLeftChildAvl(Node);
+        while (RtlRightChildAvl(DeleteNode)) DeleteNode = RtlRightChildAvl(DeleteNode);        
+    }
+    
+    /* Get the parent node */
+    ParentNode = RtlParentAvl(DeleteNode);
+    
+    /* Pick which now to use based on whether or not we have a left child */
+    Node1 = RtlLeftChildAvl(DeleteNode) ? &DeleteNode->LeftChild : &DeleteNode->RightChild;
+            
+    /* Pick which node to swap based on if we're already a left child or not */
+    Node2 = RtlIsLeftChildAvl(DeleteNode) ? &ParentNode->LeftChild : &ParentNode->RightChild;
+        
+    /* Pick the correct balance depending on which side will get heavier */
+    Balance = RtlIsLeftChildAvl(DeleteNode) ? RtlLeftHeavyAvlTree : RtlRightHeavyAvlTree;
+    
+    /* Swap the children nodes, making one side heavier */
+    *Node2 = *Node1;
+    
+    /* If the node has a child now, update its parent */
+    if (*Node1) RtlSetParent(*Node1, ParentNode);
+
+    /* Assume balanced root for loop optimization */
+    RtlSetBalance(&Table->BalancedRoot, RtlBalancedAvlTree);
+    
+    /* Loop up the tree by parents */
+    while (TRUE)
+    {
+        /* Check if the tree's balance increased */
+        if (RtlBalance(ParentNode) == Balance)
+        {
+            /* Now the tree is balanced */
+            RtlSetBalance(ParentNode, RtlBalancedAvlTree);
+        }
+        else if (RtlBalance(ParentNode) == RtlBalancedAvlTree)
+        {
+            /* The tree has now become less balanced, since it was balanced */
+            RtlSetBalance(ParentNode, -Balance);
+
+            /* Deal with the loop optimization to detect loss of a tree level */
+            if (RtlBalance(&Table->BalancedRoot) != RtlBalancedAvlTree) Table->DepthOfTree--;
+            break;
+        }
+        else
+        {
+            /* The tree has become unbalanced, so a rebalance is needed */
+            if (RtlpRebalanceAvlTreeNode(ParentNode)) break;
+
+            /* Get the new parent after the balance */
+            ParentNode = RtlParentAvl(ParentNode);
+        }
+
+        /* Choose which balance factor to use based on which side we're on */
+        Balance = RtlIsRightChild(ParentNode) ?
+                  RtlRightHeavyAvlTree : RtlLeftHeavyAvlTree;
+        
+        /* Iterate up the tree */
+        ParentNode = RtlParentAvl(ParentNode);
+    }
+
+    /* Check if this isn't the node we ended up deleting directly */
+    if (Node == DeleteNode) return;
+
+    /* Copy the deleted node itself */
+    RtlpCopyAvlNodeData(DeleteNode, Node);
+    
+    /* Pick the right node to unlink */
+    Node1 = RtlIsLeftChildAvl(Node) ?
+            &(RtlParentAvl(DeleteNode))->LeftChild : &(RtlParentAvl(DeleteNode))->RightChild;
+    *Node1 = DeleteNode;
+
+    /* Reparent as appropriate */
+    if (RtlLeftChildAvl(DeleteNode)) RtlSetParent(RtlLeftChildAvl(DeleteNode), DeleteNode);
+    if (RtlRightChildAvl(DeleteNode)) RtlSetParent(RtlRightChildAvl(DeleteNode), DeleteNode);
+}
+
 /* EOF */

diff --git a/reactos/lib/rtl/avltable.c b/reactos/lib/rtl/avltable.c
index f85025b..acfb99d 100644 (file)
--- a/reactos/lib/rtl/avltable.c
+++ b/reactos/lib/rtl/avltable.c
@@ -296,8 +296,30 @@ NTAPI
 RtlDeleteElementGenericTableAvl(IN PRTL_AVL_TABLE Table,
                                 IN PVOID Buffer)
 {
-    UNIMPLEMENTED;
-       return FALSE;
+    PRTL_BALANCED_LINKS Node;
+    TABLE_SEARCH_RESULT SearchResult;
+
+    /* Find the node */
+    SearchResult = RtlpFindAvlTableNodeOrParent(Table, Buffer, &Node);
+    if (SearchResult != TableFoundNode) return FALSE;
+    
+    /* If this node was the key, update it */
+    if (Node == Table->RestartKey) Table->RestartKey = RtlRealPredecessorAvl(Node);
+    
+    /* Do the delete */
+    Table->DeleteCount++;
+    RtlpDeleteAvlTreeNode(Table, Node);
+    Table->NumberGenericTableElements--;
+    
+    /* Reset accounting */
+    Table->WhichOrderedElement = 0;
+    Table->OrderedPointer = NULL;
+
+    /* Free the node's data */
+    Table->FreeRoutine(Table, Node);
+
+    /* It's done */
+    return TRUE;
 }
 
 /* EOF */

diff --git a/reactos/lib/rtl/rtlavl.h b/reactos/lib/rtl/rtlavl.h
index b320ad4..7088ce1 100644 (file)
--- a/reactos/lib/rtl/rtlavl.h
+++ b/reactos/lib/rtl/rtlavl.h
@@ -24,6 +24,14 @@
 #define RtlInsertAsLeftChildAvl     RtlInsertAsLeftChild
 #define RtlIsLeftChildAvl           RtlIsLeftChild
 
+VOID
+FORCEINLINE
+RtlpCopyAvlNodeData(IN PRTL_BALANCED_LINKS Node1,
+                    IN PRTL_BALANCED_LINKS Node2)
+{
+    *Node1 = *Node2;
+}
+ 
 RTL_GENERIC_COMPARE_RESULTS
 FORCEINLINE
 RtlpAvlCompareRoutine(IN PRTL_AVL_TABLE Table,

diff --git a/reactos/ntoskrnl/mm/ARM3/miarm.h b/reactos/ntoskrnl/mm/ARM3/miarm.h
index 417544c..7d82887 100644 (file)
--- a/reactos/ntoskrnl/mm/ARM3/miarm.h
+++ b/reactos/ntoskrnl/mm/ARM3/miarm.h
@@ -1107,4 +1107,11 @@ MiInsertNode(
     IN PMM_AVL_TABLE Table
 );
 
+VOID
+NTAPI
+MiRemoveNode(
+    IN PMMADDRESS_NODE Node,
+    IN PMM_AVL_TABLE Table
+);
+
 /* EOF */

diff --git a/reactos/ntoskrnl/mm/ARM3/miavl.h b/reactos/ntoskrnl/mm/ARM3/miavl.h
index e32d00a..8b0ce6d 100644 (file)
--- a/reactos/ntoskrnl/mm/ARM3/miavl.h
+++ b/reactos/ntoskrnl/mm/ARM3/miavl.h
@@ -28,6 +28,16 @@
 #define PRTL_BALANCED_LINKS         PMMADDRESS_NODE
 #define MI_ASSERT(x)                ASSERT(x)
 
+VOID
+FORCEINLINE
+RtlpCopyAvlNodeData(IN PRTL_BALANCED_LINKS Node1,
+                    IN PRTL_BALANCED_LINKS Node2)
+{
+    Node1->u1.Parent = Node2->u1.Parent;
+    Node1->LeftChild = Node2->LeftChild;
+    Node1->RightChild = Node2->RightChild;
+}
+
 RTL_GENERIC_COMPARE_RESULTS
 FORCEINLINE
 RtlpAvlCompareRoutine(IN PRTL_AVL_TABLE Table,

diff --git a/reactos/ntoskrnl/mm/ARM3/vadnode.c b/reactos/ntoskrnl/mm/ARM3/vadnode.c
index f87c585..c6f8be6 100644 (file)
--- a/reactos/ntoskrnl/mm/ARM3/vadnode.c
+++ b/reactos/ntoskrnl/mm/ARM3/vadnode.c
@@ -107,6 +107,18 @@ MiInsertNode(IN PMMADDRESS_NODE NewNode,
     RtlpInsertAvlTreeNode(Table, NewNode, NodeOrParent, Result);
 }
 
+VOID
+NTAPI
+MiRemoveNode(IN PMMADDRESS_NODE Node,
+             IN PMM_AVL_TABLE Table)
+{
+    /* Call the AVL code */
+    RtlpDeleteAvlTreeNode(Table, Node);
+    
+    /* Decrease element count */
+    Table->NumberGenericTableElements--;
+}
+
 PMMADDRESS_NODE
 NTAPI
 MiGetPreviousNode(IN PMMADDRESS_NODE Node)