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