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