1 /* 2 * Copyright (c) 2024 Huawei Device Co., Ltd. 3 * Licensed under the Apache License, Version 2.0 (the "License"); 4 * you may not use this file except in compliance with the License. 5 * You may obtain a copy of the License at 6 * 7 * http://www.apache.org/licenses/LICENSE-2.0 8 * 9 * Unless required by applicable law or agreed to in writing, software 10 * distributed under the License is distributed on an "AS IS" BASIS, 11 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. 12 * See the License for the specific language governing permissions and 13 * limitations under the License. 14 */ 15 16 #include <chrono> 17 18 #include <gtest/gtest.h> 19 20 #include <base/containers/unordered_map.h> 21 22 using namespace BASE_NS; 23 using namespace testing::ext; 24 25 template<typename T> 26 struct Node { 27 T x, y, z; 28 // Constructor 29 Node() noexcept = default; NodeNode30 Node(T x, T y, T z) 31 { 32 this->x = x; 33 this->y = y; 34 this->z = z; 35 } 36 }; 37 38 class UnorderedMapTest : public testing::Test { 39 public: SetUpTestSuite()40 static void SetUpTestSuite() {} TearDownTestSuite()41 static void TearDownTestSuite() {} SetUp()42 void SetUp() override {} TearDown()43 void TearDown() override {} 44 }; 45 46 HWTEST_F(UnorderedMapTest, PairVerification, TestSize.Level1) 47 { 48 // Default constructor 49 auto original = BASE_NS::pair<int, int>(); 50 original.first = 12; 51 original.second = 15; 52 ASSERT_EQ(original.first, 12); 53 ASSERT_EQ(original.second, 15); 54 original = {}; 55 ASSERT_EQ(original.first, 0); 56 ASSERT_EQ(original.second, 0); 57 BASE_NS::pair<int, int> original3 = { 100, 30 }; 58 ASSERT_EQ(original3.first, 100); 59 ASSERT_EQ(original3.second, 30); 60 } 61 62 HWTEST_F(UnorderedMapTest, Default, TestSize.Level1) 63 { 64 // Test some types 65 unordered_map<int, int> int_int1; 66 auto int_int2 = unordered_map<int, int>(); 67 auto int_float = unordered_map<int, float>(); 68 auto int_bool = unordered_map<int, bool>(); 69 auto string_int = unordered_map<BASE_NS::string, int>(); 70 auto int_string = unordered_map<int, BASE_NS::string>(); 71 auto stringView_int = unordered_map<string_view, int>(); 72 auto int_stringView = unordered_map<int, string_view>(); 73 auto int_vector = unordered_map<int, BASE_NS::vector<int>>(); 74 auto int_map = unordered_map<int, unordered_map<int, BASE_NS::vector<int>>>(); 75 auto int_node = unordered_map<int, Node<int>>(); 76 77 // Not supported - hash function issue 78 // unordered_map<char, int> map; 79 // unordered_map<float, int> map; 80 } 81 82 HWTEST_F(UnorderedMapTest, Initialization, TestSize.Level1) 83 { 84 // Test some types 85 unordered_map<int, int> int_int; 86 int_int[42] = 32; 87 ASSERT_EQ(int_int[42], 32); 88 89 auto int_float = unordered_map<int, float>(); 90 int_float[42] = 32.000005f; 91 ASSERT_EQ(int_float[42], 32.000005f); 92 93 auto int_bool = unordered_map<int, bool>(); 94 int_bool[42] = true; 95 ASSERT_EQ(int_bool[42], true); 96 97 auto string_int = unordered_map<BASE_NS::string, int>(); 98 string_int[string_view("First")] = 10; 99 string_int.insert({ "Second", 456 }); 100 string_int.insert({ "Third", 0 }); 101 const BASE_NS::string cKey = "Key"; 102 const int cValue = 987; 103 const BASE_NS::pair<string_view, int> cPair = { cKey, cValue }; 104 string_int.insert(cPair); 105 ASSERT_EQ(string_int[string_view("First")], 10); 106 ASSERT_EQ(string_int[string_view("Second")], 456); 107 ASSERT_EQ(string_int[string_view("Third")], 0); 108 ASSERT_EQ(string_int.insert(cPair).second, false); 109 ASSERT_EQ(string_int[cKey], cValue); 110 111 auto int_string = unordered_map<int, BASE_NS::string>(); 112 int_string.insert({ 10, "First" }); 113 int_string.insert({ 456, "Second" }); 114 ASSERT_EQ(int_string[10], "First"); 115 ASSERT_EQ(int_string[456], "Second"); 116 117 auto int_char = unordered_map<int, char>(); 118 int_char.insert({ 10, 'a' }); 119 int_char.insert({ 456, 'b' }); 120 ASSERT_EQ(int_char[10], 'a'); 121 ASSERT_EQ(int_char[456], 'b'); 122 123 auto int_node = unordered_map<int, Node<float>>(); 124 int_node.insert({ 1, Node(5.f, 10.f, 20.f) }); 125 ASSERT_EQ(int_node[1].x, 5.f); 126 ASSERT_EQ(int_node[1].y, 10.f); 127 ASSERT_EQ(int_node[1].z, 20.f); 128 } 129 130 HWTEST_F(UnorderedMapTest, InitializerList, TestSize.Level1) 131 { 132 unordered_map<int, int> int_int({ { 1, 10 }, { 2, 20 }, { 3, 30 } }); 133 unordered_map<BASE_NS::string, int> string_int({ { "First", 10 }, { "Second", 20 }, { "Third", 30 } }); 134 ASSERT_EQ(string_int[string_view("First")], 10); 135 ASSERT_EQ(string_int[string_view("Second")], 20); 136 ASSERT_EQ(string_int[string_view("Third")], 30); 137 string_int = { { "A", 1 }, { "B", 2 }, { "C", 3 } }; 138 ASSERT_EQ(string_int[string_view("A")], 1); 139 ASSERT_EQ(string_int[string_view("B")], 2); 140 ASSERT_EQ(string_int[string_view("C")], 3); 141 } 142 143 HWTEST_F(UnorderedMapTest, Copy, TestSize.Level1) 144 { 145 const auto original = unordered_map<int, int>(); 146 ASSERT_NO_FATAL_FAILURE(const auto copy = original); 147 unordered_map<int, int> t; 148 t.operator=(original); 149 } 150 151 HWTEST_F(UnorderedMapTest, CopyVerification, TestSize.Level1) 152 { 153 auto original = unordered_map<int, int>(); 154 original[42] = 32; 155 auto copy = original; 156 ASSERT_TRUE(copy[42] == original[42]); 157 } 158 159 HWTEST_F(UnorderedMapTest, PointerActions, TestSize.Level1) 160 { 161 auto original = unordered_map<int, int>(); 162 original[42] = 32; 163 unordered_map<int, int> t; 164 t.operator=(original); 165 unordered_map<int, int>* p = new unordered_map<int, int>[3]; 166 p[0] = original; 167 p[1] = t; 168 p[2] = {}; 169 unordered_map<int, int>* p2 = &p[1]; 170 ASSERT_EQ(p2->begin(), p[1].begin()); 171 ASSERT_EQ(p2->end(), p[1].end()); 172 ASSERT_EQ(p[0][42], p[1][42]); 173 ASSERT_NE(p[0].begin(), p[1].begin()); // copy 174 ASSERT_EQ(p[2].begin(), p[2].end()); // empty 175 ASSERT_EQ(p[2].cbegin(), p[2].cend()); // empty 176 delete[] p; 177 } 178 179 HWTEST_F(UnorderedMapTest, Capacity, TestSize.Level1) 180 { 181 // Size 182 auto int_int = unordered_map<int, int>(); 183 int_int.insert({ 10, 20 }); 184 int_int.insert({ 10, 30 }); 185 int_int.insert({ 10, 40 }); 186 ASSERT_TRUE(int_int.size() == 1); 187 ASSERT_EQ(int_int[10], 20); 188 189 auto string_int = unordered_map<BASE_NS::string, int>(); 190 string_int.insert({ "One", 20 }); 191 string_int.insert({ "ONE", 30 }); 192 string_int.insert({ "one", 40 }); 193 ASSERT_TRUE(string_int.size() == 3); 194 195 // Empty 196 auto original = unordered_map<int, int>(); 197 ASSERT_TRUE(original.empty()); 198 } 199 200 HWTEST_F(UnorderedMapTest, Iterators, TestSize.Level1) 201 { 202 // Test iterator 203 auto string_int = unordered_map<BASE_NS::string, int>(); 204 string_int.insert({ "First", 10 }); 205 string_int.insert({ "Second", 500 }); 206 string_int.insert({ "Third", 0 }); 207 208 // Values to match the order of unordered map (assigned hash values) 209 BASE_NS::vector<BASE_NS::pair<BASE_NS::string, int>> keyValVec; 210 keyValVec.push_back({ "First", 10 }); 211 keyValVec.push_back({ "Third", 0 }); 212 keyValVec.push_back({ "Second", 500 }); 213 214 // Iterator pointing to begining of map 215 unordered_map<BASE_NS::string, int>::iterator it = string_int.begin(); 216 // Iterate over the map using iterator 217 size_t count = 0; 218 while (it != string_int.end()) { 219 ASSERT_STREQ(it->first.c_str(), keyValVec[count].first.c_str()); 220 ASSERT_EQ((*it).second, keyValVec[count].second); 221 ++it; 222 // it++ not supported 223 count++; 224 } 225 226 // Iterate using range-based for loop 227 count = 0; 228 for (BASE_NS::pair<const BASE_NS::string, int> element : string_int) { 229 ASSERT_EQ(element.first, keyValVec[count].first); 230 ASSERT_EQ(element.second, keyValVec[count].second); 231 count++; 232 } 233 234 // Iterate for loop using begin() and end() 235 for (auto iter = string_int.begin(); iter != string_int.end(); ++iter) { 236 auto cur = iter->first; 237 string_int[cur] = 7; 238 } 239 ASSERT_EQ(string_int[string_view("First")], 7); 240 ASSERT_EQ(string_int[string_view("Second")], 7); 241 ASSERT_EQ(string_int[string_view("Third")], 7); 242 } 243 244 HWTEST_F(UnorderedMapTest, Modifiers001, TestSize.Level1) 245 { 246 auto original = unordered_map<int, int>(); 247 // Insert 248 original.insert({ 15, 0 }); 249 original.insert({ 20, 15 }); 250 original.insert({ 70, 77 }); 251 ASSERT_EQ(original[15], 0); 252 ASSERT_EQ(original[20], 15); 253 ASSERT_EQ(original[70], 77); 254 // Assign value to a key that already exists using "insert" 255 ASSERT_NO_FATAL_FAILURE(original.insert({ 70, 80 })); 256 // Confirm no value change for already existing key 257 ASSERT_EQ(original[70], 77); 258 259 // Insert or Assign 260 original.insert_or_assign(15, 500); 261 original.insert_or_assign(25, 2500); 262 ASSERT_EQ(original[15], 500); 263 ASSERT_EQ(original[25], 2500); 264 ASSERT_EQ(original[20], 15); 265 ASSERT_EQ(original[70], 77); 266 } 267 268 HWTEST_F(UnorderedMapTest, Modifiers002, TestSize.Level1) 269 { 270 auto strMap = unordered_map<int, BASE_NS::string>(); 271 { 272 BASE_NS::string lvalue = "lvalue"; 273 const BASE_NS::string constLvalue = "const lvalue"; 274 275 auto insertedLvalue = strMap.insert_or_assign(0, lvalue); 276 EXPECT_EQ(insertedLvalue.first->second, lvalue); 277 EXPECT_TRUE(insertedLvalue.second); 278 279 auto insertedConstLvalue = strMap.insert_or_assign(1, constLvalue); 280 EXPECT_EQ(insertedConstLvalue.first->second, constLvalue); 281 EXPECT_TRUE(insertedConstLvalue.second); 282 283 auto insertedRvalue = strMap.insert_or_assign(2, BASE_NS::string("rvalue")); 284 EXPECT_EQ(insertedRvalue.first->second, "rvalue"); 285 EXPECT_TRUE(insertedRvalue.second); 286 } 287 { 288 BASE_NS::string lvalue = "lvalue"; 289 const BASE_NS::string constLvalue = "const lvalue"; 290 291 auto assignedLvalue = strMap.insert_or_assign(0, lvalue); 292 EXPECT_EQ(assignedLvalue.first->second, lvalue); 293 EXPECT_FALSE(assignedLvalue.second); 294 295 auto assignedConstLvalue = strMap.insert_or_assign(1, constLvalue); 296 EXPECT_EQ(assignedConstLvalue.first->second, constLvalue); 297 EXPECT_FALSE(assignedConstLvalue.second); 298 299 auto assignedRvalue = strMap.insert_or_assign(2, BASE_NS::string("rvalue")); 300 EXPECT_EQ(assignedRvalue.first->second, "rvalue"); 301 EXPECT_FALSE(assignedRvalue.second); 302 } 303 } 304 305 HWTEST_F(UnorderedMapTest, Modifiers003, TestSize.Level1) 306 { 307 auto original = unordered_map<int, int>(); 308 // Insert 309 original.insert({ 15, 0 }); 310 original.insert({ 20, 15 }); 311 original.insert({ 70, 77 }); 312 // Insert or Assign 313 original.insert_or_assign(15, 500); 314 original.insert_or_assign(25, 2500); 315 // Erase using key 316 ASSERT_EQ(original.erase(16), 0u); 317 ASSERT_EQ(original.erase(15), 1u); 318 ASSERT_EQ(original.size(), 3); 319 ASSERT_EQ(original.erase(15), 0u); 320 321 // Erase using iterator 322 original.erase(original.begin()); 323 ASSERT_EQ(original.size(), 2); 324 325 // Add more elements 326 original.insert({ 44, -80 }); 327 original.insert({ 55, 80 }); 328 ASSERT_EQ(original.size(), 4); 329 330 // Extract 331 auto currentNodeHandle = original.extract(20); 332 ASSERT_FALSE(currentNodeHandle.empty()); 333 ASSERT_EQ(currentNodeHandle.key(), 20); 334 ASSERT_EQ(currentNodeHandle.mapped(), 15); 335 ASSERT_EQ(currentNodeHandle.pointer->data.first, 20); 336 ASSERT_EQ(currentNodeHandle.pointer->data.second, 15); 337 338 // Not existing 339 ASSERT_EQ(original[90], false); 340 341 // Clear 342 original.clear(); 343 ASSERT_EQ(original.size(), 0); 344 345 // Add node 346 original.insert(move(currentNodeHandle)); 347 ASSERT_EQ(original[20], 15); 348 } 349 350 HWTEST_F(UnorderedMapTest, Lookup, TestSize.Level1) 351 { 352 auto string_int = unordered_map<BASE_NS::string, int>(); 353 string_int.insert({ "First", 10 }); 354 string_int.insert({ "Second", 456 }); 355 string_int.insert({ "Third", 0 }); 356 357 // Find 358 unordered_map<BASE_NS::string, int>::const_iterator got = string_int.find("Second"); 359 ASSERT_EQ(got->first, "Second"); 360 ASSERT_EQ(got->second, 456); 361 got = string_int.find("None"); 362 ASSERT_FALSE(got != string_int.end()); 363 364 const unordered_map<BASE_NS::string, int>::const_iterator cGot = string_int.find("Third"); 365 ASSERT_EQ(cGot->first, "Third"); 366 ASSERT_EQ(cGot->second, 0); 367 368 // Count 369 ASSERT_EQ(string_int.count("First"), 1); 370 ASSERT_EQ(string_int.count("Third"), 1); 371 ASSERT_EQ(string_int.count("None"), 0); 372 373 // Contains 374 ASSERT_TRUE(string_int.contains("First")); 375 ASSERT_TRUE(string_int.contains("Third")); 376 ASSERT_FALSE(string_int.contains("None")); 377 } 378 379 HWTEST_F(UnorderedMapTest, ExtractInsertBug, TestSize.Level1) 380 { 381 auto original = unordered_map<int, int>(); 382 original.insert({ 20, 15 }); 383 384 // This is a bit brittle and will break if implementation changes. Find a key which will have the same bucket index 385 // as 20. __anonaf2356a70102(int key) 386 auto bucketIndex = [](int key) { 387 constexpr auto defaultShiftAmount = 4U; 388 constexpr uint64_t GOLDEN_RATIO_64 = 0x9E3779B97F4A7C15ull; 389 constexpr uint64_t shift = 64u - defaultShiftAmount; 390 uint64_t h = hash(key); 391 h ^= h >> shift; 392 return static_cast<uint32_t>(((GOLDEN_RATIO_64 * h) >> shift)); 393 }; 394 const auto index20 = bucketIndex(20); 395 int key = 0; 396 for (uint32_t index = bucketIndex(key); index != index20; index = bucketIndex(++key)) { 397 } 398 399 original.insert({ key, 81 }); 400 401 // Extract 402 auto currentNodeHandle = original.extract(20); 403 ASSERT_FALSE(currentNodeHandle.empty()); 404 405 // Clear 406 original.clear(); 407 ASSERT_EQ(original.size(), 0); 408 409 // Add node 410 ASSERT_TRUE(original.insert(move(currentNodeHandle)).inserted); 411 ASSERT_EQ(original.size(), 1); 412 413 // Bug check: If the same bucket had multiple entries and one was extracted it's prev/next pointers were not 414 // cleared. Due to the dangling prev pointer the second extract would update an invalid address to null and the 415 // bucket would still point to the node. Inserting the node would find a match with the key and the node wasn't 416 // added and there was a size mismatch. 417 currentNodeHandle = original.extract(20); 418 ASSERT_EQ(original.size(), 0); 419 ASSERT_FALSE(currentNodeHandle.empty()); 420 ASSERT_TRUE(original.insert(move(currentNodeHandle)).inserted); 421 ASSERT_EQ(original.size(), 1); 422 } 423 424 HWTEST_F(UnorderedMapTest, ExtractInsertBug02, TestSize.Level1) 425 { 426 auto map = unordered_map<uint64_t, uint64_t>(); 427 428 constexpr uint64_t id1 = 0x300000011; 429 constexpr uint64_t id2 = 0x200000059; 430 constexpr uint64_t id3 = 0x10000007f; 431 432 map[id1] = 1; 433 map[id2] = 2; 434 map[id3] = 3; 435 map.erase(id2); 436 map.erase(id1); 437 438 ASSERT_TRUE(map.find(id1) == map.end()); // Should not be in the map. 439 ASSERT_TRUE(map.find(id2) == map.end()); // Should not be in the map. 440 ASSERT_TRUE(map.find(id3) != map.end()); // Should still be in the map. 441 } 442 443 HWTEST_F(UnorderedMapTest, StringView001, TestSize.Level1) 444 { 445 unordered_map<BASE_NS::string, int> string_int = unordered_map<BASE_NS::string, int>(); 446 const string_view fifth = "Fifth"; 447 string_int.insert({ fifth, 345 }); 448 const string_view sixth = "Sixth"; 449 const BASE_NS::pair<string_view, int> sixth_pair = { sixth, 6 }; 450 string_int.insert(sixth_pair); 451 452 ASSERT_EQ(string_int[fifth], 345); 453 ASSERT_EQ(string_int[sixth], 6); 454 455 ASSERT_EQ((string_int.insert({ fifth, 345 })).second, false); 456 ASSERT_EQ((string_int.insert(sixth_pair)).second, false); 457 458 { 459 BASE_NS::unordered_map_iterator<unordered_map_base<BASE_NS::string, int>> findRes = string_int.find(fifth); 460 ASSERT_EQ(findRes->first, fifth); 461 ASSERT_EQ(findRes->second, 345); 462 } 463 { 464 const auto string_int_C = string_int; 465 const auto findRes = string_int_C.find(fifth); 466 ASSERT_EQ(findRes->first, fifth); 467 ASSERT_EQ(findRes->second, 345); 468 } 469 } 470 471 HWTEST_F(UnorderedMapTest, StringView002, TestSize.Level1) 472 { 473 unordered_map<BASE_NS::string, int> string_int; 474 const string_view fifth = "Fifth"; 475 string_int.insert({ fifth, 345 }); 476 477 ASSERT_EQ(true, string_int.contains(fifth)); 478 ASSERT_EQ(1, string_int.count(fifth)); 479 EXPECT_EQ(1, string_int.erase(fifth)); 480 EXPECT_EQ(0, string_int.erase(fifth)); 481 ASSERT_EQ(false, string_int.contains(fifth)); 482 ASSERT_EQ(0, string_int.contains(fifth)); 483 484 { 485 BASE_NS::unordered_map_iterator<unordered_map_base<BASE_NS::string, int>> findRes = string_int.find(fifth); 486 ASSERT_FALSE(findRes != string_int.end()); 487 } 488 { 489 const auto string_int_C = string_int; 490 const auto findRes = string_int_C.find(fifth); 491 ASSERT_FALSE(findRes != string_int_C.end()); 492 } 493 ASSERT_EQ(string_int[fifth], false); 494 // Checking element on existance adds it to unordered_map with false value 495 ASSERT_EQ(string_int[fifth], false); 496 ASSERT_EQ(true, string_int.contains(fifth)); 497 ASSERT_EQ(1, string_int.count(fifth)); 498 string_int.insert({ fifth, 345 }); 499 // As a result adding it with proper key will not overrite it 500 ASSERT_EQ(1, string_int.count(fifth)); 501 ASSERT_EQ(string_int[fifth], false); 502 string_int[fifth] = 345; 503 ASSERT_EQ(string_int[fifth], 345); 504 } 505 506 HWTEST_F(UnorderedMapTest, StringView003, TestSize.Level1) 507 { 508 unordered_map<BASE_NS::string, int> string_int; 509 const string_view fifth = "Fifth"; 510 string_int.insert({ fifth, 345 }); 511 static constexpr auto seventh = string_view { "Seventh" }; 512 auto inserted = string_int.insert_or_assign(seventh, 346); 513 EXPECT_EQ(inserted.first->first, seventh); 514 EXPECT_EQ(inserted.first->second, 346); 515 EXPECT_TRUE(inserted.second); 516 517 auto assigned = string_int.insert_or_assign(seventh, 347); 518 EXPECT_EQ(assigned.first->first, seventh); 519 EXPECT_EQ(assigned.first->second, 347); 520 EXPECT_FALSE(assigned.second); 521 522 { 523 // as node is not inserted back into the container we expect it to be properly cleaned up. 524 auto node = string_int.extract(Base::string(fifth)); 525 EXPECT_EQ(node.key(), fifth); 526 node = string_int.extract(Base::string(seventh)); 527 EXPECT_EQ(node.key(), seventh); 528 } 529 }