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
TEST(ReverseIterationTest,DenseMapTest1)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 *> {
getEmptyKeyllvm::DenseMapInfo64 static PtrLikeInt *getEmptyKey() {
65 static PtrLikeInt EmptyKey;
66 return &EmptyKey;
67 }
68
getTombstoneKeyllvm::DenseMapInfo69 static PtrLikeInt *getTombstoneKey() {
70 static PtrLikeInt TombstoneKey;
71 return &TombstoneKey;
72 }
73
getHashValuellvm::DenseMapInfo74 static int getHashValue(const PtrLikeInt *P) {
75 return P->value;
76 }
77
isEqualllvm::DenseMapInfo78 static bool isEqual(const PtrLikeInt *LHS, const PtrLikeInt *RHS) {
79 return LHS == RHS;
80 }
81 };
82
83 } // end namespace llvm
84
TEST(ReverseIterationTest,DenseMapTest2)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