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