diff options
Diffstat (limited to 'third_party/abseil_cpp/absl/container/node_hash_map_test.cc')
| -rw-r--r-- | third_party/abseil_cpp/absl/container/node_hash_map_test.cc | 260 |
1 files changed, 260 insertions, 0 deletions
diff --git a/third_party/abseil_cpp/absl/container/node_hash_map_test.cc b/third_party/abseil_cpp/absl/container/node_hash_map_test.cc new file mode 100644 index 0000000000..5d74b814b5 --- /dev/null +++ b/third_party/abseil_cpp/absl/container/node_hash_map_test.cc @@ -0,0 +1,260 @@ +// 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}}; + erase_if(s, [](std::pair<const int, int>) { return true; }); + EXPECT_THAT(s, IsEmpty()); + } + // Erase no elements. + { + node_hash_map<int, int> s = {{1, 1}, {2, 2}, {3, 3}, {4, 4}, {5, 5}}; + erase_if(s, [](std::pair<const int, int>) { return false; }); + 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}}; + erase_if(s, + [](std::pair<const int, int> kvp) { return kvp.first % 2 == 1; }); + 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}}; + erase_if(s, FirstIsEven); + 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}}; + erase_if(s, &FirstIsEven); + EXPECT_THAT(s, UnorderedElementsAre(Pair(1, 1), Pair(3, 3), Pair(5, 5))); + } +} + +} // namespace +} // namespace container_internal +ABSL_NAMESPACE_END +} // namespace absl |