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 // clang-format off
7 #include "../helpers/prefix.hpp"
8 #include <boost/unordered_set.hpp>
9 #include <boost/unordered_map.hpp>
10 #include "../helpers/postfix.hpp"
11 // clang-format on
12 
13 #include <boost/functional/hash/hash.hpp>
14 #include "../helpers/test.hpp"
15 #include "../helpers/count.hpp"
16 #include <string>
17 
18 // Test that various emplace methods work with different numbers of
19 // arguments.
20 
21 namespace emplace_tests {
22   // Constructible with 2 to 10 arguments
23   struct emplace_value : private test::counted_object
24   {
25     typedef int A0;
26     typedef std::string A1;
27     typedef char A2;
28     typedef int A3;
29     typedef int A4;
30     typedef int A5;
31     typedef int A6;
32     typedef int A7;
33     typedef int A8;
34     typedef int A9;
35 
36     int arg_count;
37 
38     A0 a0;
39     A1 a1;
40     A2 a2;
41     A3 a3;
42     A4 a4;
43     A5 a5;
44     A6 a6;
45     A7 a7;
46     A8 a8;
47     A9 a9;
48 
emplace_valueemplace_tests::emplace_value49     emplace_value(A0 const& b0, A1 const& b1) : arg_count(2), a0(b0), a1(b1) {}
50 
emplace_valueemplace_tests::emplace_value51     emplace_value(A0 const& b0, A1 const& b1, A2 const& b2)
52         : arg_count(3), a0(b0), a1(b1), a2(b2)
53     {
54     }
55 
emplace_valueemplace_tests::emplace_value56     emplace_value(A0 const& b0, A1 const& b1, A2 const& b2, A3 const& b3)
57         : arg_count(4), a0(b0), a1(b1), a2(b2), a3(b3)
58     {
59     }
60 
emplace_valueemplace_tests::emplace_value61     emplace_value(
62       A0 const& b0, A1 const& b1, A2 const& b2, A3 const& b3, A4 const& b4)
63         : arg_count(5), a0(b0), a1(b1), a2(b2), a3(b3), a4(b4)
64     {
65     }
66 
emplace_valueemplace_tests::emplace_value67     emplace_value(A0 const& b0, A1 const& b1, A2 const& b2, A3 const& b3,
68       A4 const& b4, A5 const& b5)
69         : arg_count(6), a0(b0), a1(b1), a2(b2), a3(b3), a4(b4), a5(b5)
70     {
71     }
72 
emplace_valueemplace_tests::emplace_value73     emplace_value(A0 const& b0, A1 const& b1, A2 const& b2, A3 const& b3,
74       A4 const& b4, A5 const& b5, A6 const& b6)
75         : arg_count(7), a0(b0), a1(b1), a2(b2), a3(b3), a4(b4), a5(b5), a6(b6)
76     {
77     }
78 
emplace_valueemplace_tests::emplace_value79     emplace_value(A0 const& b0, A1 const& b1, A2 const& b2, A3 const& b3,
80       A4 const& b4, A5 const& b5, A6 const& b6, A7 const& b7)
81         : arg_count(8), a0(b0), a1(b1), a2(b2), a3(b3), a4(b4), a5(b5), a6(b6),
82           a7(b7)
83     {
84     }
85 
emplace_valueemplace_tests::emplace_value86     emplace_value(A0 const& b0, A1 const& b1, A2 const& b2, A3 const& b3,
87       A4 const& b4, A5 const& b5, A6 const& b6, A7 const& b7, A8 const& b8)
88         : arg_count(9), a0(b0), a1(b1), a2(b2), a3(b3), a4(b4), a5(b5), a6(b6),
89           a7(b7), a8(b8)
90     {
91     }
92 
emplace_valueemplace_tests::emplace_value93     emplace_value(A0 const& b0, A1 const& b1, A2 const& b2, A3 const& b3,
94       A4 const& b4, A5 const& b5, A6 const& b6, A7 const& b7, A8 const& b8,
95       A9 const& b9)
96         : arg_count(10), a0(b0), a1(b1), a2(b2), a3(b3), a4(b4), a5(b5), a6(b6),
97           a7(b7), a8(b8), a9(b9)
98     {
99     }
100 
hash_value(emplace_value const & x)101     friend std::size_t hash_value(emplace_value const& x)
102     {
103       std::size_t r1 = 23894278u;
104       if (x.arg_count >= 1)
105         boost::hash_combine(r1, x.a0);
106       if (x.arg_count >= 2)
107         boost::hash_combine(r1, x.a1);
108       if (x.arg_count >= 3)
109         boost::hash_combine(r1, x.a2);
110       if (x.arg_count >= 4)
111         boost::hash_combine(r1, x.a3);
112       if (x.arg_count >= 5)
113         boost::hash_combine(r1, x.a4);
114       if (x.arg_count >= 6)
115         boost::hash_combine(r1, x.a5);
116       if (x.arg_count >= 7)
117         boost::hash_combine(r1, x.a6);
118       if (x.arg_count >= 8)
119         boost::hash_combine(r1, x.a7);
120       if (x.arg_count >= 9)
121         boost::hash_combine(r1, x.a8);
122       if (x.arg_count >= 10)
123         boost::hash_combine(r1, x.a9);
124       return r1;
125     }
126 
operator ==(emplace_value const & x,emplace_value const & y)127     friend bool operator==(emplace_value const& x, emplace_value const& y)
128     {
129       if (x.arg_count != y.arg_count) {
130         return false;
131       }
132       if (x.arg_count >= 1 && x.a0 != y.a0) {
133         return false;
134       }
135       if (x.arg_count >= 2 && x.a1 != y.a1) {
136         return false;
137       }
138       if (x.arg_count >= 3 && x.a2 != y.a2) {
139         return false;
140       }
141       if (x.arg_count >= 4 && x.a3 != y.a3) {
142         return false;
143       }
144       if (x.arg_count >= 5 && x.a4 != y.a4) {
145         return false;
146       }
147       if (x.arg_count >= 6 && x.a5 != y.a5) {
148         return false;
149       }
150       if (x.arg_count >= 7 && x.a6 != y.a6) {
151         return false;
152       }
153       if (x.arg_count >= 8 && x.a7 != y.a7) {
154         return false;
155       }
156       if (x.arg_count >= 9 && x.a8 != y.a8) {
157         return false;
158       }
159       if (x.arg_count >= 10 && x.a9 != y.a9) {
160         return false;
161       }
162       return true;
163     }
164 
165   private:
166     emplace_value();
167     emplace_value(emplace_value const&);
168   };
169 
UNORDERED_AUTO_TEST(emplace_set)170   UNORDERED_AUTO_TEST (emplace_set) {
171     test::check_instances check_;
172 
173     typedef boost::unordered_set<emplace_value, boost::hash<emplace_value> >
174       container;
175     typedef container::iterator iterator;
176     typedef std::pair<iterator, bool> return_type;
177     container x(10);
178     iterator i1;
179     return_type r1, r2;
180 
181     // 2 args
182 
183     emplace_value v1(10, "x");
184     r1 = x.emplace(10, std::string("x"));
185     BOOST_TEST_EQ(x.size(), 1u);
186     BOOST_TEST(r1.second);
187     BOOST_TEST(*r1.first == v1);
188     BOOST_TEST(r1.first == x.find(v1));
189     BOOST_TEST_EQ(check_.instances(), 2);
190     BOOST_TEST_EQ(check_.constructions(), 2);
191 
192     // 3 args
193 
194     emplace_value v2(3, "foo", 'a');
195     r1 = x.emplace(3, "foo", 'a');
196     BOOST_TEST_EQ(x.size(), 2u);
197     BOOST_TEST(r1.second);
198     BOOST_TEST(*r1.first == v2);
199     BOOST_TEST(r1.first == x.find(v2));
200     BOOST_TEST_EQ(check_.instances(), 4);
201     BOOST_TEST_EQ(check_.constructions(), 4);
202 
203     // 7 args with hint + duplicate
204 
205     emplace_value v3(25, "something", 'z', 4, 5, 6, 7);
206     i1 = x.emplace_hint(r1.first, 25, "something", 'z', 4, 5, 6, 7);
207     BOOST_TEST_EQ(x.size(), 3u);
208     BOOST_TEST(*i1 == v3);
209     BOOST_TEST(i1 == x.find(v3));
210     BOOST_TEST_EQ(check_.instances(), 6);
211     BOOST_TEST_EQ(check_.constructions(), 6);
212 
213     r2 = x.emplace(25, "something", 'z', 4, 5, 6, 7);
214     BOOST_TEST_EQ(x.size(), 3u);
215     BOOST_TEST(!r2.second);
216     BOOST_TEST(i1 == r2.first);
217     // The container has to construct an object in order to check
218     // whether it can emplace, so there's an extra cosntruction
219     // here.
220     BOOST_TEST_EQ(check_.instances(), 6);
221     BOOST_TEST_EQ(check_.constructions(), 7);
222 
223     // 10 args + hint duplicate
224 
225     std::string s1;
226     emplace_value v4(10, s1, 'a', 4, 5, 6, 7, 8, 9, 10);
227     r1 = x.emplace(10, s1, 'a', 4, 5, 6, 7, 8, 9, 10);
228     BOOST_TEST_EQ(x.size(), 4u);
229     BOOST_TEST(r1.second);
230     BOOST_TEST(*r1.first == v4);
231     BOOST_TEST(r1.first == x.find(v4));
232     BOOST_TEST_EQ(check_.instances(), 8);
233     BOOST_TEST_EQ(check_.constructions(), 9);
234 
235     BOOST_TEST(
236       r1.first == x.emplace_hint(r1.first, 10, "", 'a', 4, 5, 6, 7, 8, 9, 10));
237     BOOST_TEST(
238       r1.first == x.emplace_hint(r2.first, 10, "", 'a', 4, 5, 6, 7, 8, 9, 10));
239     BOOST_TEST(
240       r1.first == x.emplace_hint(x.end(), 10, "", 'a', 4, 5, 6, 7, 8, 9, 10));
241     BOOST_TEST_EQ(check_.instances(), 8);
242     BOOST_TEST_EQ(check_.constructions(), 12);
243 
244     BOOST_TEST_EQ(x.size(), 4u);
245     BOOST_TEST(x.count(v1) == 1);
246     BOOST_TEST(x.count(v2) == 1);
247     BOOST_TEST(x.count(v3) == 1);
248     BOOST_TEST(x.count(v4) == 1);
249   }
250 
UNORDERED_AUTO_TEST(emplace_multiset)251   UNORDERED_AUTO_TEST (emplace_multiset) {
252     test::check_instances check_;
253 
254     typedef boost::unordered_multiset<emplace_value,
255       boost::hash<emplace_value> >
256       container;
257     typedef container::iterator iterator;
258     container x(10);
259     iterator i1, i2;
260 
261     // 2 args.
262 
263     emplace_value v1(10, "x");
264     i1 = x.emplace(10, std::string("x"));
265     BOOST_TEST_EQ(x.size(), 1u);
266     BOOST_TEST(i1 == x.find(v1));
267     BOOST_TEST_EQ(check_.instances(), 2);
268     BOOST_TEST_EQ(check_.constructions(), 2);
269 
270     // 4 args + duplicate
271 
272     emplace_value v2(4, "foo", 'a', 15);
273     i1 = x.emplace(4, "foo", 'a', 15);
274     BOOST_TEST_EQ(x.size(), 2u);
275     BOOST_TEST(i1 == x.find(v2));
276     BOOST_TEST_EQ(check_.instances(), 4);
277     BOOST_TEST_EQ(check_.constructions(), 4);
278 
279     i2 = x.emplace(4, "foo", 'a', 15);
280     BOOST_TEST_EQ(x.size(), 3u);
281     BOOST_TEST(i1 != i2);
282     BOOST_TEST(*i1 == *i2);
283     BOOST_TEST(x.count(*i1) == 2);
284     BOOST_TEST_EQ(check_.instances(), 5);
285     BOOST_TEST_EQ(check_.constructions(), 5);
286 
287     // 7 args + duplicate using hint.
288 
289     emplace_value v3(7, "", 'z', 4, 5, 6, 7);
290     i1 = x.emplace(7, "", 'z', 4, 5, 6, 7);
291     BOOST_TEST_EQ(x.size(), 4u);
292     BOOST_TEST_EQ(i1->a2, 'z');
293     BOOST_TEST(x.count(*i1) == 1);
294     BOOST_TEST(i1 == x.find(v3));
295     BOOST_TEST_EQ(check_.instances(), 7);
296     BOOST_TEST_EQ(check_.constructions(), 7);
297 
298     i2 = x.emplace_hint(i1, 7, "", 'z', 4, 5, 6, 7);
299     BOOST_TEST_EQ(x.size(), 5u);
300     BOOST_TEST(*i1 == *i2);
301     BOOST_TEST(i1 != i2);
302     BOOST_TEST(x.count(*i1) == 2);
303     BOOST_TEST_EQ(check_.instances(), 8);
304     BOOST_TEST_EQ(check_.constructions(), 8);
305 
306     // 10 args with bad hint + duplicate
307 
308     emplace_value v4(10, "", 'a', 4, 5, 6, 7, 8, 9, 10);
309     i1 = x.emplace_hint(i2, 10, "", 'a', 4, 5, 6, 7, 8, 9, 10);
310     BOOST_TEST_EQ(x.size(), 6u);
311     BOOST_TEST_EQ(i1->arg_count, 10);
312     BOOST_TEST(i1 == x.find(v4));
313     BOOST_TEST_EQ(check_.instances(), 10);
314     BOOST_TEST_EQ(check_.constructions(), 10);
315 
316     i2 = x.emplace_hint(x.end(), 10, "", 'a', 4, 5, 6, 7, 8, 9, 10);
317     BOOST_TEST_EQ(x.size(), 7u);
318     BOOST_TEST(*i1 == *i2);
319     BOOST_TEST(i1 != i2);
320     BOOST_TEST(x.count(*i1) == 2);
321     BOOST_TEST_EQ(check_.instances(), 11);
322     BOOST_TEST_EQ(check_.constructions(), 11);
323 
324     BOOST_TEST_EQ(x.count(v1), 1u);
325     BOOST_TEST_EQ(x.count(v2), 2u);
326     BOOST_TEST_EQ(x.count(v3), 2u);
327   }
328 
UNORDERED_AUTO_TEST(emplace_map)329   UNORDERED_AUTO_TEST (emplace_map) {
330     test::check_instances check_;
331 
332     typedef boost::unordered_map<emplace_value, emplace_value,
333       boost::hash<emplace_value> >
334       container;
335     typedef container::iterator iterator;
336     typedef std::pair<iterator, bool> return_type;
337     container x(10);
338     return_type r1, r2;
339 
340     // 5/8 args + duplicate
341 
342     emplace_value k1(5, "", 'b', 4, 5);
343     emplace_value m1(8, "xxx", 'z', 4, 5, 6, 7, 8);
344     r1 = x.emplace(boost::unordered::piecewise_construct,
345       boost::make_tuple(5, "", 'b', 4, 5),
346       boost::make_tuple(8, "xxx", 'z', 4, 5, 6, 7, 8));
347     BOOST_TEST_EQ(x.size(), 1u);
348     BOOST_TEST(r1.second);
349     BOOST_TEST(x.find(k1) == r1.first);
350     BOOST_TEST(x.find(k1)->second == m1);
351     BOOST_TEST_EQ(check_.instances(), 4);
352     BOOST_TEST_EQ(check_.constructions(), 4);
353 
354     r2 = x.emplace(boost::unordered::piecewise_construct,
355       boost::make_tuple(5, "", 'b', 4, 5),
356       boost::make_tuple(8, "xxx", 'z', 4, 5, 6, 7, 8));
357     BOOST_TEST_EQ(x.size(), 1u);
358     BOOST_TEST(!r2.second);
359     BOOST_TEST(r1.first == r2.first);
360     BOOST_TEST(x.find(k1)->second == m1);
361     BOOST_TEST_EQ(check_.instances(), 4);
362     // constructions could possibly be 5 if the implementation only
363     // constructed the key.
364     BOOST_TEST_EQ(check_.constructions(), 6);
365 
366     // 9/3 args + duplicates with hints, different mapped value.
367 
368     emplace_value k2(9, "", 'b', 4, 5, 6, 7, 8, 9);
369     emplace_value m2(3, "aaa", 'm');
370     r1 = x.emplace(boost::unordered::piecewise_construct,
371       boost::make_tuple(9, "", 'b', 4, 5, 6, 7, 8, 9),
372       boost::make_tuple(3, "aaa", 'm'));
373     BOOST_TEST_EQ(x.size(), 2u);
374     BOOST_TEST(r1.second);
375     BOOST_TEST(r1.first->first.arg_count == 9);
376     BOOST_TEST(r1.first->second.arg_count == 3);
377     BOOST_TEST(x.find(k2) == r1.first);
378     BOOST_TEST(x.find(k2)->second == m2);
379     BOOST_TEST_EQ(check_.instances(), 8);
380     BOOST_TEST_EQ(check_.constructions(), 10);
381 
382     BOOST_TEST(r1.first ==
383                x.emplace_hint(r1.first, boost::unordered::piecewise_construct,
384                  boost::make_tuple(9, "", 'b', 4, 5, 6, 7, 8, 9),
385                  boost::make_tuple(15, "jkjk")));
386     BOOST_TEST(r1.first ==
387                x.emplace_hint(r2.first, boost::unordered::piecewise_construct,
388                  boost::make_tuple(9, "", 'b', 4, 5, 6, 7, 8, 9),
389                  boost::make_tuple(275, "xxx", 'm', 6)));
390     BOOST_TEST(r1.first ==
391                x.emplace_hint(x.end(), boost::unordered::piecewise_construct,
392                  boost::make_tuple(9, "", 'b', 4, 5, 6, 7, 8, 9),
393                  boost::make_tuple(-10, "blah blah", '\0')));
394     BOOST_TEST_EQ(x.size(), 2u);
395     BOOST_TEST(x.find(k2)->second == m2);
396     BOOST_TEST_EQ(check_.instances(), 8);
397     BOOST_TEST_EQ(check_.constructions(), 16);
398   }
399 
UNORDERED_AUTO_TEST(emplace_multimap)400   UNORDERED_AUTO_TEST (emplace_multimap) {
401     test::check_instances check_;
402 
403     typedef boost::unordered_multimap<emplace_value, emplace_value,
404       boost::hash<emplace_value> >
405       container;
406     typedef container::iterator iterator;
407     container x(10);
408     iterator i1, i2, i3, i4;
409 
410     // 5/8 args + duplicate
411 
412     emplace_value k1(5, "", 'b', 4, 5);
413     emplace_value m1(8, "xxx", 'z', 4, 5, 6, 7, 8);
414     i1 = x.emplace(boost::unordered::piecewise_construct,
415       boost::make_tuple(5, "", 'b', 4, 5),
416       boost::make_tuple(8, "xxx", 'z', 4, 5, 6, 7, 8));
417     BOOST_TEST_EQ(x.size(), 1u);
418     BOOST_TEST(x.find(k1) == i1);
419     BOOST_TEST(x.find(k1)->second == m1);
420     BOOST_TEST_EQ(check_.instances(), 4);
421     BOOST_TEST_EQ(check_.constructions(), 4);
422 
423     emplace_value m1a(8, "xxx", 'z', 4, 5, 6, 7, 8);
424     i2 = x.emplace(boost::unordered::piecewise_construct,
425       boost::make_tuple(5, "", 'b', 4, 5),
426       boost::make_tuple(8, "xxx", 'z', 4, 5, 6, 7, 8));
427     BOOST_TEST_EQ(x.size(), 2u);
428     BOOST_TEST(i1 != i2);
429     BOOST_TEST(i1->second == m1);
430     BOOST_TEST(i2->second == m1a);
431     BOOST_TEST_EQ(check_.instances(), 7);
432     BOOST_TEST_EQ(check_.constructions(), 7);
433 
434     // 9/3 args + duplicates with hints, different mapped value.
435 
436     emplace_value k2(9, "", 'b', 4, 5, 6, 7, 8, 9);
437     emplace_value m2(3, "aaa", 'm');
438     i1 = x.emplace(boost::unordered::piecewise_construct,
439       boost::make_tuple(9, "", 'b', 4, 5, 6, 7, 8, 9),
440       boost::make_tuple(3, "aaa", 'm'));
441     BOOST_TEST_EQ(x.size(), 3u);
442     BOOST_TEST(i1->first.arg_count == 9);
443     BOOST_TEST(i1->second.arg_count == 3);
444     BOOST_TEST_EQ(check_.instances(), 11);
445     BOOST_TEST_EQ(check_.constructions(), 11);
446 
447     emplace_value m2a(15, "jkjk");
448     i2 = x.emplace_hint(i2, boost::unordered::piecewise_construct,
449       boost::make_tuple(9, "", 'b', 4, 5, 6, 7, 8, 9),
450       boost::make_tuple(15, "jkjk"));
451     emplace_value m2b(275, "xxx", 'm', 6);
452     i3 = x.emplace_hint(i1, boost::unordered::piecewise_construct,
453       boost::make_tuple(9, "", 'b', 4, 5, 6, 7, 8, 9),
454       boost::make_tuple(275, "xxx", 'm', 6));
455     emplace_value m2c(-10, "blah blah", '\0');
456     i4 = x.emplace_hint(x.end(), boost::unordered::piecewise_construct,
457       boost::make_tuple(9, "", 'b', 4, 5, 6, 7, 8, 9),
458       boost::make_tuple(-10, "blah blah", '\0'));
459     BOOST_TEST_EQ(x.size(), 6u);
460     BOOST_TEST(x.find(k2)->second == m2);
461     BOOST_TEST_EQ(check_.instances(), 20);
462     BOOST_TEST_EQ(check_.constructions(), 20);
463   }
464 
UNORDERED_AUTO_TEST(try_emplace)465   UNORDERED_AUTO_TEST (try_emplace) {
466     test::check_instances check_;
467 
468     typedef boost::unordered_map<int, emplace_value> container;
469     typedef container::iterator iterator;
470     typedef std::pair<iterator, bool> return_type;
471     container x(10);
472     return_type r1, r2, r3;
473 
474     int k1 = 3;
475     emplace_value m1(414, "grr");
476     r1 = x.try_emplace(3, 414, "grr");
477     BOOST_TEST(r1.second);
478     BOOST_TEST(r1.first->first == k1);
479     BOOST_TEST(r1.first->second == m1);
480     BOOST_TEST_EQ(x.size(), 1u);
481     BOOST_TEST_EQ(check_.instances(), 2);
482     BOOST_TEST_EQ(check_.constructions(), 2);
483 
484     int k2 = 10;
485     emplace_value m2(25, "", 'z');
486     r2 = x.try_emplace(10, 25, std::string(""), 'z');
487     BOOST_TEST(r2.second);
488     BOOST_TEST(r2.first->first == k2);
489     BOOST_TEST(r2.first->second == m2);
490     BOOST_TEST_EQ(x.size(), 2u);
491     BOOST_TEST_EQ(check_.instances(), 4);
492     BOOST_TEST_EQ(check_.constructions(), 4);
493 
494     BOOST_TEST(x.find(k1)->second == m1);
495     BOOST_TEST(x.find(k2)->second == m2);
496 
497     r3 = x.try_emplace(k2, 68, "jfeoj", 'p', 49309, 2323);
498     BOOST_TEST(!r3.second);
499     BOOST_TEST(r3.first == r2.first);
500     BOOST_TEST(r3.first->second == m2);
501     BOOST_TEST_EQ(x.size(), 2u);
502     BOOST_TEST_EQ(check_.instances(), 4);
503     BOOST_TEST_EQ(check_.constructions(), 4);
504 
505     BOOST_TEST(r2.first == x.try_emplace(r2.first, k2, 808709, "what"));
506     BOOST_TEST(
507       r2.first ==
508       x.try_emplace(r2.first, k2, 10, "xxx", 'a', 4, 5, 6, 7, 8, 9, 10));
509     BOOST_TEST(r2.first->second == m2);
510     BOOST_TEST_EQ(x.size(), 2u);
511   }
512 }
513 
514 RUN_TESTS()
515