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