1
2 // Copyright 2016 Daniel James.
3 // Distributed under the Boost Software License, Version 1.0. (See accompanying
4 // file LICENSE_1_0.txt or copy at http://www.boost.org/LICENSE_1_0.txt)
5
6 #include "../helpers/postfix.hpp"
7 #include "../helpers/prefix.hpp"
8 #include <boost/unordered_map.hpp>
9 #include <boost/unordered_set.hpp>
10
11 #include "../helpers/helpers.hpp"
12 #include "../helpers/metafunctions.hpp"
13 #include "../helpers/test.hpp"
14 #include <boost/core/pointer_traits.hpp>
15 #include <boost/static_assert.hpp>
16 #include <boost/type_traits/is_same.hpp>
17 #include <set>
18 #include <string>
19
UNORDERED_AUTO_TEST(example1)20 UNORDERED_AUTO_TEST (example1) {
21 typedef boost::unordered_map<int, std::string>::insert_return_type
22 insert_return_type;
23
24 boost::unordered_map<int, std::string> src;
25 src.emplace(1, "one");
26 src.emplace(2, "two");
27 src.emplace(3, "buckle my shoe");
28 boost::unordered_map<int, std::string> dst;
29 dst.emplace(3, "three");
30
31 dst.insert(src.extract(src.find(1)));
32 dst.insert(src.extract(2));
33 insert_return_type r = dst.insert(src.extract(3));
34
35 BOOST_TEST(src.empty());
36 BOOST_TEST(dst.size() == 3);
37 BOOST_TEST(dst[1] == "one");
38 BOOST_TEST(dst[2] == "two");
39 BOOST_TEST(dst[3] == "three");
40 BOOST_TEST(!r.inserted);
41 BOOST_TEST(r.position == dst.find(3));
42 BOOST_TEST(r.node.mapped() == "buckle my shoe");
43 }
44
UNORDERED_AUTO_TEST(example2)45 UNORDERED_AUTO_TEST (example2) {
46 boost::unordered_set<int> src;
47 src.insert(1);
48 src.insert(3);
49 src.insert(5);
50 boost::unordered_set<int> dst;
51 dst.insert(2);
52 dst.insert(4);
53 dst.insert(5);
54 // dst.merge(src);
55 // Merge src into dst.
56 // src == {5}
57 // dst == {1, 2, 3, 4, 5}
58 }
59
UNORDERED_AUTO_TEST(example3)60 UNORDERED_AUTO_TEST (example3) {
61 typedef boost::unordered_set<int>::iterator iterator;
62
63 boost::unordered_set<int> src;
64 src.insert(1);
65 src.insert(3);
66 src.insert(5);
67 boost::unordered_set<int> dst;
68 dst.insert(2);
69 dst.insert(4);
70 dst.insert(5);
71 for (iterator i = src.begin(); i != src.end();) {
72 std::pair<iterator, iterator> p = dst.equal_range(*i);
73 if (p.first == p.second)
74 dst.insert(p.first, src.extract(i++));
75 else
76 ++i;
77 }
78 BOOST_TEST(src.size() == 1);
79 BOOST_TEST(*src.begin() == 5);
80
81 std::set<int> dst2(dst.begin(), dst.end());
82 std::set<int>::iterator it = dst2.begin();
83 BOOST_TEST(*it++ == 1);
84 BOOST_TEST(*it++ == 2);
85 BOOST_TEST(*it++ == 3);
86 BOOST_TEST(*it++ == 4);
87 BOOST_TEST(*it++ == 5);
88 BOOST_TEST(it == dst2.end());
89 }
90
UNORDERED_AUTO_TEST(failed_insertion_with_hint)91 UNORDERED_AUTO_TEST (failed_insertion_with_hint) {
92 {
93 boost::unordered_set<int> src;
94 boost::unordered_set<int> dst;
95 src.emplace(10);
96 src.emplace(20);
97 dst.emplace(10);
98 dst.emplace(20);
99
100 boost::unordered_set<int>::node_type nh = src.extract(10);
101
102 BOOST_TEST(dst.insert(dst.find(10), boost::move(nh)) == dst.find(10));
103 BOOST_TEST(nh);
104 BOOST_TEST(!nh.empty());
105 BOOST_TEST(nh.value() == 10);
106
107 BOOST_TEST(dst.insert(dst.find(20), boost::move(nh)) == dst.find(10));
108 BOOST_TEST(nh);
109 BOOST_TEST(!nh.empty());
110 BOOST_TEST(nh.value() == 10);
111
112 BOOST_TEST(src.count(10) == 0);
113 BOOST_TEST(src.count(20) == 1);
114 BOOST_TEST(dst.count(10) == 1);
115 BOOST_TEST(dst.count(20) == 1);
116 }
117
118 {
119 boost::unordered_map<int, int> src;
120 boost::unordered_map<int, int> dst;
121 src.emplace(10, 30);
122 src.emplace(20, 5);
123 dst.emplace(10, 20);
124 dst.emplace(20, 2);
125
126 boost::unordered_map<int, int>::node_type nh = src.extract(10);
127 BOOST_TEST(dst.insert(dst.find(10), boost::move(nh)) == dst.find(10));
128 BOOST_TEST(nh);
129 BOOST_TEST(!nh.empty());
130 BOOST_TEST(nh.key() == 10);
131 BOOST_TEST(nh.mapped() == 30);
132 BOOST_TEST(dst[10] == 20);
133
134 BOOST_TEST(dst.insert(dst.find(20), boost::move(nh)) == dst.find(10));
135 BOOST_TEST(nh);
136 BOOST_TEST(!nh.empty());
137 BOOST_TEST(nh.key() == 10);
138 BOOST_TEST(nh.mapped() == 30);
139 BOOST_TEST(dst[10] == 20);
140
141 BOOST_TEST(src.count(10) == 0);
142 BOOST_TEST(src.count(20) == 1);
143 BOOST_TEST(dst.count(10) == 1);
144 BOOST_TEST(dst.count(20) == 1);
145 }
146 }
147
148 template <typename NodeHandle>
node_handle_compare(NodeHandle const & nh,typename NodeHandle::value_type const & x)149 bool node_handle_compare(
150 NodeHandle const& nh, typename NodeHandle::value_type const& x)
151 {
152 return x == nh.value();
153 }
154
155 template <typename NodeHandle>
node_handle_compare(NodeHandle const & nh,std::pair<typename NodeHandle::key_type const,typename NodeHandle::mapped_type> const & x)156 bool node_handle_compare(
157 NodeHandle const& nh, std::pair<typename NodeHandle::key_type const,
158 typename NodeHandle::mapped_type> const& x)
159 {
160 return x.first == nh.key() && x.second == nh.mapped();
161 }
162
node_handle_tests_impl(Container & c)163 template <typename Container> void node_handle_tests_impl(Container& c)
164 {
165 typedef typename Container::node_type node_type;
166
167 typename Container::value_type value = *c.begin();
168
169 node_type n1;
170 BOOST_TEST(!n1);
171 BOOST_TEST(n1.empty());
172
173 node_type n2 = c.extract(c.begin());
174 BOOST_TEST(n2);
175 BOOST_TEST(!n2.empty());
176 node_handle_compare(n2, value);
177
178 node_type n3 = boost::move(n2);
179 BOOST_TEST(n3);
180 BOOST_TEST(!n2);
181 node_handle_compare(n3, value);
182 // TODO: Check that n2 doesn't have an allocator?
183 // Maybe by swapping and observing that the allocator is
184 // swapped rather than moved?
185
186 n1 = boost::move(n3);
187 BOOST_TEST(n1);
188 BOOST_TEST(!n3);
189 node_handle_compare(n1, value);
190
191 // Self move-assignment empties the node_handle.
192 n1 = boost::move(n1);
193 BOOST_TEST(!n1);
194
195 n3 = boost::move(n3);
196 BOOST_TEST(!n3);
197
198 typename Container::value_type value1 = *c.begin();
199 n1 = c.extract(c.begin());
200 typename Container::value_type value2 = *c.begin();
201 n2 = c.extract(c.begin());
202 n3 = node_type();
203
204 node_handle_compare(n1, value1);
205 node_handle_compare(n2, value2);
206 n1.swap(n2);
207 BOOST_TEST(n1);
208 BOOST_TEST(n2);
209 node_handle_compare(n1, value2);
210 node_handle_compare(n2, value1);
211
212 BOOST_TEST(n1);
213 BOOST_TEST(!n3);
214 n1.swap(n3);
215 BOOST_TEST(!n1);
216 BOOST_TEST(n3);
217 node_handle_compare(n3, value2);
218
219 BOOST_TEST(!n1);
220 BOOST_TEST(n2);
221 n1.swap(n2);
222 BOOST_TEST(n1);
223 BOOST_TEST(!n2);
224 node_handle_compare(n1, value1);
225
226 node_type n4;
227 BOOST_TEST(!n2);
228 BOOST_TEST(!n4);
229 n2.swap(n4);
230 BOOST_TEST(!n2);
231 BOOST_TEST(!n4);
232 }
233
UNORDERED_AUTO_TEST(node_handle_tests)234 UNORDERED_AUTO_TEST (node_handle_tests) {
235 boost::unordered_set<int> x1;
236 x1.emplace(100);
237 x1.emplace(140);
238 x1.emplace(-55);
239 node_handle_tests_impl(x1);
240
241 boost::unordered_map<int, std::string> x2;
242 x2.emplace(10, "ten");
243 x2.emplace(-23, "twenty");
244 x2.emplace(-76, "thirty");
245 node_handle_tests_impl(x2);
246 }
247
248 template <typename Container1, typename Container2>
insert_node_handle_unique(Container1 & c1,Container2 & c2)249 void insert_node_handle_unique(Container1& c1, Container2& c2)
250 {
251 typedef typename Container1::node_type node_type;
252 typedef typename Container1::value_type value_type;
253 BOOST_STATIC_ASSERT(
254 (boost::is_same<node_type, typename Container2::node_type>::value));
255
256 typedef typename Container1::insert_return_type insert_return_type1;
257 typedef typename Container2::insert_return_type insert_return_type2;
258
259 insert_return_type1 r1 = c1.insert(node_type());
260 insert_return_type2 r2 = c2.insert(node_type());
261 BOOST_TEST(!r1.inserted);
262 BOOST_TEST(!r1.node);
263 BOOST_TEST(r1.position == c1.end());
264 BOOST_TEST(!r2.inserted);
265 BOOST_TEST(!r2.node);
266 BOOST_TEST(r2.position == c2.end());
267
268 while (!c1.empty()) {
269 value_type v = *c1.begin();
270 value_type const* v_ptr = boost::to_address(c1.begin());
271 std::size_t count = c2.count(test::get_key<Container1>(v));
272 insert_return_type2 r = c2.insert(c1.extract(c1.begin()));
273 if (!count) {
274 BOOST_TEST(r.inserted);
275 BOOST_TEST_EQ(c2.count(test::get_key<Container1>(v)), count + 1);
276 BOOST_TEST(r.position != c2.end());
277 BOOST_TEST(boost::to_address(r.position) == v_ptr);
278 BOOST_TEST(!r.node);
279 } else {
280 BOOST_TEST(!r.inserted);
281 BOOST_TEST_EQ(c2.count(test::get_key<Container1>(v)), count);
282 BOOST_TEST(r.position != c2.end());
283 BOOST_TEST(
284 test::get_key<Container2>(*r.position) == test::get_key<Container2>(v));
285 BOOST_TEST(r.node);
286 node_handle_compare(r.node, v);
287 }
288 }
289 }
290
291 template <typename Container1, typename Container2>
insert_node_handle_unique2(Container1 & c1,Container2 & c2)292 void insert_node_handle_unique2(Container1& c1, Container2& c2)
293 {
294 typedef typename Container1::node_type node_type;
295 typedef typename Container1::value_type value_type;
296 BOOST_STATIC_ASSERT(
297 (boost::is_same<node_type, typename Container2::node_type>::value));
298
299 // typedef typename Container1::insert_return_type
300 // insert_return_type1;
301 typedef typename Container2::insert_return_type insert_return_type2;
302
303 while (!c1.empty()) {
304 value_type v = *c1.begin();
305 value_type const* v_ptr = boost::to_address(c1.begin());
306 std::size_t count = c2.count(test::get_key<Container1>(v));
307 insert_return_type2 r = c2.insert(c1.extract(test::get_key<Container1>(v)));
308 if (r.inserted) {
309 BOOST_TEST_EQ(c2.count(test::get_key<Container1>(v)), count + 1);
310 BOOST_TEST(r.position != c2.end());
311 BOOST_TEST(boost::to_address(r.position) == v_ptr);
312 BOOST_TEST(!r.node);
313 } else {
314 BOOST_TEST_EQ(c2.count(test::get_key<Container1>(v)), count);
315 BOOST_TEST(r.position != c2.end());
316 BOOST_TEST(
317 test::get_key<Container2>(*r.position) == test::get_key<Container2>(v));
318 BOOST_TEST(r.node);
319 node_handle_compare(r.node, v);
320 }
321 }
322 }
323
324 template <typename Container1, typename Container2>
insert_node_handle_equiv(Container1 & c1,Container2 & c2)325 void insert_node_handle_equiv(Container1& c1, Container2& c2)
326 {
327 typedef typename Container1::node_type node_type;
328 typedef typename Container1::value_type value_type;
329 BOOST_STATIC_ASSERT(
330 (boost::is_same<node_type, typename Container2::node_type>::value));
331
332 typedef typename Container1::iterator iterator1;
333 typedef typename Container2::iterator iterator2;
334
335 iterator1 r1 = c1.insert(node_type());
336 iterator2 r2 = c2.insert(node_type());
337 BOOST_TEST(r1 == c1.end());
338 BOOST_TEST(r2 == c2.end());
339
340 while (!c1.empty()) {
341 value_type v = *c1.begin();
342 value_type const* v_ptr = boost::to_address(c1.begin());
343 std::size_t count = c2.count(test::get_key<Container1>(v));
344 iterator2 r = c2.insert(c1.extract(c1.begin()));
345 BOOST_TEST_EQ(c2.count(test::get_key<Container1>(v)), count + 1);
346 BOOST_TEST(r != c2.end());
347 BOOST_TEST(boost::to_address(r) == v_ptr);
348 }
349 }
350
351 struct hash_thing
352 {
operator ()hash_thing353 std::size_t operator()(int x) const
354 {
355 return static_cast<std::size_t>(x * 13 + 5);
356 }
357 };
358
UNORDERED_AUTO_TEST(insert_node_handle_unique_tests)359 UNORDERED_AUTO_TEST (insert_node_handle_unique_tests) {
360 {
361 boost::unordered_set<int> x1;
362 boost::unordered_set<int> x2;
363 x1.emplace(100);
364 x1.emplace(140);
365 x1.emplace(-55);
366 x2.emplace(140);
367 insert_node_handle_unique(x1, x2);
368 BOOST_TEST(x2.size() == 3);
369 }
370
371 {
372 boost::unordered_map<int, int, hash_thing> x1;
373 boost::unordered_map<int, int> x2;
374 x1.emplace(67, 50);
375 x1.emplace(23, 45);
376 x1.emplace(18, 19);
377 x2.emplace(23, 50);
378 x2.emplace(12, 49);
379 insert_node_handle_unique(x1, x2);
380 BOOST_TEST(x2.size() == 4);
381 }
382 }
383
UNORDERED_AUTO_TEST(insert_node_handle_equiv_tests)384 UNORDERED_AUTO_TEST (insert_node_handle_equiv_tests) {
385 {
386 boost::unordered_multimap<int, int, hash_thing> x1;
387 boost::unordered_multimap<int, int> x2;
388 x1.emplace(67, 50);
389 x1.emplace(67, 100);
390 x1.emplace(23, 45);
391 x1.emplace(18, 19);
392 x2.emplace(23, 50);
393 x2.emplace(12, 49);
394 insert_node_handle_equiv(x1, x2);
395 BOOST_TEST(x2.size() == 6);
396 }
397 }
398
UNORDERED_AUTO_TEST(insert_node_handle_unique_tests2)399 UNORDERED_AUTO_TEST (insert_node_handle_unique_tests2) {
400 {
401 boost::unordered_set<int> x1;
402 boost::unordered_set<int> x2;
403 x1.emplace(100);
404 x1.emplace(140);
405 x1.emplace(-55);
406 x2.emplace(140);
407 insert_node_handle_unique2(x1, x2);
408 BOOST_TEST(x2.size() == 3);
409 }
410
411 {
412 boost::unordered_map<int, int, hash_thing> x1;
413 boost::unordered_map<int, int> x2;
414 x1.emplace(67, 50);
415 x1.emplace(23, 45);
416 x1.emplace(18, 19);
417 x2.emplace(23, 50);
418 x2.emplace(12, 49);
419 insert_node_handle_unique2(x1, x2);
420 BOOST_TEST(x2.size() == 4);
421 }
422 }
423
424 RUN_TESTS()
425