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 "llvm/ADT/STLExtras.h"
17#include "gtest/gtest.h"
18
19using namespace llvm;
20
21TEST(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 (auto Tuple : zip(t&: Map, u&: 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.
59struct PtrLikeInt { int value; };
60
61namespace llvm {
62
63template<> 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
85TEST(ReverseIterationTest, DenseMapTest2) {
86 static_assert(detail::IsPointerLike<PtrLikeInt *>::value,
87 "PtrLikeInt * is pointer-like");
88
89 PtrLikeInt a = {.value: 4}, b = {.value: 8}, c = {.value: 12}, d = {.value: 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(first: &Keys[0], last: &Keys[4]);
101
102 // Check that the DenseMap is iterated in the expected order.
103 for (auto Tuple : zip(t&: Map, u&: 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

source code of llvm/unittests/Support/ReverseIterationTest.cpp