boost/container/detail/utilities.hpp
////////////////////////////////////////////////////////////////////////////// // // (C) Copyright Ion Gaztanaga 2005-2012. Distributed under the Boost // Software License, Version 1.0. (See accompanying file // LICENSE_1_0.txt or copy at http://www.boost.org/LICENSE_1_0.txt) // // See http://www.boost.org/libs/container for documentation. // ////////////////////////////////////////////////////////////////////////////// #ifndef BOOST_CONTAINER_DETAIL_UTILITIES_HPP #define BOOST_CONTAINER_DETAIL_UTILITIES_HPP #include "config_begin.hpp" #include <cstdio> #include <cstring> //for ::memcpy #include <boost/type_traits/is_fundamental.hpp> #include <boost/type_traits/is_pointer.hpp> #include <boost/type_traits/is_enum.hpp> #include <boost/type_traits/is_member_pointer.hpp> #include <boost/type_traits/is_class.hpp> #include <boost/type_traits/has_trivial_destructor.hpp> #include <boost/move/core.hpp> #include <boost/move/utility.hpp> #include <boost/move/iterator.hpp> #include <boost/container/detail/mpl.hpp> #include <boost/container/detail/type_traits.hpp> #include <boost/container/allocator_traits.hpp> #include <boost/detail/no_exceptions_support.hpp> #include <boost/type_traits/has_trivial_copy.hpp> #include <boost/type_traits/has_trivial_assign.hpp> #include <boost/container/detail/memory_util.hpp> #include <boost/aligned_storage.hpp> #include <algorithm> #include <iterator> #include <utility> //std::distance namespace boost { namespace container { ////////////////////////////////////////////////////////////////////////////// // // swap // ////////////////////////////////////////////////////////////////////////////// namespace container_swap { template<class T, bool IsClass = boost::is_class<T>::value > struct has_member_swap { static const bool value = boost::container::container_detail:: has_member_function_callable_with_swap<T, T &>::value; }; template<class T> struct has_member_swap<T, false> { static const bool value = false; }; } //namespace container_swap { template<class T> inline typename container_detail::enable_if_c <container_swap::has_member_swap<T>::value, void>::type swap_dispatch(T &left, T &right) //swap using member swap { left.swap(right); // may throw } template<class T> inline typename container_detail::enable_if_c <!container_swap::has_member_swap<T>::value && boost::has_move_emulation_enabled<T>::value, void>::type swap_dispatch(T &left, T &right) { T temp(boost::move(left)); // may throw left = boost::move(right); // may throw right = boost::move(temp); // may throw } template<class T> inline typename container_detail::enable_if_c <!container_swap::has_member_swap<T>::value && !boost::has_move_emulation_enabled<T>::value, void>::type swap_dispatch(T &left, T &right) { using std::swap; swap(left, right); // may throw } namespace container_detail { template <typename T> inline T* addressof(T& obj) { return static_cast<T*>( static_cast<void*>( const_cast<char*>( &reinterpret_cast<const char&>(obj) ))); } template<class T> const T &max_value(const T &a, const T &b) { return a > b ? a : b; } template<class T> const T &min_value(const T &a, const T &b) { return a < b ? a : b; } template <class SizeType> SizeType get_next_capacity(const SizeType max_size ,const SizeType capacity ,const SizeType n) { // if (n > max_size - capacity) // throw std::length_error("get_next_capacity"); const SizeType m3 = max_size/3; if (capacity < m3) return capacity + max_value(3*(capacity+1)/5, n); if (capacity < m3*2) return capacity + max_value((capacity+1)/2, n); return max_size; } template <class T> inline T* to_raw_pointer(T* p) { return p; } template <class Pointer> inline typename Pointer::element_type* to_raw_pointer(const Pointer &p) { return boost::container::container_detail::to_raw_pointer(p.operator->()); } template<class AllocatorType> inline void swap_alloc(AllocatorType &, AllocatorType &, container_detail::false_type) BOOST_CONTAINER_NOEXCEPT {} template<class AllocatorType> inline void swap_alloc(AllocatorType &l, AllocatorType &r, container_detail::true_type) { boost::container::swap_dispatch(l, r); } template<class AllocatorType> inline void assign_alloc(AllocatorType &, const AllocatorType &, container_detail::false_type) BOOST_CONTAINER_NOEXCEPT {} template<class AllocatorType> inline void assign_alloc(AllocatorType &l, const AllocatorType &r, container_detail::true_type) { l = r; } template<class AllocatorType> inline void move_alloc(AllocatorType &, AllocatorType &, container_detail::false_type) BOOST_CONTAINER_NOEXCEPT {} template<class AllocatorType> inline void move_alloc(AllocatorType &l, AllocatorType &r, container_detail::true_type) { l = ::boost::move(r); } //Rounds "orig_size" by excess to round_to bytes template<class SizeType> inline SizeType get_rounded_size(SizeType orig_size, SizeType round_to) { return ((orig_size-1)/round_to+1)*round_to; } template <std::size_t OrigSize, std::size_t RoundTo> struct ct_rounded_size { enum { value = ((OrigSize-1)/RoundTo+1)*RoundTo }; }; template<class I> struct are_elements_contiguous { static const bool value = false; }; ///////////////////////// // raw pointers ///////////////////////// template<class T> struct are_elements_contiguous<T*> { static const bool value = true; }; ///////////////////////// // predeclarations ///////////////////////// #ifndef BOOST_CONTAINER_VECTOR_ITERATOR_IS_POINTER template<class Pointer> class vector_iterator; template<class Pointer> class vector_const_iterator; #endif //BOOST_CONTAINER_VECTOR_ITERATOR_IS_POINTER } //namespace container_detail { } //namespace container { namespace interprocess { template <class PointedType, class DifferenceType, class OffsetType, std::size_t OffsetAlignment> class offset_ptr; } //namespace interprocess { namespace container { namespace container_detail { ///////////////////////// //vector_[const_]iterator ///////////////////////// #ifndef BOOST_CONTAINER_VECTOR_ITERATOR_IS_POINTER template<class Pointer> struct are_elements_contiguous<boost::container::container_detail::vector_iterator<Pointer> > { static const bool value = true; }; template<class Pointer> struct are_elements_contiguous<boost::container::container_detail::vector_const_iterator<Pointer> > { static const bool value = true; }; #endif //BOOST_CONTAINER_VECTOR_ITERATOR_IS_POINTER ///////////////////////// // offset_ptr ///////////////////////// template <class PointedType, class DifferenceType, class OffsetType, std::size_t OffsetAlignment> struct are_elements_contiguous< ::boost::interprocess::offset_ptr<PointedType, DifferenceType, OffsetType, OffsetAlignment> > { static const bool value = true; }; template <typename I, typename O> struct are_contiguous_and_same { static const bool is_same_io = is_same< typename remove_const< typename ::std::iterator_traits<I>::value_type >::type , typename ::std::iterator_traits<O>::value_type >::value; static const bool value = is_same_io && are_elements_contiguous<I>::value && are_elements_contiguous<O>::value; }; template <typename I, typename O> struct is_memcpy_copy_assignable { static const bool value = are_contiguous_and_same<I, O>::value && boost::has_trivial_assign< typename ::std::iterator_traits<I>::value_type >::value; }; template <typename I, typename O> struct is_memcpy_copy_constructible { static const bool value = are_contiguous_and_same<I, O>::value && boost::has_trivial_copy< typename ::std::iterator_traits<I>::value_type >::value; }; template <typename I, typename O, typename R> struct enable_if_memcpy_copy_constructible : public enable_if_c<container_detail::is_memcpy_copy_constructible<I, O>::value, R> {}; template <typename I, typename O, typename R> struct disable_if_memcpy_copy_constructible : public enable_if_c<!container_detail::is_memcpy_copy_constructible<I, O>::value, R> {}; template <typename I, typename O, typename R> struct enable_if_memcpy_copy_assignable : public enable_if_c<container_detail::is_memcpy_copy_assignable<I, O>::value, R> {}; template <typename I, typename O, typename R> struct disable_if_memcpy_copy_assignable : public enable_if_c<!container_detail::is_memcpy_copy_assignable<I, O>::value, R> {}; template <typename I, // I models InputIterator typename F> // F models ForwardIterator inline F memcpy(I f, I l, F r) BOOST_CONTAINER_NOEXCEPT { typedef typename std::iterator_traits<I>::value_type value_type; typename std::iterator_traits<I>::difference_type n = std::distance(f, l); ::memcpy(container_detail::addressof(*r), container_detail::addressof(*f), sizeof(value_type)*n); std::advance(r, n); return r; } template <typename I, // I models InputIterator typename F> // F models ForwardIterator F memcpy_n(I f, typename std::iterator_traits<I>::difference_type n, F r) BOOST_CONTAINER_NOEXCEPT { typedef typename std::iterator_traits<I>::value_type value_type; ::memcpy(container_detail::addressof(*r), container_detail::addressof(*f), sizeof(value_type)*n); std::advance(r, n); return r; } template <typename I, // I models InputIterator typename F> // F models ForwardIterator I memcpy_n_source(I f, typename std::iterator_traits<I>::difference_type n, F r) BOOST_CONTAINER_NOEXCEPT { typedef typename std::iterator_traits<I>::value_type value_type; ::memcpy(container_detail::addressof(*r), container_detail::addressof(*f), sizeof(value_type)*n); std::advance(f, n); return f; } template <typename I, // I models InputIterator typename F> // F models ForwardIterator I memcpy_n_source_dest(I f, typename std::iterator_traits<I>::difference_type n, F &r) BOOST_CONTAINER_NOEXCEPT { typedef typename std::iterator_traits<I>::value_type value_type; ::memcpy(container_detail::addressof(*r), container_detail::addressof(*f), sizeof(value_type)*n); std::advance(f, n); std::advance(r, n); return f; } } //namespace container_detail { ////////////////////////////////////////////////////////////////////////////// // // uninitialized_move_alloc // ////////////////////////////////////////////////////////////////////////////// //! <b>Effects</b>: //! \code //! for (; f != l; ++r, ++f) //! allocator_traits::construct(a, &*r, boost::move(*f)); //! \endcode //! //! <b>Returns</b>: r template <typename A, typename I, // I models InputIterator typename F> // F models ForwardIterator inline typename container_detail::disable_if_memcpy_copy_constructible<I, F, F>::type uninitialized_move_alloc(A &a, I f, I l, F r) { F back = r; BOOST_TRY{ while (f != l) { allocator_traits<A>::construct(a, container_detail::to_raw_pointer(&*r), boost::move(*f)); ++f; ++r; } } BOOST_CATCH(...){ for (; back != r; ++back){ allocator_traits<A>::destroy(a, container_detail::to_raw_pointer(&*back)); } BOOST_RETHROW; } BOOST_CATCH_END return r; } template <typename A, typename I, // I models InputIterator typename F> // F models ForwardIterator inline typename container_detail::enable_if_memcpy_copy_constructible<I, F, F>::type uninitialized_move_alloc(A &, I f, I l, F r) BOOST_CONTAINER_NOEXCEPT { return container_detail::memcpy(f, l, r); } ////////////////////////////////////////////////////////////////////////////// // // uninitialized_move_alloc_n // ////////////////////////////////////////////////////////////////////////////// //! <b>Effects</b>: //! \code //! for (; n--; ++r, ++f) //! allocator_traits::construct(a, &*r, boost::move(*f)); //! \endcode //! //! <b>Returns</b>: r template <typename A, typename I, // I models InputIterator typename F> // F models ForwardIterator inline typename container_detail::disable_if_memcpy_copy_constructible<I, F, F>::type uninitialized_move_alloc_n(A &a, I f, typename std::iterator_traits<I>::difference_type n, F r) { F back = r; BOOST_TRY{ while (n--) { allocator_traits<A>::construct(a, container_detail::to_raw_pointer(&*r), boost::move(*f)); ++f; ++r; } } BOOST_CATCH(...){ for (; back != r; ++back){ allocator_traits<A>::destroy(a, container_detail::to_raw_pointer(&*back)); } BOOST_RETHROW; } BOOST_CATCH_END return r; } template <typename A, typename I, // I models InputIterator typename F> // F models ForwardIterator inline typename container_detail::enable_if_memcpy_copy_constructible<I, F, F>::type uninitialized_move_alloc_n(A &, I f, typename std::iterator_traits<I>::difference_type n, F r) BOOST_CONTAINER_NOEXCEPT { return container_detail::memcpy_n(f, n, r); } ////////////////////////////////////////////////////////////////////////////// // // uninitialized_move_alloc_n_source // ////////////////////////////////////////////////////////////////////////////// //! <b>Effects</b>: //! \code //! for (; n--; ++r, ++f) //! allocator_traits::construct(a, &*r, boost::move(*f)); //! \endcode //! //! <b>Returns</b>: f (after incremented) template <typename A, typename I, // I models InputIterator typename F> // F models ForwardIterator inline typename container_detail::disable_if_memcpy_copy_constructible<I, F, I>::type uninitialized_move_alloc_n_source(A &a, I f, typename std::iterator_traits<I>::difference_type n, F r) { F back = r; BOOST_TRY{ while (n--) { allocator_traits<A>::construct(a, container_detail::to_raw_pointer(&*r), boost::move(*f)); ++f; ++r; } } BOOST_CATCH(...){ for (; back != r; ++back){ allocator_traits<A>::destroy(a, container_detail::to_raw_pointer(&*back)); } BOOST_RETHROW; } BOOST_CATCH_END return f; } template <typename A, typename I, // I models InputIterator typename F> // F models ForwardIterator inline typename container_detail::enable_if_memcpy_copy_constructible<I, F, I>::type uninitialized_move_alloc_n_source(A &, I f, typename std::iterator_traits<I>::difference_type n, F r) BOOST_CONTAINER_NOEXCEPT { return container_detail::memcpy_n_source(f, n, r); } ////////////////////////////////////////////////////////////////////////////// // // uninitialized_copy_alloc // ////////////////////////////////////////////////////////////////////////////// //! <b>Effects</b>: //! \code //! for (; f != l; ++r, ++f) //! allocator_traits::construct(a, &*r, *f); //! \endcode //! //! <b>Returns</b>: r template <typename A, typename I, // I models InputIterator typename F> // F models ForwardIterator inline typename container_detail::disable_if_memcpy_copy_constructible<I, F, F>::type uninitialized_copy_alloc(A &a, I f, I l, F r) { F back = r; BOOST_TRY{ while (f != l) { allocator_traits<A>::construct(a, container_detail::to_raw_pointer(&*r), *f); ++f; ++r; } } BOOST_CATCH(...){ for (; back != r; ++back){ allocator_traits<A>::destroy(a, container_detail::to_raw_pointer(&*back)); } BOOST_RETHROW; } BOOST_CATCH_END return r; } template <typename A, typename I, // I models InputIterator typename F> // F models ForwardIterator inline typename container_detail::enable_if_memcpy_copy_constructible<I, F, F>::type uninitialized_copy_alloc(A &, I f, I l, F r) BOOST_CONTAINER_NOEXCEPT { return container_detail::memcpy(f, l, r); } ////////////////////////////////////////////////////////////////////////////// // // uninitialized_copy_alloc_n // ////////////////////////////////////////////////////////////////////////////// //! <b>Effects</b>: //! \code //! for (; n--; ++r, ++f) //! allocator_traits::construct(a, &*r, *f); //! \endcode //! //! <b>Returns</b>: r template <typename A, typename I, // I models InputIterator typename F> // F models ForwardIterator inline typename container_detail::disable_if_memcpy_copy_constructible<I, F, F>::type uninitialized_copy_alloc_n(A &a, I f, typename std::iterator_traits<I>::difference_type n, F r) { F back = r; BOOST_TRY{ while (n--) { allocator_traits<A>::construct(a, container_detail::to_raw_pointer(&*r), *f); ++f; ++r; } } BOOST_CATCH(...){ for (; back != r; ++back){ allocator_traits<A>::destroy(a, container_detail::to_raw_pointer(&*back)); } BOOST_RETHROW; } BOOST_CATCH_END return r; } template <typename A, typename I, // I models InputIterator typename F> // F models ForwardIterator inline typename container_detail::enable_if_memcpy_copy_constructible<I, F, F>::type uninitialized_copy_alloc_n(A &, I f, typename std::iterator_traits<I>::difference_type n, F r) BOOST_CONTAINER_NOEXCEPT { return container_detail::memcpy_n(f, n, r); } ////////////////////////////////////////////////////////////////////////////// // // uninitialized_copy_alloc_n_source // ////////////////////////////////////////////////////////////////////////////// //! <b>Effects</b>: //! \code //! for (; n--; ++r, ++f) //! allocator_traits::construct(a, &*r, *f); //! \endcode //! //! <b>Returns</b>: f (after incremented) template <typename A, typename I, // I models InputIterator typename F> // F models ForwardIterator inline typename container_detail::disable_if_memcpy_copy_constructible<I, F, I>::type uninitialized_copy_alloc_n_source(A &a, I f, typename std::iterator_traits<I>::difference_type n, F r) { F back = r; BOOST_TRY{ while (n--) { allocator_traits<A>::construct(a, container_detail::to_raw_pointer(&*r), *f); ++f; ++r; } } BOOST_CATCH(...){ for (; back != r; ++back){ allocator_traits<A>::destroy(a, container_detail::to_raw_pointer(&*back)); } BOOST_RETHROW; } BOOST_CATCH_END return f; } template <typename A, typename I, // I models InputIterator typename F> // F models ForwardIterator inline typename container_detail::enable_if_memcpy_copy_constructible<I, F, I>::type uninitialized_copy_alloc_n_source(A &, I f, typename std::iterator_traits<I>::difference_type n, F r) BOOST_CONTAINER_NOEXCEPT { return container_detail::memcpy_n_source(f, n, r); } ////////////////////////////////////////////////////////////////////////////// // // uninitialized_default_alloc_n // ////////////////////////////////////////////////////////////////////////////// //! <b>Effects</b>: //! \code //! for (; n--; ++r, ++f) //! allocator_traits::construct(a, &*r); //! \endcode //! //! <b>Returns</b>: r template <typename A, typename F> // F models ForwardIterator inline F uninitialized_default_alloc_n(A &a, typename allocator_traits<A>::difference_type n, F r) { F back = r; BOOST_TRY{ while (n--) { allocator_traits<A>::construct(a, container_detail::to_raw_pointer(&*r)); ++r; } } BOOST_CATCH(...){ for (; back != r; ++back){ allocator_traits<A>::destroy(a, container_detail::to_raw_pointer(&*back)); } BOOST_RETHROW; } BOOST_CATCH_END return r; } ////////////////////////////////////////////////////////////////////////////// // // uninitialized_fill_alloc // ////////////////////////////////////////////////////////////////////////////// //! <b>Effects</b>: //! \code //! for (; f != l; ++r, ++f) //! allocator_traits::construct(a, &*r, *f); //! \endcode //! //! <b>Returns</b>: r template <typename A, typename F, // F models ForwardIterator typename T> inline void uninitialized_fill_alloc(A &a, F f, F l, const T &t) { F back = f; BOOST_TRY{ while (f != l) { allocator_traits<A>::construct(a, container_detail::to_raw_pointer(&*f), t); ++f; } } BOOST_CATCH(...){ for (; back != l; ++back){ allocator_traits<A>::destroy(a, container_detail::to_raw_pointer(&*back)); } BOOST_RETHROW; } BOOST_CATCH_END } ////////////////////////////////////////////////////////////////////////////// // // uninitialized_fill_alloc_n // ////////////////////////////////////////////////////////////////////////////// //! <b>Effects</b>: //! \code //! for (; n--; ++r, ++f) //! allocator_traits::construct(a, &*r, v); //! \endcode //! //! <b>Returns</b>: r template <typename A, typename T, typename F> // F models ForwardIterator inline F uninitialized_fill_alloc_n(A &a, const T &v, typename allocator_traits<A>::difference_type n, F r) { F back = r; BOOST_TRY{ while (n--) { allocator_traits<A>::construct(a, container_detail::to_raw_pointer(&*r), v); ++r; } } BOOST_CATCH(...){ for (; back != r; ++back){ allocator_traits<A>::destroy(a, container_detail::to_raw_pointer(&*back)); } BOOST_RETHROW; } BOOST_CATCH_END return r; } ////////////////////////////////////////////////////////////////////////////// // // copy // ////////////////////////////////////////////////////////////////////////////// template <typename I, // I models InputIterator typename F> // F models ForwardIterator inline typename container_detail::disable_if_memcpy_copy_assignable<I, F, F>::type copy(I f, I l, F r) { while (f != l) { *r = *f; ++f; ++r; } return r; } template <typename I, // I models InputIterator typename F> // F models ForwardIterator inline typename container_detail::enable_if_memcpy_copy_assignable<I, F, F>::type copy(I f, I l, F r) BOOST_CONTAINER_NOEXCEPT { return container_detail::memcpy(f, l, r); } ////////////////////////////////////////////////////////////////////////////// // // copy_n // ////////////////////////////////////////////////////////////////////////////// template <typename I, // I models InputIterator typename F> // F models ForwardIterator inline typename container_detail::disable_if_memcpy_copy_assignable<I, F, F>::type copy_n(I f, typename std::iterator_traits<I>::difference_type n, F r) { while (n--) { *r = *f; ++f; ++r; } return r; } template <typename I, // I models InputIterator typename F> // F models ForwardIterator inline typename container_detail::enable_if_memcpy_copy_assignable<I, F, F>::type copy_n(I f, typename std::iterator_traits<I>::difference_type n, F r) BOOST_CONTAINER_NOEXCEPT { return container_detail::memcpy_n(f, n, r); } ////////////////////////////////////////////////////////////////////////////// // // copy_n_source // ////////////////////////////////////////////////////////////////////////////// template <typename I, // I models InputIterator typename F> // F models ForwardIterator inline typename container_detail::disable_if_memcpy_copy_assignable<I, F, I>::type copy_n_source(I f, typename std::iterator_traits<I>::difference_type n, F r) { while (n--) { *r = *f; ++f; ++r; } return f; } template <typename I, // I models InputIterator typename F> // F models ForwardIterator inline typename container_detail::enable_if_memcpy_copy_assignable<I, F, I>::type copy_n_source(I f, typename std::iterator_traits<I>::difference_type n, F r) BOOST_CONTAINER_NOEXCEPT { return container_detail::memcpy_n_source(f, n, r); } ////////////////////////////////////////////////////////////////////////////// // // copy_n_source_dest // ////////////////////////////////////////////////////////////////////////////// template <typename I, // I models InputIterator typename F> // F models ForwardIterator inline typename container_detail::disable_if_memcpy_copy_assignable<I, F, I>::type copy_n_source_dest(I f, typename std::iterator_traits<I>::difference_type n, F &r) { while (n--) { *r = *f; ++f; ++r; } return f; } template <typename I, // I models InputIterator typename F> // F models ForwardIterator inline typename container_detail::enable_if_memcpy_copy_assignable<I, F, I>::type copy_n_source_dest(I f, typename std::iterator_traits<I>::difference_type n, F &r) BOOST_CONTAINER_NOEXCEPT { return container_detail::memcpy_n_source_dest(f, n, r); } ////////////////////////////////////////////////////////////////////////////// // // move // ////////////////////////////////////////////////////////////////////////////// template <typename I, // I models InputIterator typename F> // F models ForwardIterator inline typename container_detail::disable_if_memcpy_copy_assignable<I, F, F>::type move(I f, I l, F r) { while (f != l) { *r = ::boost::move(*f); ++f; ++r; } return r; } template <typename I, // I models InputIterator typename F> // F models ForwardIterator inline typename container_detail::enable_if_memcpy_copy_assignable<I, F, F>::type move(I f, I l, F r) BOOST_CONTAINER_NOEXCEPT { return container_detail::memcpy(f, l, r); } ////////////////////////////////////////////////////////////////////////////// // // move_n // ////////////////////////////////////////////////////////////////////////////// template <typename I, // I models InputIterator typename F> // F models ForwardIterator inline typename container_detail::disable_if_memcpy_copy_assignable<I, F, F>::type move_n(I f, typename std::iterator_traits<I>::difference_type n, F r) { while (n--) { *r = ::boost::move(*f); ++f; ++r; } return r; } template <typename I, // I models InputIterator typename F> // F models ForwardIterator inline typename container_detail::enable_if_memcpy_copy_assignable<I, F, F>::type move_n(I f, typename std::iterator_traits<I>::difference_type n, F r) BOOST_CONTAINER_NOEXCEPT { return container_detail::memcpy_n(f, n, r); } ////////////////////////////////////////////////////////////////////////////// // // move_n_source // ////////////////////////////////////////////////////////////////////////////// template <typename I // I models InputIterator ,typename F> // F models ForwardIterator inline typename container_detail::disable_if_memcpy_copy_assignable<I, F, I>::type move_n_source(I f, typename std::iterator_traits<I>::difference_type n, F r) { while (n--) { *r = ::boost::move(*f); ++f; ++r; } return f; } template <typename I // I models InputIterator ,typename F> // F models ForwardIterator inline typename container_detail::enable_if_memcpy_copy_assignable<I, F, I>::type move_n_source(I f, typename std::iterator_traits<I>::difference_type n, F r) BOOST_CONTAINER_NOEXCEPT { return container_detail::memcpy_n_source(f, n, r); } ////////////////////////////////////////////////////////////////////////////// // // move_n_source_dest // ////////////////////////////////////////////////////////////////////////////// template <typename I // I models InputIterator ,typename F> // F models ForwardIterator inline typename container_detail::disable_if_memcpy_copy_assignable<I, F, I>::type move_n_source_dest(I f, typename std::iterator_traits<I>::difference_type n, F &r) { while (n--) { *r = ::boost::move(*f); ++f; ++r; } return f; } template <typename I // I models InputIterator ,typename F> // F models ForwardIterator inline typename container_detail::enable_if_memcpy_copy_assignable<I, F, I>::type move_n_source_dest(I f, typename std::iterator_traits<I>::difference_type n, F &r) BOOST_CONTAINER_NOEXCEPT { return container_detail::memcpy_n_source_dest(f, n, r); } ////////////////////////////////////////////////////////////////////////////// // // destroy_n // ////////////////////////////////////////////////////////////////////////////// template <typename A ,typename I> // I models InputIterator inline void destroy_alloc_n(A &a, I f, typename std::iterator_traits<I>::difference_type n ,typename boost::container::container_detail::enable_if_c < !boost::has_trivial_destructor<typename std::iterator_traits<I>::value_type>::value >::type* = 0) { while(n--){ allocator_traits<A>::destroy(a, container_detail::addressof(*f++)); } } template <typename A ,typename I> // I models InputIterator inline void destroy_alloc_n(A &, I, typename std::iterator_traits<I>::difference_type ,typename boost::container::container_detail::enable_if_c < boost::has_trivial_destructor<typename std::iterator_traits<I>::value_type>::value >::type* = 0) {} ////////////////////////////////////////////////////////////////////////////// // // deep_swap_alloc_n // ////////////////////////////////////////////////////////////////////////////// template <std::size_t MaxTmpBytes ,typename A ,typename F // F models ForwardIterator ,typename G // G models ForwardIterator > inline typename container_detail::disable_if_memcpy_copy_assignable<F, G, void>::type deep_swap_alloc_n( A &a, F short_range_f, typename allocator_traits<A>::size_type n_i , G large_range_f, typename allocator_traits<A>::size_type n_j) { typename allocator_traits<A>::size_type n = 0; for (; n != n_i ; ++short_range_f, ++large_range_f, ++n){ boost::container::swap_dispatch(*short_range_f, *large_range_f); } boost::container::uninitialized_move_alloc_n(a, large_range_f, n_j - n_i, short_range_f); // may throw boost::container::destroy_alloc_n(a, large_range_f, n_j - n_i); } static const std::size_t DeepSwapAllocNMaxStorage = std::size_t(1) << std::size_t(11); //2K bytes template <std::size_t MaxTmpBytes ,typename A ,typename F // F models ForwardIterator ,typename G // G models ForwardIterator > inline typename container_detail::enable_if_c < container_detail::is_memcpy_copy_assignable<F, G>::value && (MaxTmpBytes <= DeepSwapAllocNMaxStorage) && false , void>::type deep_swap_alloc_n( A &a, F short_range_f, typename allocator_traits<A>::size_type n_i , G large_range_f, typename allocator_traits<A>::size_type n_j) { typedef typename allocator_traits<A>::value_type value_type; typedef typename boost::aligned_storage <MaxTmpBytes, container_detail::alignment_of<value_type>::value>::type storage_type; storage_type storage; const std::size_t n_i_bytes = sizeof(value_type)*n_i; unsigned char *const large_ptr = static_cast<unsigned char*>(static_cast<void*>(container_detail::addressof(*large_range_f))); unsigned char *const short_ptr = static_cast<unsigned char*>(static_cast<void*>(container_detail::addressof(*short_range_f))); unsigned char *const stora_ptr = static_cast<unsigned char*>(static_cast<void*>(container_detail::addressof(storage))); ::memcpy(stora_ptr, large_ptr, n_i_bytes); ::memcpy(large_ptr, short_ptr, n_i_bytes); ::memcpy(short_ptr, stora_ptr, n_i_bytes); std::advance(large_range_f, n_i); std::advance(short_range_f, n_i); boost::container::uninitialized_move_alloc_n(a, large_range_f, n_j - n_i, short_range_f); // may throw boost::container::destroy_alloc_n(a, large_range_f, n_j - n_i); } template <std::size_t MaxTmpBytes ,typename A ,typename F // F models ForwardIterator ,typename G // G models ForwardIterator > inline typename container_detail::enable_if_c < container_detail::is_memcpy_copy_assignable<F, G>::value && true//(MaxTmpBytes > DeepSwapAllocNMaxStorage) , void>::type deep_swap_alloc_n( A &a, F short_range_f, typename allocator_traits<A>::size_type n_i , G large_range_f, typename allocator_traits<A>::size_type n_j) { typedef typename allocator_traits<A>::value_type value_type; typedef typename boost::aligned_storage <DeepSwapAllocNMaxStorage, container_detail::alignment_of<value_type>::value>::type storage_type; storage_type storage; const std::size_t sizeof_storage = sizeof(storage); std::size_t n_i_bytes = sizeof(value_type)*n_i; char *large_ptr = static_cast<char*>(static_cast<void*>(container_detail::addressof(*large_range_f))); char *short_ptr = static_cast<char*>(static_cast<void*>(container_detail::addressof(*short_range_f))); char *stora_ptr = static_cast<char*>(static_cast<void*>(container_detail::addressof(storage))); std::size_t szt_times = n_i_bytes/sizeof_storage; const std::size_t szt_rem = n_i_bytes%sizeof_storage; //Loop unrolling using Duff's device, as it seems it helps on some architectures const std::size_t Unroll = 4; std::size_t n = (szt_times + (Unroll-1))/Unroll; const std::size_t branch_number = ((!szt_times)*Unroll) + (szt_times % Unroll); switch(branch_number){ case 4: break; case 0: do{ ::memcpy(stora_ptr, large_ptr, sizeof_storage); ::memcpy(large_ptr, short_ptr, sizeof_storage); ::memcpy(short_ptr, stora_ptr, sizeof_storage); large_ptr += sizeof_storage; short_ptr += sizeof_storage; case 3: ::memcpy(stora_ptr, large_ptr, sizeof_storage); ::memcpy(large_ptr, short_ptr, sizeof_storage); ::memcpy(short_ptr, stora_ptr, sizeof_storage); large_ptr += sizeof_storage; short_ptr += sizeof_storage; case 2: ::memcpy(stora_ptr, large_ptr, sizeof_storage); ::memcpy(large_ptr, short_ptr, sizeof_storage); ::memcpy(short_ptr, stora_ptr, sizeof_storage); large_ptr += sizeof_storage; short_ptr += sizeof_storage; case 1: ::memcpy(stora_ptr, large_ptr, sizeof_storage); ::memcpy(large_ptr, short_ptr, sizeof_storage); ::memcpy(short_ptr, stora_ptr, sizeof_storage); large_ptr += sizeof_storage; short_ptr += sizeof_storage; } while(--n); } ::memcpy(stora_ptr, large_ptr, szt_rem); ::memcpy(large_ptr, short_ptr, szt_rem); ::memcpy(short_ptr, stora_ptr, szt_rem); std::advance(large_range_f, n_i); std::advance(short_range_f, n_i); boost::container::uninitialized_move_alloc_n(a, large_range_f, n_j - n_i, short_range_f); // may throw boost::container::destroy_alloc_n(a, large_range_f, n_j - n_i); } ////////////////////////////////////////////////////////////////////////////// // // copy_assign_range_alloc_n // ////////////////////////////////////////////////////////////////////////////// template <typename A ,typename I // F models InputIterator ,typename O // G models OutputIterator > void copy_assign_range_alloc_n( A &a, I inp_start, typename allocator_traits<A>::size_type n_i , O out_start, typename allocator_traits<A>::size_type n_o ) { if (n_o < n_i){ inp_start = boost::container::copy_n_source_dest(inp_start, n_o, out_start); // may throw boost::container::uninitialized_copy_alloc_n(a, inp_start, n_i - n_o, out_start);// may throw } else{ out_start = boost::container::copy_n(inp_start, n_i, out_start); // may throw boost::container::destroy_alloc_n(a, out_start, n_o - n_i); } } ////////////////////////////////////////////////////////////////////////////// // // move_assign_range_alloc_n // ////////////////////////////////////////////////////////////////////////////// template <typename A ,typename I // F models InputIterator ,typename O // G models OutputIterator > void move_assign_range_alloc_n( A &a, I inp_start, typename allocator_traits<A>::size_type n_i , O out_start, typename allocator_traits<A>::size_type n_o ) { if (n_o < n_i){ inp_start = boost::container::move_n_source_dest(inp_start, n_o, out_start); // may throw boost::container::uninitialized_move_alloc_n(a, inp_start, n_i - n_o, out_start); // may throw } else{ out_start = boost::container::move_n(inp_start, n_i, out_start); // may throw boost::container::destroy_alloc_n(a, out_start, n_o - n_i); } } } //namespace container { } //namespace boost { #include <boost/container/detail/config_end.hpp> #endif //#ifndef BOOST_CONTAINER_DETAIL_UTILITIES_HPP