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