node_hash_map_test.cc
Go to the documentation of this file.
00001 // Copyright 2018 The Abseil Authors.
00002 //
00003 // Licensed under the Apache License, Version 2.0 (the "License");
00004 // you may not use this file except in compliance with the License.
00005 // You may obtain a copy of the License at
00006 //
00007 //      https://www.apache.org/licenses/LICENSE-2.0
00008 //
00009 // Unless required by applicable law or agreed to in writing, software
00010 // distributed under the License is distributed on an "AS IS" BASIS,
00011 // WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
00012 // See the License for the specific language governing permissions and
00013 // limitations under the License.
00014 
00015 #include "absl/container/node_hash_map.h"
00016 
00017 #include "absl/container/internal/tracked.h"
00018 #include "absl/container/internal/unordered_map_constructor_test.h"
00019 #include "absl/container/internal/unordered_map_lookup_test.h"
00020 #include "absl/container/internal/unordered_map_members_test.h"
00021 #include "absl/container/internal/unordered_map_modifiers_test.h"
00022 
00023 namespace absl {
00024 namespace container_internal {
00025 namespace {
00026 
00027 using ::testing::Field;
00028 using ::testing::Pair;
00029 using ::testing::UnorderedElementsAre;
00030 
00031 using MapTypes = ::testing::Types<
00032     absl::node_hash_map<int, int, StatefulTestingHash, StatefulTestingEqual,
00033                         Alloc<std::pair<const int, int>>>,
00034     absl::node_hash_map<std::string, std::string, StatefulTestingHash,
00035                         StatefulTestingEqual,
00036                         Alloc<std::pair<const std::string, std::string>>>>;
00037 
00038 INSTANTIATE_TYPED_TEST_SUITE_P(NodeHashMap, ConstructorTest, MapTypes);
00039 INSTANTIATE_TYPED_TEST_SUITE_P(NodeHashMap, LookupTest, MapTypes);
00040 INSTANTIATE_TYPED_TEST_SUITE_P(NodeHashMap, MembersTest, MapTypes);
00041 INSTANTIATE_TYPED_TEST_SUITE_P(NodeHashMap, ModifiersTest, MapTypes);
00042 
00043 using M = absl::node_hash_map<std::string, Tracked<int>>;
00044 
00045 TEST(NodeHashMap, Emplace) {
00046   M m;
00047   Tracked<int> t(53);
00048   m.emplace("a", t);
00049   ASSERT_EQ(0, t.num_moves());
00050   ASSERT_EQ(1, t.num_copies());
00051 
00052   m.emplace(std::string("a"), t);
00053   ASSERT_EQ(0, t.num_moves());
00054   ASSERT_EQ(1, t.num_copies());
00055 
00056   std::string a("a");
00057   m.emplace(a, t);
00058   ASSERT_EQ(0, t.num_moves());
00059   ASSERT_EQ(1, t.num_copies());
00060 
00061   const std::string ca("a");
00062   m.emplace(a, t);
00063   ASSERT_EQ(0, t.num_moves());
00064   ASSERT_EQ(1, t.num_copies());
00065 
00066   m.emplace(std::make_pair("a", t));
00067   ASSERT_EQ(0, t.num_moves());
00068   ASSERT_EQ(2, t.num_copies());
00069 
00070   m.emplace(std::make_pair(std::string("a"), t));
00071   ASSERT_EQ(0, t.num_moves());
00072   ASSERT_EQ(3, t.num_copies());
00073 
00074   std::pair<std::string, Tracked<int>> p("a", t);
00075   ASSERT_EQ(0, t.num_moves());
00076   ASSERT_EQ(4, t.num_copies());
00077   m.emplace(p);
00078   ASSERT_EQ(0, t.num_moves());
00079   ASSERT_EQ(4, t.num_copies());
00080 
00081   const std::pair<std::string, Tracked<int>> cp("a", t);
00082   ASSERT_EQ(0, t.num_moves());
00083   ASSERT_EQ(5, t.num_copies());
00084   m.emplace(cp);
00085   ASSERT_EQ(0, t.num_moves());
00086   ASSERT_EQ(5, t.num_copies());
00087 
00088   std::pair<const std::string, Tracked<int>> pc("a", t);
00089   ASSERT_EQ(0, t.num_moves());
00090   ASSERT_EQ(6, t.num_copies());
00091   m.emplace(pc);
00092   ASSERT_EQ(0, t.num_moves());
00093   ASSERT_EQ(6, t.num_copies());
00094 
00095   const std::pair<const std::string, Tracked<int>> cpc("a", t);
00096   ASSERT_EQ(0, t.num_moves());
00097   ASSERT_EQ(7, t.num_copies());
00098   m.emplace(cpc);
00099   ASSERT_EQ(0, t.num_moves());
00100   ASSERT_EQ(7, t.num_copies());
00101 
00102   m.emplace(std::piecewise_construct, std::forward_as_tuple("a"),
00103             std::forward_as_tuple(t));
00104   ASSERT_EQ(0, t.num_moves());
00105   ASSERT_EQ(7, t.num_copies());
00106 
00107   m.emplace(std::piecewise_construct, std::forward_as_tuple(std::string("a")),
00108             std::forward_as_tuple(t));
00109   ASSERT_EQ(0, t.num_moves());
00110   ASSERT_EQ(7, t.num_copies());
00111 }
00112 
00113 TEST(NodeHashMap, AssignRecursive) {
00114   struct Tree {
00115     // Verify that unordered_map<K, IncompleteType> can be instantiated.
00116     absl::node_hash_map<int, Tree> children;
00117   };
00118   Tree root;
00119   const Tree& child = root.children.emplace().first->second;
00120   // Verify that `lhs = rhs` doesn't read rhs after clearing lhs.
00121   root = child;
00122 }
00123 
00124 TEST(FlatHashMap, MoveOnlyKey) {
00125   struct Key {
00126     Key() = default;
00127     Key(Key&&) = default;
00128     Key& operator=(Key&&) = default;
00129   };
00130   struct Eq {
00131     bool operator()(const Key&, const Key&) const { return true; }
00132   };
00133   struct Hash {
00134     size_t operator()(const Key&) const { return 0; }
00135   };
00136   absl::node_hash_map<Key, int, Hash, Eq> m;
00137   m[Key()];
00138 }
00139 
00140 struct NonMovableKey {
00141   explicit NonMovableKey(int i) : i(i) {}
00142   NonMovableKey(NonMovableKey&&) = delete;
00143   int i;
00144 };
00145 struct NonMovableKeyHash {
00146   using is_transparent = void;
00147   size_t operator()(const NonMovableKey& k) const { return k.i; }
00148   size_t operator()(int k) const { return k; }
00149 };
00150 struct NonMovableKeyEq {
00151   using is_transparent = void;
00152   bool operator()(const NonMovableKey& a, const NonMovableKey& b) const {
00153     return a.i == b.i;
00154   }
00155   bool operator()(const NonMovableKey& a, int b) const { return a.i == b; }
00156 };
00157 
00158 TEST(NodeHashMap, MergeExtractInsert) {
00159   absl::node_hash_map<NonMovableKey, int, NonMovableKeyHash, NonMovableKeyEq>
00160       set1, set2;
00161   set1.emplace(std::piecewise_construct, std::make_tuple(7),
00162                std::make_tuple(-7));
00163   set1.emplace(std::piecewise_construct, std::make_tuple(17),
00164                std::make_tuple(-17));
00165 
00166   set2.emplace(std::piecewise_construct, std::make_tuple(7),
00167                std::make_tuple(-70));
00168   set2.emplace(std::piecewise_construct, std::make_tuple(19),
00169                std::make_tuple(-190));
00170 
00171   auto Elem = [](int key, int value) {
00172     return Pair(Field(&NonMovableKey::i, key), value);
00173   };
00174 
00175   EXPECT_THAT(set1, UnorderedElementsAre(Elem(7, -7), Elem(17, -17)));
00176   EXPECT_THAT(set2, UnorderedElementsAre(Elem(7, -70), Elem(19, -190)));
00177 
00178   // NonMovableKey is neither copyable nor movable. We should still be able to
00179   // move nodes around.
00180   static_assert(!std::is_move_constructible<NonMovableKey>::value, "");
00181   set1.merge(set2);
00182 
00183   EXPECT_THAT(set1,
00184               UnorderedElementsAre(Elem(7, -7), Elem(17, -17), Elem(19, -190)));
00185   EXPECT_THAT(set2, UnorderedElementsAre(Elem(7, -70)));
00186 
00187   auto node = set1.extract(7);
00188   EXPECT_TRUE(node);
00189   EXPECT_EQ(node.key().i, 7);
00190   EXPECT_EQ(node.mapped(), -7);
00191   EXPECT_THAT(set1, UnorderedElementsAre(Elem(17, -17), Elem(19, -190)));
00192 
00193   auto insert_result = set2.insert(std::move(node));
00194   EXPECT_FALSE(node);
00195   EXPECT_FALSE(insert_result.inserted);
00196   EXPECT_TRUE(insert_result.node);
00197   EXPECT_EQ(insert_result.node.key().i, 7);
00198   EXPECT_EQ(insert_result.node.mapped(), -7);
00199   EXPECT_THAT(*insert_result.position, Elem(7, -70));
00200   EXPECT_THAT(set2, UnorderedElementsAre(Elem(7, -70)));
00201 
00202   node = set1.extract(17);
00203   EXPECT_TRUE(node);
00204   EXPECT_EQ(node.key().i, 17);
00205   EXPECT_EQ(node.mapped(), -17);
00206   EXPECT_THAT(set1, UnorderedElementsAre(Elem(19, -190)));
00207 
00208   node.mapped() = 23;
00209 
00210   insert_result = set2.insert(std::move(node));
00211   EXPECT_FALSE(node);
00212   EXPECT_TRUE(insert_result.inserted);
00213   EXPECT_FALSE(insert_result.node);
00214   EXPECT_THAT(*insert_result.position, Elem(17, 23));
00215   EXPECT_THAT(set2, UnorderedElementsAre(Elem(7, -70), Elem(17, 23)));
00216 }
00217 
00218 }  // namespace
00219 }  // namespace container_internal
00220 }  // namespace absl


abseil_cpp
Author(s):
autogenerated on Wed Jun 19 2019 19:42:15