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::__anonb3d9dcee0111::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
184 class PoisonSoo {
185 int64_t data_;
186
187 public:
PoisonSoo(int64_t d)188 explicit PoisonSoo(int64_t d) : data_(d) { SanitizerPoisonObject(&data_); }
PoisonSoo(const PoisonSoo & that)189 PoisonSoo(const PoisonSoo& that) : PoisonSoo(*that) {}
~PoisonSoo()190 ~PoisonSoo() { SanitizerUnpoisonObject(&data_); }
191
operator *() const192 int64_t operator*() const {
193 SanitizerUnpoisonObject(&data_);
194 const int64_t ret = data_;
195 SanitizerPoisonObject(&data_);
196 return ret;
197 }
198 template <typename H>
AbslHashValue(H h,const PoisonSoo & pi)199 friend H AbslHashValue(H h, const PoisonSoo& pi) {
200 return H::combine(std::move(h), *pi);
201 }
operator ==(const PoisonSoo & rhs) const202 bool operator==(const PoisonSoo& rhs) const { return **this == *rhs; }
203 };
204
TEST(FlatHashSet,PoisonSooBasic)205 TEST(FlatHashSet, PoisonSooBasic) {
206 PoisonSoo a(0), b(1);
207 flat_hash_set<PoisonSoo> set;
208 set.insert(a);
209 EXPECT_THAT(set, UnorderedElementsAre(a));
210 set.insert(b);
211 EXPECT_THAT(set, UnorderedElementsAre(a, b));
212 set.erase(a);
213 EXPECT_THAT(set, UnorderedElementsAre(b));
214 set.rehash(0); // Shrink to SOO.
215 EXPECT_THAT(set, UnorderedElementsAre(b));
216 }
217
TEST(FlatHashSet,PoisonSooMoveConstructSooToSoo)218 TEST(FlatHashSet, PoisonSooMoveConstructSooToSoo) {
219 PoisonSoo a(0);
220 flat_hash_set<PoisonSoo> set;
221 set.insert(a);
222 flat_hash_set<PoisonSoo> set2(std::move(set));
223 EXPECT_THAT(set2, UnorderedElementsAre(a));
224 }
225
TEST(FlatHashSet,PoisonSooAllocMoveConstructSooToSoo)226 TEST(FlatHashSet, PoisonSooAllocMoveConstructSooToSoo) {
227 PoisonSoo a(0);
228 flat_hash_set<PoisonSoo> set;
229 set.insert(a);
230 flat_hash_set<PoisonSoo> set2(std::move(set), std::allocator<PoisonSoo>());
231 EXPECT_THAT(set2, UnorderedElementsAre(a));
232 }
233
TEST(FlatHashSet,PoisonSooMoveAssignFullSooToEmptySoo)234 TEST(FlatHashSet, PoisonSooMoveAssignFullSooToEmptySoo) {
235 PoisonSoo a(0);
236 flat_hash_set<PoisonSoo> set, set2;
237 set.insert(a);
238 set2 = std::move(set);
239 EXPECT_THAT(set2, UnorderedElementsAre(a));
240 }
241
TEST(FlatHashSet,PoisonSooMoveAssignFullSooToFullSoo)242 TEST(FlatHashSet, PoisonSooMoveAssignFullSooToFullSoo) {
243 PoisonSoo a(0), b(1);
244 flat_hash_set<PoisonSoo> set, set2;
245 set.insert(a);
246 set2.insert(b);
247 set2 = std::move(set);
248 EXPECT_THAT(set2, UnorderedElementsAre(a));
249 }
250
TEST(FlatHashSet,FlatHashSetPolicyDestroyReturnsTrue)251 TEST(FlatHashSet, FlatHashSetPolicyDestroyReturnsTrue) {
252 EXPECT_TRUE((decltype(FlatHashSetPolicy<int>::destroy<std::allocator<int>>(
253 nullptr, nullptr))()));
254 EXPECT_FALSE(
255 (decltype(FlatHashSetPolicy<int>::destroy<CountingAllocator<int>>(
256 nullptr, nullptr))()));
257 EXPECT_FALSE((decltype(FlatHashSetPolicy<std::unique_ptr<int>>::destroy<
258 std::allocator<int>>(nullptr, nullptr))()));
259 }
260
261 } // namespace
262 } // namespace container_internal
263 ABSL_NAMESPACE_END
264 } // namespace absl
265