container/internal/unordered_map_modifiers_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_MODIFIERS_TEST_H_
0016 #define ABSL_CONTAINER_INTERNAL_UNORDERED_MAP_MODIFIERS_TEST_H_
0017
0018 #include <memory>
0019
0020 #include "gmock/gmock.h"
0021 #include "gtest/gtest.h"
0022 #include "absl/container/internal/hash_generator_testing.h"
0023 #include "absl/container/internal/hash_policy_testing.h"
0024
0025 namespace absl {
0026 ABSL_NAMESPACE_BEGIN
0027 namespace container_internal {
0028
0029 template <class UnordMap>
0030 class ModifiersTest : public ::testing::Test {};
0031
0032 TYPED_TEST_SUITE_P(ModifiersTest);
0033
0034 TYPED_TEST_P(ModifiersTest, Clear) {
0035   using T = hash_internal::GeneratedType<TypeParam>;
0036   std::vector<T> values;
0037   std::generate_n(std::back_inserter(values), 10,
0038                   hash_internal::Generator<T>());
0039   TypeParam m(values.begin(), values.end());
0040   ASSERT_THAT(items(m), ::testing::UnorderedElementsAreArray(values));
0041   m.clear();
0042   EXPECT_THAT(items(m), ::testing::UnorderedElementsAre());
0043   EXPECT_TRUE(m.empty());
0044 }
0045
0046 TYPED_TEST_P(ModifiersTest, Insert) {
0047   using T = hash_internal::GeneratedType<TypeParam>;
0048   using V = typename TypeParam::mapped_type;
0049   T val = hash_internal::Generator<T>()();
0050   TypeParam m;
0051   auto p = m.insert(val);
0052   EXPECT_TRUE(p.second);
0053   EXPECT_EQ(val, *p.first);
0054   T val2 = {val.first, hash_internal::Generator<V>()()};
0055   p = m.insert(val2);
0056   EXPECT_FALSE(p.second);
0057   EXPECT_EQ(val, *p.first);
0058 }
0059
0060 TYPED_TEST_P(ModifiersTest, InsertHint) {
0061   using T = hash_internal::GeneratedType<TypeParam>;
0062   using V = typename TypeParam::mapped_type;
0063   T val = hash_internal::Generator<T>()();
0064   TypeParam m;
0065   auto it = m.insert(m.end(), val);
0066   EXPECT_TRUE(it != m.end());
0067   EXPECT_EQ(val, *it);
0068   T val2 = {val.first, hash_internal::Generator<V>()()};
0069   it = m.insert(it, val2);
0070   EXPECT_TRUE(it != m.end());
0071   EXPECT_EQ(val, *it);
0072 }
0073
0074 TYPED_TEST_P(ModifiersTest, InsertRange) {
0075   using T = hash_internal::GeneratedType<TypeParam>;
0076   std::vector<T> values;
0077   std::generate_n(std::back_inserter(values), 10,
0078                   hash_internal::Generator<T>());
0079   TypeParam m;
0080   m.insert(values.begin(), values.end());
0081   ASSERT_THAT(items(m), ::testing::UnorderedElementsAreArray(values));
0082 }
0083
0084 TYPED_TEST_P(ModifiersTest, InsertWithinCapacity) {
0085   using T = hash_internal::GeneratedType<TypeParam>;
0086   using V = typename TypeParam::mapped_type;
0087   T val = hash_internal::Generator<T>()();
0088   TypeParam m;
0089   m.reserve(10);
0090   const size_t original_capacity = m.bucket_count();
0091   m.insert(val);
0092   EXPECT_EQ(m.bucket_count(), original_capacity);
0093   T val2 = {val.first, hash_internal::Generator<V>()()};
0094   m.insert(val2);
0095   EXPECT_EQ(m.bucket_count(), original_capacity);
0096 }
0097
0098 TYPED_TEST_P(ModifiersTest, InsertRangeWithinCapacity) {
0099 #if !defined(__GLIBCXX__)
0100   using T = hash_internal::GeneratedType<TypeParam>;
0101   std::vector<T> base_values;
0102   std::generate_n(std::back_inserter(base_values), 10,
0103                   hash_internal::Generator<T>());
0104   std::vector<T> values;
0105   while (values.size() != 100) {
0106     std::copy_n(base_values.begin(), 10, std::back_inserter(values));
0107   }
0108   TypeParam m;
0109   m.reserve(10);
0110   const size_t original_capacity = m.bucket_count();
0111   m.insert(values.begin(), values.end());
0112   EXPECT_EQ(m.bucket_count(), original_capacity);
0113 #endif
0114 }
0115
0116 TYPED_TEST_P(ModifiersTest, InsertOrAssign) {
0117 #ifdef UNORDERED_MAP_CXX17
0118   using std::get;
0119   using K = typename TypeParam::key_type;
0120   using V = typename TypeParam::mapped_type;
0121   K k = hash_internal::Generator<K>()();
0122   V val = hash_internal::Generator<V>()();
0123   TypeParam m;
0124   auto p = m.insert_or_assign(k, val);
0125   EXPECT_TRUE(p.second);
0126   EXPECT_EQ(k, get<0>(*p.first));
0127   EXPECT_EQ(val, get<1>(*p.first));
0128   V val2 = hash_internal::Generator<V>()();
0129   p = m.insert_or_assign(k, val2);
0130   EXPECT_FALSE(p.second);
0131   EXPECT_EQ(k, get<0>(*p.first));
0132   EXPECT_EQ(val2, get<1>(*p.first));
0133 #endif
0134 }
0135
0136 TYPED_TEST_P(ModifiersTest, InsertOrAssignHint) {
0137 #ifdef UNORDERED_MAP_CXX17
0138   using std::get;
0139   using K = typename TypeParam::key_type;
0140   using V = typename TypeParam::mapped_type;
0141   K k = hash_internal::Generator<K>()();
0142   V val = hash_internal::Generator<V>()();
0143   TypeParam m;
0144   auto it = m.insert_or_assign(m.end(), k, val);
0145   EXPECT_TRUE(it != m.end());
0146   EXPECT_EQ(k, get<0>(*it));
0147   EXPECT_EQ(val, get<1>(*it));
0148   V val2 = hash_internal::Generator<V>()();
0149   it = m.insert_or_assign(it, k, val2);
0150   EXPECT_EQ(k, get<0>(*it));
0151   EXPECT_EQ(val2, get<1>(*it));
0152 #endif
0153 }
0154
0155 TYPED_TEST_P(ModifiersTest, Emplace) {
0156   using T = hash_internal::GeneratedType<TypeParam>;
0157   using V = typename TypeParam::mapped_type;
0158   T val = hash_internal::Generator<T>()();
0159   TypeParam m;
0160   // TODO(alkis): We need a way to run emplace in a more meaningful way. Perhaps
0161   // with test traits/policy.
0162   auto p = m.emplace(val);
0163   EXPECT_TRUE(p.second);
0164   EXPECT_EQ(val, *p.first);
0165   T val2 = {val.first, hash_internal::Generator<V>()()};
0166   p = m.emplace(val2);
0167   EXPECT_FALSE(p.second);
0168   EXPECT_EQ(val, *p.first);
0169 }
0170
0171 TYPED_TEST_P(ModifiersTest, EmplaceHint) {
0172   using T = hash_internal::GeneratedType<TypeParam>;
0173   using V = typename TypeParam::mapped_type;
0174   T val = hash_internal::Generator<T>()();
0175   TypeParam m;
0176   // TODO(alkis): We need a way to run emplace in a more meaningful way. Perhaps
0177   // with test traits/policy.
0178   auto it = m.emplace_hint(m.end(), val);
0179   EXPECT_EQ(val, *it);
0180   T val2 = {val.first, hash_internal::Generator<V>()()};
0181   it = m.emplace_hint(it, val2);
0182   EXPECT_EQ(val, *it);
0183 }
0184
0185 TYPED_TEST_P(ModifiersTest, TryEmplace) {
0186 #ifdef UNORDERED_MAP_CXX17
0187   using T = hash_internal::GeneratedType<TypeParam>;
0188   using V = typename TypeParam::mapped_type;
0189   T val = hash_internal::Generator<T>()();
0190   TypeParam m;
0191   // TODO(alkis): We need a way to run emplace in a more meaningful way. Perhaps
0192   // with test traits/policy.
0193   auto p = m.try_emplace(val.first, val.second);
0194   EXPECT_TRUE(p.second);
0195   EXPECT_EQ(val, *p.first);
0196   T val2 = {val.first, hash_internal::Generator<V>()()};
0197   p = m.try_emplace(val2.first, val2.second);
0198   EXPECT_FALSE(p.second);
0199   EXPECT_EQ(val, *p.first);
0200 #endif
0201 }
0202
0203 TYPED_TEST_P(ModifiersTest, TryEmplaceHint) {
0204 #ifdef UNORDERED_MAP_CXX17
0205   using T = hash_internal::GeneratedType<TypeParam>;
0206   using V = typename TypeParam::mapped_type;
0207   T val = hash_internal::Generator<T>()();
0208   TypeParam m;
0209   // TODO(alkis): We need a way to run emplace in a more meaningful way. Perhaps
0210   // with test traits/policy.
0211   auto it = m.try_emplace(m.end(), val.first, val.second);
0212   EXPECT_EQ(val, *it);
0213   T val2 = {val.first, hash_internal::Generator<V>()()};
0214   it = m.try_emplace(it, val2.first, val2.second);
0215   EXPECT_EQ(val, *it);
0216 #endif
0217 }
0218
0219 template <class V>
0220 using IfNotVoid = typename std::enable_if<!std::is_void<V>::value, V>::type;
0221
0222 // In openmap we chose not to return the iterator from erase because that's
0223 // more expensive. As such we adapt erase to return an iterator here.
0224 struct EraseFirst {
0225   template <class Map>
0226   auto operator()(Map* m, int) const
0227       -> IfNotVoid<decltype(m->erase(m->begin()))> {
0228     return m->erase(m->begin());
0229   }
0230   template <class Map>
0231   typename Map::iterator operator()(Map* m, ...) const {
0232     auto it = m->begin();
0233     m->erase(it++);
0234     return it;
0235   }
0236 };
0237
0238 TYPED_TEST_P(ModifiersTest, Erase) {
0239   using T = hash_internal::GeneratedType<TypeParam>;
0240   using std::get;
0241   std::vector<T> values;
0242   std::generate_n(std::back_inserter(values), 10,
0243                   hash_internal::Generator<T>());
0244   TypeParam m(values.begin(), values.end());
0245   ASSERT_THAT(items(m), ::testing::UnorderedElementsAreArray(values));
0246   auto& first = *m.begin();
0247   std::vector<T> values2;
0248   for (const auto& val : values)
0249     if (get<0>(val) != get<0>(first)) values2.push_back(val);
0250   auto it = EraseFirst()(&m, 0);
0251   ASSERT_TRUE(it != m.end());
0252   EXPECT_EQ(1, std::count(values2.begin(), values2.end(), *it));
0253   EXPECT_THAT(items(m), ::testing::UnorderedElementsAreArray(values2.begin(),
0254                                                              values2.end()));
0255 }
0256
0257 TYPED_TEST_P(ModifiersTest, EraseRange) {
0258   using T = hash_internal::GeneratedType<TypeParam>;
0259   std::vector<T> values;
0260   std::generate_n(std::back_inserter(values), 10,
0261                   hash_internal::Generator<T>());
0262   TypeParam m(values.begin(), values.end());
0263   ASSERT_THAT(items(m), ::testing::UnorderedElementsAreArray(values));
0264   auto it = m.erase(m.begin(), m.end());
0265   EXPECT_THAT(items(m), ::testing::UnorderedElementsAre());
0266   EXPECT_TRUE(it == m.end());
0267 }
0268
0269 TYPED_TEST_P(ModifiersTest, EraseKey) {
0270   using T = hash_internal::GeneratedType<TypeParam>;
0271   std::vector<T> values;
0272   std::generate_n(std::back_inserter(values), 10,
0273                   hash_internal::Generator<T>());
0274   TypeParam m(values.begin(), values.end());
0275   ASSERT_THAT(items(m), ::testing::UnorderedElementsAreArray(values));
0276   EXPECT_EQ(1, m.erase(values[0].first));
0277   EXPECT_EQ(0, std::count(m.begin(), m.end(), values[0]));
0278   EXPECT_THAT(items(m), ::testing::UnorderedElementsAreArray(values.begin() + 1,
0279                                                              values.end()));
0280 }
0281
0282 TYPED_TEST_P(ModifiersTest, Swap) {
0283   using T = hash_internal::GeneratedType<TypeParam>;
0284   std::vector<T> v1;
0285   std::vector<T> v2;
0286   std::generate_n(std::back_inserter(v1), 5, hash_internal::Generator<T>());
0287   std::generate_n(std::back_inserter(v2), 5, hash_internal::Generator<T>());
0288   TypeParam m1(v1.begin(), v1.end());
0289   TypeParam m2(v2.begin(), v2.end());
0290   EXPECT_THAT(items(m1), ::testing::UnorderedElementsAreArray(v1));
0291   EXPECT_THAT(items(m2), ::testing::UnorderedElementsAreArray(v2));
0292   m1.swap(m2);
0293   EXPECT_THAT(items(m1), ::testing::UnorderedElementsAreArray(v2));
0294   EXPECT_THAT(items(m2), ::testing::UnorderedElementsAreArray(v1));
0295 }
0296
0297 // TODO(alkis): Write tests for extract.
0298 // TODO(alkis): Write tests for merge.
0299
0300 REGISTER_TYPED_TEST_SUITE_P(ModifiersTest, Clear, Insert, InsertHint,
0301                             InsertRange, InsertWithinCapacity,
0302                             InsertRangeWithinCapacity, InsertOrAssign,
0303                             InsertOrAssignHint, Emplace, EmplaceHint,
0304                             TryEmplace, TryEmplaceHint, Erase, EraseRange,
0305                             EraseKey, Swap);
0306
0307 template <typename Type>
0308 struct is_unique_ptr : std::false_type {};
0309
0310 template <typename Type>
0311 struct is_unique_ptr<std::unique_ptr<Type>> : std::true_type {};
0312
0313 template <class UnordMap>
0314 class UniquePtrModifiersTest : public ::testing::Test {
0315  protected:
0316   UniquePtrModifiersTest() {
0317     static_assert(is_unique_ptr<typename UnordMap::mapped_type>::value,
0318                   "UniquePtrModifiersTyest may only be called with a "
0319                   "std::unique_ptr value type.");
0320   }
0321 };
0322
0323 GTEST_ALLOW_UNINSTANTIATED_PARAMETERIZED_TEST(UniquePtrModifiersTest);
0324
0325 TYPED_TEST_SUITE_P(UniquePtrModifiersTest);
0326
0327 // Test that we do not move from rvalue arguments if an insertion does not
0328 // happen.
0329 TYPED_TEST_P(UniquePtrModifiersTest, TryEmplace) {
0330 #ifdef UNORDERED_MAP_CXX17
0331   using T = hash_internal::GeneratedType<TypeParam>;
0332   using V = typename TypeParam::mapped_type;
0333   T val = hash_internal::Generator<T>()();
0334   TypeParam m;
0335   auto p = m.try_emplace(val.first, std::move(val.second));
0336   EXPECT_TRUE(p.second);
0337   // A moved from std::unique_ptr is guaranteed to be nullptr.
0338   EXPECT_EQ(val.second, nullptr);
0339   T val2 = {val.first, hash_internal::Generator<V>()()};
0340   p = m.try_emplace(val2.first, std::move(val2.second));
0341   EXPECT_FALSE(p.second);
0342   EXPECT_NE(val2.second, nullptr);
0343 #endif
0344 }
0345
0346 REGISTER_TYPED_TEST_SUITE_P(UniquePtrModifiersTest, TryEmplace);
0347
0348 }  // namespace container_internal
0349 ABSL_NAMESPACE_END
0350 }  // namespace absl
0351
0352 #endif  // ABSL_CONTAINER_INTERNAL_UNORDERED_MAP_MODIFIERS_TEST_H_