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 | |
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 (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. |
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 = {.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 | |