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
39namespace boost {
40namespace container {
41namespace container_detail {
42
43template<class I>
44struct are_elements_contiguous
45{
46 static const bool value = false;
47};
48
49/////////////////////////
50// raw pointers
51/////////////////////////
52
53template<class T>
54struct are_elements_contiguous<T*>
55{
56 static const bool value = true;
57};
58
59/////////////////////////
60// move iterators
61/////////////////////////
62
63template<class It>
64struct 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
74template<class Pointer>
75class vector_iterator;
76
77template<class Pointer>
78class vector_const_iterator;
79
80#endif //BOOST_CONTAINER_VECTOR_ITERATOR_IS_POINTER
81
82} //namespace container_detail {
83} //namespace container {
84
85namespace interprocess {
86
87template <class PointedType, class DifferenceType, class OffsetType, std::size_t OffsetAlignment>
88class offset_ptr;
89
90} //namespace interprocess {
91
92namespace container {
93
94namespace container_detail {
95
96/////////////////////////
97//vector_[const_]iterator
98/////////////////////////
99
100#ifndef BOOST_CONTAINER_VECTOR_ITERATOR_IS_POINTER
101
102template<class Pointer>
103struct are_elements_contiguous<boost::container::container_detail::vector_iterator<Pointer> >
104{
105 static const bool value = true;
106};
107
108template<class Pointer>
109struct 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
120template <class PointedType, class DifferenceType, class OffsetType, std::size_t OffsetAlignment>
121struct are_elements_contiguous< ::boost::interprocess::offset_ptr<PointedType, DifferenceType, OffsetType, OffsetAlignment> >
122{
123 static const bool value = true;
124};
125
126template <typename I, typename O>
127struct 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
137template <typename I, typename O>
138struct 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
145template <typename I, typename O>
146struct 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
153template <typename I, typename O, typename R>
154struct enable_if_memtransfer_copy_constructible
155 : enable_if<container_detail::is_memtransfer_copy_constructible<I, O>, R>
156{};
157
158template <typename I, typename O, typename R>
159struct disable_if_memtransfer_copy_constructible
160 : disable_if<container_detail::is_memtransfer_copy_constructible<I, O>, R>
161{};
162
163template <typename I, typename O, typename R>
164struct enable_if_memtransfer_copy_assignable
165 : enable_if<container_detail::is_memtransfer_copy_assignable<I, O>, R>
166{};
167
168template <typename I, typename O, typename R>
169struct disable_if_memtransfer_copy_assignable
170 : disable_if<container_detail::is_memtransfer_copy_assignable<I, O>, R>
171{};
172
173template
174 <typename I, // I models InputIterator
175 typename F> // F models ForwardIterator
176inline 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
187template
188 <typename I, // I models InputIterator
189 typename U, // U models unsigned integral constant
190 typename F> // F models ForwardIterator
191F 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
201template
202 <typename I, // I models InputIterator
203 typename U, // U models unsigned integral constant
204 typename F> // F models ForwardIterator
205I 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
215template
216 <typename I, // I models InputIterator
217 typename U, // U models unsigned integral constant
218 typename F> // F models ForwardIterator
219I 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
230template <typename O>
231struct 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
248template <typename O, typename R>
249struct enable_if_memzero_initializable
250 : enable_if_c<container_detail::is_memzero_initializable<O>::value, R>
251{};
252
253template <typename O, typename R>
254struct disable_if_memzero_initializable
255 : enable_if_c<!container_detail::is_memzero_initializable<O>::value, R>
256{};
257
258template <typename I, typename R>
259struct 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
265template <typename I, typename R>
266struct 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
288template
289 <typename Allocator,
290 typename I, // I models InputIterator
291 typename F> // F models ForwardIterator
292inline typename container_detail::disable_if_memtransfer_copy_constructible<I, F, F>::type
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
312template
313 <typename Allocator,
314 typename I, // I models InputIterator
315 typename F> // F models ForwardIterator
316inline typename container_detail::enable_if_memtransfer_copy_constructible<I, F, F>::type
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
333template
334 <typename Allocator,
335 typename I, // I models InputIterator
336 typename F> // F models ForwardIterator
337inline typename container_detail::disable_if_memtransfer_copy_constructible<I, F, F>::type
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
357template
358 <typename Allocator,
359 typename I, // I models InputIterator
360 typename F> // F models ForwardIterator
361inline typename container_detail::enable_if_memtransfer_copy_constructible<I, F, F>::type
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)
378template
379 <typename Allocator,
380 typename I, // I models InputIterator
381 typename F> // F models ForwardIterator
382inline typename container_detail::disable_if_memtransfer_copy_constructible<I, F, I>::type
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
402template
403 <typename Allocator,
404 typename I, // I models InputIterator
405 typename F> // F models ForwardIterator
406inline typename container_detail::enable_if_memtransfer_copy_constructible<I, F, I>::type
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
423template
424 <typename Allocator,
425 typename I, // I models InputIterator
426 typename F> // F models ForwardIterator
427inline typename container_detail::disable_if_memtransfer_copy_constructible<I, F, F>::type
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
447template
448 <typename Allocator,
449 typename I, // I models InputIterator
450 typename F> // F models ForwardIterator
451inline typename container_detail::enable_if_memtransfer_copy_constructible<I, F, F>::type
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
468template
469 <typename Allocator,
470 typename I, // I models InputIterator
471 typename F> // F models ForwardIterator
472inline typename container_detail::disable_if_memtransfer_copy_constructible<I, F, F>::type
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
492template
493 <typename Allocator,
494 typename I, // I models InputIterator
495 typename F> // F models ForwardIterator
496inline typename container_detail::enable_if_memtransfer_copy_constructible<I, F, F>::type
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)
513template
514 <typename Allocator,
515 typename I, // I models InputIterator
516 typename F> // F models ForwardIterator
517inline typename container_detail::disable_if_memtransfer_copy_constructible<I, F, I>::type
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
537template
538 <typename Allocator,
539 typename I, // I models InputIterator
540 typename F> // F models ForwardIterator
541inline typename container_detail::enable_if_memtransfer_copy_constructible<I, F, I>::type
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
558template
559 <typename Allocator,
560 typename F> // F models ForwardIterator
561inline typename container_detail::disable_if_memzero_initializable<F, F>::type
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
581template
582 <typename Allocator,
583 typename F> // F models ForwardIterator
584inline typename container_detail::enable_if_memzero_initializable<F, F>::type
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
606template
607 <typename Allocator,
608 typename F> // F models ForwardIterator
609inline 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
641template
642 <typename Allocator,
643 typename F, // F models ForwardIterator
644 typename T>
645inline 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
677template
678 <typename Allocator,
679 typename T,
680 typename F> // F models ForwardIterator
681inline 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
706template
707<typename I, // I models InputIterator
708typename F> // F models ForwardIterator
709inline typename container_detail::disable_if_memtransfer_copy_assignable<I, F, F>::type
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
719template
720<typename I, // I models InputIterator
721typename F> // F models ForwardIterator
722inline typename container_detail::enable_if_memtransfer_copy_assignable<I, F, F>::type
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
732template
733<typename I, // I models InputIterator
734typename U, // U models unsigned integral constant
735typename F> // F models ForwardIterator
736inline typename container_detail::disable_if_memtransfer_copy_assignable<I, F, F>::type
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
746template
747<typename I, // I models InputIterator
748typename U, // U models unsigned integral constant
749typename F> // F models ForwardIterator
750inline typename container_detail::enable_if_memtransfer_copy_assignable<I, F, F>::type
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
760template
761<typename I, // I models InputIterator
762typename U, // U models unsigned integral constant
763typename F> // F models ForwardIterator
764inline typename container_detail::disable_if_memtransfer_copy_assignable<I, F, I>::type
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
774template
775<typename I, // I models InputIterator
776typename U, // U models unsigned integral constant
777typename F> // F models ForwardIterator
778inline typename container_detail::enable_if_memtransfer_copy_assignable<I, F, I>::type
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
788template
789<typename I, // I models InputIterator
790typename U, // U models unsigned integral constant
791typename F> // F models ForwardIterator
792inline typename container_detail::disable_if_memtransfer_copy_assignable<I, F, I>::type
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
802template
803<typename I, // I models InputIterator
804typename U, // U models unsigned integral constant
805typename F> // F models ForwardIterator
806inline typename container_detail::enable_if_memtransfer_copy_assignable<I, F, I>::type
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
816template
817<typename I, // I models InputIterator
818typename F> // F models ForwardIterator
819inline typename container_detail::disable_if_memtransfer_copy_assignable<I, F, F>::type
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
829template
830<typename I, // I models InputIterator
831typename F> // F models ForwardIterator
832inline typename container_detail::enable_if_memtransfer_copy_assignable<I, F, F>::type
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
842template
843<typename I, // I models InputIterator
844typename U, // U models unsigned integral constant
845typename F> // F models ForwardIterator
846inline typename container_detail::disable_if_memtransfer_copy_assignable<I, F, F>::type
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
856template
857<typename I, // I models InputIterator
858typename U, // U models unsigned integral constant
859typename F> // F models ForwardIterator
860inline typename container_detail::enable_if_memtransfer_copy_assignable<I, F, F>::type
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
871template
872<typename I, // I models BidirectionalIterator
873typename F> // F models ForwardIterator
874inline typename container_detail::disable_if_memtransfer_copy_assignable<I, F, F>::type
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
884template
885<typename I, // I models InputIterator
886typename F> // F models ForwardIterator
887inline typename container_detail::enable_if_memtransfer_copy_assignable<I, F, F>::type
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
903template
904<typename I // I models InputIterator
905,typename U // U models unsigned integral constant
906,typename F> // F models ForwardIterator
907inline typename container_detail::disable_if_memtransfer_copy_assignable<I, F, I>::type
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
917template
918<typename I // I models InputIterator
919,typename U // U models unsigned integral constant
920,typename F> // F models ForwardIterator
921inline typename container_detail::enable_if_memtransfer_copy_assignable<I, F, I>::type
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
931template
932<typename I // I models InputIterator
933,typename U // U models unsigned integral constant
934,typename F> // F models ForwardIterator
935inline typename container_detail::disable_if_memtransfer_copy_assignable<I, F, I>::type
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
945template
946<typename I // I models InputIterator
947,typename U // U models unsigned integral constant
948,typename F> // F models ForwardIterator
949inline typename container_detail::enable_if_memtransfer_copy_assignable<I, F, I>::type
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
959template
960 <typename Allocator
961 ,typename I // I models InputIterator
962 ,typename U> // U models unsigned integral constant
963inline typename container_detail::disable_if_trivially_destructible<I, void>::type
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
973template
974 <typename Allocator
975 ,typename I // I models InputIterator
976 ,typename U> // U models unsigned integral constant
977inline typename container_detail::enable_if_trivially_destructible<I, void>::type
978 destroy_alloc_n(Allocator &, I, U)
979{}
980
981//////////////////////////////////////////////////////////////////////////////
982//
983// deep_swap_alloc_n
984//
985//////////////////////////////////////////////////////////////////////////////
986
987template
988 <std::size_t MaxTmpBytes
989 ,typename Allocator
990 ,typename F // F models ForwardIterator
991 ,typename G // G models ForwardIterator
992 >
993inline typename container_detail::disable_if_memtransfer_copy_assignable<F, G, void>::type
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
1005static const std::size_t DeepSwapAllocNMaxStorage = std::size_t(1) << std::size_t(11); //2K bytes
1006
1007template
1008 <std::size_t MaxTmpBytes
1009 ,typename Allocator
1010 ,typename F // F models ForwardIterator
1011 ,typename G // G models ForwardIterator
1012 >
1013inline typename container_detail::enable_if_c
1014 < container_detail::is_memtransfer_copy_assignable<F, G>::value && (MaxTmpBytes <= DeepSwapAllocNMaxStorage) && false
1015 , void>::type
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
1037template
1038 <std::size_t MaxTmpBytes
1039 ,typename Allocator
1040 ,typename F // F models ForwardIterator
1041 ,typename G // G models ForwardIterator
1042 >
1043inline typename container_detail::enable_if_c
1044 < container_detail::is_memtransfer_copy_assignable<F, G>::value && true//(MaxTmpBytes > DeepSwapAllocNMaxStorage)
1045 , void>::type
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
1115template
1116 <typename Allocator
1117 ,typename I // F models InputIterator
1118 ,typename O // G models OutputIterator
1119 >
1120void 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
1139template
1140 <typename Allocator
1141 ,typename I // F models InputIterator
1142 ,typename O // G models OutputIterator
1143 >
1144void 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