• Home
  • Line#
  • Scopes#
  • Navigate#
  • Raw
  • Download
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(&not_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