For React Native.
From: Zhiyi Zhang zzhang@codeweavers.com
--- dlls/ntdll/ntdll.spec | 2 +- dlls/ntdll/rtl.c | 99 +++++++++++++++++++++++++++++ dlls/ntoskrnl.exe/ntoskrnl.exe.spec | 2 +- include/ddk/ntddk.h | 1 + 4 files changed, 102 insertions(+), 2 deletions(-)
diff --git a/dlls/ntdll/ntdll.spec b/dlls/ntdll/ntdll.spec index b4d9b6969f8..ffa68f7a3f6 100644 --- a/dlls/ntdll/ntdll.spec +++ b/dlls/ntdll/ntdll.spec @@ -1043,7 +1043,7 @@ @ stdcall RtlSizeHeap(long long ptr) @ stdcall RtlSleepConditionVariableCS(ptr ptr ptr) @ stdcall RtlSleepConditionVariableSRW(ptr ptr ptr long) -@ stub RtlSplay +@ stdcall RtlSplay(ptr) @ stub RtlStartRXact # @ stub RtlStatMemoryStream @ stdcall RtlStringFromGUID(ptr ptr) diff --git a/dlls/ntdll/rtl.c b/dlls/ntdll/rtl.c index 575579a551e..3e9c9f9db5f 100644 --- a/dlls/ntdll/rtl.c +++ b/dlls/ntdll/rtl.c @@ -236,6 +236,58 @@ NTSTATUS WINAPI RtlResetNtUserPfn(void) return STATUS_SUCCESS; }
+static void rtl_splay_left_rotate(RTL_SPLAY_LINKS *x) +{ + RTL_SPLAY_LINKS *y = x->RightChild; + + if (y) + { + x->RightChild = y->LeftChild; + if (y->LeftChild) + y->LeftChild->Parent = x; + + y->Parent = RtlIsRoot(x) ? y : x->Parent; + } + + if (!RtlIsRoot(x)) + { + if (RtlIsLeftChild(x)) + x->Parent->LeftChild = y; + else + x->Parent->RightChild = y; + } + + if (y) + y->LeftChild = x; + x->Parent = y; +} + +static void rtl_splay_right_rotate(RTL_SPLAY_LINKS *x) +{ + RTL_SPLAY_LINKS *y = x->LeftChild; + + if (y) + { + x->LeftChild = y->RightChild; + if (y->RightChild) + y->RightChild->Parent = x; + + y->Parent = RtlIsRoot(x) ? y : x->Parent; + } + + if (!RtlIsRoot(x)) + { + if (RtlIsLeftChild(x)) + x->Parent->LeftChild = y; + else + x->Parent->RightChild = y; + } + + if (y) + y->RightChild = x; + x->Parent = y; +} + /****************************************************************************** * RtlSubtreePredecessor [NTDLL.@] */ @@ -328,6 +380,53 @@ RTL_SPLAY_LINKS * WINAPI RtlRealSuccessor(RTL_SPLAY_LINKS *links) return NULL; }
+/****************************************************************************** + * RtlSplay [NTDLL.@] + */ +RTL_SPLAY_LINKS * WINAPI RtlSplay(RTL_SPLAY_LINKS *links) +{ + TRACE("(%p)\n", links); + + while (!RtlIsRoot(links)) + { + if (RtlIsRoot(links->Parent)) + { + /* Zig */ + if (RtlIsLeftChild(links)) + rtl_splay_right_rotate(links->Parent); + /* Zag */ + else + rtl_splay_left_rotate(links->Parent); + } + /* Zig-Zig */ + else if (RtlIsLeftChild(links->Parent) && RtlIsLeftChild(links)) + { + rtl_splay_right_rotate(links->Parent->Parent); + rtl_splay_right_rotate(links->Parent); + } + /* Zag-Zag */ + else if (RtlIsRightChild(links->Parent) && RtlIsRightChild(links)) + { + rtl_splay_left_rotate(links->Parent->Parent); + rtl_splay_left_rotate(links->Parent); + } + /* Zig-Zag */ + else if (RtlIsRightChild(links->Parent) && RtlIsLeftChild(links)) + { + rtl_splay_right_rotate(links->Parent); + rtl_splay_left_rotate(links->Parent); + } + /* Zag-Zig */ + else + { + rtl_splay_left_rotate(links->Parent); + rtl_splay_right_rotate(links->Parent); + } + } + + return links; +} + /****************************************************************************** * RtlInitializeGenericTable [NTDLL.@] */ diff --git a/dlls/ntoskrnl.exe/ntoskrnl.exe.spec b/dlls/ntoskrnl.exe/ntoskrnl.exe.spec index 46f11cc951b..b1b50d9d37a 100644 --- a/dlls/ntoskrnl.exe/ntoskrnl.exe.spec +++ b/dlls/ntoskrnl.exe/ntoskrnl.exe.spec @@ -1265,7 +1265,7 @@ @ stdcall RtlSetSaclSecurityDescriptor(ptr long ptr long) @ stdcall RtlSetTimeZoneInformation(ptr) @ stdcall RtlSizeHeap(long long ptr) -@ stub RtlSplay +@ stdcall RtlSplay(ptr) @ stdcall RtlStringFromGUID(ptr ptr) @ stdcall RtlSubAuthorityCountSid(ptr) @ stdcall RtlSubAuthoritySid(ptr long) diff --git a/include/ddk/ntddk.h b/include/ddk/ntddk.h index a7c0b1e44b5..3320d10cfa3 100644 --- a/include/ddk/ntddk.h +++ b/include/ddk/ntddk.h @@ -315,6 +315,7 @@ ULONG WINAPI RtlNumberGenericTableElementsAvl(PRTL_AVL_TABLE); BOOLEAN WINAPI RtlPrefixUnicodeString(const UNICODE_STRING*,const UNICODE_STRING*,BOOLEAN); PRTL_SPLAY_LINKS WINAPI RtlRealPredecessor(PRTL_SPLAY_LINKS); PRTL_SPLAY_LINKS WINAPI RtlRealSuccessor(PRTL_SPLAY_LINKS); +PRTL_SPLAY_LINKS WINAPI RtlSplay(PRTL_SPLAY_LINKS); PRTL_SPLAY_LINKS WINAPI RtlSubtreePredecessor(PRTL_SPLAY_LINKS); PRTL_SPLAY_LINKS WINAPI RtlSubtreeSuccessor(PRTL_SPLAY_LINKS); NTSTATUS WINAPI RtlUpcaseUnicodeString(UNICODE_STRING*,const UNICODE_STRING*,BOOLEAN);
From: Zhiyi Zhang zzhang@codeweavers.com
--- dlls/ntdll/tests/rtl.c | 239 +++++++++++++++++++++++++++++++++++++++++ 1 file changed, 239 insertions(+)
diff --git a/dlls/ntdll/tests/rtl.c b/dlls/ntdll/tests/rtl.c index 9abe0d2e9cc..cbf564fa513 100644 --- a/dlls/ntdll/tests/rtl.c +++ b/dlls/ntdll/tests/rtl.c @@ -125,6 +125,7 @@ static NTSTATUS (WINAPI *pRtlRetrieveNtUserPfn)( const UINT64 **client_procsA, static NTSTATUS (WINAPI *pRtlResetNtUserPfn)(void); static PRTL_SPLAY_LINKS (WINAPI *pRtlSubtreePredecessor)(PRTL_SPLAY_LINKS); static PRTL_SPLAY_LINKS (WINAPI *pRtlSubtreeSuccessor)(PRTL_SPLAY_LINKS); +static PRTL_SPLAY_LINKS (WINAPI *pRtlSplay)(PRTL_SPLAY_LINKS);
static HMODULE hkernel32 = 0; static BOOL (WINAPI *pIsWow64Process)(HANDLE, PBOOL); @@ -179,6 +180,7 @@ static void InitFunctionPtrs(void) pRtlResetNtUserPfn = (void *)GetProcAddress(hntdll, "RtlResetNtUserPfn"); pRtlSubtreePredecessor = (void *)GetProcAddress(hntdll, "RtlSubtreePredecessor"); pRtlSubtreeSuccessor = (void *)GetProcAddress(hntdll, "RtlSubtreeSuccessor"); + pRtlSplay = (void *)GetProcAddress(hntdll, "RtlSplay"); } hkernel32 = LoadLibraryA("kernel32.dll"); ok(hkernel32 != 0, "LoadLibrary failed\n"); @@ -4101,6 +4103,60 @@ static void init_splay_indices(RTL_SPLAY_LINKS *links, unsigned int links_count, } }
+#define expect_splay_indices(a, b, c, d) _expect_splay_indices(__LINE__, a, b, c, d) +static void _expect_splay_indices(int line, RTL_SPLAY_LINKS *links, RTL_SPLAY_LINKS *root, + const struct splay_index *indices, unsigned int index_count) +{ + const struct splay_index *index; + unsigned int i; + + ok_(__FILE__, line)(RtlIsRoot(root), "Got unexpected root node %d.\n", root ? (int)(root - links) : -1); + ok_(__FILE__, line)(root == &links[indices[0].parent_index], "Expected root %d, got %d.\n", + indices[0].parent_index, root ? (int)(root - links) : -1); + + for (i = 0; i < index_count; i++) + { + winetest_push_context("%d", i); + + index = &indices[i]; + if (index->left_index != -1) + { + ok_(__FILE__, line)(links[index->parent_index].LeftChild == &links[index->left_index], + "Node %d got unexpected left child %d.\n", index->parent_index, + links[index->parent_index].LeftChild ? + (int)(links[index->parent_index].LeftChild - links) : -1); + ok_(__FILE__, line)(links[index->left_index].Parent == &links[index->parent_index], + "Node %d got unexpected parent %d.\n", index->left_index, + (int)(links[index->left_index].Parent - links)); + } + else + { + ok_(__FILE__, line)(!links[index->parent_index].LeftChild, + "Node %d shouldn't have left child %d.\n", + index->parent_index, (int)(links[index->parent_index].LeftChild - links)); + } + + if (index->right_index != -1) + { + ok_(__FILE__, line)(links[index->parent_index].RightChild == &links[index->right_index], + "Node %d got unexpected right child %d.\n", index->parent_index, + links[index->parent_index].RightChild ? + (int)(links[index->parent_index].RightChild - links) : -1); + ok_(__FILE__, line)(links[index->right_index].Parent == &links[index->parent_index], + "Node %d got unexpected parent %d.\n", index->right_index, + (int)(links[index->right_index].Parent - links)); + } + else + { + ok_(__FILE__, line)(!links[index->parent_index].RightChild, + "Node %d shouldn't have right child %d.\n", + index->parent_index, (int)(links[index->parent_index].RightChild - links)); + } + + winetest_pop_context(); + } +} + static void test_RtlSubtreePredecessor(void) { /* 3 @@ -4261,6 +4317,188 @@ static void test_RtlRealSuccessor(void) } }
+static void test_RtlSplay(void) +{ + /* 3 + * / \ + * 1 5 + * / \ / \ + * 0 2 4 6 + */ + static const struct splay_index splay_indices[] = + { + {3, 1, 5}, + {1, 0, 2}, + {5, 4, 6}, + {0, -1, -1}, + {2, -1, -1}, + {4, -1, -1}, + {6, -1, -1}, + }; + /* 0 + * \ + * 1 + * \ + * 3 + * / \ + * 2 5 + * / \ + * 4 6 + */ + static const struct splay_index splay0[] = + { + {0, -1, 1}, + {1, -1, 3}, + {3, 2, 5}, + {5, 4, 6}, + {2, -1, -1}, + {4, -1, -1}, + {6, -1, -1}, + }; + /* 1 + * / \ + * 0 3 + * / \ + * 2 5 + * / \ + * 4 6 + */ + static const struct splay_index splay1[] = + { + {1, 0, 3}, + {3, 2, 5}, + {5, 4, 6}, + {0, -1, -1}, + {2, -1, -1}, + {4, -1, -1}, + {6, -1, -1}, + }; + /* 2 + * / \ + * 1 3 + * / \ + * 0 5 + * / \ + * 4 6 + */ + static const struct splay_index splay2[] = + { + {2, 1, 3}, + {1, 0, -1}, + {3, -1, 5}, + {5, 4, 6}, + {0, -1, -1}, + {4, -1, -1}, + {6, -1, -1}, + }; + /* 3 + * / \ + * 1 5 + * / \ / \ + * 0 2 4 6 + */ + static const struct splay_index splay3[] = + { + {3, 1, 5}, + {1, 0, 2}, + {5, 4, 6}, + {0, -1, -1}, + {2, -1, -1}, + {4, -1, -1}, + {6, -1, -1}, + }; + /* 4 + * / \ + * 3 5 + * / \ + * 1 6 + * / \ + * 0 2 + */ + static const struct splay_index splay4[] = + { + {4, 3, 5}, + {3, 1, -1}, + {5, -1, 6}, + {1, 0, 2}, + {0, -1, -1}, + {2, -1, -1}, + {6, -1, -1}, + }; + /* 5 + * / \ + * 3 6 + * / \ + * 1 4 + * / \ + * 0 2 + */ + static const struct splay_index splay5[] = + { + {5, 3, 6}, + {3, 1, 4}, + {1, 0, 2}, + {0, -1, -1}, + {2, -1, -1}, + {4, -1, -1}, + {6, -1, -1}, + }; + /* 6 + * / + * 5 + * / + * 3 + * / \ + * 1 4 + * / \ + * 0 2 + */ + static const struct splay_index splay6[] = + { + {6, 5, -1}, + {5, 3, -1}, + {3, 1, 4}, + {1, 0, 2}, + {0, -1, -1}, + {2, -1, -1}, + {4, -1, -1}, + }; + RTL_SPLAY_LINKS links[7], *root; + static const struct + { + const struct splay_index *indices; + unsigned int indices_count; + } + expected_indices[] = + { + {splay0, ARRAY_SIZE(splay0)}, + {splay1, ARRAY_SIZE(splay1)}, + {splay2, ARRAY_SIZE(splay2)}, + {splay3, ARRAY_SIZE(splay3)}, + {splay4, ARRAY_SIZE(splay4)}, + {splay5, ARRAY_SIZE(splay5)}, + {splay6, ARRAY_SIZE(splay6)}, + }; + unsigned int i; + + if (!pRtlSplay) + { + win_skip("RtlSplay is unavailable.\n"); + return; + } + + for (i = 0; i < ARRAY_SIZE(expected_indices); i++) + { + winetest_push_context("%d", i); + + init_splay_indices(links, ARRAY_SIZE(links), splay_indices, ARRAY_SIZE(splay_indices)); + root = pRtlSplay(&links[i]); + expect_splay_indices(links, root, expected_indices[i].indices, expected_indices[i].indices_count); + + winetest_pop_context(); + } +} + START_TEST(rtl) { InitFunctionPtrs(); @@ -4317,4 +4555,5 @@ START_TEST(rtl) test_RtlSubtreeSuccessor(); test_RtlRealPredecessor(); test_RtlRealSuccessor(); + test_RtlSplay(); }
From: Zhiyi Zhang zzhang@codeweavers.com
--- 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);
From: Zhiyi Zhang zzhang@codeweavers.com
--- dlls/ntdll/tests/rtl.c | 168 +++++++++++++++++++++++++++++++++++++++++ 1 file changed, 168 insertions(+)
diff --git a/dlls/ntdll/tests/rtl.c b/dlls/ntdll/tests/rtl.c index cbf564fa513..2f7a1d4cdc0 100644 --- a/dlls/ntdll/tests/rtl.c +++ b/dlls/ntdll/tests/rtl.c @@ -89,6 +89,7 @@ __ASM_STDCALL_FUNC( wrap_fastcall_func1, 8,
/* Function ptrs for ntdll calls */ static HMODULE hntdll = 0; +static void (WINAPI *pRtlDeleteNoSplay)(PRTL_SPLAY_LINKS, PRTL_SPLAY_LINKS *); static VOID (WINAPI *pRtlMoveMemory)(LPVOID,LPCVOID,SIZE_T); static VOID (WINAPI *pRtlFillMemory)(LPVOID,SIZE_T,BYTE); static VOID (WINAPI *pRtlFillMemoryUlong)(LPVOID,SIZE_T,ULONG); @@ -148,6 +149,7 @@ static void InitFunctionPtrs(void) hntdll = LoadLibraryA("ntdll.dll"); ok(hntdll != 0, "LoadLibrary failed\n"); if (hntdll) { + pRtlDeleteNoSplay = (void *)GetProcAddress(hntdll, "RtlDeleteNoSplay"); pRtlMoveMemory = (void *)GetProcAddress(hntdll, "RtlMoveMemory"); pRtlFillMemory = (void *)GetProcAddress(hntdll, "RtlFillMemory"); pRtlFillMemoryUlong = (void *)GetProcAddress(hntdll, "RtlFillMemoryUlong"); @@ -4499,6 +4501,171 @@ static void test_RtlSplay(void) } }
+static void test_RtlDeleteNoSplay(void) +{ + /* 3 + * / \ + * 1 5 + * / \ / \ + * 0 2 4 6 + */ + static const struct splay_index splay_indices[] = + { + {3, 1, 5}, + {1, 0, 2}, + {5, 4, 6}, + {0, -1, -1}, + {2, -1, -1}, + {4, -1, -1}, + {6, -1, -1}, + }; + /* 3 + * / \ + * 1 5 + * \ / \ + * 2 4 6 + */ + static const struct splay_index delete0[] = + { + {3, 1, 5}, + {1, -1, 2}, + {5, 4, 6}, + {2, -1, -1}, + {4, -1, -1}, + {6, -1, -1}, + }; + /* 3 + * / \ + * 0 5 + * \ / \ + * 2 4 6 + */ + static const struct splay_index delete1[] = + { + {3, 0, 5}, + {0, -1, 2}, + {5, 4, 6}, + {2, -1, -1}, + {4, -1, -1}, + {6, -1, -1}, + }; + /* 3 + * / \ + * 1 5 + * / / \ + * 0 4 6 + */ + static const struct splay_index delete2[] = + { + {3, 1, 5}, + {1, 0, -1}, + {5, 4, 6}, + {0, -1, -1}, + {4, -1, -1}, + {6, -1, -1}, + }; + /* 2 + * / \ + * 1 5 + * / / \ + * 0 4 6 + */ + static const struct splay_index delete3[] = + { + {2, 1, 5}, + {1, 0, -1}, + {5, 4, 6}, + {0, -1, -1}, + {4, -1, -1}, + {6, -1, -1}, + }; + /* 3 + * / \ + * 1 5 + * / \ \ + * 0 2 6 + */ + static const struct splay_index delete4[] = + { + {3, 1, 5}, + {1, 0, 2}, + {5, -1, 6}, + {0, -1, -1}, + {2, -1, -1}, + {6, -1, -1}, + }; + /* 3 + * / \ + * 1 4 + * / \ \ + * 0 2 6 + */ + static const struct splay_index delete5[] = + { + {3, 1, 4}, + {1, 0, 2}, + {4, -1, 6}, + {0, -1, -1}, + {2, -1, -1}, + {6, -1, -1}, + }; + /* 3 + * / \ + * 1 5 + * / \ / + * 0 2 4 + */ + static const struct splay_index delete6[] = + { + {3, 1, 5}, + {1, 0, 2}, + {5, 4, -1}, + {0, -1, -1}, + {2, -1, -1}, + {4, -1, -1}, + }; + RTL_SPLAY_LINKS links[7], *root; + static const struct + { + const struct splay_index *indices; + unsigned int index_count; + } + expected_indices[] = + { + {delete0, ARRAY_SIZE(delete0)}, + {delete1, ARRAY_SIZE(delete1)}, + {delete2, ARRAY_SIZE(delete2)}, + {delete3, ARRAY_SIZE(delete3)}, + {delete4, ARRAY_SIZE(delete4)}, + {delete5, ARRAY_SIZE(delete5)}, + {delete6, ARRAY_SIZE(delete6)}, + }; + unsigned int i; + + if (!pRtlDeleteNoSplay) + { + win_skip("RtlDeleteNoSplay is unavailable.\n"); + return; + } + + for (i = 0; i < ARRAY_SIZE(expected_indices); i++) + { + winetest_push_context("%d", i); + + init_splay_indices(links, ARRAY_SIZE(links), splay_indices, ARRAY_SIZE(splay_indices)); + root = &links[expected_indices[i].indices[0].parent_index]; + pRtlDeleteNoSplay(&links[i], &root); + expect_splay_indices(links, root, expected_indices[i].indices, expected_indices[i].index_count); + + winetest_pop_context(); + } + + /* Test that root should be NULL when the splay tree is empty */ + RtlInitializeSplayLinks(&links[0]); + pRtlDeleteNoSplay(&links[0], &root); + ok(root == NULL, "Got unexpected root.\n"); +} + START_TEST(rtl) { InitFunctionPtrs(); @@ -4556,4 +4723,5 @@ START_TEST(rtl) test_RtlRealPredecessor(); test_RtlRealSuccessor(); test_RtlSplay(); + test_RtlDeleteNoSplay(); }
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*);
From: Zhiyi Zhang zzhang@codeweavers.com
--- dlls/ntdll/tests/rtl.c | 181 +++++++++++++++++++++++++++++++++++++++++ 1 file changed, 181 insertions(+)
diff --git a/dlls/ntdll/tests/rtl.c b/dlls/ntdll/tests/rtl.c index 2f7a1d4cdc0..fa887421233 100644 --- a/dlls/ntdll/tests/rtl.c +++ b/dlls/ntdll/tests/rtl.c @@ -89,6 +89,7 @@ __ASM_STDCALL_FUNC( wrap_fastcall_func1, 8,
/* Function ptrs for ntdll calls */ static HMODULE hntdll = 0; +static PRTL_SPLAY_LINKS (WINAPI *pRtlDelete)(PRTL_SPLAY_LINKS); static void (WINAPI *pRtlDeleteNoSplay)(PRTL_SPLAY_LINKS, PRTL_SPLAY_LINKS *); static VOID (WINAPI *pRtlMoveMemory)(LPVOID,LPCVOID,SIZE_T); static VOID (WINAPI *pRtlFillMemory)(LPVOID,SIZE_T,BYTE); @@ -149,6 +150,7 @@ static void InitFunctionPtrs(void) hntdll = LoadLibraryA("ntdll.dll"); ok(hntdll != 0, "LoadLibrary failed\n"); if (hntdll) { + pRtlDelete = (void *)GetProcAddress(hntdll, "RtlDelete"); pRtlDeleteNoSplay = (void *)GetProcAddress(hntdll, "RtlDeleteNoSplay"); pRtlMoveMemory = (void *)GetProcAddress(hntdll, "RtlMoveMemory"); pRtlFillMemory = (void *)GetProcAddress(hntdll, "RtlFillMemory"); @@ -4666,6 +4668,184 @@ static void test_RtlDeleteNoSplay(void) ok(root == NULL, "Got unexpected root.\n"); }
+static void test_RtlDelete(void) +{ + /* 3 + * / \ + * 1 5 + * / \ / \ + * 0 2 4 6 + */ + static const struct splay_index splay_indices[] = + { + {3, 1, 5}, + {1, 0, 2}, + {5, 4, 6}, + {0, -1, -1}, + {2, -1, -1}, + {4, -1, -1}, + {6, -1, -1}, + }; + /* 1 + * \ + * 3 + * / \ + * 2 5 + * / \ + * 4 6 + */ + static const struct splay_index delete0[] = + { + {1, -1, 3}, + {3, 2, 5}, + {5, 4, 6}, + {2, -1, -1}, + {4, -1, -1}, + {6, -1, -1}, + }; + /* 0 + * \ + * 3 + * / \ + * 2 5 + * / \ + * 4 6 + */ + static const struct splay_index delete1[] = + { + {0, -1, 3}, + {3, 2, 5}, + {5, 4, 6}, + {2, -1, -1}, + {4, -1, -1}, + {6, -1, -1}, + }; + /* 1 + * / \ + * 0 3 + * \ + * 5 + * / \ + * 4 6 + */ + static const struct splay_index delete2[] = + { + {1, 0, 3}, + {3, -1, 5}, + {5, 4, 6}, + {0, -1, -1}, + {4, -1, -1}, + {6, -1, -1}, + }; + /* 1 + * / \ + * 0 2 + * \ + * 5 + * / \ + * 4 6 + */ + static const struct splay_index delete3[] = + { + {1, 0, 2}, + {2, -1, 5}, + {5, 4, 6}, + {0, -1, -1}, + {4, -1, -1}, + {6, -1, -1}, + }; + /* 5 + * / \ + * 3 6 + * / + * 1 + * / \ + * 0 2 + */ + static const struct splay_index delete4[] = + { + {5, 3, 6}, + {3, 1, -1}, + {1, 0, 2}, + {0, -1, -1}, + {2, -1, -1}, + {6, -1, -1}, + }; + /* 4 + * / \ + * 3 6 + * / + * 1 + * / \ + * 0 2 + */ + static const struct splay_index delete5[] = + { + {4, 3, 6}, + {3, 1, -1}, + {1, 0, 2}, + {0, -1, -1}, + {2, -1, -1}, + {6, -1, -1}, + }; + /* 5 + * / + * 3 + * / \ + * 1 4 + * / \ + * 0 2 + */ + static const struct splay_index delete6[] = + { + {5, 3, -1}, + {3, 1, 4}, + {1, 0, 2}, + {0, -1, -1}, + {2, -1, -1}, + {4, -1, -1}, + }; + RTL_SPLAY_LINKS links[7], *root; + static const struct + { + const struct splay_index *indices; + unsigned int index_count; + } + expected_indices[] = + { + {delete0, ARRAY_SIZE(delete0)}, + {delete1, ARRAY_SIZE(delete1)}, + {delete2, ARRAY_SIZE(delete2)}, + {delete3, ARRAY_SIZE(delete3)}, + {delete4, ARRAY_SIZE(delete4)}, + {delete5, ARRAY_SIZE(delete5)}, + {delete6, ARRAY_SIZE(delete6)}, + }; + unsigned int i; + + if (!pRtlDelete) + { + win_skip("RtlDelete is unavailable.\n"); + return; + } + for (i = 0; i < ARRAY_SIZE(expected_indices); i++) + { + winetest_push_context("%d", i); + + init_splay_indices(links, ARRAY_SIZE(links), splay_indices, ARRAY_SIZE(splay_indices)); + + root = pRtlDelete(&links[i]); + expect_splay_indices(links, root, expected_indices[i].indices, expected_indices[i].index_count); + + winetest_pop_context(); + } + + /* Test that root should be NULL when the splay tree is empty */ + RtlInitializeSplayLinks(&links[0]); + root = pRtlDelete(&links[0]); + ok(root == NULL, "Got unexpected root.\n"); +} + START_TEST(rtl) { InitFunctionPtrs(); @@ -4724,4 +4904,5 @@ START_TEST(rtl) test_RtlRealSuccessor(); test_RtlSplay(); test_RtlDeleteNoSplay(); + test_RtlDelete(); }
Hi,
It looks like your patch introduced the new failures shown below. Please investigate and fix them before resubmitting your patch. If they are not new, fixing them anyway would help a lot. Otherwise please ask for the known failures list to be updated.
The tests also ran into some preexisting test failures. If you know how to fix them that would be helpful. See the TestBot job for the details:
The full results can be found at: https://testbot.winehq.org/JobDetails.pl?Key=151256
Your paranoid android.
=== debian11b (64 bit WoW report) ===
user32: input.c:4306: Test succeeded inside todo block: button_down_hwnd_todo 1: got MSG_TEST_WIN hwnd 0000000000AB00F0, msg WM_LBUTTONDOWN, wparam 0x1, lparam 0x320032
-
Marvin -
Zhiyi Zhang -
Zhiyi Zhang (＠zhiyi)