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 <vector> 21 22 using namespace llvm; 23 24 namespace { 25 26 // The world's worst RNG, but it is deterministic and makes it easy to get 27 // *some* shuffling of elements. 28 static ptrdiff_t test_shuffle_rng(ptrdiff_t i) { 29 return (i + i * 33) % i; 30 } 31 static ptrdiff_t (*test_shuffle_rng_p)(ptrdiff_t) = &test_shuffle_rng; 32 33 template <typename VectorT> 34 class TinyPtrVectorTest : public testing::Test { 35 protected: 36 typedef typename VectorT::value_type PtrT; 37 typedef typename std::remove_pointer<PtrT>::type ValueT; 38 39 VectorT V; 40 VectorT V2; 41 42 ValueT TestValues[1024]; 43 std::vector<PtrT> TestPtrs; 44 45 TinyPtrVectorTest() { 46 for (size_t i = 0, e = array_lengthof(TestValues); i != e; ++i) 47 TestPtrs.push_back(&TestValues[i]); 48 49 std::random_shuffle(TestPtrs.begin(), TestPtrs.end(), test_shuffle_rng_p); 50 } 51 52 ArrayRef<PtrT> testArray(size_t N) { 53 return makeArrayRef(&TestPtrs[0], N); 54 } 55 56 void appendValues(VectorT &V, ArrayRef<PtrT> Values) { 57 for (size_t i = 0, e = Values.size(); i != e; ++i) 58 V.push_back(Values[i]); 59 } 60 61 void setVectors(ArrayRef<PtrT> Values1, ArrayRef<PtrT> Values2) { 62 V.clear(); 63 appendValues(V, Values1); 64 V2.clear(); 65 appendValues(V2, Values2); 66 } 67 68 void expectValues(const VectorT &V, ArrayRef<PtrT> Values) { 69 EXPECT_EQ(Values.empty(), V.empty()); 70 EXPECT_EQ(Values.size(), V.size()); 71 for (size_t i = 0, e = Values.size(); i != e; ++i) { 72 EXPECT_EQ(Values[i], V[i]); 73 EXPECT_EQ(Values[i], *std::next(V.begin(), i)); 74 } 75 EXPECT_EQ(V.end(), std::next(V.begin(), Values.size())); 76 } 77 }; 78 79 typedef ::testing::Types<TinyPtrVector<int*>, 80 TinyPtrVector<double*> 81 > TinyPtrVectorTestTypes; 82 TYPED_TEST_CASE(TinyPtrVectorTest, TinyPtrVectorTestTypes); 83 84 TYPED_TEST(TinyPtrVectorTest, EmptyTest) { 85 this->expectValues(this->V, this->testArray(0)); 86 } 87 88 TYPED_TEST(TinyPtrVectorTest, PushPopBack) { 89 this->V.push_back(this->TestPtrs[0]); 90 this->expectValues(this->V, this->testArray(1)); 91 this->V.push_back(this->TestPtrs[1]); 92 this->expectValues(this->V, this->testArray(2)); 93 this->V.push_back(this->TestPtrs[2]); 94 this->expectValues(this->V, this->testArray(3)); 95 this->V.push_back(this->TestPtrs[3]); 96 this->expectValues(this->V, this->testArray(4)); 97 this->V.push_back(this->TestPtrs[4]); 98 this->expectValues(this->V, this->testArray(5)); 99 100 // Pop and clobber a few values to keep things interesting. 101 this->V.pop_back(); 102 this->expectValues(this->V, this->testArray(4)); 103 this->V.pop_back(); 104 this->expectValues(this->V, this->testArray(3)); 105 this->TestPtrs[3] = &this->TestValues[42]; 106 this->TestPtrs[4] = &this->TestValues[43]; 107 this->V.push_back(this->TestPtrs[3]); 108 this->expectValues(this->V, this->testArray(4)); 109 this->V.push_back(this->TestPtrs[4]); 110 this->expectValues(this->V, this->testArray(5)); 111 112 this->V.pop_back(); 113 this->expectValues(this->V, this->testArray(4)); 114 this->V.pop_back(); 115 this->expectValues(this->V, this->testArray(3)); 116 this->V.pop_back(); 117 this->expectValues(this->V, this->testArray(2)); 118 this->V.pop_back(); 119 this->expectValues(this->V, this->testArray(1)); 120 this->V.pop_back(); 121 this->expectValues(this->V, this->testArray(0)); 122 123 this->appendValues(this->V, this->testArray(42)); 124 this->expectValues(this->V, this->testArray(42)); 125 } 126 127 TYPED_TEST(TinyPtrVectorTest, ClearTest) { 128 this->expectValues(this->V, this->testArray(0)); 129 this->V.clear(); 130 this->expectValues(this->V, this->testArray(0)); 131 132 this->appendValues(this->V, this->testArray(1)); 133 this->expectValues(this->V, this->testArray(1)); 134 this->V.clear(); 135 this->expectValues(this->V, this->testArray(0)); 136 137 this->appendValues(this->V, this->testArray(42)); 138 this->expectValues(this->V, this->testArray(42)); 139 this->V.clear(); 140 this->expectValues(this->V, this->testArray(0)); 141 } 142 143 TYPED_TEST(TinyPtrVectorTest, CopyAndMoveCtorTest) { 144 this->appendValues(this->V, this->testArray(42)); 145 TypeParam Copy(this->V); 146 this->expectValues(Copy, this->testArray(42)); 147 148 // This is a separate copy, and so it shouldn't destroy the original. 149 Copy.clear(); 150 this->expectValues(Copy, this->testArray(0)); 151 this->expectValues(this->V, this->testArray(42)); 152 153 TypeParam Copy2(this->V2); 154 this->appendValues(Copy2, this->testArray(42)); 155 this->expectValues(Copy2, this->testArray(42)); 156 this->expectValues(this->V2, this->testArray(0)); 157 158 TypeParam Move(std::move(Copy2)); 159 this->expectValues(Move, this->testArray(42)); 160 this->expectValues(Copy2, 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
