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
13using namespace llvm;
14
15namespace {
16
17static_assert(
18 std::is_const_v<
19 std::remove_pointer_t<DenseSet<int>::const_iterator::pointer>>,
20 "Iterator pointer type should be const");
21static_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.
27TEST(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
35struct 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
51template <typename T> class DenseSetTest : public testing::Test {
52protected:
53 T Set = GetTestSet();
54
55private:
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.
66typedef ::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;
73TYPED_TEST_SUITE(DenseSetTest, DenseSetTestTypes, );
74
75TYPED_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
84TYPED_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
93TYPED_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
101TYPED_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
110TYPED_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
117TYPED_TEST(DenseSetTest, EmptyInitializerList) {
118 TypeParam set({});
119 EXPECT_EQ(0u, set.size());
120 EXPECT_EQ(0u, set.count(0));
121}
122
123TYPED_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
142TYPED_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
152struct 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};
177int CountCopyAndMove::Copy = 0;
178int CountCopyAndMove::Move = 0;
179} // anonymous namespace
180
181namespace llvm {
182// Specialization required to insert a CountCopyAndMove into a DenseSet.
183template <> 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
198namespace {
199// Make sure reserve actually gives us enough buckets to insert N items
200// without increasing allocation size.
201TEST(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}
222TEST(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

source code of llvm/unittests/ADT/DenseSetTest.cpp