container/internal/unordered_map_constructor_test.h

0001 // Copyright 2018 The Abseil Authors.
0002 //
0003 // Licensed under the Apache License, Version 2.0 (the "License");
0004 // you may not use this file except in compliance with the License.
0005 // You may obtain a copy of the License at
0006 //
0007 //      https://www.apache.org/licenses/LICENSE-2.0
0008 //
0009 // Unless required by applicable law or agreed to in writing, software
0010 // distributed under the License is distributed on an "AS IS" BASIS,
0011 // WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
0012 // See the License for the specific language governing permissions and
0013 // limitations under the License.
0014
0015 #ifndef ABSL_CONTAINER_INTERNAL_UNORDERED_MAP_CONSTRUCTOR_TEST_H_
0016 #define ABSL_CONTAINER_INTERNAL_UNORDERED_MAP_CONSTRUCTOR_TEST_H_
0017
0018 #include <algorithm>
0019 #include <unordered_map>
0020 #include <vector>
0021
0022 #include "gmock/gmock.h"
0023 #include "gtest/gtest.h"
0024 #include "absl/container/internal/hash_generator_testing.h"
0025 #include "absl/container/internal/hash_policy_testing.h"
0026
0027 namespace absl {
0028 ABSL_NAMESPACE_BEGIN
0029 namespace container_internal {
0030
0031 template <class UnordMap>
0032 class ConstructorTest : public ::testing::Test {};
0033
0034 TYPED_TEST_SUITE_P(ConstructorTest);
0035
0036 TYPED_TEST_P(ConstructorTest, NoArgs) {
0037   TypeParam m;
0038   EXPECT_TRUE(m.empty());
0039   EXPECT_THAT(m, ::testing::UnorderedElementsAre());
0040 }
0041
0042 TYPED_TEST_P(ConstructorTest, BucketCount) {
0043   TypeParam m(123);
0044   EXPECT_TRUE(m.empty());
0045   EXPECT_THAT(m, ::testing::UnorderedElementsAre());
0046   EXPECT_GE(m.bucket_count(), 123);
0047 }
0048
0049 TYPED_TEST_P(ConstructorTest, BucketCountHash) {
0050   using H = typename TypeParam::hasher;
0051   H hasher;
0052   TypeParam m(123, hasher);
0053   EXPECT_EQ(m.hash_function(), hasher);
0054   EXPECT_TRUE(m.empty());
0055   EXPECT_THAT(m, ::testing::UnorderedElementsAre());
0056   EXPECT_GE(m.bucket_count(), 123);
0057 }
0058
0059 TYPED_TEST_P(ConstructorTest, BucketCountHashEqual) {
0060   using H = typename TypeParam::hasher;
0061   using E = typename TypeParam::key_equal;
0062   H hasher;
0063   E equal;
0064   TypeParam m(123, hasher, equal);
0065   EXPECT_EQ(m.hash_function(), hasher);
0066   EXPECT_EQ(m.key_eq(), equal);
0067   EXPECT_TRUE(m.empty());
0068   EXPECT_THAT(m, ::testing::UnorderedElementsAre());
0069   EXPECT_GE(m.bucket_count(), 123);
0070 }
0071
0072 TYPED_TEST_P(ConstructorTest, BucketCountHashEqualAlloc) {
0073   using H = typename TypeParam::hasher;
0074   using E = typename TypeParam::key_equal;
0075   using A = typename TypeParam::allocator_type;
0076   H hasher;
0077   E equal;
0078   A alloc(0);
0079   TypeParam m(123, hasher, equal, alloc);
0080   EXPECT_EQ(m.hash_function(), hasher);
0081   EXPECT_EQ(m.key_eq(), equal);
0082   EXPECT_EQ(m.get_allocator(), alloc);
0083   EXPECT_TRUE(m.empty());
0084   EXPECT_THAT(m, ::testing::UnorderedElementsAre());
0085   EXPECT_GE(m.bucket_count(), 123);
0086 }
0087
0088 template <typename T>
0089 struct is_std_unordered_map : std::false_type {};
0090
0091 template <typename... T>
0092 struct is_std_unordered_map<std::unordered_map<T...>> : std::true_type {};
0093
0094 #if defined(UNORDERED_MAP_CXX14) || defined(UNORDERED_MAP_CXX17)
0095 using has_cxx14_std_apis = std::true_type;
0096 #else
0097 using has_cxx14_std_apis = std::false_type;
0098 #endif
0099
0100 template <typename T>
0101 using expect_cxx14_apis =
0102     absl::disjunction<absl::negation<is_std_unordered_map<T>>,
0103                       has_cxx14_std_apis>;
0104
0105 template <typename TypeParam>
0106 void BucketCountAllocTest(std::false_type) {}
0107
0108 template <typename TypeParam>
0109 void BucketCountAllocTest(std::true_type) {
0110   using A = typename TypeParam::allocator_type;
0111   A alloc(0);
0112   TypeParam m(123, alloc);
0113   EXPECT_EQ(m.get_allocator(), alloc);
0114   EXPECT_TRUE(m.empty());
0115   EXPECT_THAT(m, ::testing::UnorderedElementsAre());
0116   EXPECT_GE(m.bucket_count(), 123);
0117 }
0118
0119 TYPED_TEST_P(ConstructorTest, BucketCountAlloc) {
0120   BucketCountAllocTest<TypeParam>(expect_cxx14_apis<TypeParam>());
0121 }
0122
0123 template <typename TypeParam>
0124 void BucketCountHashAllocTest(std::false_type) {}
0125
0126 template <typename TypeParam>
0127 void BucketCountHashAllocTest(std::true_type) {
0128   using H = typename TypeParam::hasher;
0129   using A = typename TypeParam::allocator_type;
0130   H hasher;
0131   A alloc(0);
0132   TypeParam m(123, hasher, alloc);
0133   EXPECT_EQ(m.hash_function(), hasher);
0134   EXPECT_EQ(m.get_allocator(), alloc);
0135   EXPECT_TRUE(m.empty());
0136   EXPECT_THAT(m, ::testing::UnorderedElementsAre());
0137   EXPECT_GE(m.bucket_count(), 123);
0138 }
0139
0140 TYPED_TEST_P(ConstructorTest, BucketCountHashAlloc) {
0141   BucketCountHashAllocTest<TypeParam>(expect_cxx14_apis<TypeParam>());
0142 }
0143
0144 #if ABSL_UNORDERED_SUPPORTS_ALLOC_CTORS
0145 using has_alloc_std_constructors = std::true_type;
0146 #else
0147 using has_alloc_std_constructors = std::false_type;
0148 #endif
0149
0150 template <typename T>
0151 using expect_alloc_constructors =
0152     absl::disjunction<absl::negation<is_std_unordered_map<T>>,
0153                       has_alloc_std_constructors>;
0154
0155 template <typename TypeParam>
0156 void AllocTest(std::false_type) {}
0157
0158 template <typename TypeParam>
0159 void AllocTest(std::true_type) {
0160   using A = typename TypeParam::allocator_type;
0161   A alloc(0);
0162   TypeParam m(alloc);
0163   EXPECT_EQ(m.get_allocator(), alloc);
0164   EXPECT_TRUE(m.empty());
0165   EXPECT_THAT(m, ::testing::UnorderedElementsAre());
0166 }
0167
0168 TYPED_TEST_P(ConstructorTest, Alloc) {
0169   AllocTest<TypeParam>(expect_alloc_constructors<TypeParam>());
0170 }
0171
0172 TYPED_TEST_P(ConstructorTest, InputIteratorBucketHashEqualAlloc) {
0173   using T = hash_internal::GeneratedType<TypeParam>;
0174   using H = typename TypeParam::hasher;
0175   using E = typename TypeParam::key_equal;
0176   using A = typename TypeParam::allocator_type;
0177   H hasher;
0178   E equal;
0179   A alloc(0);
0180   std::vector<T> values;
0181   std::generate_n(std::back_inserter(values), 10,
0182                   hash_internal::UniqueGenerator<T>());
0183   TypeParam m(values.begin(), values.end(), 123, hasher, equal, alloc);
0184   EXPECT_EQ(m.hash_function(), hasher);
0185   EXPECT_EQ(m.key_eq(), equal);
0186   EXPECT_EQ(m.get_allocator(), alloc);
0187   EXPECT_THAT(items(m), ::testing::UnorderedElementsAreArray(values));
0188   EXPECT_GE(m.bucket_count(), 123);
0189 }
0190
0191 template <typename TypeParam>
0192 void InputIteratorBucketAllocTest(std::false_type) {}
0193
0194 template <typename TypeParam>
0195 void InputIteratorBucketAllocTest(std::true_type) {
0196   using T = hash_internal::GeneratedType<TypeParam>;
0197   using A = typename TypeParam::allocator_type;
0198   A alloc(0);
0199   std::vector<T> values;
0200   std::generate_n(std::back_inserter(values), 10,
0201                   hash_internal::UniqueGenerator<T>());
0202   TypeParam m(values.begin(), values.end(), 123, alloc);
0203   EXPECT_EQ(m.get_allocator(), alloc);
0204   EXPECT_THAT(items(m), ::testing::UnorderedElementsAreArray(values));
0205   EXPECT_GE(m.bucket_count(), 123);
0206 }
0207
0208 TYPED_TEST_P(ConstructorTest, InputIteratorBucketAlloc) {
0209   InputIteratorBucketAllocTest<TypeParam>(expect_cxx14_apis<TypeParam>());
0210 }
0211
0212 template <typename TypeParam>
0213 void InputIteratorBucketHashAllocTest(std::false_type) {}
0214
0215 template <typename TypeParam>
0216 void InputIteratorBucketHashAllocTest(std::true_type) {
0217   using T = hash_internal::GeneratedType<TypeParam>;
0218   using H = typename TypeParam::hasher;
0219   using A = typename TypeParam::allocator_type;
0220   H hasher;
0221   A alloc(0);
0222   std::vector<T> values;
0223   std::generate_n(std::back_inserter(values), 10,
0224                   hash_internal::UniqueGenerator<T>());
0225   TypeParam m(values.begin(), values.end(), 123, hasher, alloc);
0226   EXPECT_EQ(m.hash_function(), hasher);
0227   EXPECT_EQ(m.get_allocator(), alloc);
0228   EXPECT_THAT(items(m), ::testing::UnorderedElementsAreArray(values));
0229   EXPECT_GE(m.bucket_count(), 123);
0230 }
0231
0232 TYPED_TEST_P(ConstructorTest, InputIteratorBucketHashAlloc) {
0233   InputIteratorBucketHashAllocTest<TypeParam>(expect_cxx14_apis<TypeParam>());
0234 }
0235
0236 TYPED_TEST_P(ConstructorTest, CopyConstructor) {
0237   using T = hash_internal::GeneratedType<TypeParam>;
0238   using H = typename TypeParam::hasher;
0239   using E = typename TypeParam::key_equal;
0240   using A = typename TypeParam::allocator_type;
0241   H hasher;
0242   E equal;
0243   A alloc(0);
0244   hash_internal::UniqueGenerator<T> gen;
0245   TypeParam m(123, hasher, equal, alloc);
0246   for (size_t i = 0; i != 10; ++i) m.insert(gen());
0247   TypeParam n(m);
0248   EXPECT_EQ(m.hash_function(), n.hash_function());
0249   EXPECT_EQ(m.key_eq(), n.key_eq());
0250   EXPECT_EQ(m.get_allocator(), n.get_allocator());
0251   EXPECT_EQ(m, n);
0252 }
0253
0254 template <typename TypeParam>
0255 void CopyConstructorAllocTest(std::false_type) {}
0256
0257 template <typename TypeParam>
0258 void CopyConstructorAllocTest(std::true_type) {
0259   using T = hash_internal::GeneratedType<TypeParam>;
0260   using H = typename TypeParam::hasher;
0261   using E = typename TypeParam::key_equal;
0262   using A = typename TypeParam::allocator_type;
0263   H hasher;
0264   E equal;
0265   A alloc(0);
0266   hash_internal::UniqueGenerator<T> gen;
0267   TypeParam m(123, hasher, equal, alloc);
0268   for (size_t i = 0; i != 10; ++i) m.insert(gen());
0269   TypeParam n(m, A(11));
0270   EXPECT_EQ(m.hash_function(), n.hash_function());
0271   EXPECT_EQ(m.key_eq(), n.key_eq());
0272   EXPECT_NE(m.get_allocator(), n.get_allocator());
0273   EXPECT_EQ(m, n);
0274 }
0275
0276 TYPED_TEST_P(ConstructorTest, CopyConstructorAlloc) {
0277   CopyConstructorAllocTest<TypeParam>(expect_alloc_constructors<TypeParam>());
0278 }
0279
0280 // TODO(alkis): Test non-propagating allocators on copy constructors.
0281
0282 TYPED_TEST_P(ConstructorTest, MoveConstructor) {
0283   using T = hash_internal::GeneratedType<TypeParam>;
0284   using H = typename TypeParam::hasher;
0285   using E = typename TypeParam::key_equal;
0286   using A = typename TypeParam::allocator_type;
0287   H hasher;
0288   E equal;
0289   A alloc(0);
0290   hash_internal::UniqueGenerator<T> gen;
0291   TypeParam m(123, hasher, equal, alloc);
0292   for (size_t i = 0; i != 10; ++i) m.insert(gen());
0293   TypeParam t(m);
0294   TypeParam n(std::move(t));
0295   EXPECT_EQ(m.hash_function(), n.hash_function());
0296   EXPECT_EQ(m.key_eq(), n.key_eq());
0297   EXPECT_EQ(m.get_allocator(), n.get_allocator());
0298   EXPECT_EQ(m, n);
0299 }
0300
0301 template <typename TypeParam>
0302 void MoveConstructorAllocTest(std::false_type) {}
0303
0304 template <typename TypeParam>
0305 void MoveConstructorAllocTest(std::true_type) {
0306   using T = hash_internal::GeneratedType<TypeParam>;
0307   using H = typename TypeParam::hasher;
0308   using E = typename TypeParam::key_equal;
0309   using A = typename TypeParam::allocator_type;
0310   H hasher;
0311   E equal;
0312   A alloc(0);
0313   hash_internal::UniqueGenerator<T> gen;
0314   TypeParam m(123, hasher, equal, alloc);
0315   for (size_t i = 0; i != 10; ++i) m.insert(gen());
0316   TypeParam t(m);
0317   TypeParam n(std::move(t), A(1));
0318   EXPECT_EQ(m.hash_function(), n.hash_function());
0319   EXPECT_EQ(m.key_eq(), n.key_eq());
0320   EXPECT_NE(m.get_allocator(), n.get_allocator());
0321   EXPECT_EQ(m, n);
0322 }
0323
0324 TYPED_TEST_P(ConstructorTest, MoveConstructorAlloc) {
0325   MoveConstructorAllocTest<TypeParam>(expect_alloc_constructors<TypeParam>());
0326 }
0327
0328 // TODO(alkis): Test non-propagating allocators on move constructors.
0329
0330 TYPED_TEST_P(ConstructorTest, InitializerListBucketHashEqualAlloc) {
0331   using T = hash_internal::GeneratedType<TypeParam>;
0332   hash_internal::UniqueGenerator<T> gen;
0333   std::initializer_list<T> values = {gen(), gen(), gen(), gen(), gen()};
0334   using H = typename TypeParam::hasher;
0335   using E = typename TypeParam::key_equal;
0336   using A = typename TypeParam::allocator_type;
0337   H hasher;
0338   E equal;
0339   A alloc(0);
0340   TypeParam m(values, 123, hasher, equal, alloc);
0341   EXPECT_EQ(m.hash_function(), hasher);
0342   EXPECT_EQ(m.key_eq(), equal);
0343   EXPECT_EQ(m.get_allocator(), alloc);
0344   EXPECT_THAT(items(m), ::testing::UnorderedElementsAreArray(values));
0345   EXPECT_GE(m.bucket_count(), 123);
0346 }
0347
0348 template <typename TypeParam>
0349 void InitializerListBucketAllocTest(std::false_type) {}
0350
0351 template <typename TypeParam>
0352 void InitializerListBucketAllocTest(std::true_type) {
0353   using T = hash_internal::GeneratedType<TypeParam>;
0354   using A = typename TypeParam::allocator_type;
0355   hash_internal::UniqueGenerator<T> gen;
0356   std::initializer_list<T> values = {gen(), gen(), gen(), gen(), gen()};
0357   A alloc(0);
0358   TypeParam m(values, 123, alloc);
0359   EXPECT_EQ(m.get_allocator(), alloc);
0360   EXPECT_THAT(items(m), ::testing::UnorderedElementsAreArray(values));
0361   EXPECT_GE(m.bucket_count(), 123);
0362 }
0363
0364 TYPED_TEST_P(ConstructorTest, InitializerListBucketAlloc) {
0365   InitializerListBucketAllocTest<TypeParam>(expect_cxx14_apis<TypeParam>());
0366 }
0367
0368 template <typename TypeParam>
0369 void InitializerListBucketHashAllocTest(std::false_type) {}
0370
0371 template <typename TypeParam>
0372 void InitializerListBucketHashAllocTest(std::true_type) {
0373   using T = hash_internal::GeneratedType<TypeParam>;
0374   using H = typename TypeParam::hasher;
0375   using A = typename TypeParam::allocator_type;
0376   H hasher;
0377   A alloc(0);
0378   hash_internal::UniqueGenerator<T> gen;
0379   std::initializer_list<T> values = {gen(), gen(), gen(), gen(), gen()};
0380   TypeParam m(values, 123, hasher, alloc);
0381   EXPECT_EQ(m.hash_function(), hasher);
0382   EXPECT_EQ(m.get_allocator(), alloc);
0383   EXPECT_THAT(items(m), ::testing::UnorderedElementsAreArray(values));
0384   EXPECT_GE(m.bucket_count(), 123);
0385 }
0386
0387 TYPED_TEST_P(ConstructorTest, InitializerListBucketHashAlloc) {
0388   InitializerListBucketHashAllocTest<TypeParam>(expect_cxx14_apis<TypeParam>());
0389 }
0390
0391 TYPED_TEST_P(ConstructorTest, Assignment) {
0392   using T = hash_internal::GeneratedType<TypeParam>;
0393   using H = typename TypeParam::hasher;
0394   using E = typename TypeParam::key_equal;
0395   using A = typename TypeParam::allocator_type;
0396   H hasher;
0397   E equal;
0398   A alloc(0);
0399   hash_internal::UniqueGenerator<T> gen;
0400   TypeParam m({gen(), gen(), gen()}, 123, hasher, equal, alloc);
0401   TypeParam n;
0402   n = m;
0403   EXPECT_EQ(m.hash_function(), n.hash_function());
0404   EXPECT_EQ(m.key_eq(), n.key_eq());
0405   EXPECT_EQ(m, n);
0406 }
0407
0408 // TODO(alkis): Test [non-]propagating allocators on move/copy assignments
0409 // (it depends on traits).
0410
0411 TYPED_TEST_P(ConstructorTest, MoveAssignment) {
0412   using T = hash_internal::GeneratedType<TypeParam>;
0413   using H = typename TypeParam::hasher;
0414   using E = typename TypeParam::key_equal;
0415   using A = typename TypeParam::allocator_type;
0416   H hasher;
0417   E equal;
0418   A alloc(0);
0419   hash_internal::UniqueGenerator<T> gen;
0420   TypeParam m({gen(), gen(), gen()}, 123, hasher, equal, alloc);
0421   TypeParam t(m);
0422   TypeParam n;
0423   n = std::move(t);
0424   EXPECT_EQ(m.hash_function(), n.hash_function());
0425   EXPECT_EQ(m.key_eq(), n.key_eq());
0426   EXPECT_EQ(m, n);
0427 }
0428
0429 TYPED_TEST_P(ConstructorTest, AssignmentFromInitializerList) {
0430   using T = hash_internal::GeneratedType<TypeParam>;
0431   hash_internal::UniqueGenerator<T> gen;
0432   std::initializer_list<T> values = {gen(), gen(), gen(), gen(), gen()};
0433   TypeParam m;
0434   m = values;
0435   EXPECT_THAT(items(m), ::testing::UnorderedElementsAreArray(values));
0436 }
0437
0438 TYPED_TEST_P(ConstructorTest, AssignmentOverwritesExisting) {
0439   using T = hash_internal::GeneratedType<TypeParam>;
0440   hash_internal::UniqueGenerator<T> gen;
0441   TypeParam m({gen(), gen(), gen()});
0442   TypeParam n({gen()});
0443   n = m;
0444   EXPECT_EQ(m, n);
0445 }
0446
0447 TYPED_TEST_P(ConstructorTest, MoveAssignmentOverwritesExisting) {
0448   using T = hash_internal::GeneratedType<TypeParam>;
0449   hash_internal::UniqueGenerator<T> gen;
0450   TypeParam m({gen(), gen(), gen()});
0451   TypeParam t(m);
0452   TypeParam n({gen()});
0453   n = std::move(t);
0454   EXPECT_EQ(m, n);
0455 }
0456
0457 TYPED_TEST_P(ConstructorTest, AssignmentFromInitializerListOverwritesExisting) {
0458   using T = hash_internal::GeneratedType<TypeParam>;
0459   hash_internal::UniqueGenerator<T> gen;
0460   std::initializer_list<T> values = {gen(), gen(), gen(), gen(), gen()};
0461   TypeParam m;
0462   m = values;
0463   EXPECT_THAT(items(m), ::testing::UnorderedElementsAreArray(values));
0464 }
0465
0466 TYPED_TEST_P(ConstructorTest, AssignmentOnSelf) {
0467   using T = hash_internal::GeneratedType<TypeParam>;
0468   hash_internal::UniqueGenerator<T> gen;
0469   std::initializer_list<T> values = {gen(), gen(), gen(), gen(), gen()};
0470   TypeParam m(values);
0471   m = *&m;  // Avoid -Wself-assign
0472   EXPECT_THAT(items(m), ::testing::UnorderedElementsAreArray(values));
0473 }
0474
0475 // We cannot test self move as standard states that it leaves standard
0476 // containers in unspecified state (and in practice in causes memory-leak
0477 // according to heap-checker!).
0478
0479 REGISTER_TYPED_TEST_SUITE_P(
0480     ConstructorTest, NoArgs, BucketCount, BucketCountHash, BucketCountHashEqual,
0481     BucketCountHashEqualAlloc, BucketCountAlloc, BucketCountHashAlloc, Alloc,
0482     InputIteratorBucketHashEqualAlloc, InputIteratorBucketAlloc,
0483     InputIteratorBucketHashAlloc, CopyConstructor, CopyConstructorAlloc,
0484     MoveConstructor, MoveConstructorAlloc, InitializerListBucketHashEqualAlloc,
0485     InitializerListBucketAlloc, InitializerListBucketHashAlloc, Assignment,
0486     MoveAssignment, AssignmentFromInitializerList, AssignmentOverwritesExisting,
0487     MoveAssignmentOverwritesExisting,
0488     AssignmentFromInitializerListOverwritesExisting, AssignmentOnSelf);
0489
0490 }  // namespace container_internal
0491 ABSL_NAMESPACE_END
0492 }  // namespace absl
0493
0494 #endif  // ABSL_CONTAINER_INTERNAL_UNORDERED_MAP_CONSTRUCTOR_TEST_H_