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 
21 #include "utils.h"
22 
int_cmp(const void * lhs,const void * rhs)23 static int int_cmp(const void* lhs, const void* rhs) {
24   return *reinterpret_cast<const int*>(rhs) - *reinterpret_cast<const int*>(lhs);
25 }
26 
TEST(search,lfind_lsearch)27 TEST(search, lfind_lsearch) {
28   int xs[10];
29   memset(xs, 0, sizeof(xs));
30   size_t x_size = 0;
31 
32   int needle;
33 
34   // lfind(3) can't find '2' in the empty table.
35   needle = 2;
36   ASSERT_EQ(nullptr, lfind(&needle, xs, &x_size, sizeof(xs[0]), int_cmp));
37   ASSERT_EQ(0U, x_size);
38 
39   // lsearch(3) will add it.
40   ASSERT_EQ(&xs[0], lsearch(&needle, xs, &x_size, sizeof(xs[0]), int_cmp));
41   ASSERT_EQ(2, xs[0]);
42   ASSERT_EQ(1U, x_size);
43 
44   // And then lfind(3) can find it.
45   ASSERT_EQ(&xs[0], lfind(&needle, xs, &x_size, sizeof(xs[0]), int_cmp));
46   ASSERT_EQ(1U, x_size);
47 
48   // Inserting a duplicate does nothing (but returns the existing element).
49   ASSERT_EQ(&xs[0], lsearch(&needle, xs, &x_size, sizeof(xs[0]), int_cmp));
50   ASSERT_EQ(1U, x_size);
51 }
52 
53 struct node {
nodenode54   explicit node(const char* s) : s(strdup(s)) {}
55 
56   char* s;
57 };
58 
node_cmp(const void * lhs,const void * rhs)59 static int node_cmp(const void* lhs, const void* rhs) {
60   return strcmp(reinterpret_cast<const node*>(lhs)->s, reinterpret_cast<const node*>(rhs)->s);
61 }
62 
63 static std::vector<std::string> g_nodes;
64 
node_walk(const void * p,VISIT order,int)65 static void node_walk(const void* p, VISIT order, int) {
66   const node* n = *reinterpret_cast<const node* const*>(p);
67   if (order == postorder || order == leaf)  {
68     g_nodes.push_back(n->s);
69   }
70 }
71 
72 static size_t g_free_calls;
73 
node_free(void * p)74 static void node_free(void* p) {
75   node* n = reinterpret_cast<node*>(p);
76   free(n->s);
77   ++g_free_calls;
78 }
79 
TEST(search,tfind_tsearch_twalk_tdestroy)80 TEST(search, tfind_tsearch_twalk_tdestroy) {
81   void* root = nullptr;
82 
83   node n1("z");
84   node n2("a");
85   node n3("m");
86 
87   // tfind(3) can't find anything in the empty tree.
88   ASSERT_EQ(nullptr, tfind(&n1, &root, node_cmp));
89   ASSERT_EQ(nullptr, tfind(&n2, &root, node_cmp));
90   ASSERT_EQ(nullptr, tfind(&n3, &root, node_cmp));
91 
92   // tsearch(3) inserts and returns a pointer to a new node.
93   void* i1 = tsearch(&n1, &root, node_cmp);
94   ASSERT_NE(nullptr, i1);
95 
96   // ...which tfind(3) will then return.
97   ASSERT_EQ(i1, tfind(&n1, &root, node_cmp));
98   ASSERT_EQ(nullptr, tfind(&n2, &root, node_cmp));
99   ASSERT_EQ(nullptr, tfind(&n3, &root, node_cmp));
100 
101   // Add the other nodes.
102   ASSERT_NE(nullptr, tsearch(&n2, &root, node_cmp));
103   ASSERT_NE(nullptr, tsearch(&n3, &root, node_cmp));
104 
105   // Use twalk(3) to iterate over the nodes.
106   g_nodes.clear();
107   twalk(root, node_walk);
108   ASSERT_EQ(3U, g_nodes.size());
109   ASSERT_EQ("a", g_nodes[0]);
110   ASSERT_EQ("m", g_nodes[1]);
111   ASSERT_EQ("z", g_nodes[2]);
112 
113   // tdestroy(3) removes nodes under a node, calling our callback to destroy each one.
114   g_free_calls = 0;
115   tdestroy(root, node_free);
116   ASSERT_EQ(3U, g_free_calls);
117 }
118 
TEST(search,tdestroy_null)119 TEST(search, tdestroy_null) {
120   // It's okay to pass a null node, and your callback will not be called.
121   tdestroy(nullptr, nullptr);
122 }
123 
124 struct pod_node {
pod_nodepod_node125   explicit pod_node(int i) : i(i) {}
126   int i;
127 };
128 
pod_node_cmp(const void * lhs,const void * rhs)129 static int pod_node_cmp(const void* lhs, const void* rhs) {
130   return reinterpret_cast<const pod_node*>(rhs)->i - reinterpret_cast<const pod_node*>(lhs)->i;
131 }
132 
TEST(search,tdelete)133 TEST(search, tdelete) {
134   void* root = nullptr;
135 
136   pod_node n1(123);
137   ASSERT_NE(nullptr, tsearch(&n1, &root, pod_node_cmp));
138 
139   // tdelete(3) leaks n1.
140   pod_node not_there(456);
141   ASSERT_EQ(nullptr, tdelete(&not_there, &root, pod_node_cmp));
142   ASSERT_NE(nullptr, tdelete(&n1, &root, pod_node_cmp));
143 }
144 
145 struct q_node {
q_nodeq_node146   explicit q_node(int i) : i(i) {}
147 
148   q_node* next;
149   q_node* prev;
150 
151   int i;
152 };
153 
TEST(search,insque_remque)154 TEST(search, insque_remque) {
155   q_node zero(0);
156   q_node one(1);
157   q_node two(2);
158 
159   // Linear (not circular).
160 
161   insque(&zero, nullptr);
162   insque(&one, &zero);
163   insque(&two, &one);
164 
165   int expected = 0;
166   for (q_node* q = &zero; q != nullptr; q = q->next) {
167     ASSERT_EQ(expected, q->i);
168     ++expected;
169   }
170   ASSERT_EQ(3, expected);
171 
172   for (q_node* q = &two; q != nullptr; q = q->prev) {
173     --expected;
174     ASSERT_EQ(expected, q->i);
175   }
176   ASSERT_EQ(0, expected);
177 
178   q_node* head = &zero;
179 
180   remque(&one);
181   ASSERT_EQ(0, head->i);
182   ASSERT_EQ(2, head->next->i);
183   ASSERT_EQ(nullptr, head->next->next);
184 
185   remque(&two);
186   ASSERT_EQ(0, head->i);
187   ASSERT_EQ(nullptr, head->next);
188 
189   remque(&zero);
190 
191   // Circular.
192 
193   zero.next = &zero;
194   zero.prev = &zero;
195 
196   insque(&one, &zero);
197   insque(&two, &one);
198 
199   ASSERT_EQ(0, head->i);
200   ASSERT_EQ(1, head->next->i);
201   ASSERT_EQ(2, head->next->next->i);
202   ASSERT_EQ(0, head->next->next->next->i);
203   ASSERT_EQ(1, head->next->next->next->next->i);
204   ASSERT_EQ(2, head->next->next->next->next->next->i);
205 
206   remque(&one);
207   ASSERT_EQ(0, head->i);
208   ASSERT_EQ(2, head->next->i);
209   ASSERT_EQ(0, head->next->next->i);
210   ASSERT_EQ(2, head->next->next->next->i);
211 
212   remque(&two);
213   ASSERT_EQ(0, head->i);
214   ASSERT_EQ(0, head->next->i);
215 
216   remque(&zero);
217 }
218 
AssertEntry(ENTRY * e,const char * expected_key,const char * expected_data)219 static void AssertEntry(ENTRY* e, const char* expected_key, const char* expected_data) {
220   ASSERT_TRUE(e != nullptr);
221   ASSERT_STREQ(expected_key, reinterpret_cast<char*>(e->key));
222   ASSERT_STREQ(expected_data, reinterpret_cast<char*>(e->data));
223 }
224 
TEST(search,hcreate_hsearch_hdestroy)225 TEST(search, hcreate_hsearch_hdestroy) {
226   ASSERT_NE(0, hcreate(13));
227 
228   // Add some initial entries.
229   ENTRY* e;
230   e = hsearch(ENTRY{.key = const_cast<char*>("a"), .data = const_cast<char*>("A")}, ENTER);
231   AssertEntry(e, "a", "A");
232   e = hsearch(ENTRY{.key = const_cast<char*>("aa"), .data = const_cast<char*>("B")}, ENTER);
233   AssertEntry(e, "aa", "B");
234   e = hsearch(ENTRY{.key = const_cast<char*>("aaa"), .data = const_cast<char*>("C")}, ENTER);
235   AssertEntry(e, "aaa", "C");
236 
237   // Check missing.
238   e = hsearch(ENTRY{.key = const_cast<char*>("aaaa"), .data = nullptr}, FIND);
239   ASSERT_FALSE(e != nullptr);
240 
241   // Check present.
242   e = hsearch(ENTRY{.key = const_cast<char*>("aa"), .data = nullptr}, FIND);
243   AssertEntry(e, "aa", "B");
244 
245   // ENTER with an existing key just returns the existing ENTRY.
246   e = hsearch(ENTRY{.key = const_cast<char*>("aa"), .data = const_cast<char*>("X")}, ENTER);
247   AssertEntry(e, "aa", "B");
248   e->data = const_cast<char*>("X");
249 
250   // Check present and updated.
251   e = hsearch(ENTRY{.key = const_cast<char*>("aa"), .data = nullptr}, FIND);
252   AssertEntry(e, "aa", "X");
253   // But other entries stayed the same.
254   e = hsearch(ENTRY{.key = const_cast<char*>("a"), .data = nullptr}, FIND);
255   AssertEntry(e, "a", "A");
256   e = hsearch(ENTRY{.key = const_cast<char*>("aaa"), .data = nullptr}, FIND);
257   AssertEntry(e, "aaa", "C");
258 
259   hdestroy();
260 }
261 
TEST(search,hcreate_r_hsearch_r_hdestroy_r)262 TEST(search, hcreate_r_hsearch_r_hdestroy_r) {
263   hsearch_data h1 = {};
264   ASSERT_EQ(1, hcreate_r(13, &h1));
265 
266   hsearch_data h2 = {};
267   ASSERT_EQ(1, hcreate_r(128, &h2));
268 
269   // Add some initial entries.
270   ENTRY* e;
271   ASSERT_EQ(1, hsearch_r(ENTRY{.key = const_cast<char*>("a"), .data = const_cast<char*>("A")},
272                          ENTER, &e, &h1));
273   AssertEntry(e, "a", "A");
274   ASSERT_EQ(1, hsearch_r(ENTRY{.key = const_cast<char*>("a"), .data = const_cast<char*>("B")},
275                          ENTER, &e, &h2));
276   AssertEntry(e, "a", "B");
277 
278   // Check missing.
279   errno = 0;
280   ASSERT_EQ(0, hsearch_r(ENTRY{.key = const_cast<char*>("b"), .data = nullptr}, FIND, &e, &h1));
281   ASSERT_ERRNO(ESRCH);
282 
283   // Check present.
284   ASSERT_EQ(1, hsearch_r(ENTRY{.key = const_cast<char*>("a"), .data = nullptr}, FIND, &e, &h1));
285   AssertEntry(e, "a", "A");
286   ASSERT_EQ(1, hsearch_r(ENTRY{.key = const_cast<char*>("a"), .data = nullptr}, FIND, &e, &h2));
287   AssertEntry(e, "a", "B");
288 
289   // Destroying one doesn't affect the other.
290   hdestroy_r(&h1);
291   ASSERT_EQ(1, hsearch_r(ENTRY{.key = const_cast<char*>("a"), .data = nullptr}, FIND, &e, &h2));
292   AssertEntry(e, "a", "B");
293   hdestroy_r(&h2);
294 }
295 
TEST(search,hsearch_resizing)296 TEST(search, hsearch_resizing) {
297   ASSERT_NE(0, hcreate(1));
298 
299   std::vector<char*> entries;
300   // Add enough entries to ensure that we've had to resize.
301   for (char ch = ' '; ch <= '~'; ++ch) {
302     char* p;
303     asprintf(&p, "%c", ch);
304     ENTRY e;
305     e.data = e.key = p;
306     ASSERT_TRUE(hsearch(e, ENTER) != nullptr);
307     entries.push_back(p);
308   }
309 
310   // Check they're all there.
311   for (auto& p : entries) {
312     ENTRY* e = hsearch(ENTRY{.key = p, .data = nullptr}, FIND);
313     AssertEntry(e, p, p);
314   }
315 
316   for (auto& p : entries) free(p);
317 }
318