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