594 lines · cpp
1//===- unittest/ADT/MapVectorTest.cpp - MapVector unit tests ----*- C++ -*-===//2//3// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.4// See https://llvm.org/LICENSE.txt for license information.5// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception6//7//===----------------------------------------------------------------------===//8 9#include "llvm/ADT/MapVector.h"10#include "llvm/ADT/ArrayRef.h"11#include "llvm/ADT/iterator_range.h"12#include "gmock/gmock.h"13#include "gtest/gtest.h"14#include <memory>15#include <utility>16 17using namespace llvm;18 19namespace {20struct CountCopyAndMove {21 CountCopyAndMove() = default;22 CountCopyAndMove(const CountCopyAndMove &) { copy = 1; }23 CountCopyAndMove(CountCopyAndMove &&) { move = 1; }24 void operator=(const CountCopyAndMove &) { ++copy; }25 void operator=(CountCopyAndMove &&) { ++move; }26 int copy = 0;27 int move = 0;28};29 30struct A : CountCopyAndMove {31 A(int v) : v(v) {}32 int v;33};34} // namespace35 36namespace llvm {37template <> struct DenseMapInfo<A> {38 static inline A getEmptyKey() { return 0x7fffffff; }39 static inline A getTombstoneKey() { return -0x7fffffff - 1; }40 static unsigned getHashValue(const A &Val) { return (unsigned)(Val.v * 37U); }41 static bool isEqual(const A &LHS, const A &RHS) { return LHS.v == RHS.v; }42};43} // namespace llvm44 45namespace {46TEST(MapVectorTest, swap) {47 MapVector<int, int> MV1, MV2;48 std::pair<MapVector<int, int>::iterator, bool> R;49 50 R = MV1.insert(std::make_pair(1, 2));51 ASSERT_EQ(R.first, MV1.begin());52 EXPECT_EQ(R.first->first, 1);53 EXPECT_EQ(R.first->second, 2);54 EXPECT_TRUE(R.second);55 56 EXPECT_FALSE(MV1.empty());57 EXPECT_TRUE(MV2.empty());58 MV2.swap(MV1);59 EXPECT_TRUE(MV1.empty());60 EXPECT_FALSE(MV2.empty());61 62 auto I = MV1.find(1);63 ASSERT_EQ(MV1.end(), I);64 65 I = MV2.find(1);66 ASSERT_EQ(I, MV2.begin());67 EXPECT_EQ(I->first, 1);68 EXPECT_EQ(I->second, 2);69}70 71TEST(MapVectorTest, insert_pop) {72 MapVector<int, int> MV;73 std::pair<MapVector<int, int>::iterator, bool> R;74 75 R = MV.insert(std::make_pair(1, 2));76 ASSERT_EQ(R.first, MV.begin());77 EXPECT_EQ(R.first->first, 1);78 EXPECT_EQ(R.first->second, 2);79 EXPECT_TRUE(R.second);80 81 R = MV.insert(std::make_pair(1, 3));82 ASSERT_EQ(R.first, MV.begin());83 EXPECT_EQ(R.first->first, 1);84 EXPECT_EQ(R.first->second, 2);85 EXPECT_FALSE(R.second);86 87 R = MV.insert(std::make_pair(4, 5));88 ASSERT_NE(R.first, MV.end());89 EXPECT_EQ(R.first->first, 4);90 EXPECT_EQ(R.first->second, 5);91 EXPECT_TRUE(R.second);92 93 EXPECT_EQ(MV.size(), 2u);94 EXPECT_EQ(MV[1], 2);95 EXPECT_EQ(MV[4], 5);96 97 MV.pop_back();98 EXPECT_EQ(MV.size(), 1u);99 EXPECT_EQ(MV[1], 2);100 101 R = MV.insert(std::make_pair(4, 7));102 ASSERT_NE(R.first, MV.end());103 EXPECT_EQ(R.first->first, 4);104 EXPECT_EQ(R.first->second, 7);105 EXPECT_TRUE(R.second);106 107 EXPECT_EQ(MV.size(), 2u);108 EXPECT_EQ(MV[1], 2);109 EXPECT_EQ(MV[4], 7);110}111 112TEST(MapVectorTest, try_emplace) {113 struct AAndU {114 A a;115 std::unique_ptr<int> b;116 AAndU(A a, std::unique_ptr<int> b) : a(a), b(std::move(b)) {}117 };118 MapVector<A, AAndU> mv;119 120 A zero(0);121 auto try0 = mv.try_emplace(zero, zero, nullptr);122 EXPECT_TRUE(try0.second);123 EXPECT_EQ(0, try0.first->second.a.v);124 EXPECT_EQ(1, try0.first->second.a.copy);125 EXPECT_EQ(0, try0.first->second.a.move);126 127 auto try1 = mv.try_emplace(zero, zero, nullptr);128 EXPECT_FALSE(try1.second);129 EXPECT_EQ(0, try1.first->second.a.v);130 EXPECT_EQ(1, try1.first->second.a.copy);131 EXPECT_EQ(0, try1.first->second.a.move);132 133 EXPECT_EQ(try0.first, try1.first);134 EXPECT_EQ(1, try1.first->first.copy);135 EXPECT_EQ(0, try1.first->first.move);136 137 A two(2);138 auto try2 = mv.try_emplace(2, std::move(two), std::make_unique<int>(2));139 EXPECT_TRUE(try2.second);140 EXPECT_EQ(2, try2.first->second.a.v);141 EXPECT_EQ(0, try2.first->second.a.move);142 143 std::unique_ptr<int> p(new int(3));144 auto try3 = mv.try_emplace(std::move(two), 3, std::move(p));145 EXPECT_FALSE(try3.second);146 EXPECT_EQ(2, try3.first->second.a.v);147 EXPECT_EQ(1, try3.first->second.a.copy);148 EXPECT_EQ(0, try3.first->second.a.move);149 150 EXPECT_EQ(try2.first, try3.first);151 EXPECT_EQ(0, try3.first->first.copy);152 EXPECT_EQ(1, try3.first->first.move);153 EXPECT_NE(nullptr, p);154}155 156TEST(MapVectorTest, insert_or_assign) {157 MapVector<A, A> mv;158 159 A zero(0);160 auto try0 = mv.insert_or_assign(zero, zero);161 EXPECT_TRUE(try0.second);162 EXPECT_EQ(0, try0.first->second.v);163 EXPECT_EQ(1, try0.first->second.copy);164 EXPECT_EQ(0, try0.first->second.move);165 166 auto try1 = mv.insert_or_assign(zero, zero);167 EXPECT_FALSE(try1.second);168 EXPECT_EQ(0, try1.first->second.v);169 EXPECT_EQ(2, try1.first->second.copy);170 EXPECT_EQ(0, try1.first->second.move);171 172 EXPECT_EQ(try0.first, try1.first);173 EXPECT_EQ(1, try1.first->first.copy);174 EXPECT_EQ(0, try1.first->first.move);175 176 A two(2);177 auto try2 = mv.try_emplace(2, std::move(two));178 EXPECT_TRUE(try2.second);179 EXPECT_EQ(2, try2.first->second.v);180 EXPECT_EQ(1, try2.first->second.move);181 182 auto try3 = mv.insert_or_assign(std::move(two), 3);183 EXPECT_FALSE(try3.second);184 EXPECT_EQ(3, try3.first->second.v);185 EXPECT_EQ(0, try3.first->second.copy);186 EXPECT_EQ(2, try3.first->second.move);187 188 EXPECT_EQ(try2.first, try3.first);189 EXPECT_EQ(0, try3.first->first.copy);190 EXPECT_EQ(1, try3.first->first.move);191}192 193TEST(MapVectorTest, erase) {194 MapVector<int, int> MV;195 196 MV.insert(std::make_pair(1, 2));197 MV.insert(std::make_pair(3, 4));198 MV.insert(std::make_pair(5, 6));199 ASSERT_EQ(MV.size(), 3u);200 201 ASSERT_TRUE(MV.contains(1));202 MV.erase(MV.find(1));203 ASSERT_EQ(MV.size(), 2u);204 ASSERT_FALSE(MV.contains(1));205 ASSERT_EQ(MV.find(1), MV.end());206 ASSERT_EQ(MV[3], 4);207 ASSERT_EQ(MV[5], 6);208 209 ASSERT_EQ(MV.erase(3), 1u);210 ASSERT_EQ(MV.size(), 1u);211 ASSERT_EQ(MV.find(3), MV.end());212 ASSERT_EQ(MV[5], 6);213 214 ASSERT_EQ(MV.erase(79), 0u);215 ASSERT_EQ(MV.size(), 1u);216}217 218TEST(MapVectorTest, remove_if) {219 MapVector<int, int> MV;220 221 MV.insert(std::make_pair(1, 11));222 MV.insert(std::make_pair(2, 12));223 MV.insert(std::make_pair(3, 13));224 MV.insert(std::make_pair(4, 14));225 MV.insert(std::make_pair(5, 15));226 MV.insert(std::make_pair(6, 16));227 ASSERT_EQ(MV.size(), 6u);228 229 MV.remove_if([](const std::pair<int, int> &Val) { return Val.second % 2; });230 ASSERT_EQ(MV.size(), 3u);231 ASSERT_EQ(MV.find(1), MV.end());232 ASSERT_EQ(MV.find(3), MV.end());233 ASSERT_EQ(MV.find(5), MV.end());234 ASSERT_EQ(MV[2], 12);235 ASSERT_EQ(MV[4], 14);236 ASSERT_EQ(MV[6], 16);237}238 239TEST(MapVectorTest, iteration_test) {240 MapVector<int, int> MV;241 242 MV.insert(std::make_pair(1, 11));243 MV.insert(std::make_pair(2, 12));244 MV.insert(std::make_pair(3, 13));245 MV.insert(std::make_pair(4, 14));246 MV.insert(std::make_pair(5, 15));247 MV.insert(std::make_pair(6, 16));248 ASSERT_EQ(MV.size(), 6u);249 250 int count = 1;251 for (auto P : make_range(MV.begin(), MV.end())) {252 ASSERT_EQ(P.first, count);253 count++;254 }255 256 count = 6;257 for (auto P : make_range(MV.rbegin(), MV.rend())) {258 ASSERT_EQ(P.first, count);259 count--;260 }261}262 263TEST(MapVectorTest, NonCopyable) {264 MapVector<int, std::unique_ptr<int>> MV;265 MV.insert(std::make_pair(1, std::make_unique<int>(1)));266 MV.insert(std::make_pair(2, std::make_unique<int>(2)));267 268 ASSERT_EQ(MV.count(1), 1u);269 ASSERT_EQ(*MV.find(2)->second, 2);270}271 272TEST(MapVectorTest, GetArrayRef) {273 MapVector<int, int> MV;274 275 // The underlying vector is empty to begin with.276 EXPECT_TRUE(MV.getArrayRef().empty());277 278 // Test inserted element.279 MV.insert(std::make_pair(100, 99));280 EXPECT_TRUE(MV.getArrayRef().equals({std::pair(100, 99)}));281 282 // Inserting a different element for an existing key won't change the283 // underlying vector.284 auto [Iter, Inserted] = MV.try_emplace(100, 98);285 EXPECT_FALSE(Inserted);286 EXPECT_EQ(Iter->second, 99);287 EXPECT_TRUE(MV.getArrayRef().equals({std::pair(100, 99)}));288 289 // Inserting a new element. Tests that elements are in order in the underlying290 // array.291 MV.insert(std::make_pair(99, 98));292 EXPECT_TRUE(MV.getArrayRef().equals({std::pair(100, 99), std::pair(99, 98)}));293}294 295TEST(MapVectorTest, AtTest) {296 MapVector<int, int> MV;297 MV[0] = 10;298 MV[1] = 11;299 EXPECT_EQ(MV.at(0), 10);300 EXPECT_EQ(MV.at(1), 11);301 302 MV.at(1) = 12;303 EXPECT_EQ(MV.at(1), 12);304 305 const auto &ConstMV = MV;306 EXPECT_EQ(ConstMV.at(0), 10);307 EXPECT_EQ(ConstMV.at(1), 12);308}309 310TEST(MapVectorTest, KeysValuesIterator) {311 MapVector<int, int> MV;312 313 MV.insert(std::make_pair(1, 11));314 MV.insert(std::make_pair(2, 12));315 MV.insert(std::make_pair(3, 13));316 MV.insert(std::make_pair(4, 14));317 MV.insert(std::make_pair(5, 15));318 MV.insert(std::make_pair(6, 16));319 320 EXPECT_THAT(MV.keys(), testing::ElementsAre(1, 2, 3, 4, 5, 6));321 EXPECT_THAT(MV.values(), testing::ElementsAre(11, 12, 13, 14, 15, 16));322 323 const MapVector<int, int> &ConstMV = MV;324 EXPECT_THAT(ConstMV.keys(), testing::ElementsAre(1, 2, 3, 4, 5, 6));325 EXPECT_THAT(ConstMV.values(), testing::ElementsAre(11, 12, 13, 14, 15, 16));326}327 328template <class IntType> struct MapVectorMappedTypeTest : ::testing::Test {329 using int_type = IntType;330};331 332using MapIntTypes = ::testing::Types<int, long, long long, unsigned,333 unsigned long, unsigned long long>;334TYPED_TEST_SUITE(MapVectorMappedTypeTest, MapIntTypes, );335 336TYPED_TEST(MapVectorMappedTypeTest, DifferentDenseMap) {337 // Test that using a map with a mapped type other than 'unsigned' compiles338 // and works.339 using IntType = typename TestFixture::int_type;340 using MapVectorType = MapVector<int, int, DenseMap<int, IntType>>;341 342 MapVectorType MV;343 std::pair<typename MapVectorType::iterator, bool> R;344 345 R = MV.insert(std::make_pair(1, 2));346 ASSERT_EQ(R.first, MV.begin());347 EXPECT_EQ(R.first->first, 1);348 EXPECT_EQ(R.first->second, 2);349 EXPECT_TRUE(R.second);350 351 const std::pair<int, int> Elem(1, 3);352 R = MV.insert(Elem);353 ASSERT_EQ(R.first, MV.begin());354 EXPECT_EQ(R.first->first, 1);355 EXPECT_EQ(R.first->second, 2);356 EXPECT_FALSE(R.second);357 358 int& value = MV[4];359 EXPECT_EQ(value, 0);360 value = 5;361 362 EXPECT_EQ(MV.size(), 2u);363 EXPECT_EQ(MV[1], 2);364 EXPECT_EQ(MV[4], 5);365}366 367TEST(SmallMapVectorSmallTest, insert_pop) {368 SmallMapVector<int, int, 32> MV;369 std::pair<SmallMapVector<int, int, 32>::iterator, bool> R;370 371 R = MV.insert(std::make_pair(1, 2));372 ASSERT_EQ(R.first, MV.begin());373 EXPECT_EQ(R.first->first, 1);374 EXPECT_EQ(R.first->second, 2);375 EXPECT_TRUE(R.second);376 377 R = MV.insert(std::make_pair(1, 3));378 ASSERT_EQ(R.first, MV.begin());379 EXPECT_EQ(R.first->first, 1);380 EXPECT_EQ(R.first->second, 2);381 EXPECT_FALSE(R.second);382 383 R = MV.insert(std::make_pair(4, 5));384 ASSERT_NE(R.first, MV.end());385 EXPECT_EQ(R.first->first, 4);386 EXPECT_EQ(R.first->second, 5);387 EXPECT_TRUE(R.second);388 389 EXPECT_EQ(MV.size(), 2u);390 EXPECT_EQ(MV[1], 2);391 EXPECT_EQ(MV[4], 5);392 393 MV.pop_back();394 EXPECT_EQ(MV.size(), 1u);395 EXPECT_EQ(MV[1], 2);396 397 R = MV.insert(std::make_pair(4, 7));398 ASSERT_NE(R.first, MV.end());399 EXPECT_EQ(R.first->first, 4);400 EXPECT_EQ(R.first->second, 7);401 EXPECT_TRUE(R.second);402 403 EXPECT_EQ(MV.size(), 2u);404 EXPECT_EQ(MV[1], 2);405 EXPECT_EQ(MV[4], 7);406}407 408TEST(SmallMapVectorSmallTest, erase) {409 SmallMapVector<int, int, 32> MV;410 411 MV.insert(std::make_pair(1, 2));412 MV.insert(std::make_pair(3, 4));413 MV.insert(std::make_pair(5, 6));414 ASSERT_EQ(MV.size(), 3u);415 416 MV.erase(MV.find(1));417 ASSERT_EQ(MV.size(), 2u);418 ASSERT_EQ(MV.find(1), MV.end());419 ASSERT_EQ(MV[3], 4);420 ASSERT_EQ(MV[5], 6);421 422 ASSERT_EQ(MV.erase(3), 1u);423 ASSERT_EQ(MV.size(), 1u);424 ASSERT_EQ(MV.find(3), MV.end());425 ASSERT_EQ(MV[5], 6);426 427 ASSERT_EQ(MV.erase(79), 0u);428 ASSERT_EQ(MV.size(), 1u);429}430 431TEST(SmallMapVectorSmallTest, remove_if) {432 SmallMapVector<int, int, 32> MV;433 434 MV.insert(std::make_pair(1, 11));435 MV.insert(std::make_pair(2, 12));436 MV.insert(std::make_pair(3, 13));437 MV.insert(std::make_pair(4, 14));438 MV.insert(std::make_pair(5, 15));439 MV.insert(std::make_pair(6, 16));440 ASSERT_EQ(MV.size(), 6u);441 442 MV.remove_if([](const std::pair<int, int> &Val) { return Val.second % 2; });443 ASSERT_EQ(MV.size(), 3u);444 ASSERT_EQ(MV.find(1), MV.end());445 ASSERT_EQ(MV.find(3), MV.end());446 ASSERT_EQ(MV.find(5), MV.end());447 ASSERT_EQ(MV[2], 12);448 ASSERT_EQ(MV[4], 14);449 ASSERT_EQ(MV[6], 16);450}451 452TEST(SmallMapVectorSmallTest, iteration_test) {453 SmallMapVector<int, int, 32> MV;454 455 MV.insert(std::make_pair(1, 11));456 MV.insert(std::make_pair(2, 12));457 MV.insert(std::make_pair(3, 13));458 MV.insert(std::make_pair(4, 14));459 MV.insert(std::make_pair(5, 15));460 MV.insert(std::make_pair(6, 16));461 ASSERT_EQ(MV.size(), 6u);462 463 int count = 1;464 for (auto P : make_range(MV.begin(), MV.end())) {465 ASSERT_EQ(P.first, count);466 count++;467 }468 469 count = 6;470 for (auto P : make_range(MV.rbegin(), MV.rend())) {471 ASSERT_EQ(P.first, count);472 count--;473 }474}475 476TEST(SmallMapVectorSmallTest, NonCopyable) {477 SmallMapVector<int, std::unique_ptr<int>, 8> MV;478 MV.insert(std::make_pair(1, std::make_unique<int>(1)));479 MV.insert(std::make_pair(2, std::make_unique<int>(2)));480 481 ASSERT_EQ(MV.count(1), 1u);482 ASSERT_EQ(*MV.find(2)->second, 2);483}484 485TEST(SmallMapVectorLargeTest, insert_pop) {486 SmallMapVector<int, int, 1> MV;487 std::pair<SmallMapVector<int, int, 1>::iterator, bool> R;488 489 R = MV.insert(std::make_pair(1, 2));490 ASSERT_EQ(R.first, MV.begin());491 EXPECT_EQ(R.first->first, 1);492 EXPECT_EQ(R.first->second, 2);493 EXPECT_TRUE(R.second);494 495 R = MV.insert(std::make_pair(1, 3));496 ASSERT_EQ(R.first, MV.begin());497 EXPECT_EQ(R.first->first, 1);498 EXPECT_EQ(R.first->second, 2);499 EXPECT_FALSE(R.second);500 501 R = MV.insert(std::make_pair(4, 5));502 ASSERT_NE(R.first, MV.end());503 EXPECT_EQ(R.first->first, 4);504 EXPECT_EQ(R.first->second, 5);505 EXPECT_TRUE(R.second);506 507 EXPECT_EQ(MV.size(), 2u);508 EXPECT_EQ(MV[1], 2);509 EXPECT_EQ(MV[4], 5);510 511 MV.pop_back();512 EXPECT_EQ(MV.size(), 1u);513 EXPECT_EQ(MV[1], 2);514 515 R = MV.insert(std::make_pair(4, 7));516 ASSERT_NE(R.first, MV.end());517 EXPECT_EQ(R.first->first, 4);518 EXPECT_EQ(R.first->second, 7);519 EXPECT_TRUE(R.second);520 521 EXPECT_EQ(MV.size(), 2u);522 EXPECT_EQ(MV[1], 2);523 EXPECT_EQ(MV[4], 7);524}525 526TEST(SmallMapVectorLargeTest, erase) {527 SmallMapVector<int, int, 1> MV;528 529 MV.insert(std::make_pair(1, 2));530 MV.insert(std::make_pair(3, 4));531 MV.insert(std::make_pair(5, 6));532 ASSERT_EQ(MV.size(), 3u);533 534 MV.erase(MV.find(1));535 ASSERT_EQ(MV.size(), 2u);536 ASSERT_EQ(MV.find(1), MV.end());537 ASSERT_EQ(MV[3], 4);538 ASSERT_EQ(MV[5], 6);539 540 ASSERT_EQ(MV.erase(3), 1u);541 ASSERT_EQ(MV.size(), 1u);542 ASSERT_EQ(MV.find(3), MV.end());543 ASSERT_EQ(MV[5], 6);544 545 ASSERT_EQ(MV.erase(79), 0u);546 ASSERT_EQ(MV.size(), 1u);547}548 549TEST(SmallMapVectorLargeTest, remove_if) {550 SmallMapVector<int, int, 1> MV;551 552 MV.insert(std::make_pair(1, 11));553 MV.insert(std::make_pair(2, 12));554 MV.insert(std::make_pair(3, 13));555 MV.insert(std::make_pair(4, 14));556 MV.insert(std::make_pair(5, 15));557 MV.insert(std::make_pair(6, 16));558 ASSERT_EQ(MV.size(), 6u);559 560 MV.remove_if([](const std::pair<int, int> &Val) { return Val.second % 2; });561 ASSERT_EQ(MV.size(), 3u);562 ASSERT_EQ(MV.find(1), MV.end());563 ASSERT_EQ(MV.find(3), MV.end());564 ASSERT_EQ(MV.find(5), MV.end());565 ASSERT_EQ(MV[2], 12);566 ASSERT_EQ(MV[4], 14);567 ASSERT_EQ(MV[6], 16);568}569 570TEST(SmallMapVectorLargeTest, iteration_test) {571 SmallMapVector<int, int, 1> MV;572 573 MV.insert(std::make_pair(1, 11));574 MV.insert(std::make_pair(2, 12));575 MV.insert(std::make_pair(3, 13));576 MV.insert(std::make_pair(4, 14));577 MV.insert(std::make_pair(5, 15));578 MV.insert(std::make_pair(6, 16));579 ASSERT_EQ(MV.size(), 6u);580 581 int count = 1;582 for (auto P : make_range(MV.begin(), MV.end())) {583 ASSERT_EQ(P.first, count);584 count++;585 }586 587 count = 6;588 for (auto P : make_range(MV.rbegin(), MV.rend())) {589 ASSERT_EQ(P.first, count);590 count--;591 }592}593} // namespace594