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