diff options
Diffstat (limited to '3rdParty/Boost/src/boost/container/detail/utilities.hpp')
-rw-r--r-- | 3rdParty/Boost/src/boost/container/detail/utilities.hpp | 1152 |
1 files changed, 1083 insertions, 69 deletions
diff --git a/3rdParty/Boost/src/boost/container/detail/utilities.hpp b/3rdParty/Boost/src/boost/container/detail/utilities.hpp index ece9a2e..5aca542 100644 --- a/3rdParty/Boost/src/boost/container/detail/utilities.hpp +++ b/3rdParty/Boost/src/boost/container/detail/utilities.hpp @@ -1,6 +1,6 @@ ////////////////////////////////////////////////////////////////////////////// // -// (C) Copyright Ion Gaztanaga 2005-2012. Distributed under the Boost +// (C) Copyright Ion Gaztanaga 2005-2013. 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) // @@ -11,21 +11,92 @@ #ifndef BOOST_CONTAINER_DETAIL_UTILITIES_HPP #define BOOST_CONTAINER_DETAIL_UTILITIES_HPP -#include "config_begin.hpp" +#include <boost/container/detail/config_begin.hpp> +#include <boost/container/detail/workaround.hpp> + #include <cstdio> +#include <cstring> //for ::memmove / ::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/move/move.hpp> +#include <boost/type_traits/is_integral.hpp> +#include <boost/type_traits/is_floating_point.hpp> +#include <boost/type_traits/is_pointer.hpp> +#include <boost/type_traits/has_trivial_destructor.hpp> +#include <boost/type_traits/has_trivial_copy.hpp> +#include <boost/type_traits/has_trivial_assign.hpp> +#include <boost/type_traits/is_pod.hpp> +#include <boost/move/core.hpp> +#include <boost/move/utility.hpp> +#include <boost/move/iterator.hpp> +#include <boost/assert.hpp> +#include <boost/container/throw_exception.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/container/detail/memory_util.hpp> +#include <boost/intrusive/pointer_traits.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> @@ -46,42 +117,73 @@ 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) +enum NextCapacityOption { NextCapacityDouble, NextCapacity60Percent }; + +template<class SizeType, NextCapacityOption Option> +struct next_capacity_calculator; + +template<class SizeType> +struct next_capacity_calculator<SizeType, NextCapacityDouble> { -// if (n > max_size - capacity) -// throw std::length_error("get_next_capacity"); + static SizeType get(const SizeType max_size + ,const SizeType capacity + ,const SizeType n) + { + const SizeType remaining = max_size - capacity; + if ( remaining < n ) + boost::container::throw_length_error("get_next_capacity, allocator's max_size reached"); + const SizeType additional = max_value(n, capacity); + return ( remaining < additional ) ? max_size : ( capacity + additional ); + } +}; - const SizeType m3 = max_size/3; - if (capacity < m3) - return capacity + max_value(3*(capacity+1)/5, n); +template<class SizeType> +struct next_capacity_calculator<SizeType, NextCapacity60Percent> +{ + static SizeType get(const SizeType max_size + ,const SizeType capacity + ,const SizeType n) + { + const SizeType remaining = max_size - capacity; + if ( remaining < n ) + boost::container::throw_length_error("get_next_capacity, allocator's max_size reached"); + const SizeType m3 = max_size/3; - if (capacity < m3*2) - return capacity + max_value((capacity+1)/2, n); + if (capacity < m3) + return capacity + max_value(3*(capacity+1)/5, n); - return max_size; -} + 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* +inline typename boost::intrusive::pointer_traits<Pointer>::element_type* to_raw_pointer(const Pointer &p) { return boost::container::container_detail::to_raw_pointer(p.operator->()); } -//!To avoid ADL problems with swap template <class T> -inline void do_swap(T& x, T& y) -{ - using std::swap; - swap(x, y); -} +inline T* iterator_to_pointer(T* i) +{ return i; } + +template <class Iterator> +inline typename std::iterator_traits<Iterator>::pointer + iterator_to_pointer(const Iterator &i) +{ return i.operator->(); } + +template <class Iterator> +inline + typename boost::intrusive::pointer_traits + <typename std::iterator_traits<Iterator>::pointer>::element_type* + iterator_to_raw_pointer(const Iterator &i) +{ return (to_raw_pointer)((iterator_to_pointer)(i)); } + template<class AllocatorType> inline void swap_alloc(AllocatorType &, AllocatorType &, container_detail::false_type) @@ -90,7 +192,7 @@ inline void swap_alloc(AllocatorType &, AllocatorType &, container_detail::false template<class AllocatorType> inline void swap_alloc(AllocatorType &l, AllocatorType &r, container_detail::true_type) -{ container_detail::do_swap(l, r); } +{ boost::container::swap_dispatch(l, r); } template<class AllocatorType> inline void assign_alloc(AllocatorType &, const AllocatorType &, container_detail::false_type) @@ -123,70 +225,339 @@ 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 move_const_ref_type - : if_c -// < ::boost::is_fundamental<T>::value || ::boost::is_pointer<T>::value || ::boost::is_member_pointer<T>::value || ::boost::is_enum<T>::value - < !::boost::is_class<T>::value - ,const T & - ,BOOST_CATCH_CONST_RLVALUE(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_memtransfer_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_memtransfer_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_memtransfer_copy_constructible + : public enable_if_c<container_detail::is_memtransfer_copy_constructible<I, O>::value, R> +{}; + +template <typename I, typename O, typename R> +struct disable_if_memtransfer_copy_constructible + : public enable_if_c<!container_detail::is_memtransfer_copy_constructible<I, O>::value, R> +{}; + +template <typename I, typename O, typename R> +struct enable_if_memtransfer_copy_assignable + : public enable_if_c<container_detail::is_memtransfer_copy_assignable<I, O>::value, R> +{}; + +template <typename I, typename O, typename R> +struct disable_if_memtransfer_copy_assignable + : public enable_if_c<!container_detail::is_memtransfer_copy_assignable<I, O>::value, R> +{}; + +template + <typename I, // I models InputIterator + typename F> // F models ForwardIterator +inline F memmove(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); + ::memmove((iterator_to_raw_pointer)(r), (iterator_to_raw_pointer)(f), sizeof(value_type)*n); + std::advance(r, n); + return r; +} + +template + <typename I, // I models InputIterator + typename F> // F models ForwardIterator +F memmove_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; + ::memmove((iterator_to_raw_pointer)(r), (iterator_to_raw_pointer)(f), sizeof(value_type)*n); + std::advance(r, n); + return r; +} + +template + <typename I, // I models InputIterator + typename F> // F models ForwardIterator +I memmove_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; + ::memmove((iterator_to_raw_pointer)(r), (iterator_to_raw_pointer)(f), sizeof(value_type)*n); + std::advance(f, n); + return f; +} + +template + <typename I, // I models InputIterator + typename F> // F models ForwardIterator +I memmove_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; + ::memmove((iterator_to_raw_pointer)(r), (iterator_to_raw_pointer)(f), sizeof(value_type)*n); + std::advance(f, n); + std::advance(r, n); + return f; +} + +template <typename O> +struct is_memzero_initializable +{ + typedef typename ::std::iterator_traits<O>::value_type value_type; + static const bool value = are_elements_contiguous<O>::value && + ( ::boost::is_integral<value_type>::value || ::boost::is_enum<value_type>::value + #if defined(BOOST_CONTAINER_MEMZEROED_POINTER_IS_NULL) + || ::boost::is_pointer<value_type>::value + #endif + #if defined(BOOST_CONTAINER_MEMZEROED_FLOATING_POINT_IS_ZERO) + || ::boost::is_floating_point<value_type>::value + #endif + #if defined(BOOST_CONTAINER_MEMZEROED_FLOATING_POINT_IS_ZERO) && defined(BOOST_CONTAINER_MEMZEROED_POINTER_IS_NULL) + || ::boost::is_pod<value_type>::value + #endif + ); +}; + +template <typename O, typename R> +struct enable_if_memzero_initializable + : public enable_if_c<container_detail::is_memzero_initializable<O>::value, R> +{}; + +template <typename O, typename R> +struct disable_if_memzero_initializable + : public enable_if_c<!container_detail::is_memzero_initializable<O>::value, R> {}; } //namespace container_detail { + ////////////////////////////////////////////////////////////////////////////// // // uninitialized_move_alloc // ////////////////////////////////////////////////////////////////////////////// + //! <b>Effects</b>: //! \code -//! for (; first != last; ++result, ++first) -//! allocator_traits::construct(a, &*result, boost::move(*first)); +//! for (; f != l; ++r, ++f) +//! allocator_traits::construct(a, &*r, boost::move(*f)); //! \endcode //! -//! <b>Returns</b>: result +//! <b>Returns</b>: r template <typename A, typename I, // I models InputIterator typename F> // F models ForwardIterator -F uninitialized_move_alloc(A &a, I f, I l, F r) +inline typename container_detail::disable_if_memtransfer_copy_constructible<I, F, F>::type + uninitialized_move_alloc(A &a, I f, I l, F r) { - while (f != l) { - allocator_traits<A>::construct(a, container_detail::to_raw_pointer(&*r), boost::move(*f)); - ++f; ++r; + F back = r; + BOOST_TRY{ + while (f != l) { + allocator_traits<A>::construct(a, container_detail::iterator_to_raw_pointer(r), boost::move(*f)); + ++f; ++r; + } + } + BOOST_CATCH(...){ + for (; back != r; ++back){ + allocator_traits<A>::destroy(a, container_detail::iterator_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_memtransfer_copy_constructible<I, F, F>::type + uninitialized_move_alloc(A &, I f, I l, F r) BOOST_CONTAINER_NOEXCEPT +{ return container_detail::memmove(f, l, r); } + ////////////////////////////////////////////////////////////////////////////// // -// uninitialized_copy_alloc +// uninitialized_move_alloc_n // ////////////////////////////////////////////////////////////////////////////// //! <b>Effects</b>: //! \code -//! for (; first != last; ++result, ++first) -//! allocator_traits::construct(a, &*result, *first); +//! for (; n--; ++r, ++f) +//! allocator_traits::construct(a, &*r, boost::move(*f)); //! \endcode //! -//! <b>Returns</b>: result +//! <b>Returns</b>: r template <typename A, typename I, // I models InputIterator typename F> // F models ForwardIterator -F uninitialized_copy_alloc(A &a, I f, I l, F r) +inline typename container_detail::disable_if_memtransfer_copy_constructible<I, F, F>::type + uninitialized_move_alloc_n(A &a, I f, typename std::iterator_traits<I>::difference_type n, F r) { - while (f != l) { - allocator_traits<A>::construct(a, container_detail::to_raw_pointer(&*r), *f); - ++f; ++r; + F back = r; + BOOST_TRY{ + while (n--) { + allocator_traits<A>::construct(a, container_detail::iterator_to_raw_pointer(r), boost::move(*f)); + ++f; ++r; + } + } + BOOST_CATCH(...){ + for (; back != r; ++back){ + allocator_traits<A>::destroy(a, container_detail::iterator_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_memtransfer_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::memmove_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_memtransfer_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::iterator_to_raw_pointer(r), boost::move(*f)); + ++f; ++r; + } + } + BOOST_CATCH(...){ + for (; back != r; ++back){ + allocator_traits<A>::destroy(a, container_detail::iterator_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_memtransfer_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::memmove_n_source(f, n, r); } + ////////////////////////////////////////////////////////////////////////////// // // uninitialized_copy_alloc @@ -195,58 +566,701 @@ F uninitialized_copy_alloc(A &a, I f, I l, F r) //! <b>Effects</b>: //! \code -//! for (; first != last; ++result, ++first) -//! allocator_traits::construct(a, &*result, *first); +//! 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_memtransfer_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::iterator_to_raw_pointer(r), *f); + ++f; ++r; + } + } + BOOST_CATCH(...){ + for (; back != r; ++back){ + allocator_traits<A>::destroy(a, container_detail::iterator_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_memtransfer_copy_constructible<I, F, F>::type + uninitialized_copy_alloc(A &, I f, I l, F r) BOOST_CONTAINER_NOEXCEPT +{ return container_detail::memmove(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_memtransfer_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::iterator_to_raw_pointer(r), *f); + ++f; ++r; + } + } + BOOST_CATCH(...){ + for (; back != r; ++back){ + allocator_traits<A>::destroy(a, container_detail::iterator_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_memtransfer_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::memmove_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_memtransfer_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::iterator_to_raw_pointer(r), *f); + ++f; ++r; + } + } + BOOST_CATCH(...){ + for (; back != r; ++back){ + allocator_traits<A>::destroy(a, container_detail::iterator_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_memtransfer_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::memmove_n_source(f, n, r); } + +////////////////////////////////////////////////////////////////////////////// +// +// uninitialized_value_init_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 typename container_detail::disable_if_memzero_initializable<F, F>::type + uninitialized_value_init_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::iterator_to_raw_pointer(r)); + ++r; + } + } + BOOST_CATCH(...){ + for (; back != r; ++back){ + allocator_traits<A>::destroy(a, container_detail::iterator_to_raw_pointer(back)); + } + BOOST_RETHROW; + } + BOOST_CATCH_END + return r; +} + +template + <typename A, + typename F> // F models ForwardIterator +inline typename container_detail::enable_if_memzero_initializable<F, F>::type + uninitialized_value_init_alloc_n(A &, typename allocator_traits<A>::difference_type n, F r) +{ + typedef typename std::iterator_traits<F>::value_type value_type; + ::memset((void*)container_detail::iterator_to_raw_pointer(r), 0, sizeof(value_type)*n); + std::advance(r, n); + return r; +} + +////////////////////////////////////////////////////////////////////////////// +// +// uninitialized_default_init_alloc_n +// +////////////////////////////////////////////////////////////////////////////// + +//! <b>Effects</b>: +//! \code +//! for (; n--; ++r, ++f) +//! allocator_traits::construct(a, &*r); //! \endcode //! -//! <b>Returns</b>: result +//! <b>Returns</b>: r +template + <typename A, + typename F> // F models ForwardIterator +inline F uninitialized_default_init_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::iterator_to_raw_pointer(r), default_init); + ++r; + } + } + BOOST_CATCH(...){ + for (; back != r; ++back){ + allocator_traits<A>::destroy(a, container_detail::iterator_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> -void uninitialized_fill_alloc(A &a, F f, F l, const T &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::iterator_to_raw_pointer(f), t); + ++f; + } + } + BOOST_CATCH(...){ + for (; back != l; ++back){ + allocator_traits<A>::destroy(a, container_detail::iterator_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::iterator_to_raw_pointer(r), v); + ++r; + } + } + BOOST_CATCH(...){ + for (; back != r; ++back){ + allocator_traits<A>::destroy(a, container_detail::iterator_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_memtransfer_copy_assignable<I, F, F>::type + copy(I f, I l, F r) { while (f != l) { - allocator_traits<A>::construct(a, container_detail::to_raw_pointer(&*f), t); - ++f; + *r = *f; + ++f; ++r; + } + return r; +} + +template +<typename I, // I models InputIterator +typename F> // F models ForwardIterator +inline typename container_detail::enable_if_memtransfer_copy_assignable<I, F, F>::type + copy(I f, I l, F r) BOOST_CONTAINER_NOEXCEPT +{ return container_detail::memmove(f, l, r); } + +////////////////////////////////////////////////////////////////////////////// +// +// copy_n +// +////////////////////////////////////////////////////////////////////////////// + +template +<typename I, // I models InputIterator +typename F> // F models ForwardIterator +inline typename container_detail::disable_if_memtransfer_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_memtransfer_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::memmove_n(f, n, r); } + ////////////////////////////////////////////////////////////////////////////// // -// uninitialized_copy_or_move_alloc +// copy_n_source // ////////////////////////////////////////////////////////////////////////////// template -<typename A -,typename I // I models InputIterator +<typename I, // I models InputIterator +typename F> // F models ForwardIterator +inline typename container_detail::disable_if_memtransfer_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_memtransfer_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::memmove_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_memtransfer_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_memtransfer_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::memmove_n_source_dest(f, n, r); } + +////////////////////////////////////////////////////////////////////////////// +// +// move +// +////////////////////////////////////////////////////////////////////////////// + +template +<typename I, // I models InputIterator +typename F> // F models ForwardIterator +inline typename container_detail::disable_if_memtransfer_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_memtransfer_copy_assignable<I, F, F>::type + move(I f, I l, F r) BOOST_CONTAINER_NOEXCEPT +{ return container_detail::memmove(f, l, r); } + +////////////////////////////////////////////////////////////////////////////// +// +// move_n +// +////////////////////////////////////////////////////////////////////////////// + +template +<typename I, // I models InputIterator +typename F> // F models ForwardIterator +inline typename container_detail::disable_if_memtransfer_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_memtransfer_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::memmove_n(f, n, r); } + +////////////////////////////////////////////////////////////////////////////// +// +// move_n_source +// +////////////////////////////////////////////////////////////////////////////// + +template +<typename I // I models InputIterator ,typename F> // F models ForwardIterator -F uninitialized_copy_or_move_alloc - (A &a, I f, I l, F r - ,typename boost::container::container_detail::enable_if - < boost::move_detail::is_move_iterator<I> >::type* = 0) +inline typename container_detail::disable_if_memtransfer_copy_assignable<I, F, I>::type + move_n_source(I f, typename std::iterator_traits<I>::difference_type n, F r) { - return ::boost::container::uninitialized_move_alloc(a, f, l, r); + while (n--) { + *r = ::boost::move(*f); + ++f; ++r; + } + return f; } template -<typename A -,typename I // I models InputIterator +<typename I // I models InputIterator ,typename F> // F models ForwardIterator -F uninitialized_copy_or_move_alloc - (A &a, I f, I l, F r - ,typename boost::container::container_detail::disable_if - < boost::move_detail::is_move_iterator<I> >::type* = 0) +inline typename container_detail::enable_if_memtransfer_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::memmove_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_memtransfer_copy_assignable<I, F, I>::type + move_n_source_dest(I f, typename std::iterator_traits<I>::difference_type n, F &r) { - return ::boost::container::uninitialized_copy_alloc(a, f, l, 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_memtransfer_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::memmove_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::iterator_to_raw_pointer(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_memtransfer_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_memtransfer_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; + void *const large_ptr = static_cast<void*>(container_detail::iterator_to_raw_pointer(large_range_f)); + void *const short_ptr = static_cast<void*>(container_detail::iterator_to_raw_pointer(short_range_f)); + void *const stora_ptr = static_cast<void*>(container_detail::iterator_to_raw_pointer(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_memtransfer_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::iterator_to_raw_pointer(large_range_f))); + char *short_ptr = static_cast<char*>(static_cast<void*>(container_detail::iterator_to_raw_pointer(short_range_f))); + char *stora_ptr = static_cast<char*>(static_cast<void*>(&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; + BOOST_CONTAINER_FALLTHOUGH + 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; + BOOST_CONTAINER_FALLTHOUGH + 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; + BOOST_CONTAINER_FALLTHOUGH + 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 |