[ros-diffs] [arty] 53015: [RTL] Implemenet SwapSplayLinks, return 'NewElement' correctly when inserting. Thanks to Alex Ionescu for helping out with this patch.
arty at svn.reactos.org
arty at svn.reactos.org
Mon Aug 1 03:23:54 UTC 2011
Author: arty
Date: Mon Aug 1 03:23:53 2011
New Revision: 53015
URL: http://svn.reactos.org/svn/reactos?rev=53015&view=rev
Log:
[RTL]
Implemenet SwapSplayLinks, return 'NewElement' correctly when inserting.
Thanks to Alex Ionescu for helping out with this patch.
Modified:
trunk/reactos/lib/rtl/generictable.c
trunk/reactos/lib/rtl/splaytree.c
Modified: trunk/reactos/lib/rtl/generictable.c
URL: http://svn.reactos.org/svn/reactos/trunk/reactos/lib/rtl/generictable.c?rev=53015&r1=53014&r2=53015&view=diff
==============================================================================
--- trunk/reactos/lib/rtl/generictable.c [iso-8859-1] (original)
+++ trunk/reactos/lib/rtl/generictable.c [iso-8859-1] Mon Aug 1 03:23:53 2011
@@ -213,7 +213,7 @@
Table->TableRoot = RtlSplay(NewNode);
/* Return status */
- if (NewElement) *NewElement = (SearchResult == TableFoundNode);
+ if (NewElement) *NewElement = (SearchResult != TableFoundNode);
/* Return pointer to user data */
return &((PTABLE_ENTRY_HEADER)NewNode)->UserData;
@@ -300,7 +300,7 @@
/* Get the splay links and table search result immediately */
Result = RtlpFindGenericTableNodeOrParent(Table, Buffer, &NodeOrParent);
- if ((Result == TableEmptyTree) || (Result != TableFoundNode))
+ if (Result != TableFoundNode)
{
/* Nothing to delete */
return FALSE;
Modified: trunk/reactos/lib/rtl/splaytree.c
URL: http://svn.reactos.org/svn/reactos/trunk/reactos/lib/rtl/splaytree.c?rev=53015&r1=53014&r2=53015&view=diff
==============================================================================
--- trunk/reactos/lib/rtl/splaytree.c [iso-8859-1] (original)
+++ trunk/reactos/lib/rtl/splaytree.c [iso-8859-1] Mon Aug 1 03:23:53 2011
@@ -13,13 +13,134 @@
#define NDEBUG
#include <debug.h>
+//#define VERIFY_SWAP_SPLAY_LINKS
+
/* FUNCTIONS ***************************************************************/
+static
+VOID
+FixupChildLinks(PRTL_SPLAY_LINKS Links, BOOLEAN Root, BOOLEAN LeftChild)
+{
+ if (RtlLeftChild(Links)) {
+ RtlInsertAsLeftChild(Links, RtlLeftChild(Links));
+ }
+ if (RtlRightChild(Links)) {
+ RtlInsertAsRightChild(Links, RtlRightChild(Links));
+ }
+ if (!Root) {
+ if (LeftChild) {
+ RtlInsertAsLeftChild(RtlParent(Links), Links);
+ } else {
+ RtlInsertAsRightChild(RtlParent(Links), Links);
+ }
+ }
+}
+
+/*
+
+Given the tree:
+ D
+ B F
+A C E G
+
+Swap(Q,S):
+
+Q S Q.P Q.L Q.R S.P S.L S.R
+A C S.P S.L S.R Q.P Q.L Q.R
+B A S S.L S.R Q.P Q Q.R
+B C S S.L S.R Q.P Q.L Q
+D A S.P S.L S.R S Q.L Q.R
+D B S S.L S.R S Q Q.R
+D F S S.L S.R S Q.L Q
+
+When Q is the immediate parent of S,
+ Set Q's parent to S, and the proper child ptr of S to Q
+When Q is the root,
+ Set S's parent to S
+ */
+
+static
VOID
SwapSplayLinks(PRTL_SPLAY_LINKS LinkA,
PRTL_SPLAY_LINKS LinkB)
{
- DPRINT1("UNIMPLEMENTED!\n");
+ if (RtlParent(LinkA) == LinkB || RtlIsRoot(LinkB)) {
+ PRTL_SPLAY_LINKS Tmp = LinkA;
+ LinkA = LinkB;
+ LinkB = Tmp;
+ }
+
+ {
+ RTL_SPLAY_LINKS Ta = *LinkA, Tb = *LinkB;
+ BOOLEAN RootA = RtlIsRoot(LinkA),
+ LeftA = RtlIsLeftChild(LinkA),
+ LeftB = RtlIsLeftChild(LinkB);
+ *LinkB = Ta; *LinkA = Tb;
+
+ // A was parent of B is a special case: A->Parent is now B
+ if (RtlParent(&Tb) == LinkA) {
+ if (!RootA) {
+ if (LeftA) {
+ RtlInsertAsLeftChild(RtlParent(&Ta), LinkB);
+ } else {
+ RtlInsertAsRightChild(RtlParent(&Ta), LinkB);
+ }
+ }
+ if (LeftB) {
+ RtlInsertAsLeftChild(LinkB, LinkA);
+ } else {
+ RtlInsertAsRightChild(LinkB, LinkA);
+ }
+ }
+
+ FixupChildLinks(LinkA, FALSE, LeftB);
+ FixupChildLinks(LinkB, RootA, LeftA);
+
+ // A was root is a special case: B->Parent is now B
+ if (RootA)
+ RtlParent(LinkB) = LinkB;
+
+#ifdef VERIFY_SWAP_SPLAY_LINKS
+ // Verify the distinct cases of node swap
+ if (RootA) {
+ if (RtlParent(&Tb) == LinkA) {
+ // LinkA = D, LinkB = B
+ // D B S S.L S.R S Q Q.R
+ ASSERT(RtlParent(LinkA) == LinkB);
+ ASSERT(RtlLeftChild(LinkA) == RtlLeftChild(&Tb));
+ ASSERT(RtlRightChild(LinkA) == RtlRightChild(&Tb));
+ ASSERT(RtlParent(LinkB) == LinkB);
+ ASSERT(RtlLeftChild(LinkB) == (LeftB ? LinkA : RtlLeftChild(&Ta)));
+ ASSERT(RtlRightChild(LinkB) == (LeftB ? RtlRightChild(&Ta) : LinkA));
+ } else {
+ // LinkA = D, LinkB = A
+ // D A S.P S.L S.R S Q.L Q.R
+ ASSERT(RtlParent(LinkA) == RtlParent(&Tb));
+ ASSERT(RtlLeftChild(LinkA) == RtlLeftChild(&Tb));
+ ASSERT(RtlRightChild(LinkA) == RtlRightChild(&Tb));
+ ASSERT(RtlParent(LinkB) == LinkB);
+ ASSERT(RtlLeftChild(LinkB) == RtlLeftChild(&Ta));
+ ASSERT(RtlRightChild(LinkB) == RtlRightChild(&Ta));
+ }
+ } else {
+ if (RtlParent(&Tb) == LinkA) {
+ // LinkA = B, LinkB = A
+ // B A S S.L S.R Q.P Q Q.R
+ ASSERT(RtlParent(LinkA) == LinkB);
+ ASSERT(RtlLeftChild(LinkA) == RtlLeftChild(&Tb));
+ ASSERT(RtlRightChild(LinkA) == RtlRightChild(&Tb));
+ ASSERT(RtlParent(LinkB) == RtlParent(&Ta));
+ ASSERT(RtlLeftChild(LinkB) == (LeftB ? LinkA : RtlLeftChild(&Ta)));
+ ASSERT(RtlRightChild(LinkB) == (LeftB ? RtlRightChild(&Ta) : LinkA));
+ } else {
+ // LinkA = A, LinkB = C
+ // A C S.P S.L S.R Q.P Q.L Q.R
+ ASSERT(!memcmp(LinkA, &Tb, sizeof(Tb)));
+ ASSERT(!memcmp(LinkB, &Ta, sizeof(Ta)));
+ }
+ }
+#endif
+ }
}
/*
@@ -513,6 +634,7 @@
}
/* Return the root entry */
+ ASSERT(RtlIsRoot(N));
return N;
}
More information about the Ros-diffs
mailing list