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
memmove_n_source(I f,U n,F r)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
memmove_n_source_dest(I f,U n,F & r)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 if (BOOST_LIKELY(n)){
591 std::memset((void*)boost::movelib::iterator_to_raw_pointer(r), 0, sizeof(value_type)*n);
592 boost::container::iterator_advance(r, n);
593 }
594 return r;
595 }
596
597 //////////////////////////////////////////////////////////////////////////////
598 //
599 // uninitialized_default_init_alloc_n
600 //
601 //////////////////////////////////////////////////////////////////////////////
602
603 //! <b>Effects</b>:
604 //! \code
605 //! for (; n--; ++r, ++f)
606 //! allocator_traits::construct(a, &*r);
607 //! \endcode
608 //!
609 //! <b>Returns</b>: r
610 template
611 <typename Allocator,
612 typename F> // F models ForwardIterator
uninitialized_default_init_alloc_n(Allocator & a,typename boost::container::allocator_traits<Allocator>::size_type n,F r)613 inline F uninitialized_default_init_alloc_n(Allocator &a, typename boost::container::allocator_traits<Allocator>::size_type n, F r)
614 {
615 F back = r;
616 BOOST_TRY{
617 while (n--) {
618 allocator_traits<Allocator>::construct(a, boost::movelib::iterator_to_raw_pointer(r), default_init);
619 ++r;
620 }
621 }
622 BOOST_CATCH(...){
623 for (; back != r; ++back){
624 allocator_traits<Allocator>::destroy(a, boost::movelib::iterator_to_raw_pointer(back));
625 }
626 BOOST_RETHROW;
627 }
628 BOOST_CATCH_END
629 return r;
630 }
631
632 //////////////////////////////////////////////////////////////////////////////
633 //
634 // uninitialized_fill_alloc
635 //
636 //////////////////////////////////////////////////////////////////////////////
637
638 //! <b>Effects</b>:
639 //! \code
640 //! for (; f != l; ++r, ++f)
641 //! allocator_traits::construct(a, &*r, *f);
642 //! \endcode
643 //!
644 //! <b>Returns</b>: r
645 template
646 <typename Allocator,
647 typename F, // F models ForwardIterator
648 typename T>
uninitialized_fill_alloc(Allocator & a,F f,F l,const T & t)649 inline void uninitialized_fill_alloc(Allocator &a, F f, F l, const T &t)
650 {
651 F back = f;
652 BOOST_TRY{
653 while (f != l) {
654 allocator_traits<Allocator>::construct(a, boost::movelib::iterator_to_raw_pointer(f), t);
655 ++f;
656 }
657 }
658 BOOST_CATCH(...){
659 for (; back != l; ++back){
660 allocator_traits<Allocator>::destroy(a, boost::movelib::iterator_to_raw_pointer(back));
661 }
662 BOOST_RETHROW;
663 }
664 BOOST_CATCH_END
665 }
666
667
668 //////////////////////////////////////////////////////////////////////////////
669 //
670 // uninitialized_fill_alloc_n
671 //
672 //////////////////////////////////////////////////////////////////////////////
673
674 //! <b>Effects</b>:
675 //! \code
676 //! for (; n--; ++r, ++f)
677 //! allocator_traits::construct(a, &*r, v);
678 //! \endcode
679 //!
680 //! <b>Returns</b>: r
681 template
682 <typename Allocator,
683 typename T,
684 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)685 inline F uninitialized_fill_alloc_n(Allocator &a, const T &v, typename boost::container::allocator_traits<Allocator>::size_type n, F r)
686 {
687 F back = r;
688 BOOST_TRY{
689 while (n--) {
690 allocator_traits<Allocator>::construct(a, boost::movelib::iterator_to_raw_pointer(r), v);
691 ++r;
692 }
693 }
694 BOOST_CATCH(...){
695 for (; back != r; ++back){
696 allocator_traits<Allocator>::destroy(a, boost::movelib::iterator_to_raw_pointer(back));
697 }
698 BOOST_RETHROW;
699 }
700 BOOST_CATCH_END
701 return r;
702 }
703
704 //////////////////////////////////////////////////////////////////////////////
705 //
706 // copy
707 //
708 //////////////////////////////////////////////////////////////////////////////
709
710 template
711 <typename I, // I models InputIterator
712 typename F> // F models ForwardIterator
713 inline typename dtl::disable_if_memtransfer_copy_assignable<I, F, F>::type
copy(I f,I l,F r)714 copy(I f, I l, F r)
715 {
716 while (f != l) {
717 *r = *f;
718 ++f; ++r;
719 }
720 return r;
721 }
722
723 template
724 <typename I, // I models InputIterator
725 typename F> // F models ForwardIterator
726 inline typename dtl::enable_if_memtransfer_copy_assignable<I, F, F>::type
copy(I f,I l,F r)727 copy(I f, I l, F r) BOOST_NOEXCEPT_OR_NOTHROW
728 { return dtl::memmove(f, l, r); }
729
730 //////////////////////////////////////////////////////////////////////////////
731 //
732 // copy_n
733 //
734 //////////////////////////////////////////////////////////////////////////////
735
736 template
737 <typename I, // I models InputIterator
738 typename U, // U models unsigned integral constant
739 typename F> // F models ForwardIterator
740 inline typename dtl::disable_if_memtransfer_copy_assignable<I, F, F>::type
copy_n(I f,U n,F r)741 copy_n(I f, U n, F r)
742 {
743 while (n) {
744 --n;
745 *r = *f;
746 ++f; ++r;
747 }
748 return r;
749 }
750
751 template
752 <typename I, // I models InputIterator
753 typename U, // U models unsigned integral constant
754 typename F> // F models ForwardIterator
755 inline typename dtl::enable_if_memtransfer_copy_assignable<I, F, F>::type
copy_n(I f,U n,F r)756 copy_n(I f, U n, F r) BOOST_NOEXCEPT_OR_NOTHROW
757 { return dtl::memmove_n(f, n, r); }
758
759 //////////////////////////////////////////////////////////////////////////////
760 //
761 // copy_n_source
762 //
763 //////////////////////////////////////////////////////////////////////////////
764
765 template
766 <typename I, // I models InputIterator
767 typename U, // U models unsigned integral constant
768 typename F> // F models ForwardIterator
769 inline typename dtl::disable_if_memtransfer_copy_assignable<I, F, I>::type
copy_n_source(I f,U n,F r)770 copy_n_source(I f, U n, F r)
771 {
772 while (n--) {
773 boost::container::assign_in_place(r, f);
774 ++f; ++r;
775 }
776 return f;
777 }
778
779 template
780 <typename I, // I models InputIterator
781 typename U, // U models unsigned integral constant
782 typename F> // F models ForwardIterator
783 inline typename dtl::enable_if_memtransfer_copy_assignable<I, F, I>::type
copy_n_source(I f,U n,F r)784 copy_n_source(I f, U n, F r) BOOST_NOEXCEPT_OR_NOTHROW
785 { return dtl::memmove_n_source(f, n, r); }
786
787 //////////////////////////////////////////////////////////////////////////////
788 //
789 // copy_n_source_dest
790 //
791 //////////////////////////////////////////////////////////////////////////////
792
793 template
794 <typename I, // I models InputIterator
795 typename U, // U models unsigned integral constant
796 typename F> // F models ForwardIterator
797 inline typename dtl::disable_if_memtransfer_copy_assignable<I, F, I>::type
copy_n_source_dest(I f,U n,F & r)798 copy_n_source_dest(I f, U n, F &r)
799 {
800 while (n--) {
801 *r = *f;
802 ++f; ++r;
803 }
804 return f;
805 }
806
807 template
808 <typename I, // I models InputIterator
809 typename U, // U models unsigned integral constant
810 typename F> // F models ForwardIterator
811 inline typename dtl::enable_if_memtransfer_copy_assignable<I, F, I>::type
copy_n_source_dest(I f,U n,F & r)812 copy_n_source_dest(I f, U n, F &r) BOOST_NOEXCEPT_OR_NOTHROW
813 { return dtl::memmove_n_source_dest(f, n, r); }
814
815 //////////////////////////////////////////////////////////////////////////////
816 //
817 // move
818 //
819 //////////////////////////////////////////////////////////////////////////////
820
821 template
822 <typename I, // I models InputIterator
823 typename F> // F models ForwardIterator
824 inline typename dtl::disable_if_memtransfer_copy_assignable<I, F, F>::type
move(I f,I l,F r)825 move(I f, I l, F r)
826 {
827 while (f != l) {
828 *r = ::boost::move(*f);
829 ++f; ++r;
830 }
831 return r;
832 }
833
834 template
835 <typename I, // I models InputIterator
836 typename F> // F models ForwardIterator
837 inline typename dtl::enable_if_memtransfer_copy_assignable<I, F, F>::type
move(I f,I l,F r)838 move(I f, I l, F r) BOOST_NOEXCEPT_OR_NOTHROW
839 { return dtl::memmove(f, l, r); }
840
841 //////////////////////////////////////////////////////////////////////////////
842 //
843 // move_n
844 //
845 //////////////////////////////////////////////////////////////////////////////
846
847 template
848 <typename I, // I models InputIterator
849 typename U, // U models unsigned integral constant
850 typename F> // F models ForwardIterator
851 inline typename dtl::disable_if_memtransfer_copy_assignable<I, F, F>::type
move_n(I f,U n,F r)852 move_n(I f, U n, F r)
853 {
854 while (n--) {
855 *r = ::boost::move(*f);
856 ++f; ++r;
857 }
858 return r;
859 }
860
861 template
862 <typename I, // I models InputIterator
863 typename U, // U models unsigned integral constant
864 typename F> // F models ForwardIterator
865 inline typename dtl::enable_if_memtransfer_copy_assignable<I, F, F>::type
move_n(I f,U n,F r)866 move_n(I f, U n, F r) BOOST_NOEXCEPT_OR_NOTHROW
867 { return dtl::memmove_n(f, n, r); }
868
869
870 //////////////////////////////////////////////////////////////////////////////
871 //
872 // move_backward
873 //
874 //////////////////////////////////////////////////////////////////////////////
875
876 template
877 <typename I, // I models BidirectionalIterator
878 typename F> // F models ForwardIterator
879 inline typename dtl::disable_if_memtransfer_copy_assignable<I, F, F>::type
move_backward(I f,I l,F r)880 move_backward(I f, I l, F r)
881 {
882 while (f != l) {
883 --l; --r;
884 *r = ::boost::move(*l);
885 }
886 return r;
887 }
888
889 template
890 <typename I, // I models InputIterator
891 typename F> // F models ForwardIterator
892 inline typename dtl::enable_if_memtransfer_copy_assignable<I, F, F>::type
move_backward(I f,I l,F r)893 move_backward(I f, I l, F r) BOOST_NOEXCEPT_OR_NOTHROW
894 {
895 typedef typename boost::container::iterator_traits<I>::value_type value_type;
896 const typename boost::container::iterator_traits<I>::difference_type n = boost::container::iterator_distance(f, l);
897 if (BOOST_LIKELY(n)){
898 r -= n;
899 std::memmove((boost::movelib::iterator_to_raw_pointer)(r), (boost::movelib::iterator_to_raw_pointer)(f), sizeof(value_type)*n);
900 }
901 return r;
902 }
903
904 //////////////////////////////////////////////////////////////////////////////
905 //
906 // move_n_source_dest
907 //
908 //////////////////////////////////////////////////////////////////////////////
909
910 template
911 <typename I // I models InputIterator
912 ,typename U // U models unsigned integral constant
913 ,typename F> // F models ForwardIterator
914 inline typename dtl::disable_if_memtransfer_copy_assignable<I, F, I>::type
move_n_source_dest(I f,U n,F & r)915 move_n_source_dest(I f, U n, F &r)
916 {
917 while (n--) {
918 *r = ::boost::move(*f);
919 ++f; ++r;
920 }
921 return f;
922 }
923
924 template
925 <typename I // I models InputIterator
926 ,typename U // U models unsigned integral constant
927 ,typename F> // F models ForwardIterator
928 inline typename dtl::enable_if_memtransfer_copy_assignable<I, F, I>::type
move_n_source_dest(I f,U n,F & r)929 move_n_source_dest(I f, U n, F &r) BOOST_NOEXCEPT_OR_NOTHROW
930 { return dtl::memmove_n_source_dest(f, n, r); }
931
932 //////////////////////////////////////////////////////////////////////////////
933 //
934 // move_n_source
935 //
936 //////////////////////////////////////////////////////////////////////////////
937
938 template
939 <typename I // I models InputIterator
940 ,typename U // U models unsigned integral constant
941 ,typename F> // F models ForwardIterator
942 inline typename dtl::disable_if_memtransfer_copy_assignable<I, F, I>::type
move_n_source(I f,U n,F r)943 move_n_source(I f, U n, F r)
944 {
945 while (n--) {
946 *r = ::boost::move(*f);
947 ++f; ++r;
948 }
949 return f;
950 }
951
952 template
953 <typename I // I models InputIterator
954 ,typename U // U models unsigned integral constant
955 ,typename F> // F models ForwardIterator
956 inline typename dtl::enable_if_memtransfer_copy_assignable<I, F, I>::type
move_n_source(I f,U n,F r)957 move_n_source(I f, U n, F r) BOOST_NOEXCEPT_OR_NOTHROW
958 { return dtl::memmove_n_source(f, n, r); }
959
960 //////////////////////////////////////////////////////////////////////////////
961 //
962 // destroy_alloc_n
963 //
964 //////////////////////////////////////////////////////////////////////////////
965
966 template
967 <typename Allocator
968 ,typename I // I models InputIterator
969 ,typename U> // U models unsigned integral constant
970 inline typename dtl::disable_if_trivially_destructible<I, void>::type
destroy_alloc_n(Allocator & a,I f,U n)971 destroy_alloc_n(Allocator &a, I f, U n)
972 {
973 while(n){
974 --n;
975 allocator_traits<Allocator>::destroy(a, boost::movelib::iterator_to_raw_pointer(f));
976 ++f;
977 }
978 }
979
980 template
981 <typename Allocator
982 ,typename I // I models InputIterator
983 ,typename U> // U models unsigned integral constant
984 inline typename dtl::enable_if_trivially_destructible<I, void>::type
destroy_alloc_n(Allocator &,I,U)985 destroy_alloc_n(Allocator &, I, U)
986 {}
987
988 //////////////////////////////////////////////////////////////////////////////
989 //
990 // deep_swap_alloc_n
991 //
992 //////////////////////////////////////////////////////////////////////////////
993
994 template
995 <std::size_t MaxTmpBytes
996 ,typename Allocator
997 ,typename F // F models ForwardIterator
998 ,typename G // G models ForwardIterator
999 >
1000 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)1001 deep_swap_alloc_n( Allocator &a, F short_range_f, typename allocator_traits<Allocator>::size_type n_i
1002 , G large_range_f, typename allocator_traits<Allocator>::size_type n_j)
1003 {
1004 typename allocator_traits<Allocator>::size_type n = 0;
1005 for (; n != n_i ; ++short_range_f, ++large_range_f, ++n){
1006 boost::adl_move_swap(*short_range_f, *large_range_f);
1007 }
1008 boost::container::uninitialized_move_alloc_n(a, large_range_f, n_j - n_i, short_range_f); // may throw
1009 boost::container::destroy_alloc_n(a, large_range_f, n_j - n_i);
1010 }
1011
1012 static const std::size_t DeepSwapAllocNMaxStorage = std::size_t(1) << std::size_t(11); //2K bytes
1013
1014 template
1015 <std::size_t MaxTmpBytes
1016 ,typename Allocator
1017 ,typename F // F models ForwardIterator
1018 ,typename G // G models ForwardIterator
1019 >
1020 inline typename dtl::enable_if_c
1021 < dtl::is_memtransfer_copy_assignable<F, G>::value && (MaxTmpBytes <= DeepSwapAllocNMaxStorage) && false
1022 , 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)1023 deep_swap_alloc_n( Allocator &a, F short_range_f, typename allocator_traits<Allocator>::size_type n_i
1024 , G large_range_f, typename allocator_traits<Allocator>::size_type n_j)
1025 {
1026 typedef typename allocator_traits<Allocator>::value_type value_type;
1027 typedef typename dtl::aligned_storage
1028 <MaxTmpBytes, dtl::alignment_of<value_type>::value>::type storage_type;
1029 storage_type storage;
1030
1031 const std::size_t n_i_bytes = sizeof(value_type)*n_i;
1032 void *const large_ptr = static_cast<void*>(boost::movelib::iterator_to_raw_pointer(large_range_f));
1033 void *const short_ptr = static_cast<void*>(boost::movelib::iterator_to_raw_pointer(short_range_f));
1034 void *const stora_ptr = static_cast<void*>(boost::movelib::iterator_to_raw_pointer(storage.data));
1035 std::memcpy(stora_ptr, large_ptr, n_i_bytes);
1036 std::memcpy(large_ptr, short_ptr, n_i_bytes);
1037 std::memcpy(short_ptr, stora_ptr, n_i_bytes);
1038 boost::container::iterator_advance(large_range_f, n_i);
1039 boost::container::iterator_advance(short_range_f, n_i);
1040 boost::container::uninitialized_move_alloc_n(a, large_range_f, n_j - n_i, short_range_f); // may throw
1041 boost::container::destroy_alloc_n(a, large_range_f, n_j - n_i);
1042 }
1043
1044 template
1045 <std::size_t MaxTmpBytes
1046 ,typename Allocator
1047 ,typename F // F models ForwardIterator
1048 ,typename G // G models ForwardIterator
1049 >
1050 inline typename dtl::enable_if_c
1051 < dtl::is_memtransfer_copy_assignable<F, G>::value && true//(MaxTmpBytes > DeepSwapAllocNMaxStorage)
1052 , 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)1053 deep_swap_alloc_n( Allocator &a, F short_range_f, typename allocator_traits<Allocator>::size_type n_i
1054 , G large_range_f, typename allocator_traits<Allocator>::size_type n_j)
1055 {
1056 typedef typename allocator_traits<Allocator>::value_type value_type;
1057 typedef typename dtl::aligned_storage
1058 <DeepSwapAllocNMaxStorage, dtl::alignment_of<value_type>::value>::type storage_type;
1059 storage_type storage;
1060 const std::size_t sizeof_storage = sizeof(storage);
1061
1062 std::size_t n_i_bytes = sizeof(value_type)*n_i;
1063 char *large_ptr = static_cast<char*>(static_cast<void*>(boost::movelib::iterator_to_raw_pointer(large_range_f)));
1064 char *short_ptr = static_cast<char*>(static_cast<void*>(boost::movelib::iterator_to_raw_pointer(short_range_f)));
1065 char *stora_ptr = static_cast<char*>(static_cast<void*>(storage.data));
1066
1067 std::size_t szt_times = n_i_bytes/sizeof_storage;
1068 const std::size_t szt_rem = n_i_bytes%sizeof_storage;
1069
1070 //Loop unrolling using Duff's device, as it seems it helps on some architectures
1071 const std::size_t Unroll = 4;
1072 std::size_t n = (szt_times + (Unroll-1))/Unroll;
1073 const std::size_t branch_number = (!szt_times)*Unroll + (szt_times % Unroll);
1074 switch(branch_number){
1075 case 4:
1076 break;
1077 case 0: do{
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_FALLTHROUGH;
1084 case 3:
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_FALLTHROUGH;
1091 case 2:
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 BOOST_FALLTHROUGH;
1098 case 1:
1099 std::memcpy(stora_ptr, large_ptr, sizeof_storage);
1100 std::memcpy(large_ptr, short_ptr, sizeof_storage);
1101 std::memcpy(short_ptr, stora_ptr, sizeof_storage);
1102 large_ptr += sizeof_storage;
1103 short_ptr += sizeof_storage;
1104 } while(--n);
1105 }
1106 std::memcpy(stora_ptr, large_ptr, szt_rem);
1107 std::memcpy(large_ptr, short_ptr, szt_rem);
1108 std::memcpy(short_ptr, stora_ptr, szt_rem);
1109 boost::container::iterator_advance(large_range_f, n_i);
1110 boost::container::iterator_advance(short_range_f, n_i);
1111 boost::container::uninitialized_move_alloc_n(a, large_range_f, n_j - n_i, short_range_f); // may throw
1112 boost::container::destroy_alloc_n(a, large_range_f, n_j - n_i);
1113 }
1114
1115
1116 //////////////////////////////////////////////////////////////////////////////
1117 //
1118 // copy_assign_range_alloc_n
1119 //
1120 //////////////////////////////////////////////////////////////////////////////
1121
1122 template
1123 <typename Allocator
1124 ,typename I // F models InputIterator
1125 ,typename O // G models OutputIterator
1126 >
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)1127 void copy_assign_range_alloc_n( Allocator &a, I inp_start, typename allocator_traits<Allocator>::size_type n_i
1128 , O out_start, typename allocator_traits<Allocator>::size_type n_o )
1129 {
1130 if (n_o < n_i){
1131 inp_start = boost::container::copy_n_source_dest(inp_start, n_o, out_start); // may throw
1132 boost::container::uninitialized_copy_alloc_n(a, inp_start, n_i - n_o, out_start);// may throw
1133 }
1134 else{
1135 out_start = boost::container::copy_n(inp_start, n_i, out_start); // may throw
1136 boost::container::destroy_alloc_n(a, out_start, n_o - n_i);
1137 }
1138 }
1139
1140 //////////////////////////////////////////////////////////////////////////////
1141 //
1142 // move_assign_range_alloc_n
1143 //
1144 //////////////////////////////////////////////////////////////////////////////
1145
1146 template
1147 <typename Allocator
1148 ,typename I // F models InputIterator
1149 ,typename O // G models OutputIterator
1150 >
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)1151 void move_assign_range_alloc_n( Allocator &a, I inp_start, typename allocator_traits<Allocator>::size_type n_i
1152 , O out_start, typename allocator_traits<Allocator>::size_type n_o )
1153 {
1154 if (n_o < n_i){
1155 inp_start = boost::container::move_n_source_dest(inp_start, n_o, out_start); // may throw
1156 boost::container::uninitialized_move_alloc_n(a, inp_start, n_i - n_o, out_start); // may throw
1157 }
1158 else{
1159 out_start = boost::container::move_n(inp_start, n_i, out_start); // may throw
1160 boost::container::destroy_alloc_n(a, out_start, n_o - n_i);
1161 }
1162 }
1163
1164 } //namespace container {
1165 } //namespace boost {
1166
1167 //#pragma GCC diagnostic ignored "-Wclass-memaccess"
1168 #if defined(BOOST_GCC) && (BOOST_GCC >= 40600)
1169 #pragma GCC diagnostic pop
1170 #endif
1171
1172 #endif //#ifndef BOOST_CONTAINER_DETAIL_COPY_MOVE_ALGO_HPP
1173