node_hash_map_test.cc (11065B)
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 #include "absl/container/node_hash_map.h" 16 17 #include <cstddef> 18 #include <new> 19 #include <string> 20 #include <tuple> 21 #include <type_traits> 22 #include <utility> 23 #include <vector> 24 25 #include "gmock/gmock.h" 26 #include "gtest/gtest.h" 27 #include "absl/base/config.h" 28 #include "absl/container/internal/hash_policy_testing.h" 29 #include "absl/container/internal/tracked.h" 30 #include "absl/container/internal/unordered_map_constructor_test.h" 31 #include "absl/container/internal/unordered_map_lookup_test.h" 32 #include "absl/container/internal/unordered_map_members_test.h" 33 #include "absl/container/internal/unordered_map_modifiers_test.h" 34 35 namespace absl { 36 ABSL_NAMESPACE_BEGIN 37 namespace container_internal { 38 namespace { 39 40 using ::testing::Field; 41 using ::testing::IsEmpty; 42 using ::testing::Pair; 43 using ::testing::UnorderedElementsAre; 44 using ::testing::UnorderedElementsAreArray; 45 46 using MapTypes = ::testing::Types< 47 absl::node_hash_map<int, int, StatefulTestingHash, StatefulTestingEqual, 48 Alloc<std::pair<const int, int>>>, 49 absl::node_hash_map<std::string, std::string, StatefulTestingHash, 50 StatefulTestingEqual, 51 Alloc<std::pair<const std::string, std::string>>>>; 52 53 INSTANTIATE_TYPED_TEST_SUITE_P(NodeHashMap, ConstructorTest, MapTypes); 54 INSTANTIATE_TYPED_TEST_SUITE_P(NodeHashMap, LookupTest, MapTypes); 55 INSTANTIATE_TYPED_TEST_SUITE_P(NodeHashMap, MembersTest, MapTypes); 56 INSTANTIATE_TYPED_TEST_SUITE_P(NodeHashMap, ModifiersTest, MapTypes); 57 58 using M = absl::node_hash_map<std::string, Tracked<int>>; 59 60 TEST(NodeHashMap, Emplace) { 61 M m; 62 Tracked<int> t(53); 63 m.emplace("a", t); 64 ASSERT_EQ(0, t.num_moves()); 65 ASSERT_EQ(1, t.num_copies()); 66 67 m.emplace(std::string("a"), t); 68 ASSERT_EQ(0, t.num_moves()); 69 ASSERT_EQ(1, t.num_copies()); 70 71 std::string a("a"); 72 m.emplace(a, t); 73 ASSERT_EQ(0, t.num_moves()); 74 ASSERT_EQ(1, t.num_copies()); 75 76 const std::string ca("a"); 77 m.emplace(a, t); 78 ASSERT_EQ(0, t.num_moves()); 79 ASSERT_EQ(1, t.num_copies()); 80 81 m.emplace(std::make_pair("a", t)); 82 ASSERT_EQ(0, t.num_moves()); 83 ASSERT_EQ(2, t.num_copies()); 84 85 m.emplace(std::make_pair(std::string("a"), t)); 86 ASSERT_EQ(0, t.num_moves()); 87 ASSERT_EQ(3, t.num_copies()); 88 89 std::pair<std::string, Tracked<int>> p("a", t); 90 ASSERT_EQ(0, t.num_moves()); 91 ASSERT_EQ(4, t.num_copies()); 92 m.emplace(p); 93 ASSERT_EQ(0, t.num_moves()); 94 ASSERT_EQ(4, t.num_copies()); 95 96 const std::pair<std::string, Tracked<int>> cp("a", t); 97 ASSERT_EQ(0, t.num_moves()); 98 ASSERT_EQ(5, t.num_copies()); 99 m.emplace(cp); 100 ASSERT_EQ(0, t.num_moves()); 101 ASSERT_EQ(5, t.num_copies()); 102 103 std::pair<const std::string, Tracked<int>> pc("a", t); 104 ASSERT_EQ(0, t.num_moves()); 105 ASSERT_EQ(6, t.num_copies()); 106 m.emplace(pc); 107 ASSERT_EQ(0, t.num_moves()); 108 ASSERT_EQ(6, t.num_copies()); 109 110 const std::pair<const std::string, Tracked<int>> cpc("a", t); 111 ASSERT_EQ(0, t.num_moves()); 112 ASSERT_EQ(7, t.num_copies()); 113 m.emplace(cpc); 114 ASSERT_EQ(0, t.num_moves()); 115 ASSERT_EQ(7, t.num_copies()); 116 117 m.emplace(std::piecewise_construct, std::forward_as_tuple("a"), 118 std::forward_as_tuple(t)); 119 ASSERT_EQ(0, t.num_moves()); 120 ASSERT_EQ(7, t.num_copies()); 121 122 m.emplace(std::piecewise_construct, std::forward_as_tuple(std::string("a")), 123 std::forward_as_tuple(t)); 124 ASSERT_EQ(0, t.num_moves()); 125 ASSERT_EQ(7, t.num_copies()); 126 } 127 128 TEST(NodeHashMap, AssignRecursive) { 129 struct Tree { 130 // Verify that unordered_map<K, IncompleteType> can be instantiated. 131 absl::node_hash_map<int, Tree> children; 132 }; 133 Tree root; 134 const Tree& child = root.children.emplace().first->second; 135 // Verify that `lhs = rhs` doesn't read rhs after clearing lhs. 136 root = child; 137 } 138 139 TEST(FlatHashMap, MoveOnlyKey) { 140 struct Key { 141 Key() = default; 142 Key(Key&&) = default; 143 Key& operator=(Key&&) = default; 144 }; 145 struct Eq { 146 bool operator()(const Key&, const Key&) const { return true; } 147 }; 148 struct Hash { 149 size_t operator()(const Key&) const { return 0; } 150 }; 151 absl::node_hash_map<Key, int, Hash, Eq> m; 152 m[Key()]; 153 } 154 155 struct NonMovableKey { 156 explicit NonMovableKey(int i) : i(i) {} 157 NonMovableKey(NonMovableKey&&) = delete; 158 int i; 159 }; 160 struct NonMovableKeyHash { 161 using is_transparent = void; 162 size_t operator()(const NonMovableKey& k) const { return k.i; } 163 size_t operator()(int k) const { return k; } 164 }; 165 struct NonMovableKeyEq { 166 using is_transparent = void; 167 bool operator()(const NonMovableKey& a, const NonMovableKey& b) const { 168 return a.i == b.i; 169 } 170 bool operator()(const NonMovableKey& a, int b) const { return a.i == b; } 171 }; 172 173 TEST(NodeHashMap, MergeExtractInsert) { 174 absl::node_hash_map<NonMovableKey, int, NonMovableKeyHash, NonMovableKeyEq> 175 set1, set2; 176 set1.emplace(std::piecewise_construct, std::make_tuple(7), 177 std::make_tuple(-7)); 178 set1.emplace(std::piecewise_construct, std::make_tuple(17), 179 std::make_tuple(-17)); 180 181 set2.emplace(std::piecewise_construct, std::make_tuple(7), 182 std::make_tuple(-70)); 183 set2.emplace(std::piecewise_construct, std::make_tuple(19), 184 std::make_tuple(-190)); 185 186 auto Elem = [](int key, int value) { 187 return Pair(Field(&NonMovableKey::i, key), value); 188 }; 189 190 EXPECT_THAT(set1, UnorderedElementsAre(Elem(7, -7), Elem(17, -17))); 191 EXPECT_THAT(set2, UnorderedElementsAre(Elem(7, -70), Elem(19, -190))); 192 193 // NonMovableKey is neither copyable nor movable. We should still be able to 194 // move nodes around. 195 static_assert(!std::is_move_constructible<NonMovableKey>::value, ""); 196 set1.merge(set2); 197 198 EXPECT_THAT(set1, 199 UnorderedElementsAre(Elem(7, -7), Elem(17, -17), Elem(19, -190))); 200 EXPECT_THAT(set2, UnorderedElementsAre(Elem(7, -70))); 201 202 auto node = set1.extract(7); 203 EXPECT_TRUE(node); 204 EXPECT_EQ(node.key().i, 7); 205 EXPECT_EQ(node.mapped(), -7); 206 EXPECT_THAT(set1, UnorderedElementsAre(Elem(17, -17), Elem(19, -190))); 207 208 auto insert_result = set2.insert(std::move(node)); 209 EXPECT_FALSE(node); 210 EXPECT_FALSE(insert_result.inserted); 211 EXPECT_TRUE(insert_result.node); 212 EXPECT_EQ(insert_result.node.key().i, 7); 213 EXPECT_EQ(insert_result.node.mapped(), -7); 214 EXPECT_THAT(*insert_result.position, Elem(7, -70)); 215 EXPECT_THAT(set2, UnorderedElementsAre(Elem(7, -70))); 216 217 node = set1.extract(17); 218 EXPECT_TRUE(node); 219 EXPECT_EQ(node.key().i, 17); 220 EXPECT_EQ(node.mapped(), -17); 221 EXPECT_THAT(set1, UnorderedElementsAre(Elem(19, -190))); 222 223 node.mapped() = 23; 224 225 insert_result = set2.insert(std::move(node)); 226 EXPECT_FALSE(node); 227 EXPECT_TRUE(insert_result.inserted); 228 EXPECT_FALSE(insert_result.node); 229 EXPECT_THAT(*insert_result.position, Elem(17, 23)); 230 EXPECT_THAT(set2, UnorderedElementsAre(Elem(7, -70), Elem(17, 23))); 231 } 232 233 bool FirstIsEven(std::pair<const int, int> p) { return p.first % 2 == 0; } 234 235 TEST(NodeHashMap, EraseIf) { 236 // Erase all elements. 237 { 238 node_hash_map<int, int> s = {{1, 1}, {2, 2}, {3, 3}, {4, 4}, {5, 5}}; 239 EXPECT_EQ(erase_if(s, [](std::pair<const int, int>) { return true; }), 5); 240 EXPECT_THAT(s, IsEmpty()); 241 } 242 // Erase no elements. 243 { 244 node_hash_map<int, int> s = {{1, 1}, {2, 2}, {3, 3}, {4, 4}, {5, 5}}; 245 EXPECT_EQ(erase_if(s, [](std::pair<const int, int>) { return false; }), 0); 246 EXPECT_THAT(s, UnorderedElementsAre(Pair(1, 1), Pair(2, 2), Pair(3, 3), 247 Pair(4, 4), Pair(5, 5))); 248 } 249 // Erase specific elements. 250 { 251 node_hash_map<int, int> s = {{1, 1}, {2, 2}, {3, 3}, {4, 4}, {5, 5}}; 252 EXPECT_EQ(erase_if(s, 253 [](std::pair<const int, int> kvp) { 254 return kvp.first % 2 == 1; 255 }), 256 3); 257 EXPECT_THAT(s, UnorderedElementsAre(Pair(2, 2), Pair(4, 4))); 258 } 259 // Predicate is function reference. 260 { 261 node_hash_map<int, int> s = {{1, 1}, {2, 2}, {3, 3}, {4, 4}, {5, 5}}; 262 EXPECT_EQ(erase_if(s, FirstIsEven), 2); 263 EXPECT_THAT(s, UnorderedElementsAre(Pair(1, 1), Pair(3, 3), Pair(5, 5))); 264 } 265 // Predicate is function pointer. 266 { 267 node_hash_map<int, int> s = {{1, 1}, {2, 2}, {3, 3}, {4, 4}, {5, 5}}; 268 EXPECT_EQ(erase_if(s, &FirstIsEven), 2); 269 EXPECT_THAT(s, UnorderedElementsAre(Pair(1, 1), Pair(3, 3), Pair(5, 5))); 270 } 271 } 272 273 TEST(NodeHashMap, CForEach) { 274 node_hash_map<int, int> m; 275 std::vector<std::pair<int, int>> expected; 276 for (int i = 0; i < 100; ++i) { 277 { 278 SCOPED_TRACE("mutable object iteration"); 279 std::vector<std::pair<int, int>> v; 280 absl::container_internal::c_for_each_fast( 281 m, [&v](std::pair<const int, int>& p) { v.push_back(p); }); 282 EXPECT_THAT(v, UnorderedElementsAreArray(expected)); 283 } 284 { 285 SCOPED_TRACE("const object iteration"); 286 std::vector<std::pair<int, int>> v; 287 const node_hash_map<int, int>& cm = m; 288 absl::container_internal::c_for_each_fast( 289 cm, [&v](const std::pair<const int, int>& p) { v.push_back(p); }); 290 EXPECT_THAT(v, UnorderedElementsAreArray(expected)); 291 } 292 { 293 SCOPED_TRACE("const object iteration"); 294 std::vector<std::pair<int, int>> v; 295 absl::container_internal::c_for_each_fast( 296 node_hash_map<int, int>(m), 297 [&v](std::pair<const int, int>& p) { v.push_back(p); }); 298 EXPECT_THAT(v, UnorderedElementsAreArray(expected)); 299 } 300 m[i] = i; 301 expected.emplace_back(i, i); 302 } 303 } 304 305 TEST(NodeHashMap, CForEachMutate) { 306 node_hash_map<int, int> s; 307 std::vector<std::pair<int, int>> expected; 308 for (int i = 0; i < 100; ++i) { 309 std::vector<std::pair<int, int>> v; 310 absl::container_internal::c_for_each_fast( 311 s, [&v](std::pair<const int, int>& p) { 312 v.push_back(p); 313 p.second++; 314 }); 315 EXPECT_THAT(v, UnorderedElementsAreArray(expected)); 316 for (auto& p : expected) { 317 p.second++; 318 } 319 EXPECT_THAT(s, UnorderedElementsAreArray(expected)); 320 s[i] = i; 321 expected.emplace_back(i, i); 322 } 323 } 324 325 TEST(NodeHashMap, NodeHandleMutableKeyAccess) { 326 node_hash_map<std::string, std::string> map; 327 328 map["key1"] = "mapped"; 329 330 auto nh = map.extract(map.begin()); 331 nh.key().resize(3); 332 map.insert(std::move(nh)); 333 334 EXPECT_THAT(map, testing::ElementsAre(Pair("key", "mapped"))); 335 } 336 337 TEST(NodeHashMap, RecursiveTypeCompiles) { 338 struct RecursiveType { 339 node_hash_map<int, RecursiveType> m; 340 }; 341 RecursiveType t; 342 t.m[0] = RecursiveType{}; 343 } 344 345 } // namespace 346 } // namespace container_internal 347 ABSL_NAMESPACE_END 348 } // namespace absl