unittests/ADT/MapVectorTest.cpp

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