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 "gtest/gtest.h"
  11 #include "llvm/ADT/MapVector.h"
  12 #include "llvm/ADT/iterator_range.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(SmallMapVectorSmallTest, insert_pop) {
 152   SmallMapVector<int, int, 32> MV;
 153   std::pair<SmallMapVector<int, int, 32>::iterator, bool> R;
 154
 155   R = MV.insert(std::make_pair(1, 2));
 156   ASSERT_EQ(R.first, MV.begin());
 157   EXPECT_EQ(R.first->first, 1);
 158   EXPECT_EQ(R.first->second, 2);
 159   EXPECT_TRUE(R.second);
 160
 161   R = MV.insert(std::make_pair(1, 3));
 162   ASSERT_EQ(R.first, MV.begin());
 163   EXPECT_EQ(R.first->first, 1);
 164   EXPECT_EQ(R.first->second, 2);
 165   EXPECT_FALSE(R.second);
 166
 167   R = MV.insert(std::make_pair(4, 5));
 168   ASSERT_NE(R.first, MV.end());
 169   EXPECT_EQ(R.first->first, 4);
 170   EXPECT_EQ(R.first->second, 5);
 171   EXPECT_TRUE(R.second);
 172
 173   EXPECT_EQ(MV.size(), 2u);
 174   EXPECT_EQ(MV[1], 2);
 175   EXPECT_EQ(MV[4], 5);
 176
 177   MV.pop_back();
 178   EXPECT_EQ(MV.size(), 1u);
 179   EXPECT_EQ(MV[1], 2);
 180
 181   R = MV.insert(std::make_pair(4, 7));
 182   ASSERT_NE(R.first, MV.end());
 183   EXPECT_EQ(R.first->first, 4);
 184   EXPECT_EQ(R.first->second, 7);
 185   EXPECT_TRUE(R.second);
 186
 187   EXPECT_EQ(MV.size(), 2u);
 188   EXPECT_EQ(MV[1], 2);
 189   EXPECT_EQ(MV[4], 7);
 190 }
 191
 192 TEST(SmallMapVectorSmallTest, erase) {
 193   SmallMapVector<int, int, 32> MV;
 194
 195   MV.insert(std::make_pair(1, 2));
 196   MV.insert(std::make_pair(3, 4));
 197   MV.insert(std::make_pair(5, 6));
 198   ASSERT_EQ(MV.size(), 3u);
 199
 200   MV.erase(MV.find(1));
 201   ASSERT_EQ(MV.size(), 2u);
 202   ASSERT_EQ(MV.find(1), MV.end());
 203   ASSERT_EQ(MV[3], 4);
 204   ASSERT_EQ(MV[5], 6);
 205
 206   ASSERT_EQ(MV.erase(3), 1u);
 207   ASSERT_EQ(MV.size(), 1u);
 208   ASSERT_EQ(MV.find(3), MV.end());
 209   ASSERT_EQ(MV[5], 6);
 210
 211   ASSERT_EQ(MV.erase(79), 0u);
 212   ASSERT_EQ(MV.size(), 1u);
 213 }
 214
 215 TEST(SmallMapVectorSmallTest, remove_if) {
 216   SmallMapVector<int, int, 32> MV;
 217
 218   MV.insert(std::make_pair(1, 11));
 219   MV.insert(std::make_pair(2, 12));
 220   MV.insert(std::make_pair(3, 13));
 221   MV.insert(std::make_pair(4, 14));
 222   MV.insert(std::make_pair(5, 15));
 223   MV.insert(std::make_pair(6, 16));
 224   ASSERT_EQ(MV.size(), 6u);
 225
 226   MV.remove_if([](const std::pair<int, int> &Val) { return Val.second % 2; });
 227   ASSERT_EQ(MV.size(), 3u);
 228   ASSERT_EQ(MV.find(1), MV.end());
 229   ASSERT_EQ(MV.find(3), MV.end());
 230   ASSERT_EQ(MV.find(5), MV.end());
 231   ASSERT_EQ(MV[2], 12);
 232   ASSERT_EQ(MV[4], 14);
 233   ASSERT_EQ(MV[6], 16);
 234 }
 235
 236 TEST(SmallMapVectorSmallTest, iteration_test) {
 237   SmallMapVector<int, int, 32> MV;
 238
 239   MV.insert(std::make_pair(1, 11));
 240   MV.insert(std::make_pair(2, 12));
 241   MV.insert(std::make_pair(3, 13));
 242   MV.insert(std::make_pair(4, 14));
 243   MV.insert(std::make_pair(5, 15));
 244   MV.insert(std::make_pair(6, 16));
 245   ASSERT_EQ(MV.size(), 6u);
 246
 247   int count = 1;
 248   for (auto P : make_range(MV.begin(), MV.end())) {
 249     ASSERT_EQ(P.first, count);
 250     count++;
 251   }
 252
 253   count = 6;
 254   for (auto P : make_range(MV.rbegin(), MV.rend())) {
 255     ASSERT_EQ(P.first, count);
 256     count--;
 257   }
 258 }
 259
 260 TEST(SmallMapVectorLargeTest, insert_pop) {
 261   SmallMapVector<int, int, 1> MV;
 262   std::pair<SmallMapVector<int, int, 1>::iterator, bool> R;
 263
 264   R = MV.insert(std::make_pair(1, 2));
 265   ASSERT_EQ(R.first, MV.begin());
 266   EXPECT_EQ(R.first->first, 1);
 267   EXPECT_EQ(R.first->second, 2);
 268   EXPECT_TRUE(R.second);
 269
 270   R = MV.insert(std::make_pair(1, 3));
 271   ASSERT_EQ(R.first, MV.begin());
 272   EXPECT_EQ(R.first->first, 1);
 273   EXPECT_EQ(R.first->second, 2);
 274   EXPECT_FALSE(R.second);
 275
 276   R = MV.insert(std::make_pair(4, 5));
 277   ASSERT_NE(R.first, MV.end());
 278   EXPECT_EQ(R.first->first, 4);
 279   EXPECT_EQ(R.first->second, 5);
 280   EXPECT_TRUE(R.second);
 281
 282   EXPECT_EQ(MV.size(), 2u);
 283   EXPECT_EQ(MV[1], 2);
 284   EXPECT_EQ(MV[4], 5);
 285
 286   MV.pop_back();
 287   EXPECT_EQ(MV.size(), 1u);
 288   EXPECT_EQ(MV[1], 2);
 289
 290   R = MV.insert(std::make_pair(4, 7));
 291   ASSERT_NE(R.first, MV.end());
 292   EXPECT_EQ(R.first->first, 4);
 293   EXPECT_EQ(R.first->second, 7);
 294   EXPECT_TRUE(R.second);
 295
 296   EXPECT_EQ(MV.size(), 2u);
 297   EXPECT_EQ(MV[1], 2);
 298   EXPECT_EQ(MV[4], 7);
 299 }
 300
 301 TEST(SmallMapVectorLargeTest, erase) {
 302   SmallMapVector<int, int, 1> MV;
 303
 304   MV.insert(std::make_pair(1, 2));
 305   MV.insert(std::make_pair(3, 4));
 306   MV.insert(std::make_pair(5, 6));
 307   ASSERT_EQ(MV.size(), 3u);
 308
 309   MV.erase(MV.find(1));
 310   ASSERT_EQ(MV.size(), 2u);
 311   ASSERT_EQ(MV.find(1), MV.end());
 312   ASSERT_EQ(MV[3], 4);
 313   ASSERT_EQ(MV[5], 6);
 314
 315   ASSERT_EQ(MV.erase(3), 1u);
 316   ASSERT_EQ(MV.size(), 1u);
 317   ASSERT_EQ(MV.find(3), MV.end());
 318   ASSERT_EQ(MV[5], 6);
 319
 320   ASSERT_EQ(MV.erase(79), 0u);
 321   ASSERT_EQ(MV.size(), 1u);
 322 }
 323
 324 TEST(SmallMapVectorLargeTest, remove_if) {
 325   SmallMapVector<int, int, 1> MV;
 326
 327   MV.insert(std::make_pair(1, 11));
 328   MV.insert(std::make_pair(2, 12));
 329   MV.insert(std::make_pair(3, 13));
 330   MV.insert(std::make_pair(4, 14));
 331   MV.insert(std::make_pair(5, 15));
 332   MV.insert(std::make_pair(6, 16));
 333   ASSERT_EQ(MV.size(), 6u);
 334
 335   MV.remove_if([](const std::pair<int, int> &Val) { return Val.second % 2; });
 336   ASSERT_EQ(MV.size(), 3u);
 337   ASSERT_EQ(MV.find(1), MV.end());
 338   ASSERT_EQ(MV.find(3), MV.end());
 339   ASSERT_EQ(MV.find(5), MV.end());
 340   ASSERT_EQ(MV[2], 12);
 341   ASSERT_EQ(MV[4], 14);
 342   ASSERT_EQ(MV[6], 16);
 343 }
 344
 345 TEST(SmallMapVectorLargeTest, iteration_test) {
 346   SmallMapVector<int, int, 1> MV;
 347
 348   MV.insert(std::make_pair(1, 11));
 349   MV.insert(std::make_pair(2, 12));
 350   MV.insert(std::make_pair(3, 13));
 351   MV.insert(std::make_pair(4, 14));
 352   MV.insert(std::make_pair(5, 15));
 353   MV.insert(std::make_pair(6, 16));
 354   ASSERT_EQ(MV.size(), 6u);
 355
 356   int count = 1;
 357   for (auto P : make_range(MV.begin(), MV.end())) {
 358     ASSERT_EQ(P.first, count);
 359     count++;
 360   }
 361
 362   count = 6;
 363   for (auto P : make_range(MV.rbegin(), MV.rend())) {
 364     ASSERT_EQ(P.first, count);
 365     count--;
 366   }
 367 }