| // Copyright 2018 The Abseil Authors. |
| // |
| // Licensed under the Apache License, Version 2.0 (the "License"); |
| // you may not use this file except in compliance with the License. |
| // You may obtain a copy of the License at |
| // |
| // https://www.apache.org/licenses/LICENSE-2.0 |
| // |
| // Unless required by applicable law or agreed to in writing, software |
| // distributed under the License is distributed on an "AS IS" BASIS, |
| // WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. |
| // See the License for the specific language governing permissions and |
| // limitations under the License. |
| |
| #include "absl/container/node_hash_map.h" |
| |
| #include "absl/container/internal/tracked.h" |
| #include "absl/container/internal/unordered_map_constructor_test.h" |
| #include "absl/container/internal/unordered_map_lookup_test.h" |
| #include "absl/container/internal/unordered_map_members_test.h" |
| #include "absl/container/internal/unordered_map_modifiers_test.h" |
| |
| namespace absl { |
| ABSL_NAMESPACE_BEGIN |
| namespace container_internal { |
| namespace { |
| |
| using ::testing::Field; |
| using ::testing::IsEmpty; |
| using ::testing::Pair; |
| using ::testing::UnorderedElementsAre; |
| |
| using MapTypes = ::testing::Types< |
| absl::node_hash_map<int, int, StatefulTestingHash, StatefulTestingEqual, |
| Alloc<std::pair<const int, int>>>, |
| absl::node_hash_map<std::string, std::string, StatefulTestingHash, |
| StatefulTestingEqual, |
| Alloc<std::pair<const std::string, std::string>>>>; |
| |
| INSTANTIATE_TYPED_TEST_SUITE_P(NodeHashMap, ConstructorTest, MapTypes); |
| INSTANTIATE_TYPED_TEST_SUITE_P(NodeHashMap, LookupTest, MapTypes); |
| INSTANTIATE_TYPED_TEST_SUITE_P(NodeHashMap, MembersTest, MapTypes); |
| INSTANTIATE_TYPED_TEST_SUITE_P(NodeHashMap, ModifiersTest, MapTypes); |
| |
| using M = absl::node_hash_map<std::string, Tracked<int>>; |
| |
| TEST(NodeHashMap, Emplace) { |
| M m; |
| Tracked<int> t(53); |
| m.emplace("a", t); |
| ASSERT_EQ(0, t.num_moves()); |
| ASSERT_EQ(1, t.num_copies()); |
| |
| m.emplace(std::string("a"), t); |
| ASSERT_EQ(0, t.num_moves()); |
| ASSERT_EQ(1, t.num_copies()); |
| |
| std::string a("a"); |
| m.emplace(a, t); |
| ASSERT_EQ(0, t.num_moves()); |
| ASSERT_EQ(1, t.num_copies()); |
| |
| const std::string ca("a"); |
| m.emplace(a, t); |
| ASSERT_EQ(0, t.num_moves()); |
| ASSERT_EQ(1, t.num_copies()); |
| |
| m.emplace(std::make_pair("a", t)); |
| ASSERT_EQ(0, t.num_moves()); |
| ASSERT_EQ(2, t.num_copies()); |
| |
| m.emplace(std::make_pair(std::string("a"), t)); |
| ASSERT_EQ(0, t.num_moves()); |
| ASSERT_EQ(3, t.num_copies()); |
| |
| std::pair<std::string, Tracked<int>> p("a", t); |
| ASSERT_EQ(0, t.num_moves()); |
| ASSERT_EQ(4, t.num_copies()); |
| m.emplace(p); |
| ASSERT_EQ(0, t.num_moves()); |
| ASSERT_EQ(4, t.num_copies()); |
| |
| const std::pair<std::string, Tracked<int>> cp("a", t); |
| ASSERT_EQ(0, t.num_moves()); |
| ASSERT_EQ(5, t.num_copies()); |
| m.emplace(cp); |
| ASSERT_EQ(0, t.num_moves()); |
| ASSERT_EQ(5, t.num_copies()); |
| |
| std::pair<const std::string, Tracked<int>> pc("a", t); |
| ASSERT_EQ(0, t.num_moves()); |
| ASSERT_EQ(6, t.num_copies()); |
| m.emplace(pc); |
| ASSERT_EQ(0, t.num_moves()); |
| ASSERT_EQ(6, t.num_copies()); |
| |
| const std::pair<const std::string, Tracked<int>> cpc("a", t); |
| ASSERT_EQ(0, t.num_moves()); |
| ASSERT_EQ(7, t.num_copies()); |
| m.emplace(cpc); |
| ASSERT_EQ(0, t.num_moves()); |
| ASSERT_EQ(7, t.num_copies()); |
| |
| m.emplace(std::piecewise_construct, std::forward_as_tuple("a"), |
| std::forward_as_tuple(t)); |
| ASSERT_EQ(0, t.num_moves()); |
| ASSERT_EQ(7, t.num_copies()); |
| |
| m.emplace(std::piecewise_construct, std::forward_as_tuple(std::string("a")), |
| std::forward_as_tuple(t)); |
| ASSERT_EQ(0, t.num_moves()); |
| ASSERT_EQ(7, t.num_copies()); |
| } |
| |
| TEST(NodeHashMap, AssignRecursive) { |
| struct Tree { |
| // Verify that unordered_map<K, IncompleteType> can be instantiated. |
| absl::node_hash_map<int, Tree> children; |
| }; |
| Tree root; |
| const Tree& child = root.children.emplace().first->second; |
| // Verify that `lhs = rhs` doesn't read rhs after clearing lhs. |
| root = child; |
| } |
| |
| TEST(FlatHashMap, MoveOnlyKey) { |
| struct Key { |
| Key() = default; |
| Key(Key&&) = default; |
| Key& operator=(Key&&) = default; |
| }; |
| struct Eq { |
| bool operator()(const Key&, const Key&) const { return true; } |
| }; |
| struct Hash { |
| size_t operator()(const Key&) const { return 0; } |
| }; |
| absl::node_hash_map<Key, int, Hash, Eq> m; |
| m[Key()]; |
| } |
| |
| struct NonMovableKey { |
| explicit NonMovableKey(int i) : i(i) {} |
| NonMovableKey(NonMovableKey&&) = delete; |
| int i; |
| }; |
| struct NonMovableKeyHash { |
| using is_transparent = void; |
| size_t operator()(const NonMovableKey& k) const { return k.i; } |
| size_t operator()(int k) const { return k; } |
| }; |
| struct NonMovableKeyEq { |
| using is_transparent = void; |
| bool operator()(const NonMovableKey& a, const NonMovableKey& b) const { |
| return a.i == b.i; |
| } |
| bool operator()(const NonMovableKey& a, int b) const { return a.i == b; } |
| }; |
| |
| TEST(NodeHashMap, MergeExtractInsert) { |
| absl::node_hash_map<NonMovableKey, int, NonMovableKeyHash, NonMovableKeyEq> |
| set1, set2; |
| set1.emplace(std::piecewise_construct, std::make_tuple(7), |
| std::make_tuple(-7)); |
| set1.emplace(std::piecewise_construct, std::make_tuple(17), |
| std::make_tuple(-17)); |
| |
| set2.emplace(std::piecewise_construct, std::make_tuple(7), |
| std::make_tuple(-70)); |
| set2.emplace(std::piecewise_construct, std::make_tuple(19), |
| std::make_tuple(-190)); |
| |
| auto Elem = [](int key, int value) { |
| return Pair(Field(&NonMovableKey::i, key), value); |
| }; |
| |
| EXPECT_THAT(set1, UnorderedElementsAre(Elem(7, -7), Elem(17, -17))); |
| EXPECT_THAT(set2, UnorderedElementsAre(Elem(7, -70), Elem(19, -190))); |
| |
| // NonMovableKey is neither copyable nor movable. We should still be able to |
| // move nodes around. |
| static_assert(!std::is_move_constructible<NonMovableKey>::value, ""); |
| set1.merge(set2); |
| |
| EXPECT_THAT(set1, |
| UnorderedElementsAre(Elem(7, -7), Elem(17, -17), Elem(19, -190))); |
| EXPECT_THAT(set2, UnorderedElementsAre(Elem(7, -70))); |
| |
| auto node = set1.extract(7); |
| EXPECT_TRUE(node); |
| EXPECT_EQ(node.key().i, 7); |
| EXPECT_EQ(node.mapped(), -7); |
| EXPECT_THAT(set1, UnorderedElementsAre(Elem(17, -17), Elem(19, -190))); |
| |
| auto insert_result = set2.insert(std::move(node)); |
| EXPECT_FALSE(node); |
| EXPECT_FALSE(insert_result.inserted); |
| EXPECT_TRUE(insert_result.node); |
| EXPECT_EQ(insert_result.node.key().i, 7); |
| EXPECT_EQ(insert_result.node.mapped(), -7); |
| EXPECT_THAT(*insert_result.position, Elem(7, -70)); |
| EXPECT_THAT(set2, UnorderedElementsAre(Elem(7, -70))); |
| |
| node = set1.extract(17); |
| EXPECT_TRUE(node); |
| EXPECT_EQ(node.key().i, 17); |
| EXPECT_EQ(node.mapped(), -17); |
| EXPECT_THAT(set1, UnorderedElementsAre(Elem(19, -190))); |
| |
| node.mapped() = 23; |
| |
| insert_result = set2.insert(std::move(node)); |
| EXPECT_FALSE(node); |
| EXPECT_TRUE(insert_result.inserted); |
| EXPECT_FALSE(insert_result.node); |
| EXPECT_THAT(*insert_result.position, Elem(17, 23)); |
| EXPECT_THAT(set2, UnorderedElementsAre(Elem(7, -70), Elem(17, 23))); |
| } |
| |
| bool FirstIsEven(std::pair<const int, int> p) { return p.first % 2 == 0; } |
| |
| TEST(NodeHashMap, EraseIf) { |
| // Erase all elements. |
| { |
| node_hash_map<int, int> s = {{1, 1}, {2, 2}, {3, 3}, {4, 4}, {5, 5}}; |
| EXPECT_EQ(erase_if(s, [](std::pair<const int, int>) { return true; }), 5); |
| EXPECT_THAT(s, IsEmpty()); |
| } |
| // Erase no elements. |
| { |
| node_hash_map<int, int> s = {{1, 1}, {2, 2}, {3, 3}, {4, 4}, {5, 5}}; |
| EXPECT_EQ(erase_if(s, [](std::pair<const int, int>) { return false; }), 0); |
| EXPECT_THAT(s, UnorderedElementsAre(Pair(1, 1), Pair(2, 2), Pair(3, 3), |
| Pair(4, 4), Pair(5, 5))); |
| } |
| // Erase specific elements. |
| { |
| node_hash_map<int, int> s = {{1, 1}, {2, 2}, {3, 3}, {4, 4}, {5, 5}}; |
| EXPECT_EQ(erase_if(s, |
| [](std::pair<const int, int> kvp) { |
| return kvp.first % 2 == 1; |
| }), |
| 3); |
| EXPECT_THAT(s, UnorderedElementsAre(Pair(2, 2), Pair(4, 4))); |
| } |
| // Predicate is function reference. |
| { |
| node_hash_map<int, int> s = {{1, 1}, {2, 2}, {3, 3}, {4, 4}, {5, 5}}; |
| EXPECT_EQ(erase_if(s, FirstIsEven), 2); |
| EXPECT_THAT(s, UnorderedElementsAre(Pair(1, 1), Pair(3, 3), Pair(5, 5))); |
| } |
| // Predicate is function pointer. |
| { |
| node_hash_map<int, int> s = {{1, 1}, {2, 2}, {3, 3}, {4, 4}, {5, 5}}; |
| EXPECT_EQ(erase_if(s, &FirstIsEven), 2); |
| EXPECT_THAT(s, UnorderedElementsAre(Pair(1, 1), Pair(3, 3), Pair(5, 5))); |
| } |
| } |
| |
| // This test requires std::launder for mutable key access in node handles. |
| #if defined(__cpp_lib_launder) && __cpp_lib_launder >= 201606 |
| TEST(NodeHashMap, NodeHandleMutableKeyAccess) { |
| node_hash_map<std::string, std::string> map; |
| |
| map["key1"] = "mapped"; |
| |
| auto nh = map.extract(map.begin()); |
| nh.key().resize(3); |
| map.insert(std::move(nh)); |
| |
| EXPECT_THAT(map, testing::ElementsAre(Pair("key", "mapped"))); |
| } |
| #endif |
| |
| } // namespace |
| } // namespace container_internal |
| ABSL_NAMESPACE_END |
| } // namespace absl |