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