1 //===- llvm/unittest/ADT/TinyPtrVectorTest.cpp ----------------------------===// 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 // TinyPtrVector unit tests. 11 // 12 //===----------------------------------------------------------------------===// 13 14 #include "llvm/ADT/TinyPtrVector.h" 15 #include "llvm/ADT/ArrayRef.h" 16 #include "llvm/ADT/STLExtras.h" 17 #include "llvm/Support/type_traits.h" 18 #include "gtest/gtest.h" 19 #include <algorithm> 20 #include <random> 21 #include <vector> 22 23 using namespace llvm; 24 25 namespace { 26 27 template <typename VectorT> 28 class TinyPtrVectorTest : public testing::Test { 29 protected: 30 typedef typename VectorT::value_type PtrT; 31 typedef typename std::remove_pointer<PtrT>::type ValueT; 32 33 VectorT V; 34 VectorT V2; 35 36 ValueT TestValues[1024]; 37 std::vector<PtrT> TestPtrs; 38 39 TinyPtrVectorTest() { 40 for (size_t i = 0, e = array_lengthof(TestValues); i != e; ++i) 41 TestPtrs.push_back(&TestValues[i]); 42 43 std::shuffle(TestPtrs.begin(), TestPtrs.end(), std::mt19937{}); 44 } 45 46 ArrayRef<PtrT> testArray(size_t N) { 47 return makeArrayRef(&TestPtrs[0], N); 48 } 49 50 void appendValues(VectorT &V, ArrayRef<PtrT> Values) { 51 for (size_t i = 0, e = Values.size(); i != e; ++i) 52 V.push_back(Values[i]); 53 } 54 55 void setVectors(ArrayRef<PtrT> Values1, ArrayRef<PtrT> Values2) { 56 V.clear(); 57 appendValues(V, Values1); 58 V2.clear(); 59 appendValues(V2, Values2); 60 } 61 62 void expectValues(const VectorT &V, ArrayRef<PtrT> Values) { 63 EXPECT_EQ(Values.empty(), V.empty()); 64 EXPECT_EQ(Values.size(), V.size()); 65 for (size_t i = 0, e = Values.size(); i != e; ++i) { 66 EXPECT_EQ(Values[i], V[i]); 67 EXPECT_EQ(Values[i], *std::next(V.begin(), i)); 68 } 69 EXPECT_EQ(V.end(), std::next(V.begin(), Values.size())); 70 } 71 }; 72 73 typedef ::testing::Types<TinyPtrVector<int*>, 74 TinyPtrVector<double*> 75 > TinyPtrVectorTestTypes; 76 TYPED_TEST_CASE(TinyPtrVectorTest, TinyPtrVectorTestTypes); 77 78 TYPED_TEST(TinyPtrVectorTest, EmptyTest) { 79 this->expectValues(this->V, this->testArray(0)); 80 } 81 82 TYPED_TEST(TinyPtrVectorTest, PushPopBack) { 83 this->V.push_back(this->TestPtrs[0]); 84 this->expectValues(this->V, this->testArray(1)); 85 this->V.push_back(this->TestPtrs[1]); 86 this->expectValues(this->V, this->testArray(2)); 87 this->V.push_back(this->TestPtrs[2]); 88 this->expectValues(this->V, this->testArray(3)); 89 this->V.push_back(this->TestPtrs[3]); 90 this->expectValues(this->V, this->testArray(4)); 91 this->V.push_back(this->TestPtrs[4]); 92 this->expectValues(this->V, this->testArray(5)); 93 94 // Pop and clobber a few values to keep things interesting. 95 this->V.pop_back(); 96 this->expectValues(this->V, this->testArray(4)); 97 this->V.pop_back(); 98 this->expectValues(this->V, this->testArray(3)); 99 this->TestPtrs[3] = &this->TestValues[42]; 100 this->TestPtrs[4] = &this->TestValues[43]; 101 this->V.push_back(this->TestPtrs[3]); 102 this->expectValues(this->V, this->testArray(4)); 103 this->V.push_back(this->TestPtrs[4]); 104 this->expectValues(this->V, this->testArray(5)); 105 106 this->V.pop_back(); 107 this->expectValues(this->V, this->testArray(4)); 108 this->V.pop_back(); 109 this->expectValues(this->V, this->testArray(3)); 110 this->V.pop_back(); 111 this->expectValues(this->V, this->testArray(2)); 112 this->V.pop_back(); 113 this->expectValues(this->V, this->testArray(1)); 114 this->V.pop_back(); 115 this->expectValues(this->V, this->testArray(0)); 116 117 this->appendValues(this->V, this->testArray(42)); 118 this->expectValues(this->V, this->testArray(42)); 119 } 120 121 TYPED_TEST(TinyPtrVectorTest, ClearTest) { 122 this->expectValues(this->V, this->testArray(0)); 123 this->V.clear(); 124 this->expectValues(this->V, this->testArray(0)); 125 126 this->appendValues(this->V, this->testArray(1)); 127 this->expectValues(this->V, this->testArray(1)); 128 this->V.clear(); 129 this->expectValues(this->V, this->testArray(0)); 130 131 this->appendValues(this->V, this->testArray(42)); 132 this->expectValues(this->V, this->testArray(42)); 133 this->V.clear(); 134 this->expectValues(this->V, this->testArray(0)); 135 } 136 137 TYPED_TEST(TinyPtrVectorTest, CopyAndMoveCtorTest) { 138 this->appendValues(this->V, this->testArray(42)); 139 TypeParam Copy(this->V); 140 this->expectValues(Copy, this->testArray(42)); 141 142 // This is a separate copy, and so it shouldn't destroy the original. 143 Copy.clear(); 144 this->expectValues(Copy, this->testArray(0)); 145 this->expectValues(this->V, this->testArray(42)); 146 147 TypeParam Copy2(this->V2); 148 this->appendValues(Copy2, this->testArray(42)); 149 this->expectValues(Copy2, this->testArray(42)); 150 this->expectValues(this->V2, this->testArray(0)); 151 152 TypeParam Move(std::move(Copy2)); 153 this->expectValues(Move, this->testArray(42)); 154 this->expectValues(Copy2, this->testArray(0)); 155 156 TypeParam MultipleElements(this->testArray(2)); 157 TypeParam SingleElement(this->testArray(1)); 158 MultipleElements = std::move(SingleElement); 159 this->expectValues(MultipleElements, this->testArray(1)); 160 this->expectValues(SingleElement, this->testArray(0)); 161 } 162 163 TYPED_TEST(TinyPtrVectorTest, CopyAndMoveTest) { 164 this->V = this->V2; 165 this->expectValues(this->V, this->testArray(0)); 166 this->expectValues(this->V2, this->testArray(0)); 167 this->V = std::move(this->V2); 168 this->expectValues(this->V, this->testArray(0)); 169 170 this->setVectors(this->testArray(1), this->testArray(0)); 171 this->V = this->V2; 172 this->expectValues(this->V, this->testArray(0)); 173 this->expectValues(this->V2, this->testArray(0)); 174 this->setVectors(this->testArray(1), this->testArray(0)); 175 this->V = std::move(this->V2); 176 this->expectValues(this->V, this->testArray(0)); 177 178 this->setVectors(this->testArray(2), this->testArray(0)); 179 this->V = this->V2; 180 this->expectValues(this->V, this->testArray(0)); 181 this->expectValues(this->V2, this->testArray(0)); 182 this->setVectors(this->testArray(2), this->testArray(0)); 183 this->V = std::move(this->V2); 184 this->expectValues(this->V, this->testArray(0)); 185 186 this->setVectors(this->testArray(42), this->testArray(0)); 187 this->V = this->V2; 188 this->expectValues(this->V, this->testArray(0)); 189 this->expectValues(this->V2, this->testArray(0)); 190 this->setVectors(this->testArray(42), this->testArray(0)); 191 this->V = std::move(this->V2); 192 this->expectValues(this->V, this->testArray(0)); 193 194 this->setVectors(this->testArray(0), this->testArray(1)); 195 this->V = this->V2; 196 this->expectValues(this->V, this->testArray(1)); 197 this->expectValues(this->V2, this->testArray(1)); 198 this->setVectors(this->testArray(0), this->testArray(1)); 199 this->V = std::move(this->V2); 200 this->expectValues(this->V, this->testArray(1)); 201 202 this->setVectors(this->testArray(0), this->testArray(2)); 203 this->V = this->V2; 204 this->expectValues(this->V, this->testArray(2)); 205 this->expectValues(this->V2, this->testArray(2)); 206 this->setVectors(this->testArray(0), this->testArray(2)); 207 this->V = std::move(this->V2); 208 this->expectValues(this->V, this->testArray(2)); 209 210 this->setVectors(this->testArray(0), this->testArray(42)); 211 this->V = this->V2; 212 this->expectValues(this->V, this->testArray(42)); 213 this->expectValues(this->V2, this->testArray(42)); 214 this->setVectors(this->testArray(0), this->testArray(42)); 215 this->V = std::move(this->V2); 216 this->expectValues(this->V, this->testArray(42)); 217 218 this->setVectors(this->testArray(1), this->testArray(1)); 219 this->V = this->V2; 220 this->expectValues(this->V, this->testArray(1)); 221 this->expectValues(this->V2, this->testArray(1)); 222 this->V = std::move(this->V2); 223 this->expectValues(this->V, this->testArray(1)); 224 225 this->setVectors(this->testArray(1), this->testArray(2)); 226 this->V = this->V2; 227 this->expectValues(this->V, this->testArray(2)); 228 this->expectValues(this->V2, this->testArray(2)); 229 this->setVectors(this->testArray(1), this->testArray(2)); 230 this->V = std::move(this->V2); 231 this->expectValues(this->V, this->testArray(2)); 232 233 this->setVectors(this->testArray(1), this->testArray(42)); 234 this->V = this->V2; 235 this->expectValues(this->V, this->testArray(42)); 236 this->expectValues(this->V2, this->testArray(42)); 237 this->setVectors(this->testArray(1), this->testArray(42)); 238 this->V = std::move(this->V2); 239 this->expectValues(this->V, this->testArray(42)); 240 241 this->setVectors(this->testArray(2), this->testArray(1)); 242 this->V = this->V2; 243 this->expectValues(this->V, this->testArray(1)); 244 this->expectValues(this->V2, this->testArray(1)); 245 this->setVectors(this->testArray(2), this->testArray(1)); 246 this->V = std::move(this->V2); 247 this->expectValues(this->V, this->testArray(1)); 248 249 this->setVectors(this->testArray(2), this->testArray(2)); 250 this->V = this->V2; 251 this->expectValues(this->V, this->testArray(2)); 252 this->expectValues(this->V2, this->testArray(2)); 253 this->setVectors(this->testArray(2), this->testArray(2)); 254 this->V = std::move(this->V2); 255 this->expectValues(this->V, this->testArray(2)); 256 257 this->setVectors(this->testArray(2), this->testArray(42)); 258 this->V = this->V2; 259 this->expectValues(this->V, this->testArray(42)); 260 this->expectValues(this->V2, this->testArray(42)); 261 this->setVectors(this->testArray(2), this->testArray(42)); 262 this->V = std::move(this->V2); 263 this->expectValues(this->V, this->testArray(42)); 264 265 this->setVectors(this->testArray(42), this->testArray(1)); 266 this->V = this->V2; 267 this->expectValues(this->V, this->testArray(1)); 268 this->expectValues(this->V2, this->testArray(1)); 269 this->setVectors(this->testArray(42), this->testArray(1)); 270 this->V = std::move(this->V2); 271 this->expectValues(this->V, this->testArray(1)); 272 273 this->setVectors(this->testArray(42), this->testArray(2)); 274 this->V = this->V2; 275 this->expectValues(this->V, this->testArray(2)); 276 this->expectValues(this->V2, this->testArray(2)); 277 this->setVectors(this->testArray(42), this->testArray(2)); 278 this->V = std::move(this->V2); 279 this->expectValues(this->V, this->testArray(2)); 280 281 this->setVectors(this->testArray(42), this->testArray(42)); 282 this->V = this->V2; 283 this->expectValues(this->V, this->testArray(42)); 284 this->expectValues(this->V2, this->testArray(42)); 285 this->setVectors(this->testArray(42), this->testArray(42)); 286 this->V = std::move(this->V2); 287 this->expectValues(this->V, this->testArray(42)); 288 } 289 290 TYPED_TEST(TinyPtrVectorTest, EraseTest) { 291 this->appendValues(this->V, this->testArray(1)); 292 this->expectValues(this->V, this->testArray(1)); 293 this->V.erase(this->V.begin()); 294 this->expectValues(this->V, this->testArray(0)); 295 296 this->appendValues(this->V, this->testArray(42)); 297 this->expectValues(this->V, this->testArray(42)); 298 this->V.erase(this->V.begin()); 299 this->TestPtrs.erase(this->TestPtrs.begin()); 300 this->expectValues(this->V, this->testArray(41)); 301 this->V.erase(std::next(this->V.begin(), 1)); 302 this->TestPtrs.erase(std::next(this->TestPtrs.begin(), 1)); 303 this->expectValues(this->V, this->testArray(40)); 304 this->V.erase(std::next(this->V.begin(), 2)); 305 this->TestPtrs.erase(std::next(this->TestPtrs.begin(), 2)); 306 this->expectValues(this->V, this->testArray(39)); 307 this->V.erase(std::next(this->V.begin(), 5)); 308 this->TestPtrs.erase(std::next(this->TestPtrs.begin(), 5)); 309 this->expectValues(this->V, this->testArray(38)); 310 this->V.erase(std::next(this->V.begin(), 13)); 311 this->TestPtrs.erase(std::next(this->TestPtrs.begin(), 13)); 312 this->expectValues(this->V, this->testArray(37)); 313 314 typename TypeParam::iterator I = this->V.begin(); 315 do { 316 I = this->V.erase(I); 317 } while (I != this->V.end()); 318 this->expectValues(this->V, this->testArray(0)); 319 } 320 321 TYPED_TEST(TinyPtrVectorTest, EraseRangeTest) { 322 this->appendValues(this->V, this->testArray(1)); 323 this->expectValues(this->V, this->testArray(1)); 324 this->V.erase(this->V.begin(), this->V.begin()); 325 this->expectValues(this->V, this->testArray(1)); 326 this->V.erase(this->V.end(), this->V.end()); 327 this->expectValues(this->V, this->testArray(1)); 328 this->V.erase(this->V.begin(), this->V.end()); 329 this->expectValues(this->V, this->testArray(0)); 330 331 this->appendValues(this->V, this->testArray(42)); 332 this->expectValues(this->V, this->testArray(42)); 333 this->V.erase(this->V.begin(), std::next(this->V.begin(), 1)); 334 this->TestPtrs.erase(this->TestPtrs.begin(), 335 std::next(this->TestPtrs.begin(), 1)); 336 this->expectValues(this->V, this->testArray(41)); 337 this->V.erase(std::next(this->V.begin(), 1), std::next(this->V.begin(), 2)); 338 this->TestPtrs.erase(std::next(this->TestPtrs.begin(), 1), 339 std::next(this->TestPtrs.begin(), 2)); 340 this->expectValues(this->V, this->testArray(40)); 341 this->V.erase(std::next(this->V.begin(), 2), std::next(this->V.begin(), 4)); 342 this->TestPtrs.erase(std::next(this->TestPtrs.begin(), 2), 343 std::next(this->TestPtrs.begin(), 4)); 344 this->expectValues(this->V, this->testArray(38)); 345 this->V.erase(std::next(this->V.begin(), 5), std::next(this->V.begin(), 10)); 346 this->TestPtrs.erase(std::next(this->TestPtrs.begin(), 5), 347 std::next(this->TestPtrs.begin(), 10)); 348 this->expectValues(this->V, this->testArray(33)); 349 this->V.erase(std::next(this->V.begin(), 13), std::next(this->V.begin(), 26)); 350 this->TestPtrs.erase(std::next(this->TestPtrs.begin(), 13), 351 std::next(this->TestPtrs.begin(), 26)); 352 this->expectValues(this->V, this->testArray(20)); 353 this->V.erase(std::next(this->V.begin(), 7), this->V.end()); 354 this->expectValues(this->V, this->testArray(7)); 355 this->V.erase(this->V.begin(), this->V.end()); 356 this->expectValues(this->V, this->testArray(0)); 357 } 358 359 TYPED_TEST(TinyPtrVectorTest, Insert) { 360 this->V.insert(this->V.end(), this->TestPtrs[0]); 361 this->expectValues(this->V, this->testArray(1)); 362 this->V.clear(); 363 this->appendValues(this->V, this->testArray(4)); 364 this->expectValues(this->V, this->testArray(4)); 365 this->V.insert(this->V.end(), this->TestPtrs[4]); 366 this->expectValues(this->V, this->testArray(5)); 367 this->V.insert(this->V.begin(), this->TestPtrs[42]); 368 this->TestPtrs.insert(this->TestPtrs.begin(), this->TestPtrs[42]); 369 this->expectValues(this->V, this->testArray(6)); 370 this->V.insert(std::next(this->V.begin(), 3), this->TestPtrs[43]); 371 this->TestPtrs.insert(std::next(this->TestPtrs.begin(), 3), 372 this->TestPtrs[43]); 373 this->expectValues(this->V, this->testArray(7)); 374 } 375 376 TYPED_TEST(TinyPtrVectorTest, InsertRange) { 377 this->V.insert(this->V.end(), this->TestPtrs.begin(), this->TestPtrs.begin()); 378 this->expectValues(this->V, this->testArray(0)); 379 this->V.insert(this->V.begin(), this->TestPtrs.begin(), 380 this->TestPtrs.begin()); 381 this->expectValues(this->V, this->testArray(0)); 382 this->V.insert(this->V.end(), this->TestPtrs.end(), this->TestPtrs.end()); 383 this->expectValues(this->V, this->testArray(0)); 384 this->V.insert(this->V.end(), this->TestPtrs.begin(), 385 std::next(this->TestPtrs.begin())); 386 this->expectValues(this->V, this->testArray(1)); 387 this->V.clear(); 388 this->V.insert(this->V.end(), this->TestPtrs.begin(), 389 std::next(this->TestPtrs.begin(), 2)); 390 this->expectValues(this->V, this->testArray(2)); 391 this->V.clear(); 392 this->V.insert(this->V.end(), this->TestPtrs.begin(), 393 std::next(this->TestPtrs.begin(), 42)); 394 this->expectValues(this->V, this->testArray(42)); 395 this->V.clear(); 396 this->V.insert(this->V.end(), 397 std::next(this->TestPtrs.begin(), 5), 398 std::next(this->TestPtrs.begin(), 13)); 399 this->V.insert(this->V.begin(), 400 std::next(this->TestPtrs.begin(), 0), 401 std::next(this->TestPtrs.begin(), 3)); 402 this->V.insert(std::next(this->V.begin(), 2), 403 std::next(this->TestPtrs.begin(), 2), 404 std::next(this->TestPtrs.begin(), 4)); 405 this->V.erase(std::next(this->V.begin(), 4)); 406 this->V.insert(std::next(this->V.begin(), 4), 407 std::next(this->TestPtrs.begin(), 4), 408 std::next(this->TestPtrs.begin(), 5)); 409 this->expectValues(this->V, this->testArray(13)); 410 } 411 412 } 413 414 TEST(TinyPtrVectorTest, SingleEltCtorTest) { 415 int v = 55; 416 TinyPtrVector<int *> V(&v); 417 418 EXPECT_TRUE(V.size() == 1); 419 EXPECT_FALSE(V.empty()); 420 EXPECT_TRUE(V.front() == &v); 421 } 422 423 TEST(TinyPtrVectorTest, ArrayRefCtorTest) { 424 int data_array[128]; 425 std::vector<int *> data; 426 427 for (unsigned i = 0, e = 128; i != e; ++i) { 428 data_array[i] = 324 - int(i); 429 data.push_back(&data_array[i]); 430 } 431 432 TinyPtrVector<int *> V(data); 433 EXPECT_TRUE(V.size() == 128); 434 EXPECT_FALSE(V.empty()); 435 for (unsigned i = 0, e = 128; i != e; ++i) { 436 EXPECT_TRUE(V[i] == data[i]); 437 } 438 } 439 440 TEST(TinyPtrVectorTest, MutableArrayRefTest) { 441 int data_array[128]; 442 std::vector<int *> data; 443 444 for (unsigned i = 0, e = 128; i != e; ++i) { 445 data_array[i] = 324 - int(i); 446 data.push_back(&data_array[i]); 447 } 448 449 TinyPtrVector<int *> V(data); 450 EXPECT_TRUE(V.size() == 128); 451 EXPECT_FALSE(V.empty()); 452 453 MutableArrayRef<int *> mut_array = V; 454 for (unsigned i = 0, e = 128; i != e; ++i) { 455 EXPECT_TRUE(mut_array[i] == data[i]); 456 mut_array[i] = 324 + mut_array[i]; 457 EXPECT_TRUE(mut_array[i] == (324 + data[i])); 458 } 459 } 460