[sir_richard] 48223: [NTOS]: Implement an AVL node deletion algorithm (RtlpDeleteAvlTreeNode). Use it in MiRemoveNode, now implemeneted, and RtlDeleteElementGenericTableAvl, also now implemented. It hopefully works.

Author: sir_richard
Date: Sat Jul 24 04:00:22 2010
New Revision: 48223

URL: http://svn.reactos.org/svn/reactos?rev=48223&view=rev
Log:
[NTOS]: Implement an AVL node deletion algorithm (RtlpDeleteAvlTreeNode). Use it in MiRemoveNode, now implemeneted, and RtlDeleteElementGenericTableAvl, also now implemented. It hopefully works.

Modified:
    trunk/reactos/lib/rtl/avlsupp.c
    trunk/reactos/lib/rtl/avltable.c
    trunk/reactos/lib/rtl/rtlavl.h
    trunk/reactos/ntoskrnl/mm/ARM3/miarm.h
    trunk/reactos/ntoskrnl/mm/ARM3/miavl.h
    trunk/reactos/ntoskrnl/mm/ARM3/vadnode.c

Modified: trunk/reactos/lib/rtl/avlsupp.c
URL: http://svn.reactos.org/svn/reactos/trunk/reactos/lib/rtl/avlsupp.c?rev=48223...
==============================================================================
--- trunk/reactos/lib/rtl/avlsupp.c [iso-8859-1] (original)
+++ trunk/reactos/lib/rtl/avlsupp.c [iso-8859-1] Sat Jul 24 04:00:22 2010
@@ -292,4 +292,102 @@
     }
 }

+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 */

Modified: trunk/reactos/lib/rtl/avltable.c
URL: http://svn.reactos.org/svn/reactos/trunk/reactos/lib/rtl/avltable.c?rev=4822...
==============================================================================
--- trunk/reactos/lib/rtl/avltable.c [iso-8859-1] (original)
+++ trunk/reactos/lib/rtl/avltable.c [iso-8859-1] Sat Jul 24 04:00:22 2010
@@ -296,8 +296,30 @@
 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 */

Modified: trunk/reactos/lib/rtl/rtlavl.h
URL: http://svn.reactos.org/svn/reactos/trunk/reactos/lib/rtl/rtlavl.h?rev=48223&...
==============================================================================
--- trunk/reactos/lib/rtl/rtlavl.h [iso-8859-1] (original)
+++ trunk/reactos/lib/rtl/rtlavl.h [iso-8859-1] Sat Jul 24 04:00:22 2010
@@ -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,

Modified: trunk/reactos/ntoskrnl/mm/ARM3/miarm.h
URL: http://svn.reactos.org/svn/reactos/trunk/reactos/ntoskrnl/mm/ARM3/miarm.h?re...
==============================================================================
--- trunk/reactos/ntoskrnl/mm/ARM3/miarm.h [iso-8859-1] (original)
+++ trunk/reactos/ntoskrnl/mm/ARM3/miarm.h [iso-8859-1] Sat Jul 24 04:00:22 2010
@@ -1107,4 +1107,11 @@
     IN PMM_AVL_TABLE Table
 );

+VOID
+NTAPI
+MiRemoveNode(
+    IN PMMADDRESS_NODE Node,
+    IN PMM_AVL_TABLE Table
+);
+
 /* EOF */

Modified: trunk/reactos/ntoskrnl/mm/ARM3/miavl.h
URL: http://svn.reactos.org/svn/reactos/trunk/reactos/ntoskrnl/mm/ARM3/miavl.h?re...
==============================================================================
--- trunk/reactos/ntoskrnl/mm/ARM3/miavl.h [iso-8859-1] (original)
+++ trunk/reactos/ntoskrnl/mm/ARM3/miavl.h [iso-8859-1] Sat Jul 24 04:00:22 2010
@@ -27,6 +27,16 @@
 #define PRTL_AVL_TABLE              PMM_AVL_TABLE
 #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

Modified: trunk/reactos/ntoskrnl/mm/ARM3/vadnode.c
URL: http://svn.reactos.org/svn/reactos/trunk/reactos/ntoskrnl/mm/ARM3/vadnode.c?...
==============================================================================
--- trunk/reactos/ntoskrnl/mm/ARM3/vadnode.c [iso-8859-1] (original)
+++ trunk/reactos/ntoskrnl/mm/ARM3/vadnode.c [iso-8859-1] Sat Jul 24 04:00:22 2010
@@ -105,6 +105,18 @@

/* Insert it into the tree */
     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