Mark MDNode::getOperand as readonly.

[oota-llvm.git] / unittests / ADT / DenseMapTest.cpp

diff --git a/unittests/ADT/DenseMapTest.cpp b/unittests/ADT/DenseMapTest.cpp
index d61f991bd55d13415c85172d656fa9367619a6e5..15eb6988f669058154407df6f4402b64b015340d 100644 (file)
--- a/unittests/ADT/DenseMapTest.cpp
+++ b/unittests/ADT/DenseMapTest.cpp
@@ -10,6 +10,7 @@
 #include "gtest/gtest.h"
 #include "llvm/ADT/DenseMap.h"
 #include <map>
+#include <set>
 
 using namespace llvm;
 
@@ -29,6 +30,47 @@ 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<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
@@ -57,8 +99,11 @@ 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 *>,
+                         DenseMap<CtorTester, CtorTester, CtorTesterMapInfo>,
                          SmallDenseMap<uint32_t, uint32_t>,
-                         SmallDenseMap<uint32_t *, uint32_t *>
+                         SmallDenseMap<uint32_t *, uint32_t *>,
+                         SmallDenseMap<CtorTester, CtorTester, 4,
+                                       CtorTesterMapInfo>
                          > DenseMapTestTypes;
 TYPED_TEST_CASE(DenseMapTest, DenseMapTestTypes);
 
@@ -173,6 +218,42 @@ TYPED_TEST(DenseMapTest, AssignmentTest) {
   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];
@@ -249,4 +330,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<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());
+}
+
 }