1 // Copyright 2018 The Abseil Authors.
2 //
3 // Licensed under the Apache License, Version 2.0 (the "License");
4 // you may not use this file except in compliance with the License.
5 // You may obtain a copy of the License at
6 //
7 // https://www.apache.org/licenses/LICENSE-2.0
8 //
9 // Unless required by applicable law or agreed to in writing, software
10 // distributed under the License is distributed on an "AS IS" BASIS,
11 // WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
12 // See the License for the specific language governing permissions and
13 // limitations under the License.
14
15 #include "absl/container/flat_hash_set.h"
16
17 #include <cstdint>
18 #include <memory>
19 #include <type_traits>
20 #include <utility>
21 #include <vector>
22
23 #include "gmock/gmock.h"
24 #include "gtest/gtest.h"
25 #include "absl/base/config.h"
26 #include "absl/container/internal/container_memory.h"
27 #include "absl/container/internal/hash_generator_testing.h"
28 #include "absl/container/internal/test_allocator.h"
29 #include "absl/container/internal/unordered_set_constructor_test.h"
30 #include "absl/container/internal/unordered_set_lookup_test.h"
31 #include "absl/container/internal/unordered_set_members_test.h"
32 #include "absl/container/internal/unordered_set_modifiers_test.h"
33 #include "absl/log/check.h"
34 #include "absl/memory/memory.h"
35 #include "absl/strings/string_view.h"
36
37 namespace absl {
38 ABSL_NAMESPACE_BEGIN
39 namespace container_internal {
40 namespace {
41
42 using ::absl::container_internal::hash_internal::Enum;
43 using ::absl::container_internal::hash_internal::EnumClass;
44 using ::testing::IsEmpty;
45 using ::testing::Pointee;
46 using ::testing::UnorderedElementsAre;
47 using ::testing::UnorderedElementsAreArray;
48
49 // Check that absl::flat_hash_set works in a global constructor.
50 struct BeforeMain {
BeforeMainabsl::container_internal::__anone43652810111::BeforeMain51 BeforeMain() {
52 absl::flat_hash_set<int> x;
53 x.insert(1);
54 CHECK(!x.contains(0)) << "x should not contain 0";
55 CHECK(x.contains(1)) << "x should contain 1";
56 }
57 };
58 const BeforeMain before_main;
59
60 template <class T>
61 using Set =
62 absl::flat_hash_set<T, StatefulTestingHash, StatefulTestingEqual, Alloc<T>>;
63
64 using SetTypes =
65 ::testing::Types<Set<int>, Set<std::string>, Set<Enum>, Set<EnumClass>>;
66
67 INSTANTIATE_TYPED_TEST_SUITE_P(FlatHashSet, ConstructorTest, SetTypes);
68 INSTANTIATE_TYPED_TEST_SUITE_P(FlatHashSet, LookupTest, SetTypes);
69 INSTANTIATE_TYPED_TEST_SUITE_P(FlatHashSet, MembersTest, SetTypes);
70 INSTANTIATE_TYPED_TEST_SUITE_P(FlatHashSet, ModifiersTest, SetTypes);
71
TEST(FlatHashSet,EmplaceString)72 TEST(FlatHashSet, EmplaceString) {
73 std::vector<std::string> v = {"a", "b"};
74 absl::flat_hash_set<absl::string_view> hs(v.begin(), v.end());
75 EXPECT_THAT(hs, UnorderedElementsAreArray(v));
76 }
77
TEST(FlatHashSet,BitfieldArgument)78 TEST(FlatHashSet, BitfieldArgument) {
79 union {
80 int n : 1;
81 };
82 n = 0;
83 absl::flat_hash_set<int> s = {n};
84 s.insert(n);
85 s.insert(s.end(), n);
86 s.insert({n});
87 s.erase(n);
88 s.count(n);
89 s.prefetch(n);
90 s.find(n);
91 s.contains(n);
92 s.equal_range(n);
93 }
94
TEST(FlatHashSet,MergeExtractInsert)95 TEST(FlatHashSet, MergeExtractInsert) {
96 struct Hash {
97 size_t operator()(const std::unique_ptr<int>& p) const { return *p; }
98 };
99 struct Eq {
100 bool operator()(const std::unique_ptr<int>& a,
101 const std::unique_ptr<int>& b) const {
102 return *a == *b;
103 }
104 };
105 absl::flat_hash_set<std::unique_ptr<int>, Hash, Eq> set1, set2;
106 set1.insert(absl::make_unique<int>(7));
107 set1.insert(absl::make_unique<int>(17));
108
109 set2.insert(absl::make_unique<int>(7));
110 set2.insert(absl::make_unique<int>(19));
111
112 EXPECT_THAT(set1, UnorderedElementsAre(Pointee(7), Pointee(17)));
113 EXPECT_THAT(set2, UnorderedElementsAre(Pointee(7), Pointee(19)));
114
115 set1.merge(set2);
116
117 EXPECT_THAT(set1, UnorderedElementsAre(Pointee(7), Pointee(17), Pointee(19)));
118 EXPECT_THAT(set2, UnorderedElementsAre(Pointee(7)));
119
120 auto node = set1.extract(absl::make_unique<int>(7));
121 EXPECT_TRUE(node);
122 EXPECT_THAT(node.value(), Pointee(7));
123 EXPECT_THAT(set1, UnorderedElementsAre(Pointee(17), Pointee(19)));
124
125 auto insert_result = set2.insert(std::move(node));
126 EXPECT_FALSE(node);
127 EXPECT_FALSE(insert_result.inserted);
128 EXPECT_TRUE(insert_result.node);
129 EXPECT_THAT(insert_result.node.value(), Pointee(7));
130 EXPECT_EQ(**insert_result.position, 7);
131 EXPECT_NE(insert_result.position->get(), insert_result.node.value().get());
132 EXPECT_THAT(set2, UnorderedElementsAre(Pointee(7)));
133
134 node = set1.extract(absl::make_unique<int>(17));
135 EXPECT_TRUE(node);
136 EXPECT_THAT(node.value(), Pointee(17));
137 EXPECT_THAT(set1, UnorderedElementsAre(Pointee(19)));
138
139 node.value() = absl::make_unique<int>(23);
140
141 insert_result = set2.insert(std::move(node));
142 EXPECT_FALSE(node);
143 EXPECT_TRUE(insert_result.inserted);
144 EXPECT_FALSE(insert_result.node);
145 EXPECT_EQ(**insert_result.position, 23);
146 EXPECT_THAT(set2, UnorderedElementsAre(Pointee(7), Pointee(23)));
147 }
148
IsEven(int k)149 bool IsEven(int k) { return k % 2 == 0; }
150
TEST(FlatHashSet,EraseIf)151 TEST(FlatHashSet, EraseIf) {
152 // Erase all elements.
153 {
154 flat_hash_set<int> s = {1, 2, 3, 4, 5};
155 EXPECT_EQ(erase_if(s, [](int) { return true; }), 5);
156 EXPECT_THAT(s, IsEmpty());
157 }
158 // Erase no elements.
159 {
160 flat_hash_set<int> s = {1, 2, 3, 4, 5};
161 EXPECT_EQ(erase_if(s, [](int) { return false; }), 0);
162 EXPECT_THAT(s, UnorderedElementsAre(1, 2, 3, 4, 5));
163 }
164 // Erase specific elements.
165 {
166 flat_hash_set<int> s = {1, 2, 3, 4, 5};
167 EXPECT_EQ(erase_if(s, [](int k) { return k % 2 == 1; }), 3);
168 EXPECT_THAT(s, UnorderedElementsAre(2, 4));
169 }
170 // Predicate is function reference.
171 {
172 flat_hash_set<int> s = {1, 2, 3, 4, 5};
173 EXPECT_EQ(erase_if(s, IsEven), 2);
174 EXPECT_THAT(s, UnorderedElementsAre(1, 3, 5));
175 }
176 // Predicate is function pointer.
177 {
178 flat_hash_set<int> s = {1, 2, 3, 4, 5};
179 EXPECT_EQ(erase_if(s, &IsEven), 2);
180 EXPECT_THAT(s, UnorderedElementsAre(1, 3, 5));
181 }
182 }
183
TEST(FlatHashSet,CForEach)184 TEST(FlatHashSet, CForEach) {
185 using ValueType = std::pair<int, int>;
186 flat_hash_set<ValueType> s;
187 std::vector<ValueType> expected;
188 for (int i = 0; i < 100; ++i) {
189 {
190 SCOPED_TRACE("mutable object iteration");
191 std::vector<ValueType> v;
192 absl::container_internal::c_for_each_fast(
193 s, [&v](const ValueType& p) { v.push_back(p); });
194 ASSERT_THAT(v, UnorderedElementsAreArray(expected));
195 }
196 {
197 SCOPED_TRACE("const object iteration");
198 std::vector<ValueType> v;
199 const flat_hash_set<ValueType>& cs = s;
200 absl::container_internal::c_for_each_fast(
201 cs, [&v](const ValueType& p) { v.push_back(p); });
202 ASSERT_THAT(v, UnorderedElementsAreArray(expected));
203 }
204 {
205 SCOPED_TRACE("temporary object iteration");
206 std::vector<ValueType> v;
207 absl::container_internal::c_for_each_fast(
208 flat_hash_set<ValueType>(s),
209 [&v](const ValueType& p) { v.push_back(p); });
210 ASSERT_THAT(v, UnorderedElementsAreArray(expected));
211 }
212 s.emplace(i, i);
213 expected.emplace_back(i, i);
214 }
215 }
216
217 class PoisonSoo {
218 int64_t data_;
219
220 public:
PoisonSoo(int64_t d)221 explicit PoisonSoo(int64_t d) : data_(d) { SanitizerPoisonObject(&data_); }
PoisonSoo(const PoisonSoo & that)222 PoisonSoo(const PoisonSoo& that) : PoisonSoo(*that) {}
~PoisonSoo()223 ~PoisonSoo() { SanitizerUnpoisonObject(&data_); }
224
operator *() const225 int64_t operator*() const {
226 SanitizerUnpoisonObject(&data_);
227 const int64_t ret = data_;
228 SanitizerPoisonObject(&data_);
229 return ret;
230 }
231 template <typename H>
AbslHashValue(H h,const PoisonSoo & pi)232 friend H AbslHashValue(H h, const PoisonSoo& pi) {
233 return H::combine(std::move(h), *pi);
234 }
operator ==(const PoisonSoo & rhs) const235 bool operator==(const PoisonSoo& rhs) const { return **this == *rhs; }
236 };
237
TEST(FlatHashSet,PoisonSooBasic)238 TEST(FlatHashSet, PoisonSooBasic) {
239 PoisonSoo a(0), b(1);
240 flat_hash_set<PoisonSoo> set;
241 set.insert(a);
242 EXPECT_THAT(set, UnorderedElementsAre(a));
243 set.insert(b);
244 EXPECT_THAT(set, UnorderedElementsAre(a, b));
245 set.erase(a);
246 EXPECT_THAT(set, UnorderedElementsAre(b));
247 set.rehash(0); // Shrink to SOO.
248 EXPECT_THAT(set, UnorderedElementsAre(b));
249 }
250
TEST(FlatHashSet,PoisonSooMoveConstructSooToSoo)251 TEST(FlatHashSet, PoisonSooMoveConstructSooToSoo) {
252 PoisonSoo a(0);
253 flat_hash_set<PoisonSoo> set;
254 set.insert(a);
255 flat_hash_set<PoisonSoo> set2(std::move(set));
256 EXPECT_THAT(set2, UnorderedElementsAre(a));
257 }
258
TEST(FlatHashSet,PoisonSooAllocMoveConstructSooToSoo)259 TEST(FlatHashSet, PoisonSooAllocMoveConstructSooToSoo) {
260 PoisonSoo a(0);
261 flat_hash_set<PoisonSoo> set;
262 set.insert(a);
263 flat_hash_set<PoisonSoo> set2(std::move(set), std::allocator<PoisonSoo>());
264 EXPECT_THAT(set2, UnorderedElementsAre(a));
265 }
266
TEST(FlatHashSet,PoisonSooMoveAssignFullSooToEmptySoo)267 TEST(FlatHashSet, PoisonSooMoveAssignFullSooToEmptySoo) {
268 PoisonSoo a(0);
269 flat_hash_set<PoisonSoo> set, set2;
270 set.insert(a);
271 set2 = std::move(set);
272 EXPECT_THAT(set2, UnorderedElementsAre(a));
273 }
274
TEST(FlatHashSet,PoisonSooMoveAssignFullSooToFullSoo)275 TEST(FlatHashSet, PoisonSooMoveAssignFullSooToFullSoo) {
276 PoisonSoo a(0), b(1);
277 flat_hash_set<PoisonSoo> set, set2;
278 set.insert(a);
279 set2.insert(b);
280 set2 = std::move(set);
281 EXPECT_THAT(set2, UnorderedElementsAre(a));
282 }
283
TEST(FlatHashSet,FlatHashSetPolicyDestroyReturnsTrue)284 TEST(FlatHashSet, FlatHashSetPolicyDestroyReturnsTrue) {
285 EXPECT_TRUE((decltype(FlatHashSetPolicy<int>::destroy<std::allocator<int>>(
286 nullptr, nullptr))()));
287 EXPECT_FALSE(
288 (decltype(FlatHashSetPolicy<int>::destroy<CountingAllocator<int>>(
289 nullptr, nullptr))()));
290 EXPECT_FALSE((decltype(FlatHashSetPolicy<std::unique_ptr<int>>::destroy<
291 std::allocator<int>>(nullptr, nullptr))()));
292 }
293
294 } // namespace
295 } // namespace container_internal
296 ABSL_NAMESPACE_END
297 } // namespace absl
298