unordered_map_modifiers_test.h (12172B)
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_MODIFIERS_TEST_H_ 16 #define ABSL_CONTAINER_INTERNAL_UNORDERED_MAP_MODIFIERS_TEST_H_ 17 18 #include <memory> 19 20 #include "gmock/gmock.h" 21 #include "gtest/gtest.h" 22 #include "absl/container/internal/hash_generator_testing.h" 23 #include "absl/container/internal/hash_policy_testing.h" 24 25 namespace absl { 26 ABSL_NAMESPACE_BEGIN 27 namespace container_internal { 28 29 template <class UnordMap> 30 class ModifiersTest : public ::testing::Test {}; 31 32 TYPED_TEST_SUITE_P(ModifiersTest); 33 34 TYPED_TEST_P(ModifiersTest, Clear) { 35 using T = hash_internal::GeneratedType<TypeParam>; 36 std::vector<T> values; 37 std::generate_n(std::back_inserter(values), 10, 38 hash_internal::Generator<T>()); 39 TypeParam m(values.begin(), values.end()); 40 ASSERT_THAT(items(m), ::testing::UnorderedElementsAreArray(values)); 41 m.clear(); 42 EXPECT_THAT(items(m), ::testing::UnorderedElementsAre()); 43 EXPECT_TRUE(m.empty()); 44 } 45 46 TYPED_TEST_P(ModifiersTest, Insert) { 47 using T = hash_internal::GeneratedType<TypeParam>; 48 using V = typename TypeParam::mapped_type; 49 T val = hash_internal::Generator<T>()(); 50 TypeParam m; 51 auto p = m.insert(val); 52 EXPECT_TRUE(p.second); 53 EXPECT_EQ(val, *p.first); 54 T val2 = {val.first, hash_internal::Generator<V>()()}; 55 p = m.insert(val2); 56 EXPECT_FALSE(p.second); 57 EXPECT_EQ(val, *p.first); 58 } 59 60 TYPED_TEST_P(ModifiersTest, InsertHint) { 61 using T = hash_internal::GeneratedType<TypeParam>; 62 using V = typename TypeParam::mapped_type; 63 T val = hash_internal::Generator<T>()(); 64 TypeParam m; 65 auto it = m.insert(m.end(), val); 66 EXPECT_TRUE(it != m.end()); 67 EXPECT_EQ(val, *it); 68 T val2 = {val.first, hash_internal::Generator<V>()()}; 69 it = m.insert(it, val2); 70 EXPECT_TRUE(it != m.end()); 71 EXPECT_EQ(val, *it); 72 } 73 74 TYPED_TEST_P(ModifiersTest, InsertRange) { 75 using T = hash_internal::GeneratedType<TypeParam>; 76 std::vector<T> values; 77 std::generate_n(std::back_inserter(values), 10, 78 hash_internal::Generator<T>()); 79 TypeParam m; 80 m.insert(values.begin(), values.end()); 81 ASSERT_THAT(items(m), ::testing::UnorderedElementsAreArray(values)); 82 } 83 84 TYPED_TEST_P(ModifiersTest, InsertWithinCapacity) { 85 using T = hash_internal::GeneratedType<TypeParam>; 86 using V = typename TypeParam::mapped_type; 87 T val = hash_internal::Generator<T>()(); 88 TypeParam m; 89 m.reserve(10); 90 const size_t original_capacity = m.bucket_count(); 91 m.insert(val); 92 EXPECT_EQ(m.bucket_count(), original_capacity); 93 T val2 = {val.first, hash_internal::Generator<V>()()}; 94 m.insert(val2); 95 EXPECT_EQ(m.bucket_count(), original_capacity); 96 } 97 98 TYPED_TEST_P(ModifiersTest, InsertRangeWithinCapacity) { 99 #if !defined(__GLIBCXX__) 100 using T = hash_internal::GeneratedType<TypeParam>; 101 std::vector<T> base_values; 102 std::generate_n(std::back_inserter(base_values), 10, 103 hash_internal::Generator<T>()); 104 std::vector<T> values; 105 while (values.size() != 100) { 106 std::copy_n(base_values.begin(), 10, std::back_inserter(values)); 107 } 108 TypeParam m; 109 m.reserve(10); 110 const size_t original_capacity = m.bucket_count(); 111 m.insert(values.begin(), values.end()); 112 EXPECT_EQ(m.bucket_count(), original_capacity); 113 #endif 114 } 115 116 TYPED_TEST_P(ModifiersTest, InsertOrAssign) { 117 #ifdef UNORDERED_MAP_CXX17 118 using std::get; 119 using K = typename TypeParam::key_type; 120 using V = typename TypeParam::mapped_type; 121 K k = hash_internal::Generator<K>()(); 122 V val = hash_internal::Generator<V>()(); 123 TypeParam m; 124 auto p = m.insert_or_assign(k, val); 125 EXPECT_TRUE(p.second); 126 EXPECT_EQ(k, get<0>(*p.first)); 127 EXPECT_EQ(val, get<1>(*p.first)); 128 V val2 = hash_internal::Generator<V>()(); 129 p = m.insert_or_assign(k, val2); 130 EXPECT_FALSE(p.second); 131 EXPECT_EQ(k, get<0>(*p.first)); 132 EXPECT_EQ(val2, get<1>(*p.first)); 133 #endif 134 } 135 136 TYPED_TEST_P(ModifiersTest, InsertOrAssignHint) { 137 #ifdef UNORDERED_MAP_CXX17 138 using std::get; 139 using K = typename TypeParam::key_type; 140 using V = typename TypeParam::mapped_type; 141 K k = hash_internal::Generator<K>()(); 142 V val = hash_internal::Generator<V>()(); 143 TypeParam m; 144 auto it = m.insert_or_assign(m.end(), k, val); 145 EXPECT_TRUE(it != m.end()); 146 EXPECT_EQ(k, get<0>(*it)); 147 EXPECT_EQ(val, get<1>(*it)); 148 V val2 = hash_internal::Generator<V>()(); 149 it = m.insert_or_assign(it, k, val2); 150 EXPECT_EQ(k, get<0>(*it)); 151 EXPECT_EQ(val2, get<1>(*it)); 152 #endif 153 } 154 155 TYPED_TEST_P(ModifiersTest, Emplace) { 156 using T = hash_internal::GeneratedType<TypeParam>; 157 using V = typename TypeParam::mapped_type; 158 T val = hash_internal::Generator<T>()(); 159 TypeParam m; 160 // TODO(alkis): We need a way to run emplace in a more meaningful way. Perhaps 161 // with test traits/policy. 162 auto p = m.emplace(val); 163 EXPECT_TRUE(p.second); 164 EXPECT_EQ(val, *p.first); 165 T val2 = {val.first, hash_internal::Generator<V>()()}; 166 p = m.emplace(val2); 167 EXPECT_FALSE(p.second); 168 EXPECT_EQ(val, *p.first); 169 } 170 171 TYPED_TEST_P(ModifiersTest, EmplaceHint) { 172 using T = hash_internal::GeneratedType<TypeParam>; 173 using V = typename TypeParam::mapped_type; 174 T val = hash_internal::Generator<T>()(); 175 TypeParam m; 176 // TODO(alkis): We need a way to run emplace in a more meaningful way. Perhaps 177 // with test traits/policy. 178 auto it = m.emplace_hint(m.end(), val); 179 EXPECT_EQ(val, *it); 180 T val2 = {val.first, hash_internal::Generator<V>()()}; 181 it = m.emplace_hint(it, val2); 182 EXPECT_EQ(val, *it); 183 } 184 185 TYPED_TEST_P(ModifiersTest, TryEmplace) { 186 #ifdef UNORDERED_MAP_CXX17 187 using T = hash_internal::GeneratedType<TypeParam>; 188 using V = typename TypeParam::mapped_type; 189 T val = hash_internal::Generator<T>()(); 190 TypeParam m; 191 // TODO(alkis): We need a way to run emplace in a more meaningful way. Perhaps 192 // with test traits/policy. 193 auto p = m.try_emplace(val.first, val.second); 194 EXPECT_TRUE(p.second); 195 EXPECT_EQ(val, *p.first); 196 T val2 = {val.first, hash_internal::Generator<V>()()}; 197 p = m.try_emplace(val2.first, val2.second); 198 EXPECT_FALSE(p.second); 199 EXPECT_EQ(val, *p.first); 200 #endif 201 } 202 203 TYPED_TEST_P(ModifiersTest, TryEmplaceHint) { 204 #ifdef UNORDERED_MAP_CXX17 205 using T = hash_internal::GeneratedType<TypeParam>; 206 using V = typename TypeParam::mapped_type; 207 T val = hash_internal::Generator<T>()(); 208 TypeParam m; 209 // TODO(alkis): We need a way to run emplace in a more meaningful way. Perhaps 210 // with test traits/policy. 211 auto it = m.try_emplace(m.end(), val.first, val.second); 212 EXPECT_EQ(val, *it); 213 T val2 = {val.first, hash_internal::Generator<V>()()}; 214 it = m.try_emplace(it, val2.first, val2.second); 215 EXPECT_EQ(val, *it); 216 #endif 217 } 218 219 template <class V> 220 using IfNotVoid = typename std::enable_if<!std::is_void<V>::value, V>::type; 221 222 // In openmap we chose not to return the iterator from erase because that's 223 // more expensive. As such we adapt erase to return an iterator here. 224 struct EraseFirst { 225 template <class Map> 226 auto operator()(Map* m, int) const 227 -> IfNotVoid<decltype(m->erase(m->begin()))> { 228 return m->erase(m->begin()); 229 } 230 template <class Map> 231 typename Map::iterator operator()(Map* m, ...) const { 232 auto it = m->begin(); 233 m->erase(it++); 234 return it; 235 } 236 }; 237 238 TYPED_TEST_P(ModifiersTest, Erase) { 239 using T = hash_internal::GeneratedType<TypeParam>; 240 using std::get; 241 std::vector<T> values; 242 std::generate_n(std::back_inserter(values), 10, 243 hash_internal::Generator<T>()); 244 TypeParam m(values.begin(), values.end()); 245 ASSERT_THAT(items(m), ::testing::UnorderedElementsAreArray(values)); 246 auto& first = *m.begin(); 247 std::vector<T> values2; 248 for (const auto& val : values) 249 if (get<0>(val) != get<0>(first)) values2.push_back(val); 250 auto it = EraseFirst()(&m, 0); 251 ASSERT_TRUE(it != m.end()); 252 EXPECT_EQ(1, std::count(values2.begin(), values2.end(), *it)); 253 EXPECT_THAT(items(m), ::testing::UnorderedElementsAreArray(values2.begin(), 254 values2.end())); 255 } 256 257 TYPED_TEST_P(ModifiersTest, EraseRange) { 258 using T = hash_internal::GeneratedType<TypeParam>; 259 std::vector<T> values; 260 std::generate_n(std::back_inserter(values), 10, 261 hash_internal::Generator<T>()); 262 TypeParam m(values.begin(), values.end()); 263 ASSERT_THAT(items(m), ::testing::UnorderedElementsAreArray(values)); 264 auto it = m.erase(m.begin(), m.end()); 265 EXPECT_THAT(items(m), ::testing::UnorderedElementsAre()); 266 EXPECT_TRUE(it == m.end()); 267 } 268 269 TYPED_TEST_P(ModifiersTest, EraseKey) { 270 using T = hash_internal::GeneratedType<TypeParam>; 271 std::vector<T> values; 272 std::generate_n(std::back_inserter(values), 10, 273 hash_internal::Generator<T>()); 274 TypeParam m(values.begin(), values.end()); 275 ASSERT_THAT(items(m), ::testing::UnorderedElementsAreArray(values)); 276 EXPECT_EQ(1, m.erase(values[0].first)); 277 EXPECT_EQ(0, std::count(m.begin(), m.end(), values[0])); 278 EXPECT_THAT(items(m), ::testing::UnorderedElementsAreArray(values.begin() + 1, 279 values.end())); 280 } 281 282 TYPED_TEST_P(ModifiersTest, Swap) { 283 using T = hash_internal::GeneratedType<TypeParam>; 284 std::vector<T> v1; 285 std::vector<T> v2; 286 std::generate_n(std::back_inserter(v1), 5, hash_internal::Generator<T>()); 287 std::generate_n(std::back_inserter(v2), 5, hash_internal::Generator<T>()); 288 TypeParam m1(v1.begin(), v1.end()); 289 TypeParam m2(v2.begin(), v2.end()); 290 EXPECT_THAT(items(m1), ::testing::UnorderedElementsAreArray(v1)); 291 EXPECT_THAT(items(m2), ::testing::UnorderedElementsAreArray(v2)); 292 m1.swap(m2); 293 EXPECT_THAT(items(m1), ::testing::UnorderedElementsAreArray(v2)); 294 EXPECT_THAT(items(m2), ::testing::UnorderedElementsAreArray(v1)); 295 } 296 297 // TODO(alkis): Write tests for extract. 298 // TODO(alkis): Write tests for merge. 299 300 REGISTER_TYPED_TEST_SUITE_P(ModifiersTest, Clear, Insert, InsertHint, 301 InsertRange, InsertWithinCapacity, 302 InsertRangeWithinCapacity, InsertOrAssign, 303 InsertOrAssignHint, Emplace, EmplaceHint, 304 TryEmplace, TryEmplaceHint, Erase, EraseRange, 305 EraseKey, Swap); 306 307 template <typename Type> 308 struct is_unique_ptr : std::false_type {}; 309 310 template <typename Type> 311 struct is_unique_ptr<std::unique_ptr<Type>> : std::true_type {}; 312 313 template <class UnordMap> 314 class UniquePtrModifiersTest : public ::testing::Test { 315 protected: 316 UniquePtrModifiersTest() { 317 static_assert(is_unique_ptr<typename UnordMap::mapped_type>::value, 318 "UniquePtrModifiersTyest may only be called with a " 319 "std::unique_ptr value type."); 320 } 321 }; 322 323 GTEST_ALLOW_UNINSTANTIATED_PARAMETERIZED_TEST(UniquePtrModifiersTest); 324 325 TYPED_TEST_SUITE_P(UniquePtrModifiersTest); 326 327 // Test that we do not move from rvalue arguments if an insertion does not 328 // happen. 329 TYPED_TEST_P(UniquePtrModifiersTest, TryEmplace) { 330 #ifdef UNORDERED_MAP_CXX17 331 using T = hash_internal::GeneratedType<TypeParam>; 332 using V = typename TypeParam::mapped_type; 333 T val = hash_internal::Generator<T>()(); 334 TypeParam m; 335 auto p = m.try_emplace(val.first, std::move(val.second)); 336 EXPECT_TRUE(p.second); 337 // A moved from std::unique_ptr is guaranteed to be nullptr. 338 EXPECT_EQ(val.second, nullptr); 339 T val2 = {val.first, hash_internal::Generator<V>()()}; 340 p = m.try_emplace(val2.first, std::move(val2.second)); 341 EXPECT_FALSE(p.second); 342 EXPECT_NE(val2.second, nullptr); 343 #endif 344 } 345 346 REGISTER_TYPED_TEST_SUITE_P(UniquePtrModifiersTest, TryEmplace); 347 348 } // namespace container_internal 349 ABSL_NAMESPACE_END 350 } // namespace absl 351 352 #endif // ABSL_CONTAINER_INTERNAL_UNORDERED_MAP_MODIFIERS_TEST_H_