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
21static int int_cmp(const void* lhs, const void* rhs) {
22  return *reinterpret_cast<const int*>(rhs) - *reinterpret_cast<const int*>(lhs);
23}
24
25TEST(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
51struct node {
52  explicit node(const char* s) : s(strdup(s)) {}
53
54  char* s;
55};
56
57static 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
61static std::vector<std::string> g_nodes;
62
63static 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
70static size_t g_free_calls;
71
72static void node_free(void* p) {
73  node* n = reinterpret_cast<node*>(p);
74  free(n->s);
75  ++g_free_calls;
76}
77
78TEST(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
117struct pod_node {
118  explicit pod_node(int i) : i(i) {}
119  int i;
120};
121
122static 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
126TEST(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
138struct q_node {
139  explicit q_node(int i) : i(i) {}
140
141  q_node* next;
142  q_node* prev;
143
144  int i;
145};
146
147TEST(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, NULL);
155  insque(&one, &zero);
156  insque(&two, &one);
157
158  int expected = 0;
159  for (q_node* q = &zero; q != NULL; 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 != NULL; 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