[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, inse

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...
==============================================================================
--- 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=4817...
==============================================================================
--- 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=...
==============================================================================
--- 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 ([e-mail])
-*                  Art Yerks ([e-mail])
 */

/* 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=4817...
==============================================================================
--- 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&...
==============================================================================
--- 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?re...
==============================================================================
--- 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?...
==============================================================================
--- 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.r...
==============================================================================
--- 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>