diff options
Diffstat (limited to 'boost/move/algo/detail/merge.hpp')
| -rw-r--r-- | boost/move/algo/detail/merge.hpp | 447 |
1 files changed, 437 insertions, 10 deletions
diff --git a/boost/move/algo/detail/merge.hpp b/boost/move/algo/detail/merge.hpp index 860773579c..58df061637 100644 --- a/boost/move/algo/detail/merge.hpp +++ b/boost/move/algo/detail/merge.hpp @@ -19,10 +19,263 @@ #include <boost/move/algo/predicate.hpp> #include <boost/move/detail/iterator_to_raw_pointer.hpp> #include <boost/assert.hpp> +#include <cstddef> namespace boost { namespace movelib { +template<class T, class RandRawIt = T*, class SizeType = typename iterator_traits<RandRawIt>::size_type> +class adaptive_xbuf +{ + adaptive_xbuf(const adaptive_xbuf &); + adaptive_xbuf & operator=(const adaptive_xbuf &); + + #if !defined(UINTPTR_MAX) + typedef std::size_t uintptr_t; + #endif + + public: + typedef RandRawIt iterator; + typedef SizeType size_type; + + adaptive_xbuf() + : m_ptr(), m_size(0), m_capacity(0) + {} + + adaptive_xbuf(RandRawIt raw_memory, size_type capacity) + : m_ptr(raw_memory), m_size(0), m_capacity(capacity) + {} + + template<class RandIt> + void move_assign(RandIt first, size_type n) + { + if(n <= m_size){ + boost::move(first, first+n, m_ptr); + size_type size = m_size; + while(size-- != n){ + m_ptr[size].~T(); + } + m_size = n; + } + else{ + RandRawIt result = boost::move(first, first+m_size, m_ptr); + boost::uninitialized_move(first+m_size, first+n, result); + m_size = n; + } + } + + template<class RandIt> + void push_back(RandIt first, size_type n) + { + BOOST_ASSERT(m_capacity - m_size >= n); + boost::uninitialized_move(first, first+n, m_ptr+m_size); + m_size += n; + } + + template<class RandIt> + iterator add(RandIt it) + { + BOOST_ASSERT(m_size < m_capacity); + RandRawIt p_ret = m_ptr + m_size; + ::new(&*p_ret) T(::boost::move(*it)); + ++m_size; + return p_ret; + } + + template<class RandIt> + void insert(iterator pos, RandIt it) + { + if(pos == (m_ptr + m_size)){ + this->add(it); + } + else{ + this->add(m_ptr+m_size-1); + //m_size updated + boost::move_backward(pos, m_ptr+m_size-2, m_ptr+m_size-1); + *pos = boost::move(*it); + } + } + + void set_size(size_type size) + { + m_size = size; + } + + void shrink_to_fit(size_type const size) + { + if(m_size > size){ + for(size_type szt_i = size; szt_i != m_size; ++szt_i){ + m_ptr[szt_i].~T(); + } + m_size = size; + } + } + + void initialize_until(size_type const size, T &t) + { + BOOST_ASSERT(m_size < m_capacity); + if(m_size < size){ + BOOST_TRY + { + ::new((void*)&m_ptr[m_size]) T(::boost::move(t)); + ++m_size; + for(; m_size != size; ++m_size){ + ::new((void*)&m_ptr[m_size]) T(::boost::move(m_ptr[m_size-1])); + } + t = ::boost::move(m_ptr[m_size-1]); + } + BOOST_CATCH(...) + { + while(m_size) + { + --m_size; + m_ptr[m_size].~T(); + } + } + BOOST_CATCH_END + } + } + + 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(size_type size, size_type trail_count) const + { + 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; + } + + template<class U> + U *aligned_trailing() const + { + return this->aligned_trailing<U>(this->size()); + } + + template<class U> + U *aligned_trailing(size_type pos) const + { + uintptr_t u_addr = uintptr_t(&*(this->data()+pos)); + u_addr = ((u_addr + sizeof(U)-1)/sizeof(U))*sizeof(U); + return (U*)u_addr; + } + + ~adaptive_xbuf() + { + this->clear(); + } + + size_type capacity() const + { return m_capacity; } + + iterator data() const + { return m_ptr; } + + iterator begin() const + { return m_ptr; } + + iterator end() const + { return m_ptr+m_size; } + + size_type size() const + { return m_size; } + + bool empty() const + { return !m_size; } + + void clear() + { + this->shrink_to_fit(0u); + } + + private: + RandRawIt m_ptr; + size_type m_size; + size_type m_capacity; +}; + +template<class Iterator, class SizeType, class Op> +class range_xbuf +{ + range_xbuf(const range_xbuf &); + range_xbuf & operator=(const range_xbuf &); + + public: + typedef SizeType size_type; + typedef Iterator iterator; + + range_xbuf(Iterator first, Iterator last) + : m_first(first), m_last(first), m_cap(last) + {} + + template<class RandIt> + void move_assign(RandIt first, size_type n) + { + BOOST_ASSERT(size_type(n) <= size_type(m_cap-m_first)); + m_last = Op()(forward_t(), first, first+n, m_first); + } + + ~range_xbuf() + {} + + size_type capacity() const + { return m_cap-m_first; } + + Iterator data() const + { return m_first; } + + Iterator end() const + { return m_last; } + + size_type size() const + { return m_last-m_first; } + + bool empty() const + { return m_first == m_last; } + + void clear() + { + m_last = m_first; + } + + template<class RandIt> + iterator add(RandIt it) + { + Iterator pos(m_last); + *pos = boost::move(*it); + ++m_last; + return pos; + } + + void set_size(size_type size) + { + m_last = m_first; + m_last += size; + } + + private: + Iterator const m_first; + Iterator m_last; + Iterator const m_cap; +}; + + + // @cond /* @@ -256,6 +509,45 @@ void swap_merge_right op_merge_right(first1, last1, last2, buf_last, comp, swap_op()); } +/////////////////////////////////////////////////////////////////////////////// +// +// BUFFERED MERGE +// +/////////////////////////////////////////////////////////////////////////////// +template<class RandIt, class Compare, class Op, class Buf> +void op_buffered_merge + ( RandIt first, RandIt const middle, RandIt last + , Compare comp, Op op + , Buf &xbuf) +{ + if(first != middle && middle != last && comp(*middle, middle[-1])){ + typedef typename iterator_traits<RandIt>::size_type size_type; + size_type const len1 = size_type(middle-first); + size_type const len2 = size_type(last-middle); + if(len1 <= len2){ + 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 = 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); + } + } +} + +template<class RandIt, class Compare, class XBuf> +void buffered_merge + ( RandIt first, RandIt const middle, RandIt last + , Compare comp + , XBuf &xbuf) +{ + op_buffered_merge(first, middle, last, comp, move_op(), xbuf); +} + //Complexity: min(len1,len2)^2 + max(len1,len2) template<class RandIt, class Compare> void merge_bufferless_ON2(RandIt first, RandIt middle, RandIt last, Compare comp) @@ -289,11 +581,14 @@ void merge_bufferless_ON2(RandIt first, RandIt middle, RandIt last, Compare comp } } -static const std::size_t MergeBufferlessONLogNRotationThreshold = 32; +static const std::size_t MergeBufferlessONLogNRotationThreshold = 16u; -template <class RandIt, class Distance, class Compare> +template <class RandIt, class Compare> void merge_bufferless_ONlogN_recursive - (RandIt first, RandIt middle, RandIt last, Distance len1, Distance len2, Compare comp) + ( RandIt first, RandIt middle, RandIt last + , typename iterator_traits<RandIt>::size_type len1 + , typename iterator_traits<RandIt>::size_type len2 + , Compare comp) { typedef typename iterator_traits<RandIt>::size_type size_type; @@ -317,8 +612,8 @@ void merge_bufferless_ONlogN_recursive RandIt first_cut = first; RandIt second_cut = middle; - Distance len11 = 0; - Distance len22 = 0; + size_type len11 = 0; + size_type len22 = 0; if (len1 > len2) { len11 = len1 / 2; first_cut += len11; @@ -334,16 +629,16 @@ void merge_bufferless_ONlogN_recursive RandIt new_middle = rotate_gcd(first_cut, middle, second_cut); //Avoid one recursive call doing a manual tail call elimination on the biggest range - const Distance len_internal = len11+len22; + const size_type len_internal = len11+len22; if( len_internal < (len1 + len2 - len_internal) ) { - merge_bufferless_ONlogN_recursive(first, first_cut, new_middle, len11, len22, comp); + merge_bufferless_ONlogN_recursive(first, first_cut, new_middle, len11, len22, comp); first = new_middle; middle = second_cut; len1 -= len11; len2 -= len22; } else { - merge_bufferless_ONlogN_recursive(new_middle, second_cut, last, len1 - len11, len2 - len22, comp); + merge_bufferless_ONlogN_recursive(new_middle, second_cut, last, len1 - len11, len2 - len22, comp); middle = first_cut; last = new_middle; len1 = len11; @@ -352,12 +647,14 @@ void merge_bufferless_ONlogN_recursive } } + //Complexity: NlogN template<class RandIt, class Compare> void merge_bufferless_ONlogN(RandIt first, RandIt middle, RandIt last, Compare comp) { + typedef typename iterator_traits<RandIt>::size_type size_type; merge_bufferless_ONlogN_recursive - (first, middle, last, middle - first, last - middle, comp); + (first, middle, last, size_type(middle - first), size_type(last - middle), comp); } template<class RandIt, class Compare> @@ -441,7 +738,7 @@ void op_merge_with_left_placed // @endcond -// [irst, last) are already in the right part of the destination range. +// [first, last) are already in the right part of the destination range. template <class Compare, class BidirIterator, class BidirOutIterator> void merge_with_left_placed ( BidirOutIterator const first, BidirOutIterator last, BidirOutIterator dest_last @@ -547,6 +844,136 @@ void uninitialized_merge_with_left_placed } */ + +/// This is a helper function for the merge routines. +template<typename BidirectionalIterator1, typename BidirectionalIterator2> + BidirectionalIterator1 + rotate_adaptive(BidirectionalIterator1 first, + BidirectionalIterator1 middle, + BidirectionalIterator1 last, + typename iterator_traits<BidirectionalIterator1>::size_type len1, + typename iterator_traits<BidirectionalIterator1>::size_type len2, + BidirectionalIterator2 buffer, + typename iterator_traits<BidirectionalIterator1>::size_type buffer_size) +{ + if (len1 > len2 && len2 <= buffer_size) + { + if(len2) //Protect against self-move ranges + { + BidirectionalIterator2 buffer_end = boost::move(middle, last, buffer); + boost::move_backward(first, middle, last); + return boost::move(buffer, buffer_end, first); + } + else + return first; + } + else if (len1 <= buffer_size) + { + if(len1) //Protect against self-move ranges + { + BidirectionalIterator2 buffer_end = boost::move(first, middle, buffer); + BidirectionalIterator1 ret = boost::move(middle, last, first); + boost::move(buffer, buffer_end, ret); + return ret; + } + else + return last; + } + else + return rotate_gcd(first, middle, last); +} + +template<typename BidirectionalIterator, + typename Pointer, typename Compare> + void merge_adaptive_ONlogN_recursive + (BidirectionalIterator first, + BidirectionalIterator middle, + BidirectionalIterator last, + typename iterator_traits<BidirectionalIterator>::size_type len1, + typename iterator_traits<BidirectionalIterator>::size_type len2, + Pointer buffer, + typename iterator_traits<BidirectionalIterator>::size_type buffer_size, + Compare comp) +{ + typedef typename iterator_traits<BidirectionalIterator>::size_type size_type; + //trivial cases + if (!len2 || !len1) { + return; + } + else if (len1 <= buffer_size || len2 <= buffer_size) + { + range_xbuf<Pointer, size_type, move_op> rxbuf(buffer, buffer + buffer_size); + buffered_merge(first, middle, last, comp, rxbuf); + } + else if (size_type(len1 + len2) == 2u) { + if (comp(*middle, *first)) + adl_move_swap(*first, *middle); + return; + } + else if (size_type(len1 + len2) < MergeBufferlessONLogNRotationThreshold) { + merge_bufferless_ON2(first, middle, last, comp); + return; + } + BidirectionalIterator first_cut = first; + BidirectionalIterator second_cut = middle; + size_type len11 = 0; + size_type len22 = 0; + if (len1 > len2) //(len1 < len2) + { + len11 = len1 / 2; + first_cut += len11; + second_cut = boost::movelib::lower_bound(middle, last, *first_cut, comp); + len22 = second_cut - middle; + } + else + { + len22 = len2 / 2; + second_cut += len22; + first_cut = boost::movelib::upper_bound(first, middle, *second_cut, comp); + len11 = first_cut - first; + } + + BidirectionalIterator new_middle + = rotate_adaptive(first_cut, middle, second_cut, + size_type(len1 - len11), len22, buffer, + buffer_size); + merge_adaptive_ONlogN_recursive(first, first_cut, new_middle, len11, + len22, buffer, buffer_size, comp); + merge_adaptive_ONlogN_recursive(new_middle, second_cut, last, + len1 - len11, len2 - len22, buffer, buffer_size, comp); +} + + +template<typename BidirectionalIterator, typename Compare, typename RandRawIt> +void merge_adaptive_ONlogN(BidirectionalIterator first, + BidirectionalIterator middle, + BidirectionalIterator last, + Compare comp, + RandRawIt uninitialized, + typename iterator_traits<BidirectionalIterator>::size_type uninitialized_len) +{ + typedef typename iterator_traits<BidirectionalIterator>::value_type value_type; + typedef typename iterator_traits<BidirectionalIterator>::size_type size_type; + + if (first == middle || middle == last) + return; + + if(uninitialized_len) + { + const size_type len1 = size_type(middle - first); + const size_type len2 = size_type(last - middle); + + ::boost::movelib::adaptive_xbuf<value_type, RandRawIt> xbuf(uninitialized, uninitialized_len); + xbuf.initialize_until(uninitialized_len, *first); + merge_adaptive_ONlogN_recursive(first, middle, last, len1, len2, xbuf.begin(), uninitialized_len, comp); + } + else + { + merge_bufferless(first, middle, last, comp); + } +} + + } //namespace movelib { } //namespace boost { |