diff options
Diffstat (limited to 'boost/container/detail/utilities.hpp')
-rw-r--r-- | boost/container/detail/utilities.hpp | 1267 |
1 files changed, 0 insertions, 1267 deletions
diff --git a/boost/container/detail/utilities.hpp b/boost/container/detail/utilities.hpp deleted file mode 100644 index 25f035df50..0000000000 --- a/boost/container/detail/utilities.hpp +++ /dev/null @@ -1,1267 +0,0 @@ -////////////////////////////////////////////////////////////////////////////// -// -// (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) -// -// See http://www.boost.org/libs/container for documentation. -// -////////////////////////////////////////////////////////////////////////////// - -#ifndef BOOST_CONTAINER_DETAIL_UTILITIES_HPP -#define BOOST_CONTAINER_DETAIL_UTILITIES_HPP - -#if defined(_MSC_VER) -# pragma once -#endif - -#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_pointer.hpp> -#include <boost/type_traits/is_enum.hpp> -#include <boost/type_traits/is_class.hpp> -#include <boost/type_traits/is_integral.hpp> -#include <boost/type_traits/is_floating_point.hpp> -#include <boost/type_traits/is_copy_constructible.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_core.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/core/no_exceptions_support.hpp> -#include <boost/container/detail/memory_util.hpp> -#include <boost/intrusive/pointer_traits.hpp> -#include <boost/aligned_storage.hpp> -#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; } - -enum NextCapacityOption { NextCapacityDouble, NextCapacity60Percent }; - -template<class SizeType, NextCapacityOption Option> -struct next_capacity_calculator; - -template<class SizeType> -struct next_capacity_calculator<SizeType, NextCapacityDouble> -{ - 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 ); - } -}; - - -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) - 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 boost::intrusive::pointer_traits<Pointer>::element_type* - to_raw_pointer(const Pointer &p) -{ return boost::container::container_detail::to_raw_pointer(p.operator->()); } - -template <class T> -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) - 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_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 (; 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_memtransfer_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::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_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_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) -{ - 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 -// -////////////////////////////////////////////////////////////////////////////// - -//! <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_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>: 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> -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) { - *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); } - -////////////////////////////////////////////////////////////////////////////// -// -// copy_n_source -// -////////////////////////////////////////////////////////////////////////////// - -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(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 -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) -{ - 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(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) -{ - 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 |