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 static int int_cmp(const void* lhs, const void* rhs) { 22 return *reinterpret_cast<const int*>(rhs) - *reinterpret_cast<const int*>(lhs); 23 } 24 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 { 52 explicit node(const char* s) : s(strdup(s)) {} 53 54 char* s; 55 }; 56 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 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 72 static void node_free(void* p) { 73 node* n = reinterpret_cast<node*>(p); 74 free(n->s); 75 ++g_free_calls; 76 } 77 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 { 118 explicit pod_node(int i) : i(i) {} 119 int i; 120 }; 121 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 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 { 139 explicit q_node(int i) : i(i) {} 140 141 q_node* next; 142 q_node* prev; 143 144 int i; 145 }; 146 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, 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 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 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 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
