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