[PATCH 3/6] ntdll: Implement RtlDeleteNoSplay().

[Zhiyi Zhang]

From: Zhiyi Zhang

---
 dlls/ntdll/ntdll.spec               |  2 +-
 dlls/ntdll/rtl.c                    | 45 +++++++++++++++++++++++++++++
 dlls/ntoskrnl.exe/ntoskrnl.exe.spec |  2 +-
 include/ddk/ntddk.h                 |  1 +
 4 files changed, 48 insertions(+), 2 deletions(-)

diff --git a/dlls/ntdll/ntdll.spec b/dlls/ntdll/ntdll.spec
index ffa68f7a3f6..c428a1fbfe9 100644
--- a/dlls/ntdll/ntdll.spec
+++ b/dlls/ntdll/ntdll.spec
@@ -618,7 +618,7 @@
 @ stub RtlDeleteElementGenericTable
 @ stub RtlDeleteElementGenericTableAvl
 @ cdecl -arch=!i386 RtlDeleteFunctionTable(ptr)
-@ stub RtlDeleteNoSplay
+@ stdcall RtlDeleteNoSplay(ptr ptr)
 @ stub RtlDeleteOwnersRanges
 @ stub RtlDeleteRange
 @ stdcall RtlDeleteRegistryValue(long ptr wstr)
diff --git a/dlls/ntdll/rtl.c b/dlls/ntdll/rtl.c
index 3e9c9f9db5f..139a55d0c5d 100644
--- a/dlls/ntdll/rtl.c
+++ b/dlls/ntdll/rtl.c
@@ -236,6 +236,19 @@ NTSTATUS WINAPI RtlResetNtUserPfn(void)
     return STATUS_SUCCESS;
 }

+static void rtl_splay_replace(RTL_SPLAY_LINKS *x, RTL_SPLAY_LINKS *y, RTL_SPLAY_LINKS **root)
+{
+    if (RtlIsRoot(x))
+        *root = y;
+    else if (RtlIsLeftChild(x))
+        x->Parent->LeftChild = y;
+    else
+        x->Parent->RightChild = y;
+
+    if (y)
+        y->Parent = RtlIsRoot(x) ? y : x->Parent;
+}
+
 static void rtl_splay_left_rotate(RTL_SPLAY_LINKS *x)
 {
     RTL_SPLAY_LINKS *y = x->RightChild;
@@ -427,6 +440,38 @@ RTL_SPLAY_LINKS * WINAPI RtlSplay(RTL_SPLAY_LINKS *links)
     return links;
 }

+/******************************************************************************
+ *  RtlDeleteNoSplay           [NTDLL.@]
+ */
+void WINAPI RtlDeleteNoSplay(RTL_SPLAY_LINKS *links, RTL_SPLAY_LINKS **root)
+{
+    TRACE("(%p, %p)\n", links, root);
+
+    if (RtlIsRoot(links) && !RtlLeftChild(links) && !RtlRightChild(links))
+    {
+        *root = NULL;
+    }
+    else  if (!links->LeftChild)
+    {
+        rtl_splay_replace(links, links->RightChild, root);
+    }
+    else if (!links->RightChild)
+    {
+        rtl_splay_replace(links, links->LeftChild, root);
+    }
+    else
+    {
+        RTL_SPLAY_LINKS *predecessor = RtlSubtreePredecessor(links);
+        if (predecessor->Parent != links)
+        {
+            rtl_splay_replace(predecessor, predecessor->LeftChild, root);
+            RtlInsertAsLeftChild(predecessor, links->LeftChild);
+        }
+        rtl_splay_replace(links, predecessor, root);
+        RtlInsertAsRightChild(predecessor, links->RightChild);
+    }
+}
+
 /******************************************************************************
  *  RtlInitializeGenericTable           [NTDLL.@]
  */
diff --git a/dlls/ntoskrnl.exe/ntoskrnl.exe.spec b/dlls/ntoskrnl.exe/ntoskrnl.exe.spec
index b1b50d9d37a..53253a08653 100644
--- a/dlls/ntoskrnl.exe/ntoskrnl.exe.spec
+++ b/dlls/ntoskrnl.exe/ntoskrnl.exe.spec
@@ -1056,7 +1056,7 @@
 @ stdcall RtlDeleteAtomFromAtomTable(ptr long)
 @ stub RtlDeleteElementGenericTable
 @ stub RtlDeleteElementGenericTableAvl
-@ stub RtlDeleteNoSplay
+@ stdcall RtlDeleteNoSplay(ptr ptr)
 @ stub RtlDeleteOwnersRanges
 @ stub RtlDeleteRange
 @ stdcall RtlDeleteRegistryValue(long ptr ptr)
diff --git a/include/ddk/ntddk.h b/include/ddk/ntddk.h
index 3320d10cfa3..4084d913025 100644
--- a/include/ddk/ntddk.h
+++ b/include/ddk/ntddk.h
@@ -300,6 +300,7 @@ NTSTATUS  WINAPI PsSetLoadImageNotifyRoutine(PLOAD_IMAGE_NOTIFY_ROUTINE);
 NTSTATUS  WINAPI PsSetLoadImageNotifyRoutineEx(PLOAD_IMAGE_NOTIFY_ROUTINE,ULONG_PTR);
 LONG      WINAPI RtlCompareString(const STRING*,const STRING*,BOOLEAN);
 void      WINAPI RtlCopyString(STRING*,const STRING*);
+void      WINAPI RtlDeleteNoSplay(PRTL_SPLAY_LINKS,PRTL_SPLAY_LINKS *);
 void *    WINAPI RtlEnumerateGenericTableWithoutSplaying(PRTL_GENERIC_TABLE,PVOID*);
 void *    WINAPI RtlEnumerateGenericTableWithoutSplayingAvl(PRTL_AVL_TABLE,PVOID*);
 BOOLEAN   WINAPI RtlEqualString(const STRING*,const STRING*,BOOLEAN);