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