Debian Codegraph @

tests/unordered_map_modifiers_test.h

raw
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 PHMAP_PRIV_UNORDERED_MAP_MODIFIERS_TEST_H_
16 #define PHMAP_PRIV_UNORDERED_MAP_MODIFIERS_TEST_H_
17
18 #ifdef _MSC_VER
19 #pragma warning(push, 0)
20 #endif
21
22 #include "gmock/gmock.h"
23 #include "gtest/gtest.h"
24 #include "hash_generator_testing.h"
25 #include "hash_policy_testing.h"
26
27 #ifdef _MSC_VER
28 #pragma warning(pop)
29 #endif
30
31 namespace phmap {
32 namespace priv {
33
34 template <class UnordMap>
35 class ModifiersTest : public ::testing::Test {};
36
37 TYPED_TEST_SUITE_P(ModifiersTest);
38
39 TYPED_TEST_P(ModifiersTest, Clear) {
40 using T = hash_internal::GeneratedType<TypeParam>;
41 std::vector<T> values;
42 std::generate_n(std::back_inserter(values), 10,
43 hash_internal::Generator<T>());
44 TypeParam m(values.begin(), values.end());
45 ASSERT_THAT(items(m), ::testing::UnorderedElementsAreArray(values));
46 m.clear();
47 EXPECT_THAT(items(m), ::testing::UnorderedElementsAre());
48 EXPECT_TRUE(m.empty());
49 }
50
51 TYPED_TEST_P(ModifiersTest, Insert) {
52 using T = hash_internal::GeneratedType<TypeParam>;
53 using V = typename TypeParam::mapped_type;
54 T val = hash_internal::Generator<T>()();
55 TypeParam m;
56 auto p = m.insert(val);
57 EXPECT_TRUE(p.second);
58 EXPECT_EQ(val, *p.first);
59 T val2 = {val.first, hash_internal::Generator<V>()()};
60 p = m.insert(val2);
61 EXPECT_FALSE(p.second);
62 EXPECT_EQ(val, *p.first);
63 }
64
65 TYPED_TEST_P(ModifiersTest, InsertHint) {
66 using T = hash_internal::GeneratedType<TypeParam>;
67 using V = typename TypeParam::mapped_type;
68 T val = hash_internal::Generator<T>()();
69 TypeParam m;
70 auto it = m.insert(m.end(), val);
71 EXPECT_TRUE(it != m.end());
72 EXPECT_EQ(val, *it);
73 T val2 = {val.first, hash_internal::Generator<V>()()};
74 it = m.insert(it, val2);
75 EXPECT_TRUE(it != m.end());
76 EXPECT_EQ(val, *it);
77 }
78
79 TYPED_TEST_P(ModifiersTest, InsertRange) {
80 using T = hash_internal::GeneratedType<TypeParam>;
81 std::vector<T> values;
82 std::generate_n(std::back_inserter(values), 10,
83 hash_internal::Generator<T>());
84 TypeParam m;
85 m.insert(values.begin(), values.end());
86 ASSERT_THAT(items(m), ::testing::UnorderedElementsAreArray(values));
87 }
88
89 TYPED_TEST_P(ModifiersTest, InsertOrAssign) {
90 #ifdef UNORDERED_MAP_CXX17
91 using std::get;
92 using K = typename TypeParam::key_type;
93 using V = typename TypeParam::mapped_type;
94 K k = hash_internal::Generator<K>()();
95 V val = hash_internal::Generator<V>()();
96 TypeParam m;
97 auto p = m.insert_or_assign(k, val);
98 EXPECT_TRUE(p.second);
99 EXPECT_EQ(k, get<0>(*p.first));
100 EXPECT_EQ(val, get<1>(*p.first));
101 V val2 = hash_internal::Generator<V>()();
102 p = m.insert_or_assign(k, val2);
103 EXPECT_FALSE(p.second);
104 EXPECT_EQ(k, get<0>(*p.first));
105 EXPECT_EQ(val2, get<1>(*p.first));
106 #endif
107 }
108
109 TYPED_TEST_P(ModifiersTest, InsertOrAssignHint) {
110 #ifdef UNORDERED_MAP_CXX17
111 using std::get;
112 using K = typename TypeParam::key_type;
113 using V = typename TypeParam::mapped_type;
114 K k = hash_internal::Generator<K>()();
115 V val = hash_internal::Generator<V>()();
116 TypeParam m;
117 auto it = m.insert_or_assign(m.end(), k, val);
118 EXPECT_TRUE(it != m.end());
119 EXPECT_EQ(k, get<0>(*it));
120 EXPECT_EQ(val, get<1>(*it));
121 V val2 = hash_internal::Generator<V>()();
122 it = m.insert_or_assign(it, k, val2);
123 EXPECT_EQ(k, get<0>(*it));
124 EXPECT_EQ(val2, get<1>(*it));
125 #endif
126 }
127
128 TYPED_TEST_P(ModifiersTest, Emplace) {
129 using T = hash_internal::GeneratedType<TypeParam>;
130 using V = typename TypeParam::mapped_type;
131 T val = hash_internal::Generator<T>()();
132 TypeParam m;
133 // TODO(alkis): We need a way to run emplace in a more meaningful way. Perhaps
134 // with test traits/policy.
135 auto p = m.emplace(val);
136 EXPECT_TRUE(p.second);
137 EXPECT_EQ(val, *p.first);
138 T val2 = {val.first, hash_internal::Generator<V>()()};
139 p = m.emplace(val2);
140 EXPECT_FALSE(p.second);
141 EXPECT_EQ(val, *p.first);
142 }
143
144 TYPED_TEST_P(ModifiersTest, EmplaceHint) {
145 using T = hash_internal::GeneratedType<TypeParam>;
146 using V = typename TypeParam::mapped_type;
147 T val = hash_internal::Generator<T>()();
148 TypeParam m;
149 // TODO(alkis): We need a way to run emplace in a more meaningful way. Perhaps
150 // with test traits/policy.
151 auto it = m.emplace_hint(m.end(), val);
152 EXPECT_EQ(val, *it);
153 T val2 = {val.first, hash_internal::Generator<V>()()};
154 it = m.emplace_hint(it, val2);
155 EXPECT_EQ(val, *it);
156 }
157
158 TYPED_TEST_P(ModifiersTest, TryEmplace) {
159 #ifdef UNORDERED_MAP_CXX17
160 using T = hash_internal::GeneratedType<TypeParam>;
161 using V = typename TypeParam::mapped_type;
162 T val = hash_internal::Generator<T>()();
163 TypeParam m;
164 // TODO(alkis): We need a way to run emplace in a more meaningful way. Perhaps
165 // with test traits/policy.
166 auto p = m.try_emplace(val.first, val.second);
167 EXPECT_TRUE(p.second);
168 EXPECT_EQ(val, *p.first);
169 T val2 = {val.first, hash_internal::Generator<V>()()};
170 p = m.try_emplace(val2.first, val2.second);
171 EXPECT_FALSE(p.second);
172 EXPECT_EQ(val, *p.first);
173 #endif
174 }
175
176 TYPED_TEST_P(ModifiersTest, TryEmplaceHint) {
177 #ifdef UNORDERED_MAP_CXX17
178 using T = hash_internal::GeneratedType<TypeParam>;
179 using V = typename TypeParam::mapped_type;
180 T val = hash_internal::Generator<T>()();
181 TypeParam m;
182 // TODO(alkis): We need a way to run emplace in a more meaningful way. Perhaps
183 // with test traits/policy.
184 auto it = m.try_emplace(m.end(), val.first, val.second);
185 EXPECT_EQ(val, *it);
186 T val2 = {val.first, hash_internal::Generator<V>()()};
187 it = m.try_emplace(it, val2.first, val2.second);
188 EXPECT_EQ(val, *it);
189 #endif
190 }
191
192 template <class V>
193 using IfNotVoid = typename std::enable_if<!std::is_void<V>::value, V>::type;
194
195 // In openmap we chose not to return the iterator from erase because that's
196 // more expensive. As such we adapt erase to return an iterator here.
197 struct EraseFirst {
198 template <class Map>
199 auto operator()(Map* m, int) const
200 -> IfNotVoid<decltype(m->erase(m->begin()))> {
201 return m->erase(m->begin());
202 }
203 template <class Map>
204 typename Map::iterator operator()(Map* m, ...) const {
205 auto it = m->begin();
206 m->erase(it++);
207 return it;
208 }
209 };
210
211 TYPED_TEST_P(ModifiersTest, Erase) {
212 using T = hash_internal::GeneratedType<TypeParam>;
213 using std::get;
214 std::vector<T> values;
215 std::generate_n(std::back_inserter(values), 10,
216 hash_internal::Generator<T>());
217 TypeParam m(values.begin(), values.end());
218 ASSERT_THAT(items(m), ::testing::UnorderedElementsAreArray(values));
219 auto& first = *m.begin();
220 std::vector<T> values2;
221 for (const auto& val : values)
222 if (get<0>(val) != get<0>(first)) values2.push_back(val);
223 auto it = EraseFirst()(&m, 0);
224 ASSERT_TRUE(it != m.end());
225 EXPECT_EQ(1, std::count(values2.begin(), values2.end(), *it));
226 EXPECT_THAT(items(m), ::testing::UnorderedElementsAreArray(values2.begin(),
227 values2.end()));
228 }
229
230 TYPED_TEST_P(ModifiersTest, EraseRange) {
231 using T = hash_internal::GeneratedType<TypeParam>;
232 std::vector<T> values;
233 std::generate_n(std::back_inserter(values), 10,
234 hash_internal::Generator<T>());
235 TypeParam m(values.begin(), values.end());
236 ASSERT_THAT(items(m), ::testing::UnorderedElementsAreArray(values));
237 auto it = m.erase(m.begin(), m.end());
238 EXPECT_THAT(items(m), ::testing::UnorderedElementsAre());
239 EXPECT_TRUE(it == m.end());
240 }
241
242 TYPED_TEST_P(ModifiersTest, EraseKey) {
243 using T = hash_internal::GeneratedType<TypeParam>;
244 std::vector<T> values;
245 std::generate_n(std::back_inserter(values), 10,
246 hash_internal::Generator<T>());
247 TypeParam m(values.begin(), values.end());
248 ASSERT_THAT(items(m), ::testing::UnorderedElementsAreArray(values));
249 EXPECT_EQ(1, m.erase(values[0].first));
250 EXPECT_EQ(0, std::count(m.begin(), m.end(), values[0]));
251 EXPECT_THAT(items(m), ::testing::UnorderedElementsAreArray(values.begin() + 1,
252 values.end()));
253 }
254
255 TYPED_TEST_P(ModifiersTest, Swap) {
256 using T = hash_internal::GeneratedType<TypeParam>;
257 std::vector<T> v1;
258 std::vector<T> v2;
259 std::generate_n(std::back_inserter(v1), 5, hash_internal::Generator<T>());
260 std::generate_n(std::back_inserter(v2), 5, hash_internal::Generator<T>());
261 TypeParam m1(v1.begin(), v1.end());
262 TypeParam m2(v2.begin(), v2.end());
263 EXPECT_THAT(items(m1), ::testing::UnorderedElementsAreArray(v1));
264 EXPECT_THAT(items(m2), ::testing::UnorderedElementsAreArray(v2));
265 m1.swap(m2);
266 EXPECT_THAT(items(m1), ::testing::UnorderedElementsAreArray(v2));
267 EXPECT_THAT(items(m2), ::testing::UnorderedElementsAreArray(v1));
268 }
269
270 // TODO(alkis): Write tests for extract.
271 // TODO(alkis): Write tests for merge.
272
273 REGISTER_TYPED_TEST_SUITE_P(ModifiersTest, Clear, Insert, InsertHint,
274 InsertRange, InsertOrAssign, InsertOrAssignHint,
275 Emplace, EmplaceHint, TryEmplace, TryEmplaceHint,
276 Erase, EraseRange, EraseKey, Swap);
277
278 } // namespace priv
279 } // namespace phmap
280
281 #endif // PHMAP_PRIV_UNORDERED_MAP_MODIFIERS_TEST_H_