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 } 425
