1 | //===- llvm/unittest/ADT/DenseSetTest.cpp - DenseSet unit tests --*- C++ -*-===// |
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 | #include "llvm/ADT/DenseSet.h" |
10 | #include "gtest/gtest.h" |
11 | #include <type_traits> |
12 | |
13 | using namespace llvm; |
14 | |
15 | namespace { |
16 | |
17 | static_assert( |
18 | std::is_const_v< |
19 | std::remove_pointer_t<DenseSet<int>::const_iterator::pointer>>, |
20 | "Iterator pointer type should be const" ); |
21 | static_assert( |
22 | std::is_const_v< |
23 | std::remove_reference_t<DenseSet<int>::const_iterator::reference>>, |
24 | "Iterator reference type should be const" ); |
25 | |
26 | // Test hashing with a set of only two entries. |
27 | TEST(DenseSetTest, DoubleEntrySetTest) { |
28 | llvm::DenseSet<unsigned> set(2); |
29 | set.insert(V: 0); |
30 | set.insert(V: 1); |
31 | // Original failure was an infinite loop in this call: |
32 | EXPECT_EQ(0u, set.count(2)); |
33 | } |
34 | |
35 | struct TestDenseSetInfo { |
36 | static inline unsigned getEmptyKey() { return ~0; } |
37 | static inline unsigned getTombstoneKey() { return ~0U - 1; } |
38 | static unsigned getHashValue(const unsigned& Val) { return Val * 37U; } |
39 | static unsigned getHashValue(const char* Val) { |
40 | return (unsigned)(Val[0] - 'a') * 37U; |
41 | } |
42 | static bool isEqual(const unsigned& LHS, const unsigned& RHS) { |
43 | return LHS == RHS; |
44 | } |
45 | static bool isEqual(const char* LHS, const unsigned& RHS) { |
46 | return (unsigned)(LHS[0] - 'a') == RHS; |
47 | } |
48 | }; |
49 | |
50 | // Test fixture |
51 | template <typename T> class DenseSetTest : public testing::Test { |
52 | protected: |
53 | T Set = GetTestSet(); |
54 | |
55 | private: |
56 | static T GetTestSet() { |
57 | std::remove_const_t<T> Set; |
58 | Set.insert(0); |
59 | Set.insert(1); |
60 | Set.insert(2); |
61 | return Set; |
62 | } |
63 | }; |
64 | |
65 | // Register these types for testing. |
66 | typedef ::testing::Types<DenseSet<unsigned, TestDenseSetInfo>, |
67 | const DenseSet<unsigned, TestDenseSetInfo>, |
68 | SmallDenseSet<unsigned, 1, TestDenseSetInfo>, |
69 | SmallDenseSet<unsigned, 4, TestDenseSetInfo>, |
70 | const SmallDenseSet<unsigned, 4, TestDenseSetInfo>, |
71 | SmallDenseSet<unsigned, 64, TestDenseSetInfo>> |
72 | DenseSetTestTypes; |
73 | TYPED_TEST_SUITE(DenseSetTest, DenseSetTestTypes, ); |
74 | |
75 | TYPED_TEST(DenseSetTest, Constructor) { |
76 | constexpr unsigned a[] = {1, 2, 4}; |
77 | TypeParam set(std::begin(arr: a), std::end(arr: a)); |
78 | EXPECT_EQ(3u, set.size()); |
79 | EXPECT_EQ(1u, set.count(1)); |
80 | EXPECT_EQ(1u, set.count(2)); |
81 | EXPECT_EQ(1u, set.count(4)); |
82 | } |
83 | |
84 | TYPED_TEST(DenseSetTest, InitializerList) { |
85 | TypeParam set({1, 2, 1, 4}); |
86 | EXPECT_EQ(3u, set.size()); |
87 | EXPECT_EQ(1u, set.count(1)); |
88 | EXPECT_EQ(1u, set.count(2)); |
89 | EXPECT_EQ(1u, set.count(4)); |
90 | EXPECT_EQ(0u, set.count(3)); |
91 | } |
92 | |
93 | TYPED_TEST(DenseSetTest, InitializerListWithNonPowerOfTwoLength) { |
94 | TypeParam set({1, 2, 3}); |
95 | EXPECT_EQ(3u, set.size()); |
96 | EXPECT_EQ(1u, set.count(1)); |
97 | EXPECT_EQ(1u, set.count(2)); |
98 | EXPECT_EQ(1u, set.count(3)); |
99 | } |
100 | |
101 | TYPED_TEST(DenseSetTest, ConstIteratorComparison) { |
102 | TypeParam set({1}); |
103 | const TypeParam &cset = set; |
104 | EXPECT_EQ(set.begin(), cset.begin()); |
105 | EXPECT_EQ(set.end(), cset.end()); |
106 | EXPECT_NE(set.end(), cset.begin()); |
107 | EXPECT_NE(set.begin(), cset.end()); |
108 | } |
109 | |
110 | TYPED_TEST(DenseSetTest, DefaultConstruction) { |
111 | typename TypeParam::iterator I, J; |
112 | typename TypeParam::const_iterator CI, CJ; |
113 | EXPECT_EQ(I, J); |
114 | EXPECT_EQ(CI, CJ); |
115 | } |
116 | |
117 | TYPED_TEST(DenseSetTest, EmptyInitializerList) { |
118 | TypeParam set({}); |
119 | EXPECT_EQ(0u, set.size()); |
120 | EXPECT_EQ(0u, set.count(0)); |
121 | } |
122 | |
123 | TYPED_TEST(DenseSetTest, FindAsTest) { |
124 | auto &set = this->Set; |
125 | // Size tests |
126 | EXPECT_EQ(3u, set.size()); |
127 | |
128 | // Normal lookup tests |
129 | EXPECT_EQ(1u, set.count(1)); |
130 | EXPECT_EQ(0u, *set.find(0)); |
131 | EXPECT_EQ(1u, *set.find(1)); |
132 | EXPECT_EQ(2u, *set.find(2)); |
133 | EXPECT_TRUE(set.find(3) == set.end()); |
134 | |
135 | // find_as() tests |
136 | EXPECT_EQ(0u, *set.find_as("a" )); |
137 | EXPECT_EQ(1u, *set.find_as("b" )); |
138 | EXPECT_EQ(2u, *set.find_as("c" )); |
139 | EXPECT_TRUE(set.find_as("d" ) == set.end()); |
140 | } |
141 | |
142 | TYPED_TEST(DenseSetTest, EqualityComparisonTest) { |
143 | TypeParam set1({1, 2, 3, 4}); |
144 | TypeParam set2({4, 3, 2, 1}); |
145 | TypeParam set3({2, 3, 4, 5}); |
146 | |
147 | EXPECT_EQ(set1, set2); |
148 | EXPECT_NE(set1, set3); |
149 | } |
150 | |
151 | // Simple class that counts how many moves and copy happens when growing a map |
152 | struct CountCopyAndMove { |
153 | static int Move; |
154 | static int Copy; |
155 | int Value; |
156 | CountCopyAndMove(int Value) : Value(Value) {} |
157 | |
158 | CountCopyAndMove(const CountCopyAndMove &RHS) { |
159 | Value = RHS.Value; |
160 | Copy++; |
161 | } |
162 | CountCopyAndMove &operator=(const CountCopyAndMove &RHS) { |
163 | Value = RHS.Value; |
164 | Copy++; |
165 | return *this; |
166 | } |
167 | CountCopyAndMove(CountCopyAndMove &&RHS) { |
168 | Value = RHS.Value; |
169 | Move++; |
170 | } |
171 | CountCopyAndMove &operator=(const CountCopyAndMove &&RHS) { |
172 | Value = RHS.Value; |
173 | Move++; |
174 | return *this; |
175 | } |
176 | }; |
177 | int CountCopyAndMove::Copy = 0; |
178 | int CountCopyAndMove::Move = 0; |
179 | } // anonymous namespace |
180 | |
181 | namespace llvm { |
182 | // Specialization required to insert a CountCopyAndMove into a DenseSet. |
183 | template <> struct DenseMapInfo<CountCopyAndMove> { |
184 | static inline CountCopyAndMove getEmptyKey() { return CountCopyAndMove(-1); }; |
185 | static inline CountCopyAndMove getTombstoneKey() { |
186 | return CountCopyAndMove(-2); |
187 | }; |
188 | static unsigned getHashValue(const CountCopyAndMove &Val) { |
189 | return Val.Value; |
190 | } |
191 | static bool isEqual(const CountCopyAndMove &LHS, |
192 | const CountCopyAndMove &RHS) { |
193 | return LHS.Value == RHS.Value; |
194 | } |
195 | }; |
196 | } |
197 | |
198 | namespace { |
199 | // Make sure reserve actually gives us enough buckets to insert N items |
200 | // without increasing allocation size. |
201 | TEST(DenseSetCustomTest, ReserveTest) { |
202 | // Test a few different size, 48 is *not* a random choice: we need a value |
203 | // that is 2/3 of a power of two to stress the grow() condition, and the power |
204 | // of two has to be at least 64 because of minimum size allocation in the |
205 | // DenseMa. 66 is a value just above the 64 default init. |
206 | for (auto Size : {1, 2, 48, 66}) { |
207 | DenseSet<CountCopyAndMove> Set; |
208 | Set.reserve(Size); |
209 | unsigned MemorySize = Set.getMemorySize(); |
210 | CountCopyAndMove::Copy = 0; |
211 | CountCopyAndMove::Move = 0; |
212 | for (int i = 0; i < Size; ++i) |
213 | Set.insert(V: CountCopyAndMove(i)); |
214 | // Check that we didn't grow |
215 | EXPECT_EQ(MemorySize, Set.getMemorySize()); |
216 | // Check that move was called the expected number of times |
217 | EXPECT_EQ(Size, CountCopyAndMove::Move); |
218 | // Check that no copy occurred |
219 | EXPECT_EQ(0, CountCopyAndMove::Copy); |
220 | } |
221 | } |
222 | TEST(DenseSetCustomTest, ConstTest) { |
223 | // Test that const pointers work okay for count and find, even when the |
224 | // underlying map is a non-const pointer. |
225 | DenseSet<int *> Map; |
226 | int A; |
227 | int *B = &A; |
228 | const int *C = &A; |
229 | Map.insert(V: B); |
230 | EXPECT_EQ(Map.count(B), 1u); |
231 | EXPECT_EQ(Map.count(C), 1u); |
232 | EXPECT_TRUE(Map.contains(B)); |
233 | EXPECT_TRUE(Map.contains(C)); |
234 | } |
235 | } |
236 | |