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 <utility>
  13
  14 using namespace llvm;
  15
  16 TEST(MapVectorTest, swap) {
  17   MapVector<int, int> MV1, MV2;
  18   std::pair<MapVector<int, int>::iterator, bool> R;
  19
  20   R = MV1.insert(std::make_pair(1, 2));
  21   ASSERT_EQ(R.first, MV1.begin());
  22   EXPECT_EQ(R.first->first, 1);
  23   EXPECT_EQ(R.first->second, 2);
  24   EXPECT_TRUE(R.second);
  25
  26   EXPECT_FALSE(MV1.empty());
  27   EXPECT_TRUE(MV2.empty());
  28   MV2.swap(MV1);
  29   EXPECT_TRUE(MV1.empty());
  30   EXPECT_FALSE(MV2.empty());
  31
  32   auto I = MV1.find(1);
  33   ASSERT_EQ(MV1.end(), I);
  34
  35   I = MV2.find(1);
  36   ASSERT_EQ(I, MV2.begin());
  37   EXPECT_EQ(I->first, 1);
  38   EXPECT_EQ(I->second, 2);
  39 }
  40
  41 TEST(MapVectorTest, insert_pop) {
  42   MapVector<int, int> MV;
  43   std::pair<MapVector<int, int>::iterator, bool> R;
  44
  45   R = MV.insert(std::make_pair(1, 2));
  46   ASSERT_EQ(R.first, MV.begin());
  47   EXPECT_EQ(R.first->first, 1);
  48   EXPECT_EQ(R.first->second, 2);
  49   EXPECT_TRUE(R.second);
  50
  51   R = MV.insert(std::make_pair(1, 3));
  52   ASSERT_EQ(R.first, MV.begin());
  53   EXPECT_EQ(R.first->first, 1);
  54   EXPECT_EQ(R.first->second, 2);
  55   EXPECT_FALSE(R.second);
  56
  57   R = MV.insert(std::make_pair(4, 5));
  58   ASSERT_NE(R.first, MV.end());
  59   EXPECT_EQ(R.first->first, 4);
  60   EXPECT_EQ(R.first->second, 5);
  61   EXPECT_TRUE(R.second);
  62
  63   EXPECT_EQ(MV.size(), 2u);
  64   EXPECT_EQ(MV[1], 2);
  65   EXPECT_EQ(MV[4], 5);
  66
  67   MV.pop_back();
  68   EXPECT_EQ(MV.size(), 1u);
  69   EXPECT_EQ(MV[1], 2);
  70
  71   R = MV.insert(std::make_pair(4, 7));
  72   ASSERT_NE(R.first, MV.end());
  73   EXPECT_EQ(R.first->first, 4);
  74   EXPECT_EQ(R.first->second, 7);
  75   EXPECT_TRUE(R.second);
  76
  77   EXPECT_EQ(MV.size(), 2u);
  78   EXPECT_EQ(MV[1], 2);
  79   EXPECT_EQ(MV[4], 7);
  80 }
  81
  82 TEST(MapVectorTest, erase) {
  83   MapVector<int, int> MV;
  84
  85   MV.insert(std::make_pair(1, 2));
  86   MV.insert(std::make_pair(3, 4));
  87   MV.insert(std::make_pair(5, 6));
  88   ASSERT_EQ(MV.size(), 3u);
  89
  90   MV.erase(MV.find(1));
  91   ASSERT_EQ(MV.size(), 2u);
  92   ASSERT_EQ(MV.find(1), MV.end());
  93   ASSERT_EQ(MV[3], 4);
  94   ASSERT_EQ(MV[5], 6);
  95
  96   ASSERT_EQ(MV.erase(3), 1u);
  97   ASSERT_EQ(MV.size(), 1u);
  98   ASSERT_EQ(MV.find(3), MV.end());
  99   ASSERT_EQ(MV[5], 6);
 100
 101   ASSERT_EQ(MV.erase(79), 0u);
 102   ASSERT_EQ(MV.size(), 1u);
 103 }
 104
 105 TEST(MapVectorTest, remove_if) {
 106   MapVector<int, int> MV;
 107
 108   MV.insert(std::make_pair(1, 11));
 109   MV.insert(std::make_pair(2, 12));
 110   MV.insert(std::make_pair(3, 13));
 111   MV.insert(std::make_pair(4, 14));
 112   MV.insert(std::make_pair(5, 15));
 113   MV.insert(std::make_pair(6, 16));
 114   ASSERT_EQ(MV.size(), 6u);
 115
 116   MV.remove_if([](const std::pair<int, int> &Val) { return Val.second % 2; });
 117   ASSERT_EQ(MV.size(), 3u);
 118   ASSERT_EQ(MV.find(1), MV.end());
 119   ASSERT_EQ(MV.find(3), MV.end());
 120   ASSERT_EQ(MV.find(5), MV.end());
 121   ASSERT_EQ(MV[2], 12);
 122   ASSERT_EQ(MV[4], 14);
 123   ASSERT_EQ(MV[6], 16);
 124 }
 125
 126 TEST(MapVectorTest, iteration_test) {
 127   MapVector<int, int> MV;
 128
 129   MV.insert(std::make_pair(1, 11));
 130   MV.insert(std::make_pair(2, 12));
 131   MV.insert(std::make_pair(3, 13));
 132   MV.insert(std::make_pair(4, 14));
 133   MV.insert(std::make_pair(5, 15));
 134   MV.insert(std::make_pair(6, 16));
 135   ASSERT_EQ(MV.size(), 6u);
 136
 137   int count = 1;
 138   for (auto P : make_range(MV.begin(), MV.end())) {
 139     ASSERT_EQ(P.first, count);
 140     count++;
 141   }
 142
 143   count = 6;
 144   for (auto P : make_range(MV.rbegin(), MV.rend())) {
 145     ASSERT_EQ(P.first, count);
 146     count--;
 147   }
 148 }
 149
 150 TEST(MapVectorTest, NonCopyable) {
 151   MapVector<int, std::unique_ptr<int>> MV;
 152   MV.insert(std::make_pair(1, std::make_unique<int>(1)));
 153   MV.insert(std::make_pair(2, std::make_unique<int>(2)));
 154
 155   ASSERT_EQ(MV.count(1), 1u);
 156   ASSERT_EQ(*MV.find(2)->second, 2);
 157 }
 158
 159 template <class IntType> struct MapVectorMappedTypeTest : ::testing::Test {
 160   using int_type = IntType;
 161 };
 162
 163 using MapIntTypes = ::testing::Types<int, long, long long, unsigned,
 164                                      unsigned long, unsigned long long>;
 165 TYPED_TEST_SUITE(MapVectorMappedTypeTest, MapIntTypes, );
 166
 167 TYPED_TEST(MapVectorMappedTypeTest, DifferentDenseMap) {
 168   // Test that using a map with a mapped type other than 'unsigned' compiles
 169   // and works.
 170   using IntType = typename TestFixture::int_type;
 171   using MapVectorType = MapVector<int, int, DenseMap<int, IntType>>;
 172
 173   MapVectorType MV;
 174   std::pair<typename MapVectorType::iterator, bool> R;
 175
 176   R = MV.insert(std::make_pair(1, 2));
 177   ASSERT_EQ(R.first, MV.begin());
 178   EXPECT_EQ(R.first->first, 1);
 179   EXPECT_EQ(R.first->second, 2);
 180   EXPECT_TRUE(R.second);
 181
 182   const std::pair<int, int> Elem(1, 3);
 183   R = MV.insert(Elem);
 184   ASSERT_EQ(R.first, MV.begin());
 185   EXPECT_EQ(R.first->first, 1);
 186   EXPECT_EQ(R.first->second, 2);
 187   EXPECT_FALSE(R.second);
 188
 189   int& value = MV[4];
 190   EXPECT_EQ(value, 0);
 191   value = 5;
 192
 193   EXPECT_EQ(MV.size(), 2u);
 194   EXPECT_EQ(MV[1], 2);
 195   EXPECT_EQ(MV[4], 5);
 196 }
 197
 198 TEST(SmallMapVectorSmallTest, insert_pop) {
 199   SmallMapVector<int, int, 32> MV;
 200   std::pair<SmallMapVector<int, int, 32>::iterator, bool> R;
 201
 202   R = MV.insert(std::make_pair(1, 2));
 203   ASSERT_EQ(R.first, MV.begin());
 204   EXPECT_EQ(R.first->first, 1);
 205   EXPECT_EQ(R.first->second, 2);
 206   EXPECT_TRUE(R.second);
 207
 208   R = MV.insert(std::make_pair(1, 3));
 209   ASSERT_EQ(R.first, MV.begin());
 210   EXPECT_EQ(R.first->first, 1);
 211   EXPECT_EQ(R.first->second, 2);
 212   EXPECT_FALSE(R.second);
 213
 214   R = MV.insert(std::make_pair(4, 5));
 215   ASSERT_NE(R.first, MV.end());
 216   EXPECT_EQ(R.first->first, 4);
 217   EXPECT_EQ(R.first->second, 5);
 218   EXPECT_TRUE(R.second);
 219
 220   EXPECT_EQ(MV.size(), 2u);
 221   EXPECT_EQ(MV[1], 2);
 222   EXPECT_EQ(MV[4], 5);
 223
 224   MV.pop_back();
 225   EXPECT_EQ(MV.size(), 1u);
 226   EXPECT_EQ(MV[1], 2);
 227
 228   R = MV.insert(std::make_pair(4, 7));
 229   ASSERT_NE(R.first, MV.end());
 230   EXPECT_EQ(R.first->first, 4);
 231   EXPECT_EQ(R.first->second, 7);
 232   EXPECT_TRUE(R.second);
 233
 234   EXPECT_EQ(MV.size(), 2u);
 235   EXPECT_EQ(MV[1], 2);
 236   EXPECT_EQ(MV[4], 7);
 237 }
 238
 239 TEST(SmallMapVectorSmallTest, erase) {
 240   SmallMapVector<int, int, 32> MV;
 241
 242   MV.insert(std::make_pair(1, 2));
 243   MV.insert(std::make_pair(3, 4));
 244   MV.insert(std::make_pair(5, 6));
 245   ASSERT_EQ(MV.size(), 3u);
 246
 247   MV.erase(MV.find(1));
 248   ASSERT_EQ(MV.size(), 2u);
 249   ASSERT_EQ(MV.find(1), MV.end());
 250   ASSERT_EQ(MV[3], 4);
 251   ASSERT_EQ(MV[5], 6);
 252
 253   ASSERT_EQ(MV.erase(3), 1u);
 254   ASSERT_EQ(MV.size(), 1u);
 255   ASSERT_EQ(MV.find(3), MV.end());
 256   ASSERT_EQ(MV[5], 6);
 257
 258   ASSERT_EQ(MV.erase(79), 0u);
 259   ASSERT_EQ(MV.size(), 1u);
 260 }
 261
 262 TEST(SmallMapVectorSmallTest, remove_if) {
 263   SmallMapVector<int, int, 32> MV;
 264
 265   MV.insert(std::make_pair(1, 11));
 266   MV.insert(std::make_pair(2, 12));
 267   MV.insert(std::make_pair(3, 13));
 268   MV.insert(std::make_pair(4, 14));
 269   MV.insert(std::make_pair(5, 15));
 270   MV.insert(std::make_pair(6, 16));
 271   ASSERT_EQ(MV.size(), 6u);
 272
 273   MV.remove_if([](const std::pair<int, int> &Val) { return Val.second % 2; });
 274   ASSERT_EQ(MV.size(), 3u);
 275   ASSERT_EQ(MV.find(1), MV.end());
 276   ASSERT_EQ(MV.find(3), MV.end());
 277   ASSERT_EQ(MV.find(5), MV.end());
 278   ASSERT_EQ(MV[2], 12);
 279   ASSERT_EQ(MV[4], 14);
 280   ASSERT_EQ(MV[6], 16);
 281 }
 282
 283 TEST(SmallMapVectorSmallTest, iteration_test) {
 284   SmallMapVector<int, int, 32> MV;
 285
 286   MV.insert(std::make_pair(1, 11));
 287   MV.insert(std::make_pair(2, 12));
 288   MV.insert(std::make_pair(3, 13));
 289   MV.insert(std::make_pair(4, 14));
 290   MV.insert(std::make_pair(5, 15));
 291   MV.insert(std::make_pair(6, 16));
 292   ASSERT_EQ(MV.size(), 6u);
 293
 294   int count = 1;
 295   for (auto P : make_range(MV.begin(), MV.end())) {
 296     ASSERT_EQ(P.first, count);
 297     count++;
 298   }
 299
 300   count = 6;
 301   for (auto P : make_range(MV.rbegin(), MV.rend())) {
 302     ASSERT_EQ(P.first, count);
 303     count--;
 304   }
 305 }
 306
 307 TEST(SmallMapVectorSmallTest, NonCopyable) {
 308   SmallMapVector<int, std::unique_ptr<int>, 8> MV;
 309   MV.insert(std::make_pair(1, std::make_unique<int>(1)));
 310   MV.insert(std::make_pair(2, std::make_unique<int>(2)));
 311
 312   ASSERT_EQ(MV.count(1), 1u);
 313   ASSERT_EQ(*MV.find(2)->second, 2);
 314 }
 315
 316 TEST(SmallMapVectorLargeTest, insert_pop) {
 317   SmallMapVector<int, int, 1> MV;
 318   std::pair<SmallMapVector<int, int, 1>::iterator, bool> R;
 319
 320   R = MV.insert(std::make_pair(1, 2));
 321   ASSERT_EQ(R.first, MV.begin());
 322   EXPECT_EQ(R.first->first, 1);
 323   EXPECT_EQ(R.first->second, 2);
 324   EXPECT_TRUE(R.second);
 325
 326   R = MV.insert(std::make_pair(1, 3));
 327   ASSERT_EQ(R.first, MV.begin());
 328   EXPECT_EQ(R.first->first, 1);
 329   EXPECT_EQ(R.first->second, 2);
 330   EXPECT_FALSE(R.second);
 331
 332   R = MV.insert(std::make_pair(4, 5));
 333   ASSERT_NE(R.first, MV.end());
 334   EXPECT_EQ(R.first->first, 4);
 335   EXPECT_EQ(R.first->second, 5);
 336   EXPECT_TRUE(R.second);
 337
 338   EXPECT_EQ(MV.size(), 2u);
 339   EXPECT_EQ(MV[1], 2);
 340   EXPECT_EQ(MV[4], 5);
 341
 342   MV.pop_back();
 343   EXPECT_EQ(MV.size(), 1u);
 344   EXPECT_EQ(MV[1], 2);
 345
 346   R = MV.insert(std::make_pair(4, 7));
 347   ASSERT_NE(R.first, MV.end());
 348   EXPECT_EQ(R.first->first, 4);
 349   EXPECT_EQ(R.first->second, 7);
 350   EXPECT_TRUE(R.second);
 351
 352   EXPECT_EQ(MV.size(), 2u);
 353   EXPECT_EQ(MV[1], 2);
 354   EXPECT_EQ(MV[4], 7);
 355 }
 356
 357 TEST(SmallMapVectorLargeTest, erase) {
 358   SmallMapVector<int, int, 1> MV;
 359
 360   MV.insert(std::make_pair(1, 2));
 361   MV.insert(std::make_pair(3, 4));
 362   MV.insert(std::make_pair(5, 6));
 363   ASSERT_EQ(MV.size(), 3u);
 364
 365   MV.erase(MV.find(1));
 366   ASSERT_EQ(MV.size(), 2u);
 367   ASSERT_EQ(MV.find(1), MV.end());
 368   ASSERT_EQ(MV[3], 4);
 369   ASSERT_EQ(MV[5], 6);
 370
 371   ASSERT_EQ(MV.erase(3), 1u);
 372   ASSERT_EQ(MV.size(), 1u);
 373   ASSERT_EQ(MV.find(3), MV.end());
 374   ASSERT_EQ(MV[5], 6);
 375
 376   ASSERT_EQ(MV.erase(79), 0u);
 377   ASSERT_EQ(MV.size(), 1u);
 378 }
 379
 380 TEST(SmallMapVectorLargeTest, remove_if) {
 381   SmallMapVector<int, int, 1> MV;
 382
 383   MV.insert(std::make_pair(1, 11));
 384   MV.insert(std::make_pair(2, 12));
 385   MV.insert(std::make_pair(3, 13));
 386   MV.insert(std::make_pair(4, 14));
 387   MV.insert(std::make_pair(5, 15));
 388   MV.insert(std::make_pair(6, 16));
 389   ASSERT_EQ(MV.size(), 6u);
 390
 391   MV.remove_if([](const std::pair<int, int> &Val) { return Val.second % 2; });
 392   ASSERT_EQ(MV.size(), 3u);
 393   ASSERT_EQ(MV.find(1), MV.end());
 394   ASSERT_EQ(MV.find(3), MV.end());
 395   ASSERT_EQ(MV.find(5), MV.end());
 396   ASSERT_EQ(MV[2], 12);
 397   ASSERT_EQ(MV[4], 14);
 398   ASSERT_EQ(MV[6], 16);
 399 }
 400
 401 TEST(SmallMapVectorLargeTest, iteration_test) {
 402   SmallMapVector<int, int, 1> MV;
 403
 404   MV.insert(std::make_pair(1, 11));
 405   MV.insert(std::make_pair(2, 12));
 406   MV.insert(std::make_pair(3, 13));
 407   MV.insert(std::make_pair(4, 14));
 408   MV.insert(std::make_pair(5, 15));
 409   MV.insert(std::make_pair(6, 16));
 410   ASSERT_EQ(MV.size(), 6u);
 411
 412   int count = 1;
 413   for (auto P : make_range(MV.begin(), MV.end())) {
 414     ASSERT_EQ(P.first, count);
 415     count++;
 416   }
 417
 418   count = 6;
 419   for (auto P : make_range(MV.rbegin(), MV.rend())) {
 420     ASSERT_EQ(P.first, count);
 421     count--;
 422   }
 423 }