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