X-Git-Url: http://demsky.eecs.uci.edu/git/?a=blobdiff_plain;f=unittests%2FADT%2FDenseMapTest.cpp;h=2c6fe35883271a6a767b4cad8a5ad4a114b00bd8;hb=f41971f6e7f9e5ba0c590c7e35e2c1af0cd38c69;hp=d61f991bd55d13415c85172d656fa9367619a6e5;hpb=dd9d38d57bbd2161e04af90a9e03011afb039b16;p=oota-llvm.git diff --git a/unittests/ADT/DenseMapTest.cpp b/unittests/ADT/DenseMapTest.cpp index d61f991bd55..2c6fe358832 100644 --- a/unittests/ADT/DenseMapTest.cpp +++ b/unittests/ADT/DenseMapTest.cpp @@ -10,6 +10,7 @@ #include "gtest/gtest.h" #include "llvm/ADT/DenseMap.h" #include +#include using namespace llvm; @@ -29,6 +30,48 @@ uint32_t *getTestValue(int i, uint32_t **) { return &dummy_arr1[i]; } +/// \brief A test class that tries to check that construction and destruction +/// occur correctly. +class CtorTester { + static std::set Constructed; + int Value; + +public: + explicit CtorTester(int Value = 0) : Value(Value) { + EXPECT_TRUE(Constructed.insert(this).second); + } + CtorTester(uint32_t Value) : Value(Value) { + EXPECT_TRUE(Constructed.insert(this).second); + } + CtorTester(const CtorTester &Arg) : Value(Arg.Value) { + EXPECT_TRUE(Constructed.insert(this).second); + } + CtorTester &operator=(const CtorTester &) = default; + ~CtorTester() { + EXPECT_EQ(1u, Constructed.erase(this)); + } + operator uint32_t() const { return Value; } + + int getValue() const { return Value; } + bool operator==(const CtorTester &RHS) const { return Value == RHS.Value; } +}; + +std::set CtorTester::Constructed; + +struct CtorTesterMapInfo { + static inline CtorTester getEmptyKey() { return CtorTester(-1); } + static inline CtorTester getTombstoneKey() { return CtorTester(-2); } + static unsigned getHashValue(const CtorTester &Val) { + return Val.getValue() * 37u; + } + static bool isEqual(const CtorTester &LHS, const CtorTester &RHS) { + return LHS == RHS; + } +}; + +CtorTester getTestKey(int i, CtorTester *) { return CtorTester(i); } +CtorTester getTestValue(int i, CtorTester *) { return CtorTester(42 + i); } + // Test fixture, with helper functions implemented by forwarding to global // function overloads selected by component types of the type parameter. This // allows all of the map implementations to be tested with shared @@ -50,15 +93,18 @@ protected: }; template -typename T::key_type *const DenseMapTest::dummy_key_ptr = 0; +typename T::key_type *const DenseMapTest::dummy_key_ptr = nullptr; template -typename T::mapped_type *const DenseMapTest::dummy_value_ptr = 0; +typename T::mapped_type *const DenseMapTest::dummy_value_ptr = nullptr; // Register these types for testing. typedef ::testing::Types, DenseMap, + DenseMap, SmallDenseMap, - SmallDenseMap + SmallDenseMap, + SmallDenseMap > DenseMapTestTypes; TYPED_TEST_CASE(DenseMapTest, DenseMapTestTypes); @@ -74,7 +120,7 @@ TYPED_TEST(DenseMapTest, EmptyIntMapTest) { // Lookup tests EXPECT_FALSE(this->Map.count(this->getKey())); EXPECT_TRUE(this->Map.find(this->getKey()) == this->Map.end()); -#ifndef _MSC_VER +#if !defined(_MSC_VER) || defined(__clang__) EXPECT_EQ(typename TypeParam::mapped_type(), this->Map.lookup(this->getKey())); #else @@ -164,6 +210,34 @@ TYPED_TEST(DenseMapTest, CopyConstructorTest) { EXPECT_EQ(this->getValue(), copyMap[this->getKey()]); } +// Test copy constructor method where SmallDenseMap isn't small. +TYPED_TEST(DenseMapTest, CopyConstructorNotSmallTest) { + for (int Key = 0; Key < 5; ++Key) + this->Map[this->getKey(Key)] = this->getValue(Key); + TypeParam copyMap(this->Map); + + EXPECT_EQ(5u, copyMap.size()); + for (int Key = 0; Key < 5; ++Key) + EXPECT_EQ(this->getValue(Key), copyMap[this->getKey(Key)]); +} + +// Test copying from a default-constructed map. +TYPED_TEST(DenseMapTest, CopyConstructorFromDefaultTest) { + TypeParam copyMap(this->Map); + + EXPECT_TRUE(copyMap.empty()); +} + +// Test copying from an empty map where SmallDenseMap isn't small. +TYPED_TEST(DenseMapTest, CopyConstructorFromEmptyTest) { + for (int Key = 0; Key < 5; ++Key) + this->Map[this->getKey(Key)] = this->getValue(Key); + this->Map.clear(); + TypeParam copyMap(this->Map); + + EXPECT_TRUE(copyMap.empty()); +} + // Test assignment operator method TYPED_TEST(DenseMapTest, AssignmentTest) { this->Map[this->getKey()] = this->getValue(); @@ -171,6 +245,47 @@ TYPED_TEST(DenseMapTest, AssignmentTest) { EXPECT_EQ(1u, copyMap.size()); EXPECT_EQ(this->getValue(), copyMap[this->getKey()]); + + // test self-assignment. + copyMap = copyMap; + EXPECT_EQ(1u, copyMap.size()); + EXPECT_EQ(this->getValue(), copyMap[this->getKey()]); +} + +// Test swap method +TYPED_TEST(DenseMapTest, SwapTest) { + this->Map[this->getKey()] = this->getValue(); + TypeParam otherMap; + + this->Map.swap(otherMap); + EXPECT_EQ(0u, this->Map.size()); + EXPECT_TRUE(this->Map.empty()); + EXPECT_EQ(1u, otherMap.size()); + EXPECT_EQ(this->getValue(), otherMap[this->getKey()]); + + this->Map.swap(otherMap); + EXPECT_EQ(0u, otherMap.size()); + EXPECT_TRUE(otherMap.empty()); + EXPECT_EQ(1u, this->Map.size()); + EXPECT_EQ(this->getValue(), this->Map[this->getKey()]); + + // Make this more interesting by inserting 100 numbers into the map. + for (int i = 0; i < 100; ++i) + this->Map[this->getKey(i)] = this->getValue(i); + + this->Map.swap(otherMap); + EXPECT_EQ(0u, this->Map.size()); + EXPECT_TRUE(this->Map.empty()); + EXPECT_EQ(100u, otherMap.size()); + for (int i = 0; i < 100; ++i) + EXPECT_EQ(this->getValue(i), otherMap[this->getKey(i)]); + + this->Map.swap(otherMap); + EXPECT_EQ(0u, otherMap.size()); + EXPECT_TRUE(otherMap.empty()); + EXPECT_EQ(100u, this->Map.size()); + for (int i = 0; i < 100; ++i) + EXPECT_EQ(this->getValue(i), this->Map[this->getKey(i)]); } // A more complex iteration test @@ -208,6 +323,31 @@ TYPED_TEST(DenseMapTest, ConstIteratorTest) { EXPECT_TRUE(cit == cit2); } +// Make sure DenseMap works with StringRef keys. +TEST(DenseMapCustomTest, StringRefTest) { + DenseMap M; + + M["a"] = 1; + M["b"] = 2; + M["c"] = 3; + + EXPECT_EQ(3u, M.size()); + EXPECT_EQ(1, M.lookup("a")); + EXPECT_EQ(2, M.lookup("b")); + EXPECT_EQ(3, M.lookup("c")); + + EXPECT_EQ(0, M.lookup("q")); + + // Test the empty string, spelled various ways. + EXPECT_EQ(0, M.lookup("")); + EXPECT_EQ(0, M.lookup(StringRef())); + EXPECT_EQ(0, M.lookup(StringRef("a", 0))); + M[""] = 42; + EXPECT_EQ(42, M.lookup("")); + EXPECT_EQ(42, M.lookup(StringRef())); + EXPECT_EQ(42, M.lookup(StringRef("a", 0))); +} + // Key traits that allows lookup with either an unsigned or char* key; // In the latter case, "a" == 0, "b" == 1 and so on. struct TestDenseMapInfo { @@ -236,7 +376,7 @@ TEST(DenseMapCustomTest, FindAsTest) { EXPECT_EQ(3u, map.size()); // Normal lookup tests - EXPECT_EQ(1, map.count(1)); + EXPECT_EQ(1u, map.count(1)); EXPECT_EQ(1u, map.find(0)->second); EXPECT_EQ(2u, map.find(1)->second); EXPECT_EQ(3u, map.find(2)->second); @@ -249,4 +389,37 @@ TEST(DenseMapCustomTest, FindAsTest) { EXPECT_TRUE(map.find_as("d") == map.end()); } +struct ContiguousDenseMapInfo { + static inline unsigned getEmptyKey() { return ~0; } + static inline unsigned getTombstoneKey() { return ~0U - 1; } + static unsigned getHashValue(const unsigned& Val) { return Val; } + static bool isEqual(const unsigned& LHS, const unsigned& RHS) { + return LHS == RHS; + } +}; + +// Test that filling a small dense map with exactly the number of elements in +// the map grows to have enough space for an empty bucket. +TEST(DenseMapCustomTest, SmallDenseMapGrowTest) { + SmallDenseMap map; + // Add some number of elements, then delete a few to leave us some tombstones. + // If we just filled the map with 32 elements we'd grow because of not enough + // tombstones which masks the issue here. + for (unsigned i = 0; i < 20; ++i) + map[i] = i + 1; + for (unsigned i = 0; i < 10; ++i) + map.erase(i); + for (unsigned i = 20; i < 32; ++i) + map[i] = i + 1; + + // Size tests + EXPECT_EQ(22u, map.size()); + + // Try to find an element which doesn't exist. There was a bug in + // SmallDenseMap which led to a map with num elements == small capacity not + // having an empty bucket any more. Finding an element not in the map would + // therefore never terminate. + EXPECT_TRUE(map.find(32) == map.end()); +} + }