ceph/src/boost/libs/unordered/test/unordered/emplace_tests.cpp

   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
  49     emplace_value(A0 const& b0, A1 const& b1) : arg_count(2), a0(b0), a1(b1) {}
  50
  51     emplace_value(A0 const& b0, A1 const& b1, A2 const& b2)
  52         : arg_count(3), a0(b0), a1(b1), a2(b2)
  53     {
  54     }
  55
  56     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
  61     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
  67     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
  73     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
  79     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
  86     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
  93     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
 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
 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
 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
 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
 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
 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
 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()