From 56af6d9a256c29f4d41091e1692dda9716a4a15f Mon Sep 17 00:00:00 2001 From: Timo Kreuzer Date: Sat, 11 Oct 2014 12:40:24 +0000 Subject: [PATCH] [RTL/NTOSKRNL] Rename AVL tree functions with macros when included from Mm. This is necessary since the compiler might chose to not inline these functions (and does so on MSVC debug builds) yet only generate one instance of the function, where 2 different versions are required. This caused RtlAvlTree functions to fail on MSVC builds, since they were calling the functions compiled for Mm AVL trees! svn path=/trunk/; revision=64664 --- reactos/lib/rtl/avlsupp.c | 10 +++--- reactos/ntoskrnl/mm/ARM3/miavl.h | 52 ++++++++++++++++++++------------ 2 files changed, 38 insertions(+), 24 deletions(-) diff --git a/reactos/lib/rtl/avlsupp.c b/reactos/lib/rtl/avlsupp.c index 6d303d19a68..ff89bc1dbda 100644 --- a/reactos/lib/rtl/avlsupp.c +++ b/reactos/lib/rtl/avlsupp.c @@ -96,7 +96,7 @@ RtlpFindAvlTableNodeOrParent(IN PRTL_AVL_TABLE Table, FORCEINLINE VOID -RtlPromoteAvlTreeNode(IN PRTL_BALANCED_LINKS Node) +RtlpPromoteAvlTreeNode(IN PRTL_BALANCED_LINKS Node) { PRTL_BALANCED_LINKS ParentNode, SuperParentNode; PRTL_BALANCED_LINKS *SwapNode1, *SwapNode2; @@ -139,7 +139,7 @@ RtlpRebalanceAvlTreeNode(IN PRTL_BALANCED_LINKS Node) if (RtlBalance(ChildNode) == Balance) { /* This performs the rotation described in Knuth A8-A10 for Case 1 */ - RtlPromoteAvlTreeNode(ChildNode); + RtlpPromoteAvlTreeNode(ChildNode); /* The nodes are now balanced */ RtlSetBalance(ChildNode, RtlBalancedAvlTree); @@ -155,8 +155,8 @@ RtlpRebalanceAvlTreeNode(IN PRTL_BALANCED_LINKS Node) RtlLeftChildAvl(ChildNode) : RtlRightChildAvl(ChildNode); /* Do the double-rotation described in Knuth A8-A10 for Case 2 */ - RtlPromoteAvlTreeNode(SubChildNode); - RtlPromoteAvlTreeNode(SubChildNode); + RtlpPromoteAvlTreeNode(SubChildNode); + RtlpPromoteAvlTreeNode(SubChildNode); /* Was the sub-child sharing the same balance as the node? */ if (RtlBalance(SubChildNode) == Balance) @@ -194,7 +194,7 @@ RtlpRebalanceAvlTreeNode(IN PRTL_BALANCED_LINKS Node) * 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); + RtlpPromoteAvlTreeNode(ChildNode); /* Now the child has the opposite weight of the node */ RtlSetBalance(ChildNode, -Balance); diff --git a/reactos/ntoskrnl/mm/ARM3/miavl.h b/reactos/ntoskrnl/mm/ARM3/miavl.h index 6c514baefab..ae4146f49f8 100644 --- a/reactos/ntoskrnl/mm/ARM3/miavl.h +++ b/reactos/ntoskrnl/mm/ARM3/miavl.h @@ -28,9 +28,30 @@ #define PRTL_BALANCED_LINKS PMMADDRESS_NODE #define MI_ASSERT(x) ASSERT(x) +/* We need to rename the functions to prevent conflicts when not inlined! */ +#define RtlpFindAvlTableNodeOrParent MiFindAvlTableNodeOrParent +#define RtlpPromoteAvlTreeNode MiPromoteAvlTreeNode +#define RtlpRebalanceAvlTreeNode MiRebalanceAvlTreeNode +#define RtlpInsertAvlTreeNode MiInsertAvlTreeNode +#define RtlpDeleteAvlTreeNode MiDeleteAvlTreeNode + +/* These are implementation specific */ +#define RtlpCopyAvlNodeData MiCopyAvlNodeData +#define RtlpAvlCompareRoutine MiAvlCompareRoutine +#define RtlSetParent MiSetParent +#define RtlSetBalance MiSetBalance +#define RtlBalance MiBalance +#define RtlParentAvl MiParentAvl +#define RtlRightChildAvl MiRightChildAvl +#define RtlLeftChildAvl MiLeftChildAvl +#define RtlIsLeftChildAvl MiIsLeftChildAvl +#define RtlIsRightChildAvl MiIsRightChildAvl +#define RtlInsertAsLeftChildAvl MiInsertAsLeftChildAvl +#define RtlInsertAsRightChildAvl MiInsertAsRightChildAvl + FORCEINLINE VOID -RtlpCopyAvlNodeData(IN PRTL_BALANCED_LINKS Node1, +MiCopyAvlNodeData(IN PRTL_BALANCED_LINKS Node1, IN PRTL_BALANCED_LINKS Node2) { Node1->u1.Parent = Node2->u1.Parent; @@ -40,7 +61,7 @@ RtlpCopyAvlNodeData(IN PRTL_BALANCED_LINKS Node1, FORCEINLINE RTL_GENERIC_COMPARE_RESULTS -RtlpAvlCompareRoutine(IN PRTL_AVL_TABLE Table, +MiAvlCompareRoutine(IN PRTL_AVL_TABLE Table, IN PVOID Buffer, IN PVOID UserData) { @@ -62,7 +83,7 @@ RtlpAvlCompareRoutine(IN PRTL_AVL_TABLE Table, FORCEINLINE VOID -RtlSetParent(IN PRTL_BALANCED_LINKS Node, +MiSetParent(IN PRTL_BALANCED_LINKS Node, IN PRTL_BALANCED_LINKS Parent) { Node->u1.Parent = (PRTL_BALANCED_LINKS)((ULONG_PTR)Parent | (Node->u1.Balance & 0x3)); @@ -70,7 +91,7 @@ RtlSetParent(IN PRTL_BALANCED_LINKS Node, FORCEINLINE VOID -RtlSetBalance(IN PRTL_BALANCED_LINKS Node, +MiSetBalance(IN PRTL_BALANCED_LINKS Node, IN SCHAR Balance) { Node->u1.Balance = Balance; @@ -78,56 +99,49 @@ RtlSetBalance(IN PRTL_BALANCED_LINKS Node, FORCEINLINE SCHAR -RtlBalance(IN PRTL_BALANCED_LINKS Node) +MiBalance(IN PRTL_BALANCED_LINKS Node) { return (SCHAR)Node->u1.Balance; } FORCEINLINE PRTL_BALANCED_LINKS -RtlParentAvl(IN PRTL_BALANCED_LINKS Node) +MiParentAvl(IN PRTL_BALANCED_LINKS Node) { return (PRTL_BALANCED_LINKS)((ULONG_PTR)Node->u1.Parent & ~3); } -FORCEINLINE -BOOLEAN -RtlIsRootAvl(IN PRTL_BALANCED_LINKS Node) -{ - return (RtlParentAvl(Node) == Node); -} - FORCEINLINE PRTL_BALANCED_LINKS -RtlRightChildAvl(IN PRTL_BALANCED_LINKS Node) +MiRightChildAvl(IN PRTL_BALANCED_LINKS Node) { return Node->RightChild; } FORCEINLINE PRTL_BALANCED_LINKS -RtlLeftChildAvl(IN PRTL_BALANCED_LINKS Node) +MiLeftChildAvl(IN PRTL_BALANCED_LINKS Node) { return Node->LeftChild; } FORCEINLINE BOOLEAN -RtlIsLeftChildAvl(IN PRTL_BALANCED_LINKS Node) +MiIsLeftChildAvl(IN PRTL_BALANCED_LINKS Node) { return (RtlLeftChildAvl(RtlParentAvl(Node)) == Node); } FORCEINLINE BOOLEAN -RtlIsRightChildAvl(IN PRTL_BALANCED_LINKS Node) +MiIsRightChildAvl(IN PRTL_BALANCED_LINKS Node) { return (RtlRightChildAvl(RtlParentAvl(Node)) == Node); } FORCEINLINE VOID -RtlInsertAsLeftChildAvl(IN PRTL_BALANCED_LINKS Parent, +MiInsertAsLeftChildAvl(IN PRTL_BALANCED_LINKS Parent, IN PRTL_BALANCED_LINKS Node) { Parent->LeftChild = Node; @@ -136,7 +150,7 @@ RtlInsertAsLeftChildAvl(IN PRTL_BALANCED_LINKS Parent, FORCEINLINE VOID -RtlInsertAsRightChildAvl(IN PRTL_BALANCED_LINKS Parent, +MiInsertAsRightChildAvl(IN PRTL_BALANCED_LINKS Parent, IN PRTL_BALANCED_LINKS Node) { Parent->RightChild = Node; -- 2.17.1