[ros-diffs] [sir_richard] 48173: This patch introduces a highly-shareable version of AVL trees both for RTL usage and for ARM3's MM_AVL_TABLE/MMADDRESS_NODE structures used by VADs on Windows (and soon, ReactOS): [RTL]: Uncouple generic table from AVL table implementation into its own avltable.c [RTL]: Get rid of "Austin" and fix prototypes of AVL table functions. [RTL]: Re-implement AVL table functions, sharing as much code as possible with the SPLAY tree implementation which is pretty decent. Lookup, insert, enumeration are implemented, but not delete. [RTL]: Make large part of the RTL AVL package into its own "support" file that can work both with MMADDRESS_NODE and RTL_BALANCED_LINKS structures. The former is used by ARM3 for VADs. [NTOS]: Implement basic VAD AVL tree routines (Insert, LookupEmpty, GetPrevious, CheckForConflict, Locate). This is enough to insert VADs, find a free address range, and locate a VAD by address. No delete yet Thanks to Timo Kreuzer for some clever definitions, Knuth for his genius, several online C implementations for ideas, the HPI kernel blog for insight on how Windows does it, and others.
sir_richard at svn.reactos.org
sir_richard at svn.reactos.org
Thu Jul 22 01:41:46 UTC 2010
Author: sir_richard
Date: Thu Jul 22 01:41:45 2010
New Revision: 48173
URL: http://svn.reactos.org/svn/reactos?rev=48173&view=rev
Log:
This patch introduces a highly-shareable version of AVL trees both for RTL usage and for ARM3's MM_AVL_TABLE/MMADDRESS_NODE structures used by VADs on Windows (and soon, ReactOS):
[RTL]: Uncouple generic table from AVL table implementation into its own avltable.c
[RTL]: Get rid of "Austin" and fix prototypes of AVL table functions.
[RTL]: Re-implement AVL table functions, sharing as much code as possible with the SPLAY tree implementation which is pretty decent. Lookup, insert, enumeration are implemented, but not delete.
[RTL]: Make large part of the RTL AVL package into its own "support" file that can work both with MMADDRESS_NODE and RTL_BALANCED_LINKS structures. The former is used by ARM3 for VADs.
[NTOS]: Implement basic VAD AVL tree routines (Insert, LookupEmpty, GetPrevious, CheckForConflict, Locate). This is enough to insert VADs, find a free address range, and locate a VAD by address. No delete yet
Thanks to Timo Kreuzer for some clever definitions, Knuth for his genius, several online C implementations for ideas, the HPI kernel blog for insight on how Windows does it, and others.
Added:
trunk/reactos/lib/rtl/avlsupp.c (with props)
trunk/reactos/lib/rtl/avltable.c (with props)
trunk/reactos/lib/rtl/rtlavl.h (with props)
trunk/reactos/ntoskrnl/mm/ARM3/miavl.h (with props)
trunk/reactos/ntoskrnl/mm/ARM3/vadnode.c (with props)
Removed:
trunk/reactos/lib/rtl/austin/
Modified:
trunk/reactos/lib/rtl/generictable.c
trunk/reactos/lib/rtl/rtl.rbuild
trunk/reactos/ntoskrnl/ntoskrnl-generic.rbuild
Added: trunk/reactos/lib/rtl/avlsupp.c
URL: http://svn.reactos.org/svn/reactos/trunk/reactos/lib/rtl/avlsupp.c?rev=48173&view=auto
==============================================================================
--- trunk/reactos/lib/rtl/avlsupp.c (added)
+++ trunk/reactos/lib/rtl/avlsupp.c [iso-8859-1] Thu Jul 22 01:41:45 2010
@@ -1,0 +1,295 @@
+/*
+ * PROJECT: ReactOS Runtime Library
+ * LICENSE: BSD - See COPYING.ARM in the top level directory
+ * FILE: lib/rtl/avlsupp.c
+ * PURPOSE: AVL Tree Internal Support Routines/Main Algorithms
+ * PROGRAMMERS: ReactOS Portable Systems Group
+ */
+
+/* INCLUDES ******************************************************************/
+
+/* Internal header for table entries */
+typedef struct _TABLE_ENTRY_HEADER
+{
+ RTL_BALANCED_LINKS BalancedLinks;
+ LIST_ENTRY ListEntry;
+ LONGLONG UserData;
+} TABLE_ENTRY_HEADER, *PTABLE_ENTRY_HEADER;
+
+typedef enum _RTL_AVL_BALANCE_FACTOR
+{
+ RtlUnbalancedAvlTree = -2,
+ RtlLeftHeavyAvlTree,
+ RtlBalancedAvlTree,
+ RtlRightHeavyAvlTree,
+} RTL_AVL_BALANCE_FACTOR;
+
+C_ASSERT(RtlBalancedAvlTree == 0);
+
+/* FUNCTIONS ******************************************************************/
+
+TABLE_SEARCH_RESULT
+FORCEINLINE
+RtlpFindAvlTableNodeOrParent(IN PRTL_AVL_TABLE Table,
+ IN PVOID Buffer,
+ OUT PRTL_BALANCED_LINKS *NodeOrParent)
+{
+ PRTL_BALANCED_LINKS CurrentNode, ChildNode;
+ RTL_GENERIC_COMPARE_RESULTS Result;
+
+ /* Quick check to see if the table is empty */
+ if (!Table->NumberGenericTableElements) return TableEmptyTree;
+
+ /* Set the current node */
+ CurrentNode = RtlRightChildAvl(&Table->BalancedRoot);
+
+ /* Start compare loop */
+ while (TRUE)
+ {
+ /* Compare which side is greater */
+ Result = RtlpAvlCompareRoutine(Table,
+ Buffer,
+ &((PTABLE_ENTRY_HEADER)CurrentNode)->
+ UserData);
+ if (Result == GenericLessThan)
+ {
+ /* We're less, check if this is the left child */
+ ChildNode = RtlLeftChildAvl(CurrentNode);
+ if (ChildNode)
+ {
+ /* Continue searching from this node */
+ CurrentNode = ChildNode;
+ }
+ else
+ {
+ /* Otherwise, the element isn't in this tree */
+ *NodeOrParent = CurrentNode;
+ return TableInsertAsLeft;
+ }
+ }
+ else if (Result == GenericGreaterThan)
+ {
+ /* We're more, check if this is the right child */
+ ChildNode = RtlRightChildAvl(CurrentNode);
+ if (ChildNode)
+ {
+ /* Continue searching from this node */
+ CurrentNode = ChildNode;
+ }
+ else
+ {
+ /* Otherwise, the element isn't in this tree */
+ *NodeOrParent = CurrentNode;
+ return TableInsertAsRight;
+ }
+ }
+ else
+ {
+ /* We should've found the node */
+ ASSERT(Result == GenericEqual);
+
+ /* Return node found */
+ *NodeOrParent = CurrentNode;
+ return TableFoundNode;
+ }
+ }
+}
+
+VOID
+FORCEINLINE
+RtlPromoteAvlTreeNode(IN PRTL_BALANCED_LINKS Node)
+{
+ PRTL_BALANCED_LINKS ParentNode, SuperParentNode;
+ PRTL_BALANCED_LINKS *SwapNode1, *SwapNode2;
+
+ /* Grab parents up to 2 levels high */
+ ParentNode = RtlParentAvl(Node);
+ SuperParentNode = RtlParentAvl(ParentNode);
+
+ /* Pick which nodes will be rotated */
+ SwapNode1 = RtlIsLeftChildAvl(Node) ? &ParentNode->LeftChild : &ParentNode->RightChild;
+ SwapNode2 = RtlIsLeftChildAvl(Node) ? &Node->RightChild : &Node->LeftChild;
+
+ /* Do the rotate, and update the parent and super-parent as needed */
+ *SwapNode1 = *SwapNode2;
+ if (*SwapNode1) RtlSetParent(*SwapNode1, ParentNode);
+ *SwapNode2 = ParentNode;
+ RtlSetParent(ParentNode, Node);
+
+ /* Now update the super-parent child link, and make it parent of the node*/
+ SwapNode1 = (RtlLeftChildAvl(SuperParentNode) == ParentNode) ?
+ &SuperParentNode->LeftChild: &SuperParentNode->RightChild;
+ *SwapNode1 = Node;
+ RtlSetParent(Node, SuperParentNode);
+}
+
+BOOLEAN
+FORCEINLINE
+RtlpRebalanceAvlTreeNode(IN PRTL_BALANCED_LINKS Node)
+{
+ PRTL_BALANCED_LINKS ChildNode, SubChildNode;
+ CHAR Balance;
+ ASSERT(RtlParentAvl(Node) != Node);
+
+ /* Get the balance, and figure out which child node to go down on */
+ Balance = RtlBalance(Node);
+ ChildNode = (Balance == RtlRightHeavyAvlTree) ?
+ RtlRightChildAvl(Node) : RtlLeftChildAvl(Node);
+
+ /* The child and node have the same balance, promote the child upwards */
+ if (RtlBalance(ChildNode) == Balance)
+ {
+ /* This performs the rotation described in Knuth A8-A10 for Case 1 */
+ RtlPromoteAvlTreeNode(ChildNode);
+
+ /* The nodes are now balanced */
+ RtlSetBalance(ChildNode, RtlBalancedAvlTree);
+ RtlSetBalance(Node, RtlBalancedAvlTree);
+ return FALSE;
+ }
+
+ /* The child has the opposite balance, a double promotion of the child's child must happen */
+ if (RtlBalance(ChildNode) == -Balance)
+ {
+ /* Pick which sub-child to use based on the balance */
+ SubChildNode = (Balance == RtlRightHeavyAvlTree) ?
+ RtlLeftChildAvl(ChildNode) : RtlRightChildAvl(ChildNode);
+
+ /* Do the double-rotation described in Knuth A8-A10 for Case 2 */
+ RtlPromoteAvlTreeNode(SubChildNode);
+ RtlPromoteAvlTreeNode(SubChildNode);
+
+ /* Was the sub-child sharing the same balance as the node? */
+ if (RtlBalance(SubChildNode) == Balance)
+ {
+ /* Then the subchild is now balanced, and the node's weight is inversed */
+ RtlSetBalance(ChildNode, RtlBalancedAvlTree);
+ RtlSetBalance(Node, -Balance);
+ }
+ else if (RtlBalance(SubChildNode) == -Balance)
+ {
+ /*
+ * In this case, the sub-child weight was the inverse of the node, so
+ * the child now shares the node's balance original weight, while the
+ * node becomes balanced.
+ */
+ RtlSetBalance(ChildNode, Balance);
+ RtlSetBalance(Node, RtlBalancedAvlTree);
+ }
+ else
+ {
+ /*
+ * Otherwise, the sub-child was unbalanced, so both the child and node
+ * now become balanced.
+ */
+ RtlSetBalance(ChildNode, RtlBalancedAvlTree);
+ RtlSetBalance(Node, RtlBalancedAvlTree);
+ }
+
+ /* In all cases, the sub-child is now balanced */
+ RtlSetBalance(SubChildNode, RtlBalancedAvlTree);
+ return FALSE;
+ }
+
+ /*
+ * The case that remains is that the child was already balanced, so this is
+ * This is the rotation required for Case 3 in Knuth A8-A10
+ */
+ RtlPromoteAvlTreeNode(ChildNode);
+
+ /* Now the child has the opposite weight of the node */
+ RtlSetBalance(ChildNode, -Balance);
+
+ /* This only happens on deletion, so we return TRUE to terminate the delete */
+ return TRUE;
+}
+
+VOID
+FORCEINLINE
+RtlpInsertAvlTreeNode(IN PRTL_AVL_TABLE Table,
+ IN PRTL_BALANCED_LINKS NewNode,
+ IN OUT PVOID NodeOrParent,
+ IN OUT TABLE_SEARCH_RESULT SearchResult)
+{
+ CHAR Balance;
+
+ /* Initialize the new inserted element */
+ MI_ASSERT(SearchResult != TableFoundNode);
+ NewNode->LeftChild = NewNode->RightChild = NULL;
+
+ /* 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);
+ MI_ASSERT(RtlBalance(NewNode) == RtlBalancedAvlTree);
+
+ /* 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 */
+ MI_ASSERT(RtlBalance(NewNode) == RtlBalancedAvlTree);
+ 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;
+ }
+ }
+}
+
+/* EOF */
Propchange: trunk/reactos/lib/rtl/avlsupp.c
------------------------------------------------------------------------------
svn:eol-style = native
Added: trunk/reactos/lib/rtl/avltable.c
URL: http://svn.reactos.org/svn/reactos/trunk/reactos/lib/rtl/avltable.c?rev=48173&view=auto
==============================================================================
--- trunk/reactos/lib/rtl/avltable.c (added)
+++ trunk/reactos/lib/rtl/avltable.c [iso-8859-1] Thu Jul 22 01:41:45 2010
@@ -1,0 +1,303 @@
+/*
+* PROJECT: ReactOS Runtime Library
+* LICENSE: BSD - See COPYING.ARM in the top level directory
+* FILE: lib/rtl/avltable.c
+* PURPOSE: AVL Tree Generic Table Implementation
+* PROGRAMMERS: ReactOS Portable Systems Group
+*/
+
+/* INCLUDES ******************************************************************/
+
+#include <rtl.h>
+#define NDEBUG
+#include <debug.h>
+
+/* Include RTL version of AVL support */
+#include "rtlavl.h"
+#include "avlsupp.c"
+
+/* AVL FUNCTIONS *************************************************************/
+
+/*
+ * @implemented
+ */
+VOID
+NTAPI
+RtlInitializeGenericTableAvl(IN OUT PRTL_AVL_TABLE Table,
+ IN PRTL_AVL_COMPARE_ROUTINE CompareRoutine,
+ IN PRTL_AVL_ALLOCATE_ROUTINE AllocateRoutine,
+ IN PRTL_AVL_FREE_ROUTINE FreeRoutine,
+ IN PVOID TableContext)
+{
+ /* Setup the table */
+ RtlZeroMemory(Table, sizeof(RTL_AVL_TABLE));
+ Table->BalancedRoot.Parent = &Table->BalancedRoot;
+ Table->CompareRoutine = CompareRoutine;
+ Table->AllocateRoutine = AllocateRoutine;
+ Table->FreeRoutine = FreeRoutine;
+ Table->TableContext = TableContext;
+}
+
+/*
+ * @implemented
+ */
+PVOID
+NTAPI
+RtlInsertElementGenericTableFullAvl(IN PRTL_AVL_TABLE Table,
+ IN PVOID Buffer,
+ IN ULONG BufferSize,
+ OUT PBOOLEAN NewElement OPTIONAL,
+ IN OUT PVOID NodeOrParent,
+ IN OUT TABLE_SEARCH_RESULT SearchResult)
+{
+ PRTL_BALANCED_LINKS NewNode;
+ PVOID UserData;
+
+ /* Check if the entry wasn't already found */
+ if (SearchResult != TableFoundNode)
+ {
+ /* We're doing an allocation, sanity check */
+ ASSERT(Table->NumberGenericTableElements != (MAXULONG - 1));
+
+ /* Allocate a node */
+ NewNode = Table->AllocateRoutine(Table,
+ BufferSize +
+ FIELD_OFFSET(TABLE_ENTRY_HEADER,
+ UserData));
+ if (!NewNode)
+ {
+ /* No memory or other allocation error, fail */
+ if (NewElement) *NewElement = FALSE;
+ return NULL;
+ }
+
+ /* Data to return to user */
+ UserData = &((PTABLE_ENTRY_HEADER)NewNode)->UserData;
+
+ /* Insert the node in the tree */
+ RtlpInsertAvlTreeNode(Table, NewNode, NodeOrParent, SearchResult);
+
+ /* Copy user buffer */
+ RtlCopyMemory(UserData, Buffer, BufferSize);
+ }
+ else
+ {
+ /* Return the node we already found */
+ NewNode = NodeOrParent;
+ UserData = &((PTABLE_ENTRY_HEADER)NewNode)->UserData;
+ }
+
+ /* Return status */
+ if (NewElement) *NewElement = (SearchResult == TableFoundNode);
+
+ /* Return pointer to user data */
+ return UserData;
+}
+
+/*
+ * @implemented
+ */
+PVOID
+NTAPI
+RtlInsertElementGenericTableAvl(IN PRTL_AVL_TABLE Table,
+ IN PVOID Buffer,
+ IN ULONG BufferSize,
+ OUT PBOOLEAN NewElement OPTIONAL)
+{
+ PRTL_BALANCED_LINKS NodeOrParent = NULL;
+ TABLE_SEARCH_RESULT Result;
+
+ /* Get the balanced links and table search result immediately */
+ Result = RtlpFindAvlTableNodeOrParent(Table, Buffer, &NodeOrParent);
+
+ /* Now call the routine to do the full insert */
+ return RtlInsertElementGenericTableFullAvl(Table,
+ Buffer,
+ BufferSize,
+ NewElement,
+ NodeOrParent,
+ Result);
+}
+
+/*
+ * @implemented
+ */
+BOOLEAN
+NTAPI
+RtlIsGenericTableEmptyAvl(IN PRTL_AVL_TABLE Table)
+{
+ /* If there's no elements, the table is empty */
+ return Table->NumberGenericTableElements == 0;
+}
+
+/*
+ * @implemented
+ */
+ULONG
+NTAPI
+RtlNumberGenericTableElementsAvl(IN PRTL_AVL_TABLE Table)
+{
+ /* Return the element count */
+ return Table->NumberGenericTableElements;
+}
+
+/*
+ * @implemented
+ */
+PVOID
+NTAPI
+RtlLookupElementGenericTableFullAvl(IN PRTL_AVL_TABLE Table,
+ IN PVOID Buffer,
+ IN OUT PVOID *NodeOrParent,
+ IN OUT TABLE_SEARCH_RESULT *SearchResult)
+{
+ /* Find the node */
+ *SearchResult = RtlpFindAvlTableNodeOrParent(Table,
+ Buffer,
+ (PRTL_BALANCED_LINKS*)NodeOrParent);
+ if (*SearchResult != TableFoundNode) return NULL;
+
+ /* Node found, return the user data */
+ return &((PTABLE_ENTRY_HEADER)*NodeOrParent)->UserData;
+}
+
+/*
+ * @implemented
+ */
+PVOID
+NTAPI
+RtlLookupElementGenericTableAvl(IN PRTL_AVL_TABLE Table,
+ IN PVOID Buffer)
+{
+ PRTL_BALANCED_LINKS NodeOrParent;
+ TABLE_SEARCH_RESULT Lookup;
+
+ /* Call the full function */
+ return RtlLookupElementGenericTableFullAvl(Table,
+ Buffer,
+ (PVOID*)&NodeOrParent,
+ &Lookup);
+}
+
+/*
+ * @implemented
+ */
+PVOID
+NTAPI
+RtlEnumerateGenericTableAvl(IN PRTL_AVL_TABLE Table,
+ IN BOOLEAN Restart)
+{
+ /* Reset the restart key if needed */
+ if (Restart) Table->RestartKey = NULL;
+
+ /* Call the full function */
+ return RtlEnumerateGenericTableWithoutSplayingAvl(Table,
+ (PVOID*)&Table->RestartKey);
+}
+
+/*
+* @implemented
+*/
+PVOID
+NTAPI
+RtlLookupFirstMatchingElementGenericTableAvl(IN PRTL_AVL_TABLE Table,
+ IN PVOID Buffer,
+ OUT PVOID *RestartKey)
+{
+ PRTL_BALANCED_LINKS Node, PreviousNode;
+ TABLE_SEARCH_RESULT SearchResult;
+ RTL_GENERIC_COMPARE_RESULTS Result = GenericEqual;
+
+ /* Assume failure */
+ *RestartKey = NULL;
+
+ /* Find the node */
+ SearchResult = RtlpFindAvlTableNodeOrParent(Table, Buffer, &Node);
+ if (SearchResult != TableFoundNode) return NULL;
+
+ /* Scan each predecessor until a match is found */
+ PreviousNode = Node;
+ while (Result == GenericEqual)
+ {
+ /* Save the node */
+ Node = PreviousNode;
+
+ /* Get the predecessor */
+ PreviousNode = RtlRealPredecessorAvl(Node);
+ if ((!PreviousNode) || (RtlParentAvl(PreviousNode) == PreviousNode)) break;
+
+ /* Check if this node matches */
+ Result = RtlpAvlCompareRoutine(Table,
+ Buffer,
+ &((PTABLE_ENTRY_HEADER)PreviousNode)->
+ UserData);
+ }
+
+ /* Save the node as the restart key, and return its data */
+ *RestartKey = Node;
+ return &((PTABLE_ENTRY_HEADER)Node)->UserData;
+}
+
+/*
+ * @unimplemented
+ */
+PVOID
+NTAPI
+RtlEnumerateGenericTableWithoutSplayingAvl(IN PRTL_AVL_TABLE Table,
+ IN OUT PVOID *RestartKey)
+{
+ PRTL_BALANCED_LINKS CurrentNode;
+
+ /* Skip an empty tree */
+ if (RtlIsGenericTableEmptyAvl(Table)) return NULL;
+
+ /* Check if we have a starting point */
+ if (!*RestartKey)
+ {
+ /* We'll have to find it, keep going until the leftmost child */
+ for (CurrentNode = RtlRightChildAvl(&Table->BalancedRoot);
+ RtlLeftChildAvl(CurrentNode);
+ CurrentNode = RtlLeftChildAvl(CurrentNode));
+
+ /* Found it */
+ *RestartKey = CurrentNode;
+ }
+ else
+ {
+ /* We already had a child, keep going by getting its successor */
+ CurrentNode = RtlRealSuccessorAvl(*RestartKey);
+
+ /* If there was one, update the restart key */
+ if (CurrentNode) *RestartKey = CurrentNode;
+ }
+
+ /* Return the node's data if it was found, otherwise return NULL */
+ if (CurrentNode) return &((PTABLE_ENTRY_HEADER)CurrentNode)->UserData;
+ return NULL;
+}
+
+/*
+ * @unimplemented
+ */
+PVOID
+NTAPI
+RtlGetElementGenericTableAvl(IN PRTL_AVL_TABLE Table,
+ IN ULONG I)
+{
+ UNIMPLEMENTED;
+ return NULL;
+}
+
+/*
+ * @implemented
+ */
+BOOLEAN
+NTAPI
+RtlDeleteElementGenericTableAvl(IN PRTL_AVL_TABLE Table,
+ IN PVOID Buffer)
+{
+ UNIMPLEMENTED;
+ return FALSE;
+}
+
+/* EOF */
Propchange: trunk/reactos/lib/rtl/avltable.c
------------------------------------------------------------------------------
svn:eol-style = native
Modified: trunk/reactos/lib/rtl/generictable.c
URL: http://svn.reactos.org/svn/reactos/trunk/reactos/lib/rtl/generictable.c?rev=48173&r1=48172&r2=48173&view=diff
==============================================================================
--- trunk/reactos/lib/rtl/generictable.c [iso-8859-1] (original)
+++ trunk/reactos/lib/rtl/generictable.c [iso-8859-1] Thu Jul 22 01:41:45 2010
@@ -1,16 +1,14 @@
/*
-* PROJECT: ReactOS Kernel
+* PROJECT: ReactOS Runtime Library
* LICENSE: GPL - See COPYING in the top level directory
* FILE: lib/rtl/generictable.c
-* PURPOSE: Splay Tree and AVL Tree Generic Table Implementation
+* PURPOSE: Splay Tree Generic Table Implementation
* PROGRAMMERS: Alex Ionescu (alex.ionescu at reactos.org)
-* Art Yerks (ayerkes at speakeasy.net)
*/
/* INCLUDES ******************************************************************/
#include <rtl.h>
-#include "austin/avl.h"
#define NDEBUG
#include <debug.h>
@@ -508,261 +506,4 @@
ListEntry))->UserData;
}
-/* AVL FUNCTIONS *************************************************************/
-
-/*
- * @implemented
- */
-PVOID
-NTAPI
-RtlLookupElementGenericTableFullAvl(IN PRTL_AVL_TABLE Table,
- IN PVOID Buffer,
- IN OUT PVOID *NodeOrParent,
- IN OUT TABLE_SEARCH_RESULT *SearchResult)
-{
- PRTL_BALANCED_LINKS OurNodeOrParent;
- TABLE_SEARCH_RESULT OurSearchResult;
-
- if( !Table->NumberGenericTableElements )
- {
- *SearchResult = TableEmptyTree;
- *NodeOrParent = NULL;
- return NULL;
- }
-
- OurSearchResult = avl_search
- (Table, Buffer,
- Table->BalancedRoot.LeftChild, &OurNodeOrParent);
-
- if(SearchResult) *SearchResult = OurSearchResult;
- if(NodeOrParent) *NodeOrParent = OurNodeOrParent;
-
- if(OurSearchResult == TableFoundNode)
- return avl_data(OurNodeOrParent);
- else
- return NULL;
-}
-
-/*
- * @implemented
- */
-PVOID
-NTAPI
-RtlLookupElementGenericTableAvl(IN PRTL_AVL_TABLE Table,
- IN PVOID Buffer)
-{
- PRTL_BALANCED_LINKS OurNodeOrParent;
- TABLE_SEARCH_RESULT OurSearchResult;
- return RtlLookupElementGenericTableFullAvl
- (Table, Buffer, (PVOID *)&OurNodeOrParent, &OurSearchResult);
-}
-
-/*
- * @implemented
- */
-BOOLEAN
-NTAPI
-RtlDeleteElementGenericTableAvl(IN PRTL_AVL_TABLE Table,
- IN PVOID Buffer)
-{
- TABLE_SEARCH_RESULT Result;
- PRTL_BALANCED_LINKS Node;
-
- RtlLookupElementGenericTableFullAvl
- ( Table, Buffer, (PVOID *)&Node, &Result );
-
- if( Result == TableFoundNode )
- {
- avl_delete_node(Table, Node);
- Table->FreeRoutine(Table, Node);
- if( Table->NumberGenericTableElements == 0 )
- avl_deinit(Table);
- return TRUE;
- }
- else
- {
- return FALSE;
- }
-}
-
-/*
- * @implemented
- */
-PVOID
-NTAPI
-RtlEnumerateGenericTableAvl(IN PRTL_AVL_TABLE Table,
- IN BOOLEAN Restart)
-{
- if( Table->NumberGenericTableElements == 0 )
- return NULL;
-
- if( Restart )
- {
- Table->RestartKey = avl_first(Table);
- }
- else
- {
- Table->RestartKey = avl_next(Table, Table->RestartKey);
- }
- if( !Table->RestartKey )
- return NULL;
- else
- return avl_data(Table->RestartKey);
-}
-
-/*
- * @implemented
- */
-PVOID
-NTAPI
-RtlEnumerateGenericTableWithoutSplayingAvl(IN PRTL_AVL_TABLE Table,
- IN OUT PVOID *RestartKey)
-{
- /* FIXME! */
- return NULL;
-}
-
-/*
- * @implemented
- */
-PVOID
-NTAPI
-RtlGetElementGenericTableAvl(IN PRTL_AVL_TABLE Table,
- IN ULONG I)
-{
- PRTL_BALANCED_LINKS Node;
-
- if( I >= Table->NumberGenericTableElements ) return NULL;
- else
- {
- Node = avl_first(Table);
- while(I--) Node = avl_next(Table, Node);
- return avl_data(Node);
- }
-}
-
-/*
- * @implemented
- */
-VOID
-NTAPI
-RtlInitializeGenericTableAvl(IN OUT PRTL_AVL_TABLE Table,
- IN PRTL_AVL_COMPARE_ROUTINE CompareRoutine,
- IN PRTL_AVL_ALLOCATE_ROUTINE AllocateRoutine,
- IN PRTL_AVL_FREE_ROUTINE FreeRoutine,
- IN PVOID TableContext)
-{
- RtlZeroMemory(Table, sizeof(RTL_AVL_TABLE));
- Table->BalancedRoot.Parent = &Table->BalancedRoot;
- Table->CompareRoutine = CompareRoutine;
- Table->AllocateRoutine = AllocateRoutine;
- Table->FreeRoutine = FreeRoutine;
- Table->TableContext = TableContext;
-}
-
-/*
- * @implemented
- */
-PVOID
-NTAPI
-RtlInsertElementGenericTableFullAvl(IN PRTL_AVL_TABLE Table,
- IN PVOID Buffer,
- IN ULONG BufferSize,
- OUT PBOOLEAN NewElement OPTIONAL,
- IN OUT PVOID *NodeOrParent,
- IN OUT TABLE_SEARCH_RESULT *SearchResult)
-{
- PRTL_BALANCED_LINKS OurNodeOrParent;
- TABLE_SEARCH_RESULT OurSearchResult;
-
- if(Table->NumberGenericTableElements == 0) {
- avl_init(Table);
- }
-
- if(NewElement)
- *NewElement = FALSE;
-
- OurSearchResult = avl_search
- (Table, Buffer,
- Table->BalancedRoot.LeftChild, &OurNodeOrParent);
-
- if(NodeOrParent) *NodeOrParent = OurNodeOrParent;
- if(SearchResult) *SearchResult = OurSearchResult;
-
- if(OurSearchResult == TableFoundNode)
- {
- RtlDeleteElementGenericTableAvl(Table, Buffer);
- return RtlInsertElementGenericTableFullAvl
- (Table, Buffer, BufferSize,
- NewElement, NodeOrParent, SearchResult);
- }
- else
- {
- PRTL_BALANCED_LINKS NewNode =
- Table->AllocateRoutine
- (Table,
- BufferSize + sizeof(RTL_BALANCED_LINKS) + BufferSize);
-
- if( !NewNode ) return NULL;
-
- NewNode->Balance = 0;
- RtlCopyMemory(avl_data(NewNode), Buffer, BufferSize);
-
- OurNodeOrParent = NewNode;
-
- avl_insert_node(Table, NewNode);
- return avl_data(NewNode);
- }
-}
-
-/*
- * @implemented
- */
-PVOID
-NTAPI
-RtlInsertElementGenericTableAvl(IN PRTL_AVL_TABLE Table,
- IN PVOID Buffer,
- IN ULONG BufferSize,
- OUT PBOOLEAN NewElement OPTIONAL)
-{
- PVOID NodeOrParent;
- TABLE_SEARCH_RESULT SearchResult;
-
- return RtlInsertElementGenericTableFullAvl
- (Table, Buffer, BufferSize, NewElement, &NodeOrParent, &SearchResult);
-}
-
-/*
- * @implemented
- */
-BOOLEAN
-NTAPI
-RtlIsGenericTableEmptyAvl(PRTL_AVL_TABLE Table)
-{
- return Table->NumberGenericTableElements == 0;
-}
-
-/*
- * @implemented
- */
-ULONG
-NTAPI
-RtlNumberGenericTableElementsAvl(IN PRTL_AVL_TABLE Table)
-{
- return Table->NumberGenericTableElements;
-}
-
-/*
-* @unimplemented
-*/
-PVOID
-NTAPI
-RtlLookupFirstMatchingElementGenericTableAvl(IN PRTL_AVL_TABLE Table,
- IN PVOID Buffer,
- OUT PVOID *RestartKey)
-{
- UNIMPLEMENTED;
- return NULL;
-}
-
/* EOF */
Modified: trunk/reactos/lib/rtl/rtl.rbuild
URL: http://svn.reactos.org/svn/reactos/trunk/reactos/lib/rtl/rtl.rbuild?rev=48173&r1=48172&r2=48173&view=diff
==============================================================================
--- trunk/reactos/lib/rtl/rtl.rbuild [iso-8859-1] (original)
+++ trunk/reactos/lib/rtl/rtl.rbuild [iso-8859-1] Thu Jul 22 01:41:45 2010
@@ -46,16 +46,12 @@
<file>mem.c</file>
<file>memgen.c</file>
</if>
- <directory name="austin">
- <file>avl.c</file>
- <file>tree.c</file>
- </directory>
-
<file>access.c</file>
<file>acl.c</file>
<file>actctx.c</file>
<file>assert.c</file>
<file>atom.c</file>
+ <file>avltable.c</file>
<file>bitmap.c</file>
<file>bootdata.c</file>
<file>compress.c</file>
Added: trunk/reactos/lib/rtl/rtlavl.h
URL: http://svn.reactos.org/svn/reactos/trunk/reactos/lib/rtl/rtlavl.h?rev=48173&view=auto
==============================================================================
--- trunk/reactos/lib/rtl/rtlavl.h (added)
+++ trunk/reactos/lib/rtl/rtlavl.h [iso-8859-1] Thu Jul 22 01:41:45 2010
@@ -1,0 +1,62 @@
+/*
+ * PROJECT: ReactOS Runtime Library
+ * LICENSE: BSD - See COPYING.ARM in the top level directory
+ * FILE: lib/rtl/rtlavl.h
+ * PURPOSE: RTL AVL Glue
+ * PROGRAMMERS: ReactOS Portable Systems Group
+ */
+
+/* INCLUDES ******************************************************************/
+
+/*
+ * This is the glue code for the AVL package in the RTL meant for external callers.
+ * It's not very exciting, it just uses the RTL-defined fields without any magic,
+ * unlike the Mm version which has special handling for balances and parents, and
+ * does not implement custom comparison callbacks.
+ */
+#define MI_ASSERT(x)
+#define RtlLeftChildAvl(x) (PRTL_BALANCED_LINKS)(RtlLeftChild(x))
+#define RtlRightChildAvl(x) (PRTL_BALANCED_LINKS)(RtlRightChild(x))
+#define RtlParentAvl(x) (PRTL_BALANCED_LINKS)(RtlParent(x))
+#define RtlRealPredecessorAvl(x) (PRTL_BALANCED_LINKS)(RtlRealPredecessor((PRTL_SPLAY_LINKS)(x)))
+#define RtlRealSuccessorAvl(x) (PRTL_BALANCED_LINKS)(RtlRealSuccessor((PRTL_SPLAY_LINKS)(x)))
+#define RtlInsertAsRightChildAvl RtlInsertAsRightChild
+#define RtlInsertAsLeftChildAvl RtlInsertAsLeftChild
+#define RtlIsLeftChildAvl RtlIsLeftChild
+
+RTL_GENERIC_COMPARE_RESULTS
+FORCEINLINE
+RtlpAvlCompareRoutine(IN PRTL_AVL_TABLE Table,
+ IN PVOID Buffer,
+ IN PVOID UserData)
+{
+ /* Do the compare */
+ return Table->CompareRoutine(Table,
+ Buffer,
+ UserData);
+}
+
+VOID
+FORCEINLINE
+RtlSetParent(IN PRTL_BALANCED_LINKS Node,
+ IN PRTL_BALANCED_LINKS Parent)
+{
+ Node->Parent = Parent;
+}
+
+VOID
+FORCEINLINE
+RtlSetBalance(IN PRTL_BALANCED_LINKS Node,
+ IN CHAR Balance)
+{
+ Node->Balance = Balance;
+}
+
+CHAR
+FORCEINLINE
+RtlBalance(IN PRTL_BALANCED_LINKS Node)
+{
+ return Node->Balance;
+}
+
+/* EOF */
Propchange: trunk/reactos/lib/rtl/rtlavl.h
------------------------------------------------------------------------------
svn:eol-style = native
Added: trunk/reactos/ntoskrnl/mm/ARM3/miavl.h
URL: http://svn.reactos.org/svn/reactos/trunk/reactos/ntoskrnl/mm/ARM3/miavl.h?rev=48173&view=auto
==============================================================================
--- trunk/reactos/ntoskrnl/mm/ARM3/miavl.h (added)
+++ trunk/reactos/ntoskrnl/mm/ARM3/miavl.h [iso-8859-1] Thu Jul 22 01:41:45 2010
@@ -1,0 +1,136 @@
+/*
+ * PROJECT: ReactOS Kernel
+ * LICENSE: BSD - See COPYING.ARM in the top level directory
+ * FILE: ntoskrnl/mm/ARM3/miavl.h
+ * PURPOSE: ARM Memory Manager VAD Node Algorithms
+ * PROGRAMMERS: ReactOS Portable Systems Group
+ */
+
+/* INCLUDES ******************************************************************/
+
+/*
+ * This is the glue code for the Memory Manager version of AVL Trees that is used
+ * to store the MM_AVL_TABLE for Virtual Address Descriptors (VAD) in the VadRoot
+ * field in EPROCESS.
+ *
+ * In this version of the package, the balance and parent pointers are stored in
+ * the same field as a union (since we know the parent will be at least 8-byte
+ * aligned), saving some space, but requiring special logic to handle setting and
+ * querying the parent and balance.
+ *
+ * The other difference is that the AVL package for Rtl has custom callbacks for
+ * comparison purposes (which would access some internal, opaque, user data) while
+ * the Mm package stores the user-data inline as StartingVpn and EndingVpn. So
+ * when a compare is being made, RtlpAvlCompareRoutine is called, which will either
+ * perform the Mm work, or call the user-specified callback in the Rtl case.
+ */
+#define PRTL_AVL_TABLE PMM_AVL_TABLE
+#define PRTL_BALANCED_LINKS PMMADDRESS_NODE
+#define MI_ASSERT(x) ASSERT(x)
+
+RTL_GENERIC_COMPARE_RESULTS
+FORCEINLINE
+RtlpAvlCompareRoutine(IN PRTL_AVL_TABLE Table,
+ IN PVOID Buffer,
+ IN PVOID UserData)
+{
+ PRTL_BALANCED_LINKS CurrentNode = (PVOID)((ULONG_PTR)UserData - sizeof(LIST_ENTRY) - sizeof(RTL_BALANCED_LINKS));
+ ULONG_PTR StartingVpn = (ULONG_PTR)Buffer;
+ if (StartingVpn < CurrentNode->StartingVpn)
+ {
+ return GenericLessThan;
+ }
+ else if (StartingVpn <= CurrentNode->EndingVpn)
+ {
+ return GenericEqual;
+ }
+ else
+ {
+ return GenericGreaterThan;
+ }
+}
+
+VOID
+FORCEINLINE
+RtlSetParent(IN PRTL_BALANCED_LINKS Node,
+ IN PRTL_BALANCED_LINKS Parent)
+{
+ Node->u1.Parent = (PRTL_BALANCED_LINKS)((ULONG_PTR)Parent | (Node->u1.Balance & 0x3));
+}
+
+VOID
+FORCEINLINE
+RtlSetBalance(IN PRTL_BALANCED_LINKS Node,
+ IN SCHAR Balance)
+{
+ Node->u1.Balance = Balance;
+}
+
+SCHAR
+FORCEINLINE
+RtlBalance(IN PRTL_BALANCED_LINKS Node)
+{
+ return Node->u1.Balance;
+}
+
+PRTL_BALANCED_LINKS
+FORCEINLINE
+RtlParentAvl(IN PRTL_BALANCED_LINKS Node)
+{
+ return (PRTL_BALANCED_LINKS)((ULONG_PTR)Node->u1.Parent & ~3);
+}
+
+BOOLEAN
+FORCEINLINE
+RtlIsRootAvl(IN PRTL_BALANCED_LINKS Node)
+{
+ return (RtlParentAvl(Node) == Node);
+}
+
+PRTL_BALANCED_LINKS
+FORCEINLINE
+RtlRightChildAvl(IN PRTL_BALANCED_LINKS Node)
+{
+ return Node->RightChild;
+}
+
+PRTL_BALANCED_LINKS
+FORCEINLINE
+RtlLeftChildAvl(IN PRTL_BALANCED_LINKS Node)
+{
+ return Node->LeftChild;
+}
+
+BOOLEAN
+FORCEINLINE
+RtlIsLeftChildAvl(IN PRTL_BALANCED_LINKS Node)
+{
+ return (RtlLeftChildAvl(RtlParentAvl(Node)) == Node);
+}
+
+BOOLEAN
+FORCEINLINE
+RtlIsRightChildAvl(IN PRTL_BALANCED_LINKS Node)
+{
+ return (RtlRightChildAvl(RtlParentAvl(Node)) == Node);
+}
+
+VOID
+FORCEINLINE
+RtlInsertAsLeftChildAvl(IN PRTL_BALANCED_LINKS Parent,
+ IN PRTL_BALANCED_LINKS Node)
+{
+ Parent->LeftChild = Node;
+ RtlSetParent(Node, Parent);
+}
+
+VOID
+FORCEINLINE
+RtlInsertAsRightChildAvl(IN PRTL_BALANCED_LINKS Parent,
+ IN PRTL_BALANCED_LINKS Node)
+{
+ Parent->RightChild = Node;
+ RtlSetParent(Node, Parent);
+}
+
+/* EOF */
Propchange: trunk/reactos/ntoskrnl/mm/ARM3/miavl.h
------------------------------------------------------------------------------
svn:eol-style = native
Added: trunk/reactos/ntoskrnl/mm/ARM3/vadnode.c
URL: http://svn.reactos.org/svn/reactos/trunk/reactos/ntoskrnl/mm/ARM3/vadnode.c?rev=48173&view=auto
==============================================================================
--- trunk/reactos/ntoskrnl/mm/ARM3/vadnode.c (added)
+++ trunk/reactos/ntoskrnl/mm/ARM3/vadnode.c [iso-8859-1] Thu Jul 22 01:41:45 2010
@@ -1,0 +1,268 @@
+/*
+ * PROJECT: ReactOS Kernel
+ * LICENSE: BSD - See COPYING.ARM in the top level directory
+ * FILE: ntoskrnl/mm/ARM3/vadnode.c
+ * PURPOSE: ARM Memory Manager VAD Node Algorithms
+ * PROGRAMMERS: ReactOS Portable Systems Group
+ */
+
+/* INCLUDES *******************************************************************/
+
+#include <ntoskrnl.h>
+#define NDEBUG
+#include <debug.h>
+
+#line 15 "ARM³::VADNODE"
+#define MODULE_INVOLVED_IN_ARM3
+#include "../ARM3/miarm.h"
+
+/* Include Mm version of AVL support */
+#include "../ARM3/miavl.h"
+#include "../../../lib/rtl/avlsupp.c"
+
+/* FUNCTIONS ******************************************************************/
+
+PMMVAD
+NTAPI
+MiLocateAddress(IN PVOID VirtualAddress)
+{
+ PMMVAD FoundVad;
+ ULONG_PTR Vpn;
+ PMM_AVL_TABLE Table = &PsGetCurrentProcess()->VadRoot;
+ TABLE_SEARCH_RESULT SearchResult;
+
+ /* Start with the the hint */
+ FoundVad = (PMMVAD)Table->NodeHint;
+ if (!FoundVad) return NULL;
+
+ /* Check if this VPN is in the hint, if so, use it */
+ Vpn = (ULONG_PTR)VirtualAddress >> PAGE_SHIFT;
+ if ((Vpn >= FoundVad->StartingVpn) && (Vpn <= FoundVad->EndingVpn)) return FoundVad;
+
+ /* VAD hint didn't work, go look for it */
+ SearchResult = RtlpFindAvlTableNodeOrParent(Table,
+ (PVOID)Vpn,
+ (PMMADDRESS_NODE*)&FoundVad);
+ if (SearchResult != TableFoundNode) return NULL;
+
+ /* We found it, update the hint */
+ ASSERT(FoundVad != NULL);
+ ASSERT((Vpn >= FoundVad->StartingVpn) && (Vpn <= FoundVad->EndingVpn));
+ Table->NodeHint = FoundVad;
+ return FoundVad;
+}
+
+PMMADDRESS_NODE
+NTAPI
+MiCheckForConflictingNode(IN ULONG_PTR StartVpn,
+ IN ULONG_PTR EndVpn,
+ IN PMM_AVL_TABLE Table)
+{
+ PMMADDRESS_NODE CurrentNode;
+
+ /* If the tree is empty, there is no conflict */
+ if (!Table->NumberGenericTableElements) return NULL;
+
+ /* Start looping from the right */
+ CurrentNode = RtlRightChildAvl(&Table->BalancedRoot);
+ ASSERT(CurrentNode != NULL);
+ while (CurrentNode)
+ {
+ /* This address comes after */
+ if (StartVpn > CurrentNode->EndingVpn)
+ {
+ /* Keep searching on the right */
+ CurrentNode = RtlRightChildAvl(CurrentNode);
+ }
+ else if (EndVpn < CurrentNode->StartingVpn)
+ {
+ /* This address ends before the node starts, search on the left */
+ CurrentNode = RtlLeftChildAvl(CurrentNode);
+ }
+ else
+ {
+ /* This address is part of this node, return it */
+ break;
+ }
+ }
+
+ /* Return either the conflicting node, or no node at all */
+ return CurrentNode;
+}
+
+VOID
+NTAPI
+MiInsertNode(IN PMMADDRESS_NODE NewNode,
+ IN PMM_AVL_TABLE Table)
+{
+ PMMADDRESS_NODE NodeOrParent = NULL;
+ TABLE_SEARCH_RESULT Result;
+
+ /* Find the node's parent, and where to insert this node */
+ Result = RtlpFindAvlTableNodeOrParent(Table,
+ (PVOID)NewNode->StartingVpn,
+ &NodeOrParent);
+
+ /* Insert it into the tree */
+ RtlpInsertAvlTreeNode(Table, NewNode, NodeOrParent, Result);
+}
+
+PMMADDRESS_NODE
+NTAPI
+MiGetPreviousNode(IN PMMADDRESS_NODE Node)
+{
+ PMMADDRESS_NODE Parent;
+
+ /* Get the left child */
+ if (RtlLeftChildAvl(Node))
+ {
+ /* Get right-most child */
+ Node = RtlLeftChildAvl(Node);
+ while (RtlRightChildAvl(Node)) Node = RtlRightChildAvl(Node);
+ return Node;
+ }
+
+ Parent = RtlParentAvl(Node);
+ ASSERT(Parent != NULL);
+ while (Parent != Node)
+ {
+ /* The parent should be a right child, return the real predecessor */
+ if (RtlIsRightChildAvl(Node))
+ {
+ /* Return it unless it's the root */
+ if (Parent == RtlParentAvl(Parent)) Parent = NULL;
+ return Parent;
+ }
+
+ /* Keep lopping until we find our parent */
+ Node = Parent;
+ Parent = RtlParentAvl(Node);
+ }
+
+ /* Nothing found */
+ return NULL;
+}
+
+NTSTATUS
+NTAPI
+MiFindEmptyAddressRangeDownTree(IN SIZE_T Length,
+ IN ULONG_PTR BoundaryAddress,
+ IN ULONG_PTR Alignment,
+ IN PMM_AVL_TABLE Table,
+ OUT PULONG_PTR Base)
+{
+ PMMADDRESS_NODE Node, PreviousNode;
+ ULONG_PTR CandidateAddress, EndAddress;
+ ULONG AlignEndVpn, CandidateVpn, BoundaryVpn, LowestVpn, StartVpn, EndVpn;
+ PFN_NUMBER PageCount;
+
+ /* Sanity checks */
+ ASSERT(BoundaryAddress);
+ ASSERT(BoundaryAddress <= ((ULONG_PTR)MM_HIGHEST_VAD_ADDRESS + 1));
+
+ /* Compute page length, make sure the boundary address is valid */
+ Length = PAGE_ROUND_UP(Length);
+ if ((BoundaryAddress + 1) < Length) return STATUS_NO_MEMORY;
+
+ /* Compute the highest address to start at */
+ CandidateAddress = ROUND_UP(BoundaryAddress + 1 - Length, Alignment);
+
+ /* Check if the table is empty */
+ if (!Table->NumberGenericTableElements)
+ {
+ /* Tree is empty, the candidate address is already the best one */
+ *Base = CandidateAddress;
+ return STATUS_SUCCESS;
+ }
+
+ /* Starting from the root, go down until the right-most child */
+ Node = RtlRightChildAvl(&Table->BalancedRoot);
+ while (RtlRightChildAvl(Node)) Node = RtlRightChildAvl(Node);
+
+ /* Get the aligned ending address of this VPN */
+ EndAddress = ROUND_UP((Node->EndingVpn << PAGE_SHIFT) | (PAGE_SIZE - 1),
+ Alignment);
+
+ /* Can we fit the address without overflowing into the node? */
+ if ((EndAddress < BoundaryAddress) &&
+ ((BoundaryAddress - EndAddress) > Length))
+ {
+ /* There is enough space to add our address */
+ *Base = ROUND_UP(BoundaryAddress - Length, Alignment);
+ return STATUS_SUCCESS;
+ }
+
+ PageCount = Length >> PAGE_SHIFT;
+ CandidateVpn = CandidateAddress >> PAGE_SHIFT;
+ BoundaryVpn = BoundaryAddress >> PAGE_SHIFT;
+ LowestVpn = (ULONG_PTR)MI_LOWEST_VAD_ADDRESS >> PAGE_SHIFT;
+
+ PreviousNode = MiGetPreviousNode(Node);
+
+ StartVpn = Node->StartingVpn;
+ EndVpn = PreviousNode ? PreviousNode->EndingVpn : 0;
+ AlignEndVpn = ROUND_UP(EndVpn + 1, Alignment >> PAGE_SHIFT);
+
+ /* Loop until a gap is found */
+ for (PageCount = Length >> PAGE_SHIFT,
+ CandidateVpn = CandidateAddress >> PAGE_SHIFT,
+ BoundaryVpn = BoundaryAddress >> PAGE_SHIFT,
+ LowestVpn = (ULONG_PTR)MI_LOWEST_VAD_ADDRESS >> PAGE_SHIFT,
+ PreviousNode = MiGetPreviousNode(Node),
+ StartVpn = Node->StartingVpn,
+ EndVpn = PreviousNode ? PreviousNode->EndingVpn : 0,
+ AlignEndVpn = ROUND_UP(EndVpn + 1, Alignment >> PAGE_SHIFT);
+ PreviousNode;
+ Node = PreviousNode,
+ PreviousNode = MiGetPreviousNode(Node),
+ StartVpn = Node->StartingVpn,
+ EndVpn = PreviousNode ? PreviousNode->EndingVpn : 0,
+ AlignEndVpn = ROUND_UP(EndVpn + 1, Alignment >> PAGE_SHIFT))
+ {
+ /* Can we fit the address without overflowing into the node? */
+ if ((StartVpn < CandidateVpn) && ((StartVpn - AlignEndVpn) >= PageCount))
+ {
+ /* Check if we can get our candidate address */
+ if ((CandidateVpn > EndVpn) && (BoundaryVpn < StartVpn))
+ {
+ /* Use it */
+ *Base = CandidateAddress;
+ return STATUS_SUCCESS;
+ }
+
+ /* Otherwise, can we fit it by changing the start address? */
+ if (StartVpn > AlignEndVpn)
+ {
+ /* It'll fit, compute the new base address for that to work */
+ *Base = ROUND_UP((StartVpn << PAGE_SHIFT) - Length, Alignment);
+ return STATUS_SUCCESS;
+ }
+ }
+
+ PreviousNode = MiGetPreviousNode(Node);
+ StartVpn = Node->StartingVpn;
+ EndVpn = PreviousNode ? PreviousNode->EndingVpn : 0;
+ AlignEndVpn = ROUND_UP(EndVpn + 1, Alignment >> PAGE_SHIFT);
+ }
+
+ /* See if we could squeeze into the last descriptor */
+ if ((StartVpn > LowestVpn) && ((StartVpn - LowestVpn) >= PageCount))
+ {
+ /* Check if we can try our candidate address */
+ if (BoundaryVpn < StartVpn)
+ {
+ /* Use it */
+ *Base = CandidateAddress;
+ return STATUS_SUCCESS;
+ }
+
+ /* Otherwise, change the base address to what's needed to fit in */
+ *Base = ROUND_UP((StartVpn << PAGE_SHIFT) - Length, Alignment);
+ return STATUS_SUCCESS;
+ }
+
+ /* No address space left at all */
+ return STATUS_NO_MEMORY;
+}
+
+/* EOF */
Propchange: trunk/reactos/ntoskrnl/mm/ARM3/vadnode.c
------------------------------------------------------------------------------
svn:eol-style = native
Modified: trunk/reactos/ntoskrnl/ntoskrnl-generic.rbuild
URL: http://svn.reactos.org/svn/reactos/trunk/reactos/ntoskrnl/ntoskrnl-generic.rbuild?rev=48173&r1=48172&r2=48173&view=diff
==============================================================================
--- trunk/reactos/ntoskrnl/ntoskrnl-generic.rbuild [iso-8859-1] (original)
+++ trunk/reactos/ntoskrnl/ntoskrnl-generic.rbuild [iso-8859-1] Thu Jul 22 01:41:45 2010
@@ -408,6 +408,7 @@
<file>procsup.c</file>
<file>sysldr.c</file>
<file>syspte.c</file>
+ <file>vadnode.c</file>
<file>virtual.c</file>
</directory>
<file>anonmem.c</file>
More information about the Ros-diffs
mailing list