#include "gtest/gtest.h"
#include "llvm/ADT/DenseMap.h"
#include <map>
+#include <set>
using namespace llvm;
namespace {
-// Test fixture
-template <typename T>
-class DenseMapTest : public testing::Test {
-protected:
- T Map;
-
- typename T::key_type getKey(int i = 0);
- typename T::mapped_type getValue(int i = 0);
-};
+uint32_t getTestKey(int i, uint32_t *) { return i; }
+uint32_t getTestValue(int i, uint32_t *) { return 42 + i; }
-template <>
-uint32_t DenseMapTest<DenseMap<uint32_t, uint32_t> >::getKey(int i) {
- return i;
-}
-
-template <>
-uint32_t DenseMapTest<DenseMap<uint32_t, uint32_t> >::getValue(int i) {
- return 42 + i;
+uint32_t *getTestKey(int i, uint32_t **) {
+ static uint32_t dummy_arr1[8192];
+ assert(i < 8192 && "Only support 8192 dummy keys.");
+ return &dummy_arr1[i];
}
-
-template <>
-uint32_t *DenseMapTest<DenseMap<uint32_t *, uint32_t *> >::getKey(int i) {
+uint32_t *getTestValue(int i, uint32_t **) {
static uint32_t dummy_arr1[8192];
assert(i < 8192 && "Only support 8192 dummy keys.");
return &dummy_arr1[i];
}
-template <>
-uint32_t *DenseMapTest<DenseMap<uint32_t *, uint32_t *> >::getValue(int i) {
- static uint32_t dummy_arr2[8192];
- assert(i < 8192 && "Only support 8192 dummy values.");
- return &dummy_arr2[i];
-}
+/// \brief A test class that tries to check that construction and destruction
+/// occur correctly.
+class CtorTester {
+ static std::set<CtorTester *> 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() {
+ 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 *> 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
+// implementations of helper routines.
+template <typename T>
+class DenseMapTest : public ::testing::Test {
+protected:
+ T Map;
+
+ static typename T::key_type *const dummy_key_ptr;
+ static typename T::mapped_type *const dummy_value_ptr;
+
+ typename T::key_type getKey(int i = 0) {
+ return getTestKey(i, dummy_key_ptr);
+ }
+ typename T::mapped_type getValue(int i = 0) {
+ return getTestValue(i, dummy_value_ptr);
+ }
+};
+
+template <typename T>
+typename T::key_type *const DenseMapTest<T>::dummy_key_ptr = 0;
+template <typename T>
+typename T::mapped_type *const DenseMapTest<T>::dummy_value_ptr = 0;
// Register these types for testing.
typedef ::testing::Types<DenseMap<uint32_t, uint32_t>,
- DenseMap<uint32_t *, uint32_t *> > DenseMapTestTypes;
+ DenseMap<uint32_t *, uint32_t *>,
+ DenseMap<CtorTester, CtorTester, CtorTesterMapInfo>,
+ SmallDenseMap<uint32_t, uint32_t>,
+ SmallDenseMap<uint32_t *, uint32_t *>,
+ SmallDenseMap<CtorTester, CtorTester, 4,
+ CtorTesterMapInfo>
+ > DenseMapTestTypes;
TYPED_TEST_CASE(DenseMapTest, DenseMapTestTypes);
// Empty map tests
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
TYPED_TEST(DenseMapTest, IterationTest) {
bool visited[100];
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<unsigned, unsigned, 32, ContiguousDenseMapInfo> 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());
+}
+
}
projects / oota-llvm.git / blobdiff