1 //===- llvm/unittest/Support/ReverseIterationTest.cpp ---------------------===// 2 // 3 // The LLVM Compiler Infrastructure 4 // 5 // This file is distributed under the University of Illinois Open Source 6 // License. See LICENSE.TXT for details. 7 // 8 //===---------------------------------------------------------------------===// 9 // 10 // Reverse Iteration unit tests. 11 // 12 //===---------------------------------------------------------------------===// 13 14 #include "llvm/Support/ReverseIteration.h" 15 #include "llvm/ADT/DenseMap.h" 16 #include "llvm/ADT/DenseMapInfo.h" 17 #include "gtest/gtest.h" 18 19 using namespace llvm; 20 21 TEST(ReverseIterationTest, DenseMapTest1) { 22 static_assert(detail::IsPointerLike<int *>::value, 23 "int * is pointer-like"); 24 static_assert(detail::IsPointerLike<uintptr_t>::value, 25 "uintptr_t is pointer-like"); 26 static_assert(!detail::IsPointerLike<int>::value, 27 "int is not pointer-like"); 28 static_assert(detail::IsPointerLike<void *>::value, 29 "void * is pointer-like"); 30 struct IncompleteType; 31 static_assert(detail::IsPointerLike<IncompleteType *>::value, 32 "incomplete * is pointer-like"); 33 34 // For a DenseMap with non-pointer-like keys, forward iteration equals 35 // reverse iteration. 36 DenseMap<int, int> Map; 37 int Keys[] = { 1, 2, 3, 4 }; 38 39 // Insert keys into the DenseMap. 40 for (auto Key: Keys) 41 Map[Key] = 0; 42 43 // Note: This is the observed order of keys in the DenseMap. 44 // If there is any change in the behavior of the DenseMap, this order 45 // would need to be adjusted accordingly. 46 int IterKeys[] = { 2, 4, 1, 3 }; 47 48 // Check that the DenseMap is iterated in the expected order. 49 for (const auto &Tuple : zip(Map, IterKeys)) 50 ASSERT_EQ(std::get<0>(Tuple).first, std::get<1>(Tuple)); 51 52 // Check operator++ (post-increment). 53 int i = 0; 54 for (auto iter = Map.begin(), end = Map.end(); iter != end; iter++, ++i) 55 ASSERT_EQ(iter->first, IterKeys[i]); 56 } 57 58 // Define a pointer-like int. 59 struct PtrLikeInt { int value; }; 60 61 namespace llvm { 62 63 template<> struct DenseMapInfo<PtrLikeInt *> { 64 static PtrLikeInt *getEmptyKey() { 65 static PtrLikeInt EmptyKey; 66 return &EmptyKey; 67 } 68 69 static PtrLikeInt *getTombstoneKey() { 70 static PtrLikeInt TombstoneKey; 71 return &TombstoneKey; 72 } 73 74 static int getHashValue(const PtrLikeInt *P) { 75 return P->value; 76 } 77 78 static bool isEqual(const PtrLikeInt *LHS, const PtrLikeInt *RHS) { 79 return LHS == RHS; 80 } 81 }; 82 83 } // end namespace llvm 84 85 TEST(ReverseIterationTest, DenseMapTest2) { 86 static_assert(detail::IsPointerLike<PtrLikeInt *>::value, 87 "PtrLikeInt * is pointer-like"); 88 89 PtrLikeInt a = {4}, b = {8}, c = {12}, d = {16}; 90 PtrLikeInt *Keys[] = { &a, &b, &c, &d }; 91 92 // Insert keys into the DenseMap. 93 DenseMap<PtrLikeInt *, int> Map; 94 for (auto *Key : Keys) 95 Map[Key] = Key->value; 96 97 // Note: If there is any change in the behavior of the DenseMap, 98 // the observed order of keys would need to be adjusted accordingly. 99 if (shouldReverseIterate<PtrLikeInt *>()) 100 std::reverse(&Keys[0], &Keys[4]); 101 102 // Check that the DenseMap is iterated in the expected order. 103 for (const auto &Tuple : zip(Map, Keys)) 104 ASSERT_EQ(std::get<0>(Tuple).second, std::get<1>(Tuple)->value); 105 106 // Check operator++ (post-increment). 107 int i = 0; 108 for (auto iter = Map.begin(), end = Map.end(); iter != end; iter++, ++i) 109 ASSERT_EQ(iter->second, Keys[i]->value); 110 } 111
