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

   1
   2 // Copyright 2006-2009 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 "../helpers/test.hpp"
  14
  15 namespace unnecessary_copy_tests {
  16   struct count_copies
  17   {
  18   private:
  19     BOOST_COPYABLE_AND_MOVABLE(count_copies)
  20   public:
  21     static int copies;
  22     static int moves;
  23     static int id_count;
  24
  25     count_copies() : tag_(0), id_(++id_count)
  26     {
  27       ++copies;
  28       trace_op("Default construct");
  29     }
  30
  31     explicit count_copies(int tag) : tag_(tag), id_(++id_count)
  32     {
  33       ++copies;
  34       trace_op("Tag construct");
  35     }
  36
  37     // This bizarre constructor is an attempt to confuse emplace.
  38     //
  39     // unordered_map<count_copies, count_copies> x:
  40     // x.emplace(count_copies(1), count_copies(2));
  41     // x.emplace(count_copies(1), count_copies(2), count_copies(3));
  42     //
  43     // The first emplace should use the single argument constructor twice.
  44     // The second emplace should use the single argument contructor for
  45     // the key, and this constructor for the value.
  46     count_copies(count_copies const&, count_copies const& x)
  47         : tag_(x.tag_), id_(++id_count)
  48     {
  49       ++copies;
  50       trace_op("Pair construct");
  51     }
  52
  53     count_copies(count_copies const& x) : tag_(x.tag_), id_(++id_count)
  54     {
  55       ++copies;
  56       trace_op("Copy construct");
  57     }
  58
  59     count_copies(BOOST_RV_REF(count_copies) x) : tag_(x.tag_), id_(++id_count)
  60     {
  61       x.tag_ = -1;
  62       ++moves;
  63       trace_op("Move construct");
  64     }
  65
  66     count_copies& operator=(
  67       BOOST_COPY_ASSIGN_REF(count_copies) p) // Copy assignment
  68     {
  69       tag_ = p.tag_;
  70       ++copies;
  71       trace_op("Copy assign");
  72       return *this;
  73     }
  74
  75     count_copies& operator=(BOOST_RV_REF(count_copies) p) // Move assignment
  76     {
  77       tag_ = p.tag_;
  78       ++moves;
  79       trace_op("Move assign");
  80       return *this;
  81     }
  82
  83     ~count_copies() { trace_op("Destruct"); }
  84
  85     void trace_op(char const* str)
  86     {
  87       BOOST_LIGHTWEIGHT_TEST_OSTREAM << str << ": " << tag_ << " (#" << id_
  88                                      << ")" << std::endl;
  89     }
  90
  91     int tag_;
  92     int id_;
  93   };
  94
  95   bool operator==(count_copies const& x, count_copies const& y)
  96   {
  97     return x.tag_ == y.tag_;
  98   }
  99
 100   template <class T> T source() { return T(); }
 101
 102   void reset()
 103   {
 104     count_copies::copies = 0;
 105     count_copies::moves = 0;
 106
 107     BOOST_LIGHTWEIGHT_TEST_OSTREAM << "\nReset\n" << std::endl;
 108   }
 109 }
 110
 111 #if defined(BOOST_NO_ARGUMENT_DEPENDENT_LOOKUP)
 112 namespace boost
 113 #else
 114 namespace unnecessary_copy_tests
 115 #endif
 116 {
 117   std::size_t hash_value(unnecessary_copy_tests::count_copies const& x)
 118   {
 119     return static_cast<std::size_t>(x.tag_);
 120   }
 121 }
 122
 123 // Boost.Move doesn't seem to work very well on this compiler.
 124 // For example for:
 125 //
 126 //     T x;
 127 //
 128 // It will default construct T, and then move it in.
 129 // For 'T const' it seems to copy.
 130
 131 #if defined(__IBMCPP__) && __IBMCPP__ <= 1210
 132 #define EXTRA_CONSTRUCT_COST 1
 133 #else
 134 #define EXTRA_CONSTRUCT_COST 0
 135 #endif
 136
 137 #define COPY_COUNT(n)                                                          \
 138   if (::unnecessary_copy_tests::count_copies::copies != n) {                   \
 139     BOOST_ERROR("Wrong number of copies.");                                    \
 140     BOOST_LIGHTWEIGHT_TEST_OSTREAM                                             \
 141       << "Number of copies: "                                                  \
 142       << ::unnecessary_copy_tests::count_copies::copies << " expecting: " << n \
 143       << std::endl;                                                            \
 144   }
 145 #define MOVE_COUNT(n)                                                          \
 146   if (::unnecessary_copy_tests::count_copies::moves != n) {                    \
 147     BOOST_ERROR("Wrong number of moves.");                                     \
 148     BOOST_LIGHTWEIGHT_TEST_OSTREAM                                             \
 149       << "Number of moves: " << ::unnecessary_copy_tests::count_copies::moves  \
 150       << " expecting: " << n << std::endl;                                     \
 151   }
 152 #define COPY_COUNT_RANGE(a, b)                                                 \
 153   if (::unnecessary_copy_tests::count_copies::copies < a ||                    \
 154       ::unnecessary_copy_tests::count_copies::copies > b) {                    \
 155     BOOST_ERROR("Wrong number of copies.");                                    \
 156     BOOST_LIGHTWEIGHT_TEST_OSTREAM                                             \
 157       << "Number of copies: "                                                  \
 158       << ::unnecessary_copy_tests::count_copies::copies << " expecting: ["     \
 159       << a << ", " << b << "]" << std::endl;                                   \
 160   }
 161 #define MOVE_COUNT_RANGE(a, b)                                                 \
 162   if (::unnecessary_copy_tests::count_copies::moves < a ||                     \
 163       ::unnecessary_copy_tests::count_copies::moves > b) {                     \
 164     BOOST_ERROR("Wrong number of moves.");                                     \
 165     BOOST_LIGHTWEIGHT_TEST_OSTREAM                                             \
 166       << "Number of moves: " << ::unnecessary_copy_tests::count_copies::moves  \
 167       << " expecting: [" << a << ", " << b << "]" << std::endl;                \
 168   }
 169 #define COPY_COUNT_EXTRA(a, b) COPY_COUNT_RANGE(a, a + b * EXTRA_CONSTRUCT_COST)
 170 #define MOVE_COUNT_EXTRA(a, b) MOVE_COUNT_RANGE(a, a + b * EXTRA_CONSTRUCT_COST)
 171
 172 namespace unnecessary_copy_tests {
 173   int count_copies::copies;
 174   int count_copies::moves;
 175   int count_copies::id_count;
 176
 177   template <class T> void unnecessary_copy_insert_test(T*)
 178   {
 179     T x;
 180     BOOST_DEDUCED_TYPENAME T::value_type a;
 181     reset();
 182     x.insert(a);
 183     COPY_COUNT(1);
 184     MOVE_COUNT(0);
 185   }
 186
 187   template <class T> void unnecessary_copy_insert_rvalue_set_test(T*)
 188   {
 189     T x;
 190     BOOST_DEDUCED_TYPENAME T::value_type a;
 191     reset();
 192     x.insert(boost::move(a));
 193     COPY_COUNT(0);
 194     MOVE_COUNT(1);
 195
 196     BOOST_DEDUCED_TYPENAME T::value_type a2;
 197     reset();
 198     x.insert(boost::move(a));
 199     COPY_COUNT(0);
 200     MOVE_COUNT((x.size() == 2 ? 1 : 0));
 201   }
 202
 203   template <class T> void unnecessary_copy_insert_rvalue_map_test(T*)
 204   {
 205     // Doesn't currently try to emulate std::pair move construction,
 206     // so std::pair's require a copy. Could try emulating it in
 207     // construct_from_args.
 208
 209     T x;
 210     BOOST_DEDUCED_TYPENAME T::value_type a;
 211     reset();
 212     x.insert(boost::move(a));
 213 #if defined(BOOST_NO_CXX11_RVALUE_REFERENCES)
 214     COPY_COUNT(1);
 215     MOVE_COUNT(0);
 216 #else
 217     COPY_COUNT(0);
 218     MOVE_COUNT(1);
 219 #endif
 220
 221     BOOST_DEDUCED_TYPENAME T::value_type a2;
 222     reset();
 223     x.insert(boost::move(a));
 224 #if defined(BOOST_NO_CXX11_RVALUE_REFERENCES)
 225     COPY_COUNT((x.size() == 2 ? 1 : 0));
 226     MOVE_COUNT(0);
 227 #else
 228     COPY_COUNT(0);
 229     MOVE_COUNT((x.size() == 2 ? 1 : 0));
 230 #endif
 231   }
 232
 233   boost::unordered_set<count_copies>* set;
 234   boost::unordered_multiset<count_copies>* multiset;
 235   boost::unordered_map<int, count_copies>* map;
 236   boost::unordered_multimap<int, count_copies>* multimap;
 237
 238   UNORDERED_TEST(unnecessary_copy_insert_test, ((set)(multiset)(map)(multimap)))
 239   UNORDERED_TEST(unnecessary_copy_insert_rvalue_set_test, ((set)(multiset)))
 240   UNORDERED_TEST(unnecessary_copy_insert_rvalue_map_test, ((map)(multimap)))
 241
 242   template <class T> void unnecessary_copy_emplace_test(T*)
 243   {
 244     reset();
 245     T x;
 246     BOOST_DEDUCED_TYPENAME T::value_type a;
 247     COPY_COUNT(1);
 248     x.emplace(a);
 249     COPY_COUNT(2);
 250   }
 251
 252   template <class T> void unnecessary_copy_emplace_rvalue_test(T*)
 253   {
 254     reset();
 255     T x;
 256     x.emplace(source<BOOST_DEDUCED_TYPENAME T::value_type>());
 257 #if !defined(BOOST_NO_CXX11_RVALUE_REFERENCES)
 258     COPY_COUNT(1);
 259 #else
 260     COPY_COUNT(2);
 261 #endif
 262   }
 263
 264   UNORDERED_TEST(
 265     unnecessary_copy_emplace_test, ((set)(multiset)(map)(multimap)))
 266   UNORDERED_TEST(
 267     unnecessary_copy_emplace_rvalue_test, ((set)(multiset)(map)(multimap)))
 268
 269 #if !defined(BOOST_NO_CXX11_RVALUE_REFERENCES)
 270   template <class T> void unnecessary_copy_emplace_std_move_test(T*)
 271   {
 272     reset();
 273     T x;
 274     BOOST_DEDUCED_TYPENAME T::value_type a;
 275     COPY_COUNT(1);
 276     MOVE_COUNT(0);
 277     x.emplace(std::move(a));
 278     COPY_COUNT(1);
 279     MOVE_COUNT(1);
 280   }
 281
 282   UNORDERED_TEST(
 283     unnecessary_copy_emplace_std_move_test, ((set)(multiset)(map)(multimap)))
 284 #endif
 285
 286   template <class T> void unnecessary_copy_emplace_boost_move_test(T*)
 287   {
 288     reset();
 289     T x;
 290     BOOST_DEDUCED_TYPENAME T::value_type a;
 291     COPY_COUNT(1);
 292     MOVE_COUNT_EXTRA(0, 1);
 293     x.emplace(boost::move(a));
 294 #if !defined(BOOST_NO_CXX11_RVALUE_REFERENCES)
 295     COPY_COUNT(1);
 296     MOVE_COUNT(1);
 297 #else
 298     // Since std::pair isn't movable, move only works for sets.
 299     COPY_COUNT_RANGE(1, 2);
 300     MOVE_COUNT_RANGE(0, 1);
 301 #endif
 302   }
 303
 304   UNORDERED_TEST(
 305     unnecessary_copy_emplace_boost_move_test, ((set)(multiset)(map)(multimap)))
 306
 307   template <class T> void unnecessary_copy_emplace_boost_move_set_test(T*)
 308   {
 309     reset();
 310     T x;
 311     BOOST_DEDUCED_TYPENAME T::value_type a;
 312     COPY_COUNT(1);
 313     MOVE_COUNT(0);
 314     x.emplace(boost::move(a));
 315     COPY_COUNT(1);
 316     MOVE_COUNT(1);
 317   }
 318
 319   UNORDERED_TEST(
 320     unnecessary_copy_emplace_boost_move_set_test, ((set)(multiset)))
 321
 322   template <class T> void unnecessary_copy_emplace_boost_move_map_test(T*)
 323   {
 324     reset();
 325     T x;
 326     COPY_COUNT(0);
 327     MOVE_COUNT(0);
 328     BOOST_DEDUCED_TYPENAME T::value_type a;
 329     COPY_COUNT(1);
 330     MOVE_COUNT_EXTRA(0, 1);
 331     x.emplace(boost::move(a));
 332 #if defined(BOOST_NO_CXX11_RVALUE_REFERENCES)
 333     COPY_COUNT(2);
 334     MOVE_COUNT_EXTRA(0, 1);
 335 #else
 336     COPY_COUNT(1);
 337     MOVE_COUNT(1);
 338 #endif
 339   }
 340
 341   UNORDERED_TEST(
 342     unnecessary_copy_emplace_boost_move_map_test, ((map)(multimap)))
 343
 344   UNORDERED_AUTO_TEST (unnecessary_copy_emplace_set_test) {
 345     // When calling 'source' the object is moved on some compilers, but not
 346     // others. So count that here to adjust later.
 347
 348     reset();
 349     source<count_copies>();
 350     int source_cost = ::unnecessary_copy_tests::count_copies::moves;
 351
 352     //
 353
 354     reset();
 355     boost::unordered_set<count_copies> x;
 356     count_copies a;
 357     x.insert(a);
 358     COPY_COUNT(2);
 359     MOVE_COUNT(0);
 360
 361 //
 362 // 0 arguments
 363 //
 364
 365 #if !BOOST_UNORDERED_SUN_WORKAROUNDS1
 366     // The container will have to create a copy in order to compare with
 367     // the existing element.
 368     reset();
 369     x.emplace();
 370
 371     // source_cost doesn't make much sense here, but it seems to fit.
 372     COPY_COUNT(1);
 373     MOVE_COUNT(source_cost);
 374 #endif
 375
 376     //
 377     // 1 argument
 378     //
 379
 380     // Emplace should be able to tell that there already is an element
 381     // without creating a new one.
 382     reset();
 383     x.emplace(a);
 384     COPY_COUNT(0);
 385     MOVE_COUNT(0);
 386
 387     // A new object is created by source, but it shouldn't be moved or
 388     // copied.
 389     reset();
 390     x.emplace(source<count_copies>());
 391     COPY_COUNT(1);
 392     MOVE_COUNT(source_cost);
 393
 394     // No move should take place.
 395     reset();
 396     x.emplace(boost::move(a));
 397     COPY_COUNT(0);
 398     MOVE_COUNT(0);
 399
 400     // Use a new value for cases where a did get moved...
 401     count_copies b;
 402
 403     // The container will have to create a copy in order to compare with
 404     // the existing element.
 405     reset();
 406     x.emplace(b.tag_);
 407     COPY_COUNT(1);
 408     MOVE_COUNT(0);
 409
 410     //
 411     // 2 arguments
 412     //
 413
 414     // The container will have to create b copy in order to compare with
 415     // the existing element.
 416     //
 417     // Note to self: If copy_count == 0 it's an error not an optimization.
 418     // TODO: Devise a better test.
 419
 420     reset();
 421
 422     x.emplace(b, b);
 423     COPY_COUNT(1);
 424     MOVE_COUNT(0);
 425   }
 426
 427   UNORDERED_AUTO_TEST (unnecessary_copy_emplace_map_test) {
 428     // When calling 'source' the object is moved on some compilers, but not
 429     // others. So count that here to adjust later.
 430
 431     reset();
 432     source<count_copies>();
 433     int source_cost = ::unnecessary_copy_tests::count_copies::moves;
 434
 435     reset();
 436     source<std::pair<count_copies, count_copies> >();
 437     int source_pair_cost = ::unnecessary_copy_tests::count_copies::moves;
 438
 439     //
 440
 441     reset();
 442     boost::unordered_map<count_copies, count_copies> x;
 443     // TODO: Run tests for pairs without const etc.
 444     std::pair<count_copies const, count_copies> a;
 445     x.emplace(a);
 446     COPY_COUNT_EXTRA(4, 1);
 447     MOVE_COUNT_EXTRA(0, 1);
 448
 449 //
 450 // 0 arguments
 451 //
 452
 453 #if !BOOST_UNORDERED_SUN_WORKAROUNDS1
 454     // COPY_COUNT(1) would be okay here.
 455     reset();
 456     x.emplace();
 457 #if BOOST_WORKAROUND(BOOST_MSVC, == 1700)
 458     // This is a little odd, Visual C++ 11 seems to move the pair, which
 459     // results in one copy (for the const key) and one move (for the
 460     // non-const mapped value). Since 'emplace(boost::move(a))' (see below)
 461     // has the normal result, it must be some odd consequence of how
 462     // Visual C++ 11 handles calling move for default arguments.
 463     COPY_COUNT(3);
 464     MOVE_COUNT(1);
 465 #else
 466     COPY_COUNT_EXTRA(2, 1);
 467     MOVE_COUNT_EXTRA(0, 1);
 468 #endif
 469 #endif
 470
 471     reset();
 472     x.emplace(boost::unordered::piecewise_construct, boost::make_tuple(),
 473       boost::make_tuple());
 474     COPY_COUNT(2);
 475     MOVE_COUNT(0);
 476
 477     //
 478     // 1 argument
 479     //
 480
 481     reset();
 482     x.emplace(a);
 483     COPY_COUNT(0);
 484     MOVE_COUNT(0);
 485
 486     // A new object is created by source, but it shouldn't be moved or
 487     // copied.
 488     reset();
 489     x.emplace(source<std::pair<count_copies, count_copies> >());
 490     COPY_COUNT(2);
 491     MOVE_COUNT(source_pair_cost);
 492
 493 #if !(defined(__GNUC__) && __cplusplus < 199900L) &&                           \
 494   !(defined(_MSC_VER) && _MSC_VER < 1600)
 495     count_copies part;
 496     reset();
 497     std::pair<count_copies const&, count_copies const&> a_ref(part, part);
 498     x.emplace(a_ref);
 499     COPY_COUNT(2);
 500     MOVE_COUNT(0);
 501
 502 #endif
 503
 504     // No move should take place.
 505     // (since a is already in the container)
 506     reset();
 507     x.emplace(boost::move(a));
 508     COPY_COUNT(0);
 509     MOVE_COUNT(0);
 510
 511     //
 512     // 2 arguments
 513     //
 514
 515     std::pair<count_copies const, count_copies> b;
 516
 517     reset();
 518     x.emplace(b.first, b.second);
 519     COPY_COUNT(0);
 520     MOVE_COUNT(0);
 521
 522     reset();
 523     x.emplace(source<count_copies>(), source<count_copies>());
 524     COPY_COUNT(2);
 525     MOVE_COUNT(source_cost * 2);
 526
 527     // source<count_copies> creates a single copy.
 528     reset();
 529     x.emplace(b.first, source<count_copies>());
 530     COPY_COUNT(1);
 531     MOVE_COUNT(source_cost);
 532
 533     reset();
 534     x.emplace(count_copies(b.first.tag_), count_copies(b.second.tag_));
 535     COPY_COUNT(2);
 536     MOVE_COUNT(0);
 537
 538     reset();
 539     x.emplace(boost::unordered::piecewise_construct,
 540       boost::make_tuple(boost::ref(b.first)),
 541       boost::make_tuple(boost::ref(b.second)));
 542     COPY_COUNT(0);
 543     MOVE_COUNT(0);
 544
 545 #if BOOST_UNORDERED_TUPLE_ARGS
 546
 547     reset();
 548     x.emplace(boost::unordered::piecewise_construct,
 549       std::make_tuple(std::ref(b.first)), std::make_tuple(std::ref(b.second)));
 550     COPY_COUNT(0);
 551     MOVE_COUNT(0);
 552
 553     std::pair<count_copies const, count_copies> move_source_trial;
 554     reset();
 555     std::make_tuple(std::move(move_source_trial.first));
 556     std::make_tuple(std::move(move_source_trial.second));
 557     int tuple_move_cost = ::unnecessary_copy_tests::count_copies::moves;
 558     int tuple_copy_cost = ::unnecessary_copy_tests::count_copies::copies;
 559
 560     std::pair<count_copies const, count_copies> move_source;
 561     reset();
 562     x.emplace(boost::unordered::piecewise_construct,
 563       std::make_tuple(std::move(move_source.first)),
 564       std::make_tuple(std::move(move_source.second)));
 565     COPY_COUNT(tuple_copy_cost);
 566     MOVE_COUNT(tuple_move_cost);
 567
 568 #if !defined(BOOST_NO_CXX11_HDR_TUPLE) &&                                      \
 569   !(defined(__GNUC__) && __GNUC__ == 4 && __GNUC_MINOR__ < 6) &&               \
 570   !(defined(BOOST_MSVC) && BOOST_MSVC < 1700)
 571     reset();
 572     x.emplace(boost::unordered::piecewise_construct,
 573       std::forward_as_tuple(b.first), std::forward_as_tuple(b.second));
 574     COPY_COUNT(0);
 575     MOVE_COUNT(0);
 576 #endif
 577
 578 #endif
 579   }
 580 }
 581
 582 RUN_TESTS()