For React Native.
From: Zhiyi Zhang zzhang@codeweavers.com
--- include/ddk/ntddk.h | 26 ++++++++++++++++++++++++++ 1 file changed, 26 insertions(+)
diff --git a/include/ddk/ntddk.h b/include/ddk/ntddk.h index e9ca903715d..e6c9ca8d97f 100644 --- a/include/ddk/ntddk.h +++ b/include/ddk/ntddk.h @@ -166,6 +166,32 @@ typedef struct _RTL_SPLAY_LINKS struct _RTL_SPLAY_LINKS *RightChild; } RTL_SPLAY_LINKS, *PRTL_SPLAY_LINKS;
+FORCEINLINE void RtlInitializeSplayLinks(PRTL_SPLAY_LINKS links) +{ + links->Parent = links; + links->LeftChild = NULL; + links->RightChild = NULL; +} + +FORCEINLINE void RtlInsertAsLeftChild(PRTL_SPLAY_LINKS parent, PRTL_SPLAY_LINKS child) +{ + parent->LeftChild = child; + child->Parent = parent; +} + +FORCEINLINE void RtlInsertAsRightChild(PRTL_SPLAY_LINKS parent, PRTL_SPLAY_LINKS child) +{ + parent->RightChild = child; + child->Parent = parent; +} + +#define RtlParent(links) ((PRTL_SPLAY_LINKS)(links)->Parent) +#define RtlLeftChild(links) ((PRTL_SPLAY_LINKS)(links)->LeftChild) +#define RtlRightChild(links) ((PRTL_SPLAY_LINKS)(links)->RightChild) +#define RtlIsRoot(links) (RtlParent(links) == (PRTL_SPLAY_LINKS)(links)) +#define RtlIsLeftChild(links) (RtlLeftChild(RtlParent(links)) == (PRTL_SPLAY_LINKS)(links)) +#define RtlIsRightChild(links) (RtlRightChild(RtlParent(links)) == (PRTL_SPLAY_LINKS)(links)) + struct _RTL_GENERIC_TABLE;
typedef RTL_GENERIC_COMPARE_RESULTS (WINAPI *PRTL_GENERIC_COMPARE_ROUTINE)(struct _RTL_GENERIC_TABLE *, void *, void *);
From: Zhiyi Zhang zzhang@codeweavers.com
--- dlls/ntdll/ntdll.spec | 2 +- dlls/ntdll/rtl.c | 19 +++++++++++++++++++ dlls/ntoskrnl.exe/ntoskrnl.exe.spec | 2 +- include/ddk/ntddk.h | 1 + 4 files changed, 22 insertions(+), 2 deletions(-)
diff --git a/dlls/ntdll/ntdll.spec b/dlls/ntdll/ntdll.spec index 620d96a5992..97adfeb853a 100644 --- a/dlls/ntdll/ntdll.spec +++ b/dlls/ntdll/ntdll.spec @@ -1048,7 +1048,7 @@ @ stdcall RtlStringFromGUID(ptr ptr) @ stdcall RtlSubAuthorityCountSid(ptr) @ stdcall RtlSubAuthoritySid(ptr long) -@ stub RtlSubtreePredecessor +@ stdcall RtlSubtreePredecessor(ptr) @ stub RtlSubtreeSuccessor @ stdcall RtlSystemTimeToLocalTime(ptr ptr) @ stdcall RtlTimeFieldsToTime(ptr ptr) diff --git a/dlls/ntdll/rtl.c b/dlls/ntdll/rtl.c index 643d6f3ce49..d98edb8745e 100644 --- a/dlls/ntdll/rtl.c +++ b/dlls/ntdll/rtl.c @@ -7,6 +7,7 @@ * Copyright 1999 Alex Korobka * Copyright 2003 Thomas Mertes * Crc32 code Copyright 1986 Gary S. Brown (Public domain) + * Copyright 2025 Zhiyi Zhang for CodeWeavers * * This library is free software; you can redistribute it and/or * modify it under the terms of the GNU Lesser General Public @@ -235,6 +236,24 @@ NTSTATUS WINAPI RtlResetNtUserPfn(void) return STATUS_SUCCESS; }
+/****************************************************************************** + * RtlSubtreePredecessor [NTDLL.@] + */ +RTL_SPLAY_LINKS * WINAPI RtlSubtreePredecessor(RTL_SPLAY_LINKS *links) +{ + RTL_SPLAY_LINKS *child; + + TRACE("(%p)\n", links); + + child = RtlLeftChild(links); + if (!child) + return NULL; + + while (RtlRightChild(child)) + child = RtlRightChild(child); + + return child; +}
/****************************************************************************** * RtlInitializeGenericTable [NTDLL.@] diff --git a/dlls/ntoskrnl.exe/ntoskrnl.exe.spec b/dlls/ntoskrnl.exe/ntoskrnl.exe.spec index 276e166c4a9..2a86e4d100b 100644 --- a/dlls/ntoskrnl.exe/ntoskrnl.exe.spec +++ b/dlls/ntoskrnl.exe/ntoskrnl.exe.spec @@ -1269,7 +1269,7 @@ @ stdcall RtlStringFromGUID(ptr ptr) @ stdcall RtlSubAuthorityCountSid(ptr) @ stdcall RtlSubAuthoritySid(ptr long) -@ stub RtlSubtreePredecessor +@ stdcall RtlSubtreePredecessor(ptr) @ stub RtlSubtreeSuccessor @ stdcall RtlSystemTimeToLocalTime(ptr ptr) @ stub RtlTestBit diff --git a/include/ddk/ntddk.h b/include/ddk/ntddk.h index e6c9ca8d97f..cc642fa6c0f 100644 --- a/include/ddk/ntddk.h +++ b/include/ddk/ntddk.h @@ -313,6 +313,7 @@ void WINAPI RtlMapGenericMask(ACCESS_MASK*,const GENERIC_MAPPING*); ULONG WINAPI RtlNumberGenericTableElements(PRTL_GENERIC_TABLE); ULONG WINAPI RtlNumberGenericTableElementsAvl(PRTL_AVL_TABLE); BOOLEAN WINAPI RtlPrefixUnicodeString(const UNICODE_STRING*,const UNICODE_STRING*,BOOLEAN); +PRTL_SPLAY_LINKS WINAPI RtlSubtreePredecessor(PRTL_SPLAY_LINKS); NTSTATUS WINAPI RtlUpcaseUnicodeString(UNICODE_STRING*,const UNICODE_STRING*,BOOLEAN); char WINAPI RtlUpperChar(char); void WINAPI RtlUpperString(STRING*,const STRING*);
From: Zhiyi Zhang zzhang@codeweavers.com
--- dlls/ntdll/tests/rtl.c | 69 ++++++++++++++++++++++++++++++++++++++++++ 1 file changed, 69 insertions(+)
diff --git a/dlls/ntdll/tests/rtl.c b/dlls/ntdll/tests/rtl.c index c7c10a8f46c..9978c0d878e 100644 --- a/dlls/ntdll/tests/rtl.c +++ b/dlls/ntdll/tests/rtl.c @@ -1,6 +1,7 @@ /* Unit test suite for Rtl* API functions * * Copyright 2003 Thomas Mertes + * Copyright 2025 Zhiyi Zhang for CodeWeavers * * This library is free software; you can redistribute it and/or * modify it under the terms of the GNU Lesser General Public @@ -120,6 +121,7 @@ static NTSTATUS (WINAPI *pRtlRetrieveNtUserPfn)( const UINT64 **client_procsA, const UINT64 **client_procsW, const UINT64 **client_workers ); static NTSTATUS (WINAPI *pRtlResetNtUserPfn)(void); +static PRTL_SPLAY_LINKS (WINAPI *pRtlSubtreePredecessor)(PRTL_SPLAY_LINKS);
static HMODULE hkernel32 = 0; static BOOL (WINAPI *pIsWow64Process)(HANDLE, PBOOL); @@ -170,6 +172,7 @@ static void InitFunctionPtrs(void) pRtlInitializeNtUserPfn = (void *)GetProcAddress(hntdll, "RtlInitializeNtUserPfn"); pRtlRetrieveNtUserPfn = (void *)GetProcAddress(hntdll, "RtlRetrieveNtUserPfn"); pRtlResetNtUserPfn = (void *)GetProcAddress(hntdll, "RtlResetNtUserPfn"); + pRtlSubtreePredecessor = (void *)GetProcAddress(hntdll, "RtlSubtreePredecessor"); } hkernel32 = LoadLibraryA("kernel32.dll"); ok(hkernel32 != 0, "LoadLibrary failed\n"); @@ -4067,6 +4070,71 @@ static void test_user_procs(void) ok( !memcmp( ptrs, ptr_A, size_A ), "pointers changed by init\n" ); }
+struct splay_index +{ + int parent_index; + int left_index; + int right_index; +}; + +static void init_splay_indices(RTL_SPLAY_LINKS *links, unsigned int links_count, + const struct splay_index *indices, unsigned int index_count) +{ + const struct splay_index *index; + unsigned int i; + + for (i = 0; i < links_count; i++) + RtlInitializeSplayLinks(&links[i]); + for (i = 0; i < index_count; i++) + { + index = &indices[i]; + if (index->left_index != -1) + RtlInsertAsLeftChild(&links[index->parent_index], &links[index->left_index]); + if (index->right_index != -1) + RtlInsertAsRightChild(&links[index->parent_index], &links[index->right_index]); + } +} + +static void test_RtlSubtreePredecessor(void) +{ + /* 3 + * / \ + * 1 5 + * / \ / \ + * 0 2 4 6 + */ + static const struct splay_index splay_indices[] = + { + {3, 1, 5}, + {1, 0, 2}, + {5, 4, 6}, + }; + static const int expected_predecessors[] = {-1, 0, -1, 2, -1, 4, -1}; + RTL_SPLAY_LINKS links[7], *predecessor; + unsigned int i; + + if (!pRtlSubtreePredecessor) + { + win_skip("RtlSubtreePredecessor is unavailable.\n"); + return; + } + + init_splay_indices(links, ARRAY_SIZE(links), splay_indices, ARRAY_SIZE(splay_indices)); + for (i = 0; i < ARRAY_SIZE(expected_predecessors); i++) + { + winetest_push_context("%d", i); + + predecessor = pRtlSubtreePredecessor(&links[i]); + if (expected_predecessors[i] == -1) + ok(!predecessor, "Expected NULL, got unexpected %d.\n", (int)(predecessor - links)); + else + ok(predecessor == &links[expected_predecessors[i]], "Expected %d, got unexpected %d.\n", + expected_predecessors[i], (int)(predecessor ? predecessor - links : -1)); + + winetest_pop_context(); + } +} + START_TEST(rtl) { InitFunctionPtrs(); @@ -4119,4 +4187,5 @@ START_TEST(rtl) test_RtlConvertDeviceFamilyInfoToString(); test_rb_tree(); test_user_procs(); + test_RtlSubtreePredecessor(); }
From: Zhiyi Zhang zzhang@codeweavers.com
--- dlls/ntdll/ntdll.spec | 2 +- dlls/ntdll/rtl.c | 19 +++++++++++++++++++ dlls/ntoskrnl.exe/ntoskrnl.exe.spec | 2 +- include/ddk/ntddk.h | 1 + 4 files changed, 22 insertions(+), 2 deletions(-)
diff --git a/dlls/ntdll/ntdll.spec b/dlls/ntdll/ntdll.spec index 97adfeb853a..946be24ee85 100644 --- a/dlls/ntdll/ntdll.spec +++ b/dlls/ntdll/ntdll.spec @@ -1049,7 +1049,7 @@ @ stdcall RtlSubAuthorityCountSid(ptr) @ stdcall RtlSubAuthoritySid(ptr long) @ stdcall RtlSubtreePredecessor(ptr) -@ stub RtlSubtreeSuccessor +@ stdcall RtlSubtreeSuccessor(ptr) @ stdcall RtlSystemTimeToLocalTime(ptr ptr) @ stdcall RtlTimeFieldsToTime(ptr ptr) @ stdcall RtlTimeToElapsedTimeFields(ptr ptr) diff --git a/dlls/ntdll/rtl.c b/dlls/ntdll/rtl.c index d98edb8745e..e277e56be1b 100644 --- a/dlls/ntdll/rtl.c +++ b/dlls/ntdll/rtl.c @@ -255,6 +255,25 @@ RTL_SPLAY_LINKS * WINAPI RtlSubtreePredecessor(RTL_SPLAY_LINKS *links) return child; }
+/****************************************************************************** + * RtlSubtreeSuccessor [NTDLL.@] + */ +RTL_SPLAY_LINKS * WINAPI RtlSubtreeSuccessor(RTL_SPLAY_LINKS *links) +{ + RTL_SPLAY_LINKS *child; + + TRACE("(%p)\n", links); + + child = RtlRightChild(links); + if (!child) + return NULL; + + while (RtlLeftChild(child)) + child = RtlLeftChild(child); + + return child; +} + /****************************************************************************** * RtlInitializeGenericTable [NTDLL.@] */ diff --git a/dlls/ntoskrnl.exe/ntoskrnl.exe.spec b/dlls/ntoskrnl.exe/ntoskrnl.exe.spec index 2a86e4d100b..2ba1dc88eeb 100644 --- a/dlls/ntoskrnl.exe/ntoskrnl.exe.spec +++ b/dlls/ntoskrnl.exe/ntoskrnl.exe.spec @@ -1270,7 +1270,7 @@ @ stdcall RtlSubAuthorityCountSid(ptr) @ stdcall RtlSubAuthoritySid(ptr long) @ stdcall RtlSubtreePredecessor(ptr) -@ stub RtlSubtreeSuccessor +@ stdcall RtlSubtreeSuccessor(ptr) @ stdcall RtlSystemTimeToLocalTime(ptr ptr) @ stub RtlTestBit @ stdcall RtlTimeFieldsToTime(ptr ptr) diff --git a/include/ddk/ntddk.h b/include/ddk/ntddk.h index cc642fa6c0f..334266d6e1d 100644 --- a/include/ddk/ntddk.h +++ b/include/ddk/ntddk.h @@ -314,6 +314,7 @@ ULONG WINAPI RtlNumberGenericTableElements(PRTL_GENERIC_TABLE); ULONG WINAPI RtlNumberGenericTableElementsAvl(PRTL_AVL_TABLE); BOOLEAN WINAPI RtlPrefixUnicodeString(const UNICODE_STRING*,const UNICODE_STRING*,BOOLEAN); 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); char WINAPI RtlUpperChar(char); void WINAPI RtlUpperString(STRING*,const STRING*);
From: Zhiyi Zhang zzhang@codeweavers.com
--- dlls/ntdll/tests/rtl.c | 43 ++++++++++++++++++++++++++++++++++++++++++ 1 file changed, 43 insertions(+)
diff --git a/dlls/ntdll/tests/rtl.c b/dlls/ntdll/tests/rtl.c index 9978c0d878e..ae430256855 100644 --- a/dlls/ntdll/tests/rtl.c +++ b/dlls/ntdll/tests/rtl.c @@ -122,6 +122,7 @@ static NTSTATUS (WINAPI *pRtlRetrieveNtUserPfn)( const UINT64 **client_procsA, const UINT64 **client_workers ); static NTSTATUS (WINAPI *pRtlResetNtUserPfn)(void); static PRTL_SPLAY_LINKS (WINAPI *pRtlSubtreePredecessor)(PRTL_SPLAY_LINKS); +static PRTL_SPLAY_LINKS (WINAPI *pRtlSubtreeSuccessor)(PRTL_SPLAY_LINKS);
static HMODULE hkernel32 = 0; static BOOL (WINAPI *pIsWow64Process)(HANDLE, PBOOL); @@ -173,6 +174,7 @@ static void InitFunctionPtrs(void) pRtlRetrieveNtUserPfn = (void *)GetProcAddress(hntdll, "RtlRetrieveNtUserPfn"); pRtlResetNtUserPfn = (void *)GetProcAddress(hntdll, "RtlResetNtUserPfn"); pRtlSubtreePredecessor = (void *)GetProcAddress(hntdll, "RtlSubtreePredecessor"); + pRtlSubtreeSuccessor = (void *)GetProcAddress(hntdll, "RtlSubtreeSuccessor"); } hkernel32 = LoadLibraryA("kernel32.dll"); ok(hkernel32 != 0, "LoadLibrary failed\n"); @@ -4135,6 +4137,46 @@ static void test_RtlSubtreePredecessor(void) } }
+static void test_RtlSubtreeSuccessor(void) +{ + /* 3 + * / \ + * 1 5 + * / \ / \ + * 0 2 4 6 + */ + static const struct splay_index splay_indices[] = + { + {3, 1, 5}, + {1, 0, 2}, + {5, 4, 6}, + }; + static const int expected_successors[] = {-1, 2, -1, 4, -1, 6, -1}; + RTL_SPLAY_LINKS links[7], *successor; + unsigned int i; + + if (!pRtlSubtreeSuccessor) + { + win_skip("RtlSubtreeSuccessor is unavailable.\n"); + return; + } + + init_splay_indices(links, ARRAY_SIZE(links), splay_indices, ARRAY_SIZE(splay_indices)); + for (i = 0; i < ARRAY_SIZE(expected_successors); i++) + { + winetest_push_context("%d", i); + + successor = pRtlSubtreeSuccessor(&links[i]); + if (expected_successors[i] == -1) + ok(!successor, "Expected NULL, got unexpected %d.\n", (int)(successor - links)); + else + ok(successor == &links[expected_successors[i]], "Expected %d, got unexpected %d.\n", + expected_successors[i], (int)(successor ? successor - links : -1)); + + winetest_pop_context(); + } +} + START_TEST(rtl) { InitFunctionPtrs(); @@ -4188,4 +4230,5 @@ START_TEST(rtl) test_rb_tree(); test_user_procs(); test_RtlSubtreePredecessor(); + test_RtlSubtreeSuccessor(); }
-
Zhiyi Zhang -
Zhiyi Zhang (＠zhiyi)