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