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