abseil-cpp/absl/container/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 ABSL_NAMESPACE_BEGIN
25 namespace container_internal {
26 namespace {
27 
28 using ::testing::Field;
29 using ::testing::IsEmpty;
30 using ::testing::Pair;
31 using ::testing::UnorderedElementsAre;
32 
33 using MapTypes = ::testing::Types<
34  absl::node_hash_map<int, int, StatefulTestingHash, StatefulTestingEqual,
35  Alloc<std::pair<const int, int>>>,
36  absl::node_hash_map<std::string, std::string, StatefulTestingHash,
37  StatefulTestingEqual,
38  Alloc<std::pair<const std::string, std::string>>>>;
39 
40 INSTANTIATE_TYPED_TEST_SUITE_P(NodeHashMap, ConstructorTest, MapTypes);
41 INSTANTIATE_TYPED_TEST_SUITE_P(NodeHashMap, LookupTest, MapTypes);
42 INSTANTIATE_TYPED_TEST_SUITE_P(NodeHashMap, MembersTest, MapTypes);
43 INSTANTIATE_TYPED_TEST_SUITE_P(NodeHashMap, ModifiersTest, MapTypes);
44 
45 using M = absl::node_hash_map<std::string, Tracked<int>>;
46 
47 TEST(NodeHashMap, Emplace) {
48  M m;
49  Tracked<int> t(53);
50  m.emplace("a", t);
51  ASSERT_EQ(0, t.num_moves());
52  ASSERT_EQ(1, t.num_copies());
53 
54  m.emplace(std::string("a"), t);
55  ASSERT_EQ(0, t.num_moves());
56  ASSERT_EQ(1, t.num_copies());
57 
58  std::string a("a");
59  m.emplace(a, t);
60  ASSERT_EQ(0, t.num_moves());
61  ASSERT_EQ(1, t.num_copies());
62 
63  const std::string ca("a");
64  m.emplace(a, t);
65  ASSERT_EQ(0, t.num_moves());
66  ASSERT_EQ(1, t.num_copies());
67 
68  m.emplace(std::make_pair("a", t));
69  ASSERT_EQ(0, t.num_moves());
70  ASSERT_EQ(2, t.num_copies());
71 
72  m.emplace(std::make_pair(std::string("a"), t));
73  ASSERT_EQ(0, t.num_moves());
74  ASSERT_EQ(3, t.num_copies());
75 
76  std::pair<std::string, Tracked<int>> p("a", t);
77  ASSERT_EQ(0, t.num_moves());
78  ASSERT_EQ(4, t.num_copies());
79  m.emplace(p);
80  ASSERT_EQ(0, t.num_moves());
81  ASSERT_EQ(4, t.num_copies());
82 
83  const std::pair<std::string, Tracked<int>> cp("a", t);
84  ASSERT_EQ(0, t.num_moves());
85  ASSERT_EQ(5, t.num_copies());
86  m.emplace(cp);
87  ASSERT_EQ(0, t.num_moves());
88  ASSERT_EQ(5, t.num_copies());
89 
90  std::pair<const std::string, Tracked<int>> pc("a", t);
91  ASSERT_EQ(0, t.num_moves());
92  ASSERT_EQ(6, t.num_copies());
93  m.emplace(pc);
94  ASSERT_EQ(0, t.num_moves());
95  ASSERT_EQ(6, t.num_copies());
96 
97  const std::pair<const std::string, Tracked<int>> cpc("a", t);
98  ASSERT_EQ(0, t.num_moves());
99  ASSERT_EQ(7, t.num_copies());
100  m.emplace(cpc);
101  ASSERT_EQ(0, t.num_moves());
102  ASSERT_EQ(7, t.num_copies());
103 
104  m.emplace(std::piecewise_construct, std::forward_as_tuple("a"),
105  std::forward_as_tuple(t));
106  ASSERT_EQ(0, t.num_moves());
107  ASSERT_EQ(7, t.num_copies());
108 
109  m.emplace(std::piecewise_construct, std::forward_as_tuple(std::string("a")),
110  std::forward_as_tuple(t));
111  ASSERT_EQ(0, t.num_moves());
112  ASSERT_EQ(7, t.num_copies());
113 }
114 
115 TEST(NodeHashMap, AssignRecursive) {
116  struct Tree {
117  // Verify that unordered_map<K, IncompleteType> can be instantiated.
118  absl::node_hash_map<int, Tree> children;
119  };
120  Tree root;
121  const Tree& child = root.children.emplace().first->second;
122  // Verify that `lhs = rhs` doesn't read rhs after clearing lhs.
123  root = child;
124 }
125 
126 TEST(FlatHashMap, MoveOnlyKey) {
127  struct Key {
128  Key() = default;
129  Key(Key&&) = default;
130  Key& operator=(Key&&) = default;
131  };
132  struct Eq {
133  bool operator()(const Key&, const Key&) const { return true; }
134  };
135  struct Hash {
136  size_t operator()(const Key&) const { return 0; }
137  };
138  absl::node_hash_map<Key, int, Hash, Eq> m;
139  m[Key()];
140 }
141 
142 struct NonMovableKey {
143  explicit NonMovableKey(int i) : i(i) {}
144  NonMovableKey(NonMovableKey&&) = delete;
145  int i;
146 };
147 struct NonMovableKeyHash {
148  using is_transparent = void;
149  size_t operator()(const NonMovableKey& k) const { return k.i; }
150  size_t operator()(int k) const { return k; }
151 };
152 struct NonMovableKeyEq {
153  using is_transparent = void;
154  bool operator()(const NonMovableKey& a, const NonMovableKey& b) const {
155  return a.i == b.i;
156  }
157  bool operator()(const NonMovableKey& a, int b) const { return a.i == b; }
158 };
159 
160 TEST(NodeHashMap, MergeExtractInsert) {
161  absl::node_hash_map<NonMovableKey, int, NonMovableKeyHash, NonMovableKeyEq>
162  set1, set2;
163  set1.emplace(std::piecewise_construct, std::make_tuple(7),
164  std::make_tuple(-7));
165  set1.emplace(std::piecewise_construct, std::make_tuple(17),
166  std::make_tuple(-17));
167 
168  set2.emplace(std::piecewise_construct, std::make_tuple(7),
169  std::make_tuple(-70));
170  set2.emplace(std::piecewise_construct, std::make_tuple(19),
171  std::make_tuple(-190));
172 
173  auto Elem = [](int key, int value) {
174  return Pair(Field(&NonMovableKey::i, key), value);
175  };
176 
177  EXPECT_THAT(set1, UnorderedElementsAre(Elem(7, -7), Elem(17, -17)));
178  EXPECT_THAT(set2, UnorderedElementsAre(Elem(7, -70), Elem(19, -190)));
179 
180  // NonMovableKey is neither copyable nor movable. We should still be able to
181  // move nodes around.
182  static_assert(!std::is_move_constructible<NonMovableKey>::value, "");
183  set1.merge(set2);
184 
185  EXPECT_THAT(set1,
186  UnorderedElementsAre(Elem(7, -7), Elem(17, -17), Elem(19, -190)));
187  EXPECT_THAT(set2, UnorderedElementsAre(Elem(7, -70)));
188 
189  auto node = set1.extract(7);
190  EXPECT_TRUE(node);
191  EXPECT_EQ(node.key().i, 7);
192  EXPECT_EQ(node.mapped(), -7);
193  EXPECT_THAT(set1, UnorderedElementsAre(Elem(17, -17), Elem(19, -190)));
194 
195  auto insert_result = set2.insert(std::move(node));
196  EXPECT_FALSE(node);
197  EXPECT_FALSE(insert_result.inserted);
198  EXPECT_TRUE(insert_result.node);
199  EXPECT_EQ(insert_result.node.key().i, 7);
200  EXPECT_EQ(insert_result.node.mapped(), -7);
201  EXPECT_THAT(*insert_result.position, Elem(7, -70));
202  EXPECT_THAT(set2, UnorderedElementsAre(Elem(7, -70)));
203 
204  node = set1.extract(17);
205  EXPECT_TRUE(node);
206  EXPECT_EQ(node.key().i, 17);
207  EXPECT_EQ(node.mapped(), -17);
208  EXPECT_THAT(set1, UnorderedElementsAre(Elem(19, -190)));
209 
210  node.mapped() = 23;
211 
212  insert_result = set2.insert(std::move(node));
213  EXPECT_FALSE(node);
214  EXPECT_TRUE(insert_result.inserted);
215  EXPECT_FALSE(insert_result.node);
216  EXPECT_THAT(*insert_result.position, Elem(17, 23));
217  EXPECT_THAT(set2, UnorderedElementsAre(Elem(7, -70), Elem(17, 23)));
218 }
219 
220 bool FirstIsEven(std::pair<const int, int> p) { return p.first % 2 == 0; }
221 
222 TEST(NodeHashMap, EraseIf) {
223  // Erase all elements.
224  {
225  node_hash_map<int, int> s = {{1, 1}, {2, 2}, {3, 3}, {4, 4}, {5, 5}};
226  EXPECT_EQ(erase_if(s, [](std::pair<const int, int>) { return true; }), 5);
227  EXPECT_THAT(s, IsEmpty());
228  }
229  // Erase no elements.
230  {
231  node_hash_map<int, int> s = {{1, 1}, {2, 2}, {3, 3}, {4, 4}, {5, 5}};
232  EXPECT_EQ(erase_if(s, [](std::pair<const int, int>) { return false; }), 0);
233  EXPECT_THAT(s, UnorderedElementsAre(Pair(1, 1), Pair(2, 2), Pair(3, 3),
234  Pair(4, 4), Pair(5, 5)));
235  }
236  // Erase specific 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,
240  [](std::pair<const int, int> kvp) {
241  return kvp.first % 2 == 1;
242  }),
243  3);
244  EXPECT_THAT(s, UnorderedElementsAre(Pair(2, 2), Pair(4, 4)));
245  }
246  // Predicate is function reference.
247  {
248  node_hash_map<int, int> s = {{1, 1}, {2, 2}, {3, 3}, {4, 4}, {5, 5}};
249  EXPECT_EQ(erase_if(s, FirstIsEven), 2);
250  EXPECT_THAT(s, UnorderedElementsAre(Pair(1, 1), Pair(3, 3), Pair(5, 5)));
251  }
252  // Predicate is function pointer.
253  {
254  node_hash_map<int, int> s = {{1, 1}, {2, 2}, {3, 3}, {4, 4}, {5, 5}};
255  EXPECT_EQ(erase_if(s, &FirstIsEven), 2);
256  EXPECT_THAT(s, UnorderedElementsAre(Pair(1, 1), Pair(3, 3), Pair(5, 5)));
257  }
258 }
259 
260 // This test requires std::launder for mutable key access in node handles.
261 #if defined(__cpp_lib_launder) && __cpp_lib_launder >= 201606
262 TEST(NodeHashMap, NodeHandleMutableKeyAccess) {
263  node_hash_map<std::string, std::string> map;
264 
265  map["key1"] = "mapped";
266 
267  auto nh = map.extract(map.begin());
268  nh.key().resize(3);
269  map.insert(std::move(nh));
270 
271  EXPECT_THAT(map, testing::ElementsAre(Pair("key", "mapped")));
272 }
273 #endif
274 
275 } // namespace
276 } // namespace container_internal
277 ABSL_NAMESPACE_END
278 } // namespace absl
EXPECT_FALSE
#define EXPECT_FALSE(condition)
Definition: bloaty/third_party/googletest/googletest/include/gtest/gtest.h:1970
Hash
Hash
Definition: abseil-cpp/absl/container/internal/hash_function_defaults_test.cc:339
EXPECT_THAT
#define EXPECT_THAT(value, matcher)
std::tr1::make_tuple
tuple make_tuple()
Definition: cares/cares/test/gmock-1.8.0/gtest/gtest.h:1619
testing::internal::string
::std::string string
Definition: bloaty/third_party/protobuf/third_party/googletest/googletest/include/gtest/internal/gtest-port.h:881
absl::node_hash_map
Definition: abseil-cpp/absl/container/node_hash_map.h:107
absl::TEST
TEST(NotificationTest, SanityTest)
Definition: abseil-cpp/absl/synchronization/notification_test.cc:126
absl::FormatConversionChar::s
@ s
a
int a
Definition: abseil-cpp/absl/container/internal/hash_policy_traits_test.cc:88
xds_manager.p
p
Definition: xds_manager.py:60
ABSL_NAMESPACE_END
#define ABSL_NAMESPACE_END
Definition: third_party/abseil-cpp/absl/base/config.h:171
setup.k
k
Definition: third_party/bloaty/third_party/capstone/bindings/python/setup.py:42
map
zval * map
Definition: php/ext/google/protobuf/encode_decode.c:480
EXPECT_EQ
#define EXPECT_EQ(a, b)
Definition: iomgr/time_averaged_stats_test.cc:27
testing::ElementsAre
internal::ElementsAreMatcher< ::testing::tuple<> > ElementsAre()
Definition: cares/cares/test/gmock-1.8.0/gmock/gmock.h:13040
testing::internal::ProxyTypeList
Definition: googletest/googletest/include/gtest/internal/gtest-type-util.h:155
i
int i
Definition: abseil-cpp/absl/container/node_hash_map_test.cc:145
ABSL_NAMESPACE_BEGIN
#define ABSL_NAMESPACE_BEGIN
Definition: third_party/abseil-cpp/absl/base/config.h:170
xds_interop_client.int
int
Definition: xds_interop_client.py:113
absl::move
constexpr absl::remove_reference_t< T > && move(T &&t) noexcept
Definition: abseil-cpp/absl/utility/utility.h:221
root
RefCountedPtr< grpc_tls_certificate_provider > root
Definition: xds_server_config_fetcher.cc:223
testing::Eq
internal::EqMatcher< T > Eq(T x)
Definition: cares/cares/test/gmock-1.8.0/gmock/gmock.h:8561
INSTANTIATE_TYPED_TEST_SUITE_P
#define INSTANTIATE_TYPED_TEST_SUITE_P(Prefix, SuiteName, Types,...)
Definition: googletest/googletest/include/gtest/gtest-typed-test.h:306
googletest-filter-unittest.child
child
Definition: bloaty/third_party/googletest/googletest/test/googletest-filter-unittest.py:62
absl::erase_if
btree_map< K, V, C, A >::size_type erase_if(btree_map< K, V, C, A > &map, Pred pred)
Definition: abseil-cpp/absl/container/btree_map.h:483
b
uint64_t b
Definition: abseil-cpp/absl/container/internal/layout_test.cc:53
testing::Pair
internal::PairMatcher< FirstMatcher, SecondMatcher > Pair(FirstMatcher first_matcher, SecondMatcher second_matcher)
Definition: cares/cares/test/gmock-1.8.0/gmock/gmock.h:9152
absl::container_internal::EraseIf
raw_hash_set< P, H, E, A >::size_type EraseIf(Predicate &pred, raw_hash_set< P, H, E, A > *c)
Definition: abseil-cpp/absl/container/internal/raw_hash_set.h:2287
value
const char * value
Definition: hpack_parser_table.cc:165
Field
struct Field Field
Definition: bloaty/third_party/protobuf/php/ext/google/protobuf/protobuf.h:647
key
const char * key
Definition: hpack_parser_table.cc:164
absl::container_internal::IsEmpty
bool IsEmpty(ctrl_t c)
Definition: abseil-cpp/absl/container/internal/raw_hash_set.h:489
absl::str_format_internal::LengthMod::t
@ t
testing::Key
internal::KeyMatcher< M > Key(M inner_matcher)
Definition: cares/cares/test/gmock-1.8.0/gmock/gmock.h:9141
testing::UnorderedElementsAre
internal::UnorderedElementsAreMatcher< ::testing::tuple<> > UnorderedElementsAre()
Definition: cares/cares/test/gmock-1.8.0/gmock/gmock.h:13255
EXPECT_TRUE
#define EXPECT_TRUE(condition)
Definition: bloaty/third_party/googletest/googletest/include/gtest/gtest.h:1967
absl
Definition: abseil-cpp/absl/algorithm/algorithm.h:31
regress.m
m
Definition: regress/regress.py:25
children
std::map< std::string, Node * > children
Definition: bloaty/third_party/protobuf/src/google/protobuf/util/field_mask_util.cc:257
i
uint64_t i
Definition: abseil-cpp/absl/container/btree_benchmark.cc:230
ASSERT_EQ
#define ASSERT_EQ(val1, val2)
Definition: bloaty/third_party/googletest/googletest/include/gtest/gtest.h:2056

grpc
Author(s):
autogenerated on Fri May 16 2025 02:59:32