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