node_hash_map_test.cc
Go to the documentation of this file.
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 "absl/container/internal/tracked.h"
18 #include "absl/container/internal/unordered_map_constructor_test.h"
19 #include "absl/container/internal/unordered_map_lookup_test.h"
20 #include "absl/container/internal/unordered_map_members_test.h"
21 #include "absl/container/internal/unordered_map_modifiers_test.h"
22 
23 namespace absl {
24 namespace container_internal {
25 namespace {
26 
27 using ::testing::Field;
28 using ::testing::Pair;
29 using ::testing::UnorderedElementsAre;
30 
31 using MapTypes = ::testing::Types<
32  absl::node_hash_map<int, int, StatefulTestingHash, StatefulTestingEqual,
33  Alloc<std::pair<const int, int>>>,
34  absl::node_hash_map<std::string, std::string, StatefulTestingHash,
35  StatefulTestingEqual,
36  Alloc<std::pair<const std::string, std::string>>>>;
37 
38 INSTANTIATE_TYPED_TEST_SUITE_P(NodeHashMap, ConstructorTest, MapTypes);
39 INSTANTIATE_TYPED_TEST_SUITE_P(NodeHashMap, LookupTest, MapTypes);
40 INSTANTIATE_TYPED_TEST_SUITE_P(NodeHashMap, MembersTest, MapTypes);
41 INSTANTIATE_TYPED_TEST_SUITE_P(NodeHashMap, ModifiersTest, MapTypes);
42 
43 using M = absl::node_hash_map<std::string, Tracked<int>>;
44 
45 TEST(NodeHashMap, Emplace) {
46  M m;
47  Tracked<int> t(53);
48  m.emplace("a", t);
49  ASSERT_EQ(0, t.num_moves());
50  ASSERT_EQ(1, t.num_copies());
51 
52  m.emplace(std::string("a"), t);
53  ASSERT_EQ(0, t.num_moves());
54  ASSERT_EQ(1, t.num_copies());
55 
56  std::string a("a");
57  m.emplace(a, t);
58  ASSERT_EQ(0, t.num_moves());
59  ASSERT_EQ(1, t.num_copies());
60 
61  const std::string ca("a");
62  m.emplace(a, t);
63  ASSERT_EQ(0, t.num_moves());
64  ASSERT_EQ(1, t.num_copies());
65 
66  m.emplace(std::make_pair("a", t));
67  ASSERT_EQ(0, t.num_moves());
68  ASSERT_EQ(2, t.num_copies());
69 
70  m.emplace(std::make_pair(std::string("a"), t));
71  ASSERT_EQ(0, t.num_moves());
72  ASSERT_EQ(3, t.num_copies());
73 
74  std::pair<std::string, Tracked<int>> p("a", t);
75  ASSERT_EQ(0, t.num_moves());
76  ASSERT_EQ(4, t.num_copies());
77  m.emplace(p);
78  ASSERT_EQ(0, t.num_moves());
79  ASSERT_EQ(4, t.num_copies());
80 
81  const std::pair<std::string, Tracked<int>> cp("a", t);
82  ASSERT_EQ(0, t.num_moves());
83  ASSERT_EQ(5, t.num_copies());
84  m.emplace(cp);
85  ASSERT_EQ(0, t.num_moves());
86  ASSERT_EQ(5, t.num_copies());
87 
88  std::pair<const std::string, Tracked<int>> pc("a", t);
89  ASSERT_EQ(0, t.num_moves());
90  ASSERT_EQ(6, t.num_copies());
91  m.emplace(pc);
92  ASSERT_EQ(0, t.num_moves());
93  ASSERT_EQ(6, t.num_copies());
94 
95  const std::pair<const std::string, Tracked<int>> cpc("a", t);
96  ASSERT_EQ(0, t.num_moves());
97  ASSERT_EQ(7, t.num_copies());
98  m.emplace(cpc);
99  ASSERT_EQ(0, t.num_moves());
100  ASSERT_EQ(7, t.num_copies());
101 
102  m.emplace(std::piecewise_construct, std::forward_as_tuple("a"),
103  std::forward_as_tuple(t));
104  ASSERT_EQ(0, t.num_moves());
105  ASSERT_EQ(7, t.num_copies());
106 
107  m.emplace(std::piecewise_construct, std::forward_as_tuple(std::string("a")),
108  std::forward_as_tuple(t));
109  ASSERT_EQ(0, t.num_moves());
110  ASSERT_EQ(7, t.num_copies());
111 }
112 
113 TEST(NodeHashMap, AssignRecursive) {
114  struct Tree {
115  // Verify that unordered_map<K, IncompleteType> can be instantiated.
116  absl::node_hash_map<int, Tree> children;
117  };
118  Tree root;
119  const Tree& child = root.children.emplace().first->second;
120  // Verify that `lhs = rhs` doesn't read rhs after clearing lhs.
121  root = child;
122 }
123 
124 TEST(FlatHashMap, MoveOnlyKey) {
125  struct Key {
126  Key() = default;
127  Key(Key&&) = default;
128  Key& operator=(Key&&) = default;
129  };
130  struct Eq {
131  bool operator()(const Key&, const Key&) const { return true; }
132  };
133  struct Hash {
134  size_t operator()(const Key&) const { return 0; }
135  };
136  absl::node_hash_map<Key, int, Hash, Eq> m;
137  m[Key()];
138 }
139 
140 struct NonMovableKey {
141  explicit NonMovableKey(int i) : i(i) {}
142  NonMovableKey(NonMovableKey&&) = delete;
143  int i;
144 };
145 struct NonMovableKeyHash {
146  using is_transparent = void;
147  size_t operator()(const NonMovableKey& k) const { return k.i; }
148  size_t operator()(int k) const { return k; }
149 };
150 struct NonMovableKeyEq {
151  using is_transparent = void;
152  bool operator()(const NonMovableKey& a, const NonMovableKey& b) const {
153  return a.i == b.i;
154  }
155  bool operator()(const NonMovableKey& a, int b) const { return a.i == b; }
156 };
157 
158 TEST(NodeHashMap, MergeExtractInsert) {
159  absl::node_hash_map<NonMovableKey, int, NonMovableKeyHash, NonMovableKeyEq>
160  set1, set2;
161  set1.emplace(std::piecewise_construct, std::make_tuple(7),
162  std::make_tuple(-7));
163  set1.emplace(std::piecewise_construct, std::make_tuple(17),
164  std::make_tuple(-17));
165 
166  set2.emplace(std::piecewise_construct, std::make_tuple(7),
167  std::make_tuple(-70));
168  set2.emplace(std::piecewise_construct, std::make_tuple(19),
169  std::make_tuple(-190));
170 
171  auto Elem = [](int key, int value) {
172  return Pair(Field(&NonMovableKey::i, key), value);
173  };
174 
175  EXPECT_THAT(set1, UnorderedElementsAre(Elem(7, -7), Elem(17, -17)));
176  EXPECT_THAT(set2, UnorderedElementsAre(Elem(7, -70), Elem(19, -190)));
177 
178  // NonMovableKey is neither copyable nor movable. We should still be able to
179  // move nodes around.
180  static_assert(!std::is_move_constructible<NonMovableKey>::value, "");
181  set1.merge(set2);
182 
183  EXPECT_THAT(set1,
184  UnorderedElementsAre(Elem(7, -7), Elem(17, -17), Elem(19, -190)));
185  EXPECT_THAT(set2, UnorderedElementsAre(Elem(7, -70)));
186 
187  auto node = set1.extract(7);
188  EXPECT_TRUE(node);
189  EXPECT_EQ(node.key().i, 7);
190  EXPECT_EQ(node.mapped(), -7);
191  EXPECT_THAT(set1, UnorderedElementsAre(Elem(17, -17), Elem(19, -190)));
192 
193  auto insert_result = set2.insert(std::move(node));
194  EXPECT_FALSE(node);
195  EXPECT_FALSE(insert_result.inserted);
196  EXPECT_TRUE(insert_result.node);
197  EXPECT_EQ(insert_result.node.key().i, 7);
198  EXPECT_EQ(insert_result.node.mapped(), -7);
199  EXPECT_THAT(*insert_result.position, Elem(7, -70));
200  EXPECT_THAT(set2, UnorderedElementsAre(Elem(7, -70)));
201 
202  node = set1.extract(17);
203  EXPECT_TRUE(node);
204  EXPECT_EQ(node.key().i, 17);
205  EXPECT_EQ(node.mapped(), -17);
206  EXPECT_THAT(set1, UnorderedElementsAre(Elem(19, -190)));
207 
208  node.mapped() = 23;
209 
210  insert_result = set2.insert(std::move(node));
211  EXPECT_FALSE(node);
212  EXPECT_TRUE(insert_result.inserted);
213  EXPECT_FALSE(insert_result.node);
214  EXPECT_THAT(*insert_result.position, Elem(17, 23));
215  EXPECT_THAT(set2, UnorderedElementsAre(Elem(7, -70), Elem(17, 23)));
216 }
217 
218 } // namespace
219 } // namespace container_internal
220 } // namespace absl
absl::container_internal::raw_hash_set< absl::container_internal::NodeHashMapPolicy< Key, Value >, Hash, Eq, Alloc >::emplace
std::pair< iterator, bool > emplace(Args &&... args)
Definition: raw_hash_set.h:1042
unordered_map_members_test.h
Hash
Hash
Definition: hash_function_defaults_test.cc:253
absl::TEST
TEST(NotificationTest, SanityTest)
Definition: notification_test.cc:125
i
int i
Definition: node_hash_map_test.cc:143
absl::node_hash_map
Definition: node_hash_map.h:101
absl::container_internal::raw_hash_set< absl::container_internal::NodeHashMapPolicy< Key, Value >, Hash, Eq, Alloc >::extract
node_type extract(const_iterator position)
Definition: raw_hash_set.h:1183
absl
Definition: algorithm.h:29
unordered_map_constructor_test.h
value
size_t value
Definition: flat_hash_map_test.cc:111
unordered_map_lookup_test.h
absl::container_internal::raw_hash_set< absl::container_internal::NodeHashMapPolicy< Key, Value >, Hash, Eq, Alloc >::merge
void merge(raw_hash_set< absl::container_internal::NodeHashMapPolicy< Key, Value >, H, E, Alloc > &src)
Definition: raw_hash_set.h:1167
unordered_map_modifiers_test.h
b
uint64_t b
Definition: layout_test.cc:50
node_hash_map.h
absl::container_internal::raw_hash_set< absl::container_internal::NodeHashMapPolicy< Key, Value >, Hash, Eq, Alloc >::insert
std::pair< iterator, bool > insert(T &&value)
Definition: raw_hash_set.h:944
absl::move
constexpr absl::remove_reference_t< T > && move(T &&t) noexcept
Definition: utility.h:219
a
int a
Definition: hash_policy_traits_test.cc:87

abseil_cpp
Author(s):
autogenerated on Mon Feb 28 2022 21:31:19