From: Zhiyi Zhang zzhang@codeweavers.com
--- dlls/ntdll/ntdll.spec | 2 +- dlls/ntdll/rtl.c | 54 +++++++++++++++++++++++++++++ dlls/ntoskrnl.exe/ntoskrnl.exe.spec | 2 +- include/ddk/ntddk.h | 1 + 4 files changed, 57 insertions(+), 2 deletions(-)
diff --git a/dlls/ntdll/ntdll.spec b/dlls/ntdll/ntdll.spec index c428a1fbfe9..ff601a1cd22 100644 --- a/dlls/ntdll/ntdll.spec +++ b/dlls/ntdll/ntdll.spec @@ -610,7 +610,7 @@ @ stdcall RtlDecompressBuffer(long ptr long ptr long ptr) @ stdcall RtlDecompressFragment(long ptr long ptr long long ptr ptr) @ stdcall RtlDefaultNpAcl(ptr) -@ stub RtlDelete +@ stdcall RtlDelete(ptr) @ stdcall RtlDeleteAce(ptr long) @ stdcall RtlDeleteAtomFromAtomTable(ptr long) @ stdcall RtlDeleteCriticalSection(ptr) diff --git a/dlls/ntdll/rtl.c b/dlls/ntdll/rtl.c index 139a55d0c5d..8a77b321797 100644 --- a/dlls/ntdll/rtl.c +++ b/dlls/ntdll/rtl.c @@ -472,6 +472,60 @@ void WINAPI RtlDeleteNoSplay(RTL_SPLAY_LINKS *links, RTL_SPLAY_LINKS **root) } }
+/****************************************************************************** + * RtlDelete [NTDLL.@] + */ +RTL_SPLAY_LINKS * WINAPI RtlDelete(RTL_SPLAY_LINKS *links) +{ + RTL_SPLAY_LINKS *root, *to_splay; + + TRACE("(%p)\n", links); + + if (RtlIsRoot(links) && !RtlLeftChild(links) && !RtlRightChild(links)) + { + return NULL; + } + else if (!links->LeftChild) + { + rtl_splay_replace(links, links->RightChild, &root); + if (RtlIsRoot(links)) + return links->RightChild; + + to_splay = links->Parent; + } + else if (!links->RightChild) + { + rtl_splay_replace(links, links->LeftChild, &root); + if (RtlIsRoot(links)) + return links->LeftChild; + + to_splay = links->Parent; + } + else + { + RTL_SPLAY_LINKS *predecessor = RtlSubtreePredecessor(links); + if (predecessor->Parent != links) + { + rtl_splay_replace(predecessor, predecessor->LeftChild, &root); + RtlInsertAsLeftChild(predecessor, links->LeftChild); + /* Delete operation first swap the value of node to delete and that of the predecessor + * and then delete the predecessor instead. Finally, the parent of the actual deleted + * node, which is the predecessor, is splayed afterwards */ + to_splay = predecessor->Parent; + } + else + { + /* links is the parent of predecessor. So after swapping, the parent of links is in + * fact the predecessor. So predecessor gets splayed */ + to_splay = predecessor; + } + rtl_splay_replace(links, predecessor, &root); + RtlInsertAsRightChild(predecessor, links->RightChild); + } + + return RtlSplay(to_splay); +} + /****************************************************************************** * RtlInitializeGenericTable [NTDLL.@] */ diff --git a/dlls/ntoskrnl.exe/ntoskrnl.exe.spec b/dlls/ntoskrnl.exe/ntoskrnl.exe.spec index 53253a08653..12382313af2 100644 --- a/dlls/ntoskrnl.exe/ntoskrnl.exe.spec +++ b/dlls/ntoskrnl.exe/ntoskrnl.exe.spec @@ -1051,7 +1051,7 @@ @ stdcall RtlDecompressBuffer(long ptr long ptr long ptr) @ stub RtlDecompressChunks @ stdcall RtlDecompressFragment(long ptr long ptr long long ptr ptr) -@ stub RtlDelete +@ stdcall RtlDelete(ptr) @ stdcall RtlDeleteAce(ptr long) @ stdcall RtlDeleteAtomFromAtomTable(ptr long) @ stub RtlDeleteElementGenericTable diff --git a/include/ddk/ntddk.h b/include/ddk/ntddk.h index 4084d913025..33cb709d172 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*); +PRTL_SPLAY_LINKS WINAPI RtlDelete(PRTL_SPLAY_LINKS); void WINAPI RtlDeleteNoSplay(PRTL_SPLAY_LINKS,PRTL_SPLAY_LINKS *); void * WINAPI RtlEnumerateGenericTableWithoutSplaying(PRTL_GENERIC_TABLE,PVOID*); void * WINAPI RtlEnumerateGenericTableWithoutSplayingAvl(PRTL_AVL_TABLE,PVOID*);