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 #ifndef ABSL_CONTAINER_INTERNAL_UNORDERED_MAP_MODIFIERS_TEST_H_
16 #define ABSL_CONTAINER_INTERNAL_UNORDERED_MAP_MODIFIERS_TEST_H_
17 
18 #include <memory>
19 
20 #include "gmock/gmock.h"
21 #include "gtest/gtest.h"
22 #include "absl/container/internal/hash_generator_testing.h"
23 #include "absl/container/internal/hash_policy_testing.h"
24 
25 namespace absl {
26 ABSL_NAMESPACE_BEGIN
27 namespace container_internal {
28 
29 template <class UnordMap>
30 class ModifiersTest : public ::testing::Test {};
31 
32 TYPED_TEST_SUITE_P(ModifiersTest);
33 
TYPED_TEST_P(ModifiersTest,Clear)34 TYPED_TEST_P(ModifiersTest, Clear) {
35   using T = hash_internal::GeneratedType<TypeParam>;
36   std::vector<T> values;
37   std::generate_n(std::back_inserter(values), 10,
38                   hash_internal::Generator<T>());
39   TypeParam m(values.begin(), values.end());
40   ASSERT_THAT(items(m), ::testing::UnorderedElementsAreArray(values));
41   m.clear();
42   EXPECT_THAT(items(m), ::testing::UnorderedElementsAre());
43   EXPECT_TRUE(m.empty());
44 }
45 
TYPED_TEST_P(ModifiersTest,Insert)46 TYPED_TEST_P(ModifiersTest, Insert) {
47   using T = hash_internal::GeneratedType<TypeParam>;
48   using V = typename TypeParam::mapped_type;
49   T val = hash_internal::Generator<T>()();
50   TypeParam m;
51   auto p = m.insert(val);
52   EXPECT_TRUE(p.second);
53   EXPECT_EQ(val, *p.first);
54   T val2 = {val.first, hash_internal::Generator<V>()()};
55   p = m.insert(val2);
56   EXPECT_FALSE(p.second);
57   EXPECT_EQ(val, *p.first);
58 }
59 
TYPED_TEST_P(ModifiersTest,InsertHint)60 TYPED_TEST_P(ModifiersTest, InsertHint) {
61   using T = hash_internal::GeneratedType<TypeParam>;
62   using V = typename TypeParam::mapped_type;
63   T val = hash_internal::Generator<T>()();
64   TypeParam m;
65   auto it = m.insert(m.end(), val);
66   EXPECT_TRUE(it != m.end());
67   EXPECT_EQ(val, *it);
68   T val2 = {val.first, hash_internal::Generator<V>()()};
69   it = m.insert(it, val2);
70   EXPECT_TRUE(it != m.end());
71   EXPECT_EQ(val, *it);
72 }
73 
TYPED_TEST_P(ModifiersTest,InsertRange)74 TYPED_TEST_P(ModifiersTest, InsertRange) {
75   using T = hash_internal::GeneratedType<TypeParam>;
76   std::vector<T> values;
77   std::generate_n(std::back_inserter(values), 10,
78                   hash_internal::Generator<T>());
79   TypeParam m;
80   m.insert(values.begin(), values.end());
81   ASSERT_THAT(items(m), ::testing::UnorderedElementsAreArray(values));
82 }
83 
TYPED_TEST_P(ModifiersTest,InsertWithinCapacity)84 TYPED_TEST_P(ModifiersTest, InsertWithinCapacity) {
85   using T = hash_internal::GeneratedType<TypeParam>;
86   using V = typename TypeParam::mapped_type;
87   T val = hash_internal::Generator<T>()();
88   TypeParam m;
89   m.reserve(10);
90   const size_t original_capacity = m.bucket_count();
91   m.insert(val);
92   EXPECT_EQ(m.bucket_count(), original_capacity);
93   T val2 = {val.first, hash_internal::Generator<V>()()};
94   m.insert(val2);
95   EXPECT_EQ(m.bucket_count(), original_capacity);
96 }
97 
TYPED_TEST_P(ModifiersTest,InsertRangeWithinCapacity)98 TYPED_TEST_P(ModifiersTest, InsertRangeWithinCapacity) {
99 #if !defined(__GLIBCXX__)
100   using T = hash_internal::GeneratedType<TypeParam>;
101   std::vector<T> base_values;
102   std::generate_n(std::back_inserter(base_values), 10,
103                   hash_internal::Generator<T>());
104   std::vector<T> values;
105   while (values.size() != 100) {
106     std::copy_n(base_values.begin(), 10, std::back_inserter(values));
107   }
108   TypeParam m;
109   m.reserve(10);
110   const size_t original_capacity = m.bucket_count();
111   m.insert(values.begin(), values.end());
112   EXPECT_EQ(m.bucket_count(), original_capacity);
113 #endif
114 }
115 
TYPED_TEST_P(ModifiersTest,InsertOrAssign)116 TYPED_TEST_P(ModifiersTest, InsertOrAssign) {
117 #ifdef UNORDERED_MAP_CXX17
118   using std::get;
119   using K = typename TypeParam::key_type;
120   using V = typename TypeParam::mapped_type;
121   K k = hash_internal::Generator<K>()();
122   V val = hash_internal::Generator<V>()();
123   TypeParam m;
124   auto p = m.insert_or_assign(k, val);
125   EXPECT_TRUE(p.second);
126   EXPECT_EQ(k, get<0>(*p.first));
127   EXPECT_EQ(val, get<1>(*p.first));
128   V val2 = hash_internal::Generator<V>()();
129   p = m.insert_or_assign(k, val2);
130   EXPECT_FALSE(p.second);
131   EXPECT_EQ(k, get<0>(*p.first));
132   EXPECT_EQ(val2, get<1>(*p.first));
133 #endif
134 }
135 
TYPED_TEST_P(ModifiersTest,InsertOrAssignHint)136 TYPED_TEST_P(ModifiersTest, InsertOrAssignHint) {
137 #ifdef UNORDERED_MAP_CXX17
138   using std::get;
139   using K = typename TypeParam::key_type;
140   using V = typename TypeParam::mapped_type;
141   K k = hash_internal::Generator<K>()();
142   V val = hash_internal::Generator<V>()();
143   TypeParam m;
144   auto it = m.insert_or_assign(m.end(), k, val);
145   EXPECT_TRUE(it != m.end());
146   EXPECT_EQ(k, get<0>(*it));
147   EXPECT_EQ(val, get<1>(*it));
148   V val2 = hash_internal::Generator<V>()();
149   it = m.insert_or_assign(it, k, val2);
150   EXPECT_EQ(k, get<0>(*it));
151   EXPECT_EQ(val2, get<1>(*it));
152 #endif
153 }
154 
TYPED_TEST_P(ModifiersTest,Emplace)155 TYPED_TEST_P(ModifiersTest, Emplace) {
156   using T = hash_internal::GeneratedType<TypeParam>;
157   using V = typename TypeParam::mapped_type;
158   T val = hash_internal::Generator<T>()();
159   TypeParam m;
160   // TODO(alkis): We need a way to run emplace in a more meaningful way. Perhaps
161   // with test traits/policy.
162   auto p = m.emplace(val);
163   EXPECT_TRUE(p.second);
164   EXPECT_EQ(val, *p.first);
165   T val2 = {val.first, hash_internal::Generator<V>()()};
166   p = m.emplace(val2);
167   EXPECT_FALSE(p.second);
168   EXPECT_EQ(val, *p.first);
169 }
170 
TYPED_TEST_P(ModifiersTest,EmplaceHint)171 TYPED_TEST_P(ModifiersTest, EmplaceHint) {
172   using T = hash_internal::GeneratedType<TypeParam>;
173   using V = typename TypeParam::mapped_type;
174   T val = hash_internal::Generator<T>()();
175   TypeParam m;
176   // TODO(alkis): We need a way to run emplace in a more meaningful way. Perhaps
177   // with test traits/policy.
178   auto it = m.emplace_hint(m.end(), val);
179   EXPECT_EQ(val, *it);
180   T val2 = {val.first, hash_internal::Generator<V>()()};
181   it = m.emplace_hint(it, val2);
182   EXPECT_EQ(val, *it);
183 }
184 
TYPED_TEST_P(ModifiersTest,TryEmplace)185 TYPED_TEST_P(ModifiersTest, TryEmplace) {
186 #ifdef UNORDERED_MAP_CXX17
187   using T = hash_internal::GeneratedType<TypeParam>;
188   using V = typename TypeParam::mapped_type;
189   T val = hash_internal::Generator<T>()();
190   TypeParam m;
191   // TODO(alkis): We need a way to run emplace in a more meaningful way. Perhaps
192   // with test traits/policy.
193   auto p = m.try_emplace(val.first, val.second);
194   EXPECT_TRUE(p.second);
195   EXPECT_EQ(val, *p.first);
196   T val2 = {val.first, hash_internal::Generator<V>()()};
197   p = m.try_emplace(val2.first, val2.second);
198   EXPECT_FALSE(p.second);
199   EXPECT_EQ(val, *p.first);
200 #endif
201 }
202 
TYPED_TEST_P(ModifiersTest,TryEmplaceHint)203 TYPED_TEST_P(ModifiersTest, TryEmplaceHint) {
204 #ifdef UNORDERED_MAP_CXX17
205   using T = hash_internal::GeneratedType<TypeParam>;
206   using V = typename TypeParam::mapped_type;
207   T val = hash_internal::Generator<T>()();
208   TypeParam m;
209   // TODO(alkis): We need a way to run emplace in a more meaningful way. Perhaps
210   // with test traits/policy.
211   auto it = m.try_emplace(m.end(), val.first, val.second);
212   EXPECT_EQ(val, *it);
213   T val2 = {val.first, hash_internal::Generator<V>()()};
214   it = m.try_emplace(it, val2.first, val2.second);
215   EXPECT_EQ(val, *it);
216 #endif
217 }
218 
219 template <class V>
220 using IfNotVoid = typename std::enable_if<!std::is_void<V>::value, V>::type;
221 
222 // In openmap we chose not to return the iterator from erase because that's
223 // more expensive. As such we adapt erase to return an iterator here.
224 struct EraseFirst {
225   template <class Map>
226   auto operator()(Map* m, int) const
227       -> IfNotVoid<decltype(m->erase(m->begin()))> {
228     return m->erase(m->begin());
229   }
230   template <class Map>
operatorEraseFirst231   typename Map::iterator operator()(Map* m, ...) const {
232     auto it = m->begin();
233     m->erase(it++);
234     return it;
235   }
236 };
237 
TYPED_TEST_P(ModifiersTest,Erase)238 TYPED_TEST_P(ModifiersTest, Erase) {
239   using T = hash_internal::GeneratedType<TypeParam>;
240   using std::get;
241   std::vector<T> values;
242   std::generate_n(std::back_inserter(values), 10,
243                   hash_internal::Generator<T>());
244   TypeParam m(values.begin(), values.end());
245   ASSERT_THAT(items(m), ::testing::UnorderedElementsAreArray(values));
246   auto& first = *m.begin();
247   std::vector<T> values2;
248   for (const auto& val : values)
249     if (get<0>(val) != get<0>(first)) values2.push_back(val);
250   auto it = EraseFirst()(&m, 0);
251   ASSERT_TRUE(it != m.end());
252   EXPECT_EQ(1, std::count(values2.begin(), values2.end(), *it));
253   EXPECT_THAT(items(m), ::testing::UnorderedElementsAreArray(values2.begin(),
254                                                              values2.end()));
255 }
256 
TYPED_TEST_P(ModifiersTest,EraseRange)257 TYPED_TEST_P(ModifiersTest, EraseRange) {
258   using T = hash_internal::GeneratedType<TypeParam>;
259   std::vector<T> values;
260   std::generate_n(std::back_inserter(values), 10,
261                   hash_internal::Generator<T>());
262   TypeParam m(values.begin(), values.end());
263   ASSERT_THAT(items(m), ::testing::UnorderedElementsAreArray(values));
264   auto it = m.erase(m.begin(), m.end());
265   EXPECT_THAT(items(m), ::testing::UnorderedElementsAre());
266   EXPECT_TRUE(it == m.end());
267 }
268 
TYPED_TEST_P(ModifiersTest,EraseKey)269 TYPED_TEST_P(ModifiersTest, EraseKey) {
270   using T = hash_internal::GeneratedType<TypeParam>;
271   std::vector<T> values;
272   std::generate_n(std::back_inserter(values), 10,
273                   hash_internal::Generator<T>());
274   TypeParam m(values.begin(), values.end());
275   ASSERT_THAT(items(m), ::testing::UnorderedElementsAreArray(values));
276   EXPECT_EQ(1, m.erase(values[0].first));
277   EXPECT_EQ(0, std::count(m.begin(), m.end(), values[0]));
278   EXPECT_THAT(items(m), ::testing::UnorderedElementsAreArray(values.begin() + 1,
279                                                              values.end()));
280 }
281 
TYPED_TEST_P(ModifiersTest,Swap)282 TYPED_TEST_P(ModifiersTest, Swap) {
283   using T = hash_internal::GeneratedType<TypeParam>;
284   std::vector<T> v1;
285   std::vector<T> v2;
286   std::generate_n(std::back_inserter(v1), 5, hash_internal::Generator<T>());
287   std::generate_n(std::back_inserter(v2), 5, hash_internal::Generator<T>());
288   TypeParam m1(v1.begin(), v1.end());
289   TypeParam m2(v2.begin(), v2.end());
290   EXPECT_THAT(items(m1), ::testing::UnorderedElementsAreArray(v1));
291   EXPECT_THAT(items(m2), ::testing::UnorderedElementsAreArray(v2));
292   m1.swap(m2);
293   EXPECT_THAT(items(m1), ::testing::UnorderedElementsAreArray(v2));
294   EXPECT_THAT(items(m2), ::testing::UnorderedElementsAreArray(v1));
295 }
296 
297 // TODO(alkis): Write tests for extract.
298 // TODO(alkis): Write tests for merge.
299 
300 REGISTER_TYPED_TEST_SUITE_P(ModifiersTest, Clear, Insert, InsertHint,
301                             InsertRange, InsertWithinCapacity,
302                             InsertRangeWithinCapacity, InsertOrAssign,
303                             InsertOrAssignHint, Emplace, EmplaceHint,
304                             TryEmplace, TryEmplaceHint, Erase, EraseRange,
305                             EraseKey, Swap);
306 
307 template <typename Type>
308 struct is_unique_ptr : std::false_type {};
309 
310 template <typename Type>
311 struct is_unique_ptr<std::unique_ptr<Type>> : std::true_type {};
312 
313 template <class UnordMap>
314 class UniquePtrModifiersTest : public ::testing::Test {
315  protected:
316   UniquePtrModifiersTest() {
317     static_assert(is_unique_ptr<typename UnordMap::mapped_type>::value,
318                   "UniquePtrModifiersTyest may only be called with a "
319                   "std::unique_ptr value type.");
320   }
321 };
322 
323 GTEST_ALLOW_UNINSTANTIATED_PARAMETERIZED_TEST(UniquePtrModifiersTest);
324 
325 TYPED_TEST_SUITE_P(UniquePtrModifiersTest);
326 
327 // Test that we do not move from rvalue arguments if an insertion does not
328 // happen.
329 TYPED_TEST_P(UniquePtrModifiersTest, TryEmplace) {
330 #ifdef UNORDERED_MAP_CXX17
331   using T = hash_internal::GeneratedType<TypeParam>;
332   using V = typename TypeParam::mapped_type;
333   T val = hash_internal::Generator<T>()();
334   TypeParam m;
335   auto p = m.try_emplace(val.first, std::move(val.second));
336   EXPECT_TRUE(p.second);
337   // A moved from std::unique_ptr is guaranteed to be nullptr.
338   EXPECT_EQ(val.second, nullptr);
339   T val2 = {val.first, hash_internal::Generator<V>()()};
340   p = m.try_emplace(val2.first, std::move(val2.second));
341   EXPECT_FALSE(p.second);
342   EXPECT_NE(val2.second, nullptr);
343 #endif
344 }
345 
346 REGISTER_TYPED_TEST_SUITE_P(UniquePtrModifiersTest, TryEmplace);
347 
348 }  // namespace container_internal
349 ABSL_NAMESPACE_END
350 }  // namespace absl
351 
352 #endif  // ABSL_CONTAINER_INTERNAL_UNORDERED_MAP_MODIFIERS_TEST_H_
353