From 40dab1059e72d3af59f2523fa8a7d05f40dafca5 Mon Sep 17 00:00:00 2001 From: Chandler Carruth Date: Tue, 31 Jul 2012 02:48:31 +0000 Subject: Bring TinyPtrVector under test. Somehow we never picked up unit tests for this class. These tests exercise most of the basic properties, but the API for TinyPtrVector is very strange currently. My plan is to start fleshing out the API to match that of SmallVector, but I wanted a test for what is there first. Sadly, it doesn't look reasonable to just re-use the SmallVector tests, as this container can only ever store pointers, and much of the SmallVector testing is to get construction and destruction right. Just to get this basic test working, I had to add value_type to the interface. While here I found a subtle bug in the combination of 'erase', 'begin', and 'end'. Both 'begin' and 'end' wanted to use a null pointer to indicate the "end" iterator of an empty vector, regardless of whether there is actually a vector allocated or the pointer union is null. Everything else was fine with this except for erase. If you erase the last element of a vector after it has held more than one element, we return the end iterator of the underlying SmallVector which need not be a null pointer. Instead, simply use the pointer, and poniter + size() begin/end definitions in the tiny case, and delegate to the inner vector whenever it is present. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@161024 91177308-0d34-0410-b5e6-96231b3b80d8 --- unittests/ADT/TinyPtrVectorTest.cpp | 191 ++++++++++++++++++++++++++++++++++++ 1 file changed, 191 insertions(+) create mode 100644 unittests/ADT/TinyPtrVectorTest.cpp (limited to 'unittests/ADT/TinyPtrVectorTest.cpp') diff --git a/unittests/ADT/TinyPtrVectorTest.cpp b/unittests/ADT/TinyPtrVectorTest.cpp new file mode 100644 index 0000000..9f02b3c --- /dev/null +++ b/unittests/ADT/TinyPtrVectorTest.cpp @@ -0,0 +1,191 @@ +//===- llvm/unittest/ADT/TinyPtrVectorTest.cpp ----------------------------===// +// +// The LLVM Compiler Infrastructure +// +// This file is distributed under the University of Illinois Open Source +// License. See LICENSE.TXT for details. +// +//===----------------------------------------------------------------------===// +// +// TinyPtrVector unit tests. +// +//===----------------------------------------------------------------------===// + +#include "gtest/gtest.h" +#include "llvm/ADT/ArrayRef.h" +#include "llvm/ADT/SmallVector.h" +#include "llvm/ADT/STLExtras.h" +#include "llvm/ADT/TinyPtrVector.h" +#include "llvm/Support/type_traits.h" +#include +#include +#include + +using namespace llvm; + +namespace { + +// The world's worst RNG, but it is deterministic and makes it easy to get +// *some* shuffling of elements. +static ptrdiff_t test_shuffle_rng(ptrdiff_t i) { + return (i + i * 33) % i; +} +static ptrdiff_t (*test_shuffle_rng_p)(ptrdiff_t) = &test_shuffle_rng; + +template +class TinyPtrVectorTest : public testing::Test { +protected: + typedef typename VectorT::value_type PtrT; + typedef typename remove_pointer::type ValueT; + + VectorT V; + VectorT V2; + + ValueT TestValues[1024]; + std::vector TestPtrs; + + TinyPtrVectorTest() { + for (size_t i = 0, e = array_lengthof(TestValues); i != e; ++i) + TestPtrs.push_back(&TestValues[i]); + + std::random_shuffle(TestPtrs.begin(), TestPtrs.end(), test_shuffle_rng_p); + } + + ArrayRef testArray(size_t N) { + return makeArrayRef(&TestPtrs[0], N); + } + + void appendValues(VectorT &V, ArrayRef Values) { + for (size_t i = 0, e = Values.size(); i != e; ++i) + V.push_back(Values[i]); + } + + void expectValues(const VectorT &V, ArrayRef Values) { + EXPECT_EQ(Values.empty(), V.empty()); + EXPECT_EQ(Values.size(), V.size()); + for (size_t i = 0, e = Values.size(); i != e; ++i) { + EXPECT_EQ(Values[i], V[i]); + EXPECT_EQ(Values[i], *llvm::next(V.begin(), i)); + } + EXPECT_EQ(V.end(), llvm::next(V.begin(), Values.size())); + } +}; + +typedef ::testing::Types, + TinyPtrVector + > TinyPtrVectorTestTypes; +TYPED_TEST_CASE(TinyPtrVectorTest, TinyPtrVectorTestTypes); + +TYPED_TEST(TinyPtrVectorTest, EmptyTest) { + this->expectValues(this->V, this->testArray(0)); +} + +TYPED_TEST(TinyPtrVectorTest, PushPopBack) { + this->V.push_back(this->TestPtrs[0]); + this->expectValues(this->V, this->testArray(1)); + this->V.push_back(this->TestPtrs[1]); + this->expectValues(this->V, this->testArray(2)); + this->V.push_back(this->TestPtrs[2]); + this->expectValues(this->V, this->testArray(3)); + this->V.push_back(this->TestPtrs[3]); + this->expectValues(this->V, this->testArray(4)); + this->V.push_back(this->TestPtrs[4]); + this->expectValues(this->V, this->testArray(5)); + + // Pop and clobber a few values to keep things interesting. + this->V.pop_back(); + this->expectValues(this->V, this->testArray(4)); + this->V.pop_back(); + this->expectValues(this->V, this->testArray(3)); + this->TestPtrs[3] = &this->TestValues[42]; + this->TestPtrs[4] = &this->TestValues[43]; + this->V.push_back(this->TestPtrs[3]); + this->expectValues(this->V, this->testArray(4)); + this->V.push_back(this->TestPtrs[4]); + this->expectValues(this->V, this->testArray(5)); + + this->V.pop_back(); + this->expectValues(this->V, this->testArray(4)); + this->V.pop_back(); + this->expectValues(this->V, this->testArray(3)); + this->V.pop_back(); + this->expectValues(this->V, this->testArray(2)); + this->V.pop_back(); + this->expectValues(this->V, this->testArray(1)); + this->V.pop_back(); + this->expectValues(this->V, this->testArray(0)); + + this->appendValues(this->V, this->testArray(42)); + this->expectValues(this->V, this->testArray(42)); +} + +TYPED_TEST(TinyPtrVectorTest, ClearTest) { + this->expectValues(this->V, this->testArray(0)); + this->V.clear(); + this->expectValues(this->V, this->testArray(0)); + + this->appendValues(this->V, this->testArray(1)); + this->expectValues(this->V, this->testArray(1)); + this->V.clear(); + this->expectValues(this->V, this->testArray(0)); + + this->appendValues(this->V, this->testArray(42)); + this->expectValues(this->V, this->testArray(42)); + this->V.clear(); + this->expectValues(this->V, this->testArray(0)); +} + +TYPED_TEST(TinyPtrVectorTest, CopyAndMoveCtorTest) { + this->appendValues(this->V, this->testArray(42)); + TypeParam Copy(this->V); + this->expectValues(Copy, this->testArray(42)); + + // This is a separate copy, and so it shouldn't destroy the original. + Copy.clear(); + this->expectValues(Copy, this->testArray(0)); + this->expectValues(this->V, this->testArray(42)); + + TypeParam Copy2(this->V2); + this->appendValues(Copy2, this->testArray(42)); + this->expectValues(Copy2, this->testArray(42)); + this->expectValues(this->V2, this->testArray(0)); + +#if LLVM_USE_RVALUE_REFERENCES + TypeParam Move(std::move(Copy2)); + this->expectValues(Move, this->testArray(42)); + this->expectValues(Copy2, this->testArray(0)); +#endif +} + +TYPED_TEST(TinyPtrVectorTest, EraseTest) { + this->appendValues(this->V, this->testArray(1)); + this->expectValues(this->V, this->testArray(1)); + this->V.erase(this->V.begin()); + this->expectValues(this->V, this->testArray(0)); + + this->appendValues(this->V, this->testArray(42)); + this->expectValues(this->V, this->testArray(42)); + this->V.erase(this->V.begin()); + this->TestPtrs.erase(this->TestPtrs.begin()); + this->expectValues(this->V, this->testArray(41)); + this->V.erase(llvm::next(this->V.begin(), 1)); + this->TestPtrs.erase(llvm::next(this->TestPtrs.begin(), 1)); + this->expectValues(this->V, this->testArray(40)); + this->V.erase(llvm::next(this->V.begin(), 2)); + this->TestPtrs.erase(llvm::next(this->TestPtrs.begin(), 2)); + this->expectValues(this->V, this->testArray(39)); + this->V.erase(llvm::next(this->V.begin(), 5)); + this->TestPtrs.erase(llvm::next(this->TestPtrs.begin(), 5)); + this->expectValues(this->V, this->testArray(38)); + this->V.erase(llvm::next(this->V.begin(), 13)); + this->TestPtrs.erase(llvm::next(this->TestPtrs.begin(), 13)); + this->expectValues(this->V, this->testArray(37)); + + typename TypeParam::iterator I = this->V.begin(); + do { + I = this->V.erase(I); + } while (I != this->V.end()); + this->expectValues(this->V, this->testArray(0)); +} + +} -- cgit v1.1 From 06bd8ca8c276d9bc20b192188224e1e5215666a0 Mon Sep 17 00:00:00 2001 From: Chandler Carruth Date: Tue, 31 Jul 2012 09:42:24 +0000 Subject: Implement copy and move assignment for TinyPtrVector. These try to re-use allocated vectors as much as possible. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@161041 91177308-0d34-0410-b5e6-96231b3b80d8 --- unittests/ADT/TinyPtrVectorTest.cpp | 166 ++++++++++++++++++++++++++++++++++++ 1 file changed, 166 insertions(+) (limited to 'unittests/ADT/TinyPtrVectorTest.cpp') diff --git a/unittests/ADT/TinyPtrVectorTest.cpp b/unittests/ADT/TinyPtrVectorTest.cpp index 9f02b3c..9493927 100644 --- a/unittests/ADT/TinyPtrVectorTest.cpp +++ b/unittests/ADT/TinyPtrVectorTest.cpp @@ -60,6 +60,13 @@ protected: V.push_back(Values[i]); } + void setVectors(ArrayRef Values1, ArrayRef Values2) { + V.clear(); + appendValues(V, Values1); + V2.clear(); + appendValues(V2, Values2); + } + void expectValues(const VectorT &V, ArrayRef Values) { EXPECT_EQ(Values.empty(), V.empty()); EXPECT_EQ(Values.size(), V.size()); @@ -157,6 +164,165 @@ TYPED_TEST(TinyPtrVectorTest, CopyAndMoveCtorTest) { #endif } +TYPED_TEST(TinyPtrVectorTest, CopyAndMoveTest) { + this->V = this->V2; + this->expectValues(this->V, this->testArray(0)); + this->expectValues(this->V2, this->testArray(0)); +#if LLVM_USE_RVALUE_REFERENCES + this->V = std::move(this->V2); + this->expectValues(this->V, this->testArray(0)); +#endif + + this->setVectors(this->testArray(1), this->testArray(0)); + this->V = this->V2; + this->expectValues(this->V, this->testArray(0)); + this->expectValues(this->V2, this->testArray(0)); +#if LLVM_USE_RVALUE_REFERENCES + this->setVectors(this->testArray(1), this->testArray(0)); + this->V = std::move(this->V2); + this->expectValues(this->V, this->testArray(0)); +#endif + + this->setVectors(this->testArray(2), this->testArray(0)); + this->V = this->V2; + this->expectValues(this->V, this->testArray(0)); + this->expectValues(this->V2, this->testArray(0)); +#if LLVM_USE_RVALUE_REFERENCES + this->setVectors(this->testArray(2), this->testArray(0)); + this->V = std::move(this->V2); + this->expectValues(this->V, this->testArray(0)); +#endif + + this->setVectors(this->testArray(42), this->testArray(0)); + this->V = this->V2; + this->expectValues(this->V, this->testArray(0)); + this->expectValues(this->V2, this->testArray(0)); +#if LLVM_USE_RVALUE_REFERENCES + this->setVectors(this->testArray(42), this->testArray(0)); + this->V = std::move(this->V2); + this->expectValues(this->V, this->testArray(0)); +#endif + + this->setVectors(this->testArray(0), this->testArray(1)); + this->V = this->V2; + this->expectValues(this->V, this->testArray(1)); + this->expectValues(this->V2, this->testArray(1)); +#if LLVM_USE_RVALUE_REFERENCES + this->setVectors(this->testArray(0), this->testArray(1)); + this->V = std::move(this->V2); + this->expectValues(this->V, this->testArray(1)); +#endif + + this->setVectors(this->testArray(0), this->testArray(2)); + this->V = this->V2; + this->expectValues(this->V, this->testArray(2)); + this->expectValues(this->V2, this->testArray(2)); +#if LLVM_USE_RVALUE_REFERENCES + this->setVectors(this->testArray(0), this->testArray(2)); + this->V = std::move(this->V2); + this->expectValues(this->V, this->testArray(2)); +#endif + + this->setVectors(this->testArray(0), this->testArray(42)); + this->V = this->V2; + this->expectValues(this->V, this->testArray(42)); + this->expectValues(this->V2, this->testArray(42)); +#if LLVM_USE_RVALUE_REFERENCES + this->setVectors(this->testArray(0), this->testArray(42)); + this->V = std::move(this->V2); + this->expectValues(this->V, this->testArray(42)); +#endif + + this->setVectors(this->testArray(1), this->testArray(1)); + this->V = this->V2; + this->expectValues(this->V, this->testArray(1)); + this->expectValues(this->V2, this->testArray(1)); +#if LLVM_USE_RVALUE_REFERENCES + this->V = std::move(this->V2); + this->expectValues(this->V, this->testArray(1)); +#endif + + this->setVectors(this->testArray(1), this->testArray(2)); + this->V = this->V2; + this->expectValues(this->V, this->testArray(2)); + this->expectValues(this->V2, this->testArray(2)); +#if LLVM_USE_RVALUE_REFERENCES + this->setVectors(this->testArray(1), this->testArray(2)); + this->V = std::move(this->V2); + this->expectValues(this->V, this->testArray(2)); +#endif + + this->setVectors(this->testArray(1), this->testArray(42)); + this->V = this->V2; + this->expectValues(this->V, this->testArray(42)); + this->expectValues(this->V2, this->testArray(42)); +#if LLVM_USE_RVALUE_REFERENCES + this->setVectors(this->testArray(1), this->testArray(42)); + this->V = std::move(this->V2); + this->expectValues(this->V, this->testArray(42)); +#endif + + this->setVectors(this->testArray(2), this->testArray(1)); + this->V = this->V2; + this->expectValues(this->V, this->testArray(1)); + this->expectValues(this->V2, this->testArray(1)); +#if LLVM_USE_RVALUE_REFERENCES + this->setVectors(this->testArray(2), this->testArray(1)); + this->V = std::move(this->V2); + this->expectValues(this->V, this->testArray(1)); +#endif + + this->setVectors(this->testArray(2), this->testArray(2)); + this->V = this->V2; + this->expectValues(this->V, this->testArray(2)); + this->expectValues(this->V2, this->testArray(2)); +#if LLVM_USE_RVALUE_REFERENCES + this->setVectors(this->testArray(2), this->testArray(2)); + this->V = std::move(this->V2); + this->expectValues(this->V, this->testArray(2)); +#endif + + this->setVectors(this->testArray(2), this->testArray(42)); + this->V = this->V2; + this->expectValues(this->V, this->testArray(42)); + this->expectValues(this->V2, this->testArray(42)); +#if LLVM_USE_RVALUE_REFERENCES + this->setVectors(this->testArray(2), this->testArray(42)); + this->V = std::move(this->V2); + this->expectValues(this->V, this->testArray(42)); +#endif + + this->setVectors(this->testArray(42), this->testArray(1)); + this->V = this->V2; + this->expectValues(this->V, this->testArray(1)); + this->expectValues(this->V2, this->testArray(1)); +#if LLVM_USE_RVALUE_REFERENCES + this->setVectors(this->testArray(42), this->testArray(1)); + this->V = std::move(this->V2); + this->expectValues(this->V, this->testArray(1)); +#endif + + this->setVectors(this->testArray(42), this->testArray(2)); + this->V = this->V2; + this->expectValues(this->V, this->testArray(2)); + this->expectValues(this->V2, this->testArray(2)); +#if LLVM_USE_RVALUE_REFERENCES + this->setVectors(this->testArray(42), this->testArray(2)); + this->V = std::move(this->V2); + this->expectValues(this->V, this->testArray(2)); +#endif + + this->setVectors(this->testArray(42), this->testArray(42)); + this->V = this->V2; + this->expectValues(this->V, this->testArray(42)); + this->expectValues(this->V2, this->testArray(42)); +#if LLVM_USE_RVALUE_REFERENCES + this->setVectors(this->testArray(42), this->testArray(42)); + this->V = std::move(this->V2); + this->expectValues(this->V, this->testArray(42)); +#endif +} + TYPED_TEST(TinyPtrVectorTest, EraseTest) { this->appendValues(this->V, this->testArray(1)); this->expectValues(this->V, this->testArray(1)); -- cgit v1.1 From 147d9e05116518461653695a6022f6109f0eb936 Mon Sep 17 00:00:00 2001 From: Chandler Carruth Date: Wed, 1 Aug 2012 08:40:48 +0000 Subject: Add range erase, element insert, and range insert methods to TinyPtrVector. With these, it is sufficiently functional for my more normal / pedestrian uses. I've not included some r-value reference stuff here because the value type for a TinyPtrVector is, necessarily, just a pointer. I've added tests that cover the basic behavior of these routines, but they aren't as comprehensive as I'd like. In particular, they don't really test the iterator semantics as thoroughly as they should. Maybe some brave soul will feel enterprising and flesh them out. ;] git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@161104 91177308-0d34-0410-b5e6-96231b3b80d8 --- unittests/ADT/TinyPtrVectorTest.cpp | 91 +++++++++++++++++++++++++++++++++++++ 1 file changed, 91 insertions(+) (limited to 'unittests/ADT/TinyPtrVectorTest.cpp') diff --git a/unittests/ADT/TinyPtrVectorTest.cpp b/unittests/ADT/TinyPtrVectorTest.cpp index 9493927..05dd797 100644 --- a/unittests/ADT/TinyPtrVectorTest.cpp +++ b/unittests/ADT/TinyPtrVectorTest.cpp @@ -354,4 +354,95 @@ TYPED_TEST(TinyPtrVectorTest, EraseTest) { this->expectValues(this->V, this->testArray(0)); } +TYPED_TEST(TinyPtrVectorTest, EraseRangeTest) { + this->appendValues(this->V, this->testArray(1)); + this->expectValues(this->V, this->testArray(1)); + this->V.erase(this->V.begin(), this->V.begin()); + this->expectValues(this->V, this->testArray(1)); + this->V.erase(this->V.end(), this->V.end()); + this->expectValues(this->V, this->testArray(1)); + this->V.erase(this->V.begin(), this->V.end()); + this->expectValues(this->V, this->testArray(0)); + + this->appendValues(this->V, this->testArray(42)); + this->expectValues(this->V, this->testArray(42)); + this->V.erase(this->V.begin(), llvm::next(this->V.begin(), 1)); + this->TestPtrs.erase(this->TestPtrs.begin(), + llvm::next(this->TestPtrs.begin(), 1)); + this->expectValues(this->V, this->testArray(41)); + this->V.erase(llvm::next(this->V.begin(), 1), llvm::next(this->V.begin(), 2)); + this->TestPtrs.erase(llvm::next(this->TestPtrs.begin(), 1), + llvm::next(this->TestPtrs.begin(), 2)); + this->expectValues(this->V, this->testArray(40)); + this->V.erase(llvm::next(this->V.begin(), 2), llvm::next(this->V.begin(), 4)); + this->TestPtrs.erase(llvm::next(this->TestPtrs.begin(), 2), + llvm::next(this->TestPtrs.begin(), 4)); + this->expectValues(this->V, this->testArray(38)); + this->V.erase(llvm::next(this->V.begin(), 5), llvm::next(this->V.begin(), 10)); + this->TestPtrs.erase(llvm::next(this->TestPtrs.begin(), 5), + llvm::next(this->TestPtrs.begin(), 10)); + this->expectValues(this->V, this->testArray(33)); + this->V.erase(llvm::next(this->V.begin(), 13), llvm::next(this->V.begin(), 26)); + this->TestPtrs.erase(llvm::next(this->TestPtrs.begin(), 13), + llvm::next(this->TestPtrs.begin(), 26)); + this->expectValues(this->V, this->testArray(20)); + this->V.erase(llvm::next(this->V.begin(), 7), this->V.end()); + this->expectValues(this->V, this->testArray(7)); + this->V.erase(this->V.begin(), this->V.end()); + this->expectValues(this->V, this->testArray(0)); +} + +TYPED_TEST(TinyPtrVectorTest, Insert) { + this->V.insert(this->V.end(), this->TestPtrs[0]); + this->expectValues(this->V, this->testArray(1)); + this->V.clear(); + this->appendValues(this->V, this->testArray(4)); + this->expectValues(this->V, this->testArray(4)); + this->V.insert(this->V.end(), this->TestPtrs[4]); + this->expectValues(this->V, this->testArray(5)); + this->V.insert(this->V.begin(), this->TestPtrs[42]); + this->TestPtrs.insert(this->TestPtrs.begin(), this->TestPtrs[42]); + this->expectValues(this->V, this->testArray(6)); + this->V.insert(llvm::next(this->V.begin(), 3), this->TestPtrs[43]); + this->TestPtrs.insert(llvm::next(this->TestPtrs.begin(), 3), + this->TestPtrs[43]); + this->expectValues(this->V, this->testArray(7)); +} + +TYPED_TEST(TinyPtrVectorTest, InsertRange) { + this->V.insert(this->V.end(), this->TestPtrs.begin(), this->TestPtrs.begin()); + this->expectValues(this->V, this->testArray(0)); + this->V.insert(this->V.begin(), this->TestPtrs.begin(), + this->TestPtrs.begin()); + this->expectValues(this->V, this->testArray(0)); + this->V.insert(this->V.end(), this->TestPtrs.end(), this->TestPtrs.end()); + this->expectValues(this->V, this->testArray(0)); + this->V.insert(this->V.end(), this->TestPtrs.begin(), + llvm::next(this->TestPtrs.begin())); + this->expectValues(this->V, this->testArray(1)); + this->V.clear(); + this->V.insert(this->V.end(), this->TestPtrs.begin(), + llvm::next(this->TestPtrs.begin(), 2)); + this->expectValues(this->V, this->testArray(2)); + this->V.clear(); + this->V.insert(this->V.end(), this->TestPtrs.begin(), + llvm::next(this->TestPtrs.begin(), 42)); + this->expectValues(this->V, this->testArray(42)); + this->V.clear(); + this->V.insert(this->V.end(), + llvm::next(this->TestPtrs.begin(), 5), + llvm::next(this->TestPtrs.begin(), 13)); + this->V.insert(this->V.begin(), + llvm::next(this->TestPtrs.begin(), 0), + llvm::next(this->TestPtrs.begin(), 3)); + this->V.insert(llvm::next(this->V.begin(), 2), + llvm::next(this->TestPtrs.begin(), 2), + llvm::next(this->TestPtrs.begin(), 4)); + this->V.erase(llvm::next(this->V.begin(), 4)); + this->V.insert(llvm::next(this->V.begin(), 4), + llvm::next(this->TestPtrs.begin(), 4), + llvm::next(this->TestPtrs.begin(), 5)); + this->expectValues(this->V, this->testArray(13)); +} + } -- cgit v1.1