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 std::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], *std::next(V.begin(), i)); 76 } 77 EXPECT_EQ(V.end(), std::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 TypeParam Move(std::move(Copy2)); 161 this->expectValues(Move, this->testArray(42)); 162 this->expectValues(Copy2, this->testArray(0)); 163 } 164 165 TYPED_TEST(TinyPtrVectorTest, CopyAndMoveTest) { 166 this->V = this->V2; 167 this->expectValues(this->V, this->testArray(0)); 168 this->expectValues(this->V2, this->testArray(0)); 169 this->V = std::move(this->V2); 170 this->expectValues(this->V, this->testArray(0)); 171 172 this->setVectors(this->testArray(1), this->testArray(0)); 173 this->V = this->V2; 174 this->expectValues(this->V, this->testArray(0)); 175 this->expectValues(this->V2, this->testArray(0)); 176 this->setVectors(this->testArray(1), this->testArray(0)); 177 this->V = std::move(this->V2); 178 this->expectValues(this->V, this->testArray(0)); 179 180 this->setVectors(this->testArray(2), this->testArray(0)); 181 this->V = this->V2; 182 this->expectValues(this->V, this->testArray(0)); 183 this->expectValues(this->V2, this->testArray(0)); 184 this->setVectors(this->testArray(2), this->testArray(0)); 185 this->V = std::move(this->V2); 186 this->expectValues(this->V, this->testArray(0)); 187 188 this->setVectors(this->testArray(42), this->testArray(0)); 189 this->V = this->V2; 190 this->expectValues(this->V, this->testArray(0)); 191 this->expectValues(this->V2, this->testArray(0)); 192 this->setVectors(this->testArray(42), this->testArray(0)); 193 this->V = std::move(this->V2); 194 this->expectValues(this->V, this->testArray(0)); 195 196 this->setVectors(this->testArray(0), this->testArray(1)); 197 this->V = this->V2; 198 this->expectValues(this->V, this->testArray(1)); 199 this->expectValues(this->V2, this->testArray(1)); 200 this->setVectors(this->testArray(0), this->testArray(1)); 201 this->V = std::move(this->V2); 202 this->expectValues(this->V, this->testArray(1)); 203 204 this->setVectors(this->testArray(0), this->testArray(2)); 205 this->V = this->V2; 206 this->expectValues(this->V, this->testArray(2)); 207 this->expectValues(this->V2, this->testArray(2)); 208 this->setVectors(this->testArray(0), this->testArray(2)); 209 this->V = std::move(this->V2); 210 this->expectValues(this->V, this->testArray(2)); 211 212 this->setVectors(this->testArray(0), this->testArray(42)); 213 this->V = this->V2; 214 this->expectValues(this->V, this->testArray(42)); 215 this->expectValues(this->V2, this->testArray(42)); 216 this->setVectors(this->testArray(0), this->testArray(42)); 217 this->V = std::move(this->V2); 218 this->expectValues(this->V, this->testArray(42)); 219 220 this->setVectors(this->testArray(1), this->testArray(1)); 221 this->V = this->V2; 222 this->expectValues(this->V, this->testArray(1)); 223 this->expectValues(this->V2, this->testArray(1)); 224 this->V = std::move(this->V2); 225 this->expectValues(this->V, this->testArray(1)); 226 227 this->setVectors(this->testArray(1), this->testArray(2)); 228 this->V = this->V2; 229 this->expectValues(this->V, this->testArray(2)); 230 this->expectValues(this->V2, this->testArray(2)); 231 this->setVectors(this->testArray(1), this->testArray(2)); 232 this->V = std::move(this->V2); 233 this->expectValues(this->V, this->testArray(2)); 234 235 this->setVectors(this->testArray(1), this->testArray(42)); 236 this->V = this->V2; 237 this->expectValues(this->V, this->testArray(42)); 238 this->expectValues(this->V2, this->testArray(42)); 239 this->setVectors(this->testArray(1), this->testArray(42)); 240 this->V = std::move(this->V2); 241 this->expectValues(this->V, this->testArray(42)); 242 243 this->setVectors(this->testArray(2), this->testArray(1)); 244 this->V = this->V2; 245 this->expectValues(this->V, this->testArray(1)); 246 this->expectValues(this->V2, this->testArray(1)); 247 this->setVectors(this->testArray(2), this->testArray(1)); 248 this->V = std::move(this->V2); 249 this->expectValues(this->V, this->testArray(1)); 250 251 this->setVectors(this->testArray(2), this->testArray(2)); 252 this->V = this->V2; 253 this->expectValues(this->V, this->testArray(2)); 254 this->expectValues(this->V2, this->testArray(2)); 255 this->setVectors(this->testArray(2), this->testArray(2)); 256 this->V = std::move(this->V2); 257 this->expectValues(this->V, this->testArray(2)); 258 259 this->setVectors(this->testArray(2), this->testArray(42)); 260 this->V = this->V2; 261 this->expectValues(this->V, this->testArray(42)); 262 this->expectValues(this->V2, this->testArray(42)); 263 this->setVectors(this->testArray(2), this->testArray(42)); 264 this->V = std::move(this->V2); 265 this->expectValues(this->V, this->testArray(42)); 266 267 this->setVectors(this->testArray(42), this->testArray(1)); 268 this->V = this->V2; 269 this->expectValues(this->V, this->testArray(1)); 270 this->expectValues(this->V2, this->testArray(1)); 271 this->setVectors(this->testArray(42), this->testArray(1)); 272 this->V = std::move(this->V2); 273 this->expectValues(this->V, this->testArray(1)); 274 275 this->setVectors(this->testArray(42), 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 this->setVectors(this->testArray(42), this->testArray(2)); 280 this->V = std::move(this->V2); 281 this->expectValues(this->V, this->testArray(2)); 282 283 this->setVectors(this->testArray(42), this->testArray(42)); 284 this->V = this->V2; 285 this->expectValues(this->V, this->testArray(42)); 286 this->expectValues(this->V2, this->testArray(42)); 287 this->setVectors(this->testArray(42), this->testArray(42)); 288 this->V = std::move(this->V2); 289 this->expectValues(this->V, this->testArray(42)); 290 } 291 292 TYPED_TEST(TinyPtrVectorTest, EraseTest) { 293 this->appendValues(this->V, this->testArray(1)); 294 this->expectValues(this->V, this->testArray(1)); 295 this->V.erase(this->V.begin()); 296 this->expectValues(this->V, this->testArray(0)); 297 298 this->appendValues(this->V, this->testArray(42)); 299 this->expectValues(this->V, this->testArray(42)); 300 this->V.erase(this->V.begin()); 301 this->TestPtrs.erase(this->TestPtrs.begin()); 302 this->expectValues(this->V, this->testArray(41)); 303 this->V.erase(std::next(this->V.begin(), 1)); 304 this->TestPtrs.erase(std::next(this->TestPtrs.begin(), 1)); 305 this->expectValues(this->V, this->testArray(40)); 306 this->V.erase(std::next(this->V.begin(), 2)); 307 this->TestPtrs.erase(std::next(this->TestPtrs.begin(), 2)); 308 this->expectValues(this->V, this->testArray(39)); 309 this->V.erase(std::next(this->V.begin(), 5)); 310 this->TestPtrs.erase(std::next(this->TestPtrs.begin(), 5)); 311 this->expectValues(this->V, this->testArray(38)); 312 this->V.erase(std::next(this->V.begin(), 13)); 313 this->TestPtrs.erase(std::next(this->TestPtrs.begin(), 13)); 314 this->expectValues(this->V, this->testArray(37)); 315 316 typename TypeParam::iterator I = this->V.begin(); 317 do { 318 I = this->V.erase(I); 319 } while (I != this->V.end()); 320 this->expectValues(this->V, this->testArray(0)); 321 } 322 323 TYPED_TEST(TinyPtrVectorTest, EraseRangeTest) { 324 this->appendValues(this->V, this->testArray(1)); 325 this->expectValues(this->V, this->testArray(1)); 326 this->V.erase(this->V.begin(), this->V.begin()); 327 this->expectValues(this->V, this->testArray(1)); 328 this->V.erase(this->V.end(), this->V.end()); 329 this->expectValues(this->V, this->testArray(1)); 330 this->V.erase(this->V.begin(), this->V.end()); 331 this->expectValues(this->V, this->testArray(0)); 332 333 this->appendValues(this->V, this->testArray(42)); 334 this->expectValues(this->V, this->testArray(42)); 335 this->V.erase(this->V.begin(), std::next(this->V.begin(), 1)); 336 this->TestPtrs.erase(this->TestPtrs.begin(), 337 std::next(this->TestPtrs.begin(), 1)); 338 this->expectValues(this->V, this->testArray(41)); 339 this->V.erase(std::next(this->V.begin(), 1), std::next(this->V.begin(), 2)); 340 this->TestPtrs.erase(std::next(this->TestPtrs.begin(), 1), 341 std::next(this->TestPtrs.begin(), 2)); 342 this->expectValues(this->V, this->testArray(40)); 343 this->V.erase(std::next(this->V.begin(), 2), std::next(this->V.begin(), 4)); 344 this->TestPtrs.erase(std::next(this->TestPtrs.begin(), 2), 345 std::next(this->TestPtrs.begin(), 4)); 346 this->expectValues(this->V, this->testArray(38)); 347 this->V.erase(std::next(this->V.begin(), 5), std::next(this->V.begin(), 10)); 348 this->TestPtrs.erase(std::next(this->TestPtrs.begin(), 5), 349 std::next(this->TestPtrs.begin(), 10)); 350 this->expectValues(this->V, this->testArray(33)); 351 this->V.erase(std::next(this->V.begin(), 13), std::next(this->V.begin(), 26)); 352 this->TestPtrs.erase(std::next(this->TestPtrs.begin(), 13), 353 std::next(this->TestPtrs.begin(), 26)); 354 this->expectValues(this->V, this->testArray(20)); 355 this->V.erase(std::next(this->V.begin(), 7), this->V.end()); 356 this->expectValues(this->V, this->testArray(7)); 357 this->V.erase(this->V.begin(), this->V.end()); 358 this->expectValues(this->V, this->testArray(0)); 359 } 360 361 TYPED_TEST(TinyPtrVectorTest, Insert) { 362 this->V.insert(this->V.end(), this->TestPtrs[0]); 363 this->expectValues(this->V, this->testArray(1)); 364 this->V.clear(); 365 this->appendValues(this->V, this->testArray(4)); 366 this->expectValues(this->V, this->testArray(4)); 367 this->V.insert(this->V.end(), this->TestPtrs[4]); 368 this->expectValues(this->V, this->testArray(5)); 369 this->V.insert(this->V.begin(), this->TestPtrs[42]); 370 this->TestPtrs.insert(this->TestPtrs.begin(), this->TestPtrs[42]); 371 this->expectValues(this->V, this->testArray(6)); 372 this->V.insert(std::next(this->V.begin(), 3), this->TestPtrs[43]); 373 this->TestPtrs.insert(std::next(this->TestPtrs.begin(), 3), 374 this->TestPtrs[43]); 375 this->expectValues(this->V, this->testArray(7)); 376 } 377 378 TYPED_TEST(TinyPtrVectorTest, InsertRange) { 379 this->V.insert(this->V.end(), this->TestPtrs.begin(), this->TestPtrs.begin()); 380 this->expectValues(this->V, this->testArray(0)); 381 this->V.insert(this->V.begin(), this->TestPtrs.begin(), 382 this->TestPtrs.begin()); 383 this->expectValues(this->V, this->testArray(0)); 384 this->V.insert(this->V.end(), this->TestPtrs.end(), this->TestPtrs.end()); 385 this->expectValues(this->V, this->testArray(0)); 386 this->V.insert(this->V.end(), this->TestPtrs.begin(), 387 std::next(this->TestPtrs.begin())); 388 this->expectValues(this->V, this->testArray(1)); 389 this->V.clear(); 390 this->V.insert(this->V.end(), this->TestPtrs.begin(), 391 std::next(this->TestPtrs.begin(), 2)); 392 this->expectValues(this->V, this->testArray(2)); 393 this->V.clear(); 394 this->V.insert(this->V.end(), this->TestPtrs.begin(), 395 std::next(this->TestPtrs.begin(), 42)); 396 this->expectValues(this->V, this->testArray(42)); 397 this->V.clear(); 398 this->V.insert(this->V.end(), 399 std::next(this->TestPtrs.begin(), 5), 400 std::next(this->TestPtrs.begin(), 13)); 401 this->V.insert(this->V.begin(), 402 std::next(this->TestPtrs.begin(), 0), 403 std::next(this->TestPtrs.begin(), 3)); 404 this->V.insert(std::next(this->V.begin(), 2), 405 std::next(this->TestPtrs.begin(), 2), 406 std::next(this->TestPtrs.begin(), 4)); 407 this->V.erase(std::next(this->V.begin(), 4)); 408 this->V.insert(std::next(this->V.begin(), 4), 409 std::next(this->TestPtrs.begin(), 4), 410 std::next(this->TestPtrs.begin(), 5)); 411 this->expectValues(this->V, this->testArray(13)); 412 } 413 414 } 415
