container/internal/unordered_set_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_SET_MODIFIERS_TEST_H_
0016 #define ABSL_CONTAINER_INTERNAL_UNORDERED_SET_MODIFIERS_TEST_H_
0017
0018 #include "gmock/gmock.h"
0019 #include "gtest/gtest.h"
0020 #include "absl/container/internal/hash_generator_testing.h"
0021 #include "absl/container/internal/hash_policy_testing.h"
0022
0023 namespace absl {
0024 ABSL_NAMESPACE_BEGIN
0025 namespace container_internal {
0026
0027 template <class UnordSet>
0028 class ModifiersTest : public ::testing::Test {};
0029
0030 TYPED_TEST_SUITE_P(ModifiersTest);
0031
0032 TYPED_TEST_P(ModifiersTest, Clear) {
0033   using T = hash_internal::GeneratedType<TypeParam>;
0034   std::vector<T> values;
0035   std::generate_n(std::back_inserter(values), 10,
0036                   hash_internal::Generator<T>());
0037   TypeParam m(values.begin(), values.end());
0038   ASSERT_THAT(keys(m), ::testing::UnorderedElementsAreArray(values));
0039   m.clear();
0040   EXPECT_THAT(keys(m), ::testing::UnorderedElementsAre());
0041   EXPECT_TRUE(m.empty());
0042 }
0043
0044 TYPED_TEST_P(ModifiersTest, Insert) {
0045   using T = hash_internal::GeneratedType<TypeParam>;
0046   T val = hash_internal::Generator<T>()();
0047   TypeParam m;
0048   auto p = m.insert(val);
0049   EXPECT_TRUE(p.second);
0050   EXPECT_EQ(val, *p.first);
0051   p = m.insert(val);
0052   EXPECT_FALSE(p.second);
0053 }
0054
0055 TYPED_TEST_P(ModifiersTest, InsertHint) {
0056   using T = hash_internal::GeneratedType<TypeParam>;
0057   T val = hash_internal::Generator<T>()();
0058   TypeParam m;
0059   auto it = m.insert(m.end(), val);
0060   EXPECT_TRUE(it != m.end());
0061   EXPECT_EQ(val, *it);
0062   it = m.insert(it, val);
0063   EXPECT_TRUE(it != m.end());
0064   EXPECT_EQ(val, *it);
0065 }
0066
0067 TYPED_TEST_P(ModifiersTest, InsertRange) {
0068   using T = hash_internal::GeneratedType<TypeParam>;
0069   std::vector<T> values;
0070   std::generate_n(std::back_inserter(values), 10,
0071                   hash_internal::Generator<T>());
0072   TypeParam m;
0073   m.insert(values.begin(), values.end());
0074   ASSERT_THAT(keys(m), ::testing::UnorderedElementsAreArray(values));
0075 }
0076
0077 TYPED_TEST_P(ModifiersTest, InsertWithinCapacity) {
0078   using T = hash_internal::GeneratedType<TypeParam>;
0079   T val = hash_internal::Generator<T>()();
0080   TypeParam m;
0081   m.reserve(10);
0082   const size_t original_capacity = m.bucket_count();
0083   m.insert(val);
0084   EXPECT_EQ(m.bucket_count(), original_capacity);
0085   m.insert(val);
0086   EXPECT_EQ(m.bucket_count(), original_capacity);
0087 }
0088
0089 TYPED_TEST_P(ModifiersTest, InsertRangeWithinCapacity) {
0090 #if !defined(__GLIBCXX__)
0091   using T = hash_internal::GeneratedType<TypeParam>;
0092   std::vector<T> base_values;
0093   std::generate_n(std::back_inserter(base_values), 10,
0094                   hash_internal::Generator<T>());
0095   std::vector<T> values;
0096   while (values.size() != 100) {
0097     values.insert(values.end(), base_values.begin(), base_values.end());
0098   }
0099   TypeParam m;
0100   m.reserve(10);
0101   const size_t original_capacity = m.bucket_count();
0102   m.insert(values.begin(), values.end());
0103   EXPECT_EQ(m.bucket_count(), original_capacity);
0104 #endif
0105 }
0106
0107 TYPED_TEST_P(ModifiersTest, Emplace) {
0108   using T = hash_internal::GeneratedType<TypeParam>;
0109   T val = hash_internal::Generator<T>()();
0110   TypeParam m;
0111   // TODO(alkis): We need a way to run emplace in a more meaningful way. Perhaps
0112   // with test traits/policy.
0113   auto p = m.emplace(val);
0114   EXPECT_TRUE(p.second);
0115   EXPECT_EQ(val, *p.first);
0116   p = m.emplace(val);
0117   EXPECT_FALSE(p.second);
0118   EXPECT_EQ(val, *p.first);
0119 }
0120
0121 TYPED_TEST_P(ModifiersTest, EmplaceHint) {
0122   using T = hash_internal::GeneratedType<TypeParam>;
0123   T val = hash_internal::Generator<T>()();
0124   TypeParam m;
0125   // TODO(alkis): We need a way to run emplace in a more meaningful way. Perhaps
0126   // with test traits/policy.
0127   auto it = m.emplace_hint(m.end(), val);
0128   EXPECT_EQ(val, *it);
0129   it = m.emplace_hint(it, val);
0130   EXPECT_EQ(val, *it);
0131 }
0132
0133 template <class V>
0134 using IfNotVoid = typename std::enable_if<!std::is_void<V>::value, V>::type;
0135
0136 // In openmap we chose not to return the iterator from erase because that's
0137 // more expensive. As such we adapt erase to return an iterator here.
0138 struct EraseFirst {
0139   template <class Map>
0140   auto operator()(Map* m, int) const
0141       -> IfNotVoid<decltype(m->erase(m->begin()))> {
0142     return m->erase(m->begin());
0143   }
0144   template <class Map>
0145   typename Map::iterator operator()(Map* m, ...) const {
0146     auto it = m->begin();
0147     m->erase(it++);
0148     return it;
0149   }
0150 };
0151
0152 TYPED_TEST_P(ModifiersTest, Erase) {
0153   using T = hash_internal::GeneratedType<TypeParam>;
0154   std::vector<T> values;
0155   std::generate_n(std::back_inserter(values), 10,
0156                   hash_internal::Generator<T>());
0157   TypeParam m(values.begin(), values.end());
0158   ASSERT_THAT(keys(m), ::testing::UnorderedElementsAreArray(values));
0159   std::vector<T> values2;
0160   for (const auto& val : values)
0161     if (val != *m.begin()) values2.push_back(val);
0162   auto it = EraseFirst()(&m, 0);
0163   ASSERT_TRUE(it != m.end());
0164   EXPECT_EQ(1, std::count(values2.begin(), values2.end(), *it));
0165   EXPECT_THAT(keys(m), ::testing::UnorderedElementsAreArray(values2.begin(),
0166                                                             values2.end()));
0167 }
0168
0169 TYPED_TEST_P(ModifiersTest, EraseRange) {
0170   using T = hash_internal::GeneratedType<TypeParam>;
0171   std::vector<T> values;
0172   std::generate_n(std::back_inserter(values), 10,
0173                   hash_internal::Generator<T>());
0174   TypeParam m(values.begin(), values.end());
0175   ASSERT_THAT(keys(m), ::testing::UnorderedElementsAreArray(values));
0176   auto it = m.erase(m.begin(), m.end());
0177   EXPECT_THAT(keys(m), ::testing::UnorderedElementsAre());
0178   EXPECT_TRUE(it == m.end());
0179 }
0180
0181 TYPED_TEST_P(ModifiersTest, EraseKey) {
0182   using T = hash_internal::GeneratedType<TypeParam>;
0183   std::vector<T> values;
0184   std::generate_n(std::back_inserter(values), 10,
0185                   hash_internal::Generator<T>());
0186   TypeParam m(values.begin(), values.end());
0187   ASSERT_THAT(keys(m), ::testing::UnorderedElementsAreArray(values));
0188   EXPECT_EQ(1, m.erase(values[0]));
0189   EXPECT_EQ(0, std::count(m.begin(), m.end(), values[0]));
0190   EXPECT_THAT(keys(m), ::testing::UnorderedElementsAreArray(values.begin() + 1,
0191                                                             values.end()));
0192 }
0193
0194 TYPED_TEST_P(ModifiersTest, Swap) {
0195   using T = hash_internal::GeneratedType<TypeParam>;
0196   std::vector<T> v1;
0197   std::vector<T> v2;
0198   std::generate_n(std::back_inserter(v1), 5, hash_internal::Generator<T>());
0199   std::generate_n(std::back_inserter(v2), 5, hash_internal::Generator<T>());
0200   TypeParam m1(v1.begin(), v1.end());
0201   TypeParam m2(v2.begin(), v2.end());
0202   EXPECT_THAT(keys(m1), ::testing::UnorderedElementsAreArray(v1));
0203   EXPECT_THAT(keys(m2), ::testing::UnorderedElementsAreArray(v2));
0204   m1.swap(m2);
0205   EXPECT_THAT(keys(m1), ::testing::UnorderedElementsAreArray(v2));
0206   EXPECT_THAT(keys(m2), ::testing::UnorderedElementsAreArray(v1));
0207 }
0208
0209 // TODO(alkis): Write tests for extract.
0210 // TODO(alkis): Write tests for merge.
0211
0212 REGISTER_TYPED_TEST_SUITE_P(ModifiersTest, Clear, Insert, InsertHint,
0213                             InsertRange, InsertWithinCapacity,
0214                             InsertRangeWithinCapacity, Emplace, EmplaceHint,
0215                             Erase, EraseRange, EraseKey, Swap);
0216
0217 }  // namespace container_internal
0218 ABSL_NAMESPACE_END
0219 }  // namespace absl
0220
0221 #endif  // ABSL_CONTAINER_INTERNAL_UNORDERED_SET_MODIFIERS_TEST_H_