jcs.org
Serenity Operating System
1/*
2 * Copyright (c) 2021, Tim Schumacher <timschumi@gmx.de>
3 *
4 * SPDX-License-Identifier: BSD-2-Clause
5 */
6
7#include <LibTest/TestCase.h>
8
9#include <bits/search.h>
10#include <search.h>
11#include <string.h>
12
13#define NODE(node) static_cast<struct search_tree_node*>(node)
14#define ROOTP(root) reinterpret_cast<void**>(root)
15#define COMP(func) reinterpret_cast<int (*)(void const*, void const*)>(func)
16#define U8(value) static_cast<u8>(value)
17
18struct twalk_test_entry {
19 void const* node;
20 VISIT order;
21 int depth;
22};
23
24#define TWALK_SET_DATA (-2)
25#define TWALK_CHECK_END (-3)
26#define TWALK_END_MARKER (-4)
27
28TEST_CASE(tsearch)
29{
30 struct search_tree_node* root = nullptr;
31 void* ret;
32 char const* key;
33 char* search;
34
35 // Try a nullptr rootp.
36 ret = tsearch("buggie", nullptr, COMP(strcmp));
37 EXPECT_EQ(ret, nullptr);
38
39 // Try creating a new tree.
40 key = "5";
41 ret = tsearch(key, ROOTP(&root), COMP(strcmp));
42 EXPECT_EQ(ret, root);
43 EXPECT_EQ(NODE(ret)->key, key);
44
45 // Insert an element on the left side.
46 key = "3";
47 ret = tsearch(key, ROOTP(&root), COMP(strcmp));
48 EXPECT_EQ(ret, root->left);
49 EXPECT_EQ(NODE(ret)->key, key);
50
51 // Insert an element on the right side.
52 key = "7";
53 ret = tsearch(key, ROOTP(&root), COMP(strcmp));
54 EXPECT_EQ(ret, root->right);
55 EXPECT_EQ(NODE(ret)->key, key);
56
57 // Add another layer for testing.
58 ret = tsearch("2", ROOTP(&root), COMP(strcmp));
59 EXPECT_EQ(ret, root->left->left);
60 ret = tsearch("4", ROOTP(&root), COMP(strcmp));
61 EXPECT_EQ(ret, root->left->right);
62 ret = tsearch("6", ROOTP(&root), COMP(strcmp));
63 EXPECT_EQ(ret, root->right->left);
64 ret = tsearch("8", ROOTP(&root), COMP(strcmp));
65 EXPECT_EQ(ret, root->right->right);
66
67 // Find the root element.
68 // strdup ensures that we are using the comparator.
69 search = strdup("5");
70 ret = tsearch(search, ROOTP(&root), COMP(strcmp));
71 EXPECT_EQ(ret, root);
72 free(search);
73
74 // Find the lowest-level elements.
75 search = strdup("2");
76 ret = tsearch(search, ROOTP(&root), COMP(strcmp));
77 EXPECT_EQ(ret, root->left->left);
78 free(search);
79
80 search = strdup("4");
81 ret = tsearch(search, ROOTP(&root), COMP(strcmp));
82 EXPECT_EQ(ret, root->left->right);
83 free(search);
84
85 search = strdup("6");
86 ret = tsearch(search, ROOTP(&root), COMP(strcmp));
87 EXPECT_EQ(ret, root->right->left);
88 free(search);
89
90 search = strdup("8");
91 ret = tsearch(search, ROOTP(&root), COMP(strcmp));
92 EXPECT_EQ(ret, root->right->right);
93 free(search);
94
95 delete_node_recursive(root);
96}
97
98TEST_CASE(tfind)
99{
100 struct search_tree_node* root = nullptr;
101 void* ret;
102 char* search;
103
104 // Try a nullptr rootp.
105 ret = tfind("buggie", nullptr, COMP(strcmp));
106 EXPECT_EQ(ret, nullptr);
107
108 // Search for something that doesn't exist.
109 ret = tfind("buggie", ROOTP(&root), COMP(strcmp));
110 EXPECT_EQ(ret, nullptr);
111
112 // Construct a tree for testing.
113 root = new_tree_node("5");
114 root->left = new_tree_node("3");
115 root->right = new_tree_node("7");
116 root->left->left = new_tree_node("2");
117 root->left->right = new_tree_node("4");
118 root->right->left = new_tree_node("6");
119 root->right->right = new_tree_node("8");
120
121 // Find the root element.
122 // strdup ensures that we are using the comparator.
123 search = strdup("5");
124 ret = tfind(search, ROOTP(&root), COMP(strcmp));
125 EXPECT_EQ(ret, root);
126 free(search);
127
128 // Find the lowest-level elements.
129 search = strdup("2");
130 ret = tfind(search, ROOTP(&root), COMP(strcmp));
131 EXPECT_EQ(ret, root->left->left);
132 free(search);
133
134 search = strdup("4");
135 ret = tfind(search, ROOTP(&root), COMP(strcmp));
136 EXPECT_EQ(ret, root->left->right);
137 free(search);
138
139 search = strdup("6");
140 ret = tfind(search, ROOTP(&root), COMP(strcmp));
141 EXPECT_EQ(ret, root->right->left);
142 free(search);
143
144 search = strdup("8");
145 ret = tfind(search, ROOTP(&root), COMP(strcmp));
146 EXPECT_EQ(ret, root->right->right);
147 free(search);
148
149 delete_node_recursive(root);
150}
151
152void twalk_action(void const* node, VISIT order, int depth);
153void twalk_action(void const* node, VISIT order, int depth)
154{
155 static int count = 0;
156 static const struct twalk_test_entry* tests = nullptr;
157
158 // Special case: Set test data.
159 if (depth == TWALK_SET_DATA) {
160 count = 0;
161 tests = static_cast<const struct twalk_test_entry*>(node);
162 return;
163 }
164
165 // Special case: End signaled by tester.
166 if (depth == TWALK_CHECK_END) {
167 if (tests[count].depth != TWALK_END_MARKER) {
168 FAIL(DeprecatedString::formatted("Expected action (node={:#x}, order={}, depth={}), but twalk ended early.",
169 tests[count].node, U8(tests[count].order), tests[count].depth));
170 }
171 return;
172 }
173
174 // Special case: End marker reached.
175 if (tests[count].depth == TWALK_END_MARKER) {
176 FAIL(DeprecatedString::formatted("Expected end, but twalk sent another action (node={:#x}, order={}, depth={}).",
177 node, U8(order), depth));
178 return;
179 }
180
181 EXPECT_EQ(node, tests[count].node);
182 EXPECT_EQ(U8(order), U8(tests[count].order));
183 EXPECT_EQ(depth, tests[count].depth);
184
185 count++;
186}
187
188TEST_CASE(twalk)
189{
190 struct search_tree_node* root = nullptr;
191
192 // Try an empty tree.
193 struct twalk_test_entry tests1[] = {
194 { nullptr, leaf, TWALK_END_MARKER },
195 };
196 twalk_action(tests1, leaf, TWALK_SET_DATA);
197 twalk(nullptr, twalk_action);
198 twalk_action(nullptr, leaf, TWALK_CHECK_END);
199
200 // Try a single node.
201 root = new_tree_node("5");
202 struct twalk_test_entry tests2[] = {
203 { root, leaf, 0 },
204 { nullptr, leaf, TWALK_END_MARKER },
205 };
206 twalk_action(tests2, leaf, TWALK_SET_DATA);
207 twalk(root, twalk_action);
208 twalk_action(nullptr, leaf, TWALK_CHECK_END);
209
210 // Try two layers of nodes.
211 root->left = new_tree_node("3");
212 root->right = new_tree_node("7");
213 struct twalk_test_entry tests3[] = {
214 { root, preorder, 0 },
215 { root->left, leaf, 1 },
216 { root, postorder, 0 },
217 { root->right, leaf, 1 },
218 { root, endorder, 0 },
219 { nullptr, leaf, TWALK_END_MARKER },
220 };
221 twalk_action(tests3, leaf, TWALK_SET_DATA);
222 twalk(root, twalk_action);
223 twalk_action(nullptr, leaf, TWALK_CHECK_END);
224
225 // Try three layers of nodes.
226 root->left->left = new_tree_node("2");
227 root->left->right = new_tree_node("4");
228 root->right->left = new_tree_node("6");
229 root->right->right = new_tree_node("8");
230 struct twalk_test_entry tests4[] = {
231 { root, preorder, 0 },
232 { root->left, preorder, 1 },
233 { root->left->left, leaf, 2 },
234 { root->left, postorder, 1 },
235 { root->left->right, leaf, 2 },
236 { root->left, endorder, 1 },
237 { root, postorder, 0 },
238 { root->right, preorder, 1 },
239 { root->right->left, leaf, 2 },
240 { root->right, postorder, 1 },
241 { root->right->right, leaf, 2 },
242 { root->right, endorder, 1 },
243 { root, endorder, 0 },
244 { nullptr, leaf, TWALK_END_MARKER },
245 };
246 twalk_action(tests4, leaf, TWALK_SET_DATA);
247 twalk(root, twalk_action);
248 twalk_action(nullptr, leaf, TWALK_CHECK_END);
249
250 delete_node_recursive(root);
251}