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