1 /*
2 * Copyright (C) 2014 The Android Open Source Project
3 *
4 * Licensed under the Apache License, Version 2.0 (the "License");
5 * you may not use this file except in compliance with the License.
6 * You may obtain a copy of the License at
7 *
8 * http://www.apache.org/licenses/LICENSE-2.0
9 *
10 * Unless required by applicable law or agreed to in writing, software
11 * distributed under the License is distributed on an "AS IS" BASIS,
12 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
13 * See the License for the specific language governing permissions and
14 * limitations under the License.
15 */
16
17 #include <gtest/gtest.h>
18
19 #include <search.h>
20
int_cmp(const void * lhs,const void * rhs)21 static int int_cmp(const void* lhs, const void* rhs) {
22 return *reinterpret_cast<const int*>(rhs) - *reinterpret_cast<const int*>(lhs);
23 }
24
TEST(search,lfind_lsearch)25 TEST(search, lfind_lsearch) {
26 int xs[10];
27 memset(xs, 0, sizeof(xs));
28 size_t x_size = 0;
29
30 int needle;
31
32 // lfind(3) can't find '2' in the empty table.
33 needle = 2;
34 ASSERT_EQ(nullptr, lfind(&needle, xs, &x_size, sizeof(xs[0]), int_cmp));
35 ASSERT_EQ(0U, x_size);
36
37 // lsearch(3) will add it.
38 ASSERT_EQ(&xs[0], lsearch(&needle, xs, &x_size, sizeof(xs[0]), int_cmp));
39 ASSERT_EQ(2, xs[0]);
40 ASSERT_EQ(1U, x_size);
41
42 // And then lfind(3) can find it.
43 ASSERT_EQ(&xs[0], lfind(&needle, xs, &x_size, sizeof(xs[0]), int_cmp));
44 ASSERT_EQ(1U, x_size);
45
46 // Inserting a duplicate does nothing (but returns the existing element).
47 ASSERT_EQ(&xs[0], lsearch(&needle, xs, &x_size, sizeof(xs[0]), int_cmp));
48 ASSERT_EQ(1U, x_size);
49 }
50
51 struct node {
nodenode52 explicit node(const char* s) : s(strdup(s)) {}
53
54 char* s;
55 };
56
node_cmp(const void * lhs,const void * rhs)57 static int node_cmp(const void* lhs, const void* rhs) {
58 return strcmp(reinterpret_cast<const node*>(lhs)->s, reinterpret_cast<const node*>(rhs)->s);
59 }
60
61 static std::vector<std::string> g_nodes;
62
node_walk(const void * p,VISIT order,int)63 static void node_walk(const void* p, VISIT order, int) {
64 const node* n = *reinterpret_cast<const node* const*>(p);
65 if (order == postorder || order == leaf) {
66 g_nodes.push_back(n->s);
67 }
68 }
69
70 static size_t g_free_calls;
71
node_free(void * p)72 static void node_free(void* p) {
73 node* n = reinterpret_cast<node*>(p);
74 free(n->s);
75 ++g_free_calls;
76 }
77
TEST(search,tfind_tsearch_twalk_tdestroy)78 TEST(search, tfind_tsearch_twalk_tdestroy) {
79 void* root = nullptr;
80
81 node n1("z");
82 node n2("a");
83 node n3("m");
84
85 // tfind(3) can't find anything in the empty tree.
86 ASSERT_EQ(nullptr, tfind(&n1, &root, node_cmp));
87 ASSERT_EQ(nullptr, tfind(&n2, &root, node_cmp));
88 ASSERT_EQ(nullptr, tfind(&n3, &root, node_cmp));
89
90 // tsearch(3) inserts and returns a pointer to a new node.
91 void* i1 = tsearch(&n1, &root, node_cmp);
92 ASSERT_NE(nullptr, i1);
93
94 // ...which tfind(3) will then return.
95 ASSERT_EQ(i1, tfind(&n1, &root, node_cmp));
96 ASSERT_EQ(nullptr, tfind(&n2, &root, node_cmp));
97 ASSERT_EQ(nullptr, tfind(&n3, &root, node_cmp));
98
99 // Add the other nodes.
100 ASSERT_NE(nullptr, tsearch(&n2, &root, node_cmp));
101 ASSERT_NE(nullptr, tsearch(&n3, &root, node_cmp));
102
103 // Use twalk(3) to iterate over the nodes.
104 g_nodes.clear();
105 twalk(root, node_walk);
106 ASSERT_EQ(3U, g_nodes.size());
107 ASSERT_EQ("a", g_nodes[0]);
108 ASSERT_EQ("m", g_nodes[1]);
109 ASSERT_EQ("z", g_nodes[2]);
110
111 // tdestroy(3) removes nodes under a node, calling our callback to destroy each one.
112 g_free_calls = 0;
113 tdestroy(root, node_free);
114 ASSERT_EQ(3U, g_free_calls);
115 }
116
117 struct pod_node {
pod_nodepod_node118 explicit pod_node(int i) : i(i) {}
119 int i;
120 };
121
pod_node_cmp(const void * lhs,const void * rhs)122 static int pod_node_cmp(const void* lhs, const void* rhs) {
123 return reinterpret_cast<const pod_node*>(rhs)->i - reinterpret_cast<const pod_node*>(lhs)->i;
124 }
125
TEST(search,tdelete)126 TEST(search, tdelete) {
127 void* root = nullptr;
128
129 pod_node n1(123);
130 ASSERT_NE(nullptr, tsearch(&n1, &root, pod_node_cmp));
131
132 // tdelete(3) leaks n1.
133 pod_node not_there(456);
134 ASSERT_EQ(nullptr, tdelete(¬_there, &root, pod_node_cmp));
135 ASSERT_NE(nullptr, tdelete(&n1, &root, pod_node_cmp));
136 }
137
138 struct q_node {
q_nodeq_node139 explicit q_node(int i) : i(i) {}
140
141 q_node* next;
142 q_node* prev;
143
144 int i;
145 };
146
TEST(search,insque_remque)147 TEST(search, insque_remque) {
148 q_node zero(0);
149 q_node one(1);
150 q_node two(2);
151
152 // Linear (not circular).
153
154 insque(&zero, nullptr);
155 insque(&one, &zero);
156 insque(&two, &one);
157
158 int expected = 0;
159 for (q_node* q = &zero; q != nullptr; q = q->next) {
160 ASSERT_EQ(expected, q->i);
161 ++expected;
162 }
163 ASSERT_EQ(3, expected);
164
165 for (q_node* q = &two; q != nullptr; q = q->prev) {
166 --expected;
167 ASSERT_EQ(expected, q->i);
168 }
169 ASSERT_EQ(0, expected);
170
171 q_node* head = &zero;
172
173 remque(&one);
174 ASSERT_EQ(0, head->i);
175 ASSERT_EQ(2, head->next->i);
176 ASSERT_EQ(nullptr, head->next->next);
177
178 remque(&two);
179 ASSERT_EQ(0, head->i);
180 ASSERT_EQ(nullptr, head->next);
181
182 remque(&zero);
183
184 // Circular.
185
186 zero.next = &zero;
187 zero.prev = &zero;
188
189 insque(&one, &zero);
190 insque(&two, &one);
191
192 ASSERT_EQ(0, head->i);
193 ASSERT_EQ(1, head->next->i);
194 ASSERT_EQ(2, head->next->next->i);
195 ASSERT_EQ(0, head->next->next->next->i);
196 ASSERT_EQ(1, head->next->next->next->next->i);
197 ASSERT_EQ(2, head->next->next->next->next->next->i);
198
199 remque(&one);
200 ASSERT_EQ(0, head->i);
201 ASSERT_EQ(2, head->next->i);
202 ASSERT_EQ(0, head->next->next->i);
203 ASSERT_EQ(2, head->next->next->next->i);
204
205 remque(&two);
206 ASSERT_EQ(0, head->i);
207 ASSERT_EQ(0, head->next->i);
208
209 remque(&zero);
210 }
211
AssertEntry(ENTRY * e,const char * expected_key,const char * expected_data)212 static void AssertEntry(ENTRY* e, const char* expected_key, const char* expected_data) {
213 ASSERT_TRUE(e != nullptr);
214 ASSERT_STREQ(expected_key, reinterpret_cast<char*>(e->key));
215 ASSERT_STREQ(expected_data, reinterpret_cast<char*>(e->data));
216 }
217
TEST(search,hcreate_hsearch_hdestroy)218 TEST(search, hcreate_hsearch_hdestroy) {
219 ASSERT_NE(0, hcreate(13));
220
221 // Add some initial entries.
222 ENTRY* e;
223 e = hsearch(ENTRY{.key = const_cast<char*>("a"), .data = const_cast<char*>("A")}, ENTER);
224 AssertEntry(e, "a", "A");
225 e = hsearch(ENTRY{.key = const_cast<char*>("aa"), .data = const_cast<char*>("B")}, ENTER);
226 AssertEntry(e, "aa", "B");
227 e = hsearch(ENTRY{.key = const_cast<char*>("aaa"), .data = const_cast<char*>("C")}, ENTER);
228 AssertEntry(e, "aaa", "C");
229
230 // Check missing.
231 e = hsearch(ENTRY{.key = const_cast<char*>("aaaa"), .data = nullptr}, FIND);
232 ASSERT_FALSE(e != nullptr);
233
234 // Check present.
235 e = hsearch(ENTRY{.key = const_cast<char*>("aa"), .data = nullptr}, FIND);
236 AssertEntry(e, "aa", "B");
237
238 // ENTER with an existing key just returns the existing ENTRY.
239 e = hsearch(ENTRY{.key = const_cast<char*>("aa"), .data = const_cast<char*>("X")}, ENTER);
240 AssertEntry(e, "aa", "B");
241 e->data = const_cast<char*>("X");
242
243 // Check present and updated.
244 e = hsearch(ENTRY{.key = const_cast<char*>("aa"), .data = nullptr}, FIND);
245 AssertEntry(e, "aa", "X");
246 // But other entries stayed the same.
247 e = hsearch(ENTRY{.key = const_cast<char*>("a"), .data = nullptr}, FIND);
248 AssertEntry(e, "a", "A");
249 e = hsearch(ENTRY{.key = const_cast<char*>("aaa"), .data = nullptr}, FIND);
250 AssertEntry(e, "aaa", "C");
251
252 hdestroy();
253 }
254
TEST(search,hcreate_r_hsearch_r_hdestroy_r)255 TEST(search, hcreate_r_hsearch_r_hdestroy_r) {
256 hsearch_data h1 = {};
257 ASSERT_EQ(1, hcreate_r(13, &h1));
258
259 hsearch_data h2 = {};
260 ASSERT_EQ(1, hcreate_r(128, &h2));
261
262 // Add some initial entries.
263 ENTRY* e;
264 ASSERT_EQ(1, hsearch_r(ENTRY{.key = const_cast<char*>("a"), .data = const_cast<char*>("A")},
265 ENTER, &e, &h1));
266 AssertEntry(e, "a", "A");
267 ASSERT_EQ(1, hsearch_r(ENTRY{.key = const_cast<char*>("a"), .data = const_cast<char*>("B")},
268 ENTER, &e, &h2));
269 AssertEntry(e, "a", "B");
270
271 // Check missing.
272 errno = 0;
273 ASSERT_EQ(0, hsearch_r(ENTRY{.key = const_cast<char*>("b"), .data = nullptr}, FIND, &e, &h1));
274 ASSERT_EQ(ESRCH, errno);
275
276 // Check present.
277 ASSERT_EQ(1, hsearch_r(ENTRY{.key = const_cast<char*>("a"), .data = nullptr}, FIND, &e, &h1));
278 AssertEntry(e, "a", "A");
279 ASSERT_EQ(1, hsearch_r(ENTRY{.key = const_cast<char*>("a"), .data = nullptr}, FIND, &e, &h2));
280 AssertEntry(e, "a", "B");
281
282 // Destroying one doesn't affect the other.
283 hdestroy_r(&h1);
284 ASSERT_EQ(1, hsearch_r(ENTRY{.key = const_cast<char*>("a"), .data = nullptr}, FIND, &e, &h2));
285 AssertEntry(e, "a", "B");
286 hdestroy_r(&h2);
287 }
288