unordered_set_modifiers_test.h (7721B)
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_SET_MODIFIERS_TEST_H_ 16 #define ABSL_CONTAINER_INTERNAL_UNORDERED_SET_MODIFIERS_TEST_H_ 17 18 #include "gmock/gmock.h" 19 #include "gtest/gtest.h" 20 #include "absl/container/internal/hash_generator_testing.h" 21 #include "absl/container/internal/hash_policy_testing.h" 22 23 namespace absl { 24 ABSL_NAMESPACE_BEGIN 25 namespace container_internal { 26 27 template <class UnordSet> 28 class ModifiersTest : public ::testing::Test {}; 29 30 TYPED_TEST_SUITE_P(ModifiersTest); 31 32 TYPED_TEST_P(ModifiersTest, Clear) { 33 using T = hash_internal::GeneratedType<TypeParam>; 34 std::vector<T> values; 35 std::generate_n(std::back_inserter(values), 10, 36 hash_internal::Generator<T>()); 37 TypeParam m(values.begin(), values.end()); 38 ASSERT_THAT(keys(m), ::testing::UnorderedElementsAreArray(values)); 39 m.clear(); 40 EXPECT_THAT(keys(m), ::testing::UnorderedElementsAre()); 41 EXPECT_TRUE(m.empty()); 42 } 43 44 TYPED_TEST_P(ModifiersTest, Insert) { 45 using T = hash_internal::GeneratedType<TypeParam>; 46 T val = hash_internal::Generator<T>()(); 47 TypeParam m; 48 auto p = m.insert(val); 49 EXPECT_TRUE(p.second); 50 EXPECT_EQ(val, *p.first); 51 p = m.insert(val); 52 EXPECT_FALSE(p.second); 53 } 54 55 TYPED_TEST_P(ModifiersTest, InsertHint) { 56 using T = hash_internal::GeneratedType<TypeParam>; 57 T val = hash_internal::Generator<T>()(); 58 TypeParam m; 59 auto it = m.insert(m.end(), val); 60 EXPECT_TRUE(it != m.end()); 61 EXPECT_EQ(val, *it); 62 it = m.insert(it, val); 63 EXPECT_TRUE(it != m.end()); 64 EXPECT_EQ(val, *it); 65 } 66 67 TYPED_TEST_P(ModifiersTest, InsertRange) { 68 using T = hash_internal::GeneratedType<TypeParam>; 69 std::vector<T> values; 70 std::generate_n(std::back_inserter(values), 10, 71 hash_internal::Generator<T>()); 72 TypeParam m; 73 m.insert(values.begin(), values.end()); 74 ASSERT_THAT(keys(m), ::testing::UnorderedElementsAreArray(values)); 75 } 76 77 TYPED_TEST_P(ModifiersTest, InsertWithinCapacity) { 78 using T = hash_internal::GeneratedType<TypeParam>; 79 T val = hash_internal::Generator<T>()(); 80 TypeParam m; 81 m.reserve(10); 82 const size_t original_capacity = m.bucket_count(); 83 m.insert(val); 84 EXPECT_EQ(m.bucket_count(), original_capacity); 85 m.insert(val); 86 EXPECT_EQ(m.bucket_count(), original_capacity); 87 } 88 89 TYPED_TEST_P(ModifiersTest, InsertRangeWithinCapacity) { 90 #if !defined(__GLIBCXX__) 91 using T = hash_internal::GeneratedType<TypeParam>; 92 std::vector<T> base_values; 93 std::generate_n(std::back_inserter(base_values), 10, 94 hash_internal::Generator<T>()); 95 std::vector<T> values; 96 while (values.size() != 100) { 97 values.insert(values.end(), base_values.begin(), base_values.end()); 98 } 99 TypeParam m; 100 m.reserve(10); 101 const size_t original_capacity = m.bucket_count(); 102 m.insert(values.begin(), values.end()); 103 EXPECT_EQ(m.bucket_count(), original_capacity); 104 #endif 105 } 106 107 TYPED_TEST_P(ModifiersTest, Emplace) { 108 using T = hash_internal::GeneratedType<TypeParam>; 109 T val = hash_internal::Generator<T>()(); 110 TypeParam m; 111 // TODO(alkis): We need a way to run emplace in a more meaningful way. Perhaps 112 // with test traits/policy. 113 auto p = m.emplace(val); 114 EXPECT_TRUE(p.second); 115 EXPECT_EQ(val, *p.first); 116 p = m.emplace(val); 117 EXPECT_FALSE(p.second); 118 EXPECT_EQ(val, *p.first); 119 } 120 121 TYPED_TEST_P(ModifiersTest, EmplaceHint) { 122 using T = hash_internal::GeneratedType<TypeParam>; 123 T val = hash_internal::Generator<T>()(); 124 TypeParam m; 125 // TODO(alkis): We need a way to run emplace in a more meaningful way. Perhaps 126 // with test traits/policy. 127 auto it = m.emplace_hint(m.end(), val); 128 EXPECT_EQ(val, *it); 129 it = m.emplace_hint(it, val); 130 EXPECT_EQ(val, *it); 131 } 132 133 template <class V> 134 using IfNotVoid = typename std::enable_if<!std::is_void<V>::value, V>::type; 135 136 // In openmap we chose not to return the iterator from erase because that's 137 // more expensive. As such we adapt erase to return an iterator here. 138 struct EraseFirst { 139 template <class Map> 140 auto operator()(Map* m, int) const 141 -> IfNotVoid<decltype(m->erase(m->begin()))> { 142 return m->erase(m->begin()); 143 } 144 template <class Map> 145 typename Map::iterator operator()(Map* m, ...) const { 146 auto it = m->begin(); 147 m->erase(it++); 148 return it; 149 } 150 }; 151 152 TYPED_TEST_P(ModifiersTest, Erase) { 153 using T = hash_internal::GeneratedType<TypeParam>; 154 std::vector<T> values; 155 std::generate_n(std::back_inserter(values), 10, 156 hash_internal::Generator<T>()); 157 TypeParam m(values.begin(), values.end()); 158 ASSERT_THAT(keys(m), ::testing::UnorderedElementsAreArray(values)); 159 std::vector<T> values2; 160 for (const auto& val : values) 161 if (val != *m.begin()) values2.push_back(val); 162 auto it = EraseFirst()(&m, 0); 163 ASSERT_TRUE(it != m.end()); 164 EXPECT_EQ(1, std::count(values2.begin(), values2.end(), *it)); 165 EXPECT_THAT(keys(m), ::testing::UnorderedElementsAreArray(values2.begin(), 166 values2.end())); 167 } 168 169 TYPED_TEST_P(ModifiersTest, EraseRange) { 170 using T = hash_internal::GeneratedType<TypeParam>; 171 std::vector<T> values; 172 std::generate_n(std::back_inserter(values), 10, 173 hash_internal::Generator<T>()); 174 TypeParam m(values.begin(), values.end()); 175 ASSERT_THAT(keys(m), ::testing::UnorderedElementsAreArray(values)); 176 auto it = m.erase(m.begin(), m.end()); 177 EXPECT_THAT(keys(m), ::testing::UnorderedElementsAre()); 178 EXPECT_TRUE(it == m.end()); 179 } 180 181 TYPED_TEST_P(ModifiersTest, EraseKey) { 182 using T = hash_internal::GeneratedType<TypeParam>; 183 std::vector<T> values; 184 std::generate_n(std::back_inserter(values), 10, 185 hash_internal::Generator<T>()); 186 TypeParam m(values.begin(), values.end()); 187 ASSERT_THAT(keys(m), ::testing::UnorderedElementsAreArray(values)); 188 EXPECT_EQ(1, m.erase(values[0])); 189 EXPECT_EQ(0, std::count(m.begin(), m.end(), values[0])); 190 EXPECT_THAT(keys(m), ::testing::UnorderedElementsAreArray(values.begin() + 1, 191 values.end())); 192 } 193 194 TYPED_TEST_P(ModifiersTest, Swap) { 195 using T = hash_internal::GeneratedType<TypeParam>; 196 std::vector<T> v1; 197 std::vector<T> v2; 198 std::generate_n(std::back_inserter(v1), 5, hash_internal::Generator<T>()); 199 std::generate_n(std::back_inserter(v2), 5, hash_internal::Generator<T>()); 200 TypeParam m1(v1.begin(), v1.end()); 201 TypeParam m2(v2.begin(), v2.end()); 202 EXPECT_THAT(keys(m1), ::testing::UnorderedElementsAreArray(v1)); 203 EXPECT_THAT(keys(m2), ::testing::UnorderedElementsAreArray(v2)); 204 m1.swap(m2); 205 EXPECT_THAT(keys(m1), ::testing::UnorderedElementsAreArray(v2)); 206 EXPECT_THAT(keys(m2), ::testing::UnorderedElementsAreArray(v1)); 207 } 208 209 // TODO(alkis): Write tests for extract. 210 // TODO(alkis): Write tests for merge. 211 212 REGISTER_TYPED_TEST_SUITE_P(ModifiersTest, Clear, Insert, InsertHint, 213 InsertRange, InsertWithinCapacity, 214 InsertRangeWithinCapacity, Emplace, EmplaceHint, 215 Erase, EraseRange, EraseKey, Swap); 216 217 } // namespace container_internal 218 ABSL_NAMESPACE_END 219 } // namespace absl 220 221 #endif // ABSL_CONTAINER_INTERNAL_UNORDERED_SET_MODIFIERS_TEST_H_