24 Jul
2010
24 Jul
'10
4 a.m.
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=4822…
==============================================================================
--- 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=482…
==============================================================================
--- 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?r…
==============================================================================
--- 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?r…
==============================================================================
--- 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