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 count_copiesunnecessary_copy_tests::count_copies25 count_copies() : tag_(0), id_(++id_count) 26 { 27 ++copies; 28 trace_op("Default construct"); 29 } 30 count_copiesunnecessary_copy_tests::count_copies31 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. count_copiesunnecessary_copy_tests::count_copies46 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 count_copiesunnecessary_copy_tests::count_copies53 count_copies(count_copies const& x) : tag_(x.tag_), id_(++id_count) 54 { 55 ++copies; 56 trace_op("Copy construct"); 57 } 58 count_copiesunnecessary_copy_tests::count_copies59 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 operator =unnecessary_copy_tests::count_copies66 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 operator =unnecessary_copy_tests::count_copies75 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 ~count_copiesunnecessary_copy_tests::count_copies83 ~count_copies() { trace_op("Destruct"); } 84 trace_opunnecessary_copy_tests::count_copies85 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 operator ==(count_copies const & x,count_copies const & y)95 bool operator==(count_copies const& x, count_copies const& y) 96 { 97 return x.tag_ == y.tag_; 98 } 99 source()100 template <class T> T source() { return T(); } 101 reset()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 { hash_value(unnecessary_copy_tests::count_copies const & x)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 unnecessary_copy_insert_test(T *)177 template <class T> void unnecessary_copy_insert_test(T*) 178 { 179 T x; 180 typename T::value_type a; 181 reset(); 182 x.insert(a); 183 COPY_COUNT(1); 184 MOVE_COUNT(0); 185 } 186 unnecessary_copy_insert_rvalue_set_test(T *)187 template <class T> void unnecessary_copy_insert_rvalue_set_test(T*) 188 { 189 T x; 190 typename T::value_type a; 191 reset(); 192 x.insert(boost::move(a)); 193 COPY_COUNT(0); 194 MOVE_COUNT(1); 195 196 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 unnecessary_copy_insert_rvalue_map_test(T *)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 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 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 unnecessary_copy_emplace_test(T *)242 template <class T> void unnecessary_copy_emplace_test(T*) 243 { 244 reset(); 245 T x; 246 typename T::value_type a; 247 COPY_COUNT(1); 248 x.emplace(a); 249 COPY_COUNT(2); 250 } 251 unnecessary_copy_emplace_rvalue_test(T *)252 template <class T> void unnecessary_copy_emplace_rvalue_test(T*) 253 { 254 reset(); 255 T x; 256 x.emplace(source<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) unnecessary_copy_emplace_std_move_test(T *)270 template <class T> void unnecessary_copy_emplace_std_move_test(T*) 271 { 272 reset(); 273 T x; 274 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 unnecessary_copy_emplace_boost_move_test(T *)286 template <class T> void unnecessary_copy_emplace_boost_move_test(T*) 287 { 288 reset(); 289 T x; 290 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 unnecessary_copy_emplace_boost_move_set_test(T *)307 template <class T> void unnecessary_copy_emplace_boost_move_set_test(T*) 308 { 309 reset(); 310 T x; 311 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 unnecessary_copy_emplace_boost_move_map_test(T *)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 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 UNORDERED_AUTO_TEST(unnecessary_copy_emplace_set_test)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 UNORDERED_AUTO_TEST(unnecessary_copy_emplace_map_test)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() 583