ceph/src/boost/libs/container/bench/detail/varray_util.hpp

   1 // Boost.Container
   2 //
   3 // varray details
   4 //
   5 // Copyright (c) 2012-2013 Adam Wulkiewicz, Lodz, Poland.
   6 // Copyright (c) 2011-2013 Andrew Hundt.
   7 //
   8 // Use, modification and distribution is subject to the Boost Software License,
   9 // Version 1.0. (See accompanying file LICENSE_1_0.txt or copy at
  10 // http://www.boost.org/LICENSE_1_0.txt)
  11
  12 #ifndef BOOST_CONTAINER_DETAIL_VARRAY_UTIL_HPP
  13 #define BOOST_CONTAINER_DETAIL_VARRAY_UTIL_HPP
  14
  15 #include <cstddef>
  16 #include <cstring>
  17 #include <memory>
  18 #include <limits>
  19
  20 #include <boost/config.hpp>
  21 #include <boost/core/no_exceptions_support.hpp>
  22
  23 #include <boost/container/detail/addressof.hpp>
  24 #if defined(BOOST_NO_CXX11_VARIADIC_TEMPLATES)
  25 #include <boost/move/detail/fwd_macros.hpp>
  26 #endif
  27 #include <boost/container/detail/iterator.hpp>
  28 #include <boost/container/detail/mpl.hpp>
  29 #include <boost/container/detail/type_traits.hpp>
  30
  31 #include <boost/move/algorithm.hpp>
  32 #include <boost/move/traits.hpp>
  33 #include <boost/move/utility_core.hpp>
  34
  35 // TODO - move vectors iterators optimization to the other, optional file instead of checking defines?
  36
  37 #if defined(BOOST_CONTAINER_VARRAY_ENABLE_VECTORS_OPTIMIZATION) && !defined(BOOST_NO_EXCEPTIONS)
  38 #include <vector>
  39 #include <boost/container/vector.hpp>
  40 #endif // BOOST_CONTAINER_VARRAY_ENABLE_ITERATORS_OPTIMIZATION && !BOOST_NO_EXCEPTIONS
  41
  42 namespace boost { namespace container { namespace varray_detail {
  43
  44 namespace bcd = ::boost::container::dtl;
  45
  46 template <typename I>
  47 struct are_elements_contiguous : boost::container::dtl::is_pointer<I>
  48 {};
  49
  50 #if defined(BOOST_CONTAINER_VARRAY_ENABLE_VECTORS_OPTIMIZATION) && !defined(BOOST_NO_EXCEPTIONS)
  51
  52 template <typename Pointer>
  53 struct are_elements_contiguous<
  54     bcd::vector_const_iterator<Pointer>
  55 > : bcd::true_type
  56 {};
  57
  58 template <typename Pointer>
  59 struct are_elements_contiguous<
  60     bcd::vector_iterator<Pointer>
  61 > : bcd::true_type
  62 {};
  63
  64 #if defined(BOOST_DINKUMWARE_STDLIB)
  65
  66 template <typename T>
  67 struct are_elements_contiguous<
  68     std::_Vector_const_iterator<T>
  69 > : bcd::true_type
  70 {};
  71
  72 template <typename T>
  73 struct are_elements_contiguous<
  74     std::_Vector_iterator<T>
  75 > : bcd::true_type
  76 {};
  77
  78 #elif defined(BOOST_GNU_STDLIB)
  79
  80 template <typename P, typename T, typename Allocator>
  81 struct are_elements_contiguous<
  82     __gnu_cxx::__normal_iterator<P, std::vector<T, Allocator> >
  83 > : bcd::true_type
  84 {};
  85
  86 #elif defined(_LIBCPP_VERSION)
  87
  88 // TODO - test it first
  89 //template <typename P>
  90 //struct are_elements_contiguous<
  91 //    __wrap_iter<P>
  92 //> : bcd::true_type
  93 //{};
  94
  95 #else // OTHER_STDLIB
  96
  97 // TODO - add other iterators implementations
  98
  99 #endif // STDLIB
 100
 101 #endif // BOOST_CONTAINER_VARRAY_ENABLE_VECTORS_OPTIMIZATION && !BOOST_NO_EXCEPTIONS
 102
 103 template <typename I, typename O>
 104 struct are_corresponding :
 105     bcd::bool_<
 106         bcd::is_same<
 107             bcd::remove_const<
 108                 typename ::boost::container::iterator_traits<I>::value_type
 109             >,
 110             bcd::remove_const<
 111                 typename ::boost::container::iterator_traits<O>::value_type
 112             >
 113         >::value &&
 114         are_elements_contiguous<I>::value &&
 115         are_elements_contiguous<O>::value
 116     >
 117 {};
 118
 119 template <typename I, typename V>
 120 struct is_corresponding_value :
 121    bcd::bool_<
 122          bcd::is_same<
 123             bcd::remove_const<typename ::boost::container::iterator_traits<I>::value_type>,
 124             bcd::remove_const<V>
 125          >::value
 126       >
 127 {};
 128
 129 // destroy(I, I)
 130
 131 template <typename I>
 132 void destroy_dispatch(I /*first*/, I /*last*/, bcd::true_type const& /*is_trivially_destructible*/)
 133 {}
 134
 135 template <typename I>
 136 void destroy_dispatch(I first, I last, bcd::false_type const& /*is_trivially_destructible*/)
 137 {
 138     typedef typename ::boost::container::iterator_traits<I>::value_type value_type;
 139     for ( ; first != last ; ++first )
 140         first->~value_type();
 141 }
 142
 143 template <typename I>
 144 void destroy(I first, I last)
 145 {
 146     typedef typename ::boost::container::iterator_traits<I>::value_type value_type;
 147     destroy_dispatch(first, last, bcd::bool_<bcd::is_trivially_destructible<value_type>::value>());
 148 }
 149
 150 // destroy(I)
 151
 152 template <typename I>
 153 void destroy_dispatch(I /*pos*/,
 154                       bcd::true_type const& /*is_trivially_destructible*/)
 155 {}
 156
 157 template <typename I>
 158 void destroy_dispatch(I pos,
 159                       bcd::false_type const& /*is_trivially_destructible*/)
 160 {
 161     typedef typename ::boost::container::iterator_traits<I>::value_type value_type;
 162     pos->~value_type();
 163 }
 164
 165 template <typename I>
 166 void destroy(I pos)
 167 {
 168     typedef typename ::boost::container::iterator_traits<I>::value_type value_type;
 169     destroy_dispatch(pos, bcd::bool_<bcd::is_trivially_destructible<value_type>::value>());
 170 }
 171
 172 // copy(I, I, O)
 173
 174 template <typename I, typename O>
 175 inline O copy_dispatch(I first, I last, O dst, bcd::true_type const& /*use_memmove*/)
 176 {
 177    typedef typename ::boost::container::iterator_traits<I>::value_type value_type;
 178    const std::size_t d = boost::container::iterator_distance(first, last);
 179    ::memmove(boost::container::dtl::addressof(*dst), boost::container::dtl::addressof(*first), sizeof(value_type) * d);
 180    return dst + d;
 181 }
 182
 183 template <typename I, typename O>
 184 inline O copy_dispatch(I first, I last, O dst, bcd::false_type const& /*use_memmove*/)
 185 {
 186     return std::copy(first, last, dst);                                         // may throw
 187 }
 188
 189 template <typename I, typename O>
 190 inline O copy(I first, I last, O dst)
 191 {
 192    typedef bcd::bool_
 193    <  are_corresponding<I, O>::value &&
 194       bcd::is_trivially_copy_assignable<typename ::boost::container::iterator_traits<O>::value_type>::value
 195    > use_memmove;
 196
 197    return copy_dispatch(first, last, dst, use_memmove());                       // may throw
 198 }
 199
 200 // uninitialized_copy(I, I, O)
 201
 202 template <typename I, typename O>
 203 inline
 204 O uninitialized_copy_dispatch(I first, I last, O dst,
 205                               bcd::true_type const& /*use_memcpy*/)
 206 {
 207    typedef typename ::boost::container::iterator_traits<I>::value_type value_type;
 208    const std::size_t d = boost::container::iterator_distance(first, last);
 209    ::memcpy(boost::container::dtl::addressof(*dst), boost::container::dtl::addressof(*first), sizeof(value_type) * d);
 210    return dst + d;
 211 }
 212
 213 template <typename I, typename F>
 214 inline
 215 F uninitialized_copy_dispatch(I first, I last, F dst,
 216                               bcd::false_type const& /*use_memcpy*/)
 217 {
 218     return std::uninitialized_copy(first, last, dst);                                       // may throw
 219 }
 220
 221 template <typename I, typename F>
 222 inline
 223 F uninitialized_copy(I first, I last, F dst)
 224 {
 225    typedef bcd::bool_
 226    <  are_corresponding<I, F>::value &&
 227       bcd::is_trivially_copy_constructible<typename ::boost::container::iterator_traits<F>::value_type>::value
 228    > use_memcpy;
 229    return uninitialized_copy_dispatch(first, last, dst, use_memcpy());          // may throw
 230 }
 231
 232 // uninitialized_move(I, I, O)
 233
 234 template <typename I, typename O>
 235 inline
 236 O uninitialized_move_dispatch(I first, I last, O dst,
 237                               bcd::true_type const& /*use_memcpy*/)
 238 {
 239    typedef typename ::boost::container::iterator_traits<I>::value_type value_type;
 240    const std::size_t d = boost::container::iterator_distance(first, last);
 241    ::memcpy(boost::container::dtl::addressof(*dst), boost::container::dtl::addressof(*first), sizeof(value_type) * d);
 242    return dst + d;
 243 }
 244
 245 template <typename I, typename O>
 246 inline
 247 O uninitialized_move_dispatch(I first, I last, O dst,
 248                               bcd::false_type const& /*use_memcpy*/)
 249 {
 250     //return boost::uninitialized_move(first, last, dst);                         // may throw
 251
 252     O o = dst;
 253
 254     BOOST_TRY
 255     {
 256         typedef typename boost::container::iterator_traits<O>::value_type value_type;
 257         for (; first != last; ++first, ++o )
 258             new (boost::container::dtl::addressof(*o)) value_type(boost::move(*first));
 259     }
 260     BOOST_CATCH(...)
 261     {
 262         destroy(dst, o);
 263         BOOST_RETHROW;
 264     }
 265     BOOST_CATCH_END
 266
 267     return dst;
 268 }
 269
 270 template <typename I, typename O>
 271 inline
 272 O uninitialized_move(I first, I last, O dst)
 273 {
 274    typedef bcd::bool_
 275    <  are_corresponding<I, O>::value &&
 276       bcd::is_trivially_copy_constructible<typename ::boost::container::iterator_traits<O>::value_type>::value
 277    > use_memcpy;
 278    return uninitialized_move_dispatch(first, last, dst, use_memcpy());         // may throw
 279 }
 280
 281 // TODO - move uses memmove - implement 2nd version using memcpy?
 282
 283 // move(I, I, O)
 284
 285 template <typename I, typename O>
 286 inline
 287 O move_dispatch(I first, I last, O dst,
 288                 bcd::true_type const& /*use_memmove*/)
 289 {
 290    typedef typename ::boost::container::iterator_traits<I>::value_type value_type;
 291    const std::size_t d = boost::container::iterator_distance(first, last);
 292    ::memmove(boost::container::dtl::addressof(*dst), boost::container::dtl::addressof(*first), sizeof(value_type)*d );
 293    return dst + d;
 294 }
 295
 296 template <typename I, typename O>
 297 inline
 298 O move_dispatch(I first, I last, O dst,
 299                 bcd::false_type const& /*use_memmove*/)
 300 {
 301    return boost::move(first, last, dst);                                         // may throw
 302 }
 303
 304 template <typename I, typename O>
 305 inline
 306 O move(I first, I last, O dst)
 307 {
 308    typedef bcd::bool_
 309    <  are_corresponding<I, O>::value &&
 310       bcd::is_trivially_copy_constructible<typename ::boost::container::iterator_traits<O>::value_type>::value
 311    > use_memmove;
 312    return move_dispatch(first, last, dst, use_memmove());                      // may throw
 313 }
 314
 315 // move_backward(BDI, BDI, BDO)
 316
 317 template <typename BDI, typename BDO>
 318 inline
 319 BDO move_backward_dispatch(BDI first, BDI last, BDO dst,
 320                            bcd::true_type const& /*use_memmove*/)
 321 {
 322     typedef typename ::boost::container::iterator_traits<BDI>::value_type value_type;
 323     const std::size_t d = boost::container::iterator_distance(first, last);
 324     BDO foo(dst - d);
 325     ::memmove(boost::container::dtl::addressof(*foo), boost::container::dtl::addressof(*first), sizeof(value_type) * d);
 326     return foo;
 327 }
 328
 329 template <typename BDI, typename BDO>
 330 inline
 331 BDO move_backward_dispatch(BDI first, BDI last, BDO dst,
 332                            bcd::false_type const& /*use_memmove*/)
 333 {
 334     return boost::move_backward(first, last, dst);                                // may throw
 335 }
 336
 337 template <typename BDI, typename BDO>
 338 inline
 339 BDO move_backward(BDI first, BDI last, BDO dst)
 340 {
 341    typedef bcd::bool_
 342    <  are_corresponding<BDI, BDO>::value &&
 343       bcd::is_trivially_copy_constructible<typename ::boost::container::iterator_traits<BDO>::value_type>::value
 344    > use_memmove;
 345    return move_backward_dispatch(first, last, dst, use_memmove());             // may throw
 346 }
 347
 348 template <typename T>
 349 struct has_nothrow_move : public
 350     bcd::bool_<
 351          ::boost::has_nothrow_move<
 352                typename bcd::remove_const<T>::type
 353          >::value
 354         ||
 355          ::boost::has_nothrow_move<T>::value
 356     >
 357 {};
 358
 359 // uninitialized_move_if_noexcept(I, I, O)
 360
 361 template <typename I, typename O>
 362 inline
 363 O uninitialized_move_if_noexcept_dispatch(I first, I last, O dst, bcd::true_type const& /*use_move*/)
 364 { return uninitialized_move(first, last, dst); }
 365
 366 template <typename I, typename O>
 367 inline
 368 O uninitialized_move_if_noexcept_dispatch(I first, I last, O dst, bcd::false_type const& /*use_move*/)
 369 { return uninitialized_copy(first, last, dst); }
 370
 371 template <typename I, typename O>
 372 inline
 373 O uninitialized_move_if_noexcept(I first, I last, O dst)
 374 {
 375     typedef has_nothrow_move<
 376         typename ::boost::container::iterator_traits<O>::value_type
 377     > use_move;
 378
 379     return uninitialized_move_if_noexcept_dispatch(first, last, dst, use_move());         // may throw
 380 }
 381
 382 // move_if_noexcept(I, I, O)
 383
 384 template <typename I, typename O>
 385 inline
 386 O move_if_noexcept_dispatch(I first, I last, O dst, bcd::true_type const& /*use_move*/)
 387 { return move(first, last, dst); }
 388
 389 template <typename I, typename O>
 390 inline
 391 O move_if_noexcept_dispatch(I first, I last, O dst, bcd::false_type const& /*use_move*/)
 392 { return copy(first, last, dst); }
 393
 394 template <typename I, typename O>
 395 inline
 396 O move_if_noexcept(I first, I last, O dst)
 397 {
 398     typedef has_nothrow_move<
 399         typename ::boost::container::iterator_traits<O>::value_type
 400     > use_move;
 401
 402     return move_if_noexcept_dispatch(first, last, dst, use_move());         // may throw
 403 }
 404
 405 // uninitialized_fill(I, I)
 406
 407 template <typename I>
 408 inline
 409 void uninitialized_fill_dispatch(I first, I last,
 410                                  bcd::true_type const& /*is_trivially_default_constructible*/,
 411                                  bcd::true_type const& /*disable_trivial_init*/)
 412 {}
 413
 414 template <typename I>
 415 inline
 416 void uninitialized_fill_dispatch(I first, I last,
 417                                  bcd::true_type const& /*is_trivially_default_constructible*/,
 418                                  bcd::false_type const& /*disable_trivial_init*/)
 419 {
 420     typedef typename ::boost::container::iterator_traits<I>::value_type value_type;
 421     for ( ; first != last ; ++first )
 422         new (boost::container::dtl::addressof(*first)) value_type();
 423 }
 424
 425 template <typename I, typename DisableTrivialInit>
 426 inline
 427 void uninitialized_fill_dispatch(I first, I last,
 428                                  bcd::false_type const& /*is_trivially_default_constructible*/,
 429                                  DisableTrivialInit const& /*not_used*/)
 430 {
 431     typedef typename ::boost::container::iterator_traits<I>::value_type value_type;
 432     I it = first;
 433
 434     BOOST_TRY
 435     {
 436         for ( ; it != last ; ++it )
 437             new (boost::container::dtl::addressof(*it)) value_type();                           // may throw
 438     }
 439     BOOST_CATCH(...)
 440     {
 441         destroy(first, it);
 442         BOOST_RETHROW;
 443     }
 444     BOOST_CATCH_END
 445 }
 446
 447 template <typename I, typename DisableTrivialInit>
 448 inline
 449 void uninitialized_fill(I first, I last, DisableTrivialInit const& disable_trivial_init)
 450 {
 451     typedef typename ::boost::container::iterator_traits<I>::value_type value_type;
 452     uninitialized_fill_dispatch(first, last
 453       , bcd::bool_<bcd::is_trivially_default_constructible<value_type>::value>()
 454       , disable_trivial_init);     // may throw
 455 }
 456
 457 // construct(I)
 458
 459 template <typename I>
 460 inline
 461 void construct_dispatch(bcd::true_type const& /*dont_init*/, I pos)
 462 {}
 463
 464 template <typename I>
 465 inline
 466 void construct_dispatch(bcd::false_type const& /*dont_init*/, I pos)
 467 {
 468     typedef typename ::boost::container::iterator_traits<I>::value_type value_type;
 469     new (static_cast<void*>(::boost::container::dtl::addressof(*pos))) value_type();                      // may throw
 470 }
 471
 472 template <typename DisableTrivialInit, typename I>
 473 inline
 474 void construct(DisableTrivialInit const&, I pos)
 475 {
 476     typedef typename ::boost::container::iterator_traits<I>::value_type value_type;
 477     bcd::bool_<
 478         bcd::is_trivially_default_constructible<value_type>::value &&
 479         DisableTrivialInit::value
 480     > dont_init;
 481     construct_dispatch(dont_init(), pos);                                                // may throw
 482 }
 483
 484 // construct(I, V)
 485
 486 template <typename I, typename V>
 487 inline
 488 void construct_dispatch(I pos, V const& v, bcd::true_type const& /*use_memcpy*/)
 489 {
 490     ::memcpy(boost::container::dtl::addressof(*pos), boost::container::dtl::addressof(v), sizeof(V));
 491 }
 492
 493 template <typename I, typename P>
 494 inline
 495 void construct_dispatch(I pos, P const& p,
 496                         bcd::false_type const& /*use_memcpy*/)
 497 {
 498     typedef typename ::boost::container::iterator_traits<I>::value_type V;
 499     new (static_cast<void*>(boost::container::dtl::addressof(*pos))) V(p);                      // may throw
 500 }
 501
 502 template <typename DisableTrivialInit, typename I, typename P>
 503 inline
 504 void construct(DisableTrivialInit const&, I pos, P const& p)
 505 {
 506    typedef bcd::bool_
 507    <  is_corresponding_value<I, P>::value &&
 508       bcd::is_trivially_copy_constructible<P>::value
 509    > use_memcpy;
 510    construct_dispatch(pos, p, use_memcpy());                                   // may throw
 511 }
 512
 513 // Needed by push_back(V &&)
 514
 515 template <typename DisableTrivialInit, typename I, typename P>
 516 inline
 517 void construct(DisableTrivialInit const&, I pos, BOOST_RV_REF(P) p)
 518 {
 519     typedef typename ::boost::container::iterator_traits<I>::value_type V;
 520     new (static_cast<void*>(boost::container::dtl::addressof(*pos))) V(::boost::move(p));                      // may throw
 521 }
 522
 523 // Needed by emplace_back() and emplace()
 524
 525 #if !defined(BOOST_CONTAINER_VARRAY_DISABLE_EMPLACE)
 526 #if !defined(BOOST_NO_CXX11_VARIADIC_TEMPLATES)
 527
 528 template <typename DisableTrivialInit, typename I, class ...Args>
 529 inline
 530 void construct(DisableTrivialInit const&,
 531                I pos,
 532                BOOST_FWD_REF(Args) ...args)
 533 {
 534     typedef typename ::boost::container::iterator_traits<I>::value_type V;
 535     new (static_cast<void*>(boost::container::dtl::addressof(*pos))) V(::boost::forward<Args>(args)...);    // may throw
 536 }
 537
 538 #else // !BOOST_NO_CXX11_VARIADIC_TEMPLATES
 539
 540 // BOOST_NO_CXX11_RVALUE_REFERENCES -> P0 const& p0
 541 // !BOOST_NO_CXX11_RVALUE_REFERENCES -> P0 && p0
 542 // which means that version with one parameter may take V const& v
 543
 544 #define BOOST_CONTAINER_VARRAY_UTIL_CONSTRUCT_CODE(N) \
 545 template <typename DisableTrivialInit, typename I, typename P BOOST_MOVE_I##N BOOST_MOVE_CLASS##N >\
 546 inline void construct(DisableTrivialInit const&, I pos, BOOST_FWD_REF(P) p BOOST_MOVE_I##N BOOST_MOVE_UREF##N )\
 547 {\
 548     typedef typename ::boost::container::iterator_traits<I>::value_type V;\
 549     new (static_cast<void*>(boost::container::dtl::addressof(*pos)))\
 550     V(::boost::forward<P>(p) BOOST_MOVE_I##N BOOST_MOVE_FWD##N); /*may throw*/\
 551 }
 552 BOOST_MOVE_ITERATE_1TO9(BOOST_CONTAINER_VARRAY_UTIL_CONSTRUCT_CODE)
 553 #undef BOOST_CONTAINER_VARRAY_UTIL_CONSTRUCT_CODE
 554
 555 #endif // !BOOST_NO_CXX11_VARIADIC_TEMPLATES
 556 #endif // !BOOST_CONTAINER_VARRAY_DISABLE_EMPLACE
 557
 558 // assign(I, V)
 559
 560 template <typename I, typename V>
 561 inline
 562 void assign_dispatch(I pos, V const& v,
 563                      bcd::true_type const& /*use_memcpy*/)
 564 {
 565     ::memcpy(boost::container::dtl::addressof(*pos), boost::container::dtl::addressof(v), sizeof(V));
 566 }
 567
 568 template <typename I, typename V>
 569 inline
 570 void assign_dispatch(I pos, V const& v,
 571                      bcd::false_type const& /*use_memcpy*/)
 572 {
 573     *pos = v;                                                                   // may throw
 574 }
 575
 576 template <typename I, typename V>
 577 inline
 578 void assign(I pos, V const& v)
 579 {
 580    typedef bcd::bool_
 581    <  is_corresponding_value<I, V>::value &&
 582       bcd::is_trivially_copy_assignable<V>::value
 583    > use_memcpy;
 584    assign_dispatch(pos, v, use_memcpy());                                        // may throw
 585 }
 586
 587 template <typename I, typename V>
 588 inline
 589 void assign(I pos, BOOST_RV_REF(V) v)
 590 {
 591     *pos = boost::move(v);                                                        // may throw
 592 }
 593
 594
 595 // uninitialized_copy_s
 596
 597 template <typename I, typename F>
 598 inline std::size_t uninitialized_copy_s(I first, I last, F dest, std::size_t max_count)
 599 {
 600     std::size_t count = 0;
 601     F it = dest;
 602
 603     BOOST_TRY
 604     {
 605         for ( ; first != last ; ++it, ++first, ++count )
 606         {
 607             if ( max_count <= count )
 608                 return (std::numeric_limits<std::size_t>::max)();
 609
 610             // dummy 0 as DisableTrivialInit
 611             construct(0, it, *first);                                              // may throw
 612         }
 613     }
 614     BOOST_CATCH(...)
 615     {
 616         destroy(dest, it);
 617         BOOST_RETHROW;
 618     }
 619     BOOST_CATCH_END
 620
 621     return count;
 622 }
 623
 624 // scoped_destructor
 625
 626 template<class T>
 627 class scoped_destructor
 628 {
 629 public:
 630     scoped_destructor(T * ptr) : m_ptr(ptr) {}
 631
 632     ~scoped_destructor()
 633     {
 634         if(m_ptr)
 635             destroy(m_ptr);
 636     }
 637
 638     void release() { m_ptr = 0; }
 639
 640 private:
 641     T * m_ptr;
 642 };
 643
 644 }}} // namespace boost::container::varray_detail
 645
 646 #endif // BOOST_CONTAINER_DETAIL_VARRAY_UTIL_HPP