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