ceph/src/boost/boost/container/detail/copy_move_algo.hpp

   1 //////////////////////////////////////////////////////////////////////////////
   2 //
   3 // (C) Copyright Ion Gaztanaga 2005-2013. Distributed under the Boost
   4 // Software License, Version 1.0. (See accompanying file
   5 // LICENSE_1_0.txt or copy at http://www.boost.org/LICENSE_1_0.txt)
   6 //
   7 // See http://www.boost.org/libs/container for documentation.
   8 //
   9 //////////////////////////////////////////////////////////////////////////////
  10 #ifndef BOOST_CONTAINER_DETAIL_COPY_MOVE_ALGO_HPP
  11 #define BOOST_CONTAINER_DETAIL_COPY_MOVE_ALGO_HPP
  12
  13 #ifndef BOOST_CONFIG_HPP
  14 #  include <boost/config.hpp>
  15 #endif
  16
  17 #if defined(BOOST_HAS_PRAGMA_ONCE)
  18 #  pragma once
  19 #endif
  20
  21 // container
  22 #include <boost/container/allocator_traits.hpp>
  23 // container/detail
  24 #include <boost/container/detail/iterator.hpp>
  25 #include <boost/move/detail/iterator_to_raw_pointer.hpp>
  26 #include <boost/container/detail/mpl.hpp>
  27 #include <boost/container/detail/type_traits.hpp>
  28 #include <boost/container/detail/construct_in_place.hpp>
  29
  30 // move
  31 #include <boost/move/adl_move_swap.hpp>
  32 #include <boost/move/iterator.hpp>
  33 #include <boost/move/utility_core.hpp>
  34 // other
  35 #include <boost/core/no_exceptions_support.hpp>
  36 // std
  37 #include <cstring> //for memmove/memcpy
  38
  39 #if defined(BOOST_GCC) && (BOOST_GCC >= 40600)
  40 #pragma GCC diagnostic push
  41 //pair memcpy optimizations rightfully detected by GCC
  42 #  if defined(BOOST_GCC) && (BOOST_GCC >= 80000)
  43 #     pragma GCC diagnostic ignored "-Wclass-memaccess"
  44 #  endif
  45 //GCC 8 seems a bit confused about array access error with static_vector
  46 //when out of bound exceptions are being thrown.
  47 #  if defined(BOOST_GCC) && (BOOST_GCC >= 80000) && (BOOST_GCC < 80200)
  48 #     pragma GCC diagnostic ignored "-Wstringop-overflow"
  49 #  endif
  50 #  pragma GCC diagnostic ignored "-Warray-bounds"
  51 #endif
  52
  53 namespace boost {
  54 namespace container {
  55 namespace dtl {
  56
  57 template<class I>
  58 struct are_elements_contiguous
  59 {
  60    static const bool value = false;
  61 };
  62
  63 /////////////////////////
  64 //    raw pointers
  65 /////////////////////////
  66
  67 template<class T>
  68 struct are_elements_contiguous<T*>
  69 {
  70    static const bool value = true;
  71 };
  72
  73 /////////////////////////
  74 //    move iterators
  75 /////////////////////////
  76
  77 template<class It>
  78 struct are_elements_contiguous< ::boost::move_iterator<It> >
  79    : are_elements_contiguous<It>
  80 {};
  81
  82 }  //namespace dtl {
  83
  84 /////////////////////////
  85 //    predeclarations
  86 /////////////////////////
  87
  88 template <class Pointer, bool IsConst>
  89 class vec_iterator;
  90
  91 }  //namespace container {
  92
  93 namespace interprocess {
  94
  95 template <class PointedType, class DifferenceType, class OffsetType, std::size_t OffsetAlignment>
  96 class offset_ptr;
  97
  98 }  //namespace interprocess {
  99
 100 namespace container {
 101
 102 namespace dtl {
 103
 104 /////////////////////////
 105 //vector_[const_]iterator
 106 /////////////////////////
 107
 108 template <class Pointer, bool IsConst>
 109 struct are_elements_contiguous<boost::container::vec_iterator<Pointer, IsConst> >
 110 {
 111    static const bool value = true;
 112 };
 113
 114 /////////////////////////
 115 //    offset_ptr
 116 /////////////////////////
 117
 118 template <class PointedType, class DifferenceType, class OffsetType, std::size_t OffsetAlignment>
 119 struct are_elements_contiguous< ::boost::interprocess::offset_ptr<PointedType, DifferenceType, OffsetType, OffsetAlignment> >
 120 {
 121    static const bool value = true;
 122 };
 123
 124 template <typename I, typename O>
 125 struct are_contiguous_and_same
 126    : boost::move_detail::and_
 127       < are_elements_contiguous<I>
 128       , are_elements_contiguous<O>
 129       , is_same< typename remove_const< typename ::boost::container::iterator_traits<I>::value_type >::type
 130                , typename ::boost::container::iterator_traits<O>::value_type
 131                >
 132       >
 133 {};
 134
 135 template <typename I, typename O>
 136 struct is_memtransfer_copy_assignable
 137    : boost::move_detail::and_
 138       < are_contiguous_and_same<I, O>
 139       , dtl::is_trivially_copy_assignable< typename ::boost::container::iterator_traits<I>::value_type >
 140       >
 141 {};
 142
 143 template <typename I, typename O>
 144 struct is_memtransfer_copy_constructible
 145    : boost::move_detail::and_
 146       < are_contiguous_and_same<I, O>
 147       , dtl::is_trivially_copy_constructible< typename ::boost::container::iterator_traits<I>::value_type >
 148       >
 149 {};
 150
 151 template <typename I, typename O, typename R>
 152 struct enable_if_memtransfer_copy_constructible
 153    : enable_if<dtl::is_memtransfer_copy_constructible<I, O>, R>
 154 {};
 155
 156 template <typename I, typename O, typename R>
 157 struct disable_if_memtransfer_copy_constructible
 158    : disable_if<dtl::is_memtransfer_copy_constructible<I, O>, R>
 159 {};
 160
 161 template <typename I, typename O, typename R>
 162 struct enable_if_memtransfer_copy_assignable
 163    : enable_if<dtl::is_memtransfer_copy_assignable<I, O>, R>
 164 {};
 165
 166 template <typename I, typename O, typename R>
 167 struct disable_if_memtransfer_copy_assignable
 168    : disable_if<dtl::is_memtransfer_copy_assignable<I, O>, R>
 169 {};
 170
 171 template
 172    <typename I, // I models InputIterator
 173     typename F> // F models ForwardIterator
 174 inline F memmove(I f, I l, F r) BOOST_NOEXCEPT_OR_NOTHROW
 175 {
 176    typedef typename boost::container::iterator_traits<I>::value_type value_type;
 177    value_type *const dest_raw = boost::movelib::iterator_to_raw_pointer(r);
 178    const value_type *const beg_raw = boost::movelib::iterator_to_raw_pointer(f);
 179    const value_type *const end_raw = boost::movelib::iterator_to_raw_pointer(l);
 180    if(BOOST_LIKELY(beg_raw != end_raw && dest_raw && beg_raw)){
 181       const typename boost::container::iterator_traits<I>::difference_type n = end_raw - beg_raw;
 182       std::memmove(dest_raw, beg_raw, sizeof(value_type)*n);
 183       boost::container::iterator_advance(r, n);
 184    }
 185    return r;
 186 }
 187
 188 template
 189    <typename I, // I models InputIterator
 190     typename U, // U models unsigned integral constant
 191     typename F> // F models ForwardIterator
 192 F memmove_n(I f, U n, F r) BOOST_NOEXCEPT_OR_NOTHROW
 193 {
 194    typedef typename boost::container::iterator_traits<I>::value_type value_type;
 195    if(BOOST_LIKELY(n)){
 196       std::memmove(boost::movelib::iterator_to_raw_pointer(r), boost::movelib::iterator_to_raw_pointer(f), sizeof(value_type)*n);
 197       boost::container::iterator_advance(r, n);
 198    }
 199
 200    return r;
 201 }
 202
 203 template
 204    <typename I, // I models InputIterator
 205     typename U, // U models unsigned integral constant
 206     typename F> // F models ForwardIterator
 207 I memmove_n_source(I f, U n, F r) BOOST_NOEXCEPT_OR_NOTHROW
 208 {
 209    if(BOOST_LIKELY(n)){
 210       typedef typename boost::container::iterator_traits<I>::value_type value_type;
 211       std::memmove(boost::movelib::iterator_to_raw_pointer(r), boost::movelib::iterator_to_raw_pointer(f), sizeof(value_type)*n);
 212       boost::container::iterator_advance(f, n);
 213    }
 214    return f;
 215 }
 216
 217 template
 218    <typename I, // I models InputIterator
 219     typename U, // U models unsigned integral constant
 220     typename F> // F models ForwardIterator
 221 I memmove_n_source_dest(I f, U n, F &r) BOOST_NOEXCEPT_OR_NOTHROW
 222 {
 223    typedef typename boost::container::iterator_traits<I>::value_type value_type;
 224    if(BOOST_LIKELY(n)){
 225       std::memmove(boost::movelib::iterator_to_raw_pointer(r), boost::movelib::iterator_to_raw_pointer(f), sizeof(value_type)*n);
 226       boost::container::iterator_advance(f, n);
 227       boost::container::iterator_advance(r, n);
 228    }
 229    return f;
 230 }
 231
 232 template <typename O>
 233 struct is_memzero_initializable
 234 {
 235    typedef typename ::boost::container::iterator_traits<O>::value_type value_type;
 236    static const bool value = are_elements_contiguous<O>::value &&
 237       (  dtl::is_integral<value_type>::value || dtl::is_enum<value_type>::value
 238       #if defined(BOOST_CONTAINER_MEMZEROED_POINTER_IS_NULL)
 239       || dtl::is_pointer<value_type>::value
 240       #endif
 241       #if defined(BOOST_CONTAINER_MEMZEROED_FLOATING_POINT_IS_ZERO)
 242       || dtl::is_floating_point<value_type>::value
 243       #endif
 244       #if defined(BOOST_CONTAINER_MEMZEROED_FLOATING_POINT_IS_ZERO) && defined(BOOST_CONTAINER_MEMZEROED_POINTER_IS_NULL)
 245       || dtl::is_pod<value_type>::value
 246       #endif
 247       );
 248 };
 249
 250 template <typename O, typename R>
 251 struct enable_if_memzero_initializable
 252    : enable_if_c<dtl::is_memzero_initializable<O>::value, R>
 253 {};
 254
 255 template <typename O, typename R>
 256 struct disable_if_memzero_initializable
 257    : enable_if_c<!dtl::is_memzero_initializable<O>::value, R>
 258 {};
 259
 260 template <typename I, typename R>
 261 struct enable_if_trivially_destructible
 262    : enable_if_c < dtl::is_trivially_destructible
 263                   <typename boost::container::iterator_traits<I>::value_type>::value
 264                , R>
 265 {};
 266
 267 template <typename I, typename R>
 268 struct disable_if_trivially_destructible
 269    : enable_if_c <!dtl::is_trivially_destructible
 270                   <typename boost::container::iterator_traits<I>::value_type>::value
 271                , R>
 272 {};
 273
 274 }  //namespace dtl {
 275
 276 //////////////////////////////////////////////////////////////////////////////
 277 //
 278 //                               uninitialized_move_alloc
 279 //
 280 //////////////////////////////////////////////////////////////////////////////
 281
 282
 283 //! <b>Effects</b>:
 284 //!   \code
 285 //!   for (; f != l; ++r, ++f)
 286 //!      allocator_traits::construct(a, &*r, boost::move(*f));
 287 //!   \endcode
 288 //!
 289 //! <b>Returns</b>: r
 290 template
 291    <typename Allocator,
 292     typename I, // I models InputIterator
 293     typename F> // F models ForwardIterator
 294 inline typename dtl::disable_if_memtransfer_copy_constructible<I, F, F>::type
 295    uninitialized_move_alloc(Allocator &a, I f, I l, F r)
 296 {
 297    F back = r;
 298    BOOST_TRY{
 299       while (f != l) {
 300          allocator_traits<Allocator>::construct(a, boost::movelib::iterator_to_raw_pointer(r), boost::move(*f));
 301          ++f; ++r;
 302       }
 303    }
 304    BOOST_CATCH(...){
 305       for (; back != r; ++back){
 306          allocator_traits<Allocator>::destroy(a, boost::movelib::iterator_to_raw_pointer(back));
 307       }
 308       BOOST_RETHROW;
 309    }
 310    BOOST_CATCH_END
 311    return r;
 312 }
 313
 314 template
 315    <typename Allocator,
 316     typename I, // I models InputIterator
 317     typename F> // F models ForwardIterator
 318 inline typename dtl::enable_if_memtransfer_copy_constructible<I, F, F>::type
 319    uninitialized_move_alloc(Allocator &, I f, I l, F r) BOOST_NOEXCEPT_OR_NOTHROW
 320 {  return dtl::memmove(f, l, r); }
 321
 322 //////////////////////////////////////////////////////////////////////////////
 323 //
 324 //                               uninitialized_move_alloc_n
 325 //
 326 //////////////////////////////////////////////////////////////////////////////
 327
 328 //! <b>Effects</b>:
 329 //!   \code
 330 //!   for (; n--; ++r, ++f)
 331 //!      allocator_traits::construct(a, &*r, boost::move(*f));
 332 //!   \endcode
 333 //!
 334 //! <b>Returns</b>: r
 335 template
 336    <typename Allocator,
 337     typename I, // I models InputIterator
 338     typename F> // F models ForwardIterator
 339 inline typename dtl::disable_if_memtransfer_copy_constructible<I, F, F>::type
 340    uninitialized_move_alloc_n(Allocator &a, I f, typename boost::container::allocator_traits<Allocator>::size_type n, F r)
 341 {
 342    F back = r;
 343    BOOST_TRY{
 344       while (n--) {
 345          allocator_traits<Allocator>::construct(a, boost::movelib::iterator_to_raw_pointer(r), boost::move(*f));
 346          ++f; ++r;
 347       }
 348    }
 349    BOOST_CATCH(...){
 350       for (; back != r; ++back){
 351          allocator_traits<Allocator>::destroy(a, boost::movelib::iterator_to_raw_pointer(back));
 352       }
 353       BOOST_RETHROW;
 354    }
 355    BOOST_CATCH_END
 356    return r;
 357 }
 358
 359 template
 360    <typename Allocator,
 361     typename I, // I models InputIterator
 362     typename F> // F models ForwardIterator
 363 inline typename dtl::enable_if_memtransfer_copy_constructible<I, F, F>::type
 364    uninitialized_move_alloc_n(Allocator &, I f, typename boost::container::allocator_traits<Allocator>::size_type n, F r) BOOST_NOEXCEPT_OR_NOTHROW
 365 {  return dtl::memmove_n(f, n, r); }
 366
 367 //////////////////////////////////////////////////////////////////////////////
 368 //
 369 //                               uninitialized_move_alloc_n_source
 370 //
 371 //////////////////////////////////////////////////////////////////////////////
 372
 373 //! <b>Effects</b>:
 374 //!   \code
 375 //!   for (; n--; ++r, ++f)
 376 //!      allocator_traits::construct(a, &*r, boost::move(*f));
 377 //!   \endcode
 378 //!
 379 //! <b>Returns</b>: f (after incremented)
 380 template
 381    <typename Allocator,
 382     typename I, // I models InputIterator
 383     typename F> // F models ForwardIterator
 384 inline typename dtl::disable_if_memtransfer_copy_constructible<I, F, I>::type
 385    uninitialized_move_alloc_n_source(Allocator &a, I f, typename boost::container::allocator_traits<Allocator>::size_type n, F r)
 386 {
 387    F back = r;
 388    BOOST_TRY{
 389       while (n--) {
 390          allocator_traits<Allocator>::construct(a, boost::movelib::iterator_to_raw_pointer(r), boost::move(*f));
 391          ++f; ++r;
 392       }
 393    }
 394    BOOST_CATCH(...){
 395       for (; back != r; ++back){
 396          allocator_traits<Allocator>::destroy(a, boost::movelib::iterator_to_raw_pointer(back));
 397       }
 398       BOOST_RETHROW;
 399    }
 400    BOOST_CATCH_END
 401    return f;
 402 }
 403
 404 template
 405    <typename Allocator,
 406     typename I, // I models InputIterator
 407     typename F> // F models ForwardIterator
 408 inline typename dtl::enable_if_memtransfer_copy_constructible<I, F, I>::type
 409    uninitialized_move_alloc_n_source(Allocator &, I f, typename boost::container::allocator_traits<Allocator>::size_type n, F r) BOOST_NOEXCEPT_OR_NOTHROW
 410 {  return dtl::memmove_n_source(f, n, r); }
 411
 412 //////////////////////////////////////////////////////////////////////////////
 413 //
 414 //                               uninitialized_copy_alloc
 415 //
 416 //////////////////////////////////////////////////////////////////////////////
 417
 418 //! <b>Effects</b>:
 419 //!   \code
 420 //!   for (; f != l; ++r, ++f)
 421 //!      allocator_traits::construct(a, &*r, *f);
 422 //!   \endcode
 423 //!
 424 //! <b>Returns</b>: r
 425 template
 426    <typename Allocator,
 427     typename I, // I models InputIterator
 428     typename F> // F models ForwardIterator
 429 inline typename dtl::disable_if_memtransfer_copy_constructible<I, F, F>::type
 430    uninitialized_copy_alloc(Allocator &a, I f, I l, F r)
 431 {
 432    F back = r;
 433    BOOST_TRY{
 434       while (f != l) {
 435          allocator_traits<Allocator>::construct(a, boost::movelib::iterator_to_raw_pointer(r), *f);
 436          ++f; ++r;
 437       }
 438    }
 439    BOOST_CATCH(...){
 440       for (; back != r; ++back){
 441          allocator_traits<Allocator>::destroy(a, boost::movelib::iterator_to_raw_pointer(back));
 442       }
 443       BOOST_RETHROW;
 444    }
 445    BOOST_CATCH_END
 446    return r;
 447 }
 448
 449 template
 450    <typename Allocator,
 451     typename I, // I models InputIterator
 452     typename F> // F models ForwardIterator
 453 inline typename dtl::enable_if_memtransfer_copy_constructible<I, F, F>::type
 454    uninitialized_copy_alloc(Allocator &, I f, I l, F r) BOOST_NOEXCEPT_OR_NOTHROW
 455 {  return dtl::memmove(f, l, r); }
 456
 457 //////////////////////////////////////////////////////////////////////////////
 458 //
 459 //                               uninitialized_copy_alloc_n
 460 //
 461 //////////////////////////////////////////////////////////////////////////////
 462
 463 //! <b>Effects</b>:
 464 //!   \code
 465 //!   for (; n--; ++r, ++f)
 466 //!      allocator_traits::construct(a, &*r, *f);
 467 //!   \endcode
 468 //!
 469 //! <b>Returns</b>: r
 470 template
 471    <typename Allocator,
 472     typename I, // I models InputIterator
 473     typename F> // F models ForwardIterator
 474 inline typename dtl::disable_if_memtransfer_copy_constructible<I, F, F>::type
 475    uninitialized_copy_alloc_n(Allocator &a, I f, typename boost::container::allocator_traits<Allocator>::size_type n, F r)
 476 {
 477    F back = r;
 478    BOOST_TRY{
 479       while (n--) {
 480          allocator_traits<Allocator>::construct(a, boost::movelib::iterator_to_raw_pointer(r), *f);
 481          ++f; ++r;
 482       }
 483    }
 484    BOOST_CATCH(...){
 485       for (; back != r; ++back){
 486          allocator_traits<Allocator>::destroy(a, boost::movelib::iterator_to_raw_pointer(back));
 487       }
 488       BOOST_RETHROW;
 489    }
 490    BOOST_CATCH_END
 491    return r;
 492 }
 493
 494 template
 495    <typename Allocator,
 496     typename I, // I models InputIterator
 497     typename F> // F models ForwardIterator
 498 inline typename dtl::enable_if_memtransfer_copy_constructible<I, F, F>::type
 499    uninitialized_copy_alloc_n(Allocator &, I f, typename boost::container::allocator_traits<Allocator>::size_type n, F r) BOOST_NOEXCEPT_OR_NOTHROW
 500 {  return dtl::memmove_n(f, n, r); }
 501
 502 //////////////////////////////////////////////////////////////////////////////
 503 //
 504 //                               uninitialized_copy_alloc_n_source
 505 //
 506 //////////////////////////////////////////////////////////////////////////////
 507
 508 //! <b>Effects</b>:
 509 //!   \code
 510 //!   for (; n--; ++r, ++f)
 511 //!      allocator_traits::construct(a, &*r, *f);
 512 //!   \endcode
 513 //!
 514 //! <b>Returns</b>: f (after incremented)
 515 template
 516    <typename Allocator,
 517     typename I, // I models InputIterator
 518     typename F> // F models ForwardIterator
 519 inline typename dtl::disable_if_memtransfer_copy_constructible<I, F, I>::type
 520    uninitialized_copy_alloc_n_source(Allocator &a, I f, typename boost::container::allocator_traits<Allocator>::size_type n, F r)
 521 {
 522    F back = r;
 523    BOOST_TRY{
 524       while (n) {
 525          boost::container::construct_in_place(a, boost::movelib::iterator_to_raw_pointer(r), f);
 526          ++f; ++r; --n;
 527       }
 528    }
 529    BOOST_CATCH(...){
 530       for (; back != r; ++back){
 531          allocator_traits<Allocator>::destroy(a, boost::movelib::iterator_to_raw_pointer(back));
 532       }
 533       BOOST_RETHROW;
 534    }
 535    BOOST_CATCH_END
 536    return f;
 537 }
 538
 539 template
 540    <typename Allocator,
 541     typename I, // I models InputIterator
 542     typename F> // F models ForwardIterator
 543 inline typename dtl::enable_if_memtransfer_copy_constructible<I, F, I>::type
 544    uninitialized_copy_alloc_n_source(Allocator &, I f, typename boost::container::allocator_traits<Allocator>::size_type n, F r) BOOST_NOEXCEPT_OR_NOTHROW
 545 {  return dtl::memmove_n_source(f, n, r); }
 546
 547 //////////////////////////////////////////////////////////////////////////////
 548 //
 549 //                               uninitialized_value_init_alloc_n
 550 //
 551 //////////////////////////////////////////////////////////////////////////////
 552
 553 //! <b>Effects</b>:
 554 //!   \code
 555 //!   for (; n--; ++r, ++f)
 556 //!      allocator_traits::construct(a, &*r);
 557 //!   \endcode
 558 //!
 559 //! <b>Returns</b>: r
 560 template
 561    <typename Allocator,
 562     typename F> // F models ForwardIterator
 563 inline typename dtl::disable_if_memzero_initializable<F, F>::type
 564    uninitialized_value_init_alloc_n(Allocator &a, typename boost::container::allocator_traits<Allocator>::size_type n, F r)
 565 {
 566    F back = r;
 567    BOOST_TRY{
 568       while (n--) {
 569          allocator_traits<Allocator>::construct(a, boost::movelib::iterator_to_raw_pointer(r));
 570          ++r;
 571       }
 572    }
 573    BOOST_CATCH(...){
 574       for (; back != r; ++back){
 575          allocator_traits<Allocator>::destroy(a, boost::movelib::iterator_to_raw_pointer(back));
 576       }
 577       BOOST_RETHROW;
 578    }
 579    BOOST_CATCH_END
 580    return r;
 581 }
 582
 583 template
 584    <typename Allocator,
 585     typename F> // F models ForwardIterator
 586 inline typename dtl::enable_if_memzero_initializable<F, F>::type
 587    uninitialized_value_init_alloc_n(Allocator &, typename boost::container::allocator_traits<Allocator>::size_type n, F r)
 588 {
 589    typedef typename boost::container::iterator_traits<F>::value_type value_type;
 590    std::memset((void*)boost::movelib::iterator_to_raw_pointer(r), 0, sizeof(value_type)*n);
 591    boost::container::iterator_advance(r, n);
 592    return r;
 593 }
 594
 595 //////////////////////////////////////////////////////////////////////////////
 596 //
 597 //                               uninitialized_default_init_alloc_n
 598 //
 599 //////////////////////////////////////////////////////////////////////////////
 600
 601 //! <b>Effects</b>:
 602 //!   \code
 603 //!   for (; n--; ++r, ++f)
 604 //!      allocator_traits::construct(a, &*r);
 605 //!   \endcode
 606 //!
 607 //! <b>Returns</b>: r
 608 template
 609    <typename Allocator,
 610     typename F> // F models ForwardIterator
 611 inline F uninitialized_default_init_alloc_n(Allocator &a, typename boost::container::allocator_traits<Allocator>::size_type n, F r)
 612 {
 613    F back = r;
 614    BOOST_TRY{
 615       while (n--) {
 616          allocator_traits<Allocator>::construct(a, boost::movelib::iterator_to_raw_pointer(r), default_init);
 617          ++r;
 618       }
 619    }
 620    BOOST_CATCH(...){
 621       for (; back != r; ++back){
 622          allocator_traits<Allocator>::destroy(a, boost::movelib::iterator_to_raw_pointer(back));
 623       }
 624       BOOST_RETHROW;
 625    }
 626    BOOST_CATCH_END
 627    return r;
 628 }
 629
 630 //////////////////////////////////////////////////////////////////////////////
 631 //
 632 //                               uninitialized_fill_alloc
 633 //
 634 //////////////////////////////////////////////////////////////////////////////
 635
 636 //! <b>Effects</b>:
 637 //!   \code
 638 //!   for (; f != l; ++r, ++f)
 639 //!      allocator_traits::construct(a, &*r, *f);
 640 //!   \endcode
 641 //!
 642 //! <b>Returns</b>: r
 643 template
 644    <typename Allocator,
 645     typename F, // F models ForwardIterator
 646     typename T>
 647 inline void uninitialized_fill_alloc(Allocator &a, F f, F l, const T &t)
 648 {
 649    F back = f;
 650    BOOST_TRY{
 651       while (f != l) {
 652          allocator_traits<Allocator>::construct(a, boost::movelib::iterator_to_raw_pointer(f), t);
 653          ++f;
 654       }
 655    }
 656    BOOST_CATCH(...){
 657       for (; back != l; ++back){
 658          allocator_traits<Allocator>::destroy(a, boost::movelib::iterator_to_raw_pointer(back));
 659       }
 660       BOOST_RETHROW;
 661    }
 662    BOOST_CATCH_END
 663 }
 664
 665
 666 //////////////////////////////////////////////////////////////////////////////
 667 //
 668 //                               uninitialized_fill_alloc_n
 669 //
 670 //////////////////////////////////////////////////////////////////////////////
 671
 672 //! <b>Effects</b>:
 673 //!   \code
 674 //!   for (; n--; ++r, ++f)
 675 //!      allocator_traits::construct(a, &*r, v);
 676 //!   \endcode
 677 //!
 678 //! <b>Returns</b>: r
 679 template
 680    <typename Allocator,
 681     typename T,
 682     typename F> // F models ForwardIterator
 683 inline F uninitialized_fill_alloc_n(Allocator &a, const T &v, typename boost::container::allocator_traits<Allocator>::size_type n, F r)
 684 {
 685    F back = r;
 686    BOOST_TRY{
 687       while (n--) {
 688          allocator_traits<Allocator>::construct(a, boost::movelib::iterator_to_raw_pointer(r), v);
 689          ++r;
 690       }
 691    }
 692    BOOST_CATCH(...){
 693       for (; back != r; ++back){
 694          allocator_traits<Allocator>::destroy(a, boost::movelib::iterator_to_raw_pointer(back));
 695       }
 696       BOOST_RETHROW;
 697    }
 698    BOOST_CATCH_END
 699    return r;
 700 }
 701
 702 //////////////////////////////////////////////////////////////////////////////
 703 //
 704 //                               copy
 705 //
 706 //////////////////////////////////////////////////////////////////////////////
 707
 708 template
 709 <typename I,   // I models InputIterator
 710 typename F>    // F models ForwardIterator
 711 inline typename dtl::disable_if_memtransfer_copy_assignable<I, F, F>::type
 712    copy(I f, I l, F r)
 713 {
 714    while (f != l) {
 715       *r = *f;
 716       ++f; ++r;
 717    }
 718    return r;
 719 }
 720
 721 template
 722 <typename I,   // I models InputIterator
 723 typename F>    // F models ForwardIterator
 724 inline typename dtl::enable_if_memtransfer_copy_assignable<I, F, F>::type
 725    copy(I f, I l, F r) BOOST_NOEXCEPT_OR_NOTHROW
 726 {  return dtl::memmove(f, l, r); }
 727
 728 //////////////////////////////////////////////////////////////////////////////
 729 //
 730 //                               copy_n
 731 //
 732 //////////////////////////////////////////////////////////////////////////////
 733
 734 template
 735 <typename I,   // I models InputIterator
 736 typename U,   // U models unsigned integral constant
 737 typename F>   // F models ForwardIterator
 738 inline typename dtl::disable_if_memtransfer_copy_assignable<I, F, F>::type
 739    copy_n(I f, U n, F r)
 740 {
 741    while (n) {
 742       --n;
 743       *r = *f;
 744       ++f; ++r;
 745    }
 746    return r;
 747 }
 748
 749 template
 750 <typename I,   // I models InputIterator
 751 typename U,   // U models unsigned integral constant
 752 typename F>   // F models ForwardIterator
 753 inline typename dtl::enable_if_memtransfer_copy_assignable<I, F, F>::type
 754    copy_n(I f, U n, F r) BOOST_NOEXCEPT_OR_NOTHROW
 755 {  return dtl::memmove_n(f, n, r); }
 756
 757 //////////////////////////////////////////////////////////////////////////////
 758 //
 759 //                            copy_n_source
 760 //
 761 //////////////////////////////////////////////////////////////////////////////
 762
 763 template
 764 <typename I,   // I models InputIterator
 765 typename U,   // U models unsigned integral constant
 766 typename F>   // F models ForwardIterator
 767 inline typename dtl::disable_if_memtransfer_copy_assignable<I, F, I>::type
 768    copy_n_source(I f, U n, F r)
 769 {
 770    while (n--) {
 771       boost::container::assign_in_place(r, f);
 772       ++f; ++r;
 773    }
 774    return f;
 775 }
 776
 777 template
 778 <typename I,   // I models InputIterator
 779 typename U,   // U models unsigned integral constant
 780 typename F>   // F models ForwardIterator
 781 inline typename dtl::enable_if_memtransfer_copy_assignable<I, F, I>::type
 782    copy_n_source(I f, U n, F r) BOOST_NOEXCEPT_OR_NOTHROW
 783 {  return dtl::memmove_n_source(f, n, r); }
 784
 785 //////////////////////////////////////////////////////////////////////////////
 786 //
 787 //                            copy_n_source_dest
 788 //
 789 //////////////////////////////////////////////////////////////////////////////
 790
 791 template
 792 <typename I,   // I models InputIterator
 793 typename U,   // U models unsigned integral constant
 794 typename F>   // F models ForwardIterator
 795 inline typename dtl::disable_if_memtransfer_copy_assignable<I, F, I>::type
 796    copy_n_source_dest(I f, U n, F &r)
 797 {
 798    while (n--) {
 799       *r = *f;
 800       ++f; ++r;
 801    }
 802    return f;
 803 }
 804
 805 template
 806 <typename I,   // I models InputIterator
 807 typename U,   // U models unsigned integral constant
 808 typename F>   // F models ForwardIterator
 809 inline typename dtl::enable_if_memtransfer_copy_assignable<I, F, I>::type
 810    copy_n_source_dest(I f, U n, F &r) BOOST_NOEXCEPT_OR_NOTHROW
 811 {  return dtl::memmove_n_source_dest(f, n, r);  }
 812
 813 //////////////////////////////////////////////////////////////////////////////
 814 //
 815 //                         move
 816 //
 817 //////////////////////////////////////////////////////////////////////////////
 818
 819 template
 820 <typename I,   // I models InputIterator
 821 typename F>   // F models ForwardIterator
 822 inline typename dtl::disable_if_memtransfer_copy_assignable<I, F, F>::type
 823    move(I f, I l, F r)
 824 {
 825    while (f != l) {
 826       *r = ::boost::move(*f);
 827       ++f; ++r;
 828    }
 829    return r;
 830 }
 831
 832 template
 833 <typename I,   // I models InputIterator
 834 typename F>   // F models ForwardIterator
 835 inline typename dtl::enable_if_memtransfer_copy_assignable<I, F, F>::type
 836    move(I f, I l, F r) BOOST_NOEXCEPT_OR_NOTHROW
 837 {  return dtl::memmove(f, l, r); }
 838
 839 //////////////////////////////////////////////////////////////////////////////
 840 //
 841 //                         move_n
 842 //
 843 //////////////////////////////////////////////////////////////////////////////
 844
 845 template
 846 <typename I,   // I models InputIterator
 847 typename U,   // U models unsigned integral constant
 848 typename F>   // F models ForwardIterator
 849 inline typename dtl::disable_if_memtransfer_copy_assignable<I, F, F>::type
 850    move_n(I f, U n, F r)
 851 {
 852    while (n--) {
 853       *r = ::boost::move(*f);
 854       ++f; ++r;
 855    }
 856    return r;
 857 }
 858
 859 template
 860 <typename I,   // I models InputIterator
 861 typename U,   // U models unsigned integral constant
 862 typename F>   // F models ForwardIterator
 863 inline typename dtl::enable_if_memtransfer_copy_assignable<I, F, F>::type
 864    move_n(I f, U n, F r) BOOST_NOEXCEPT_OR_NOTHROW
 865 {  return dtl::memmove_n(f, n, r); }
 866
 867
 868 //////////////////////////////////////////////////////////////////////////////
 869 //
 870 //                         move_backward
 871 //
 872 //////////////////////////////////////////////////////////////////////////////
 873
 874 template
 875 <typename I,   // I models BidirectionalIterator
 876 typename F>    // F models ForwardIterator
 877 inline typename dtl::disable_if_memtransfer_copy_assignable<I, F, F>::type
 878    move_backward(I f, I l, F r)
 879 {
 880    while (f != l) {
 881       --l; --r;
 882       *r = ::boost::move(*l);
 883    }
 884    return r;
 885 }
 886
 887 template
 888 <typename I,   // I models InputIterator
 889 typename F>   // F models ForwardIterator
 890 inline typename dtl::enable_if_memtransfer_copy_assignable<I, F, F>::type
 891    move_backward(I f, I l, F r) BOOST_NOEXCEPT_OR_NOTHROW
 892 {
 893    typedef typename boost::container::iterator_traits<I>::value_type value_type;
 894    const typename boost::container::iterator_traits<I>::difference_type n = boost::container::iterator_distance(f, l);
 895    r -= n;
 896    std::memmove((boost::movelib::iterator_to_raw_pointer)(r), (boost::movelib::iterator_to_raw_pointer)(f), sizeof(value_type)*n);
 897    return r;
 898 }
 899
 900 //////////////////////////////////////////////////////////////////////////////
 901 //
 902 //                         move_n_source_dest
 903 //
 904 //////////////////////////////////////////////////////////////////////////////
 905
 906 template
 907 <typename I    // I models InputIterator
 908 ,typename U    // U models unsigned integral constant
 909 ,typename F>   // F models ForwardIterator
 910 inline typename dtl::disable_if_memtransfer_copy_assignable<I, F, I>::type
 911    move_n_source_dest(I f, U n, F &r)
 912 {
 913    while (n--) {
 914       *r = ::boost::move(*f);
 915       ++f; ++r;
 916    }
 917    return f;
 918 }
 919
 920 template
 921 <typename I    // I models InputIterator
 922 ,typename U    // U models unsigned integral constant
 923 ,typename F>   // F models ForwardIterator
 924 inline typename dtl::enable_if_memtransfer_copy_assignable<I, F, I>::type
 925    move_n_source_dest(I f, U n, F &r) BOOST_NOEXCEPT_OR_NOTHROW
 926 {  return dtl::memmove_n_source_dest(f, n, r); }
 927
 928 //////////////////////////////////////////////////////////////////////////////
 929 //
 930 //                         move_n_source
 931 //
 932 //////////////////////////////////////////////////////////////////////////////
 933
 934 template
 935 <typename I    // I models InputIterator
 936 ,typename U    // U models unsigned integral constant
 937 ,typename F>   // F models ForwardIterator
 938 inline typename dtl::disable_if_memtransfer_copy_assignable<I, F, I>::type
 939    move_n_source(I f, U n, F r)
 940 {
 941    while (n--) {
 942       *r = ::boost::move(*f);
 943       ++f; ++r;
 944    }
 945    return f;
 946 }
 947
 948 template
 949 <typename I    // I models InputIterator
 950 ,typename U    // U models unsigned integral constant
 951 ,typename F>   // F models ForwardIterator
 952 inline typename dtl::enable_if_memtransfer_copy_assignable<I, F, I>::type
 953    move_n_source(I f, U n, F r) BOOST_NOEXCEPT_OR_NOTHROW
 954 {  return dtl::memmove_n_source(f, n, r); }
 955
 956 //////////////////////////////////////////////////////////////////////////////
 957 //
 958 //                               destroy_alloc_n
 959 //
 960 //////////////////////////////////////////////////////////////////////////////
 961
 962 template
 963    <typename Allocator
 964    ,typename I   // I models InputIterator
 965    ,typename U>  // U models unsigned integral constant
 966 inline typename dtl::disable_if_trivially_destructible<I, void>::type
 967    destroy_alloc_n(Allocator &a, I f, U n)
 968 {
 969    while(n){
 970       --n;
 971       allocator_traits<Allocator>::destroy(a, boost::movelib::iterator_to_raw_pointer(f));
 972       ++f;
 973    }
 974 }
 975
 976 template
 977    <typename Allocator
 978    ,typename I   // I models InputIterator
 979    ,typename U>  // U models unsigned integral constant
 980 inline typename dtl::enable_if_trivially_destructible<I, void>::type
 981    destroy_alloc_n(Allocator &, I, U)
 982 {}
 983
 984 //////////////////////////////////////////////////////////////////////////////
 985 //
 986 //                         deep_swap_alloc_n
 987 //
 988 //////////////////////////////////////////////////////////////////////////////
 989
 990 template
 991    <std::size_t MaxTmpBytes
 992    ,typename Allocator
 993    ,typename F // F models ForwardIterator
 994    ,typename G // G models ForwardIterator
 995    >
 996 inline typename dtl::disable_if_memtransfer_copy_assignable<F, G, void>::type
 997    deep_swap_alloc_n( Allocator &a, F short_range_f, typename allocator_traits<Allocator>::size_type n_i
 998                     , G large_range_f, typename allocator_traits<Allocator>::size_type n_j)
 999 {
1000    typename allocator_traits<Allocator>::size_type n = 0;
1001    for (; n != n_i ; ++short_range_f, ++large_range_f, ++n){
1002       boost::adl_move_swap(*short_range_f, *large_range_f);
1003    }
1004    boost::container::uninitialized_move_alloc_n(a, large_range_f, n_j - n_i, short_range_f);  // may throw
1005    boost::container::destroy_alloc_n(a, large_range_f, n_j - n_i);
1006 }
1007
1008 static const std::size_t DeepSwapAllocNMaxStorage = std::size_t(1) << std::size_t(11); //2K bytes
1009
1010 template
1011    <std::size_t MaxTmpBytes
1012    ,typename Allocator
1013    ,typename F // F models ForwardIterator
1014    ,typename G // G models ForwardIterator
1015    >
1016 inline typename dtl::enable_if_c
1017    < dtl::is_memtransfer_copy_assignable<F, G>::value && (MaxTmpBytes <= DeepSwapAllocNMaxStorage) && false
1018    , void>::type
1019    deep_swap_alloc_n( Allocator &a, F short_range_f, typename allocator_traits<Allocator>::size_type n_i
1020                     , G large_range_f, typename allocator_traits<Allocator>::size_type n_j)
1021 {
1022    typedef typename allocator_traits<Allocator>::value_type value_type;
1023    typedef typename dtl::aligned_storage
1024       <MaxTmpBytes, dtl::alignment_of<value_type>::value>::type storage_type;
1025    storage_type storage;
1026
1027    const std::size_t n_i_bytes = sizeof(value_type)*n_i;
1028    void *const large_ptr = static_cast<void*>(boost::movelib::iterator_to_raw_pointer(large_range_f));
1029    void *const short_ptr = static_cast<void*>(boost::movelib::iterator_to_raw_pointer(short_range_f));
1030    void *const stora_ptr = static_cast<void*>(boost::movelib::iterator_to_raw_pointer(storage.data));
1031    std::memcpy(stora_ptr, large_ptr, n_i_bytes);
1032    std::memcpy(large_ptr, short_ptr, n_i_bytes);
1033    std::memcpy(short_ptr, stora_ptr, n_i_bytes);
1034    boost::container::iterator_advance(large_range_f, n_i);
1035    boost::container::iterator_advance(short_range_f, n_i);
1036    boost::container::uninitialized_move_alloc_n(a, large_range_f, n_j - n_i, short_range_f);  // may throw
1037    boost::container::destroy_alloc_n(a, large_range_f, n_j - n_i);
1038 }
1039
1040 template
1041    <std::size_t MaxTmpBytes
1042    ,typename Allocator
1043    ,typename F // F models ForwardIterator
1044    ,typename G // G models ForwardIterator
1045    >
1046 inline typename dtl::enable_if_c
1047    < dtl::is_memtransfer_copy_assignable<F, G>::value && true//(MaxTmpBytes > DeepSwapAllocNMaxStorage)
1048    , void>::type
1049    deep_swap_alloc_n( Allocator &a, F short_range_f, typename allocator_traits<Allocator>::size_type n_i
1050                     , G large_range_f, typename allocator_traits<Allocator>::size_type n_j)
1051 {
1052    typedef typename allocator_traits<Allocator>::value_type value_type;
1053    typedef typename dtl::aligned_storage
1054       <DeepSwapAllocNMaxStorage, dtl::alignment_of<value_type>::value>::type storage_type;
1055    storage_type storage;
1056    const std::size_t sizeof_storage = sizeof(storage);
1057
1058    std::size_t n_i_bytes = sizeof(value_type)*n_i;
1059    char *large_ptr = static_cast<char*>(static_cast<void*>(boost::movelib::iterator_to_raw_pointer(large_range_f)));
1060    char *short_ptr = static_cast<char*>(static_cast<void*>(boost::movelib::iterator_to_raw_pointer(short_range_f)));
1061    char *stora_ptr = static_cast<char*>(static_cast<void*>(storage.data));
1062
1063    std::size_t szt_times = n_i_bytes/sizeof_storage;
1064    const std::size_t szt_rem = n_i_bytes%sizeof_storage;
1065
1066    //Loop unrolling using Duff's device, as it seems it helps on some architectures
1067    const std::size_t Unroll = 4;
1068    std::size_t n = (szt_times + (Unroll-1))/Unroll;
1069    const std::size_t branch_number = (!szt_times)*Unroll + (szt_times % Unroll);
1070    switch(branch_number){
1071       case 4:
1072          break;
1073       case 0: do{
1074          std::memcpy(stora_ptr, large_ptr, sizeof_storage);
1075          std::memcpy(large_ptr, short_ptr, sizeof_storage);
1076          std::memcpy(short_ptr, stora_ptr, sizeof_storage);
1077          large_ptr += sizeof_storage;
1078          short_ptr += sizeof_storage;
1079          BOOST_FALLTHROUGH;
1080       case 3:
1081          std::memcpy(stora_ptr, large_ptr, sizeof_storage);
1082          std::memcpy(large_ptr, short_ptr, sizeof_storage);
1083          std::memcpy(short_ptr, stora_ptr, sizeof_storage);
1084          large_ptr += sizeof_storage;
1085          short_ptr += sizeof_storage;
1086          BOOST_FALLTHROUGH;
1087       case 2:
1088          std::memcpy(stora_ptr, large_ptr, sizeof_storage);
1089          std::memcpy(large_ptr, short_ptr, sizeof_storage);
1090          std::memcpy(short_ptr, stora_ptr, sizeof_storage);
1091          large_ptr += sizeof_storage;
1092          short_ptr += sizeof_storage;
1093          BOOST_FALLTHROUGH;
1094       case 1:
1095          std::memcpy(stora_ptr, large_ptr, sizeof_storage);
1096          std::memcpy(large_ptr, short_ptr, sizeof_storage);
1097          std::memcpy(short_ptr, stora_ptr, sizeof_storage);
1098          large_ptr += sizeof_storage;
1099          short_ptr += sizeof_storage;
1100          } while(--n);
1101    }
1102    std::memcpy(stora_ptr, large_ptr, szt_rem);
1103    std::memcpy(large_ptr, short_ptr, szt_rem);
1104    std::memcpy(short_ptr, stora_ptr, szt_rem);
1105    boost::container::iterator_advance(large_range_f, n_i);
1106    boost::container::iterator_advance(short_range_f, n_i);
1107    boost::container::uninitialized_move_alloc_n(a, large_range_f, n_j - n_i, short_range_f);  // may throw
1108    boost::container::destroy_alloc_n(a, large_range_f, n_j - n_i);
1109 }
1110
1111
1112 //////////////////////////////////////////////////////////////////////////////
1113 //
1114 //                         copy_assign_range_alloc_n
1115 //
1116 //////////////////////////////////////////////////////////////////////////////
1117
1118 template
1119    <typename Allocator
1120    ,typename I // F models InputIterator
1121    ,typename O // G models OutputIterator
1122    >
1123 void copy_assign_range_alloc_n( Allocator &a, I inp_start, typename allocator_traits<Allocator>::size_type n_i
1124                               , O out_start, typename allocator_traits<Allocator>::size_type n_o )
1125 {
1126    if (n_o < n_i){
1127       inp_start = boost::container::copy_n_source_dest(inp_start, n_o, out_start);     // may throw
1128       boost::container::uninitialized_copy_alloc_n(a, inp_start, n_i - n_o, out_start);// may throw
1129    }
1130    else{
1131       out_start = boost::container::copy_n(inp_start, n_i, out_start);  // may throw
1132       boost::container::destroy_alloc_n(a, out_start, n_o - n_i);
1133    }
1134 }
1135
1136 //////////////////////////////////////////////////////////////////////////////
1137 //
1138 //                         move_assign_range_alloc_n
1139 //
1140 //////////////////////////////////////////////////////////////////////////////
1141
1142 template
1143    <typename Allocator
1144    ,typename I // F models InputIterator
1145    ,typename O // G models OutputIterator
1146    >
1147 void move_assign_range_alloc_n( Allocator &a, I inp_start, typename allocator_traits<Allocator>::size_type n_i
1148                               , O out_start, typename allocator_traits<Allocator>::size_type n_o )
1149 {
1150    if (n_o < n_i){
1151       inp_start = boost::container::move_n_source_dest(inp_start, n_o, out_start);  // may throw
1152       boost::container::uninitialized_move_alloc_n(a, inp_start, n_i - n_o, out_start);  // may throw
1153    }
1154    else{
1155       out_start = boost::container::move_n(inp_start, n_i, out_start);  // may throw
1156       boost::container::destroy_alloc_n(a, out_start, n_o - n_i);
1157    }
1158 }
1159
1160 }  //namespace container {
1161 }  //namespace boost {
1162
1163 //#pragma GCC diagnostic ignored "-Wclass-memaccess"
1164 #if defined(BOOST_GCC) && (BOOST_GCC >= 40600)
1165 #pragma GCC diagnostic pop
1166 #endif
1167
1168 #endif   //#ifndef BOOST_CONTAINER_DETAIL_COPY_MOVE_ALGO_HPP