diff options
Diffstat (limited to 'boost/move')
-rw-r--r-- | boost/move/algo/adaptive_sort.hpp | 15 | ||||
-rw-r--r-- | boost/move/algo/detail/adaptive_sort_merge.hpp | 95 | ||||
-rw-r--r-- | boost/move/algo/detail/basic_op.hpp | 20 | ||||
-rw-r--r-- | boost/move/algo/detail/insertion_sort.hpp | 19 | ||||
-rw-r--r-- | boost/move/algo/detail/merge.hpp | 80 | ||||
-rw-r--r-- | boost/move/algo/detail/merge_sort.hpp | 12 | ||||
-rw-r--r-- | boost/move/algo/move.hpp | 3 | ||||
-rw-r--r-- | boost/move/algo/predicate.hpp | 86 | ||||
-rw-r--r-- | boost/move/algo/unique.hpp | 55 | ||||
-rw-r--r-- | boost/move/detail/destruct_n.hpp | 7 | ||||
-rw-r--r-- | boost/move/detail/fwd_macros.hpp | 25 | ||||
-rw-r--r-- | boost/move/detail/iterator_to_raw_pointer.hpp | 59 | ||||
-rw-r--r-- | boost/move/detail/pointer_element.hpp | 168 | ||||
-rw-r--r-- | boost/move/detail/to_raw_pointer.hpp | 45 | ||||
-rw-r--r-- | boost/move/detail/unique_ptr_meta_utils.hpp | 2 |
15 files changed, 544 insertions, 147 deletions
diff --git a/boost/move/algo/adaptive_sort.hpp b/boost/move/algo/adaptive_sort.hpp index 6b5586e587..c96ab2d78b 100644 --- a/boost/move/algo/adaptive_sort.hpp +++ b/boost/move/algo/adaptive_sort.hpp @@ -43,18 +43,25 @@ namespace movelib { //! ceil(sqrt(std::distance(first, last)))*2. //! //! <b>Caution</b>: Experimental implementation, not production-ready. -template<class RandIt, class Compare> +template<class RandIt, class RandRawIt, class Compare> void adaptive_sort( RandIt first, RandIt last, Compare comp - , typename iterator_traits<RandIt>::value_type* uninitialized = 0 - , std::size_t uninitialized_len = 0) + , RandRawIt uninitialized + , std::size_t uninitialized_len) { typedef typename iterator_traits<RandIt>::size_type size_type; typedef typename iterator_traits<RandIt>::value_type value_type; - ::boost::movelib::detail_adaptive::adaptive_xbuf<value_type> xbuf(uninitialized, uninitialized_len); + ::boost::movelib::detail_adaptive::adaptive_xbuf<value_type, RandRawIt> xbuf(uninitialized, uninitialized_len); ::boost::movelib::detail_adaptive::adaptive_sort_impl(first, size_type(last - first), comp, xbuf); } +template<class RandIt, class Compare> +void adaptive_sort( RandIt first, RandIt last, Compare comp) +{ + typedef typename iterator_traits<RandIt>::value_type value_type; + adaptive_sort(first, last, comp, (value_type*)0, 0u); +} + } //namespace movelib { } //namespace boost { diff --git a/boost/move/algo/detail/adaptive_sort_merge.hpp b/boost/move/algo/detail/adaptive_sort_merge.hpp index 63b3f45979..60b5e7b06c 100644 --- a/boost/move/algo/detail/adaptive_sort_merge.hpp +++ b/boost/move/algo/detail/adaptive_sort_merge.hpp @@ -154,20 +154,20 @@ typename iterator_traits<ForwardIt>::size_type return count; } -template<class T> +template<class T, class RandRawIt = T*> class adaptive_xbuf { adaptive_xbuf(const adaptive_xbuf &); adaptive_xbuf & operator=(const adaptive_xbuf &); public: - typedef T* iterator; + typedef RandRawIt iterator; adaptive_xbuf() - : m_ptr(0), m_size(0), m_capacity(0) + : m_ptr(), m_size(0), m_capacity(0) {} - adaptive_xbuf(T *raw_memory, std::size_t capacity) + adaptive_xbuf(RandRawIt raw_memory, std::size_t capacity) : m_ptr(raw_memory), m_size(0), m_capacity(capacity) {} @@ -183,7 +183,7 @@ class adaptive_xbuf m_size = n; } else{ - T *result = boost::move(first, first+m_size, m_ptr); + RandRawIt result = boost::move(first, first+m_size, m_ptr); boost::uninitialized_move(first+m_size, first+n, result); m_size = n; } @@ -201,8 +201,8 @@ class adaptive_xbuf iterator add(RandIt it) { BOOST_ASSERT(m_size < m_capacity); - T * p_ret = m_ptr + m_size; - ::new(p_ret) T(::boost::move(*it)); + RandRawIt p_ret = m_ptr + m_size; + ::new(&*p_ret) T(::boost::move(*it)); ++m_size; return p_ret; } @@ -249,14 +249,26 @@ class adaptive_xbuf } } + private: + template<class RIt> + static bool is_raw_ptr(RIt) + { + return false; + } + + static bool is_raw_ptr(T*) + { + return true; + } + + public: template<class U> bool supports_aligned_trailing(std::size_t size, std::size_t trail_count) const { - if(this->data()){ - uintptr_t u_addr_sz = uintptr_t(this->data()+size); - uintptr_t u_addr_cp = uintptr_t(this->data()+this->capacity()); + if(this->is_raw_ptr(this->data()) && m_capacity){ + uintptr_t u_addr_sz = uintptr_t(&*(this->data()+size)); + uintptr_t u_addr_cp = uintptr_t(&*(this->data()+this->capacity())); u_addr_sz = ((u_addr_sz + sizeof(U)-1)/sizeof(U))*sizeof(U); - return (u_addr_cp >= u_addr_sz) && ((u_addr_cp - u_addr_sz)/sizeof(U) >= trail_count); } return false; @@ -271,7 +283,7 @@ class adaptive_xbuf template<class U> U *aligned_trailing(std::size_t pos) const { - uintptr_t u_addr = uintptr_t(this->data()+pos); + uintptr_t u_addr = uintptr_t(&*(this->data()+pos)); u_addr = ((u_addr + sizeof(U)-1)/sizeof(U))*sizeof(U); return (U*)u_addr; } @@ -302,7 +314,7 @@ class adaptive_xbuf } private: - T *m_ptr; + RandRawIt m_ptr; std::size_t m_size; std::size_t m_capacity; }; @@ -458,7 +470,7 @@ RandIt partial_merge_bufferless_impl if(first1 != last1 && comp(*last1, last1[-1])){ do{ RandIt const old_last1 = last1; - last1 = lower_bound(last1, last2, *first1, comp); + last1 = boost::movelib::lower_bound(last1, last2, *first1, comp); first1 = rotate_gcd(first1, old_last1, last1);//old_last1 == last1 supported if(last1 == last2){ return first1; @@ -604,13 +616,13 @@ void op_buffered_merge size_type const len1 = size_type(middle-first); size_type const len2 = size_type(last-middle); if(len1 <= len2){ - first = upper_bound(first, middle, *middle, comp); + first = boost::movelib::upper_bound(first, middle, *middle, comp); xbuf.move_assign(first, size_type(middle-first)); op_merge_with_right_placed (xbuf.data(), xbuf.end(), first, middle, last, comp, op); } else{ - last = lower_bound(middle, last, middle[-1], comp); + last = boost::movelib::lower_bound(middle, last, middle[-1], comp); xbuf.move_assign(middle, size_type(last-middle)); op_merge_with_left_placed (first, middle, last, xbuf.data(), xbuf.end(), comp, op); @@ -618,11 +630,11 @@ void op_buffered_merge } } -template<class RandIt, class Compare> +template<class RandIt, class Compare, class XBuf> void buffered_merge ( RandIt first, RandIt const middle, RandIt last , Compare comp - , adaptive_xbuf<typename iterator_traits<RandIt>::value_type> &xbuf) + , XBuf &xbuf) { op_buffered_merge(first, middle, last, comp, move_op(), xbuf); } @@ -633,15 +645,14 @@ void buffered_merge // in the begining of the range, and ordered according to comp // // Returns the number of collected keys -template<class RandIt, class Compare> +template<class RandIt, class Compare, class XBuf> typename iterator_traits<RandIt>::size_type collect_unique ( RandIt const first, RandIt const last , typename iterator_traits<RandIt>::size_type const max_collected, Compare comp - , adaptive_xbuf<typename iterator_traits<RandIt>::value_type> & xbuf) + , XBuf & xbuf) { typedef typename iterator_traits<RandIt>::size_type size_type; - typedef typename iterator_traits<RandIt>::value_type value_type; size_type h = 0; if(max_collected){ ++h; // first key is always here @@ -650,9 +661,9 @@ typename iterator_traits<RandIt>::size_type RandIt search_end = u; if(xbuf.capacity() >= max_collected){ - value_type *const ph0 = xbuf.add(first); + typename XBuf::iterator const ph0 = xbuf.add(first); while(u != last && h < max_collected){ - value_type * const r = lower_bound(ph0, xbuf.end(), *u, comp); + typename XBuf::iterator const r = boost::movelib::lower_bound(ph0, xbuf.end(), *u, comp); //If key not found add it to [h, h+h0) if(r == xbuf.end() || comp(*u, *r) ){ RandIt const new_h0 = boost::move(search_end, u, h0); @@ -669,7 +680,7 @@ typename iterator_traits<RandIt>::size_type } else{ while(u != last && h < max_collected){ - RandIt const r = lower_bound(h0, search_end, *u, comp); + RandIt const r = boost::movelib::lower_bound(h0, search_end, *u, comp); //If key not found add it to [h, h+h0) if(r == search_end || comp(*u, *r) ){ RandIt const new_h0 = rotate_gcd(h0, search_end, u); @@ -1666,14 +1677,14 @@ void op_merge_right_step_once // // As a last step, if auxiliary memory is available in-place merge is performed. // until all is merged or auxiliary memory is not large enough. -template<class RandIt, class Compare> +template<class RandIt, class Compare, class XBuf> typename iterator_traits<RandIt>::size_type adaptive_sort_build_blocks ( RandIt const first , typename iterator_traits<RandIt>::size_type const len , typename iterator_traits<RandIt>::size_type const l_base , typename iterator_traits<RandIt>::size_type const l_build_buf - , adaptive_xbuf<typename iterator_traits<RandIt>::value_type> & xbuf + , XBuf & xbuf , Compare comp) { typedef typename iterator_traits<RandIt>::size_type size_type; @@ -1820,7 +1831,7 @@ void adaptive_sort_combine_blocks //Returns true if buffer is placed in //[buffer+len-l_intbuf, buffer+len). Otherwise, buffer is //[buffer,buffer+l_intbuf) -template<class RandIt, class Compare> +template<class RandIt, class Compare, class XBuf> bool adaptive_sort_combine_all_blocks ( RandIt keys , typename iterator_traits<RandIt>::size_type &n_keys @@ -1828,7 +1839,7 @@ bool adaptive_sort_combine_all_blocks , typename iterator_traits<RandIt>::size_type const l_buf_plus_data , typename iterator_traits<RandIt>::size_type l_merged , typename iterator_traits<RandIt>::size_type &l_intbuf - , adaptive_xbuf<typename iterator_traits<RandIt>::value_type> & xbuf + , XBuf & xbuf , Compare comp) { typedef typename iterator_traits<RandIt>::size_type size_type; @@ -1916,11 +1927,11 @@ bool adaptive_sort_combine_all_blocks return buffer_right; } -template<class RandIt, class Compare> +template<class RandIt, class Compare, class XBuf> void stable_merge ( RandIt first, RandIt const middle, RandIt last , Compare comp - , adaptive_xbuf<typename iterator_traits<RandIt>::value_type> &xbuf) + , XBuf &xbuf) { BOOST_ASSERT(xbuf.empty()); typedef typename iterator_traits<RandIt>::size_type size_type; @@ -1937,13 +1948,13 @@ void stable_merge } -template<class RandIt, class Compare> +template<class RandIt, class Compare, class XBuf> void adaptive_sort_final_merge( bool buffer_right , RandIt const first , typename iterator_traits<RandIt>::size_type const l_intbuf , typename iterator_traits<RandIt>::size_type const n_keys , typename iterator_traits<RandIt>::size_type const len - , adaptive_xbuf<typename iterator_traits<RandIt>::value_type> & xbuf + , XBuf & xbuf , Compare comp) { //BOOST_ASSERT(n_keys || xbuf.size() == l_intbuf); @@ -1973,11 +1984,11 @@ void adaptive_sort_final_merge( bool buffer_right BOOST_MOVE_ADAPTIVE_SORT_PRINT(" After final_merge : ", len); } -template<class RandIt, class Compare, class Unsigned, class T> +template<class RandIt, class Compare, class Unsigned, class XBuf> bool adaptive_sort_build_params (RandIt first, Unsigned const len, Compare comp , Unsigned &n_keys, Unsigned &l_intbuf, Unsigned &l_base, Unsigned &l_build_buf - , adaptive_xbuf<T> & xbuf + , XBuf & xbuf ) { typedef Unsigned size_type; @@ -2064,7 +2075,7 @@ bool adaptive_sort_build_params return true; } -template<class RandIt, class Compare> +template<class RandIt, class Compare, class XBuf> inline void adaptive_merge_combine_blocks( RandIt first , typename iterator_traits<RandIt>::size_type len1 , typename iterator_traits<RandIt>::size_type len2 @@ -2074,7 +2085,7 @@ inline void adaptive_merge_combine_blocks( RandIt first , bool use_internal_buf , bool xbuf_used , Compare comp - , adaptive_xbuf<typename iterator_traits<RandIt>::value_type> & xbuf + , XBuf & xbuf ) { typedef typename iterator_traits<RandIt>::size_type size_type; @@ -2135,7 +2146,7 @@ inline void adaptive_merge_combine_blocks( RandIt first } } -template<class RandIt, class Compare> +template<class RandIt, class Compare, class XBuf> inline void adaptive_merge_final_merge( RandIt first , typename iterator_traits<RandIt>::size_type len1 , typename iterator_traits<RandIt>::size_type len2 @@ -2145,7 +2156,7 @@ inline void adaptive_merge_final_merge( RandIt first , bool use_internal_buf , bool xbuf_used , Compare comp - , adaptive_xbuf<typename iterator_traits<RandIt>::value_type> & xbuf + , XBuf & xbuf ) { typedef typename iterator_traits<RandIt>::size_type size_type; @@ -2270,12 +2281,12 @@ inline SizeType adaptive_merge_n_keys_intbuf(SizeType &rl_block, SizeType len1, // // * If auxiliary memory is available, the "build_blocks" will be extended to build bigger blocks // using classic merge. -template<class RandIt, class Compare> +template<class RandIt, class Compare, class XBuf> void adaptive_sort_impl ( RandIt first , typename iterator_traits<RandIt>::size_type const len , Compare comp - , adaptive_xbuf<typename iterator_traits<RandIt>::value_type> & xbuf + , XBuf & xbuf ) { typedef typename iterator_traits<RandIt>::size_type size_type; @@ -2368,13 +2379,13 @@ void adaptive_sort_impl // * If auxiliary memory is more than csqrtlen+n_keys*sizeof(std::size_t), // then no csqrtlen need to be extracted and "combine_blocks" will use integral // keys to combine blocks. -template<class RandIt, class Compare> +template<class RandIt, class Compare, class XBuf> void adaptive_merge_impl ( RandIt first , typename iterator_traits<RandIt>::size_type const len1 , typename iterator_traits<RandIt>::size_type const len2 , Compare comp - , adaptive_xbuf<typename iterator_traits<RandIt>::value_type> & xbuf + , XBuf & xbuf ) { typedef typename iterator_traits<RandIt>::size_type size_type; diff --git a/boost/move/algo/detail/basic_op.hpp b/boost/move/algo/detail/basic_op.hpp index a9369e07ba..ea5faf0e53 100644 --- a/boost/move/algo/detail/basic_op.hpp +++ b/boost/move/algo/detail/basic_op.hpp @@ -35,19 +35,19 @@ struct four_way_t{}; struct move_op { template <class SourceIt, class DestinationIt> - void operator()(SourceIt source, DestinationIt dest) + BOOST_MOVE_FORCEINLINE void operator()(SourceIt source, DestinationIt dest) { *dest = ::boost::move(*source); } template <class SourceIt, class DestinationIt> - DestinationIt operator()(forward_t, SourceIt first, SourceIt last, DestinationIt dest_begin) + BOOST_MOVE_FORCEINLINE DestinationIt operator()(forward_t, SourceIt first, SourceIt last, DestinationIt dest_begin) { return ::boost::move(first, last, dest_begin); } template <class SourceIt, class DestinationIt> - DestinationIt operator()(backward_t, SourceIt first, SourceIt last, DestinationIt dest_last) + BOOST_MOVE_FORCEINLINE DestinationIt operator()(backward_t, SourceIt first, SourceIt last, DestinationIt dest_last) { return ::boost::move_backward(first, last, dest_last); } template <class SourceIt, class DestinationIt1, class DestinationIt2> - void operator()(three_way_t, SourceIt srcit, DestinationIt1 dest1it, DestinationIt2 dest2it) + BOOST_MOVE_FORCEINLINE void operator()(three_way_t, SourceIt srcit, DestinationIt1 dest1it, DestinationIt2 dest2it) { *dest2it = boost::move(*dest1it); *dest1it = boost::move(*srcit); @@ -64,7 +64,7 @@ struct move_op } template <class SourceIt, class DestinationIt1, class DestinationIt2, class DestinationIt3> - void operator()(four_way_t, SourceIt srcit, DestinationIt1 dest1it, DestinationIt2 dest2it, DestinationIt3 dest3it) + BOOST_MOVE_FORCEINLINE void operator()(four_way_t, SourceIt srcit, DestinationIt1 dest1it, DestinationIt2 dest2it, DestinationIt3 dest3it) { *dest3it = boost::move(*dest2it); *dest2it = boost::move(*dest1it); @@ -75,19 +75,19 @@ struct move_op struct swap_op { template <class SourceIt, class DestinationIt> - void operator()(SourceIt source, DestinationIt dest) + BOOST_MOVE_FORCEINLINE void operator()(SourceIt source, DestinationIt dest) { boost::adl_move_swap(*dest, *source); } template <class SourceIt, class DestinationIt> - DestinationIt operator()(forward_t, SourceIt first, SourceIt last, DestinationIt dest_begin) + BOOST_MOVE_FORCEINLINE DestinationIt operator()(forward_t, SourceIt first, SourceIt last, DestinationIt dest_begin) { return boost::adl_move_swap_ranges(first, last, dest_begin); } template <class SourceIt, class DestinationIt> - DestinationIt operator()(backward_t, SourceIt first, SourceIt last, DestinationIt dest_begin) + BOOST_MOVE_FORCEINLINE DestinationIt operator()(backward_t, SourceIt first, SourceIt last, DestinationIt dest_begin) { return boost::adl_move_swap_ranges_backward(first, last, dest_begin); } template <class SourceIt, class DestinationIt1, class DestinationIt2> - void operator()(three_way_t, SourceIt srcit, DestinationIt1 dest1it, DestinationIt2 dest2it) + BOOST_MOVE_FORCEINLINE void operator()(three_way_t, SourceIt srcit, DestinationIt1 dest1it, DestinationIt2 dest2it) { typename ::boost::movelib::iterator_traits<SourceIt>::value_type tmp(boost::move(*dest2it)); *dest2it = boost::move(*dest1it); @@ -105,7 +105,7 @@ struct swap_op } template <class SourceIt, class DestinationIt1, class DestinationIt2, class DestinationIt3> - void operator()(four_way_t, SourceIt srcit, DestinationIt1 dest1it, DestinationIt2 dest2it, DestinationIt3 dest3it) + BOOST_MOVE_FORCEINLINE void operator()(four_way_t, SourceIt srcit, DestinationIt1 dest1it, DestinationIt2 dest2it, DestinationIt3 dest3it) { typename ::boost::movelib::iterator_traits<SourceIt>::value_type tmp(boost::move(*dest3it)); *dest3it = boost::move(*dest2it); diff --git a/boost/move/algo/detail/insertion_sort.hpp b/boost/move/algo/detail/insertion_sort.hpp index 15df35d9d6..3328f75748 100644 --- a/boost/move/algo/detail/insertion_sort.hpp +++ b/boost/move/algo/detail/insertion_sort.hpp @@ -31,6 +31,7 @@ #include <boost/move/detail/destruct_n.hpp> #include <boost/move/algo/detail/basic_op.hpp> #include <boost/move/detail/placement_new.hpp> +#include <boost/move/detail/iterator_to_raw_pointer.hpp> namespace boost { namespace movelib{ @@ -91,30 +92,30 @@ void insertion_sort(BirdirectionalIterator first, BirdirectionalIterator last, C } } -template <class Compare, class BirdirectionalIterator> +template <class Compare, class BirdirectionalIterator, class BirdirectionalRawIterator> void insertion_sort_uninitialized_copy (BirdirectionalIterator first1, BirdirectionalIterator const last1 - , typename iterator_traits<BirdirectionalIterator>::value_type* const first2 + , BirdirectionalRawIterator const first2 , Compare comp) { typedef typename iterator_traits<BirdirectionalIterator>::value_type value_type; if (first1 != last1){ - value_type* last2 = first2; - ::new(last2, boost_move_new_t()) value_type(move(*first1)); - destruct_n<value_type> d(first2); + BirdirectionalRawIterator last2 = first2; + ::new((iterator_to_raw_pointer)(last2), boost_move_new_t()) value_type(move(*first1)); + destruct_n<value_type, BirdirectionalRawIterator> d(first2); d.incr(); for (++last2; ++first1 != last1; ++last2){ - value_type* j2 = last2; - value_type* k2 = j2; + BirdirectionalRawIterator j2 = last2; + BirdirectionalRawIterator k2 = j2; if (comp(*first1, *--k2)){ - ::new(j2, boost_move_new_t()) value_type(move(*k2)); + ::new((iterator_to_raw_pointer)(j2), boost_move_new_t()) value_type(move(*k2)); d.incr(); for (--j2; k2 != first2 && comp(*first1, *--k2); --j2) *j2 = move(*k2); *j2 = move(*first1); } else{ - ::new(j2, boost_move_new_t()) value_type(move(*first1)); + ::new((iterator_to_raw_pointer)(j2), boost_move_new_t()) value_type(move(*first1)); d.incr(); } } diff --git a/boost/move/algo/detail/merge.hpp b/boost/move/algo/detail/merge.hpp index 988ffd35be..621dfa28af 100644 --- a/boost/move/algo/detail/merge.hpp +++ b/boost/move/algo/detail/merge.hpp @@ -16,6 +16,8 @@ #include <boost/move/algo/detail/basic_op.hpp> #include <boost/move/detail/iterator_traits.hpp> #include <boost/move/detail/destruct_n.hpp> +#include <boost/move/algo/predicate.hpp> +#include <boost/move/detail/iterator_to_raw_pointer.hpp> #include <boost/assert.hpp> namespace boost { @@ -181,9 +183,6 @@ void op_merge_left( RandIt buf_first //and all elements from the second half are less) op(forward_t(), first1, last1, buf_first); } - else{ - buf_first = buf_first; - } } // [buf_first, first1) -> buffer @@ -312,13 +311,13 @@ void merge_bufferless_ONlogN_recursive if (len1 > len2) { len11 = len1 / 2; first_cut += len11; - second_cut = lower_bound(middle, last, *first_cut, comp); + second_cut = boost::movelib::lower_bound(middle, last, *first_cut, comp); len22 = size_type(second_cut - middle); } else { len22 = len2 / 2; second_cut += len22; - first_cut = upper_bound(first, middle, *second_cut, comp); + first_cut = boost::movelib::upper_bound(first, middle, *second_cut, comp); len11 = size_type(first_cut - first); } BidirIt new_middle = rotate_gcd(first_cut, middle, second_cut); @@ -359,7 +358,7 @@ void merge_bufferless_ON2(RandIt first, RandIt middle, RandIt last, Compare comp if((middle - first) < (last - middle)){ while(first != middle){ RandIt const old_last1 = middle; - middle = lower_bound(middle, last, *first, comp); + middle = boost::movelib::lower_bound(middle, last, *first, comp); first = rotate_gcd(first, old_last1, middle); if(middle == last){ break; @@ -371,7 +370,7 @@ void merge_bufferless_ON2(RandIt first, RandIt middle, RandIt last, Compare comp } else{ while(middle != last){ - RandIt p = upper_bound(first, middle, last[-1], comp); + RandIt p = boost::movelib::upper_bound(first, middle, last[-1], comp); last = rotate_gcd(p, middle, last); middle = p; if(middle == first){ @@ -396,65 +395,6 @@ void merge_bufferless(RandIt first, RandIt middle, RandIt last, Compare comp) #endif //BOOST_ADAPTIVE_MERGE_NLOGN_MERGE } -template<class Comp> -struct antistable -{ - explicit antistable(Comp &comp) - : m_comp(comp) - {} - - template<class U, class V> - bool operator()(const U &u, const V & v) - { return !m_comp(v, u); } - - private: - antistable & operator=(const antistable &); - Comp &m_comp; -}; - -template <class Comp> -class negate -{ - public: - negate() - {} - - explicit negate(Comp comp) - : m_comp(comp) - {} - - template <class T1, class T2> - bool operator()(const T1& l, const T2& r) - { - return !m_comp(l, r); - } - - private: - Comp m_comp; -}; - - -template <class Comp> -class inverse -{ - public: - inverse() - {} - - explicit inverse(Comp comp) - : m_comp(comp) - {} - - template <class T1, class T2> - bool operator()(const T1& l, const T2& r) - { - return m_comp(r, l); - } - - private: - Comp m_comp; -}; - // [r_first, r_last) are already in the right part of the destination range. template <class Compare, class InputIterator, class InputOutIterator, class Op> void op_merge_with_right_placed @@ -557,12 +497,12 @@ void uninitialized_merge_with_right_placed typedef typename iterator_traits<InputOutIterator>::value_type value_type; InputOutIterator const original_r_first = r_first; - destruct_n<value_type> d(&*dest_first); + destruct_n<value_type, InputOutIterator> d(dest_first); while ( first != last && dest_first != original_r_first ) { if (r_first == r_last) { for(; dest_first != original_r_first; ++dest_first, ++first){ - ::new(&*dest_first) value_type(::boost::move(*first)); + ::new((iterator_to_raw_pointer)(dest_first)) value_type(::boost::move(*first)); d.incr(); } d.release(); @@ -572,12 +512,12 @@ void uninitialized_merge_with_right_placed return; } else if (comp(*r_first, *first)) { - ::new(&*dest_first) value_type(::boost::move(*r_first)); + ::new((iterator_to_raw_pointer)(dest_first)) value_type(::boost::move(*r_first)); d.incr(); ++r_first; } else { - ::new(&*dest_first) value_type(::boost::move(*first)); + ::new((iterator_to_raw_pointer)(dest_first)) value_type(::boost::move(*first)); d.incr(); ++first; } diff --git a/boost/move/algo/detail/merge_sort.hpp b/boost/move/algo/detail/merge_sort.hpp index 892639b05f..62d185acb6 100644 --- a/boost/move/algo/detail/merge_sort.hpp +++ b/boost/move/algo/detail/merge_sort.hpp @@ -79,9 +79,9 @@ void merge_sort_copy( RandIt first, RandIt last } } -template<class RandIt, class Compare> +template<class RandIt, class RandItRaw, class Compare> void merge_sort_uninitialized_copy( RandIt first, RandIt last - , typename iterator_traits<RandIt>::value_type* uninitialized + , RandItRaw uninitialized , Compare comp) { typedef typename iterator_traits<RandIt>::size_type size_type; @@ -94,7 +94,7 @@ void merge_sort_uninitialized_copy( RandIt first, RandIt last else{ size_type const half = count/2; merge_sort_uninitialized_copy(first + half, last, uninitialized + half, comp); - destruct_n<value_type> d(uninitialized+half); + destruct_n<value_type, RandItRaw> d(uninitialized+half); d.incr(count-half); merge_sort_copy(first, first + half, first + half, comp); uninitialized_merge_with_right_placed @@ -105,9 +105,9 @@ void merge_sort_uninitialized_copy( RandIt first, RandIt last } } -template<class RandIt, class Compare> +template<class RandIt, class RandItRaw, class Compare> void merge_sort( RandIt first, RandIt last, Compare comp - , typename iterator_traits<RandIt>::value_type* uninitialized) + , RandItRaw uninitialized) { typedef typename iterator_traits<RandIt>::size_type size_type; typedef typename iterator_traits<RandIt>::value_type value_type; @@ -123,7 +123,7 @@ void merge_sort( RandIt first, RandIt last, Compare comp RandIt const rest_it = first + rest; merge_sort_uninitialized_copy(half_it, last, uninitialized, comp); - destruct_n<value_type> d(uninitialized); + destruct_n<value_type, RandItRaw> d(uninitialized); d.incr(rest); merge_sort_copy(first, half_it, rest_it, comp); merge_with_right_placed diff --git a/boost/move/algo/move.hpp b/boost/move/algo/move.hpp index d35f04a399..2390877a43 100644 --- a/boost/move/algo/move.hpp +++ b/boost/move/algo/move.hpp @@ -26,6 +26,7 @@ #include <boost/move/utility_core.hpp> #include <boost/move/detail/iterator_traits.hpp> +#include <boost/move/detail/iterator_to_raw_pointer.hpp> #include <boost/detail/no_exceptions_support.hpp> namespace boost { @@ -126,7 +127,7 @@ F uninitialized_move(I f, I l, F r } BOOST_CATCH(...){ for (; back != r; ++back){ - back->~input_value_type(); + boost::movelib::iterator_to_raw_pointer(back)->~input_value_type(); } BOOST_RETHROW; } diff --git a/boost/move/algo/predicate.hpp b/boost/move/algo/predicate.hpp new file mode 100644 index 0000000000..0287d66318 --- /dev/null +++ b/boost/move/algo/predicate.hpp @@ -0,0 +1,86 @@ +////////////////////////////////////////////////////////////////////////////// +// +// (C) Copyright Ion Gaztanaga 2015-2016. +// 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/move for documentation. +// +////////////////////////////////////////////////////////////////////////////// +#ifndef BOOST_MOVE_ALGO_PREDICATE_HPP +#define BOOST_MOVE_ALGO_PREDICATE_HPP + +#include <boost/move/algo/move.hpp> +#include <boost/move/adl_move_swap.hpp> +#include <boost/move/algo/detail/basic_op.hpp> +#include <boost/move/detail/iterator_traits.hpp> +#include <boost/move/detail/destruct_n.hpp> +#include <boost/assert.hpp> + +namespace boost { +namespace movelib { + +template<class Comp> +struct antistable +{ + explicit antistable(Comp &comp) + : m_comp(comp) + {} + + template<class U, class V> + bool operator()(const U &u, const V & v) + { return !m_comp(v, u); } + + private: + antistable & operator=(const antistable &); + Comp &m_comp; +}; + +template <class Comp> +class negate +{ + public: + negate() + {} + + explicit negate(Comp comp) + : m_comp(comp) + {} + + template <class T1, class T2> + bool operator()(const T1& l, const T2& r) + { + return !m_comp(l, r); + } + + private: + Comp m_comp; +}; + + +template <class Comp> +class inverse +{ + public: + inverse() + {} + + explicit inverse(Comp comp) + : m_comp(comp) + {} + + template <class T1, class T2> + bool operator()(const T1& l, const T2& r) + { + return m_comp(r, l); + } + + private: + Comp m_comp; +}; + +} //namespace movelib { +} //namespace boost { + +#endif //#define BOOST_MOVE_ALGO_PREDICATE_HPP diff --git a/boost/move/algo/unique.hpp b/boost/move/algo/unique.hpp new file mode 100644 index 0000000000..8022a654e2 --- /dev/null +++ b/boost/move/algo/unique.hpp @@ -0,0 +1,55 @@ +////////////////////////////////////////////////////////////////////////////// +// +// (C) Copyright Ion Gaztanaga 2017-2017. +// 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/move for documentation. +// +////////////////////////////////////////////////////////////////////////////// + +#ifndef BOOST_MOVE_ALGO_UNIQUE_HPP +#define BOOST_MOVE_ALGO_UNIQUE_HPP + +#include <boost/move/detail/config_begin.hpp> +#include <boost/move/utility_core.hpp> + +namespace boost { +namespace movelib { + +//! <b>Requires</b>: The comparison function shall be an equivalence relation. The type of *first shall satisfy +//! the MoveAssignable requirements +//! +//! <b>Effects</b>: For a nonempty range, eliminates all but the first element from every consecutive group +//! of equivalent elements referred to by the iterator i in the range [first + 1, last) for which the +//! following conditions hold: pred(*(i - 1), *i) != false. +//! +//! <b>Returns</b>: The end of the resulting range. +//! +//! <b>Complexity</b>: For nonempty ranges, exactly (last - first) - 1 applications of the corresponding predicate. +template<class ForwardIterator, class BinaryPredicate> +ForwardIterator unique(ForwardIterator first, ForwardIterator last, BinaryPredicate pred) +{ + if (first != last) { + ForwardIterator next(first); + ++next; + for (; next != last; ++next, ++first) { + if (pred(*first, *next)) { //Find first equal element + while (++next != last) + if (!pred(*first, *next)) + *++first = ::boost::move(*next); + break; + } + } + ++first; + } + return first; +} + +} //namespace movelib { +} //namespace boost { + +#include <boost/move/detail/config_end.hpp> + +#endif //#define BOOST_MOVE_ALGO_UNIQUE_HPP diff --git a/boost/move/detail/destruct_n.hpp b/boost/move/detail/destruct_n.hpp index 06f1f589ed..9f60fc2773 100644 --- a/boost/move/detail/destruct_n.hpp +++ b/boost/move/detail/destruct_n.hpp @@ -27,11 +27,11 @@ namespace boost { namespace movelib{ -template<class T> +template<class T, class RandItUninit> class destruct_n { public: - explicit destruct_n(T *raw) + explicit destruct_n(RandItUninit raw) : m_ptr(raw), m_size() {} @@ -48,7 +48,6 @@ class destruct_n void release() { m_size = 0u; - m_ptr = 0; } ~destruct_n() @@ -58,7 +57,7 @@ class destruct_n } } private: - T *m_ptr; + RandItUninit m_ptr; std::size_t m_size; }; diff --git a/boost/move/detail/fwd_macros.hpp b/boost/move/detail/fwd_macros.hpp index 7132436783..a5df5f1be7 100644 --- a/boost/move/detail/fwd_macros.hpp +++ b/boost/move/detail/fwd_macros.hpp @@ -458,6 +458,31 @@ namespace move_detail { #define BOOST_MOVE_CLASSDFLTQ8 BOOST_MOVE_CLASSDFLTQ7, class Q7 = void #define BOOST_MOVE_CLASSDFLTQ9 BOOST_MOVE_CLASSDFLTQ8, class Q8 = void +//BOOST_MOVE_LAST_TARGN +#define BOOST_MOVE_LAST_TARG0 void +#define BOOST_MOVE_LAST_TARG1 P0 +#define BOOST_MOVE_LAST_TARG2 P1 +#define BOOST_MOVE_LAST_TARG3 P2 +#define BOOST_MOVE_LAST_TARG4 P3 +#define BOOST_MOVE_LAST_TARG5 P4 +#define BOOST_MOVE_LAST_TARG6 P5 +#define BOOST_MOVE_LAST_TARG7 P6 +#define BOOST_MOVE_LAST_TARG8 P7 +#define BOOST_MOVE_LAST_TARG9 P8 + +//BOOST_MOVE_LAST_TARGQN +#define BOOST_MOVE_LAST_TARGQ0 void +#define BOOST_MOVE_LAST_TARGQ1 Q0 +#define BOOST_MOVE_LAST_TARGQ2 Q1 +#define BOOST_MOVE_LAST_TARGQ3 Q2 +#define BOOST_MOVE_LAST_TARGQ4 Q3 +#define BOOST_MOVE_LAST_TARGQ5 Q4 +#define BOOST_MOVE_LAST_TARGQ6 Q5 +#define BOOST_MOVE_LAST_TARGQ7 Q6 +#define BOOST_MOVE_LAST_TARGQ8 Q7 +#define BOOST_MOVE_LAST_TARGQ9 Q8 + + //BOOST_MOVE_TARGN #define BOOST_MOVE_TARG0 #define BOOST_MOVE_TARG1 P0 diff --git a/boost/move/detail/iterator_to_raw_pointer.hpp b/boost/move/detail/iterator_to_raw_pointer.hpp new file mode 100644 index 0000000000..97ee3a6595 --- /dev/null +++ b/boost/move/detail/iterator_to_raw_pointer.hpp @@ -0,0 +1,59 @@ +////////////////////////////////////////////////////////////////////////////// +// +// (C) Copyright Ion Gaztanaga 2014-2015. 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_MOVE_DETAIL_ITERATOR_TO_RAW_POINTER_HPP +#define BOOST_MOVE_DETAIL_ITERATOR_TO_RAW_POINTER_HPP + +#ifndef BOOST_CONFIG_HPP +# include <boost/config.hpp> +#endif + +#if defined(BOOST_HAS_PRAGMA_ONCE) +# pragma once +#endif + +#include <boost/move/detail/iterator_traits.hpp> +#include <boost/move/detail/to_raw_pointer.hpp> +#include <boost/move/detail/pointer_element.hpp> + +namespace boost { +namespace movelib { +namespace detail { + +template <class T> +inline T* iterator_to_pointer(T* i) +{ return i; } + +template <class Iterator> +inline typename boost::movelib::iterator_traits<Iterator>::pointer + iterator_to_pointer(const Iterator &i) +{ return i.operator->(); } + +template <class Iterator> +struct iterator_to_element_ptr +{ + typedef typename boost::movelib::iterator_traits<Iterator>::pointer pointer; + typedef typename boost::movelib::pointer_element<pointer>::type element_type; + typedef element_type* type; +}; + +} //namespace detail { + +template <class Iterator> +inline typename boost::movelib::detail::iterator_to_element_ptr<Iterator>::type + iterator_to_raw_pointer(const Iterator &i) +{ + return ::boost::movelib::to_raw_pointer + ( ::boost::movelib::detail::iterator_to_pointer(i) ); +} + +} //namespace movelib { +} //namespace boost { + +#endif //#ifndef BOOST_MOVE_DETAIL_ITERATOR_TO_RAW_POINTER_HPP diff --git a/boost/move/detail/pointer_element.hpp b/boost/move/detail/pointer_element.hpp new file mode 100644 index 0000000000..ecdd6080ce --- /dev/null +++ b/boost/move/detail/pointer_element.hpp @@ -0,0 +1,168 @@ +////////////////////////////////////////////////////////////////////////////// +// +// (C) Copyright Ion Gaztanaga 2014-2017. 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/move for documentation. +// +////////////////////////////////////////////////////////////////////////////// + +#ifndef BOOST_MOVE_DETAIL_POINTER_ELEMENT_HPP +#define BOOST_MOVE_DETAIL_POINTER_ELEMENT_HPP + +#ifndef BOOST_CONFIG_HPP +# include <boost/config.hpp> +#endif + +#if defined(BOOST_HAS_PRAGMA_ONCE) +# pragma once +#endif + +#ifndef BOOST_MOVE_DETAIL_WORKAROUND_HPP +#include <boost/move/detail/workaround.hpp> +#endif //BOOST_MOVE_DETAIL_WORKAROUND_HPP + +namespace boost { +namespace movelib { +namespace detail{ + +////////////////////// +//struct first_param +////////////////////// + +template <typename T> struct first_param +{ typedef void type; }; + +#if !defined(BOOST_NO_CXX11_VARIADIC_TEMPLATES) + + template <template <typename, typename...> class TemplateClass, typename T, typename... Args> + struct first_param< TemplateClass<T, Args...> > + { + typedef T type; + }; + +#else //C++03 compilers + + template < template //0arg + <class + > class TemplateClass, class T + > + struct first_param + < TemplateClass<T> > + { typedef T type; }; + + template < template //1arg + <class,class + > class TemplateClass, class T + , class P0> + struct first_param + < TemplateClass<T, P0> > + { typedef T type; }; + + template < template //2arg + <class,class,class + > class TemplateClass, class T + , class P0, class P1> + struct first_param + < TemplateClass<T, P0, P1> > + { typedef T type; }; + + template < template //3arg + <class,class,class,class + > class TemplateClass, class T + , class P0, class P1, class P2> + struct first_param + < TemplateClass<T, P0, P1, P2> > + { typedef T type; }; + + template < template //4arg + <class,class,class,class,class + > class TemplateClass, class T + , class P0, class P1, class P2, class P3> + struct first_param + < TemplateClass<T, P0, P1, P2, P3> > + { typedef T type; }; + + template < template //5arg + <class,class,class,class,class,class + > class TemplateClass, class T + , class P0, class P1, class P2, class P3, class P4> + struct first_param + < TemplateClass<T, P0, P1, P2, P3, P4> > + { typedef T type; }; + + template < template //6arg + <class,class,class,class,class,class,class + > class TemplateClass, class T + , class P0, class P1, class P2, class P3, class P4, class P5> + struct first_param + < TemplateClass<T, P0, P1, P2, P3, P4, P5> > + { typedef T type; }; + + template < template //7arg + <class,class,class,class,class,class,class,class + > class TemplateClass, class T + , class P0, class P1, class P2, class P3, class P4, class P5, class P6> + struct first_param + < TemplateClass<T, P0, P1, P2, P3, P4, P5, P6> > + { typedef T type; }; + + template < template //8arg + <class,class,class,class,class,class,class,class,class + > class TemplateClass, class T + , class P0, class P1, class P2, class P3, class P4, class P5, class P6, class P7> + struct first_param + < TemplateClass<T, P0, P1, P2, P3, P4, P5, P6, P7> > + { typedef T type; }; + + template < template //9arg + <class,class,class,class,class,class,class,class,class,class + > class TemplateClass, class T + , class P0, class P1, class P2, class P3, class P4, class P5, class P6, class P7, class P8> + struct first_param + < TemplateClass<T, P0, P1, P2, P3, P4, P5, P6, P7, P8> > + { typedef T type; }; + +#endif //!defined(BOOST_NO_CXX11_VARIADIC_TEMPLATES) + +template <typename T> +struct has_internal_pointer_element +{ + template <typename X> + static char test(int, typename X::element_type*); + + template <typename X> + static int test(...); + + static const bool value = (1 == sizeof(test<T>(0, 0))); +}; + +template<class Ptr, bool = has_internal_pointer_element<Ptr>::value> +struct pointer_element_impl +{ + typedef typename Ptr::element_type type; +}; + +template<class Ptr> +struct pointer_element_impl<Ptr, false> +{ + typedef typename boost::movelib::detail::first_param<Ptr>::type type; +}; + +} //namespace detail{ + +template <typename Ptr> +struct pointer_element +{ + typedef typename ::boost::movelib::detail::pointer_element_impl<Ptr>::type type; +}; + +template <typename T> +struct pointer_element<T*> +{ typedef T type; }; + +} //namespace movelib { +} //namespace boost { + +#endif // defined(BOOST_MOVE_DETAIL_POINTER_ELEMENT_HPP) diff --git a/boost/move/detail/to_raw_pointer.hpp b/boost/move/detail/to_raw_pointer.hpp new file mode 100644 index 0000000000..7e89beb4db --- /dev/null +++ b/boost/move/detail/to_raw_pointer.hpp @@ -0,0 +1,45 @@ +///////////////////////////////////////////////////////////////////////////// +// +// (C) Copyright Ion Gaztanaga 2017-2017 +// +// 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/move for documentation. +// +///////////////////////////////////////////////////////////////////////////// + +#ifndef BOOST_MOVE_DETAIL_TO_RAW_POINTER_HPP +#define BOOST_MOVE_DETAIL_TO_RAW_POINTER_HPP + +#ifndef BOOST_CONFIG_HPP +# include <boost/config.hpp> +#endif + +#if defined(BOOST_HAS_PRAGMA_ONCE) +# pragma once +#endif + +#include <boost/move/detail/config_begin.hpp> +#include <boost/move/detail/workaround.hpp> +#include <boost/move/detail/pointer_element.hpp> + +namespace boost { +namespace movelib { + +template <class T> +BOOST_MOVE_FORCEINLINE T* to_raw_pointer(T* p) +{ return p; } + +template <class Pointer> +BOOST_MOVE_FORCEINLINE typename boost::movelib::pointer_element<Pointer>::type* +to_raw_pointer(const Pointer &p) +{ return ::boost::movelib::to_raw_pointer(p.operator->()); } + +} //namespace movelib +} //namespace boost + +#include <boost/move/detail/config_end.hpp> + +#endif //BOOST_MOVE_DETAIL_TO_RAW_POINTER_HPP diff --git a/boost/move/detail/unique_ptr_meta_utils.hpp b/boost/move/detail/unique_ptr_meta_utils.hpp index ac270a8fc0..e11124d898 100644 --- a/boost/move/detail/unique_ptr_meta_utils.hpp +++ b/boost/move/detail/unique_ptr_meta_utils.hpp @@ -446,7 +446,7 @@ class is_convertible #define BOOST_MOVE_TT_DECL #endif -#if defined(_MSC_EXTENSIONS) && !defined(__BORLAND__) && !defined(_WIN64) && !defined(_M_ARM) && !defined(UNDER_CE) +#if defined(_MSC_EXTENSIONS) && !defined(__BORLAND__) && !defined(_WIN64) && !defined(_M_ARM) && !defined(_M_ARM64) && !defined(UNDER_CE) #define BOOST_MOVE_TT_TEST_MSC_FUNC_SIGS #endif |