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 #ifndef ABSL_CONTAINER_INTERNAL_UNORDERED_SET_CONSTRUCTOR_TEST_H_
16 #define ABSL_CONTAINER_INTERNAL_UNORDERED_SET_CONSTRUCTOR_TEST_H_
17
18 #include <algorithm>
19 #include <unordered_set>
20 #include <vector>
21
22 #include "gmock/gmock.h"
23 #include "gtest/gtest.h"
24 #include "absl/container/internal/hash_generator_testing.h"
25 #include "absl/container/internal/hash_policy_testing.h"
26 #include "absl/meta/type_traits.h"
27
28 namespace absl {
29 ABSL_NAMESPACE_BEGIN
30 namespace container_internal {
31
32 template <class UnordMap>
33 class ConstructorTest : public ::testing::Test {};
34
35 TYPED_TEST_SUITE_P(ConstructorTest);
36
TYPED_TEST_P(ConstructorTest,NoArgs)37 TYPED_TEST_P(ConstructorTest, NoArgs) {
38 TypeParam m;
39 EXPECT_TRUE(m.empty());
40 EXPECT_THAT(keys(m), ::testing::UnorderedElementsAre());
41 }
42
TYPED_TEST_P(ConstructorTest,BucketCount)43 TYPED_TEST_P(ConstructorTest, BucketCount) {
44 TypeParam m(123);
45 EXPECT_TRUE(m.empty());
46 EXPECT_THAT(keys(m), ::testing::UnorderedElementsAre());
47 EXPECT_GE(m.bucket_count(), 123);
48 }
49
TYPED_TEST_P(ConstructorTest,BucketCountHash)50 TYPED_TEST_P(ConstructorTest, BucketCountHash) {
51 using H = typename TypeParam::hasher;
52 H hasher;
53 TypeParam m(123, hasher);
54 EXPECT_EQ(m.hash_function(), hasher);
55 EXPECT_TRUE(m.empty());
56 EXPECT_THAT(keys(m), ::testing::UnorderedElementsAre());
57 EXPECT_GE(m.bucket_count(), 123);
58 }
59
TYPED_TEST_P(ConstructorTest,BucketCountHashEqual)60 TYPED_TEST_P(ConstructorTest, BucketCountHashEqual) {
61 using H = typename TypeParam::hasher;
62 using E = typename TypeParam::key_equal;
63 H hasher;
64 E equal;
65 TypeParam m(123, hasher, equal);
66 EXPECT_EQ(m.hash_function(), hasher);
67 EXPECT_EQ(m.key_eq(), equal);
68 EXPECT_TRUE(m.empty());
69 EXPECT_THAT(keys(m), ::testing::UnorderedElementsAre());
70 EXPECT_GE(m.bucket_count(), 123);
71 }
72
TYPED_TEST_P(ConstructorTest,BucketCountHashEqualAlloc)73 TYPED_TEST_P(ConstructorTest, BucketCountHashEqualAlloc) {
74 using H = typename TypeParam::hasher;
75 using E = typename TypeParam::key_equal;
76 using A = typename TypeParam::allocator_type;
77 H hasher;
78 E equal;
79 A alloc(0);
80 TypeParam m(123, hasher, equal, alloc);
81 EXPECT_EQ(m.hash_function(), hasher);
82 EXPECT_EQ(m.key_eq(), equal);
83 EXPECT_EQ(m.get_allocator(), alloc);
84 EXPECT_TRUE(m.empty());
85 EXPECT_THAT(keys(m), ::testing::UnorderedElementsAre());
86 EXPECT_GE(m.bucket_count(), 123);
87
88 const auto& cm = m;
89 EXPECT_EQ(cm.hash_function(), hasher);
90 EXPECT_EQ(cm.key_eq(), equal);
91 EXPECT_EQ(cm.get_allocator(), alloc);
92 EXPECT_TRUE(cm.empty());
93 EXPECT_THAT(keys(cm), ::testing::UnorderedElementsAre());
94 EXPECT_GE(cm.bucket_count(), 123);
95 }
96
97 template <typename T>
98 struct is_std_unordered_set : std::false_type {};
99
100 template <typename... T>
101 struct is_std_unordered_set<std::unordered_set<T...>> : std::true_type {};
102
103 #if defined(UNORDERED_SET_CXX14) || defined(UNORDERED_SET_CXX17)
104 using has_cxx14_std_apis = std::true_type;
105 #else
106 using has_cxx14_std_apis = std::false_type;
107 #endif
108
109 template <typename T>
110 using expect_cxx14_apis =
111 absl::disjunction<absl::negation<is_std_unordered_set<T>>,
112 has_cxx14_std_apis>;
113
114 template <typename TypeParam>
115 void BucketCountAllocTest(std::false_type) {}
116
117 template <typename TypeParam>
118 void BucketCountAllocTest(std::true_type) {
119 using A = typename TypeParam::allocator_type;
120 A alloc(0);
121 TypeParam m(123, alloc);
122 EXPECT_EQ(m.get_allocator(), alloc);
123 EXPECT_TRUE(m.empty());
124 EXPECT_THAT(keys(m), ::testing::UnorderedElementsAre());
125 EXPECT_GE(m.bucket_count(), 123);
126 }
127
128 TYPED_TEST_P(ConstructorTest, BucketCountAlloc) {
129 BucketCountAllocTest<TypeParam>(expect_cxx14_apis<TypeParam>());
130 }
131
132 template <typename TypeParam>
133 void BucketCountHashAllocTest(std::false_type) {}
134
135 template <typename TypeParam>
136 void BucketCountHashAllocTest(std::true_type) {
137 using H = typename TypeParam::hasher;
138 using A = typename TypeParam::allocator_type;
139 H hasher;
140 A alloc(0);
141 TypeParam m(123, hasher, alloc);
142 EXPECT_EQ(m.hash_function(), hasher);
143 EXPECT_EQ(m.get_allocator(), alloc);
144 EXPECT_TRUE(m.empty());
145 EXPECT_THAT(keys(m), ::testing::UnorderedElementsAre());
146 EXPECT_GE(m.bucket_count(), 123);
147 }
148
149 TYPED_TEST_P(ConstructorTest, BucketCountHashAlloc) {
150 BucketCountHashAllocTest<TypeParam>(expect_cxx14_apis<TypeParam>());
151 }
152
153 #if ABSL_UNORDERED_SUPPORTS_ALLOC_CTORS
154 using has_alloc_std_constructors = std::true_type;
155 #else
156 using has_alloc_std_constructors = std::false_type;
157 #endif
158
159 template <typename T>
160 using expect_alloc_constructors =
161 absl::disjunction<absl::negation<is_std_unordered_set<T>>,
162 has_alloc_std_constructors>;
163
164 template <typename TypeParam>
165 void AllocTest(std::false_type) {}
166
167 template <typename TypeParam>
168 void AllocTest(std::true_type) {
169 using A = typename TypeParam::allocator_type;
170 A alloc(0);
171 TypeParam m(alloc);
172 EXPECT_EQ(m.get_allocator(), alloc);
173 EXPECT_TRUE(m.empty());
174 EXPECT_THAT(keys(m), ::testing::UnorderedElementsAre());
175 }
176
177 TYPED_TEST_P(ConstructorTest, Alloc) {
178 AllocTest<TypeParam>(expect_alloc_constructors<TypeParam>());
179 }
180
181 TYPED_TEST_P(ConstructorTest, InputIteratorBucketHashEqualAlloc) {
182 using T = hash_internal::GeneratedType<TypeParam>;
183 using H = typename TypeParam::hasher;
184 using E = typename TypeParam::key_equal;
185 using A = typename TypeParam::allocator_type;
186 H hasher;
187 E equal;
188 A alloc(0);
189 std::vector<T> values;
190 for (size_t i = 0; i != 10; ++i)
191 values.push_back(hash_internal::Generator<T>()());
192 TypeParam m(values.begin(), values.end(), 123, hasher, equal, alloc);
193 EXPECT_EQ(m.hash_function(), hasher);
194 EXPECT_EQ(m.key_eq(), equal);
195 EXPECT_EQ(m.get_allocator(), alloc);
196 EXPECT_THAT(keys(m), ::testing::UnorderedElementsAreArray(values));
197 EXPECT_GE(m.bucket_count(), 123);
198 }
199
200 template <typename TypeParam>
201 void InputIteratorBucketAllocTest(std::false_type) {}
202
203 template <typename TypeParam>
204 void InputIteratorBucketAllocTest(std::true_type) {
205 using T = hash_internal::GeneratedType<TypeParam>;
206 using A = typename TypeParam::allocator_type;
207 A alloc(0);
208 std::vector<T> values;
209 for (size_t i = 0; i != 10; ++i)
210 values.push_back(hash_internal::Generator<T>()());
211 TypeParam m(values.begin(), values.end(), 123, alloc);
212 EXPECT_EQ(m.get_allocator(), alloc);
213 EXPECT_THAT(keys(m), ::testing::UnorderedElementsAreArray(values));
214 EXPECT_GE(m.bucket_count(), 123);
215 }
216
217 TYPED_TEST_P(ConstructorTest, InputIteratorBucketAlloc) {
218 InputIteratorBucketAllocTest<TypeParam>(expect_cxx14_apis<TypeParam>());
219 }
220
221 template <typename TypeParam>
222 void InputIteratorBucketHashAllocTest(std::false_type) {}
223
224 template <typename TypeParam>
225 void InputIteratorBucketHashAllocTest(std::true_type) {
226 using T = hash_internal::GeneratedType<TypeParam>;
227 using H = typename TypeParam::hasher;
228 using A = typename TypeParam::allocator_type;
229 H hasher;
230 A alloc(0);
231 std::vector<T> values;
232 for (size_t i = 0; i != 10; ++i)
233 values.push_back(hash_internal::Generator<T>()());
234 TypeParam m(values.begin(), values.end(), 123, hasher, alloc);
235 EXPECT_EQ(m.hash_function(), hasher);
236 EXPECT_EQ(m.get_allocator(), alloc);
237 EXPECT_THAT(keys(m), ::testing::UnorderedElementsAreArray(values));
238 EXPECT_GE(m.bucket_count(), 123);
239 }
240
241 TYPED_TEST_P(ConstructorTest, InputIteratorBucketHashAlloc) {
242 InputIteratorBucketHashAllocTest<TypeParam>(expect_cxx14_apis<TypeParam>());
243 }
244
245 TYPED_TEST_P(ConstructorTest, CopyConstructor) {
246 using T = hash_internal::GeneratedType<TypeParam>;
247 using H = typename TypeParam::hasher;
248 using E = typename TypeParam::key_equal;
249 using A = typename TypeParam::allocator_type;
250 H hasher;
251 E equal;
252 A alloc(0);
253 TypeParam m(123, hasher, equal, alloc);
254 for (size_t i = 0; i != 10; ++i) m.insert(hash_internal::Generator<T>()());
255 TypeParam n(m);
256 EXPECT_EQ(m.hash_function(), n.hash_function());
257 EXPECT_EQ(m.key_eq(), n.key_eq());
258 EXPECT_EQ(m.get_allocator(), n.get_allocator());
259 EXPECT_EQ(m, n);
260 EXPECT_NE(TypeParam(0, hasher, equal, alloc), n);
261 }
262
263 template <typename TypeParam>
264 void CopyConstructorAllocTest(std::false_type) {}
265
266 template <typename TypeParam>
267 void CopyConstructorAllocTest(std::true_type) {
268 using T = hash_internal::GeneratedType<TypeParam>;
269 using H = typename TypeParam::hasher;
270 using E = typename TypeParam::key_equal;
271 using A = typename TypeParam::allocator_type;
272 H hasher;
273 E equal;
274 A alloc(0);
275 TypeParam m(123, hasher, equal, alloc);
276 for (size_t i = 0; i != 10; ++i) m.insert(hash_internal::Generator<T>()());
277 TypeParam n(m, A(11));
278 EXPECT_EQ(m.hash_function(), n.hash_function());
279 EXPECT_EQ(m.key_eq(), n.key_eq());
280 EXPECT_NE(m.get_allocator(), n.get_allocator());
281 EXPECT_EQ(m, n);
282 }
283
284 TYPED_TEST_P(ConstructorTest, CopyConstructorAlloc) {
285 CopyConstructorAllocTest<TypeParam>(expect_alloc_constructors<TypeParam>());
286 }
287
288 // TODO(alkis): Test non-propagating allocators on copy constructors.
289
290 TYPED_TEST_P(ConstructorTest, MoveConstructor) {
291 using T = hash_internal::GeneratedType<TypeParam>;
292 using H = typename TypeParam::hasher;
293 using E = typename TypeParam::key_equal;
294 using A = typename TypeParam::allocator_type;
295 H hasher;
296 E equal;
297 A alloc(0);
298 TypeParam m(123, hasher, equal, alloc);
299 for (size_t i = 0; i != 10; ++i) m.insert(hash_internal::Generator<T>()());
300 TypeParam t(m);
301 TypeParam n(std::move(t));
302 EXPECT_EQ(m.hash_function(), n.hash_function());
303 EXPECT_EQ(m.key_eq(), n.key_eq());
304 EXPECT_EQ(m.get_allocator(), n.get_allocator());
305 EXPECT_EQ(m, n);
306 }
307
308 template <typename TypeParam>
309 void MoveConstructorAllocTest(std::false_type) {}
310
311 template <typename TypeParam>
312 void MoveConstructorAllocTest(std::true_type) {
313 using T = hash_internal::GeneratedType<TypeParam>;
314 using H = typename TypeParam::hasher;
315 using E = typename TypeParam::key_equal;
316 using A = typename TypeParam::allocator_type;
317 H hasher;
318 E equal;
319 A alloc(0);
320 TypeParam m(123, hasher, equal, alloc);
321 for (size_t i = 0; i != 10; ++i) m.insert(hash_internal::Generator<T>()());
322 TypeParam t(m);
323 TypeParam n(std::move(t), A(1));
324 EXPECT_EQ(m.hash_function(), n.hash_function());
325 EXPECT_EQ(m.key_eq(), n.key_eq());
326 EXPECT_NE(m.get_allocator(), n.get_allocator());
327 EXPECT_EQ(m, n);
328 }
329
330 TYPED_TEST_P(ConstructorTest, MoveConstructorAlloc) {
331 MoveConstructorAllocTest<TypeParam>(expect_alloc_constructors<TypeParam>());
332 }
333
334 // TODO(alkis): Test non-propagating allocators on move constructors.
335
336 TYPED_TEST_P(ConstructorTest, InitializerListBucketHashEqualAlloc) {
337 using T = hash_internal::GeneratedType<TypeParam>;
338 hash_internal::Generator<T> gen;
339 std::initializer_list<T> values = {gen(), gen(), gen(), gen(), gen()};
340 using H = typename TypeParam::hasher;
341 using E = typename TypeParam::key_equal;
342 using A = typename TypeParam::allocator_type;
343 H hasher;
344 E equal;
345 A alloc(0);
346 TypeParam m(values, 123, hasher, equal, alloc);
347 EXPECT_EQ(m.hash_function(), hasher);
348 EXPECT_EQ(m.key_eq(), equal);
349 EXPECT_EQ(m.get_allocator(), alloc);
350 EXPECT_THAT(keys(m), ::testing::UnorderedElementsAreArray(values));
351 EXPECT_GE(m.bucket_count(), 123);
352 }
353
354 template <typename TypeParam>
355 void InitializerListBucketAllocTest(std::false_type) {}
356
357 template <typename TypeParam>
358 void InitializerListBucketAllocTest(std::true_type) {
359 using T = hash_internal::GeneratedType<TypeParam>;
360 using A = typename TypeParam::allocator_type;
361 hash_internal::Generator<T> gen;
362 std::initializer_list<T> values = {gen(), gen(), gen(), gen(), gen()};
363 A alloc(0);
364 TypeParam m(values, 123, alloc);
365 EXPECT_EQ(m.get_allocator(), alloc);
366 EXPECT_THAT(keys(m), ::testing::UnorderedElementsAreArray(values));
367 EXPECT_GE(m.bucket_count(), 123);
368 }
369
370 TYPED_TEST_P(ConstructorTest, InitializerListBucketAlloc) {
371 InitializerListBucketAllocTest<TypeParam>(expect_cxx14_apis<TypeParam>());
372 }
373
374 template <typename TypeParam>
375 void InitializerListBucketHashAllocTest(std::false_type) {}
376
377 template <typename TypeParam>
378 void InitializerListBucketHashAllocTest(std::true_type) {
379 using T = hash_internal::GeneratedType<TypeParam>;
380 using H = typename TypeParam::hasher;
381 using A = typename TypeParam::allocator_type;
382 H hasher;
383 A alloc(0);
384 hash_internal::Generator<T> gen;
385 std::initializer_list<T> values = {gen(), gen(), gen(), gen(), gen()};
386 TypeParam m(values, 123, hasher, alloc);
387 EXPECT_EQ(m.hash_function(), hasher);
388 EXPECT_EQ(m.get_allocator(), alloc);
389 EXPECT_THAT(keys(m), ::testing::UnorderedElementsAreArray(values));
390 EXPECT_GE(m.bucket_count(), 123);
391 }
392
393 TYPED_TEST_P(ConstructorTest, InitializerListBucketHashAlloc) {
394 InitializerListBucketHashAllocTest<TypeParam>(expect_cxx14_apis<TypeParam>());
395 }
396
397 TYPED_TEST_P(ConstructorTest, CopyAssignment) {
398 using T = hash_internal::GeneratedType<TypeParam>;
399 using H = typename TypeParam::hasher;
400 using E = typename TypeParam::key_equal;
401 using A = typename TypeParam::allocator_type;
402 H hasher;
403 E equal;
404 A alloc(0);
405 hash_internal::Generator<T> gen;
406 TypeParam m({gen(), gen(), gen()}, 123, hasher, equal, alloc);
407 TypeParam n;
408 n = m;
409 EXPECT_EQ(m.hash_function(), n.hash_function());
410 EXPECT_EQ(m.key_eq(), n.key_eq());
411 EXPECT_EQ(m, n);
412 }
413
414 // TODO(alkis): Test [non-]propagating allocators on move/copy assignments
415 // (it depends on traits).
416
417 TYPED_TEST_P(ConstructorTest, MoveAssignment) {
418 using T = hash_internal::GeneratedType<TypeParam>;
419 using H = typename TypeParam::hasher;
420 using E = typename TypeParam::key_equal;
421 using A = typename TypeParam::allocator_type;
422 H hasher;
423 E equal;
424 A alloc(0);
425 hash_internal::Generator<T> gen;
426 TypeParam m({gen(), gen(), gen()}, 123, hasher, equal, alloc);
427 TypeParam t(m);
428 TypeParam n;
429 n = std::move(t);
430 EXPECT_EQ(m.hash_function(), n.hash_function());
431 EXPECT_EQ(m.key_eq(), n.key_eq());
432 EXPECT_EQ(m, n);
433 }
434
435 TYPED_TEST_P(ConstructorTest, AssignmentFromInitializerList) {
436 using T = hash_internal::GeneratedType<TypeParam>;
437 hash_internal::Generator<T> gen;
438 std::initializer_list<T> values = {gen(), gen(), gen(), gen(), gen()};
439 TypeParam m;
440 m = values;
441 EXPECT_THAT(keys(m), ::testing::UnorderedElementsAreArray(values));
442 }
443
444 TYPED_TEST_P(ConstructorTest, AssignmentOverwritesExisting) {
445 using T = hash_internal::GeneratedType<TypeParam>;
446 hash_internal::Generator<T> gen;
447 TypeParam m({gen(), gen(), gen()});
448 TypeParam n({gen()});
449 n = m;
450 EXPECT_EQ(m, n);
451 }
452
453 TYPED_TEST_P(ConstructorTest, MoveAssignmentOverwritesExisting) {
454 using T = hash_internal::GeneratedType<TypeParam>;
455 hash_internal::Generator<T> gen;
456 TypeParam m({gen(), gen(), gen()});
457 TypeParam t(m);
458 TypeParam n({gen()});
459 n = std::move(t);
460 EXPECT_EQ(m, n);
461 }
462
463 TYPED_TEST_P(ConstructorTest, AssignmentFromInitializerListOverwritesExisting) {
464 using T = hash_internal::GeneratedType<TypeParam>;
465 hash_internal::Generator<T> gen;
466 std::initializer_list<T> values = {gen(), gen(), gen(), gen(), gen()};
467 TypeParam m;
468 m = values;
469 EXPECT_THAT(keys(m), ::testing::UnorderedElementsAreArray(values));
470 }
471
472 TYPED_TEST_P(ConstructorTest, AssignmentOnSelf) {
473 using T = hash_internal::GeneratedType<TypeParam>;
474 hash_internal::Generator<T> gen;
475 std::initializer_list<T> values = {gen(), gen(), gen(), gen(), gen()};
476 TypeParam m(values);
477 m = *&m; // Avoid -Wself-assign.
478 EXPECT_THAT(keys(m), ::testing::UnorderedElementsAreArray(values));
479 }
480
481 REGISTER_TYPED_TEST_CASE_P(
482 ConstructorTest, NoArgs, BucketCount, BucketCountHash, BucketCountHashEqual,
483 BucketCountHashEqualAlloc, BucketCountAlloc, BucketCountHashAlloc, Alloc,
484 InputIteratorBucketHashEqualAlloc, InputIteratorBucketAlloc,
485 InputIteratorBucketHashAlloc, CopyConstructor, CopyConstructorAlloc,
486 MoveConstructor, MoveConstructorAlloc, InitializerListBucketHashEqualAlloc,
487 InitializerListBucketAlloc, InitializerListBucketHashAlloc, CopyAssignment,
488 MoveAssignment, AssignmentFromInitializerList, AssignmentOverwritesExisting,
489 MoveAssignmentOverwritesExisting,
490 AssignmentFromInitializerListOverwritesExisting, AssignmentOnSelf);
491
492 } // namespace container_internal
493 ABSL_NAMESPACE_END
494 } // namespace absl
495
496 #endif // ABSL_CONTAINER_INTERNAL_UNORDERED_SET_CONSTRUCTOR_TEST_H_
497