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 <utility>
20 #include <vector>
21
22 #include "gmock/gmock.h"
23 #include "gtest/gtest.h"
24 #include "absl/base/config.h"
25 #include "absl/container/internal/container_memory.h"
26 #include "absl/container/internal/hash_generator_testing.h"
27 #include "absl/container/internal/unordered_set_constructor_test.h"
28 #include "absl/container/internal/unordered_set_lookup_test.h"
29 #include "absl/container/internal/unordered_set_members_test.h"
30 #include "absl/container/internal/unordered_set_modifiers_test.h"
31 #include "absl/log/check.h"
32 #include "absl/memory/memory.h"
33 #include "absl/strings/string_view.h"
34
35 namespace absl {
36 ABSL_NAMESPACE_BEGIN
37 namespace container_internal {
38 namespace {
39
40 using ::absl::container_internal::hash_internal::Enum;
41 using ::absl::container_internal::hash_internal::EnumClass;
42 using ::testing::IsEmpty;
43 using ::testing::Pointee;
44 using ::testing::UnorderedElementsAre;
45 using ::testing::UnorderedElementsAreArray;
46
47 // Check that absl::flat_hash_set works in a global constructor.
48 struct BeforeMain {
BeforeMainabsl::container_internal::__anon06b49bb20111::BeforeMain49 BeforeMain() {
50 absl::flat_hash_set<int> x;
51 x.insert(1);
52 CHECK(!x.contains(0)) << "x should not contain 0";
53 CHECK(x.contains(1)) << "x should contain 1";
54 }
55 };
56 const BeforeMain before_main;
57
58 template <class T>
59 using Set =
60 absl::flat_hash_set<T, StatefulTestingHash, StatefulTestingEqual, Alloc<T>>;
61
62 using SetTypes =
63 ::testing::Types<Set<int>, Set<std::string>, Set<Enum>, Set<EnumClass>>;
64
65 INSTANTIATE_TYPED_TEST_SUITE_P(FlatHashSet, ConstructorTest, SetTypes);
66 INSTANTIATE_TYPED_TEST_SUITE_P(FlatHashSet, LookupTest, SetTypes);
67 INSTANTIATE_TYPED_TEST_SUITE_P(FlatHashSet, MembersTest, SetTypes);
68 INSTANTIATE_TYPED_TEST_SUITE_P(FlatHashSet, ModifiersTest, SetTypes);
69
TEST(FlatHashSet,EmplaceString)70 TEST(FlatHashSet, EmplaceString) {
71 std::vector<std::string> v = {"a", "b"};
72 absl::flat_hash_set<absl::string_view> hs(v.begin(), v.end());
73 EXPECT_THAT(hs, UnorderedElementsAreArray(v));
74 }
75
TEST(FlatHashSet,BitfieldArgument)76 TEST(FlatHashSet, BitfieldArgument) {
77 union {
78 int n : 1;
79 };
80 n = 0;
81 absl::flat_hash_set<int> s = {n};
82 s.insert(n);
83 s.insert(s.end(), n);
84 s.insert({n});
85 s.erase(n);
86 s.count(n);
87 s.prefetch(n);
88 s.find(n);
89 s.contains(n);
90 s.equal_range(n);
91 }
92
TEST(FlatHashSet,MergeExtractInsert)93 TEST(FlatHashSet, MergeExtractInsert) {
94 struct Hash {
95 size_t operator()(const std::unique_ptr<int>& p) const { return *p; }
96 };
97 struct Eq {
98 bool operator()(const std::unique_ptr<int>& a,
99 const std::unique_ptr<int>& b) const {
100 return *a == *b;
101 }
102 };
103 absl::flat_hash_set<std::unique_ptr<int>, Hash, Eq> set1, set2;
104 set1.insert(absl::make_unique<int>(7));
105 set1.insert(absl::make_unique<int>(17));
106
107 set2.insert(absl::make_unique<int>(7));
108 set2.insert(absl::make_unique<int>(19));
109
110 EXPECT_THAT(set1, UnorderedElementsAre(Pointee(7), Pointee(17)));
111 EXPECT_THAT(set2, UnorderedElementsAre(Pointee(7), Pointee(19)));
112
113 set1.merge(set2);
114
115 EXPECT_THAT(set1, UnorderedElementsAre(Pointee(7), Pointee(17), Pointee(19)));
116 EXPECT_THAT(set2, UnorderedElementsAre(Pointee(7)));
117
118 auto node = set1.extract(absl::make_unique<int>(7));
119 EXPECT_TRUE(node);
120 EXPECT_THAT(node.value(), Pointee(7));
121 EXPECT_THAT(set1, UnorderedElementsAre(Pointee(17), Pointee(19)));
122
123 auto insert_result = set2.insert(std::move(node));
124 EXPECT_FALSE(node);
125 EXPECT_FALSE(insert_result.inserted);
126 EXPECT_TRUE(insert_result.node);
127 EXPECT_THAT(insert_result.node.value(), Pointee(7));
128 EXPECT_EQ(**insert_result.position, 7);
129 EXPECT_NE(insert_result.position->get(), insert_result.node.value().get());
130 EXPECT_THAT(set2, UnorderedElementsAre(Pointee(7)));
131
132 node = set1.extract(absl::make_unique<int>(17));
133 EXPECT_TRUE(node);
134 EXPECT_THAT(node.value(), Pointee(17));
135 EXPECT_THAT(set1, UnorderedElementsAre(Pointee(19)));
136
137 node.value() = absl::make_unique<int>(23);
138
139 insert_result = set2.insert(std::move(node));
140 EXPECT_FALSE(node);
141 EXPECT_TRUE(insert_result.inserted);
142 EXPECT_FALSE(insert_result.node);
143 EXPECT_EQ(**insert_result.position, 23);
144 EXPECT_THAT(set2, UnorderedElementsAre(Pointee(7), Pointee(23)));
145 }
146
IsEven(int k)147 bool IsEven(int k) { return k % 2 == 0; }
148
TEST(FlatHashSet,EraseIf)149 TEST(FlatHashSet, EraseIf) {
150 // Erase all elements.
151 {
152 flat_hash_set<int> s = {1, 2, 3, 4, 5};
153 EXPECT_EQ(erase_if(s, [](int) { return true; }), 5);
154 EXPECT_THAT(s, IsEmpty());
155 }
156 // Erase no elements.
157 {
158 flat_hash_set<int> s = {1, 2, 3, 4, 5};
159 EXPECT_EQ(erase_if(s, [](int) { return false; }), 0);
160 EXPECT_THAT(s, UnorderedElementsAre(1, 2, 3, 4, 5));
161 }
162 // Erase specific elements.
163 {
164 flat_hash_set<int> s = {1, 2, 3, 4, 5};
165 EXPECT_EQ(erase_if(s, [](int k) { return k % 2 == 1; }), 3);
166 EXPECT_THAT(s, UnorderedElementsAre(2, 4));
167 }
168 // Predicate is function reference.
169 {
170 flat_hash_set<int> s = {1, 2, 3, 4, 5};
171 EXPECT_EQ(erase_if(s, IsEven), 2);
172 EXPECT_THAT(s, UnorderedElementsAre(1, 3, 5));
173 }
174 // Predicate is function pointer.
175 {
176 flat_hash_set<int> s = {1, 2, 3, 4, 5};
177 EXPECT_EQ(erase_if(s, &IsEven), 2);
178 EXPECT_THAT(s, UnorderedElementsAre(1, 3, 5));
179 }
180 }
181
182 class PoisonInline {
183 int64_t data_;
184
185 public:
PoisonInline(int64_t d)186 explicit PoisonInline(int64_t d) : data_(d) {
187 SanitizerPoisonObject(&data_);
188 }
PoisonInline(const PoisonInline & that)189 PoisonInline(const PoisonInline& that) : PoisonInline(*that) {}
~PoisonInline()190 ~PoisonInline() { 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 PoisonInline & pi)199 friend H AbslHashValue(H h, const PoisonInline& pi) {
200 return H::combine(std::move(h), *pi);
201 }
operator ==(const PoisonInline & rhs) const202 bool operator==(const PoisonInline& rhs) const { return **this == *rhs; }
203 };
204
205 // Tests that we don't touch the poison_ member of PoisonInline.
TEST(FlatHashSet,PoisonInline)206 TEST(FlatHashSet, PoisonInline) {
207 PoisonInline a(0), b(1);
208 { // basic usage
209 flat_hash_set<PoisonInline> set;
210 set.insert(a);
211 EXPECT_THAT(set, UnorderedElementsAre(a));
212 set.insert(b);
213 EXPECT_THAT(set, UnorderedElementsAre(a, b));
214 set.erase(a);
215 EXPECT_THAT(set, UnorderedElementsAre(b));
216 set.rehash(0); // shrink to inline
217 EXPECT_THAT(set, UnorderedElementsAre(b));
218 }
219 { // test move constructor from inline to inline
220 flat_hash_set<PoisonInline> set;
221 set.insert(a);
222 flat_hash_set<PoisonInline> set2(std::move(set));
223 EXPECT_THAT(set2, UnorderedElementsAre(a));
224 }
225 { // test move assignment from inline to inline
226 flat_hash_set<PoisonInline> set, set2;
227 set.insert(a);
228 set2 = std::move(set);
229 EXPECT_THAT(set2, UnorderedElementsAre(a));
230 }
231 { // test alloc move constructor from inline to inline
232 flat_hash_set<PoisonInline> set;
233 set.insert(a);
234 flat_hash_set<PoisonInline> set2(std::move(set),
235 std::allocator<PoisonInline>());
236 EXPECT_THAT(set2, UnorderedElementsAre(a));
237 }
238 }
239
240 } // namespace
241 } // namespace container_internal
242 ABSL_NAMESPACE_END
243 } // namespace absl
244