468 lines · cpp
1//===- llvm/unittest/ADT/TinyPtrVectorTest.cpp ----------------------------===//2//3// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.4// See https://llvm.org/LICENSE.txt for license information.5// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception6//7//===----------------------------------------------------------------------===//8//9// TinyPtrVector unit tests.10//11//===----------------------------------------------------------------------===//12 13#include "llvm/ADT/TinyPtrVector.h"14#include "llvm/ADT/ArrayRef.h"15#include "llvm/ADT/STLExtras.h"16#include "llvm/Support/type_traits.h"17#include "gtest/gtest.h"18#include <algorithm>19#include <random>20#include <vector>21 22using namespace llvm;23 24namespace {25template <typename T> struct RemovePointer : std::remove_pointer<T> {};26 27template <typename PointerTy, unsigned IntBits, typename IntType,28 typename PtrTraits, typename Info>29struct RemovePointer<30 PointerIntPair<PointerTy, IntBits, IntType, PtrTraits, Info>> {31 using type = typename RemovePointer<PointerTy>::type;32};33 34template <typename VectorT>35class TinyPtrVectorTest : public testing::Test {36protected:37 using PtrT = typename VectorT::value_type;38 using ValueT = typename RemovePointer<PtrT>::type;39 using PtrTraits = PointerLikeTypeTraits<PtrT>;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 = std::size(TestValues); i != e; ++i)49 TestPtrs.push_back(PtrT(&TestValues[i]));50 51 std::shuffle(TestPtrs.begin(), TestPtrs.end(), std::mt19937{});52 }53 54 PtrT makePtr(ValueT *V) { return PtrT(V); }55 56 ArrayRef<PtrT> testArray(size_t N) { return ArrayRef(&TestPtrs[0], N); }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 81using TinyPtrVectorTestTypes =82 ::testing::Types<TinyPtrVector<int *>, TinyPtrVector<double *>,83 TinyPtrVector<PointerIntPair<int *, 1>>>;84TYPED_TEST_SUITE(TinyPtrVectorTest, TinyPtrVectorTestTypes, );85 86TYPED_TEST(TinyPtrVectorTest, EmptyTest) {87 this->expectValues(this->V, this->testArray(0));88}89 90TYPED_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->makePtr(&this->TestValues[42]);108 this->TestPtrs[4] = this->makePtr(&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 129TYPED_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 145TYPED_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 TypeParam MultipleElements(this->testArray(2));165 TypeParam SingleElement(this->testArray(1));166 MultipleElements = std::move(SingleElement);167 this->expectValues(MultipleElements, this->testArray(1));168 this->expectValues(SingleElement, this->testArray(0));169}170 171TYPED_TEST(TinyPtrVectorTest, CopyAndMoveTest) {172 this->V = this->V2;173 this->expectValues(this->V, this->testArray(0));174 this->expectValues(this->V2, this->testArray(0));175 this->V = std::move(this->V2);176 this->expectValues(this->V, this->testArray(0));177 178 this->setVectors(this->testArray(1), 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(1), this->testArray(0));183 this->V = std::move(this->V2);184 this->expectValues(this->V, this->testArray(0));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 this->setVectors(this->testArray(2), this->testArray(0));191 this->V = std::move(this->V2);192 this->expectValues(this->V, this->testArray(0));193 194 this->setVectors(this->testArray(42), this->testArray(0));195 this->V = this->V2;196 this->expectValues(this->V, this->testArray(0));197 this->expectValues(this->V2, this->testArray(0));198 this->setVectors(this->testArray(42), this->testArray(0));199 this->V = std::move(this->V2);200 this->expectValues(this->V, this->testArray(0));201 202 this->setVectors(this->testArray(0), this->testArray(1));203 this->V = this->V2;204 this->expectValues(this->V, this->testArray(1));205 this->expectValues(this->V2, this->testArray(1));206 this->setVectors(this->testArray(0), this->testArray(1));207 this->V = std::move(this->V2);208 this->expectValues(this->V, this->testArray(1));209 210 this->setVectors(this->testArray(0), this->testArray(2));211 this->V = this->V2;212 this->expectValues(this->V, this->testArray(2));213 this->expectValues(this->V2, this->testArray(2));214 this->setVectors(this->testArray(0), this->testArray(2));215 this->V = std::move(this->V2);216 this->expectValues(this->V, this->testArray(2));217 218 this->setVectors(this->testArray(0), this->testArray(42));219 this->V = this->V2;220 this->expectValues(this->V, this->testArray(42));221 this->expectValues(this->V2, this->testArray(42));222 this->setVectors(this->testArray(0), this->testArray(42));223 this->V = std::move(this->V2);224 this->expectValues(this->V, this->testArray(42));225 226 this->setVectors(this->testArray(1), this->testArray(1));227 this->V = this->V2;228 this->expectValues(this->V, this->testArray(1));229 this->expectValues(this->V2, this->testArray(1));230 this->V = std::move(this->V2);231 this->expectValues(this->V, this->testArray(1));232 233 this->setVectors(this->testArray(1), this->testArray(2));234 this->V = this->V2;235 this->expectValues(this->V, this->testArray(2));236 this->expectValues(this->V2, this->testArray(2));237 this->setVectors(this->testArray(1), this->testArray(2));238 this->V = std::move(this->V2);239 this->expectValues(this->V, this->testArray(2));240 241 this->setVectors(this->testArray(1), this->testArray(42));242 this->V = this->V2;243 this->expectValues(this->V, this->testArray(42));244 this->expectValues(this->V2, this->testArray(42));245 this->setVectors(this->testArray(1), this->testArray(42));246 this->V = std::move(this->V2);247 this->expectValues(this->V, this->testArray(42));248 249 this->setVectors(this->testArray(2), this->testArray(1));250 this->V = this->V2;251 this->expectValues(this->V, this->testArray(1));252 this->expectValues(this->V2, this->testArray(1));253 this->setVectors(this->testArray(2), this->testArray(1));254 this->V = std::move(this->V2);255 this->expectValues(this->V, this->testArray(1));256 257 this->setVectors(this->testArray(2), this->testArray(2));258 this->V = this->V2;259 this->expectValues(this->V, this->testArray(2));260 this->expectValues(this->V2, this->testArray(2));261 this->setVectors(this->testArray(2), this->testArray(2));262 this->V = std::move(this->V2);263 this->expectValues(this->V, this->testArray(2));264 265 this->setVectors(this->testArray(2), this->testArray(42));266 this->V = this->V2;267 this->expectValues(this->V, this->testArray(42));268 this->expectValues(this->V2, this->testArray(42));269 this->setVectors(this->testArray(2), this->testArray(42));270 this->V = std::move(this->V2);271 this->expectValues(this->V, this->testArray(42));272 273 this->setVectors(this->testArray(42), this->testArray(1));274 this->V = this->V2;275 this->expectValues(this->V, this->testArray(1));276 this->expectValues(this->V2, this->testArray(1));277 this->setVectors(this->testArray(42), this->testArray(1));278 this->V = std::move(this->V2);279 this->expectValues(this->V, this->testArray(1));280 281 this->setVectors(this->testArray(42), this->testArray(2));282 this->V = this->V2;283 this->expectValues(this->V, this->testArray(2));284 this->expectValues(this->V2, this->testArray(2));285 this->setVectors(this->testArray(42), this->testArray(2));286 this->V = std::move(this->V2);287 this->expectValues(this->V, this->testArray(2));288 289 this->setVectors(this->testArray(42), this->testArray(42));290 this->V = this->V2;291 this->expectValues(this->V, this->testArray(42));292 this->expectValues(this->V2, this->testArray(42));293 this->setVectors(this->testArray(42), this->testArray(42));294 this->V = std::move(this->V2);295 this->expectValues(this->V, this->testArray(42));296}297 298TYPED_TEST(TinyPtrVectorTest, EraseTest) {299 this->appendValues(this->V, this->testArray(1));300 this->expectValues(this->V, this->testArray(1));301 this->V.erase(this->V.begin());302 this->expectValues(this->V, this->testArray(0));303 304 this->appendValues(this->V, this->testArray(42));305 this->expectValues(this->V, this->testArray(42));306 this->V.erase(this->V.begin());307 this->TestPtrs.erase(this->TestPtrs.begin());308 this->expectValues(this->V, this->testArray(41));309 this->V.erase(std::next(this->V.begin(), 1));310 this->TestPtrs.erase(std::next(this->TestPtrs.begin(), 1));311 this->expectValues(this->V, this->testArray(40));312 this->V.erase(std::next(this->V.begin(), 2));313 this->TestPtrs.erase(std::next(this->TestPtrs.begin(), 2));314 this->expectValues(this->V, this->testArray(39));315 this->V.erase(std::next(this->V.begin(), 5));316 this->TestPtrs.erase(std::next(this->TestPtrs.begin(), 5));317 this->expectValues(this->V, this->testArray(38));318 this->V.erase(std::next(this->V.begin(), 13));319 this->TestPtrs.erase(std::next(this->TestPtrs.begin(), 13));320 this->expectValues(this->V, this->testArray(37));321 322 typename TypeParam::iterator I = this->V.begin();323 do {324 I = this->V.erase(I);325 } while (I != this->V.end());326 this->expectValues(this->V, this->testArray(0));327}328 329TYPED_TEST(TinyPtrVectorTest, EraseRangeTest) {330 this->appendValues(this->V, this->testArray(1));331 this->expectValues(this->V, this->testArray(1));332 this->V.erase(this->V.begin(), this->V.begin());333 this->expectValues(this->V, this->testArray(1));334 this->V.erase(this->V.end(), this->V.end());335 this->expectValues(this->V, this->testArray(1));336 this->V.erase(this->V.begin(), this->V.end());337 this->expectValues(this->V, this->testArray(0));338 339 this->appendValues(this->V, this->testArray(42));340 this->expectValues(this->V, this->testArray(42));341 this->V.erase(this->V.begin(), std::next(this->V.begin(), 1));342 this->TestPtrs.erase(this->TestPtrs.begin(),343 std::next(this->TestPtrs.begin(), 1));344 this->expectValues(this->V, this->testArray(41));345 this->V.erase(std::next(this->V.begin(), 1), std::next(this->V.begin(), 2));346 this->TestPtrs.erase(std::next(this->TestPtrs.begin(), 1),347 std::next(this->TestPtrs.begin(), 2));348 this->expectValues(this->V, this->testArray(40));349 this->V.erase(std::next(this->V.begin(), 2), std::next(this->V.begin(), 4));350 this->TestPtrs.erase(std::next(this->TestPtrs.begin(), 2),351 std::next(this->TestPtrs.begin(), 4));352 this->expectValues(this->V, this->testArray(38));353 this->V.erase(std::next(this->V.begin(), 5), std::next(this->V.begin(), 10));354 this->TestPtrs.erase(std::next(this->TestPtrs.begin(), 5),355 std::next(this->TestPtrs.begin(), 10));356 this->expectValues(this->V, this->testArray(33));357 this->V.erase(std::next(this->V.begin(), 13), std::next(this->V.begin(), 26));358 this->TestPtrs.erase(std::next(this->TestPtrs.begin(), 13),359 std::next(this->TestPtrs.begin(), 26));360 this->expectValues(this->V, this->testArray(20));361 this->V.erase(std::next(this->V.begin(), 7), this->V.end());362 this->expectValues(this->V, this->testArray(7));363 this->V.erase(this->V.begin(), this->V.end());364 this->expectValues(this->V, this->testArray(0));365}366 367TYPED_TEST(TinyPtrVectorTest, Insert) {368 this->V.insert(this->V.end(), this->TestPtrs[0]);369 this->expectValues(this->V, this->testArray(1));370 this->V.clear();371 this->appendValues(this->V, this->testArray(4));372 this->expectValues(this->V, this->testArray(4));373 this->V.insert(this->V.end(), this->TestPtrs[4]);374 this->expectValues(this->V, this->testArray(5));375 this->V.insert(this->V.begin(), this->TestPtrs[42]);376 this->TestPtrs.insert(this->TestPtrs.begin(), this->TestPtrs[42]);377 this->expectValues(this->V, this->testArray(6));378 this->V.insert(std::next(this->V.begin(), 3), this->TestPtrs[43]);379 this->TestPtrs.insert(std::next(this->TestPtrs.begin(), 3),380 this->TestPtrs[43]);381 this->expectValues(this->V, this->testArray(7));382}383 384TYPED_TEST(TinyPtrVectorTest, InsertRange) {385 this->V.insert(this->V.end(), this->TestPtrs.begin(), this->TestPtrs.begin());386 this->expectValues(this->V, this->testArray(0));387 this->V.insert(this->V.begin(), this->TestPtrs.begin(),388 this->TestPtrs.begin());389 this->expectValues(this->V, this->testArray(0));390 this->V.insert(this->V.end(), this->TestPtrs.end(), this->TestPtrs.end());391 this->expectValues(this->V, this->testArray(0));392 this->V.insert(this->V.end(), this->TestPtrs.begin(),393 std::next(this->TestPtrs.begin()));394 this->expectValues(this->V, this->testArray(1));395 this->V.clear();396 this->V.insert(this->V.end(), this->TestPtrs.begin(),397 std::next(this->TestPtrs.begin(), 2));398 this->expectValues(this->V, this->testArray(2));399 this->V.clear();400 this->V.insert(this->V.end(), this->TestPtrs.begin(),401 std::next(this->TestPtrs.begin(), 42));402 this->expectValues(this->V, this->testArray(42));403 this->V.clear();404 this->V.insert(this->V.end(),405 std::next(this->TestPtrs.begin(), 5),406 std::next(this->TestPtrs.begin(), 13));407 this->V.insert(this->V.begin(),408 std::next(this->TestPtrs.begin(), 0),409 std::next(this->TestPtrs.begin(), 3));410 this->V.insert(std::next(this->V.begin(), 2),411 std::next(this->TestPtrs.begin(), 2),412 std::next(this->TestPtrs.begin(), 4));413 this->V.erase(std::next(this->V.begin(), 4));414 this->V.insert(std::next(this->V.begin(), 4),415 std::next(this->TestPtrs.begin(), 4),416 std::next(this->TestPtrs.begin(), 5));417 this->expectValues(this->V, this->testArray(13));418}419 420}421 422TEST(TinyPtrVectorTest, SingleEltCtorTest) {423 int v = 55;424 TinyPtrVector<int *> V(&v);425 426 EXPECT_TRUE(V.size() == 1);427 EXPECT_FALSE(V.empty());428 EXPECT_TRUE(V.front() == &v);429}430 431TEST(TinyPtrVectorTest, ArrayRefCtorTest) {432 int data_array[128];433 std::vector<int *> data;434 435 for (unsigned i = 0, e = 128; i != e; ++i) {436 data_array[i] = 324 - int(i);437 data.push_back(&data_array[i]);438 }439 440 TinyPtrVector<int *> V(data);441 EXPECT_TRUE(V.size() == 128);442 EXPECT_FALSE(V.empty());443 for (unsigned i = 0, e = 128; i != e; ++i) {444 EXPECT_TRUE(V[i] == data[i]);445 }446}447 448TEST(TinyPtrVectorTest, MutableArrayRefTest) {449 int data_array[128];450 std::vector<int *> data;451 452 for (unsigned i = 0, e = 128; i != e; ++i) {453 data_array[i] = 324 - int(i);454 data.push_back(&data_array[i]);455 }456 457 TinyPtrVector<int *> V(data);458 EXPECT_TRUE(V.size() == 128);459 EXPECT_FALSE(V.empty());460 461 MutableArrayRef<int *> mut_array = V;462 for (unsigned i = 0, e = 128; i != e; ++i) {463 EXPECT_TRUE(mut_array[i] == data[i]);464 mut_array[i] = 324 + mut_array[i];465 EXPECT_TRUE(mut_array[i] == (324 + data[i]));466 }467}468