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