[unittests] Add reverse iteration unit test for pointer-like keys

[dblaikie]

unittests/Support/ReverseIterationTest.cpp

87–92

I'm not sure this is going to be more stable than the previous version, right? The pointers may be strictly ordered now, but the hashing container might order them in other ways that could mean different orders depending on higher bits in the pointer values...

What I had in mind/was previously suggesting was to use integer keys that are pointer like & so you can control all the bits. This would work for the DenseMap test, presumably, but maybe not the SmallPtrSet test (which might only accept real pointer keys, not pointer-like keys).

99

llvm::reverse(IterKeys);

[mgrang]

Added DenseMap test for pointer-like keys.

[mgrang]

unittests/Support/ReverseIterationTest.cpp

69

How about this implementation? PtrLikeInt is pointer-like but it hashes based on an integer value.
I don't think this would work for SmallPtrSet (as you had pointed out).

95

@dblaikie llvm::reverse(IterKeys) does not change the existing array, right?. I found using std::reverse cleaner than using another array to hold the reversed one. What do you say?

[mgrang]

NFC. Made the static_assert the first statement in the test.

[dblaikie]

unittests/Support/ReverseIterationTest.cpp

61–67

Rather than mangling pointers - have two fixed instances of PtrLikeInt that can be pointed to (a local static PtrLikeInt in getEmpty/TombstoneKey would probably suffice:

static PtrLikeInt *getEmptyKey() {
  static const PtrLikeInt EmptyKey;
  return &EmptyKey;
}

something like that? (drop the 'inline' keyword from (static and non-static) member functions defined inline in a class - they already have that linkage)

70

Maybe just make the value /be/ the hash, do you think? Not sure if that makes it any better or worse (it doesn't have to be a good hash function - simplicity might be preferable)

Maybe make PtrLikeInt's member 'unsigned' to match the hash value type.

[mgrang]

Addressed comments.

[mgrang]

unittests/Support/ReverseIterationTest.cpp

61–67

Making EmptyKey as a "const" would require an initializer as well as a change in the signature of the getEmptyKey function (which causes build conflicts due to mismatching definitions). So I have dropped the const.

[dblaikie]

Looks good - thanks!

unittests/Support/ReverseIterationTest.cpp

TEST(ReverseIterationTest, DenseMapTest1) {
   for (const auto &Tuple : zip(Map, IterKeys))
     ASSERT_EQ(std::get<0>(Tuple).first, std::get<1>(Tuple));
 
   // Check operator++ (post-increment).
   int i = 0;
   for (auto iter = Map.begin(), end = Map.end(); iter != end; iter++, ++i)
     ASSERT_EQ(iter->first, IterKeys[i]);
 }
+
+// Define a pointer-like int.
+struct PtrLikeInt { int value; };
+
+template<> struct DenseMapInfo<PtrLikeInt *> {
+  static inline PtrLikeInt *getEmptyKey() {
+    return reinterpret_cast<PtrLikeInt *>(0x7fffffff);
+  }
+
+  static inline PtrLikeInt *getTombstoneKey() {
+    return reinterpret_cast<PtrLikeInt *>(-0x7fffffff - 1);
+  }
+
+  static unsigned getHashValue(const PtrLikeInt *PtrVal) {
+    return (unsigned)(PtrVal->value * 37U);
+  }
+
+  static bool isEqual(const PtrLikeInt *LHS, const PtrLikeInt *RHS) {
+    return LHS == RHS;
+  }
+};
+
+TEST(ReverseIterationTest, DenseMapTest2) {
+  PtrLikeInt a = {4}, b = {8}, c = {12}, d = {16};
+
+  static_assert(detail::IsPointerLike<PtrLikeInt *>::value,
+                "PtrLikeInt * is pointer-like");
+
+  // Insert keys into the DenseMap.
+  PtrLikeInt *Keys[] = { &a, &b, &c, &d };
+  DenseMap<PtrLikeInt *, int> Map;
+  for (auto *Key : Keys)
+    Map[Key] = Key->value;
+
+  // Note: This is the observed order of keys in the DenseMap.
+  // If there is any change in the behavior of the DenseMap, this order
+  // would need to be adjusted accordingly.
+  PtrLikeInt *IterKeys[] = { &d, &a, &b, &c };
+  if (shouldReverseIterate<PtrLikeInt *>())
+    std::reverse(&IterKeys[0], &IterKeys[4]);
+
+  // Check that the DenseMap is iterated in the expected order.
+  for (const auto &Tuple : zip(Map, IterKeys))
+    ASSERT_EQ(std::get<0>(Tuple).second, std::get<1>(Tuple)->value);
+
+  // Check operator++ (post-increment).
+  int i = 0;
+  for (auto iter = Map.begin(), end = Map.end(); iter != end; iter++, ++i)
+    ASSERT_EQ(iter->second, IterKeys[i]->value);
+}