Author: hbelusca
Date: Sun Oct 19 00:05:18 2014
New Revision: 64820
URL: http://svn.reactos.org/svn/reactos?rev=64820&view=rev
Log:
Ok Arch, it's good to remove unuseful brackets, but don't exaggerate too much. Also check how the RtlInsertAsLeft/RightChild macros are defined. Since MS don't use the nice do { ... } while(0) for them, you cannot just use the if (blah) foo(); else bar(); to do the job, but you need the extra-brackets. And you cannot just change the macros definitions to not "break" headers compatibility (or... idiocies).
Modified:
trunk/reactos/lib/rtl/splaytree.c
Modified: trunk/reactos/lib/rtl/splaytree.c
URL: http://svn.reactos.org/svn/reactos/trunk/reactos/lib/rtl/splaytree.c?rev=64…
==============================================================================
--- trunk/reactos/lib/rtl/splaytree.c [iso-8859-1] (original)
+++ trunk/reactos/lib/rtl/splaytree.c [iso-8859-1] Sun Oct 19 00:05:18 2014
@@ -22,17 +22,25 @@
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);
+ }
}
}
@@ -86,15 +94,23 @@
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);
Author: hbelusca
Date: Sat Oct 18 23:51:35 2014
New Revision: 64818
URL: http://svn.reactos.org/svn/reactos?rev=64818&view=rev
Log:
[RTL]
Implement RtlDeleteNoSplay which is really just a copy/paste of RtlDelete, but without splaying the tree after deletion of the node. Needed by the filter driver fltmgr.sys. Dedicated to Mr. V ;)
Modified:
trunk/reactos/lib/rtl/splaytree.c
Modified: trunk/reactos/lib/rtl/splaytree.c
URL: http://svn.reactos.org/svn/reactos/trunk/reactos/lib/rtl/splaytree.c?rev=64…
==============================================================================
--- trunk/reactos/lib/rtl/splaytree.c [iso-8859-1] (original)
+++ trunk/reactos/lib/rtl/splaytree.c [iso-8859-1] Sat Oct 18 23:51:35 2014
@@ -154,17 +154,17 @@
N = Links;
/* Check if we have two children */
- if ((RtlLeftChild(N)) && (RtlRightChild(N)))
+ if (RtlLeftChild(N) && RtlRightChild(N))
{
/* Get the predecessor */
SP = RtlSubtreePredecessor(N);
- /* Swap it with N, this will guarantee that N will have only a child */
+ /* Swap it with N, this will guarantee that N will only have a child */
SwapSplayLinks(SP, N);
}
/* Check if we have no children */
- if (!(RtlLeftChild(N)) && !(RtlRightChild(N)))
+ if (!RtlLeftChild(N) && !RtlRightChild(N))
{
/* If we are also the root, then the tree is gone */
if (RtlIsRoot(N)) return NULL;
@@ -176,12 +176,12 @@
if (RtlIsLeftChild(N))
{
/* N was a left child, so erase its parent's left child link */
- RtlLeftChild(RtlParent(N)) = NULL;
+ RtlLeftChild(P) = NULL;
}
else
{
/* N was a right child, so erase its parent's right child link */
- RtlRightChild(RtlParent(N)) = NULL;
+ RtlRightChild(P) = NULL;
}
/* And finally splay the parent */
@@ -196,44 +196,130 @@
}
else
{
- /* We have a right child, get him instead */
+ /* We have a right child, get it instead */
C = RtlRightChild(N);
}
/* Check if we are the root entry */
if (RtlIsRoot(N))
{
- /* Our child is now root, return him */
- C->Parent = C;
+ /* Our child is now root, return it */
+ RtlParent(C) = C;
return C;
}
+
+ /* Get our parent */
+ P = RtlParent(N);
/* Find out who is referencing us and link to our child instead */
if (RtlIsLeftChild(N))
{
/* N was a left child, so set its parent's left child as our child */
- RtlLeftChild(RtlParent(N)) = C;
+ RtlLeftChild(P) = C;
}
else
{
/* N was a right child, so set its parent's right child as our child */
- RtlRightChild(RtlParent(N)) = C;
+ RtlRightChild(P) = C;
}
/* Finally, inherit our parent and splay the parent */
- C->Parent = N->Parent;
- return RtlSplay(RtlParent(C));
-}
-
-/*
-* @unimplemented
-*/
+ RtlParent(C) = P;
+ return RtlSplay(P);
+}
+
+/*
+ * @implemented
+ */
VOID
NTAPI
RtlDeleteNoSplay(PRTL_SPLAY_LINKS Links,
PRTL_SPLAY_LINKS *Root)
{
- UNIMPLEMENTED;
+ PRTL_SPLAY_LINKS N, P, C, SP;
+ N = Links;
+
+ /* Check if we have two children */
+ if (RtlLeftChild(N) && RtlRightChild(N))
+ {
+ /* Get the predecessor */
+ SP = RtlSubtreePredecessor(N);
+
+ /* If we are the root, the new root will be our predecessor after swapping */
+ if (RtlIsRoot(N)) *Root = SP;
+
+ /* Swap the predecessor with N, this will guarantee that N will only have a child */
+ SwapSplayLinks(SP, N);
+ }
+
+ /* Check if we have no children */
+ if (!RtlLeftChild(N) && !RtlRightChild(N))
+ {
+ /* If we are also the root, then the tree is gone */
+ if (RtlIsRoot(N))
+ {
+ *Root = NULL;
+ return;
+ }
+
+ /* Get our parent */
+ P = RtlParent(N);
+
+ /* Find out who is referencing us and delete the reference */
+ if (RtlIsLeftChild(N))
+ {
+ /* N was a left child, so erase its parent's left child link */
+ RtlLeftChild(P) = NULL;
+ }
+ else
+ {
+ /* N was a right child, so erase its parent's right child link */
+ RtlRightChild(P) = NULL;
+ }
+
+ /* We are done */
+ return;
+ }
+
+ /* If we got here, we have a child (not two: we swapped above!) */
+ if (RtlLeftChild(N))
+ {
+ /* We have a left child, so get it */
+ C = RtlLeftChild(N);
+ }
+ else
+ {
+ /* We have a right child, get it instead */
+ C = RtlRightChild(N);
+ }
+
+ /* Check if we are the root entry */
+ if (RtlIsRoot(N))
+ {
+ /* Our child is now root, return it */
+ RtlParent(C) = C;
+ *Root = C;
+ return;
+ }
+
+ /* Get our parent */
+ P = RtlParent(N);
+
+ /* Find out who is referencing us and link to our child instead */
+ if (RtlIsLeftChild(N))
+ {
+ /* N was a left child, so set its parent's left child as our child */
+ RtlLeftChild(P) = C;
+ }
+ else
+ {
+ /* N was a right child, so set its parent's right child as our child */
+ RtlRightChild(P) = C;
+ }
+
+ /* Finally, inherit our parent and we are done */
+ RtlParent(C) = P;
+ return;
}
/*