blob: 05804e69c26026fbb416224b7a36a2c93f718bc5 [file] [log] [blame]
Mandeep Singh Grang872f6892017-08-24 23:02:48 +00001//===- llvm/unittest/Support/ReverseIterationTest.cpp ---------------------===//
2//
Chandler Carruth2946cd72019-01-19 08:50:56 +00003// 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
Mandeep Singh Grang872f6892017-08-24 23:02:48 +00006//
7//===---------------------------------------------------------------------===//
8//
9// Reverse Iteration unit tests.
10//
11//===---------------------------------------------------------------------===//
12
Mandeep Singh Grang872f6892017-08-24 23:02:48 +000013#include "llvm/Support/ReverseIteration.h"
Davide Italianof8874062017-09-05 21:27:23 +000014#include "llvm/ADT/DenseMap.h"
15#include "llvm/ADT/DenseMapInfo.h"
Mandeep Singh Grang872f6892017-08-24 23:02:48 +000016#include "gtest/gtest.h"
17
18using namespace llvm;
19
20TEST(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");
Mandeep Singh Grang12bd3292017-08-25 01:11:28 +000025 static_assert(!detail::IsPointerLike<int>::value,
26 "int is not pointer-like");
27 static_assert(detail::IsPointerLike<void *>::value,
28 "void * is pointer-like");
Mandeep Singh Grang872f6892017-08-24 23:02:48 +000029 struct IncompleteType;
30 static_assert(detail::IsPointerLike<IncompleteType *>::value,
31 "incomplete * is pointer-like");
32
Mandeep Singh Grang872f6892017-08-24 23:02:48 +000033 // 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 (const 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}
Mandeep Singh Grang9837e992017-09-05 20:39:01 +000056
57// Define a pointer-like int.
58struct PtrLikeInt { int value; };
59
Davide Italianof8874062017-09-05 21:27:23 +000060namespace llvm {
61
Mandeep Singh Grang9837e992017-09-05 20:39:01 +000062template<> 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
Davide Italianof8874062017-09-05 21:27:23 +000082} // end namespace llvm
83
Mandeep Singh Grang9837e992017-09-05 20:39:01 +000084TEST(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 (const 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}