[PATCH 3/5] ntdll/tests: Add RtlSubtreePredecessor() tests.

[Zhiyi Zhang]

From: Zhiyi Zhang

---
 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();
 }