diff options
Diffstat (limited to 'boost/move')
23 files changed, 3815 insertions, 307 deletions
diff --git a/boost/move/adl_move_swap.hpp b/boost/move/adl_move_swap.hpp index 2a010cda57..930320108d 100644 --- a/boost/move/adl_move_swap.hpp +++ b/boost/move/adl_move_swap.hpp @@ -22,9 +22,8 @@ //Based on Boost.Core's swap. //Many thanks to Steven Watanabe, Joseph Gauterin and Niels Dekker. - -#include <boost/config.hpp> #include <cstddef> //for std::size_t +#include <boost/move/detail/workaround.hpp> //forceinline //Try to avoid including <algorithm>, as it's quite big #if defined(_MSC_VER) && defined(BOOST_DINKUMWARE_STDLIB) @@ -156,7 +155,7 @@ struct and_op_not {}; template<class T> -void swap_proxy(T& x, T& y, typename boost::move_detail::enable_if_c<!boost::move_detail::has_move_emulation_enabled_impl<T>::value>::type* = 0) +BOOST_MOVE_FORCEINLINE void swap_proxy(T& x, T& y, typename boost::move_detail::enable_if_c<!boost::move_detail::has_move_emulation_enabled_impl<T>::value>::type* = 0) { //use std::swap if argument dependent lookup fails //Use using directive ("using namespace xxx;") instead as some older compilers @@ -166,14 +165,14 @@ void swap_proxy(T& x, T& y, typename boost::move_detail::enable_if_c<!boost::mov } template<class T> -void swap_proxy(T& x, T& y +BOOST_MOVE_FORCEINLINE void swap_proxy(T& x, T& y , typename boost::move_detail::enable_if< and_op_not_impl<boost::move_detail::has_move_emulation_enabled_impl<T> , boost_move_member_swap::has_member_swap<T> > >::type* = 0) { T t(::boost::move(x)); x = ::boost::move(y); y = ::boost::move(t); } template<class T> -void swap_proxy(T& x, T& y +BOOST_MOVE_FORCEINLINE void swap_proxy(T& x, T& y , typename boost::move_detail::enable_if< and_op_impl< boost::move_detail::has_move_emulation_enabled_impl<T> , boost_move_member_swap::has_member_swap<T> > >::type* = 0) @@ -186,7 +185,7 @@ void swap_proxy(T& x, T& y namespace boost_move_adl_swap{ template<class T> -void swap_proxy(T& x, T& y) +BOOST_MOVE_FORCEINLINE void swap_proxy(T& x, T& y) { using std::swap; swap(x, y); @@ -223,11 +222,45 @@ namespace boost{ //! - Otherwise a move-based swap is called, equivalent to: //! <code>T t(::boost::move(x)); x = ::boost::move(y); y = ::boost::move(t);</code>. template<class T> -void adl_move_swap(T& x, T& y) +BOOST_MOVE_FORCEINLINE void adl_move_swap(T& x, T& y) { ::boost_move_adl_swap::swap_proxy(x, y); } +//! Exchanges elements between range [first1, last1) and another range starting at first2 +//! using boost::adl_move_swap. +//! +//! Parameters: +//! first1, last1 - the first range of elements to swap +//! first2 - beginning of the second range of elements to swap +//! +//! Type requirements: +//! - ForwardIt1, ForwardIt2 must meet the requirements of ForwardIterator. +//! - The types of dereferenced ForwardIt1 and ForwardIt2 must meet the +//! requirements of Swappable +//! +//! Return value: Iterator to the element past the last element exchanged in the range +//! beginning with first2. +template<class ForwardIt1, class ForwardIt2> +ForwardIt2 adl_move_swap_ranges(ForwardIt1 first1, ForwardIt1 last1, ForwardIt2 first2) +{ + while (first1 != last1) { + ::boost::adl_move_swap(*first1, *first2); + ++first1; + ++first2; + } + return first2; +} + +template<class BidirIt1, class BidirIt2> +BidirIt2 adl_move_swap_ranges_backward(BidirIt1 first1, BidirIt1 last1, BidirIt2 last2) +{ + while (first1 != last1) { + ::boost::adl_move_swap(*(--last1), *(--last2)); + } + return last2; +} + } //namespace boost{ #endif //#ifndef BOOST_MOVE_ADL_MOVE_SWAP_HPP diff --git a/boost/move/algo/adaptive_merge.hpp b/boost/move/algo/adaptive_merge.hpp new file mode 100644 index 0000000000..ef20651bbf --- /dev/null +++ b/boost/move/algo/adaptive_merge.hpp @@ -0,0 +1,67 @@ +////////////////////////////////////////////////////////////////////////////// +// +// (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_ADAPTIVE_MERGE_HPP +#define BOOST_MOVE_ADAPTIVE_MERGE_HPP + +#include <boost/move/detail/config_begin.hpp> +#include <boost/move/algo/detail/adaptive_sort_merge.hpp> + +namespace boost { +namespace movelib { + +//! <b>Effects</b>: Merges two consecutive sorted ranges [first, middle) and [middle, last) +//! into one sorted range [first, last) according to the given comparison function comp. +//! The algorithm is stable (if there are equivalent elements in the original two ranges, +//! the elements from the first range (preserving their original order) precede the elements +//! from the second range (preserving their original order). +//! +//! <b>Requires</b>: +//! - RandIt must meet the requirements of ValueSwappable and RandomAccessIterator. +//! - The type of dereferenced RandIt must meet the requirements of MoveAssignable and MoveConstructible. +//! +//! <b>Parameters</b>: +//! - first: the beginning of the first sorted range. +//! - middle: the end of the first sorted range and the beginning of the second +//! - last: the end of the second sorted range +//! - comp: comparison function object which returns true if the first argument is is ordered before the second. +//! - uninitialized, uninitialized_len: raw storage starting on "uninitialized", able to hold "uninitialized_len" +//! elements of type iterator_traits<RandIt>::value_type. Maximum performance is achieved when uninitialized_len +//! is min(std::distance(first, middle), std::distance(middle, last)). +//! +//! <b>Throws</b>: If comp throws or the move constructor, move assignment or swap of the type +//! of dereferenced RandIt throws. +//! +//! <b>Complexity</b>: Always K x O(N) comparisons and move assignments/constructors/swaps. +//! Constant factor for comparisons and data movement is minimized when uninitialized_len +//! is min(std::distance(first, middle), std::distance(middle, last)). +//! Pretty good enough performance is achieved when uninitialized_len is +//! ceil(sqrt(std::distance(first, last)))*2. +//! +//! <b>Caution</b>: Experimental implementation, not production-ready. +template<class RandIt, class Compare> +void adaptive_merge( RandIt first, RandIt middle, RandIt last, Compare comp + , typename iterator_traits<RandIt>::value_type* uninitialized = 0 + , std::size_t uninitialized_len = 0) +{ + 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_merge_impl(first, size_type(middle - first), size_type(last - middle), comp, xbuf); +} + +} //namespace movelib { +} //namespace boost { + +#include <boost/move/detail/config_end.hpp> + +#endif //#define BOOST_MOVE_ADAPTIVE_MERGE_HPP diff --git a/boost/move/algo/adaptive_sort.hpp b/boost/move/algo/adaptive_sort.hpp new file mode 100644 index 0000000000..6b5586e587 --- /dev/null +++ b/boost/move/algo/adaptive_sort.hpp @@ -0,0 +1,63 @@ +////////////////////////////////////////////////////////////////////////////// +// +// (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_ADAPTIVE_SORT_HPP +#define BOOST_MOVE_ADAPTIVE_SORT_HPP + +#include <boost/move/detail/config_begin.hpp> +#include <boost/move/algo/detail/adaptive_sort_merge.hpp> + +namespace boost { +namespace movelib { + +//! <b>Effects</b>: Sorts the elements in the range [first, last) in ascending order according +//! to comparison functor "comp". The sort is stable (order of equal elements +//! is guaranteed to be preserved). Performance is improved if additional raw storage is +//! provided. +//! +//! <b>Requires</b>: +//! - RandIt must meet the requirements of ValueSwappable and RandomAccessIterator. +//! - The type of dereferenced RandIt must meet the requirements of MoveAssignable and MoveConstructible. +//! +//! <b>Parameters</b>: +//! - first, last: the range of elements to sort +//! - comp: comparison function object which returns true if the first argument is is ordered before the second. +//! - uninitialized, uninitialized_len: raw storage starting on "uninitialized", able to hold "uninitialized_len" +//! elements of type iterator_traits<RandIt>::value_type. Maximum performance is achieved when uninitialized_len +//! is ceil(std::distance(first, last)/2). +//! +//! <b>Throws</b>: If comp throws or the move constructor, move assignment or swap of the type +//! of dereferenced RandIt throws. +//! +//! <b>Complexity</b>: Always K x O(Nxlog(N)) comparisons and move assignments/constructors/swaps. +//! Comparisons are close to minimum even with no additional memory. Constant factor for data movement is minimized +//! when uninitialized_len is ceil(std::distance(first, last)/2). Pretty good enough performance is achieved when +//! ceil(sqrt(std::distance(first, last)))*2. +//! +//! <b>Caution</b>: Experimental implementation, not production-ready. +template<class RandIt, 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) +{ + 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_sort_impl(first, size_type(last - first), comp, xbuf); +} + +} //namespace movelib { +} //namespace boost { + +#include <boost/move/detail/config_end.hpp> + +#endif //#define BOOST_MOVE_ADAPTIVE_SORT_HPP diff --git a/boost/move/algo/detail/adaptive_sort_merge.hpp b/boost/move/algo/detail/adaptive_sort_merge.hpp new file mode 100644 index 0000000000..46dba187c5 --- /dev/null +++ b/boost/move/algo/detail/adaptive_sort_merge.hpp @@ -0,0 +1,2284 @@ +////////////////////////////////////////////////////////////////////////////// +// +// (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. +// +////////////////////////////////////////////////////////////////////////////// +// +// Stable sorting that works in O(N*log(N)) worst time +// and uses O(1) extra memory +// +////////////////////////////////////////////////////////////////////////////// +// +// The main idea of the adaptive_sort algorithm was developed by Andrey Astrelin +// and explained in the article from the russian collaborative blog +// Habrahabr (http://habrahabr.ru/post/205290/). The algorithm is based on +// ideas from B-C. Huang and M. A. Langston explained in their article +// "Fast Stable Merging and Sorting in Constant Extra Space (1989-1992)" +// (http://comjnl.oxfordjournals.org/content/35/6/643.full.pdf). +// +// This implementation by Ion Gaztanaga uses previous ideas with additional changes: +// +// - Use of GCD-based rotation. +// - Non power of two buffer-sizes. +// - Tries to find sqrt(len)*2 unique keys, so that the merge sort +// phase can form up to sqrt(len)*4 segments if enough keys are found. +// - The merge-sort phase can take advantage of external memory to +// save some additional combination steps. +// - Optimized comparisons when selection-sorting blocks as A and B blocks +// are already sorted. +// - The combination phase is performed alternating merge to left and merge +// to right phases minimizing swaps due to internal buffer repositioning. +// - When merging blocks special optimizations are made to avoid moving some +// elements twice. +// +// The adaptive_merge algorithm was developed by Ion Gaztanaga reusing some parts +// from the sorting algorithm and implementing a block merge algorithm +// without moving elements left or right, which is used when external memory +// is available. +////////////////////////////////////////////////////////////////////////////// +#ifndef BOOST_MOVE_ADAPTIVE_SORT_MERGE_HPP +#define BOOST_MOVE_ADAPTIVE_SORT_MERGE_HPP + +#include <boost/move/detail/config_begin.hpp> +#include <boost/move/algo/move.hpp> +#include <boost/move/algo/detail/merge.hpp> +#include <boost/move/adl_move_swap.hpp> +#include <boost/move/algo/detail/insertion_sort.hpp> +#include <boost/move/algo/detail/merge_sort.hpp> +#include <boost/move/algo/detail/merge.hpp> +#include <boost/assert.hpp> +#include <boost/cstdint.hpp> + +#ifdef BOOST_MOVE_ADAPTIVE_SORT_STATS + #define BOOST_MOVE_ADAPTIVE_SORT_PRINT(STR, L) \ + print_stats(STR, L)\ + // +#else + #define BOOST_MOVE_ADAPTIVE_SORT_PRINT(STR, L) +#endif + +namespace boost { +namespace movelib { + +namespace detail_adaptive { + +static const std::size_t AdaptiveSortInsertionSortThreshold = 16; +//static const std::size_t AdaptiveSortInsertionSortThreshold = 4; +BOOST_STATIC_ASSERT((AdaptiveSortInsertionSortThreshold&(AdaptiveSortInsertionSortThreshold-1)) == 0); + +#if defined BOOST_HAS_INTPTR_T + typedef ::boost::uintptr_t uintptr_t; +#else + typedef std::size_t uintptr_t; +#endif + +template<class T> +const T &min_value(const T &a, const T &b) +{ + return a < b ? a : b; +} + +template<class T> +const T &max_value(const T &a, const T &b) +{ + return a > b ? a : b; +} + +template<class T> +class adaptive_xbuf +{ + adaptive_xbuf(const adaptive_xbuf &); + adaptive_xbuf & operator=(const adaptive_xbuf &); + + public: + typedef T* iterator; + + adaptive_xbuf() + : m_ptr(0), m_size(0), m_capacity(0) + {} + + adaptive_xbuf(T *raw_memory, std::size_t capacity) + : m_ptr(raw_memory), m_size(0), m_capacity(capacity) + {} + + template<class RandIt> + void move_assign(RandIt first, std::size_t n) + { + if(n <= m_size){ + boost::move(first, first+n, m_ptr); + std::size_t size = m_size; + while(size-- != n){ + m_ptr[size].~T(); + } + m_size = n; + } + else{ + T *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, std::size_t 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); + T * 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(std::size_t size) + { + m_size = size; + } + + 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()); + 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(std::size_t 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(); + } + + std::size_t capacity() const + { return m_capacity; } + + iterator data() const + { return m_ptr; } + + iterator end() const + { return m_ptr+m_size; } + + std::size_t size() const + { return m_size; } + + bool empty() const + { return !m_size; } + + void clear() + { + std::size_t size = m_size; + while(size--){ + m_ptr[size].~T(); + } + m_size = 0u; + } + + private: + T *m_ptr; + std::size_t m_size; + std::size_t m_capacity; +}; + +template<class Iterator, class Op> +class range_xbuf +{ + range_xbuf(const range_xbuf &); + range_xbuf & operator=(const range_xbuf &); + + public: + typedef typename iterator_traits<Iterator>::size_type 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, std::size_t n) + { + BOOST_ASSERT(size_type(n) <= size_type(m_cap-m_first)); + m_last = Op()(forward_t(), first, first+n, m_first); + } + + ~range_xbuf() + {} + + std::size_t capacity() const + { return m_cap-m_first; } + + Iterator data() const + { return m_first; } + + Iterator end() const + { return m_last; } + + std::size_t 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(std::size_t size) + { + m_last = m_first; + m_last += size; + } + + private: + Iterator const m_first; + Iterator m_last; + Iterator const m_cap; +}; + +template<class RandIt, class Buf> +bool three_way_init( RandIt first1, RandIt last1, Buf &buf + , typename Buf::iterator &buf_first, typename Buf::iterator &buf_last, move_op) +{ + buf.move_assign(first1, last1-first1); + buf_first = buf.data(); + buf_last = buf.end(); + return true; +} + +template<class RandIt, class Buf> +bool three_way_init( RandIt first, RandIt last, Buf &buf + , typename Buf::iterator &buf_first, typename Buf::iterator &buf_last, swap_op) +{ + typedef typename iterator_traits<RandIt>::size_type size_type; + buf.clear(); + buf_first = buf.data(); + buf_last = buf_first + size_type(last-first); + return false; +} + +template<class T, class Buf> +void three_way_move(T &a, T &b, Buf &buf, move_op) +{ + buf.add(&b); + b = boost::move(a); +} + +template<class T, class Buf> +void three_way_move(T &a, T &b, Buf &buf, swap_op) +{ + T tmp(boost::move(*buf.end())); + buf.add(&b); + b = boost::move(a); + a = boost::move(tmp); +} + +/////////////////////////////////////////////////////////////////////////////// +// +// PARTIAL MERGE BUF +// +/////////////////////////////////////////////////////////////////////////////// + + +template<class Buf, class RandIt, class Compare, class Op> +RandIt op_partial_merge_with_buf_impl + ( RandIt first1, RandIt const last1, RandIt first2, RandIt last2 + , Buf &buf, typename Buf::iterator &buf_first1_in_out, typename Buf::iterator &buf_last1_in_out + , Compare comp, Op op + ) +{ + typedef typename Buf::iterator buf_iterator; + typedef typename iterator_traits<RandIt>::value_type value_type; + + BOOST_ASSERT(first1 != last1); + BOOST_ASSERT(first2 != last2); + buf_iterator buf_first1 = buf_first1_in_out; + buf_iterator buf_last1 = buf_last1_in_out; + + if(buf_first1 == buf_last1){ + //Skip any element that does not need to be moved + while(!comp(*last1, *first1)){ + ++first1; + if(first1 == last1){ + return first1; + } + } + + //If initialization is successful, move to buffer while merging + //Three way moves need less moves when op is swap_op so use it + //when merging elements from range2 to the destination occupied by range1 + if(!three_way_init(first1, last1, buf, buf_first1, buf_last1, op)){ + three_way_move(*first2, *first1, buf, op); + for(++first1, ++first2; first1 != last1; ++first1){ + value_type &v = comp(*first2, *buf_first1) ? *first2++ : *buf_first1++; + three_way_move(v, *first1, buf, op); + } + } + } + + //Now merge from buffer + if(first2 != last2) + while(1){ + if(comp(*first2, *buf_first1)) { + op(first2++, first1++); + if(first2 == last2) + break; + } + else{ + op(buf_first1++, first1++); + if(buf_first1 == buf_last1) + break; + } + } + + buf_first1_in_out = buf_first1; + buf_last1_in_out = buf_last1; + return first1; +} + +template<class RandIt, class Buf, class Compare, class Op> +RandIt op_partial_merge_with_buf + ( RandIt first1, RandIt const last1, RandIt first2, RandIt last2 + , Buf &buf + , typename Buf::iterator &buf_first1_in_out + , typename Buf::iterator &buf_last1_in_out + , Compare comp + , Op op + , bool is_stable) +{ + return is_stable + ? op_partial_merge_with_buf_impl + (first1, last1, first2, last2, buf, buf_first1_in_out, buf_last1_in_out, comp, op) + : op_partial_merge_with_buf_impl + (first1, last1, first2, last2, buf, buf_first1_in_out, buf_last1_in_out, antistable<Compare>(comp), op) + ; +} + +// key_first - sequence of keys, in same order as blocks. key_comp(key, midkey) means stream A +// first - first element to merge. +// first[-l_block, 0) - buffer +// l_block - length of regular blocks. Blocks are stable sorted by 1st elements and key-coded +// l_irreg1 is the irregular block to be merged before n_bef_irreg2 blocks (can be 0) +// n_bef_irreg2/n_aft_irreg2 are regular blocks +// l_irreg2 is a irregular block, that is to be merged after n_bef_irreg2 blocks and before n_aft_irreg2 blocks +// If l_irreg2==0 then n_aft_irreg2==0 (no irregular blocks). +template<class RandItKeys, class KeyCompare, class RandIt, class Compare, class Op, class Buf> +void op_merge_blocks_with_buf + ( RandItKeys key_first + , const typename iterator_traits<RandItKeys>::value_type &midkey + , KeyCompare key_comp + , RandIt const first + , typename iterator_traits<RandIt>::size_type const l_block + , typename iterator_traits<RandIt>::size_type const l_irreg1 + , typename iterator_traits<RandIt>::size_type const n_bef_irreg2 + , typename iterator_traits<RandIt>::size_type const n_aft_irreg2 + , typename iterator_traits<RandIt>::size_type const l_irreg2 + , Compare comp + , Op op + , Buf & xbuf) +{ + if(n_bef_irreg2 == 0){ + RandIt const last_reg(first+l_irreg1+n_aft_irreg2*l_block); + op_buffered_merge(first, last_reg, last_reg+l_irreg2, comp, op, xbuf); + } + else { + typedef typename Buf::iterator buf_iterator; + buf_iterator buffer = xbuf.data(); + buf_iterator buffer_end = buffer; + RandIt first1 = first; + RandIt last1 = l_irreg1 ? first1 + l_irreg1 : first1 + l_block; + RandIt first2 = last1; + RandItKeys const key_end (key_first+n_bef_irreg2); + + for( bool is_range1_A = l_irreg1 ? true : key_comp(*key_first, midkey), skip_first_it = l_irreg1 != 0 + ; key_first != key_end; ){ + if(!skip_first_it){ + ++key_first; + } + skip_first_it = false; + bool const last_it = key_first == key_end; + //If the trailing block is empty, we'll make it equal to the previous if empty + bool const is_range2_A = last_it ? (!l_irreg2 && is_range1_A) : key_comp(*key_first, midkey); + + if(is_range1_A == is_range2_A){ + if(buffer != buffer_end){ + first1 = op(forward_t(), buffer, buffer_end, first1); + BOOST_ASSERT(first1 == first2); + buffer_end = buffer; + } + first1 = first2; + if(last_it){ + xbuf.clear(); + last1 = first2+l_block*n_aft_irreg2; + op_buffered_merge(first1, last1, last1+l_irreg2, comp, op, xbuf); + break; + } + else{ + last1 = first2 + l_block; + } + first2 += l_block; + } + else { + BOOST_ASSERT(!last_it || (l_irreg2 || n_aft_irreg2)); + if(last_it){ + RandIt res = op(forward_t(), buffer, buffer_end, first1); + BOOST_ASSERT(buffer == buffer_end || res == last1); (void)res; + last1 += l_block*n_aft_irreg2; + xbuf.clear(); + op_buffered_merge(first1, last1, last1+l_irreg2, comp, op, xbuf); + break; + } + else{ + RandIt const last2 = first2 + l_block; + first1 = op_partial_merge_with_buf(first1, last1, first2, last2, xbuf, buffer, buffer_end, comp, op, is_range1_A); + if(buffer == buffer_end){ + is_range1_A = is_range2_A; + } + last1 = last2; + first2 = last1; + BOOST_ASSERT((buffer == buffer_end) || (buffer_end-buffer) == (last1-first1)); + } + } + } + } +} + +template<class RandItKeys, class KeyCompare, class RandIt, class Compare, class Buf> +void merge_blocks_with_buf + ( RandItKeys key_first + , const typename iterator_traits<RandItKeys>::value_type &midkey + , KeyCompare key_comp + , RandIt const first + , typename iterator_traits<RandIt>::size_type const l_block + , typename iterator_traits<RandIt>::size_type const l_irreg1 + , typename iterator_traits<RandIt>::size_type const n_bef_irreg2 + , typename iterator_traits<RandIt>::size_type const n_aft_irreg2 + , typename iterator_traits<RandIt>::size_type const l_irreg2 + , Compare comp + , Buf & xbuf + , bool const xbuf_used) +{ + if(xbuf_used){ + op_merge_blocks_with_buf + (key_first, midkey, key_comp, first, l_block, l_irreg1, n_bef_irreg2, n_aft_irreg2, l_irreg2, comp, move_op(), xbuf); + } + else{ + op_merge_blocks_with_buf + (key_first, midkey, key_comp, first, l_block, l_irreg1, n_bef_irreg2, n_aft_irreg2, l_irreg2, comp, swap_op(), xbuf); + } +} + +/////////////////////////////////////////////////////////////////////////////// +// +// PARTIAL MERGE LEFT +// +/////////////////////////////////////////////////////////////////////////////// + +template<class RandIt, class Compare, class Op> +RandIt op_partial_merge_left_middle_buffer_impl + (RandIt first1, RandIt const last1, RandIt const first2 + , const typename iterator_traits<RandIt>::value_type &next_key, Compare comp + , Op op) +{ + while(first1 != last1 && !comp(next_key, *first1)){ + ++first1; + } + //Even if we copy backward, no overlapping occurs so use forward copy + //that can be faster specially with trivial types + RandIt const new_first1 = first2 - (last1 - first1); + BOOST_ASSERT(last1 <= new_first1); + op(forward_t(), first1, last1, new_first1); + return new_first1; +} + +template<class RandIt, class Compare, class Op> +RandIt op_partial_merge_left_middle_buffer + ( RandIt first1, RandIt const last1, RandIt const first2 + , const typename iterator_traits<RandIt>::value_type &next_key, Compare comp, Op op, bool is_stable) +{ + return is_stable ? op_partial_merge_left_middle_buffer_impl(first1, last1, first2, next_key, comp, op) + : op_partial_merge_left_middle_buffer_impl(first1, last1, first2, next_key, antistable<Compare>(comp), op); +} + +// Partially merges two ordered ranges. Partially means that elements are merged +// until one of two ranges is exhausted (M elements from ranges 1 y 2). +// [buf_first, ...) -> buffer that can be overwritten +// [first1, last1) merge [last1,last2) -> [buf_first, buf_first+M) +// Note: distance(buf_first, first1) >= distance(last1, last2), so no overlapping occurs. +template<class RandIt, class Compare, class Op> +RandIt op_partial_merge_left_impl + ( RandIt buf_first, RandIt first1, RandIt const last1, RandIt const last2, Compare comp, Op op) +{ + RandIt first2 = last1; + while(first1 != last1){ + if(first2 == last2){ + return first1; + } + if(comp(*first2, *first1)) { + op(first2, buf_first); + ++first2; + } + else{ + op(first1, buf_first); + ++first1; + } + ++buf_first; + } + return first2; +} + + +template<class RandIt, class Compare, class Op> +RandIt op_partial_merge_left + ( RandIt buf_first, RandIt first1, RandIt const last1, RandIt const last2, Compare comp, Op op, bool is_stable) +{ + return is_stable ? op_partial_merge_left_impl(buf_first, first1, last1, last2, comp, op) + : op_partial_merge_left_impl(buf_first, first1, last1, last2, antistable<Compare>(comp), op); +} + +template<class RandIt> +bool three_way_side_init( RandIt first1, RandIt last1, RandIt buf_first1, move_op) +{ + boost::move(first1, last1, buf_first1); + return true; +} + +template<class RandIt> +bool three_way_side_init( RandIt, RandIt, RandIt, swap_op) +{ + return false; +} + +template<class T> +void three_way_side_move(T &a, T &b, T&c, move_op) +{ + c = boost::move(b); + b = boost::move(a); +} + +template<class T> +void three_way_side_move(T &a, T &b, T &c, swap_op) +{ + T tmp(boost::move(c)); + c = boost::move(b); + b = boost::move(a); + a = boost::move(tmp); +} + + +// Partially merges two ordered ranges. Partially means that elements are merged +// until one of two ranges is exhausted (M elements from ranges 1 y 2). +// [buf_first, ...) -> buffer that can be overwritten +// [first1, last1) merge [last1,last2) -> [buf_first, buf_first+M) +// Note: distance(buf_first, first1) >= distance(last1, last2), so no overlapping occurs. +template<class RandIt, class Compare, class Op> +RandIt op_partial_merge_left_smart_impl + ( RandIt first1, RandIt last1, RandIt first2, RandIt const last2, Compare comp, Op op) +{ + typedef typename iterator_traits<RandIt>::value_type value_type; + + RandIt dest; + if(last1 != first2){ + BOOST_ASSERT((first2-last1)==(last2-first2)); + //Skip any element that does not need to be moved + while(!comp(*first2, *first1)){ + ++first1; + if(first1 == last1) + return first2; + } + + RandIt buf_first1 = first2 - (last1-first1); + + //If initialization is successful, move to buffer while merging + //Three way moves need less moves when op is swap_op so use it + //when merging elements from range2 to the destination occupied by range1 + if(!three_way_side_init(first1, last1, buf_first1, op)){ + RandIt buf_last1 = buf_first1; + three_way_side_move(*first2, *first1, *buf_last1++, op); + + RandIt const orig_first2 = first2;(void)(orig_first2); + for(++first1, ++first2; first1 != last1; ++first1, ++buf_last1){ + value_type &v = comp(*first2, *buf_first1) ? *first2++ : *buf_first1++; + three_way_side_move(v, *first1, *buf_last1, op); + } + BOOST_ASSERT(buf_last1 == orig_first2); + last1 = buf_last1; + } + else{ + last1 = first2; + } + dest = first1; + first1 = buf_first1; + BOOST_ASSERT((first1-dest) == (last2-first2)); + } + else{ + dest = first1-(last2-first2); + } + + BOOST_ASSERT(0 != (last1-first1)); + if(first2 != last2) + while(1){ + if(comp(*first2, *first1)) { + op(first2++, dest++); + if(first2 == last2){ + return first1; + } + } + else{ + op(first1++, dest++); + if(first1 == last1){ + return first2; + } + } + } + return first1; +} + + + +template<class RandIt, class Compare, class Op> +RandIt op_partial_merge_left_smart + (RandIt first1, RandIt const last1, RandIt first2, RandIt const last2, Compare comp, Op op, bool is_stable) +{ + return is_stable ? op_partial_merge_left_smart_impl(first1, last1, first2, last2, comp, op) + : op_partial_merge_left_smart_impl(first1, last1, first2, last2, antistable<Compare>(comp), op); +} + + +// first - first element to merge. +// first[-l_block, 0) - buffer +// l_block - length of regular blocks. Blocks are stable sorted by 1st elements and key-coded +// key_first - sequence of keys, in same order as blocks. key<midkey means stream A +// n_bef_irreg2/n_aft_irreg2 are regular blocks +// l_irreg2 is a irregular block, that is to be merged after n_bef_irreg2 blocks and before n_aft_irreg2 blocks +// If l_irreg2==0 then n_aft_irreg2==0 (no irregular blocks). +template<class RandItKeys, class KeyCompare, class RandIt, class Compare, class Op> +void op_merge_blocks_left + ( RandItKeys key_first + , const typename iterator_traits<RandItKeys>::value_type &midkey + , KeyCompare key_comp + , RandIt const first + , typename iterator_traits<RandIt>::size_type const l_block + , typename iterator_traits<RandIt>::size_type const l_irreg1 + , typename iterator_traits<RandIt>::size_type const n_bef_irreg2 + , typename iterator_traits<RandIt>::size_type const n_aft_irreg2 + , typename iterator_traits<RandIt>::size_type const l_irreg2 + , Compare comp, Op op) +{ + if(n_bef_irreg2 == 0){ + RandIt const last_reg(first+l_irreg1+n_aft_irreg2*l_block); + op_merge_left(first-l_block, first, last_reg, last_reg+l_irreg2, comp, op); + } + else { + RandIt buffer = first - l_block; + RandIt first1 = first; + RandIt last1 = l_irreg1 ? first1 + l_irreg1 : first1 + l_block; + RandIt first2 = last1; + RandItKeys const key_end (key_first+n_bef_irreg2); + bool skip_first_it = l_irreg1 != 0; + for( bool is_range1_A = l_irreg1 ? true : key_comp(*key_first, midkey) + ; key_first != key_end; first2 += l_block){ + if(!skip_first_it){ + ++key_first; + } + skip_first_it = false; + bool const last_it = key_first == key_end; + //If the trailing block is empty, we'll make it equal to the previous if empty + bool const is_range2_A = last_it ? (!l_irreg2 && is_range1_A) : key_comp(*key_first, midkey); + bool const is_buffer_middle = last1 == buffer; + + if(is_range1_A == is_range2_A){ + //If range1 is buffered, write it to its final position + if(!is_buffer_middle){ + buffer = op(forward_t(), first1, last1, buffer); + } + + first1 = first2; + if(last_it){ + last1 = first2+l_block*n_aft_irreg2; + op_merge_left(buffer, first1, last1, last1+l_irreg2, comp, op); + break; + } + else{ + last1 = first2 + l_block; + } + } + else { + BOOST_ASSERT(!last_it || (l_irreg2 || n_aft_irreg2)); + if(last_it){ + if(is_buffer_middle){ + //See comment below marked with (*) + first1 = op_partial_merge_left_middle_buffer(first1, last1, first2, first2[l_block*n_aft_irreg2], comp, op, is_range1_A); + last1 = first2; + buffer = first1 - l_block; + } + last1 += l_block*n_aft_irreg2; + op_merge_left(buffer, first1, last1, last1+l_irreg2, comp, op); + break; + } + else{ + RandIt const last2 = first2 + l_block; + first1 = op_partial_merge_left_smart(first1, last1, first2, last2, comp, op, is_range1_A); + + if(first1 < first2){ //is_buffer_middle == true for the next iteration + last1 = first2; + buffer = last1; + } + else{ //is_buffer_middle == false for the next iteration + is_range1_A = is_range2_A; + buffer = first1 - l_block; + last1 = last2; + } + } + } + } + } +} + +/////////////////////////////////////////////////////////////////////////////// +// +// PARTIAL MERGE RIGHT +// +/////////////////////////////////////////////////////////////////////////////// + + +template<class RandIt, class Compare, class Op> +RandIt op_partial_merge_right_middle_buffer_impl + ( RandIt const last1, RandIt const first2, RandIt last2, Compare comp, Op op) +{ + while(first2 != last2 && !comp(last2[-1], last1[-1])){ + --last2; + } + return op(forward_t(), first2, last2, last1); +} + +template<class RandIt, class Compare, class Op> +RandIt op_partial_merge_right_middle_buffer + ( RandIt const last1, RandIt first2, RandIt const last2 + , Compare comp, Op op, bool is_stable) +{ + return is_stable ? op_partial_merge_right_middle_buffer_impl(last1, first2, last2, comp, op) + : op_partial_merge_right_middle_buffer_impl(last1, first2, last2, antistable<Compare>(comp), op); +} + +// Partially merges two ordered ranges. Partially means that elements are merged +// until one of two ranges is exhausted (M elements from ranges 1 y 2). +// [last2, buf_last) -> buffer that can be overwritten +// [first1, last1) merge [last1,last2) -> [buf_last - M, buf_last) +// Note: distance(last2, buf_last) >= distance(first1, last1), so no overlapping occurs. +template<class RandIt, class Compare, class Op> +RandIt op_partial_merge_right_impl + ( RandIt const first1, RandIt last1, RandIt last2, RandIt buf_last, Compare comp, Op op) +{ + RandIt const first2 = last1; + while(first2 != last2){ + if(last1 == first1){ + return last2; + } + --last2; + --last1; + --buf_last; + if(comp(*last2, *last1)){ + op(last1, buf_last); + ++last2; + } + else{ + op(last2, buf_last); + ++last1; + } + } + return last1; +} + +template<class RandIt, class Compare, class Op> +RandIt op_partial_merge_right + ( RandIt first1, RandIt const last1, RandIt const last2, RandIt buf_last, Compare comp, Op op, bool is_stable) +{ + return is_stable ? op_partial_merge_right_impl(first1, last1, last2, buf_last, comp, op) + : op_partial_merge_right_impl(first1, last1, last2, buf_last, antistable<Compare>(comp), op); +} + + +// first - first element to merge. +// last iterator is (first+l_block*(n_bef_irreg2+n_aft_irreg2)+l_irreg2) +// [last, last+l_block) - buffer +// l_block - length of regular blocks. Blocks are stable sorted by 1st elements and key-coded +// key_first - sequence of keys, in same order as blocks. key<midkey means stream A +// n_bef_irreg2/n_aft_irreg2 are regular blocks +// l_irreg2 is a irregular block, that is to be merged after n_bef_irreg2 blocks and before n_aft_irreg2 blocks +// If l_irreg2==0 then n_aft_irreg2==0 (no irregular blocks). +template<class RandItKeys, class KeyCompare, class RandIt, class Compare, class Op> +void op_merge_blocks_right + ( RandItKeys const key_first + , const typename iterator_traits<RandItKeys>::value_type &midkey + , KeyCompare key_comp + , RandIt const first + , typename iterator_traits<RandIt>::size_type const l_block + , typename iterator_traits<RandIt>::size_type const n_bef_irreg2 + , typename iterator_traits<RandIt>::size_type const n_aft_irreg2 + , typename iterator_traits<RandIt>::size_type const l_irreg2 + , Compare comp, Op op) +{ + RandIt last1 = first + (n_bef_irreg2+n_aft_irreg2)*l_block; + RandIt first1 = last1-l_block; + RandIt first2 = last1; + RandIt last2 = first2 + l_irreg2; + RandIt buffer_end = last2 + l_block; + RandItKeys key_end (key_first+(n_bef_irreg2+n_aft_irreg2)); + + for(bool is_range2_A = false; key_first != key_end; last1 = first1, first1 -= l_block){ + --key_end; + bool const is_range1_A = key_comp(*key_end, midkey); + bool const is_buffer_middle = first2 == buffer_end; + + if(is_range1_A == is_range2_A){ + if(!is_buffer_middle){ + buffer_end = op(backward_t(), first2, last2, buffer_end); + } + //else //op forward already done on previous op_partial_merge_right + + first2 = first1; + last2 = last1; + } + else { + if(is_buffer_middle){ + //A previous op_partial_merge_right has right range2 elements after the buffer. + //In order to merge it with the next block, move them to the start of the buffer so that + //buffer is placed to the right. Move only the minimum elements as some range1 elements + //won't be moved in the merge. + last2 = op_partial_merge_right_middle_buffer(last1, first2, last2, comp, op, !is_range2_A); + first2 = last1; + buffer_end = last2 + l_block; + } + + //op_partial_merge_right merges two ranges, but stops moving elements + //once one range is emptied to avoid moving data twice in the next iteration + last2 = op_partial_merge_right(first1, last1, last2, buffer_end, comp, op, !is_range2_A); + if(last2 > first2){ //is_buffer_middle == true for the next iteration + buffer_end = first2; + } + else{ //is_buffer_middle == false for the next iteration + is_range2_A = is_range1_A; + buffer_end = last2 + l_block; + first2 = first1; + } + } + } + + if(first2 != buffer_end){ + op(backward_t(), first2, last2, buffer_end); + } +} + +/////////////////////////////////////////////////////////////////////////////// +// +// PARTIAL MERGE BUFFERLESS +// +/////////////////////////////////////////////////////////////////////////////// + +// [first1, last1) merge [last1,last2) -> [first1,last2) +template<class RandIt, class Compare> +RandIt partial_merge_bufferless_impl + (RandIt first1, RandIt last1, RandIt const last2, bool *const pis_range1_A, Compare comp) +{ + if(last1 == last2){ + return first1; + } + bool const is_range1_A = *pis_range1_A; + if(first1 != last1 && comp(*last1, last1[-1])){ + do{ + RandIt const old_last1 = last1; + last1 = lower_bound(last1, last2, *first1, comp); + first1 = rotate_gcd(first1, old_last1, last1);//old_last1 == last1 supported + if(last1 == last2){ + return first1; + } + do{ + ++first1; + } while(last1 != first1 && !comp(*last1, *first1) ); + } while(first1 != last1); + } + *pis_range1_A = !is_range1_A; + return last1; +} + +// [first1, last1) merge [last1,last2) -> [first1,last2) +template<class RandIt, class Compare> +RandIt partial_merge_bufferless + (RandIt first1, RandIt last1, RandIt const last2, bool *const pis_range1_A, Compare comp) +{ + return *pis_range1_A ? partial_merge_bufferless_impl(first1, last1, last2, pis_range1_A, comp) + : partial_merge_bufferless_impl(first1, last1, last2, pis_range1_A, antistable<Compare>(comp)); +} + + + +// l_block - length of regular blocks. First nblocks are stable sorted by 1st elements and key-coded +// keys - sequence of keys, in same order as blocks. key<midkey means stream A +// n_aft_irreg2 are regular blocks from stream A. l_irreg2 is length of last (irregular) block from stream B, that should go before n_aft_irreg2 blocks. +// l_irreg2=0 requires n_aft_irreg2=0 (no irregular blocks). l_irreg2>0, n_aft_irreg2=0 is possible. +template<class RandItKeys, class KeyCompare, class RandIt, class Compare> +void merge_blocks_bufferless + ( RandItKeys key_first + , const typename iterator_traits<RandItKeys>::value_type &midkey + , KeyCompare key_comp + , RandIt first + , typename iterator_traits<RandIt>::size_type const l_block + , typename iterator_traits<RandIt>::size_type const l_irreg1 + , typename iterator_traits<RandIt>::size_type const n_bef_irreg2 + , typename iterator_traits<RandIt>::size_type const n_aft_irreg2 + , typename iterator_traits<RandIt>::size_type const l_irreg2 + , Compare comp) +{ + if(n_bef_irreg2 == 0){ + RandIt const last_reg(first+l_irreg1+n_aft_irreg2*l_block); + merge_bufferless(first, last_reg, last_reg+l_irreg2, comp); + } + else{ + RandIt first1 = first; + RandIt last1 = l_irreg1 ? first + l_irreg1: first + l_block; + RandItKeys const key_end (key_first+n_bef_irreg2); + bool is_range1_A = l_irreg1 ? true : key_comp(*key_first++, midkey); + + for( ; key_first != key_end; ++key_first){ + bool is_range2_A = key_comp(*key_first, midkey); + if(is_range1_A == is_range2_A){ + first1 = last1; + } + else{ + first1 = partial_merge_bufferless(first1, last1, last1 + l_block, &is_range1_A, comp); + } + last1 += l_block; + } + + if(l_irreg2){ + if(!is_range1_A){ + first1 = last1; + } + last1 += l_block*n_aft_irreg2; + merge_bufferless(first1, last1, last1+l_irreg2, comp); + } + } +} + +/////////////////////////////////////////////////////////////////////////////// +// +// 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 = 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); + 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> +void buffered_merge + ( RandIt first, RandIt const middle, RandIt last + , Compare comp + , adaptive_xbuf<typename iterator_traits<RandIt>::value_type> &xbuf) +{ + op_buffered_merge(first, middle, last, comp, move_op(), xbuf); +} + +// Complexity: 2*distance(first, last)+max_collected^2/2 +// +// Tries to collect at most n_keys unique elements from [first, last), +// in the begining of the range, and ordered according to comp +// +// Returns the number of collected keys +template<class RandIt, class Compare> +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) +{ + 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 + RandIt h0 = first; + RandIt u = first; ++u; + RandIt search_end = u; + + if(xbuf.capacity() >= max_collected){ + value_type *const ph0 = xbuf.add(first); + while(u != last && h < max_collected){ + value_type * const r = 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); + search_end = u; + ++search_end; + ++h; + xbuf.insert(r, u); + h0 = new_h0; + } + ++u; + } + boost::move_backward(first, h0, h0+h); + boost::move(xbuf.data(), xbuf.end(), first); + } + else{ + while(u != last && h < max_collected){ + RandIt const r = 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); + search_end = u; + ++search_end; + ++h; + rotate_gcd(r+(new_h0-h0), u, search_end); + h0 = new_h0; + } + ++u; + } + rotate_gcd(first, h0, h0+h); + } + } + return h; +} + +template<class Unsigned> +Unsigned floor_sqrt(Unsigned const n) +{ + Unsigned x = n; + Unsigned y = x/2 + (x&1); + while (y < x){ + x = y; + y = (x + n / x)/2; + } + return x; +} + +template<class Unsigned> +Unsigned ceil_sqrt(Unsigned const n) +{ + Unsigned r = floor_sqrt(n); + return r + Unsigned((n%r) != 0); +} + +template<class Unsigned> +Unsigned floor_merge_multiple(Unsigned const n, Unsigned &base, Unsigned &pow) +{ + Unsigned s = n; + Unsigned p = 0; + while(s > AdaptiveSortInsertionSortThreshold){ + s /= 2; + ++p; + } + base = s; + pow = p; + return s << p; +} + +template<class Unsigned> +Unsigned ceil_merge_multiple(Unsigned const n, Unsigned &base, Unsigned &pow) +{ + Unsigned fm = floor_merge_multiple(n, base, pow); + + if(fm != n){ + if(base < AdaptiveSortInsertionSortThreshold){ + ++base; + } + else{ + base = AdaptiveSortInsertionSortThreshold/2 + 1; + ++pow; + } + } + return base << pow; +} + +template<class Unsigned> +Unsigned ceil_sqrt_multiple(Unsigned const n, Unsigned *pbase = 0) +{ + Unsigned const r = ceil_sqrt(n); + Unsigned pow = 0; + Unsigned base = 0; + Unsigned const res = ceil_merge_multiple(r, base, pow); + if(pbase) *pbase = base; + return res; +} + +template<class Unsigned> +Unsigned ceil_sqrt_pow2(Unsigned const n) +{ + Unsigned r=1; + Unsigned exp = 0; + Unsigned pow = 1u; + while(pow != 0 && pow < n){ + r*=2; + ++exp; + pow = r << exp; + } + return r; +} + +struct less +{ + template<class T> + bool operator()(const T &l, const T &r) + { return l < r; } +}; + +/////////////////////////////////////////////////////////////////////////////// +// +// MERGE BLOCKS +// +/////////////////////////////////////////////////////////////////////////////// + +template<class RandIt, class Compare> +void slow_stable_sort + ( RandIt const first, RandIt const last, Compare comp) +{ + typedef typename iterator_traits<RandIt>::size_type size_type; + size_type L = size_type(last - first); + { //Use insertion sort to merge first elements + size_type m = 0; + while((L - m) > size_type(AdaptiveSortInsertionSortThreshold)){ + insertion_sort(first+m, first+m+size_type(AdaptiveSortInsertionSortThreshold), comp); + m += AdaptiveSortInsertionSortThreshold; + } + insertion_sort(first+m, last, comp); + } + + size_type h = AdaptiveSortInsertionSortThreshold; + for(bool do_merge = L > h; do_merge; h*=2){ + do_merge = (L - h) > h; + size_type p0 = 0; + if(do_merge){ + size_type const h_2 = 2*h; + while((L-p0) > h_2){ + merge_bufferless(first+p0, first+p0+h, first+p0+h_2, comp); + p0 += h_2; + } + } + if((L-p0) > h){ + merge_bufferless(first+p0, first+p0+h, last, comp); + } + } +} + +//Returns new l_block and updates use_buf +template<class Unsigned> +Unsigned lblock_for_combine + (Unsigned const l_block, Unsigned const n_keys, Unsigned const l_data, bool &use_buf) +{ + BOOST_ASSERT(l_data > 1); + + //We need to guarantee lblock >= l_merged/(n_keys/2) keys for the combination. + //We have at least 4 keys guaranteed (which are the minimum to merge 2 ranges) + //If l_block != 0, then n_keys is already enough to merge all blocks in all + //phases as we've found all needed keys for that buffer and length before. + //If l_block == 0 then see if half keys can be used as buffer and the rest + //as keys guaranteeing that n_keys >= (2*l_merged)/lblock = + if(!l_block){ + //If l_block == 0 then n_keys is power of two + //(guaranteed by build_params(...)) + BOOST_ASSERT(n_keys >= 4); + //BOOST_ASSERT(0 == (n_keys &(n_keys-1))); + + //See if half keys are at least 4 and if half keys fulfill + Unsigned const new_buf = n_keys/2; + Unsigned const new_keys = n_keys-new_buf; + use_buf = new_keys >= 4 && new_keys >= l_data/new_buf; + if(use_buf){ + return new_buf; + } + else{ + return l_data/n_keys; + } + } + else{ + use_buf = true; + return l_block; + } +} + + +//Although "cycle" sort is known to have the minimum number of writes to target +//selection sort is more appropriate here as we want to minimize swaps. +template<class RandItKeys, class KeyCompare, class RandIt, class Compare> +void selection_sort_blocks + ( RandItKeys keys + , typename iterator_traits<RandIt>::size_type &midkey_idx //inout + , KeyCompare key_comp + , RandIt const first_block + , typename iterator_traits<RandIt>::size_type const l_block + , typename iterator_traits<RandIt>::size_type const n_blocks + , Compare comp + , bool use_first_element) +{ + typedef typename iterator_traits<RandIt>::size_type size_type ; + size_type const back_midkey_idx = midkey_idx; + typedef typename iterator_traits<RandIt>::size_type size_type; + typedef typename iterator_traits<RandIt>::value_type value_type; + + //Nothing to sort if 0 or 1 blocks or all belong to the first ordered half + if(n_blocks < 2 || back_midkey_idx >= n_blocks){ + return; + } + //One-past the position of the first untouched element of the second half + size_type high_watermark = back_midkey_idx+1; + BOOST_ASSERT(high_watermark <= n_blocks); + + //Sort by first element if left merging, last element otherwise + size_type const reg_off = use_first_element ? 0u: l_block-1; + + for(size_type block=0; block < n_blocks-1; ++block){ + size_type min_block = block; + //Since we are searching for the minimum value in two sorted halves: + //Optimization 1: If block belongs to first half, don't waste time comparing elements of the first half. + //Optimization 2: It is enough to compare until the first untouched element of the second half. + high_watermark = size_type(max_value(block+2, high_watermark)); + BOOST_ASSERT(high_watermark <= n_blocks); + for(size_type next_block = size_type(max_value(block+1, back_midkey_idx)); next_block < high_watermark; ++next_block){ + const value_type &v = first_block[next_block*l_block+reg_off]; + const value_type &min = first_block[min_block*l_block+reg_off]; + if( comp(v, min) || (!comp(min, v) && key_comp(keys[next_block], keys[min_block])) ){ + min_block=next_block; + } + } + + if(min_block != block){ + BOOST_ASSERT(block >= back_midkey_idx || min_block >= back_midkey_idx); + BOOST_ASSERT(min_block < high_watermark); + //Update high watermark if n_blocks is not surpassed + high_watermark += size_type((min_block + 1) != n_blocks && (min_block + 1) == high_watermark); + BOOST_ASSERT(high_watermark <= n_blocks); + boost::adl_move_swap_ranges(first_block+block*l_block, first_block+(block+1)*l_block, first_block+min_block*l_block); + boost::adl_move_swap(keys[block], keys[min_block]); + if(midkey_idx == block) + midkey_idx = min_block; + else if(midkey_idx == min_block) + midkey_idx = block; + } + } +} + +template<class RandIt, class Compare> +void stable_sort( RandIt first, RandIt last, Compare comp + , adaptive_xbuf<typename iterator_traits<RandIt>::value_type> & xbuf) +{ + typedef typename iterator_traits<RandIt>::size_type size_type; + size_type const len = size_type(last - first); + size_type const half_len = len/2 + (len&1); + if(std::size_t(xbuf.capacity() - xbuf.size()) >= half_len) { + merge_sort(first, last, comp, xbuf.data()+xbuf.size()); + } + else{ + slow_stable_sort(first, last, comp); + } +} + +template<class RandIt, class Comp> +void initialize_keys( RandIt first, RandIt last + , Comp comp + , adaptive_xbuf<typename iterator_traits<RandIt>::value_type> & xbuf) +{ + stable_sort(first, last, comp, xbuf); +} + +template<class RandIt, class U> +void initialize_keys( RandIt first, RandIt last + , less + , U &) +{ + typedef typename iterator_traits<RandIt>::value_type value_type; + std::size_t count = std::size_t(last - first); + for(std::size_t i = 0; i != count; ++i){ + *first = value_type(i); + ++first; + } +} + +template<class RandItKeys, class KeyCompare, class RandIt, class Compare> +void combine_params + ( RandItKeys const keys + , KeyCompare key_comp + , RandIt const first + , typename iterator_traits<RandIt>::size_type l_combined + , typename iterator_traits<RandIt>::size_type const l_prev_merged + , typename iterator_traits<RandIt>::size_type const l_block + , adaptive_xbuf<typename iterator_traits<RandIt>::value_type> & xbuf + , Compare comp + //Output + , typename iterator_traits<RandIt>::size_type &midkey_idx + , typename iterator_traits<RandIt>::size_type &l_irreg1 + , typename iterator_traits<RandIt>::size_type &n_bef_irreg2 + , typename iterator_traits<RandIt>::size_type &n_aft_irreg2 + , typename iterator_traits<RandIt>::size_type &l_irreg2 + , bool is_merge_left) +{ + typedef typename iterator_traits<RandIt>::size_type size_type; + typedef typename iterator_traits<RandIt>::value_type value_type; + + l_irreg1 = l_prev_merged%l_block; + l_irreg2 = (l_combined-l_irreg1)%l_block; + BOOST_ASSERT(((l_combined-l_irreg1-l_irreg2)%l_block) == 0); + size_type const n_reg_block = (l_combined-l_irreg1-l_irreg2)/l_block; + midkey_idx = l_prev_merged/l_block; + BOOST_ASSERT(n_reg_block>=midkey_idx); + initialize_keys(keys, keys+n_reg_block+(midkey_idx==n_reg_block), key_comp, xbuf); + selection_sort_blocks(keys, midkey_idx, key_comp, first+l_irreg1, l_block, n_reg_block, comp, is_merge_left); + + n_aft_irreg2 = 0; + if(l_irreg2!=0){ + size_type const reg_off = is_merge_left ? 0u: l_block-1; + size_type const irreg_off = is_merge_left ? 0u: l_irreg2-1; + RandIt prev_block_first = first + l_combined - l_irreg2; + const value_type &incomplete_block_first = prev_block_first[irreg_off]; + while(n_aft_irreg2 != n_reg_block && + comp(incomplete_block_first, (prev_block_first-= l_block)[reg_off]) ){ + ++n_aft_irreg2; + } + } + n_bef_irreg2 = n_reg_block-n_aft_irreg2; +} + +// first - first element to merge. +// first[-l_block, 0) - buffer (if use_buf == true) +// l_block - length of regular blocks. First nblocks are stable sorted by 1st elements and key-coded +// keys - sequence of keys, in same order as blocks. key<midkey means stream A +// n_bef_irreg2/n_aft_irreg2 are regular blocks +// l_irreg2 is a irregular block, that is to be combined after n_bef_irreg2 blocks and before n_aft_irreg2 blocks +// If l_irreg2==0 then n_aft_irreg2==0 (no irregular blocks). +template<class RandItKeys, class KeyCompare, class RandIt, class Compare> +void merge_blocks_left + ( RandItKeys const key_first + , const typename iterator_traits<RandItKeys>::value_type &midkey + , KeyCompare key_comp + , RandIt const first + , typename iterator_traits<RandIt>::size_type const l_block + , typename iterator_traits<RandIt>::size_type const l_irreg1 + , typename iterator_traits<RandIt>::size_type const n_bef_irreg2 + , typename iterator_traits<RandIt>::size_type const n_aft_irreg2 + , typename iterator_traits<RandIt>::size_type const l_irreg2 + , Compare comp + , bool const xbuf_used) +{ + if(xbuf_used){ + op_merge_blocks_left + (key_first, midkey, key_comp, first, l_block, l_irreg1, n_bef_irreg2, n_aft_irreg2, l_irreg2, comp, move_op()); + } + else{ + op_merge_blocks_left + (key_first, midkey, key_comp, first, l_block, l_irreg1, n_bef_irreg2, n_aft_irreg2, l_irreg2, comp, swap_op()); + } +} + + +// first - first element to merge. +// [first+l_block*(n_bef_irreg2+n_aft_irreg2)+l_irreg2, first+l_block*(n_bef_irreg2+n_aft_irreg2+1)+l_irreg2) - buffer +// l_block - length of regular blocks. First nblocks are stable sorted by 1st elements and key-coded +// keys - sequence of keys, in same order as blocks. key<midkey means stream A +// n_bef_irreg2/n_aft_irreg2 are regular blocks +// l_irreg2 is a irregular block, that is to be combined after n_bef_irreg2 blocks and before n_aft_irreg2 blocks +// If l_irreg2==0 then n_aft_irreg2==0 (no irregular blocks). +template<class RandItKeys, class KeyCompare, class RandIt, class Compare> +void merge_blocks_right + ( RandItKeys const key_first + , const typename iterator_traits<RandItKeys>::value_type &midkey + , KeyCompare key_comp + , RandIt const first + , typename iterator_traits<RandIt>::size_type const l_block + , typename iterator_traits<RandIt>::size_type const n_bef_irreg2 + , typename iterator_traits<RandIt>::size_type const n_aft_irreg2 + , typename iterator_traits<RandIt>::size_type const l_irreg2 + , Compare comp + , bool const xbuf_used) +{ + if(xbuf_used){ + op_merge_blocks_right + (key_first, midkey, key_comp, first, l_block, n_bef_irreg2, n_aft_irreg2, l_irreg2, comp, move_op()); + } + else{ + op_merge_blocks_right + (key_first, midkey, key_comp, first, l_block, n_bef_irreg2, n_aft_irreg2, l_irreg2, comp, swap_op()); + } +} + + +template<class RandIt> +void move_data_backward( RandIt cur_pos + , typename iterator_traits<RandIt>::size_type const l_data + , RandIt new_pos + , bool const xbuf_used) +{ + //Move buffer to the total combination right + if(xbuf_used){ + boost::move_backward(cur_pos, cur_pos+l_data, new_pos+l_data); + } + else{ + boost::adl_move_swap_ranges_backward(cur_pos, cur_pos+l_data, new_pos+l_data); + //Rotate does less moves but it seems slower due to cache issues + //rotate_gcd(first-l_block, first+len-l_block, first+len); + } +} + +template<class RandIt> +void move_data_forward( RandIt cur_pos + , typename iterator_traits<RandIt>::size_type const l_data + , RandIt new_pos + , bool const xbuf_used) +{ + //Move buffer to the total combination right + if(xbuf_used){ + boost::move(cur_pos, cur_pos+l_data, new_pos); + } + else{ + boost::adl_move_swap_ranges(cur_pos, cur_pos+l_data, new_pos); + //Rotate does less moves but it seems slower due to cache issues + //rotate_gcd(first-l_block, first+len-l_block, first+len); + } +} + +template <class Unsigned> +Unsigned calculate_total_combined(Unsigned const len, Unsigned const l_prev_merged, Unsigned *pl_irreg_combined = 0) +{ + typedef Unsigned size_type; + + size_type const l_combined = 2*l_prev_merged; + size_type l_irreg_combined = len%l_combined; + size_type l_total_combined = len; + if(l_irreg_combined <= l_prev_merged){ + l_total_combined -= l_irreg_combined; + l_irreg_combined = 0; + } + if(pl_irreg_combined) + *pl_irreg_combined = l_irreg_combined; + return l_total_combined; +} + +// keys are on the left of first: +// If use_buf: [first - l_block - n_keys, first - l_block). +// Otherwise: [first - n_keys, first). +// Buffer (if use_buf) is also on the left of first [first - l_block, first). +// Blocks of length l_prev_merged combined. We'll combine them in pairs +// l_prev_merged and n_keys are powers of 2. (2*l_prev_merged/l_block) keys are guaranteed +// Returns the number of combined elements (some trailing elements might be left uncombined) +template<class RandItKeys, class KeyCompare, class RandIt, class Compare> +void combine_blocks + ( RandItKeys const keys + , KeyCompare key_comp + , RandIt const first + , typename iterator_traits<RandIt>::size_type const len + , typename iterator_traits<RandIt>::size_type const l_prev_merged + , typename iterator_traits<RandIt>::size_type const l_block + , bool const use_buf + , bool const xbuf_used + , adaptive_xbuf<typename iterator_traits<RandIt>::value_type> & xbuf + , Compare comp + , bool merge_left) +{ + typedef typename iterator_traits<RandIt>::size_type size_type; + + size_type const l_combined = 2*l_prev_merged; + size_type l_irreg_combined = 0; + size_type const l_total_combined = calculate_total_combined(len, l_prev_merged, &l_irreg_combined); + size_type const n_reg_combined = len/l_combined; + RandIt combined_first = first; + + (void)l_total_combined; + BOOST_ASSERT(l_total_combined <= len); + + size_type n_bef_irreg2, n_aft_irreg2, midkey_idx, l_irreg1, l_irreg2; + size_type const max_i = n_reg_combined + (l_irreg_combined != 0); + + if(merge_left || !use_buf) + for( size_type combined_i = 0; combined_i != max_i; ++combined_i, combined_first += l_combined) { + bool const is_last = combined_i==n_reg_combined; + combine_params( keys, key_comp, combined_first, is_last ? l_irreg_combined : l_combined + , l_prev_merged, l_block, xbuf, comp + , midkey_idx, l_irreg1, n_bef_irreg2, n_aft_irreg2, l_irreg2, true); //Outputs + //BOOST_MOVE_ADAPTIVE_SORT_PRINT(" After combine_params: ", len + l_block); + BOOST_ASSERT(!l_irreg1); + if(use_buf){ + merge_blocks_left + (keys, keys[midkey_idx], key_comp, combined_first, l_block, 0u, n_bef_irreg2, n_aft_irreg2, l_irreg2, comp, xbuf_used); + } + else{ + merge_blocks_bufferless + (keys, keys[midkey_idx], key_comp, combined_first, l_block, 0u, n_bef_irreg2, n_aft_irreg2, l_irreg2, comp); + } + //BOOST_MOVE_ADAPTIVE_SORT_PRINT(" After merge_blocks_l: ", len + l_block); + } + else{ + combined_first += l_combined*(max_i-1); + for( size_type combined_i = max_i; combined_i--; combined_first -= l_combined) { + bool const is_last = combined_i==n_reg_combined; + combine_params( keys, key_comp, combined_first, is_last ? l_irreg_combined : l_combined + , l_prev_merged, l_block, xbuf, comp + , midkey_idx, l_irreg1, n_bef_irreg2, n_aft_irreg2, l_irreg2, false); //Outputs + BOOST_ASSERT(!l_irreg1); + //BOOST_MOVE_ADAPTIVE_SORT_PRINT(" After combine_params: ", len + l_block); + merge_blocks_right + (keys, keys[midkey_idx], key_comp, combined_first, l_block, n_bef_irreg2, n_aft_irreg2, l_irreg2, comp, xbuf_used); + //BOOST_MOVE_ADAPTIVE_SORT_PRINT(" After merge_blocks_r: ", len + l_block); + } + } +} + + +template<class RandIt, class Compare> +typename iterator_traits<RandIt>::size_type + buffered_merge_blocks + ( RandIt const first, RandIt const last + , typename iterator_traits<RandIt>::size_type const input_combined_size + , Compare comp + , adaptive_xbuf<typename iterator_traits<RandIt>::value_type> &xbuf) +{ + typedef typename iterator_traits<RandIt>::size_type size_type; + size_type combined_size = input_combined_size; + + for( size_type const elements_in_blocks = size_type(last - first) + ; elements_in_blocks > combined_size && size_type(xbuf.capacity()) >= combined_size + ; combined_size *=2){ + RandIt merge_point = first; + while(size_type(last - merge_point) > 2*combined_size) { + RandIt const second_half = merge_point+combined_size; + RandIt const next_merge_point = second_half+combined_size; + buffered_merge(merge_point, second_half, next_merge_point, comp, xbuf); + merge_point = next_merge_point; + } + if(size_type(last-merge_point) > combined_size){ + buffered_merge(merge_point, merge_point+combined_size, last, comp, xbuf); + } + } + return combined_size; +} + +template<class RandIt, class Compare, class Op> +typename iterator_traits<RandIt>::size_type + op_insertion_sort_step_left + ( RandIt const first + , typename iterator_traits<RandIt>::size_type const length + , typename iterator_traits<RandIt>::size_type const step + , Compare comp, Op op) +{ + typedef typename iterator_traits<RandIt>::size_type size_type; + size_type const s = min_value<size_type>(step, AdaptiveSortInsertionSortThreshold); + size_type m = 0; + + while((length - m) > s){ + insertion_sort_op(first+m, first+m+s, first+m-s, comp, op); + m += s; + } + insertion_sort_op(first+m, first+length, first+m-s, comp, op); + return s; +} + +template<class RandIt, class Compare> +typename iterator_traits<RandIt>::size_type + insertion_sort_step + ( RandIt const first + , typename iterator_traits<RandIt>::size_type const length + , typename iterator_traits<RandIt>::size_type const step + , Compare comp) +{ + typedef typename iterator_traits<RandIt>::size_type size_type; + size_type const s = min_value<size_type>(step, AdaptiveSortInsertionSortThreshold); + size_type m = 0; + + while((length - m) > s){ + insertion_sort(first+m, first+m+s, comp); + m += s; + } + insertion_sort(first+m, first+length, comp); + return s; +} + +template<class RandIt, class Compare, class Op> +typename iterator_traits<RandIt>::size_type + op_merge_left_step + ( RandIt first_block + , typename iterator_traits<RandIt>::size_type const elements_in_blocks + , typename iterator_traits<RandIt>::size_type l_merged + , typename iterator_traits<RandIt>::size_type const l_build_buf + , typename iterator_traits<RandIt>::size_type l_left_space + , Compare comp + , Op op) +{ + typedef typename iterator_traits<RandIt>::size_type size_type; + for(; l_merged < l_build_buf && l_left_space >= l_merged; l_merged*=2){ + size_type p0=0; + RandIt pos = first_block; + while((elements_in_blocks - p0) > 2*l_merged) { + op_merge_left(pos-l_merged, pos, pos+l_merged, pos+2*l_merged, comp, op); + p0 += 2*l_merged; + pos = first_block+p0; + } + if((elements_in_blocks-p0) > l_merged) { + op_merge_left(pos-l_merged, pos, pos+l_merged, first_block+elements_in_blocks, comp, op); + } + else { + op(forward_t(), pos, first_block+elements_in_blocks, pos-l_merged); + } + first_block -= l_merged; + l_left_space -= l_merged; + } + return l_merged; +} + +template<class RandIt, class Compare, class Op> +void op_merge_right_step + ( RandIt first_block + , typename iterator_traits<RandIt>::size_type const elements_in_blocks + , typename iterator_traits<RandIt>::size_type const l_build_buf + , Compare comp + , Op op) +{ + typedef typename iterator_traits<RandIt>::size_type size_type; + size_type restk = elements_in_blocks%(2*l_build_buf); + size_type p = elements_in_blocks - restk; + BOOST_ASSERT(0 == (p%(2*l_build_buf))); + + if(restk <= l_build_buf){ + op(backward_t(),first_block+p, first_block+p+restk, first_block+p+restk+l_build_buf); + } + else{ + op_merge_right(first_block+p, first_block+p+l_build_buf, first_block+p+restk, first_block+p+restk+l_build_buf, comp, op); + } + while(p>0){ + p -= 2*l_build_buf; + op_merge_right(first_block+p, first_block+p+l_build_buf, first_block+p+2*l_build_buf, first_block+p+3*l_build_buf, comp, op); + } +} + + +// build blocks of length 2*l_build_buf. l_build_buf is power of two +// input: [0, l_build_buf) elements are buffer, rest unsorted elements +// output: [0, l_build_buf) elements are buffer, blocks 2*l_build_buf and last subblock sorted +// +// First elements are merged from right to left until elements start +// at first. All old elements [first, first + l_build_buf) are placed at the end +// [first+len-l_build_buf, first+len). To achieve this: +// - If we have external memory to merge, we save elements from the buffer +// so that a non-swapping merge is used. Buffer elements are restored +// at the end of the buffer from the external memory. +// +// - When the external memory is not available or it is insufficient +// for a merge operation, left swap merging is used. +// +// Once elements are merged left to right in blocks of l_build_buf, then a single left +// to right merge step is performed to achieve merged blocks of size 2K. +// If external memory is available, usual merge is used, swap merging otherwise. +// +// 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> +typename iterator_traits<RandIt>::size_type + 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 + , Compare comp) +{ + typedef typename iterator_traits<RandIt>::size_type size_type; + BOOST_ASSERT(l_build_buf <= len); + BOOST_ASSERT(0 == ((l_build_buf / l_base)&(l_build_buf/l_base-1))); + + //Place the start pointer after the buffer + RandIt first_block = first + l_build_buf; + size_type const elements_in_blocks = len - l_build_buf; + + ////////////////////////////////// + // Start of merge to left step + ////////////////////////////////// + size_type l_merged = 0u; + +// if(xbuf.capacity()>=2*l_build_buf){ + if(!l_build_buf){ + l_merged = insertion_sort_step(first_block, elements_in_blocks, l_base, comp); + //2*l_build_buf already merged, now try to merge further + //using classic in-place mergesort if enough auxiliary memory is available + return buffered_merge_blocks + (first_block, first_block + elements_in_blocks, l_merged, comp, xbuf); + } + else{ + //If there is no enough buffer for the insertion sort step, just avoid the external buffer + size_type kbuf = min_value<size_type>(l_build_buf, size_type(xbuf.capacity())); + kbuf = kbuf < l_base ? 0 : kbuf; + + if(kbuf){ + //Backup internal buffer values in external buffer so they can be overwritten + xbuf.move_assign(first+l_build_buf-kbuf, kbuf); + l_merged = op_insertion_sort_step_left(first_block, elements_in_blocks, l_base, comp, move_op()); + + //Now combine them using the buffer. Elements from buffer can be + //overwritten since they've been saved to xbuf + l_merged = op_merge_left_step + ( first_block - l_merged, elements_in_blocks, l_merged, l_build_buf, kbuf - l_merged, comp, move_op()); + + //Restore internal buffer from external buffer unless kbuf was l_build_buf, + //in that case restoration will happen later + if(kbuf != l_build_buf){ + boost::move(xbuf.data()+kbuf-l_merged, xbuf.data() + kbuf, first_block-l_merged+elements_in_blocks); + } + } + else{ + l_merged = insertion_sort_step(first_block, elements_in_blocks, l_base, comp); + rotate_gcd(first_block - l_merged, first_block, first_block+elements_in_blocks); + } + + //Now combine elements using the buffer. Elements from buffer can't be + //overwritten since xbuf was not big enough, so merge swapping elements. + l_merged = op_merge_left_step + (first_block - l_merged, elements_in_blocks, l_merged, l_build_buf, l_build_buf - l_merged, comp, swap_op()); + + BOOST_ASSERT(l_merged == l_build_buf); + + ////////////////////////////////// + // Start of merge to right step + ////////////////////////////////// + + //If kbuf is l_build_buf then we can merge right without swapping + //Saved data is still in xbuf + if(kbuf && kbuf == l_build_buf){ + op_merge_right_step(first, elements_in_blocks, l_build_buf, comp, move_op()); + //Restore internal buffer from external buffer if kbuf was l_build_buf. + //as this operation was previously delayed. + boost::move(xbuf.data(), xbuf.data() + kbuf, first); + } + else{ + op_merge_right_step(first, elements_in_blocks, l_build_buf, comp, swap_op()); + } + xbuf.clear(); + //2*l_build_buf already merged, now try to merge further + //using classic in-place mergesort if enough auxiliary memory is available + return buffered_merge_blocks + (first_block, first_block + elements_in_blocks, l_build_buf*2, comp, xbuf); + } +} + +//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> +bool combine_all_blocks + ( RandIt keys + , typename iterator_traits<RandIt>::size_type &n_keys + , RandIt const buffer + , 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 + , Compare comp) +{ + typedef typename iterator_traits<RandIt>::size_type size_type; + RandIt const first = buffer + l_intbuf; + size_type const l_data = l_buf_plus_data - l_intbuf; + size_type const l_unique = l_intbuf+n_keys; + //Backup data to external buffer once if possible + bool const common_xbuf = l_data > l_merged && l_intbuf && l_intbuf <= xbuf.capacity(); + if(common_xbuf){ + if(n_keys){ + xbuf.move_assign(buffer, l_intbuf); + } + else{ + xbuf.clear(); + merge_sort_uninitialized_copy(buffer, first, xbuf.data(), comp); + xbuf.set_size(l_intbuf); + } + } + + bool prev_merge_left = true; + size_type l_prev_total_combined = 0u, l_prev_block = 0; + bool prev_use_internal_buf = true; + + for( size_type n = 0; l_data > l_merged + ; l_merged*=2 + , ++n){ + //If l_intbuf is non-zero, use that internal buffer. + // Implies l_block == l_intbuf && use_internal_buf == true + //If l_intbuf is zero, see if half keys can be reused as a reduced emergency buffer, + // Implies l_block == n_keys/2 && use_internal_buf == true + //Otherwise, just give up and and use all keys to merge using rotations (use_internal_buf = false) + bool use_internal_buf = false; + size_type const l_block = lblock_for_combine(l_intbuf, n_keys, 2*l_merged, use_internal_buf); + BOOST_ASSERT(!l_intbuf || (l_block == l_intbuf)); + BOOST_ASSERT(n == 0 || (!use_internal_buf || prev_use_internal_buf) ); + BOOST_ASSERT(n == 0 || (!use_internal_buf || l_prev_block == l_block) ); + + bool const is_merge_left = (n&1) == 0; + size_type const l_total_combined = calculate_total_combined(l_data, l_merged); + + if(prev_use_internal_buf && prev_merge_left){ + if(is_merge_left || !use_internal_buf){ + move_data_backward(first-l_prev_block, l_prev_total_combined, first, common_xbuf); + } + else{ + //Put the buffer just after l_total_combined + RandIt const buf_end = first+l_prev_total_combined; + RandIt const buf_beg = buf_end-l_block; + if(l_prev_total_combined > l_total_combined){ + size_type const l_diff = l_prev_total_combined - l_total_combined; + move_data_backward(buf_beg-l_diff, l_diff, buf_end-l_diff, common_xbuf); + } + else if(l_prev_total_combined < l_total_combined){ + size_type const l_diff = l_total_combined - l_prev_total_combined; + move_data_forward(buf_end, l_diff, buf_beg, common_xbuf); + } + } + } + BOOST_MOVE_ADAPTIVE_SORT_PRINT(" After move_data : ", l_data + l_intbuf); + + //Combine to form l_merged*2 segments + if(n_keys){ + combine_blocks + ( keys, comp, !use_internal_buf || is_merge_left ? first : first-l_block + , l_data, l_merged, l_block, use_internal_buf, common_xbuf, xbuf, comp, is_merge_left); + } + else{ + size_type *const uint_keys = xbuf.template aligned_trailing<size_type>(); + combine_blocks + ( uint_keys, less(), !use_internal_buf || is_merge_left ? first : first-l_block + , l_data, l_merged, l_block, use_internal_buf, common_xbuf, xbuf, comp, is_merge_left); + } + BOOST_MOVE_ADAPTIVE_SORT_PRINT(" After combine_blocks: ", l_data + l_intbuf); + prev_merge_left = is_merge_left; + l_prev_total_combined = l_total_combined; + l_prev_block = l_block; + prev_use_internal_buf = use_internal_buf; + } + BOOST_ASSERT(l_prev_total_combined == l_data); + bool const buffer_right = prev_use_internal_buf && prev_merge_left; + l_intbuf = prev_use_internal_buf ? l_prev_block : 0u; + n_keys = l_unique - l_intbuf; + //Restore data from to external common buffer if used + if(common_xbuf){ + if(buffer_right){ + boost::move(xbuf.data(), xbuf.data() + l_intbuf, buffer+l_data); + } + else{ + boost::move(xbuf.data(), xbuf.data() + l_intbuf, buffer); + } + } + return buffer_right; +} + +template<class RandIt, class Compare> +void stable_merge + ( RandIt first, RandIt const middle, RandIt last + , Compare comp + , adaptive_xbuf<typename iterator_traits<RandIt>::value_type> &xbuf) +{ + BOOST_ASSERT(xbuf.empty()); + 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); + size_type const l_min = min_value(len1, len2); + if(xbuf.capacity() >= l_min){ + buffered_merge(first, middle, last, comp, xbuf); + xbuf.clear(); + } + else{ + merge_bufferless(first, middle, last, comp); + } +} + + +template<class RandIt, class Compare> +void 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 + , Compare comp) +{ + BOOST_ASSERT(n_keys || xbuf.size() == l_intbuf); + xbuf.clear(); + + typedef typename iterator_traits<RandIt>::size_type size_type; + size_type const n_key_plus_buf = l_intbuf+n_keys; + if(buffer_right){ + stable_sort(first+len-l_intbuf, first+len, comp, xbuf); + stable_merge(first+n_keys, first+len-l_intbuf, first+len, antistable<Compare>(comp), xbuf); + stable_sort(first, first+n_keys, comp, xbuf); + stable_merge(first, first+n_keys, first+len, comp, xbuf); + } + else{ + stable_sort(first, first+n_key_plus_buf, comp, xbuf); + if(xbuf.capacity() >= n_key_plus_buf){ + buffered_merge(first, first+n_key_plus_buf, first+len, comp, xbuf); + } + else if(xbuf.capacity() >= min_value<size_type>(l_intbuf, n_keys)){ + stable_merge(first+n_keys, first+n_key_plus_buf, first+len, comp, xbuf); + stable_merge(first, first+n_keys, first+len, comp, xbuf); + } + else{ + merge_bufferless(first, first+n_key_plus_buf, first+len, comp); + } + } + BOOST_MOVE_ADAPTIVE_SORT_PRINT(" After final_merge : ", len); +} + +template<class RandIt, class Compare, class Unsigned, class T> +bool 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 + ) +{ + typedef Unsigned size_type; + + //Calculate ideal parameters and try to collect needed unique keys + l_base = 0u; + + //Try to find a value near sqrt(len) that is 2^N*l_base where + //l_base <= AdaptiveSortInsertionSortThreshold. This property is important + //as build_blocks merges to the left iteratively duplicating the + //merged size and all the buffer must be used just before the final + //merge to right step. This guarantees "build_blocks" produces + //segments of size l_build_buf*2, maximizing the classic merge phase. + l_intbuf = size_type(ceil_sqrt_multiple(len, &l_base)); + + //This is the minimum number of case to implement the ideal algorithm + // + //l_intbuf is used as buffer plus the key count + size_type n_min_ideal_keys = l_intbuf-1u; + while(n_min_ideal_keys >= (len-l_intbuf-n_min_ideal_keys)/l_intbuf){ + --n_min_ideal_keys; + } + ++n_min_ideal_keys; + BOOST_ASSERT(n_min_ideal_keys < l_intbuf); + + if(xbuf.template supports_aligned_trailing<size_type>(l_intbuf, n_min_ideal_keys)){ + n_keys = 0u; + l_build_buf = l_intbuf; + } + else{ + //Try to achieve a l_build_buf of length l_intbuf*2, so that we can merge with that + //l_intbuf*2 buffer in "build_blocks" and use half of them as buffer and the other half + //as keys in combine_all_blocks. In that case n_keys >= n_min_ideal_keys but by a small margin. + // + //If available memory is 2*sqrt(l), then only sqrt(l) unique keys are needed, + //(to be used for keys in combine_all_blocks) as the whole l_build_buf + //we'll be backuped in the buffer during build_blocks. + bool const non_unique_buf = xbuf.capacity() >= 2*l_intbuf; + size_type const to_collect = non_unique_buf ? l_intbuf : l_intbuf*2; + size_type collected = collect_unique(first, first+len, to_collect, comp, xbuf); + + //If available memory is 2*sqrt(l), then for "build_params" + //the situation is the same as if 2*l_intbuf were collected. + if(non_unique_buf && (collected >= n_min_ideal_keys)) + collected += l_intbuf; + + //If collected keys are not enough, try to fix n_keys and l_intbuf. If no fix + //is possible (due to very low unique keys), then go to a slow sort based on rotations. + if(collected < (n_min_ideal_keys+l_intbuf)){ + if(collected < 4){ //No combination possible with less that 4 keys + return false; + } + n_keys = l_intbuf; + while(n_keys&(n_keys-1)){ + n_keys &= n_keys-1; // make it power or 2 + } + while(n_keys > collected){ + n_keys/=2; + } + l_base = min_value<Unsigned>(n_keys, AdaptiveSortInsertionSortThreshold); + l_intbuf = 0; + l_build_buf = n_keys; + } + else if((collected - l_intbuf) >= l_intbuf){ + //l_intbuf*2 elements found. Use all of them in the build phase + l_build_buf = l_intbuf*2; + n_keys = l_intbuf; + } + else{ + l_build_buf = l_intbuf; + n_keys = n_min_ideal_keys; + } + BOOST_ASSERT((n_keys+l_intbuf) >= l_build_buf); + } + + return true; +} + +template<class RandIt, class Compare> +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 + ) +{ + typedef typename iterator_traits<RandIt>::size_type size_type; + + //Small sorts go directly to insertion sort + if(len <= size_type(AdaptiveSortInsertionSortThreshold)){ + insertion_sort(first, first + len, comp); + return; + } + + if((len-len/2) <= xbuf.capacity()){ + merge_sort(first, first+len, comp, xbuf.data()); + return; + } + + //Make sure it is at least two + BOOST_STATIC_ASSERT(AdaptiveSortInsertionSortThreshold >= 4); + + size_type l_base = 0; + size_type l_intbuf = 0; + size_type n_keys = 0; + size_type l_build_buf = 0; + + if(!build_params(first, len, comp, n_keys, l_intbuf, l_base, l_build_buf, xbuf)){ + stable_sort(first, first+len, comp, xbuf); + return; + } + + //Otherwise, continue in adaptive_sort + BOOST_MOVE_ADAPTIVE_SORT_PRINT("\n After collect_unique: ", len); + size_type const n_key_plus_buf = l_intbuf+n_keys; + //l_build_buf is always power of two if l_intbuf is zero + BOOST_ASSERT(l_intbuf || (0 == (l_build_buf & (l_build_buf-1)))); + + //Classic merge sort until internal buffer and xbuf are exhausted + size_type const l_merged = build_blocks + (first+n_key_plus_buf-l_build_buf, len-n_key_plus_buf+l_build_buf, l_base, l_build_buf, xbuf, comp); + BOOST_MOVE_ADAPTIVE_SORT_PRINT(" After build_blocks: ", len); + + //Non-trivial merge + bool const buffer_right = combine_all_blocks + (first, n_keys, first+n_keys, len-n_keys, l_merged, l_intbuf, xbuf, comp); + + //Sort keys and buffer and merge the whole sequence + final_merge(buffer_right, first, l_intbuf, n_keys, len, xbuf, comp); +} + +template<class RandIt, class Compare> +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 + ) +{ + typedef typename iterator_traits<RandIt>::size_type size_type; + + if(xbuf.capacity() >= min_value<size_type>(len1, len2)){ + buffered_merge(first, first+len1, first+(len1+len2), comp, xbuf); + } + else{ + const size_type len = len1+len2; + //Calculate ideal parameters and try to collect needed unique keys + size_type l_block = size_type(ceil_sqrt(len)); + + if(len1 <= l_block*2 || len2 <= l_block*2){ + merge_bufferless(first, first+len1, first+len1+len2, comp); + return; + } + + size_type l_intbuf = xbuf.capacity() >= l_block ? 0u : l_block; + + //This is the minimum number of case to implement the ideal algorithm + //ceil(len/l_block) - 1 (as the first block is used as buffer) + size_type n_keys = l_block; + while(n_keys >= (len-l_intbuf-n_keys)/l_block){ + --n_keys; + } + ++n_keys; + BOOST_ASSERT(n_keys < l_block); + + if(xbuf.template supports_aligned_trailing<size_type>(l_block, n_keys)){ + n_keys = 0u; + } + + size_type const to_collect = l_intbuf+n_keys; + size_type const collected = collect_unique(first, first+len1, to_collect, comp, xbuf); + + BOOST_MOVE_ADAPTIVE_SORT_PRINT("\n A collect: ", len); + if(collected != to_collect && collected < 4){ + merge_bufferless(first, first+len1, first+len1+len2, comp); + } + else{ + bool use_internal_buf = true; + if (collected != to_collect){ + l_intbuf = 0u; + n_keys = collected; + use_internal_buf = false; + l_block = lblock_for_combine(l_intbuf, n_keys, len, use_internal_buf); + l_intbuf = use_internal_buf ? l_block : 0u; + } + + bool xbuf_used = collected == to_collect && xbuf.capacity() >= l_block; + size_type const l_combine = len-collected; + size_type const l_combine1 = len1-collected; + + size_type n_bef_irreg2, n_aft_irreg2, l_irreg1, l_irreg2, midkey_idx; + if(n_keys){ + RandIt const first_data = first+collected; + RandIt const keys = first; + combine_params( keys, comp, first_data, l_combine + , l_combine1, l_block, xbuf, comp + , midkey_idx, l_irreg1, n_bef_irreg2, n_aft_irreg2, l_irreg2, true); //Outputs + BOOST_MOVE_ADAPTIVE_SORT_PRINT(" A combine: ", len); + if(xbuf_used){ + merge_blocks_with_buf + (keys, keys[midkey_idx], comp, first_data, l_block, l_irreg1, n_bef_irreg2, n_aft_irreg2, l_irreg2, comp, xbuf, xbuf_used); + BOOST_MOVE_ADAPTIVE_SORT_PRINT(" A mrg xbf: ", len); + } + else if(use_internal_buf){ + #define BOOST_MOVE_ADAPTIVE_MERGE_WITH_BUF + #ifdef BOOST_MOVE_ADAPTIVE_MERGE_WITH_BUF + range_xbuf<RandIt, swap_op> rbuf(first_data-l_block, first_data); + merge_blocks_with_buf + (keys, keys[midkey_idx], comp, first_data, l_block, l_irreg1, n_bef_irreg2, n_aft_irreg2, l_irreg2, comp, rbuf, xbuf_used); + BOOST_MOVE_ADAPTIVE_SORT_PRINT(" A mrg buf: ", len); + #else + merge_blocks_left + (keys, keys[midkey_idx], comp, first_data, l_block, l_irreg1, n_bef_irreg2, n_aft_irreg2, l_irreg2, comp, xbuf_used); + BOOST_MOVE_ADAPTIVE_SORT_PRINT(" A mrg lft: ", len); + #endif + } + else{ + merge_blocks_bufferless + (keys, keys[midkey_idx], comp, first_data, l_block, l_irreg1, n_bef_irreg2, n_aft_irreg2, l_irreg2, comp); + BOOST_MOVE_ADAPTIVE_SORT_PRINT(" A mrg bfl: ", len); + } + } + else{ + xbuf.clear(); + size_type *const uint_keys = xbuf.template aligned_trailing<size_type>(l_block); + combine_params( uint_keys, less(), first, l_combine + , l_combine1, l_block, xbuf, comp + , midkey_idx, l_irreg1, n_bef_irreg2, n_aft_irreg2, l_irreg2, true); //Outputs + BOOST_MOVE_ADAPTIVE_SORT_PRINT(" A combine: ", len); + merge_blocks_with_buf + (uint_keys, uint_keys[midkey_idx], less(), first, l_block, l_irreg1, n_bef_irreg2, n_aft_irreg2, l_irreg2, comp, xbuf, true); + xbuf.clear(); + BOOST_MOVE_ADAPTIVE_SORT_PRINT(" A mrg lft: ", len); + } + + n_keys = collected-l_intbuf; + if(use_internal_buf){ + if(xbuf_used){ + xbuf.clear(); + //Nothing to do + if(n_keys){ + stable_sort(first, first+n_keys, comp, xbuf); + stable_merge(first, first+n_keys, first+len, comp, xbuf); + } + } + else{ + #ifdef BOOST_MOVE_ADAPTIVE_MERGE_WITH_BUF + xbuf.clear(); + stable_sort(first, first+collected, comp, xbuf); + stable_merge(first, first+collected, first+len, comp, xbuf); + #else + xbuf.clear(); + stable_sort(first+len-l_block, first+len, comp, xbuf); + RandIt const pos1 = lower_bound(first+n_keys, first+len-l_block, first[len-1], comp); + RandIt const pos2 = rotate_gcd(pos1, first+len-l_block, first+len); + stable_merge(first+n_keys, pos1, pos2, antistable<Compare>(comp), xbuf); + if(n_keys){ + stable_sort(first, first+n_keys, comp, xbuf); + stable_merge(first, first+n_keys, first+len, comp, xbuf); + } + #endif + } + + BOOST_MOVE_ADAPTIVE_SORT_PRINT(" A buf mrg: ", len); + } + else{ + stable_sort(first, first+collected, comp, xbuf); + xbuf.clear(); + if(xbuf.capacity() >= collected){ + buffered_merge(first, first+collected, first+len1+len2, comp, xbuf); + } + else{ + merge_bufferless(first, first+collected, first+len1+len2, comp); + } + } + BOOST_MOVE_ADAPTIVE_SORT_PRINT(" A key mrg: ", len); + } + } +} + +} //namespace detail_adaptive { +} //namespace movelib { +} //namespace boost { + +#include <boost/move/detail/config_end.hpp> + +#endif //#define BOOST_MOVE_ADAPTIVE_SORT_MERGE_HPP diff --git a/boost/move/algo/detail/basic_op.hpp b/boost/move/algo/detail/basic_op.hpp new file mode 100644 index 0000000000..936f7a2a3d --- /dev/null +++ b/boost/move/algo/detail/basic_op.hpp @@ -0,0 +1,63 @@ +////////////////////////////////////////////////////////////////////////////// +// +// (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_BASIC_OP +#define BOOST_MOVE_ALGO_BASIC_OP + +#ifndef BOOST_CONFIG_HPP +# include <boost/config.hpp> +#endif +# +#if defined(BOOST_HAS_PRAGMA_ONCE) +# pragma once +#endif + +#include <boost/move/utility_core.hpp> +#include <boost/move/adl_move_swap.hpp> + +namespace boost { +namespace movelib { + +struct forward_t{}; +struct backward_t{}; + +struct move_op +{ + template <class SourceIt, class DestinationIt> + 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) + { return ::boost::move(first, last, dest_begin); } + + template <class SourceIt, class DestinationIt> + DestinationIt operator()(backward_t, SourceIt first, SourceIt last, DestinationIt dest_last) + { return ::boost::move_backward(first, last, dest_last); } +}; + +struct swap_op +{ + template <class SourceIt, class DestinationIt> + 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) + { 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) + { return boost::adl_move_swap_ranges_backward(first, last, dest_begin); } +}; + +}} //namespace boost::movelib + +#endif //BOOST_MOVE_ALGO_BASIC_OP diff --git a/boost/move/algo/detail/bufferless_merge_sort.hpp b/boost/move/algo/detail/bufferless_merge_sort.hpp new file mode 100644 index 0000000000..a8e2763d7c --- /dev/null +++ b/boost/move/algo/detail/bufferless_merge_sort.hpp @@ -0,0 +1,120 @@ +////////////////////////////////////////////////////////////////////////////// +// +// (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. +// +////////////////////////////////////////////////////////////////////////////// + +//! \file + +#ifndef BOOST_MOVE_ALGO_BUFFERLESS_MERGE_SORT_HPP +#define BOOST_MOVE_ALGO_BUFFERLESS_MERGE_SORT_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/utility_core.hpp> +#include <boost/move/adl_move_swap.hpp> + +#include <boost/move/algo/move.hpp> +#include <boost/move/algo/detail/merge.hpp> + +#include <boost/move/detail/iterator_traits.hpp> +#include <boost/move/algo/detail/insertion_sort.hpp> +#include <cassert> + +namespace boost { +namespace movelib { +// @cond +namespace detail_bufferless_mergesort { + +static const std::size_t UnbufferedMergeSortInsertionSortThreshold = 16; + +//A in-placed version based on: +//Jyrki Katajainen, Tomi Pasanen, Jukka Teuhola. +//``Practical in-place mergesort''. Nordic Journal of Computing, 1996. + +template<class RandIt, class Compare> +void bufferless_merge_sort(RandIt first, RandIt last, Compare comp); + +template<class RandIt, class Compare> +void swap_sort(RandIt const first, RandIt const last, RandIt const buffer_first, RandIt const buffer_last, Compare comp, bool buffer_at_right) +{ + typedef typename iterator_traits<RandIt>::size_type size_type; + if (size_type(last - first) > UnbufferedMergeSortInsertionSortThreshold) { + RandIt m = first + (last - first) / 2; + bufferless_merge_sort(first, m, comp); + bufferless_merge_sort(m, last, comp); + if(buffer_at_right){ + //Use antistable to minimize movements (if equal, move first half elements + //to maximize the chance last half elements are already in place. + boost::movelib::swap_merge_right(first, m, last, buffer_last, boost::movelib::antistable<Compare>(comp)); + } + else{ + boost::movelib::swap_merge_left(buffer_first, first, m, last, comp); + } + } + else + boost::movelib::insertion_sort_swap(first, last, buffer_first, comp); +} + +template<class RandIt, class Compare> +void bufferless_merge_sort(RandIt const first, RandIt const last, Compare comp) +{ + typedef typename iterator_traits<RandIt>::size_type size_type; + size_type len = size_type(last - first); + if (len > size_type(UnbufferedMergeSortInsertionSortThreshold)) { + len /= 2; + RandIt h = last - len; //ceil(half) + RandIt f = h - len; //ceil(first) + swap_sort(f, h, h, last, comp, true); //[h, last) contains sorted elements + + //Divide unsorted first half in two + len = size_type(h - first); + while (len > size_type(UnbufferedMergeSortInsertionSortThreshold)) { + len /= 2; + RandIt n = h; //new end + h = n - len; //ceil(half') + f = h - len; //ceil(first') + swap_sort(h, n, f, h, comp, false); // the first half of the previous working area [f, h) + //contains sorted elements: working area in the middle [h, n) + //Now merge small (left) sorted with big (right) sorted (buffer is between them) + swap_merge_with_right_placed(f, h, h, n, last, comp); + } + + boost::movelib::insertion_sort(first, h, comp); + boost::movelib::merge_bufferless(first, h, last, comp); + } + else{ + boost::movelib::insertion_sort(first, last, comp); + } +} + +} //namespace detail_bufferless_mergesort { + +// @endcond + +//Unstable bufferless merge sort +template<class RandIt, class Compare> +void bufferless_merge_sort(RandIt first, RandIt last, Compare comp) +{ + detail_bufferless_mergesort::bufferless_merge_sort(first, last, comp); +} + +}} //namespace boost::movelib + +#include <boost/move/detail/config_end.hpp> + +#endif //#ifndef BOOST_MOVE_ALGO_BUFFERLESS_MERGE_SORT_HPP diff --git a/boost/move/algo/detail/insertion_sort.hpp b/boost/move/algo/detail/insertion_sort.hpp new file mode 100644 index 0000000000..15df35d9d6 --- /dev/null +++ b/boost/move/algo/detail/insertion_sort.hpp @@ -0,0 +1,127 @@ +////////////////////////////////////////////////////////////////////////////// +// +// (C) Copyright Ion Gaztanaga 2014-2014. +// 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. +// +////////////////////////////////////////////////////////////////////////////// + +//! \file + +#ifndef BOOST_MOVE_DETAIL_INSERT_SORT_HPP +#define BOOST_MOVE_DETAIL_INSERT_SORT_HPP + +#ifndef BOOST_CONFIG_HPP +# include <boost/config.hpp> +#endif +# +#if defined(BOOST_HAS_PRAGMA_ONCE) +# pragma once +#endif + +#include <boost/move/utility_core.hpp> +#include <boost/move/algo/move.hpp> +#include <boost/move/detail/iterator_traits.hpp> +#include <boost/move/adl_move_swap.hpp> +#include <boost/move/utility_core.hpp> +#include <boost/move/detail/placement_new.hpp> +#include <boost/move/detail/destruct_n.hpp> +#include <boost/move/algo/detail/basic_op.hpp> +#include <boost/move/detail/placement_new.hpp> + +namespace boost { namespace movelib{ + +// @cond + +template <class Compare, class ForwardIterator, class BirdirectionalIterator, class Op> +void insertion_sort_op(ForwardIterator first1, ForwardIterator last1, BirdirectionalIterator first2, Compare comp, Op op) +{ + if (first1 != last1){ + BirdirectionalIterator last2 = first2; + op(first1, last2); + for (++last2; ++first1 != last1; ++last2){ + BirdirectionalIterator j2 = last2; + BirdirectionalIterator i2 = j2; + if (comp(*first1, *--i2)){ + op(i2, j2); + for (--j2; i2 != first2 && comp(*first1, *--i2); --j2) { + op(i2, j2); + } + } + op(first1, j2); + } + } +} + +template <class Compare, class ForwardIterator, class BirdirectionalIterator> +void insertion_sort_swap(ForwardIterator first1, ForwardIterator last1, BirdirectionalIterator first2, Compare comp) +{ + insertion_sort_op(first1, last1, first2, comp, swap_op()); +} + + +template <class Compare, class ForwardIterator, class BirdirectionalIterator> +void insertion_sort_copy(ForwardIterator first1, ForwardIterator last1, BirdirectionalIterator first2, Compare comp) +{ + insertion_sort_op(first1, last1, first2, comp, move_op()); +} + +// @endcond + +template <class Compare, class BirdirectionalIterator> +void insertion_sort(BirdirectionalIterator first, BirdirectionalIterator last, Compare comp) +{ + typedef typename boost::movelib::iterator_traits<BirdirectionalIterator>::value_type value_type; + if (first != last){ + BirdirectionalIterator i = first; + for (++i; i != last; ++i){ + BirdirectionalIterator j = i; + if (comp(*i, *--j)) { + value_type tmp(::boost::move(*i)); + *i = ::boost::move(*j); + for (BirdirectionalIterator k = j; k != first && comp(tmp, *--k); --j) { + *j = ::boost::move(*k); + } + *j = ::boost::move(tmp); + } + } + } +} + +template <class Compare, class BirdirectionalIterator> +void insertion_sort_uninitialized_copy + (BirdirectionalIterator first1, BirdirectionalIterator const last1 + , typename iterator_traits<BirdirectionalIterator>::value_type* 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); + d.incr(); + for (++last2; ++first1 != last1; ++last2){ + value_type* j2 = last2; + value_type* k2 = j2; + if (comp(*first1, *--k2)){ + ::new(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)); + d.incr(); + } + } + d.release(); + } +} + +}} //namespace boost { namespace movelib{ + +#endif //#ifndef BOOST_MOVE_DETAIL_INSERT_SORT_HPP diff --git a/boost/move/algo/detail/merge.hpp b/boost/move/algo/detail/merge.hpp new file mode 100644 index 0000000000..a0a5afa3e6 --- /dev/null +++ b/boost/move/algo/detail/merge.hpp @@ -0,0 +1,444 @@ +////////////////////////////////////////////////////////////////////////////// +// +// (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_MERGE_HPP +#define BOOST_MOVE_MERGE_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 { + +// @cond + +/* +template<typename Unsigned> +inline Unsigned gcd(Unsigned x, Unsigned y) +{ + if(0 == ((x &(x-1)) | (y & (y-1)))){ + return x < y ? x : y; + } + else{ + do + { + Unsigned t = x % y; + x = y; + y = t; + } while (y); + return x; + } +} +*/ + +//Modified version from "An Optimal In-Place Array Rotation Algorithm", Ching-Kuang Shene +template<typename Unsigned> +Unsigned gcd(Unsigned x, Unsigned y) +{ + if(0 == ((x &(x-1)) | (y & (y-1)))){ + return x < y ? x : y; + } + else{ + Unsigned z = 1; + while((!(x&1)) & (!(y&1))){ + z <<=1, x>>=1, y>>=1; + } + while(x && y){ + if(!(x&1)) + x >>=1; + else if(!(y&1)) + y >>=1; + else if(x >=y) + x = (x-y) >> 1; + else + y = (y-x) >> 1; + } + return z*(x+y); + } +} + +template<typename RandIt> +RandIt rotate_gcd(RandIt first, RandIt middle, RandIt last) +{ + typedef typename iterator_traits<RandIt>::size_type size_type; + typedef typename iterator_traits<RandIt>::value_type value_type; + + if(first == middle) + return last; + if(middle == last) + return first; + const size_type middle_pos = size_type(middle - first); + RandIt ret = last - middle_pos; + if (middle == ret){ + boost::adl_move_swap_ranges(first, middle, middle); + } + else{ + const size_type length = size_type(last - first); + for( RandIt it_i(first), it_gcd(it_i + gcd(length, middle_pos)) + ; it_i != it_gcd + ; ++it_i){ + value_type temp(boost::move(*it_i)); + RandIt it_j = it_i; + RandIt it_k = it_j+middle_pos; + do{ + *it_j = boost::move(*it_k); + it_j = it_k; + size_type const left = size_type(last - it_j); + it_k = left > middle_pos ? it_j + middle_pos : first + (middle_pos - left); + } while(it_k != it_i); + *it_j = boost::move(temp); + } + } + return ret; +} + +template <class RandIt, class T, class Compare> +RandIt lower_bound + (RandIt first, const RandIt last, const T& key, Compare comp) +{ + typedef typename iterator_traits + <RandIt>::size_type size_type; + size_type len = size_type(last - first); + RandIt middle; + + while (len) { + size_type step = len >> 1; + middle = first; + middle += step; + + if (comp(*middle, key)) { + first = ++middle; + len -= step + 1; + } + else{ + len = step; + } + } + return first; +} + +template <class RandIt, class T, class Compare> +RandIt upper_bound + (RandIt first, const RandIt last, const T& key, Compare comp) +{ + typedef typename iterator_traits + <RandIt>::size_type size_type; + size_type len = size_type(last - first); + RandIt middle; + + while (len) { + size_type step = len >> 1; + middle = first; + middle += step; + + if (!comp(key, *middle)) { + first = ++middle; + len -= step + 1; + } + else{ + len = step; + } + } + return first; +} + + +template<class RandIt, class Compare, class Op> +void op_merge_left( RandIt buf_first + , RandIt first1 + , RandIt const last1 + , RandIt const last2 + , Compare comp + , Op op) +{ + for(RandIt first2=last1; first2 != last2; ++buf_first){ + if(first1 == last1){ + op(forward_t(), first2, last2, buf_first); + return; + } + else if(comp(*first2, *first1)){ + op(first2, buf_first); + ++first2; + } + else{ + op(first1, buf_first); + ++first1; + } + } + if(buf_first != first1){//In case all remaining elements are in the same place + //(e.g. buffer is exactly the size of the second half + //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 +// [first1, last1) merge [last1,last2) -> [buf_first,buf_first+(last2-first1)) +// Elements from buffer are moved to [last2 - (first1-buf_first), last2) +// Note: distance(buf_first, first1) >= distance(last1, last2), so no overlapping occurs +template<class RandIt, class Compare> +void merge_left + (RandIt buf_first, RandIt first1, RandIt const last1, RandIt const last2, Compare comp) +{ + op_merge_left(buf_first, first1, last1, last2, comp, move_op()); +} + +// [buf_first, first1) -> buffer +// [first1, last1) merge [last1,last2) -> [buf_first,buf_first+(last2-first1)) +// Elements from buffer are swapped to [last2 - (first1-buf_first), last2) +// Note: distance(buf_first, first1) >= distance(last1, last2), so no overlapping occurs +template<class RandIt, class Compare> +void swap_merge_left + (RandIt buf_first, RandIt first1, RandIt const last1, RandIt const last2, Compare comp) +{ + op_merge_left(buf_first, first1, last1, last2, comp, swap_op()); +} + +template<class RandIt, class Compare, class Op> +void op_merge_right + (RandIt const first1, RandIt last1, RandIt last2, RandIt buf_last, Compare comp, Op op) +{ + RandIt const first2 = last1; + while(first1 != last1){ + if(last2 == first2){ + op(backward_t(), first1, last1, buf_last); + return; + } + --last2; + --last1; + --buf_last; + if(comp(*last2, *last1)){ + op(last1, buf_last); + ++last2; + } + else{ + op(last2, buf_last); + ++last1; + } + } + if(last2 != buf_last){ //In case all remaining elements are in the same place + //(e.g. buffer is exactly the size of the first half + //and all elements from the second half are less) + op(backward_t(), first2, last2, buf_last); + } +} + +// [last2, buf_last) - buffer +// [first1, last1) merge [last1,last2) -> [first1+(buf_last-last2), buf_last) +// Note: distance[last2, buf_last) >= distance[first1, last1), so no overlapping occurs +template<class RandIt, class Compare> +void merge_right + (RandIt first1, RandIt last1, RandIt last2, RandIt buf_last, Compare comp) +{ + op_merge_right(first1, last1, last2, buf_last, comp, move_op()); +} + +// [last2, buf_last) - buffer +// [first1, last1) merge [last1,last2) -> [first1+(buf_last-last2), buf_last) +// Note: distance[last2, buf_last) >= distance[first1, last1), so no overlapping occurs +template<class RandIt, class Compare> +void swap_merge_right + (RandIt first1, RandIt last1, RandIt last2, RandIt buf_last, Compare comp) +{ + op_merge_right(first1, last1, last2, buf_last, comp, swap_op()); +} + +// cost: min(L1,L2)^2+max(L1,L2) +template<class RandIt, class Compare> +void merge_bufferless(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); + first = rotate_gcd(first, old_last1, middle); + if(middle == last){ + break; + } + do{ + ++first; + } while(first != middle && !comp(*middle, *first)); + } + } + else{ + while(middle != last){ + RandIt p = upper_bound(first, middle, last[-1], comp); + last = rotate_gcd(p, middle, last); + middle = p; + if(middle == first){ + break; + } + --p; + do{ + --last; + } while(middle != last && !comp(last[-1], *p)); + } + } +} + +template<class Comp> +struct antistable +{ + 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; +}; + +// [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 + ( InputIterator first, InputIterator last + , InputOutIterator dest_first, InputOutIterator r_first, InputOutIterator r_last + , Compare comp, Op op) +{ + BOOST_ASSERT((last - first) == (r_first - dest_first)); + while ( first != last ) { + if (r_first == r_last) { + InputOutIterator end = op(forward_t(), first, last, dest_first); + BOOST_ASSERT(end == r_last); + (void)end; + return; + } + else if (comp(*r_first, *first)) { + op(r_first, dest_first); + ++r_first; + } + else { + op(first, dest_first); + ++first; + } + ++dest_first; + } + // Remaining [r_first, r_last) already in the correct place +} + +template <class Compare, class InputIterator, class InputOutIterator> +void swap_merge_with_right_placed + ( InputIterator first, InputIterator last + , InputOutIterator dest_first, InputOutIterator r_first, InputOutIterator r_last + , Compare comp) +{ + op_merge_with_right_placed(first, last, dest_first, r_first, r_last, comp, swap_op()); +} + +// [r_first, r_last) are already in the right part of the destination range. +template <class Compare, class Op, class BidirIterator, class BidirOutIterator> +void op_merge_with_left_placed + ( BidirOutIterator const first, BidirOutIterator last, BidirOutIterator dest_last + , BidirIterator const r_first, BidirIterator r_last + , Compare comp, Op op) +{ + BOOST_ASSERT((dest_last - last) == (r_last - r_first)); + while( r_first != r_last ) { + if(first == last) { + BidirOutIterator res = op(backward_t(), r_first, r_last, dest_last); + BOOST_ASSERT(last == res); + (void)res; + return; + } + --r_last; + --last; + if(comp(*r_last, *last)){ + ++r_last; + --dest_last; + op(last, dest_last); + } + else{ + ++last; + --dest_last; + op(r_last, dest_last); + } + } + // Remaining [first, last) already in the correct place +} + +// @endcond + +// [r_first, r_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 + , BidirIterator const r_first, BidirIterator r_last + , Compare comp) +{ + op_merge_with_left_placed(first, last, dest_last, r_first, r_last, comp, move_op()); +} + +// [r_first, r_last) are already in the right part of the destination range. +template <class Compare, class InputIterator, class InputOutIterator> +void merge_with_right_placed + ( InputIterator first, InputIterator last + , InputOutIterator dest_first, InputOutIterator r_first, InputOutIterator r_last + , Compare comp) +{ + op_merge_with_right_placed(first, last, dest_first, r_first, r_last, comp, move_op()); +} + +// [r_first, r_last) are already in the right part of the destination range. +// [dest_first, r_first) is uninitialized memory +template <class Compare, class InputIterator, class InputOutIterator> +void uninitialized_merge_with_right_placed + ( InputIterator first, InputIterator last + , InputOutIterator dest_first, InputOutIterator r_first, InputOutIterator r_last + , Compare comp) +{ + BOOST_ASSERT((last - first) == (r_first - dest_first)); + typedef typename iterator_traits<InputOutIterator>::value_type value_type; + InputOutIterator const original_r_first = r_first; + + destruct_n<value_type> 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)); + d.incr(); + } + d.release(); + InputOutIterator end = ::boost::move(first, last, original_r_first); + BOOST_ASSERT(end == r_last); + (void)end; + return; + } + else if (comp(*r_first, *first)) { + ::new(&*dest_first) value_type(::boost::move(*r_first)); + d.incr(); + ++r_first; + } + else { + ::new(&*dest_first) value_type(::boost::move(*first)); + d.incr(); + ++first; + } + ++dest_first; + } + d.release(); + merge_with_right_placed(first, last, original_r_first, r_first, r_last, comp); +} + +} //namespace movelib { +} //namespace boost { + +#endif //#define BOOST_MOVE_MERGE_HPP diff --git a/boost/move/algo/detail/merge_sort.hpp b/boost/move/algo/detail/merge_sort.hpp new file mode 100644 index 0000000000..8101fce654 --- /dev/null +++ b/boost/move/algo/detail/merge_sort.hpp @@ -0,0 +1,124 @@ +////////////////////////////////////////////////////////////////////////////// +// +// (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. +// +////////////////////////////////////////////////////////////////////////////// + +//! \file + +#ifndef BOOST_MOVE_DETAIL_MERGE_SORT_HPP +#define BOOST_MOVE_DETAIL_MERGE_SORT_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/utility_core.hpp> +#include <boost/move/algo/move.hpp> +#include <boost/move/algo/detail/merge.hpp> +#include <boost/move/detail/iterator_traits.hpp> +#include <boost/move/adl_move_swap.hpp> +#include <boost/move/detail/destruct_n.hpp> +#include <boost/move/algo/detail/insertion_sort.hpp> +#include <cassert> + +namespace boost { +namespace movelib { + +// @cond + +static const unsigned MergeSortInsertionSortThreshold = 16; + +// @endcond + +template<class RandIt, class RandIt2, class Compare> +void merge_sort_copy( RandIt first, RandIt last + , RandIt2 dest, Compare comp) +{ + typedef typename iterator_traits<RandIt>::size_type size_type; + + size_type const count = size_type(last - first); + if(count <= MergeSortInsertionSortThreshold){ + insertion_sort_copy(first, last, dest, comp); + } + else{ + size_type const half = count/2; + merge_sort_copy(first + half, last , dest+half , comp); + merge_sort_copy(first , first + half, first + half, comp); + merge_with_right_placed + ( first + half, first + half + half + , dest, dest+half, dest + count + , comp); + } +} + +template<class RandIt, class Compare> +void merge_sort_uninitialized_copy( RandIt first, RandIt last + , typename iterator_traits<RandIt>::value_type* uninitialized + , Compare comp) +{ + typedef typename iterator_traits<RandIt>::size_type size_type; + typedef typename iterator_traits<RandIt>::value_type value_type; + + size_type const count = size_type(last - first); + if(count <= MergeSortInsertionSortThreshold){ + insertion_sort_uninitialized_copy(first, last, uninitialized, comp); + } + else{ + size_type const half = count/2; + merge_sort_uninitialized_copy(first + half, last, uninitialized + half, comp); + destruct_n<value_type> d(uninitialized+half); + d.incr(count-half); + merge_sort_copy(first, first + half, first + half, comp); + uninitialized_merge_with_right_placed + ( first + half, first + half + half + , uninitialized, uninitialized+half, uninitialized+count + , comp); + d.release(); + } +} + +template<class RandIt, class Compare> +void merge_sort( RandIt first, RandIt last, Compare comp + , typename iterator_traits<RandIt>::value_type* uninitialized) +{ + typedef typename iterator_traits<RandIt>::size_type size_type; + typedef typename iterator_traits<RandIt>::value_type value_type; + + size_type const count = size_type(last - first); + if(count <= MergeSortInsertionSortThreshold){ + insertion_sort(first, last, comp); + } + else{ + size_type const half = count/2; + size_type const rest = count - half; + RandIt const half_it = first + half; + RandIt const rest_it = first + rest; + + merge_sort_uninitialized_copy(half_it, last, uninitialized, comp); + destruct_n<value_type> d(uninitialized); + d.incr(rest); + merge_sort_copy(first, half_it, rest_it, comp); + merge_with_right_placed + ( uninitialized, uninitialized + rest + , first, rest_it, last, antistable<Compare>(comp)); + } +} + +}} //namespace boost { namespace movelib{ + +#include <boost/move/detail/config_end.hpp> + +#endif //#ifndef BOOST_MOVE_DETAIL_MERGE_SORT_HPP diff --git a/boost/move/algo/move.hpp b/boost/move/algo/move.hpp new file mode 100644 index 0000000000..943f286c94 --- /dev/null +++ b/boost/move/algo/move.hpp @@ -0,0 +1,155 @@ +////////////////////////////////////////////////////////////////////////////// +// +// (C) Copyright Ion Gaztanaga 2012-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. +// +////////////////////////////////////////////////////////////////////////////// + +//! \file + +#ifndef BOOST_MOVE_ALGO_MOVE_HPP +#define BOOST_MOVE_ALGO_MOVE_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/utility_core.hpp> +#include <boost/move/detail/iterator_traits.hpp> +#include <boost/detail/no_exceptions_support.hpp> + +namespace boost { + +////////////////////////////////////////////////////////////////////////////// +// +// move +// +////////////////////////////////////////////////////////////////////////////// + +#if !defined(BOOST_MOVE_USE_STANDARD_LIBRARY_MOVE) + + //! <b>Effects</b>: Moves elements in the range [first,last) into the range [result,result + (last - + //! first)) starting from first and proceeding to last. For each non-negative integer n < (last-first), + //! performs *(result + n) = ::boost::move (*(first + n)). + //! + //! <b>Effects</b>: result + (last - first). + //! + //! <b>Requires</b>: result shall not be in the range [first,last). + //! + //! <b>Complexity</b>: Exactly last - first move assignments. + template <typename I, // I models InputIterator + typename O> // O models OutputIterator + O move(I f, I l, O result) + { + while (f != l) { + *result = ::boost::move(*f); + ++f; ++result; + } + return result; + } + + ////////////////////////////////////////////////////////////////////////////// + // + // move_backward + // + ////////////////////////////////////////////////////////////////////////////// + + //! <b>Effects</b>: Moves elements in the range [first,last) into the range + //! [result - (last-first),result) starting from last - 1 and proceeding to + //! first. For each positive integer n <= (last - first), + //! performs *(result - n) = ::boost::move(*(last - n)). + //! + //! <b>Requires</b>: result shall not be in the range [first,last). + //! + //! <b>Returns</b>: result - (last - first). + //! + //! <b>Complexity</b>: Exactly last - first assignments. + template <typename I, // I models BidirectionalIterator + typename O> // O models BidirectionalIterator + O move_backward(I f, I l, O result) + { + while (f != l) { + --l; --result; + *result = ::boost::move(*l); + } + return result; + } + +#else + + using ::std::move_backward; + +#endif //!defined(BOOST_MOVE_USE_STANDARD_LIBRARY_MOVE) + +////////////////////////////////////////////////////////////////////////////// +// +// uninitialized_move +// +////////////////////////////////////////////////////////////////////////////// + +//! <b>Effects</b>: +//! \code +//! for (; first != last; ++result, ++first) +//! new (static_cast<void*>(&*result)) +//! typename iterator_traits<ForwardIterator>::value_type(boost::move(*first)); +//! \endcode +//! +//! <b>Returns</b>: result +template + <typename I, // I models InputIterator + typename F> // F models ForwardIterator +F uninitialized_move(I f, I l, F r + /// @cond +// ,typename ::boost::move_detail::enable_if<has_move_emulation_enabled<typename boost::movelib::iterator_traits<I>::value_type> >::type* = 0 + /// @endcond + ) +{ + typedef typename boost::movelib::iterator_traits<I>::value_type input_value_type; + + F back = r; + BOOST_TRY{ + while (f != l) { + void * const addr = static_cast<void*>(::boost::move_detail::addressof(*r)); + ::new(addr) input_value_type(::boost::move(*f)); + ++f; ++r; + } + } + BOOST_CATCH(...){ + for (; back != r; ++back){ + back->~input_value_type(); + } + BOOST_RETHROW; + } + BOOST_CATCH_END + return r; +} + +/// @cond +/* +template + <typename I, // I models InputIterator + typename F> // F models ForwardIterator +F uninitialized_move(I f, I l, F r, + typename ::boost::move_detail::disable_if<has_move_emulation_enabled<typename boost::movelib::iterator_traits<I>::value_type> >::type* = 0) +{ + return std::uninitialized_copy(f, l, r); +} +*/ + +/// @endcond + +} //namespace boost { + +#include <boost/move/detail/config_end.hpp> + +#endif //#ifndef BOOST_MOVE_ALGO_MOVE_HPP diff --git a/boost/move/algorithm.hpp b/boost/move/algorithm.hpp index fbda0f40d1..825d7716c2 100644 --- a/boost/move/algorithm.hpp +++ b/boost/move/algorithm.hpp @@ -26,6 +26,7 @@ #include <boost/move/utility_core.hpp> #include <boost/move/iterator.hpp> +#include <boost/move/algo/move.hpp> #include <boost/detail/no_exceptions_support.hpp> #include <algorithm> //copy, copy_backward @@ -35,122 +36,6 @@ namespace boost { ////////////////////////////////////////////////////////////////////////////// // -// move -// -////////////////////////////////////////////////////////////////////////////// - -#if !defined(BOOST_MOVE_USE_STANDARD_LIBRARY_MOVE) - - //! <b>Effects</b>: Moves elements in the range [first,last) into the range [result,result + (last - - //! first)) starting from first and proceeding to last. For each non-negative integer n < (last-first), - //! performs *(result + n) = ::boost::move (*(first + n)). - //! - //! <b>Effects</b>: result + (last - first). - //! - //! <b>Requires</b>: result shall not be in the range [first,last). - //! - //! <b>Complexity</b>: Exactly last - first move assignments. - template <typename I, // I models InputIterator - typename O> // O models OutputIterator - O move(I f, I l, O result) - { - while (f != l) { - *result = ::boost::move(*f); - ++f; ++result; - } - return result; - } - - ////////////////////////////////////////////////////////////////////////////// - // - // move_backward - // - ////////////////////////////////////////////////////////////////////////////// - - //! <b>Effects</b>: Moves elements in the range [first,last) into the range - //! [result - (last-first),result) starting from last - 1 and proceeding to - //! first. For each positive integer n <= (last - first), - //! performs *(result - n) = ::boost::move(*(last - n)). - //! - //! <b>Requires</b>: result shall not be in the range [first,last). - //! - //! <b>Returns</b>: result - (last - first). - //! - //! <b>Complexity</b>: Exactly last - first assignments. - template <typename I, // I models BidirectionalIterator - typename O> // O models BidirectionalIterator - O move_backward(I f, I l, O result) - { - while (f != l) { - --l; --result; - *result = ::boost::move(*l); - } - return result; - } - -#else - - using ::std::move_backward; - -#endif //!defined(BOOST_MOVE_USE_STANDARD_LIBRARY_MOVE) - -////////////////////////////////////////////////////////////////////////////// -// -// uninitialized_move -// -////////////////////////////////////////////////////////////////////////////// - -//! <b>Effects</b>: -//! \code -//! for (; first != last; ++result, ++first) -//! new (static_cast<void*>(&*result)) -//! typename iterator_traits<ForwardIterator>::value_type(boost::move(*first)); -//! \endcode -//! -//! <b>Returns</b>: result -template - <typename I, // I models InputIterator - typename F> // F models ForwardIterator -F uninitialized_move(I f, I l, F r - /// @cond -// ,typename ::boost::move_detail::enable_if<has_move_emulation_enabled<typename std::iterator_traits<I>::value_type> >::type* = 0 - /// @endcond - ) -{ - typedef typename std::iterator_traits<I>::value_type input_value_type; - - F back = r; - BOOST_TRY{ - while (f != l) { - void * const addr = static_cast<void*>(::boost::move_detail::addressof(*r)); - ::new(addr) input_value_type(::boost::move(*f)); - ++f; ++r; - } - } - BOOST_CATCH(...){ - for (; back != r; ++back){ - back->~input_value_type(); - } - BOOST_RETHROW; - } - BOOST_CATCH_END - return r; -} - -/// @cond -/* -template - <typename I, // I models InputIterator - typename F> // F models ForwardIterator -F uninitialized_move(I f, I l, F r, - typename ::boost::move_detail::disable_if<has_move_emulation_enabled<typename std::iterator_traits<I>::value_type> >::type* = 0) -{ - return std::uninitialized_copy(f, l, r); -} -*/ - -////////////////////////////////////////////////////////////////////////////// -// // uninitialized_copy_or_move // ////////////////////////////////////////////////////////////////////////////// diff --git a/boost/move/core.hpp b/boost/move/core.hpp index 54aece0b71..c9cbec23a1 100644 --- a/boost/move/core.hpp +++ b/boost/move/core.hpp @@ -197,7 +197,7 @@ namespace move_detail { template <class Ret, class T> - inline typename ::boost::move_detail::enable_if_c + BOOST_MOVE_FORCEINLINE typename ::boost::move_detail::enable_if_c < ::boost::move_detail::is_lvalue_reference<Ret>::value || !::boost::has_move_emulation_enabled<T>::value , T&>::type @@ -207,7 +207,7 @@ } template <class Ret, class T> - inline typename ::boost::move_detail::enable_if_c + BOOST_MOVE_FORCEINLINE typename ::boost::move_detail::enable_if_c < !::boost::move_detail::is_lvalue_reference<Ret>::value && ::boost::has_move_emulation_enabled<T>::value , ::boost::rv<T>&>::type @@ -217,7 +217,7 @@ } template <class Ret, class T> - inline typename ::boost::move_detail::enable_if_c + BOOST_MOVE_FORCEINLINE typename ::boost::move_detail::enable_if_c < !::boost::move_detail::is_lvalue_reference<Ret>::value && ::boost::has_move_emulation_enabled<T>::value , ::boost::rv<T>&>::type @@ -245,9 +245,9 @@ #define BOOST_MOVABLE_BUT_NOT_COPYABLE(TYPE)\ BOOST_MOVE_IMPL_NO_COPY_CTOR_OR_ASSIGN(TYPE)\ public:\ - operator ::boost::rv<TYPE>&() \ + BOOST_MOVE_FORCEINLINE operator ::boost::rv<TYPE>&() \ { return *BOOST_MOVE_TO_RV_CAST(::boost::rv<TYPE>*, this); }\ - operator const ::boost::rv<TYPE>&() const \ + BOOST_MOVE_FORCEINLINE operator const ::boost::rv<TYPE>&() const \ { return *BOOST_MOVE_TO_RV_CAST(const ::boost::rv<TYPE>*, this); }\ private:\ // @@ -263,18 +263,18 @@ TYPE& operator=(TYPE &t)\ { this->operator=(const_cast<const TYPE &>(t)); return *this;}\ public:\ - operator ::boost::rv<TYPE>&() \ + BOOST_MOVE_FORCEINLINE operator ::boost::rv<TYPE>&() \ { return *BOOST_MOVE_TO_RV_CAST(::boost::rv<TYPE>*, this); }\ - operator const ::boost::rv<TYPE>&() const \ + BOOST_MOVE_FORCEINLINE operator const ::boost::rv<TYPE>&() const \ { return *BOOST_MOVE_TO_RV_CAST(const ::boost::rv<TYPE>*, this); }\ private:\ // #define BOOST_COPYABLE_AND_MOVABLE_ALT(TYPE)\ public:\ - operator ::boost::rv<TYPE>&() \ + BOOST_MOVE_FORCEINLINE operator ::boost::rv<TYPE>&() \ { return *BOOST_MOVE_TO_RV_CAST(::boost::rv<TYPE>*, this); }\ - operator const ::boost::rv<TYPE>&() const \ + BOOST_MOVE_FORCEINLINE operator const ::boost::rv<TYPE>&() const \ { return *BOOST_MOVE_TO_RV_CAST(const ::boost::rv<TYPE>*, this); }\ private:\ // @@ -301,6 +301,7 @@ BOOST_MOVE_IMPL_NO_COPY_CTOR_OR_ASSIGN(TYPE)\ public:\ typedef int boost_move_emulation_t;\ + private:\ // //! This macro marks a type as copyable and movable. @@ -450,7 +451,7 @@ namespace move_detail { template <class Ret, class T> - inline typename ::boost::move_detail::enable_if_c + BOOST_MOVE_FORCEINLINE typename ::boost::move_detail::enable_if_c < ::boost::move_detail::is_lvalue_reference<Ret>::value , T&>::type move_return(T& x) BOOST_NOEXCEPT @@ -459,7 +460,7 @@ } template <class Ret, class T> - inline typename ::boost::move_detail::enable_if_c + BOOST_MOVE_FORCEINLINE typename ::boost::move_detail::enable_if_c < !::boost::move_detail::is_lvalue_reference<Ret>::value , Ret && >::type move_return(T&& t) BOOST_NOEXCEPT diff --git a/boost/move/detail/config_begin.hpp b/boost/move/detail/config_begin.hpp index 342390b816..637eb158bd 100644 --- a/boost/move/detail/config_begin.hpp +++ b/boost/move/detail/config_begin.hpp @@ -16,4 +16,6 @@ # pragma warning (disable : 4324) // structure was padded due to __declspec(align()) # pragma warning (disable : 4675) // "function": resolved overload was found by argument-dependent lookup # pragma warning (disable : 4996) // "function": was declared deprecated (_CRT_SECURE_NO_DEPRECATE/_SCL_SECURE_NO_WARNINGS) +# pragma warning (disable : 4714) // "function": marked as __forceinline not inlined +# pragma warning (disable : 4127) // conditional expression is constant #endif diff --git a/boost/move/detail/destruct_n.hpp b/boost/move/detail/destruct_n.hpp new file mode 100644 index 0000000000..06f1f589ed --- /dev/null +++ b/boost/move/detail/destruct_n.hpp @@ -0,0 +1,67 @@ +////////////////////////////////////////////////////////////////////////////// +// +// (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. +// +////////////////////////////////////////////////////////////////////////////// + +//! \file + +#ifndef BOOST_MOVE_DETAIL_DESTRUCT_N_HPP +#define BOOST_MOVE_DETAIL_DESTRUCT_N_HPP + +#ifndef BOOST_CONFIG_HPP +# include <boost/config.hpp> +#endif +# +#if defined(BOOST_HAS_PRAGMA_ONCE) +# pragma once +#endif + +#include <cstddef> + +namespace boost { +namespace movelib{ + +template<class T> +class destruct_n +{ + public: + explicit destruct_n(T *raw) + : m_ptr(raw), m_size() + {} + + void incr() + { + ++m_size; + } + + void incr(std::size_t n) + { + m_size += n; + } + + void release() + { + m_size = 0u; + m_ptr = 0; + } + + ~destruct_n() + { + while(m_size--){ + m_ptr[m_size].~T(); + } + } + private: + T *m_ptr; + std::size_t m_size; +}; + +}} //namespace boost { namespace movelib{ + +#endif //#ifndef BOOST_MOVE_DETAIL_DESTRUCT_N_HPP diff --git a/boost/move/detail/iterator_traits.hpp b/boost/move/detail/iterator_traits.hpp index a75ee03827..5ffcb2cf05 100644 --- a/boost/move/detail/iterator_traits.hpp +++ b/boost/move/detail/iterator_traits.hpp @@ -23,6 +23,7 @@ #endif #include <cstddef> +#include <boost/move/detail/type_traits.hpp> #include <boost/move/detail/std_ns_begin.hpp> BOOST_MOVE_STD_NS_BEG @@ -46,6 +47,7 @@ struct iterator_traits typedef typename Iterator::pointer pointer; typedef typename Iterator::reference reference; typedef typename Iterator::iterator_category iterator_category; + typedef typename boost::move_detail::make_unsigned<difference_type>::type size_type; }; template<class T> @@ -56,6 +58,7 @@ struct iterator_traits<T*> typedef T* pointer; typedef T& reference; typedef std::random_access_iterator_tag iterator_category; + typedef typename boost::move_detail::make_unsigned<difference_type>::type size_type; }; template<class T> @@ -66,6 +69,7 @@ struct iterator_traits<const T*> typedef const T* pointer; typedef const T& reference; typedef std::random_access_iterator_tag iterator_category; + typedef typename boost::move_detail::make_unsigned<difference_type>::type size_type; }; }} //namespace boost { namespace movelib{ diff --git a/boost/move/detail/meta_utils.hpp b/boost/move/detail/meta_utils.hpp index 323c13af10..e45394c97d 100644 --- a/boost/move/detail/meta_utils.hpp +++ b/boost/move/detail/meta_utils.hpp @@ -14,13 +14,11 @@ #ifndef BOOST_MOVE_DETAIL_META_UTILS_HPP #define BOOST_MOVE_DETAIL_META_UTILS_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> //forceinline #include <boost/move/detail/meta_utils_core.hpp> #include <cstddef> //for std::size_t @@ -245,8 +243,8 @@ template<class T> struct addr_impl_ref { T & v_; - inline addr_impl_ref( T & v ): v_( v ) {} - inline operator T& () const { return v_; } + BOOST_MOVE_FORCEINLINE addr_impl_ref( T & v ): v_( v ) {} + BOOST_MOVE_FORCEINLINE operator T& () const { return v_; } private: addr_impl_ref & operator=(const addr_impl_ref &); @@ -255,18 +253,18 @@ struct addr_impl_ref template<class T> struct addressof_impl { - static inline T * f( T & v, long ) + BOOST_MOVE_FORCEINLINE static T * f( T & v, long ) { return reinterpret_cast<T*>( &const_cast<char&>(reinterpret_cast<const volatile char &>(v))); } - static inline T * f( T * v, int ) + BOOST_MOVE_FORCEINLINE static T * f( T * v, int ) { return v; } }; template<class T> -inline T * addressof( T & v ) +BOOST_MOVE_FORCEINLINE T * addressof( T & v ) { return ::boost::move_detail::addressof_impl<T>::f ( ::boost::move_detail::addr_impl_ref<T>( v ), 0 ); @@ -314,6 +312,17 @@ class is_convertible #endif +template <class T, class U, bool IsSame = is_same<T, U>::value> +struct is_same_or_convertible + : is_convertible<T, U> +{}; + +template <class T, class U> +struct is_same_or_convertible<T, U, true> +{ + static const bool value = true; +}; + template< bool C , typename F1 @@ -347,6 +356,16 @@ struct disable_if_convertible : disable_if< is_convertible<T, U>, R> {}; +template<class T, class U, class R = void> +struct enable_if_same_or_convertible + : enable_if< is_same_or_convertible<T, U>, R> +{}; + +template<class T, class U, class R = void> +struct disable_if_same_or_convertible + : disable_if< is_same_or_convertible<T, U>, R> +{}; + ////////////////////////////////////////////////////////////////////////////// // // and_ @@ -561,4 +580,6 @@ template< class T > struct remove_rvalue_reference { typedef T type; }; } //namespace move_detail { } //namespace boost { +#include <boost/move/detail/config_end.hpp> + #endif //#ifndef BOOST_MOVE_DETAIL_META_UTILS_HPP diff --git a/boost/move/detail/move_helpers.hpp b/boost/move/detail/move_helpers.hpp index 7b62e26994..a2502bf7dc 100644 --- a/boost/move/detail/move_helpers.hpp +++ b/boost/move/detail/move_helpers.hpp @@ -1,6 +1,6 @@ ////////////////////////////////////////////////////////////////////////////// // -// (C) Copyright Ion Gaztanaga 2010-2012. +// (C) Copyright Ion Gaztanaga 2010-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) @@ -20,8 +20,9 @@ # pragma once #endif +#include <boost/move/core.hpp> #include <boost/move/utility_core.hpp> -#include <boost/move/detail/meta_utils.hpp> +#include <boost/move/detail/type_traits.hpp> #if defined(BOOST_NO_CXX11_RVALUE_REFERENCES) @@ -43,6 +44,30 @@ //////////////////////////////////////// #ifdef BOOST_NO_CXX11_RVALUE_REFERENCES + + template<class RETURN_VALUE, class BOOST_MOVE_TEMPL_PARAM, class TYPE> + struct boost_move_conversion_aware_catch_1 + : public ::boost::move_detail::enable_if_and + < RETURN_VALUE + , ::boost::move_detail::is_same<TYPE, BOOST_MOVE_TEMPL_PARAM> + , ::boost::move_detail::is_class<TYPE> + , ::boost::has_move_emulation_disabled<BOOST_MOVE_TEMPL_PARAM> + > + {}; + + template<class RETURN_VALUE, class BOOST_MOVE_TEMPL_PARAM, class TYPE> + struct boost_move_conversion_aware_catch_2 + : public ::boost::move_detail::disable_if_or + < RETURN_VALUE + , ::boost::move_detail::is_same<TYPE, BOOST_MOVE_TEMPL_PARAM> + , ::boost::move_detail::is_rv_impl<BOOST_MOVE_TEMPL_PARAM> + , ::boost::move_detail::and_ + < ::boost::move_detail::is_rv_impl<BOOST_MOVE_TEMPL_PARAM> + , ::boost::move_detail::is_class<BOOST_MOVE_TEMPL_PARAM> + > + > + {}; + #define BOOST_MOVE_CONVERSION_AWARE_CATCH_COMMON(PUB_FUNCTION, TYPE, RETURN_VALUE, FWD_FUNCTION)\ RETURN_VALUE PUB_FUNCTION(BOOST_MOVE_CATCH_CONST(TYPE) x)\ { return FWD_FUNCTION(static_cast<const TYPE&>(x)); }\ @@ -59,26 +84,14 @@ \ template<class BOOST_MOVE_TEMPL_PARAM>\ RETURN_VALUE PUB_FUNCTION(const BOOST_MOVE_TEMPL_PARAM &u,\ - typename ::boost::move_detail::enable_if_and\ - < ::boost::move_detail::nat \ - , ::boost::move_detail::is_same<TYPE, BOOST_MOVE_TEMPL_PARAM>\ - , ::boost::move_detail::is_class<TYPE>\ - , ::boost::has_move_emulation_disabled<BOOST_MOVE_TEMPL_PARAM>\ - >::type* = 0)\ + typename boost_move_conversion_aware_catch_1< ::boost::move_detail::nat, BOOST_MOVE_TEMPL_PARAM, TYPE>::type* = 0)\ { return FWD_FUNCTION(u); }\ \ template<class BOOST_MOVE_TEMPL_PARAM>\ RETURN_VALUE PUB_FUNCTION(const BOOST_MOVE_TEMPL_PARAM &u,\ - typename ::boost::move_detail::disable_if_or\ - < ::boost::move_detail::nat \ - , ::boost::move_detail::is_same<TYPE, BOOST_MOVE_TEMPL_PARAM> \ - , ::boost::move_detail::and_ \ - < ::boost::move_detail::is_rv<BOOST_MOVE_TEMPL_PARAM> \ - , ::boost::move_detail::is_class<BOOST_MOVE_TEMPL_PARAM> \ - > \ - >::type* = 0)\ + typename boost_move_conversion_aware_catch_2< ::boost::move_detail::nat, BOOST_MOVE_TEMPL_PARAM, TYPE>::type* = 0)\ {\ - TYPE t(u);\ + TYPE t((u));\ return FWD_FUNCTION(::boost::move(t));\ }\ // @@ -87,27 +100,15 @@ BOOST_MOVE_CONVERSION_AWARE_CATCH_COMMON(PUB_FUNCTION, TYPE, RETURN_VALUE, FWD_FUNCTION)\ \ template<class BOOST_MOVE_TEMPL_PARAM>\ - typename ::boost::move_detail::enable_if_and\ - < RETURN_VALUE \ - , ::boost::move_detail::is_same<TYPE, BOOST_MOVE_TEMPL_PARAM>\ - , ::boost::move_detail::is_class<TYPE>\ - , ::boost::has_move_emulation_disabled<BOOST_MOVE_TEMPL_PARAM>\ - >::type\ + typename boost_move_conversion_aware_catch_1<RETURN_VALUE, BOOST_MOVE_TEMPL_PARAM, TYPE>::type\ PUB_FUNCTION(const BOOST_MOVE_TEMPL_PARAM &u)\ { return FWD_FUNCTION(u); }\ \ template<class BOOST_MOVE_TEMPL_PARAM>\ - typename ::boost::move_detail::disable_if_or\ - < RETURN_VALUE \ - , ::boost::move_detail::is_same<TYPE, BOOST_MOVE_TEMPL_PARAM> \ - , ::boost::move_detail::and_ \ - < ::boost::move_detail::is_rv<BOOST_MOVE_TEMPL_PARAM> \ - , ::boost::move_detail::is_class<BOOST_MOVE_TEMPL_PARAM> \ - > \ - >::type\ + typename boost_move_conversion_aware_catch_2<RETURN_VALUE, BOOST_MOVE_TEMPL_PARAM, TYPE>::type\ PUB_FUNCTION(const BOOST_MOVE_TEMPL_PARAM &u)\ {\ - TYPE t(u);\ + TYPE t((u));\ return FWD_FUNCTION(::boost::move(t));\ }\ // @@ -127,7 +128,7 @@ , RETURN_VALUE >::type\ PUB_FUNCTION(const BOOST_MOVE_TEMPL_PARAM &u)\ {\ - TYPE t(u);\ + TYPE t((u));\ return FWD_FUNCTION(::boost::move(t));\ }\ // @@ -151,6 +152,27 @@ //////////////////////////////////////// #ifdef BOOST_NO_CXX11_RVALUE_REFERENCES + + template<class RETURN_VALUE, class BOOST_MOVE_TEMPL_PARAM, class UNLESS_CONVERTIBLE_TO, class TYPE> + struct boost_move_conversion_aware_catch_1arg_1 + : public ::boost::move_detail::enable_if_and + < RETURN_VALUE + , ::boost::move_detail::not_< ::boost::move_detail::is_same_or_convertible<BOOST_MOVE_TEMPL_PARAM, UNLESS_CONVERTIBLE_TO> > + , ::boost::move_detail::is_same<TYPE, BOOST_MOVE_TEMPL_PARAM> + , ::boost::has_move_emulation_disabled<BOOST_MOVE_TEMPL_PARAM> + > + {}; + + template<class RETURN_VALUE, class BOOST_MOVE_TEMPL_PARAM, class UNLESS_CONVERTIBLE_TO, class TYPE> + struct boost_move_conversion_aware_catch_1arg_2 + : public ::boost::move_detail::disable_if_or + < RETURN_VALUE + , ::boost::move_detail::is_same_or_convertible< BOOST_MOVE_TEMPL_PARAM, UNLESS_CONVERTIBLE_TO> + , ::boost::move_detail::is_rv_impl<BOOST_MOVE_TEMPL_PARAM> + , ::boost::move_detail::is_same<TYPE, BOOST_MOVE_TEMPL_PARAM> + > + {}; + #define BOOST_MOVE_CONVERSION_AWARE_CATCH_1ARG_COMMON(PUB_FUNCTION, TYPE, RETURN_VALUE, FWD_FUNCTION, ARG1, UNLESS_CONVERTIBLE_TO)\ RETURN_VALUE PUB_FUNCTION(ARG1 arg1, BOOST_MOVE_CATCH_CONST(TYPE) x)\ { return FWD_FUNCTION(arg1, static_cast<const TYPE&>(x)); }\ @@ -167,23 +189,14 @@ \ template<class BOOST_MOVE_TEMPL_PARAM>\ RETURN_VALUE PUB_FUNCTION(ARG1 arg1, const BOOST_MOVE_TEMPL_PARAM &u,\ - typename ::boost::move_detail::enable_if_and\ - < ::boost::move_detail::nat \ - , ::boost::move_detail::is_same<TYPE, BOOST_MOVE_TEMPL_PARAM>\ - , ::boost::has_move_emulation_disabled<BOOST_MOVE_TEMPL_PARAM>\ - >::type* = 0)\ + typename boost_move_conversion_aware_catch_1arg_1<void, BOOST_MOVE_TEMPL_PARAM, UNLESS_CONVERTIBLE_TO, TYPE>::type* = 0)\ { return FWD_FUNCTION(arg1, u); }\ \ template<class BOOST_MOVE_TEMPL_PARAM>\ RETURN_VALUE PUB_FUNCTION(ARG1 arg1, const BOOST_MOVE_TEMPL_PARAM &u,\ - typename ::boost::move_detail::disable_if_or\ - < void \ - , ::boost::move_detail::is_rv<BOOST_MOVE_TEMPL_PARAM>\ - , ::boost::move_detail::is_same<TYPE, BOOST_MOVE_TEMPL_PARAM>\ - , ::boost::move_detail::is_convertible<BOOST_MOVE_TEMPL_PARAM, UNLESS_CONVERTIBLE_TO>\ - >::type* = 0)\ + typename boost_move_conversion_aware_catch_1arg_2<void, BOOST_MOVE_TEMPL_PARAM, UNLESS_CONVERTIBLE_TO, TYPE>::type* = 0)\ {\ - TYPE t(u);\ + TYPE t((u));\ return FWD_FUNCTION(arg1, ::boost::move(t));\ }\ // @@ -192,24 +205,15 @@ BOOST_MOVE_CONVERSION_AWARE_CATCH_1ARG_COMMON(PUB_FUNCTION, TYPE, RETURN_VALUE, FWD_FUNCTION, ARG1, UNLESS_CONVERTIBLE_TO)\ \ template<class BOOST_MOVE_TEMPL_PARAM>\ - typename ::boost::move_detail::enable_if_and\ - < RETURN_VALUE \ - , ::boost::move_detail::is_same<TYPE, BOOST_MOVE_TEMPL_PARAM>\ - , ::boost::has_move_emulation_disabled<BOOST_MOVE_TEMPL_PARAM>\ - >::type\ + typename boost_move_conversion_aware_catch_1arg_1<RETURN_VALUE, BOOST_MOVE_TEMPL_PARAM, UNLESS_CONVERTIBLE_TO, TYPE>::type\ PUB_FUNCTION(ARG1 arg1, const BOOST_MOVE_TEMPL_PARAM &u)\ { return FWD_FUNCTION(arg1, u); }\ \ template<class BOOST_MOVE_TEMPL_PARAM>\ - typename ::boost::move_detail::disable_if_or\ - < RETURN_VALUE \ - , ::boost::move_detail::is_rv<BOOST_MOVE_TEMPL_PARAM>\ - , ::boost::move_detail::is_same<TYPE, BOOST_MOVE_TEMPL_PARAM>\ - , ::boost::move_detail::is_convertible<BOOST_MOVE_TEMPL_PARAM, UNLESS_CONVERTIBLE_TO>\ - >::type\ + typename boost_move_conversion_aware_catch_1arg_2<RETURN_VALUE, BOOST_MOVE_TEMPL_PARAM, UNLESS_CONVERTIBLE_TO, TYPE>::type\ PUB_FUNCTION(ARG1 arg1, const BOOST_MOVE_TEMPL_PARAM &u)\ {\ - TYPE t(u);\ + TYPE t((u));\ return FWD_FUNCTION(arg1, ::boost::move(t));\ }\ // @@ -228,11 +232,11 @@ typename ::boost::move_detail::disable_if_or\ < RETURN_VALUE \ , ::boost::move_detail::is_same<TYPE, BOOST_MOVE_TEMPL_PARAM> \ - , ::boost::move_detail::is_convertible<BOOST_MOVE_TEMPL_PARAM, UNLESS_CONVERTIBLE_TO> \ + , ::boost::move_detail::is_same_or_convertible<BOOST_MOVE_TEMPL_PARAM, UNLESS_CONVERTIBLE_TO> \ >::type\ PUB_FUNCTION(ARG1 arg1, const BOOST_MOVE_TEMPL_PARAM &u)\ {\ - TYPE t(u);\ + TYPE t((u));\ return FWD_FUNCTION(arg1, ::boost::move(t));\ }\ // diff --git a/boost/move/detail/placement_new.hpp b/boost/move/detail/placement_new.hpp new file mode 100644 index 0000000000..69d33328cf --- /dev/null +++ b/boost/move/detail/placement_new.hpp @@ -0,0 +1,30 @@ +#ifndef BOOST_MOVE_DETAIL_PLACEMENT_NEW_HPP +#define BOOST_MOVE_DETAIL_PLACEMENT_NEW_HPP +/////////////////////////////////////////////////////////////////////////////// +// +// (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_CONFIG_HPP +# include <boost/config.hpp> +#endif + +#if defined(BOOST_HAS_PRAGMA_ONCE) +# pragma once +#endif + +struct boost_move_new_t{}; + +//avoid including <new> +inline void *operator new(std::size_t, void *p, boost_move_new_t) +{ return p; } + +inline void operator delete(void *, void *, boost_move_new_t) +{} + +#endif //BOOST_MOVE_DETAIL_PLACEMENT_NEW_HPP diff --git a/boost/move/detail/workaround.hpp b/boost/move/detail/workaround.hpp index b3f81b117f..befe141e96 100644 --- a/boost/move/detail/workaround.hpp +++ b/boost/move/detail/workaround.hpp @@ -52,4 +52,17 @@ #define BOOST_MOVE_MSVC_AUTO_MOVE_RETURN_BUG #endif +#define BOOST_MOVE_DISABLE_FORCEINLINE + +#if defined(BOOST_MOVE_DISABLE_FORCEINLINE) + #define BOOST_MOVE_FORCEINLINE inline +#elif defined(BOOST_MOVE_FORCEINLINE_IS_BOOST_FORCELINE) + #define BOOST_MOVE_FORCEINLINE BOOST_FORCEINLINE +#elif defined(BOOST_MSVC) && defined(_DEBUG) + //"__forceinline" and MSVC seems to have some bugs in debug mode + #define BOOST_MOVE_FORCEINLINE inline +#else + #define BOOST_MOVE_FORCEINLINE BOOST_FORCEINLINE +#endif + #endif //#ifndef BOOST_MOVE_DETAIL_WORKAROUND_HPP diff --git a/boost/move/iterator.hpp b/boost/move/iterator.hpp index 1b39e267ec..f36df23c0c 100644 --- a/boost/move/iterator.hpp +++ b/boost/move/iterator.hpp @@ -23,6 +23,7 @@ #endif #include <boost/move/detail/config_begin.hpp> +#include <boost/move/detail/workaround.hpp> //forceinline #include <boost/move/detail/iterator_traits.hpp> #include <boost/move/utility_core.hpp> @@ -57,22 +58,20 @@ class move_iterator typedef typename boost::movelib::iterator_traits<iterator_type>::difference_type difference_type; typedef typename boost::movelib::iterator_traits<iterator_type>::iterator_category iterator_category; - move_iterator() + BOOST_MOVE_FORCEINLINE move_iterator() + : m_it() {} - explicit move_iterator(It i) + BOOST_MOVE_FORCEINLINE explicit move_iterator(const It &i) : m_it(i) {} template <class U> - move_iterator(const move_iterator<U>& u) - : m_it(u.base()) + BOOST_MOVE_FORCEINLINE move_iterator(const move_iterator<U>& u) + : m_it(u.m_it) {} - iterator_type base() const - { return m_it; } - - reference operator*() const + BOOST_MOVE_FORCEINLINE reference operator*() const { #if defined(BOOST_NO_CXX11_RVALUE_REFERENCES) || defined(BOOST_MOVE_OLD_RVALUE_REF_BINDING_RULES) return *m_it; @@ -81,34 +80,34 @@ class move_iterator #endif } - pointer operator->() const + BOOST_MOVE_FORCEINLINE pointer operator->() const { return m_it; } - move_iterator& operator++() + BOOST_MOVE_FORCEINLINE move_iterator& operator++() { ++m_it; return *this; } - move_iterator<iterator_type> operator++(int) + BOOST_MOVE_FORCEINLINE move_iterator<iterator_type> operator++(int) { move_iterator<iterator_type> tmp(*this); ++(*this); return tmp; } - move_iterator& operator--() + BOOST_MOVE_FORCEINLINE move_iterator& operator--() { --m_it; return *this; } - move_iterator<iterator_type> operator--(int) + BOOST_MOVE_FORCEINLINE move_iterator<iterator_type> operator--(int) { move_iterator<iterator_type> tmp(*this); --(*this); return tmp; } move_iterator<iterator_type> operator+ (difference_type n) const { return move_iterator<iterator_type>(m_it + n); } - move_iterator& operator+=(difference_type n) + BOOST_MOVE_FORCEINLINE move_iterator& operator+=(difference_type n) { m_it += n; return *this; } - move_iterator<iterator_type> operator- (difference_type n) const + BOOST_MOVE_FORCEINLINE move_iterator<iterator_type> operator- (difference_type n) const { return move_iterator<iterator_type>(m_it - n); } - move_iterator& operator-=(difference_type n) + BOOST_MOVE_FORCEINLINE move_iterator& operator-=(difference_type n) { m_it -= n; return *this; } - reference operator[](difference_type n) const + BOOST_MOVE_FORCEINLINE reference operator[](difference_type n) const { #if defined(BOOST_NO_CXX11_RVALUE_REFERENCES) || defined(BOOST_MOVE_OLD_RVALUE_REF_BINDING_RULES) return m_it[n]; @@ -117,29 +116,29 @@ class move_iterator #endif } - friend bool operator==(const move_iterator& x, const move_iterator& y) - { return x.base() == y.base(); } + BOOST_MOVE_FORCEINLINE friend bool operator==(const move_iterator& x, const move_iterator& y) + { return x.m_it == y.m_it; } - friend bool operator!=(const move_iterator& x, const move_iterator& y) - { return x.base() != y.base(); } + BOOST_MOVE_FORCEINLINE friend bool operator!=(const move_iterator& x, const move_iterator& y) + { return x.m_it != y.m_it; } - friend bool operator< (const move_iterator& x, const move_iterator& y) - { return x.base() < y.base(); } + BOOST_MOVE_FORCEINLINE friend bool operator< (const move_iterator& x, const move_iterator& y) + { return x.m_it < y.m_it; } - friend bool operator<=(const move_iterator& x, const move_iterator& y) - { return x.base() <= y.base(); } + BOOST_MOVE_FORCEINLINE friend bool operator<=(const move_iterator& x, const move_iterator& y) + { return x.m_it <= y.m_it; } - friend bool operator> (const move_iterator& x, const move_iterator& y) - { return x.base() > y.base(); } + BOOST_MOVE_FORCEINLINE friend bool operator> (const move_iterator& x, const move_iterator& y) + { return x.m_it > y.m_it; } - friend bool operator>=(const move_iterator& x, const move_iterator& y) - { return x.base() >= y.base(); } + BOOST_MOVE_FORCEINLINE friend bool operator>=(const move_iterator& x, const move_iterator& y) + { return x.m_it >= y.m_it; } - friend difference_type operator-(const move_iterator& x, const move_iterator& y) - { return x.base() - y.base(); } + BOOST_MOVE_FORCEINLINE friend difference_type operator-(const move_iterator& x, const move_iterator& y) + { return x.m_it - y.m_it; } - friend move_iterator operator+(difference_type n, const move_iterator& x) - { return move_iterator(x.base() + n); } + BOOST_MOVE_FORCEINLINE friend move_iterator operator+(difference_type n, const move_iterator& x) + { return move_iterator(x.m_it + n); } private: It m_it; diff --git a/boost/move/unique_ptr.hpp b/boost/move/unique_ptr.hpp index 5b067436af..2d794e8ed5 100644 --- a/boost/move/unique_ptr.hpp +++ b/boost/move/unique_ptr.hpp @@ -20,7 +20,7 @@ #endif #include <boost/move/detail/config_begin.hpp> -#include <boost/move/detail/workaround.hpp> +#include <boost/move/detail/workaround.hpp> //forceinline #include <boost/move/detail/unique_ptr_meta_utils.hpp> #include <boost/move/default_delete.hpp> #include <boost/move/utility_core.hpp> @@ -93,25 +93,25 @@ struct unique_ptr_data typedef typename deleter_types<D>::del_ref del_ref; typedef typename deleter_types<D>::del_cref del_cref; - unique_ptr_data() BOOST_NOEXCEPT + BOOST_MOVE_FORCEINLINE unique_ptr_data() BOOST_NOEXCEPT : m_p(), d() {} - explicit unique_ptr_data(P p) BOOST_NOEXCEPT + BOOST_MOVE_FORCEINLINE explicit unique_ptr_data(P p) BOOST_NOEXCEPT : m_p(p), d() {} - unique_ptr_data(P p, deleter_arg_type1 d1) BOOST_NOEXCEPT + BOOST_MOVE_FORCEINLINE unique_ptr_data(P p, deleter_arg_type1 d1) BOOST_NOEXCEPT : m_p(p), d(d1) {} template <class U> - unique_ptr_data(P p, BOOST_FWD_REF(U) d1) BOOST_NOEXCEPT + BOOST_MOVE_FORCEINLINE unique_ptr_data(P p, BOOST_FWD_REF(U) d1) BOOST_NOEXCEPT : m_p(p), d(::boost::forward<U>(d1)) {} - del_ref deleter() { return d; } - del_cref deleter() const{ return d; } + BOOST_MOVE_FORCEINLINE del_ref deleter() { return d; } + BOOST_MOVE_FORCEINLINE del_cref deleter() const{ return d; } P m_p; D d; @@ -129,25 +129,25 @@ struct unique_ptr_data<P, D, false> typedef typename deleter_types<D>::del_ref del_ref; typedef typename deleter_types<D>::del_cref del_cref; - unique_ptr_data() BOOST_NOEXCEPT + BOOST_MOVE_FORCEINLINE unique_ptr_data() BOOST_NOEXCEPT : D(), m_p() {} - explicit unique_ptr_data(P p) BOOST_NOEXCEPT + BOOST_MOVE_FORCEINLINE explicit unique_ptr_data(P p) BOOST_NOEXCEPT : D(), m_p(p) {} - unique_ptr_data(P p, deleter_arg_type1 d1) BOOST_NOEXCEPT + BOOST_MOVE_FORCEINLINE unique_ptr_data(P p, deleter_arg_type1 d1) BOOST_NOEXCEPT : D(d1), m_p(p) {} template <class U> - unique_ptr_data(P p, BOOST_FWD_REF(U) d) BOOST_NOEXCEPT + BOOST_MOVE_FORCEINLINE unique_ptr_data(P p, BOOST_FWD_REF(U) d) BOOST_NOEXCEPT : D(::boost::forward<U>(d)), m_p(p) {} - del_ref deleter() BOOST_NOEXCEPT { return static_cast<del_ref>(*this); } - del_cref deleter() const BOOST_NOEXCEPT { return static_cast<del_cref>(*this); } + BOOST_MOVE_FORCEINLINE del_ref deleter() BOOST_NOEXCEPT { return static_cast<del_ref>(*this); } + BOOST_MOVE_FORCEINLINE del_cref deleter() const BOOST_NOEXCEPT { return static_cast<del_cref>(*this); } P m_p; @@ -389,7 +389,7 @@ class unique_ptr //! //! <b>Remarks</b>: If this constructor is instantiated with a pointer type or reference type //! for the template argument D, the program is ill-formed. - BOOST_CONSTEXPR unique_ptr() BOOST_NOEXCEPT + BOOST_MOVE_FORCEINLINE BOOST_CONSTEXPR unique_ptr() BOOST_NOEXCEPT : m_data() { //If this constructor is instantiated with a pointer type or reference type @@ -400,7 +400,7 @@ class unique_ptr //! <b>Effects</b>: Same as <tt>unique_ptr()</tt> (default constructor). //! - BOOST_CONSTEXPR unique_ptr(BOOST_MOVE_DOC0PTR(bmupd::nullptr_type)) BOOST_NOEXCEPT + BOOST_MOVE_FORCEINLINE BOOST_CONSTEXPR unique_ptr(BOOST_MOVE_DOC0PTR(bmupd::nullptr_type)) BOOST_NOEXCEPT : m_data() { //If this constructor is instantiated with a pointer type or reference type @@ -423,7 +423,7 @@ class unique_ptr //! - If T is not an array type and Pointer is implicitly convertible to pointer. //! - If T is an array type and Pointer is a more CV qualified pointer to element_type. template<class Pointer> - explicit unique_ptr(Pointer p + BOOST_MOVE_FORCEINLINE explicit unique_ptr(Pointer p BOOST_MOVE_DOCIGN(BOOST_MOVE_I typename bmupd::enable_up_ptr<T BOOST_MOVE_I Pointer BOOST_MOVE_I pointer>::type* =0) ) BOOST_NOEXCEPT : m_data(p) @@ -461,7 +461,7 @@ class unique_ptr //! - If T is not an array type and Pointer is implicitly convertible to pointer. //! - If T is an array type and Pointer is a more CV qualified pointer to element_type. template<class Pointer> - unique_ptr(Pointer p, BOOST_MOVE_SEEDOC(deleter_arg_type1) d1 + BOOST_MOVE_FORCEINLINE unique_ptr(Pointer p, BOOST_MOVE_SEEDOC(deleter_arg_type1) d1 BOOST_MOVE_DOCIGN(BOOST_MOVE_I typename bmupd::enable_up_ptr<T BOOST_MOVE_I Pointer BOOST_MOVE_I pointer>::type* =0) ) BOOST_NOEXCEPT : m_data(p, d1) @@ -474,7 +474,7 @@ class unique_ptr //! <b>Effects</b>: Same effects as <tt>template<class Pointer> unique_ptr(Pointer p, deleter_arg_type1 d1)</tt> //! and additionally <tt>get() == nullptr</tt> - unique_ptr(BOOST_MOVE_DOC0PTR(bmupd::nullptr_type), BOOST_MOVE_SEEDOC(deleter_arg_type1) d1) BOOST_NOEXCEPT + BOOST_MOVE_FORCEINLINE unique_ptr(BOOST_MOVE_DOC0PTR(bmupd::nullptr_type), BOOST_MOVE_SEEDOC(deleter_arg_type1) d1) BOOST_NOEXCEPT : m_data(pointer(), d1) {} @@ -499,7 +499,7 @@ class unique_ptr //! - If T is not an array type and Pointer is implicitly convertible to pointer. //! - If T is an array type and Pointer is a more CV qualified pointer to element_type. template<class Pointer> - unique_ptr(Pointer p, BOOST_MOVE_SEEDOC(deleter_arg_type2) d2 + BOOST_MOVE_FORCEINLINE unique_ptr(Pointer p, BOOST_MOVE_SEEDOC(deleter_arg_type2) d2 BOOST_MOVE_DOCIGN(BOOST_MOVE_I typename bmupd::enable_up_ptr<T BOOST_MOVE_I Pointer BOOST_MOVE_I pointer>::type* =0) ) BOOST_NOEXCEPT : m_data(p, ::boost::move(d2)) @@ -512,7 +512,7 @@ class unique_ptr //! <b>Effects</b>: Same effects as <tt>template<class Pointer> unique_ptr(Pointer p, deleter_arg_type2 d2)</tt> //! and additionally <tt>get() == nullptr</tt> - unique_ptr(BOOST_MOVE_DOC0PTR(bmupd::nullptr_type), BOOST_MOVE_SEEDOC(deleter_arg_type2) d2) BOOST_NOEXCEPT + BOOST_MOVE_FORCEINLINE unique_ptr(BOOST_MOVE_DOC0PTR(bmupd::nullptr_type), BOOST_MOVE_SEEDOC(deleter_arg_type2) d2) BOOST_NOEXCEPT : m_data(pointer(), ::boost::move(d2)) {} @@ -526,7 +526,7 @@ class unique_ptr //! <b>Postconditions</b>: <tt>get()</tt> yields the value u.get() yielded before the construction. <tt>get_deleter()</tt> //! returns a reference to the stored deleter that was constructed from u.get_deleter(). If D is a //! reference type then <tt>get_deleter()</tt> and <tt>u.get_deleter()</tt> both reference the same lvalue deleter. - unique_ptr(BOOST_RV_REF(unique_ptr) u) BOOST_NOEXCEPT + BOOST_MOVE_FORCEINLINE unique_ptr(BOOST_RV_REF(unique_ptr) u) BOOST_NOEXCEPT : m_data(u.release(), ::boost::move_if_not_lvalue_reference<D>(u.get_deleter())) {} @@ -546,7 +546,7 @@ class unique_ptr //! <b>Postconditions</b>: <tt>get()</tt> yields the value <tt>u.get()</tt> yielded before the construction. <tt>get_deleter()</tt> //! returns a reference to the stored deleter that was constructed from <tt>u.get_deleter()</tt>. template <class U, class E> - unique_ptr( BOOST_RV_REF_BEG_IF_CXX11 unique_ptr<U, E> BOOST_RV_REF_END_IF_CXX11 u + BOOST_MOVE_FORCEINLINE unique_ptr( BOOST_RV_REF_BEG_IF_CXX11 unique_ptr<U, E> BOOST_RV_REF_END_IF_CXX11 u BOOST_MOVE_DOCIGN(BOOST_MOVE_I typename bmupd::enable_up_moveconv_constr<T BOOST_MOVE_I D BOOST_MOVE_I U BOOST_MOVE_I E>::type* =0) ) BOOST_NOEXCEPT : m_data(u.release(), ::boost::move_if_not_lvalue_reference<E>(u.get_deleter())) @@ -629,7 +629,7 @@ class unique_ptr //! <b>Returns</b>: <tt>get()[i]</tt>. //! //! <b>Remarks</b: If T is not an array type, the program is ill-formed. - BOOST_MOVE_DOC1ST(element_type&, typename bmupmu::add_lvalue_reference<element_type>::type) + BOOST_MOVE_FORCEINLINE BOOST_MOVE_DOC1ST(element_type&, typename bmupmu::add_lvalue_reference<element_type>::type) operator[](std::size_t i) const BOOST_NOEXCEPT { BOOST_ASSERT( bmupmu::extent<T>::value == 0 || i < bmupmu::extent<T>::value ); @@ -644,7 +644,7 @@ class unique_ptr //! <b>Note</b>: use typically requires that T be a complete type. //! //! <b>Remarks</b: If T is an array type, the program is ill-formed. - pointer operator->() const BOOST_NOEXCEPT + BOOST_MOVE_FORCEINLINE pointer operator->() const BOOST_NOEXCEPT { BOOST_STATIC_ASSERT((!bmupmu::is_array<T>::value)); BOOST_ASSERT(m_data.m_p); @@ -653,27 +653,27 @@ class unique_ptr //! <b>Returns</b>: The stored pointer. //! - pointer get() const BOOST_NOEXCEPT + BOOST_MOVE_FORCEINLINE pointer get() const BOOST_NOEXCEPT { return m_data.m_p; } //! <b>Returns</b>: A reference to the stored deleter. //! - BOOST_MOVE_DOC1ST(D&, typename bmupmu::add_lvalue_reference<D>::type) + BOOST_MOVE_FORCEINLINE BOOST_MOVE_DOC1ST(D&, typename bmupmu::add_lvalue_reference<D>::type) get_deleter() BOOST_NOEXCEPT { return m_data.deleter(); } //! <b>Returns</b>: A reference to the stored deleter. //! - BOOST_MOVE_DOC1ST(const D&, typename bmupmu::add_const_lvalue_reference<D>::type) + BOOST_MOVE_FORCEINLINE BOOST_MOVE_DOC1ST(const D&, typename bmupmu::add_const_lvalue_reference<D>::type) get_deleter() const BOOST_NOEXCEPT { return m_data.deleter(); } #ifdef BOOST_MOVE_DOXYGEN_INVOKED //! <b>Returns</b>: Returns: get() != nullptr. //! - explicit operator bool + BOOST_MOVE_FORCEINLINE explicit operator bool #else - operator bmupd::explicit_bool_arg + BOOST_MOVE_FORCEINLINE operator bmupd::explicit_bool_arg #endif ()const BOOST_NOEXCEPT { @@ -685,7 +685,7 @@ class unique_ptr //! <b>Postcondition</b>: <tt>get() == nullptr</tt>. //! //! <b>Returns</b>: The value <tt>get()</tt> had at the start of the call to release. - pointer release() BOOST_NOEXCEPT + BOOST_MOVE_FORCEINLINE pointer release() BOOST_NOEXCEPT { const pointer tmp = m_data.m_p; m_data.m_p = pointer(); @@ -748,19 +748,19 @@ class unique_ptr //! <b>Effects</b>: Calls <tt>x.swap(y)</tt>. //! template <class T, class D> -inline void swap(unique_ptr<T, D> &x, unique_ptr<T, D> &y) BOOST_NOEXCEPT +BOOST_MOVE_FORCEINLINE void swap(unique_ptr<T, D> &x, unique_ptr<T, D> &y) BOOST_NOEXCEPT { x.swap(y); } //! <b>Returns</b>: <tt>x.get() == y.get()</tt>. //! template <class T1, class D1, class T2, class D2> -inline bool operator==(const unique_ptr<T1, D1> &x, const unique_ptr<T2, D2> &y) +BOOST_MOVE_FORCEINLINE bool operator==(const unique_ptr<T1, D1> &x, const unique_ptr<T2, D2> &y) { return x.get() == y.get(); } //! <b>Returns</b>: <tt>x.get() != y.get()</tt>. //! template <class T1, class D1, class T2, class D2> -inline bool operator!=(const unique_ptr<T1, D1> &x, const unique_ptr<T2, D2> &y) +BOOST_MOVE_FORCEINLINE bool operator!=(const unique_ptr<T1, D1> &x, const unique_ptr<T2, D2> &y) { return x.get() != y.get(); } //! <b>Returns</b>: x.get() < y.get(). @@ -768,99 +768,99 @@ inline bool operator!=(const unique_ptr<T1, D1> &x, const unique_ptr<T2, D2> &y) //! <b>Remarks</b>: This comparison shall induce a //! strict weak ordering betwen pointers. template <class T1, class D1, class T2, class D2> -inline bool operator<(const unique_ptr<T1, D1> &x, const unique_ptr<T2, D2> &y) +BOOST_MOVE_FORCEINLINE bool operator<(const unique_ptr<T1, D1> &x, const unique_ptr<T2, D2> &y) { return x.get() < y.get(); } //! <b>Returns</b>: !(y < x). //! template <class T1, class D1, class T2, class D2> -inline bool operator<=(const unique_ptr<T1, D1> &x, const unique_ptr<T2, D2> &y) +BOOST_MOVE_FORCEINLINE bool operator<=(const unique_ptr<T1, D1> &x, const unique_ptr<T2, D2> &y) { return !(y < x); } //! <b>Returns</b>: y < x. //! template <class T1, class D1, class T2, class D2> -inline bool operator>(const unique_ptr<T1, D1> &x, const unique_ptr<T2, D2> &y) +BOOST_MOVE_FORCEINLINE bool operator>(const unique_ptr<T1, D1> &x, const unique_ptr<T2, D2> &y) { return y < x; } //! <b>Returns</b>:!(x < y). //! template <class T1, class D1, class T2, class D2> -inline bool operator>=(const unique_ptr<T1, D1> &x, const unique_ptr<T2, D2> &y) +BOOST_MOVE_FORCEINLINE bool operator>=(const unique_ptr<T1, D1> &x, const unique_ptr<T2, D2> &y) { return !(x < y); } //! <b>Returns</b>:!x. //! template <class T, class D> -inline bool operator==(const unique_ptr<T, D> &x, BOOST_MOVE_DOC0PTR(bmupd::nullptr_type)) BOOST_NOEXCEPT +BOOST_MOVE_FORCEINLINE bool operator==(const unique_ptr<T, D> &x, BOOST_MOVE_DOC0PTR(bmupd::nullptr_type)) BOOST_NOEXCEPT { return !x; } //! <b>Returns</b>:!x. //! template <class T, class D> -inline bool operator==(BOOST_MOVE_DOC0PTR(bmupd::nullptr_type), const unique_ptr<T, D> &x) BOOST_NOEXCEPT +BOOST_MOVE_FORCEINLINE bool operator==(BOOST_MOVE_DOC0PTR(bmupd::nullptr_type), const unique_ptr<T, D> &x) BOOST_NOEXCEPT { return !x; } //! <b>Returns</b>: (bool)x. //! template <class T, class D> -inline bool operator!=(const unique_ptr<T, D> &x, BOOST_MOVE_DOC0PTR(bmupd::nullptr_type)) BOOST_NOEXCEPT +BOOST_MOVE_FORCEINLINE bool operator!=(const unique_ptr<T, D> &x, BOOST_MOVE_DOC0PTR(bmupd::nullptr_type)) BOOST_NOEXCEPT { return !!x; } //! <b>Returns</b>: (bool)x. //! template <class T, class D> -inline bool operator!=(BOOST_MOVE_DOC0PTR(bmupd::nullptr_type), const unique_ptr<T, D> &x) BOOST_NOEXCEPT +BOOST_MOVE_FORCEINLINE bool operator!=(BOOST_MOVE_DOC0PTR(bmupd::nullptr_type), const unique_ptr<T, D> &x) BOOST_NOEXCEPT { return !!x; } //! <b>Requires</b>: <tt>operator </tt> shall induce a strict weak ordering on unique_ptr<T, D>::pointer values. //! //! <b>Returns</b>: Returns <tt>x.get() < pointer()</tt>. template <class T, class D> -inline bool operator<(const unique_ptr<T, D> &x, BOOST_MOVE_DOC0PTR(bmupd::nullptr_type)) +BOOST_MOVE_FORCEINLINE bool operator<(const unique_ptr<T, D> &x, BOOST_MOVE_DOC0PTR(bmupd::nullptr_type)) { return x.get() < typename unique_ptr<T, D>::pointer(); } //! <b>Requires</b>: <tt>operator </tt> shall induce a strict weak ordering on unique_ptr<T, D>::pointer values. //! //! <b>Returns</b>: Returns <tt>pointer() < x.get()</tt>. template <class T, class D> -inline bool operator<(BOOST_MOVE_DOC0PTR(bmupd::nullptr_type), const unique_ptr<T, D> &x) +BOOST_MOVE_FORCEINLINE bool operator<(BOOST_MOVE_DOC0PTR(bmupd::nullptr_type), const unique_ptr<T, D> &x) { return typename unique_ptr<T, D>::pointer() < x.get(); } //! <b>Returns</b>: <tt>nullptr < x</tt>. //! template <class T, class D> -inline bool operator>(const unique_ptr<T, D> &x, BOOST_MOVE_DOC0PTR(bmupd::nullptr_type)) +BOOST_MOVE_FORCEINLINE bool operator>(const unique_ptr<T, D> &x, BOOST_MOVE_DOC0PTR(bmupd::nullptr_type)) { return x.get() > typename unique_ptr<T, D>::pointer(); } //! <b>Returns</b>: <tt>x < nullptr</tt>. //! template <class T, class D> -inline bool operator>(BOOST_MOVE_DOC0PTR(bmupd::nullptr_type), const unique_ptr<T, D> &x) +BOOST_MOVE_FORCEINLINE bool operator>(BOOST_MOVE_DOC0PTR(bmupd::nullptr_type), const unique_ptr<T, D> &x) { return typename unique_ptr<T, D>::pointer() > x.get(); } //! <b>Returns</b>: <tt>!(nullptr < x)</tt>. //! template <class T, class D> -inline bool operator<=(const unique_ptr<T, D> &x, BOOST_MOVE_DOC0PTR(bmupd::nullptr_type)) +BOOST_MOVE_FORCEINLINE bool operator<=(const unique_ptr<T, D> &x, BOOST_MOVE_DOC0PTR(bmupd::nullptr_type)) { return !(bmupd::nullptr_type() < x); } //! <b>Returns</b>: <tt>!(x < nullptr)</tt>. //! template <class T, class D> -inline bool operator<=(BOOST_MOVE_DOC0PTR(bmupd::nullptr_type), const unique_ptr<T, D> &x) +BOOST_MOVE_FORCEINLINE bool operator<=(BOOST_MOVE_DOC0PTR(bmupd::nullptr_type), const unique_ptr<T, D> &x) { return !(x < bmupd::nullptr_type()); } //! <b>Returns</b>: <tt>!(x < nullptr)</tt>. //! template <class T, class D> -inline bool operator>=(const unique_ptr<T, D> &x, BOOST_MOVE_DOC0PTR(bmupd::nullptr_type)) +BOOST_MOVE_FORCEINLINE bool operator>=(const unique_ptr<T, D> &x, BOOST_MOVE_DOC0PTR(bmupd::nullptr_type)) { return !(x < bmupd::nullptr_type()); } //! <b>Returns</b>: <tt>!(nullptr < x)</tt>. //! template <class T, class D> -inline bool operator>=(BOOST_MOVE_DOC0PTR(bmupd::nullptr_type), const unique_ptr<T, D> &x) +BOOST_MOVE_FORCEINLINE bool operator>=(BOOST_MOVE_DOC0PTR(bmupd::nullptr_type), const unique_ptr<T, D> &x) { return !(bmupd::nullptr_type() < x); } } //namespace movelib { diff --git a/boost/move/utility.hpp b/boost/move/utility.hpp index 8f9c20b65f..28de7935c8 100644 --- a/boost/move/utility.hpp +++ b/boost/move/utility.hpp @@ -25,6 +25,7 @@ #endif #include <boost/move/detail/config_begin.hpp> +#include <boost/move/detail/workaround.hpp> //forceinline #include <boost/move/utility_core.hpp> #include <boost/move/traits.hpp> @@ -39,7 +40,7 @@ ////////////////////////////////////////////////////////////////////////////// template <class T> - inline typename ::boost::move_detail::enable_if_c + BOOST_MOVE_FORCEINLINE typename ::boost::move_detail::enable_if_c < enable_move_utility_emulation<T>::value && !has_move_emulation_enabled<T>::value , typename ::boost::move_detail::add_const<T>::type & >::type @@ -49,7 +50,7 @@ } template <class T> - inline typename ::boost::move_detail::enable_if_c + BOOST_MOVE_FORCEINLINE typename ::boost::move_detail::enable_if_c < enable_move_utility_emulation<T>::value && has_move_emulation_enabled<T>::value && ::boost::move_detail::is_nothrow_move_constructible_or_uncopyable<T>::value, rv<T>&>::type move_if_noexcept(T& x) BOOST_NOEXCEPT @@ -58,7 +59,7 @@ } template <class T> - inline typename ::boost::move_detail::enable_if_c + BOOST_MOVE_FORCEINLINE typename ::boost::move_detail::enable_if_c < enable_move_utility_emulation<T>::value && has_move_emulation_enabled<T>::value && ::boost::move_detail::is_nothrow_move_constructible_or_uncopyable<T>::value , rv<T>& @@ -69,7 +70,7 @@ } template <class T> - inline typename ::boost::move_detail::enable_if_c + BOOST_MOVE_FORCEINLINE typename ::boost::move_detail::enable_if_c < enable_move_utility_emulation<T>::value && has_move_emulation_enabled<T>::value && !::boost::move_detail::is_nothrow_move_constructible_or_uncopyable<T>::value , typename ::boost::move_detail::add_const<T>::type & @@ -80,7 +81,7 @@ } template <class T> - inline typename ::boost::move_detail::enable_if_c + BOOST_MOVE_FORCEINLINE typename ::boost::move_detail::enable_if_c < enable_move_utility_emulation<T>::value && has_move_emulation_enabled<T>::value && !::boost::move_detail::is_nothrow_move_constructible_or_uncopyable<T>::value , typename ::boost::move_detail::add_const<T>::type & @@ -125,13 +126,13 @@ #else //BOOST_MOVE_DOXYGEN_INVOKED template <class T> - typename ::boost::move_detail::enable_if_c + BOOST_MOVE_FORCEINLINE typename ::boost::move_detail::enable_if_c < ::boost::move_detail::is_nothrow_move_constructible_or_uncopyable<T>::value, T&&>::type move_if_noexcept(T& x) BOOST_NOEXCEPT { return ::boost::move(x); } template <class T> - typename ::boost::move_detail::enable_if_c + BOOST_MOVE_FORCEINLINE typename ::boost::move_detail::enable_if_c < !::boost::move_detail::is_nothrow_move_constructible_or_uncopyable<T>::value, const T&>::type move_if_noexcept(T& x) BOOST_NOEXCEPT { return x; } diff --git a/boost/move/utility_core.hpp b/boost/move/utility_core.hpp index 7fd1ea1443..55042a9bb1 100644 --- a/boost/move/utility_core.hpp +++ b/boost/move/utility_core.hpp @@ -26,6 +26,7 @@ #endif #include <boost/move/detail/config_begin.hpp> +#include <boost/move/detail/workaround.hpp> //forceinline #include <boost/move/core.hpp> #include <boost/move/detail/meta_utils.hpp> #include <boost/static_assert.hpp> @@ -47,7 +48,7 @@ ////////////////////////////////////////////////////////////////////////////// template <class T> - inline typename ::boost::move_detail::enable_if_and + BOOST_MOVE_FORCEINLINE typename ::boost::move_detail::enable_if_and < T & , enable_move_utility_emulation<T> , has_move_emulation_disabled<T> @@ -58,7 +59,7 @@ } template <class T> - inline typename ::boost::move_detail::enable_if_and + BOOST_MOVE_FORCEINLINE typename ::boost::move_detail::enable_if_and < rv<T>& , enable_move_utility_emulation<T> , has_move_emulation_enabled<T> @@ -69,7 +70,7 @@ } template <class T> - inline typename ::boost::move_detail::enable_if_and + BOOST_MOVE_FORCEINLINE typename ::boost::move_detail::enable_if_and < rv<T>& , enable_move_utility_emulation<T> , has_move_emulation_enabled<T> @@ -86,7 +87,7 @@ ////////////////////////////////////////////////////////////////////////////// template <class T> - inline typename ::boost::move_detail::enable_if_and + BOOST_MOVE_FORCEINLINE typename ::boost::move_detail::enable_if_and < T & , enable_move_utility_emulation<T> , ::boost::move_detail::is_rv<T> @@ -97,7 +98,7 @@ } template <class T> - inline typename ::boost::move_detail::enable_if_and + BOOST_MOVE_FORCEINLINE typename ::boost::move_detail::enable_if_and < const T & , enable_move_utility_emulation<T> , ::boost::move_detail::is_not_rv<T> @@ -114,7 +115,7 @@ ////////////////////////////////////////////////////////////////////////////// template <class T> - inline typename ::boost::move_detail::enable_if_and + BOOST_MOVE_FORCEINLINE typename ::boost::move_detail::enable_if_and < T & , enable_move_utility_emulation<T> , ::boost::move_detail::is_rv<T> @@ -125,7 +126,7 @@ } template <class T> - inline typename ::boost::move_detail::enable_if_and + BOOST_MOVE_FORCEINLINE typename ::boost::move_detail::enable_if_and < typename ::boost::move_detail::add_lvalue_reference<T>::type , enable_move_utility_emulation<T> , ::boost::move_detail::is_not_rv<T> @@ -140,7 +141,7 @@ } template <class T> - inline typename ::boost::move_detail::enable_if_and + BOOST_MOVE_FORCEINLINE typename ::boost::move_detail::enable_if_and < rv<T>& , enable_move_utility_emulation<T> , ::boost::move_detail::is_not_rv<T> @@ -202,13 +203,13 @@ //Old move approach, lvalues could bind to rvalue references template <class T> - inline typename ::boost::move_detail::remove_reference<T>::type && move(T&& t) BOOST_NOEXCEPT + BOOST_MOVE_FORCEINLINE typename ::boost::move_detail::remove_reference<T>::type && move(T&& t) BOOST_NOEXCEPT { return t; } #else //BOOST_MOVE_OLD_RVALUE_REF_BINDING_RULES template <class T> - inline typename ::boost::move_detail::remove_reference<T>::type && move(T&& t) BOOST_NOEXCEPT + BOOST_MOVE_FORCEINLINE typename ::boost::move_detail::remove_reference<T>::type && move(T&& t) BOOST_NOEXCEPT { return static_cast<typename ::boost::move_detail::remove_reference<T>::type &&>(t); } #endif //BOOST_MOVE_OLD_RVALUE_REF_BINDING_RULES @@ -238,17 +239,17 @@ //Old move approach, lvalues could bind to rvalue references template <class T> - inline T&& forward(typename ::boost::move_detail::identity<T>::type&& t) BOOST_NOEXCEPT + BOOST_MOVE_FORCEINLINE T&& forward(typename ::boost::move_detail::identity<T>::type&& t) BOOST_NOEXCEPT { return t; } #else //Old move template <class T> - inline T&& forward(typename ::boost::move_detail::remove_reference<T>::type& t) BOOST_NOEXCEPT + BOOST_MOVE_FORCEINLINE T&& forward(typename ::boost::move_detail::remove_reference<T>::type& t) BOOST_NOEXCEPT { return static_cast<T&&>(t); } template <class T> - inline T&& forward(typename ::boost::move_detail::remove_reference<T>::type&& t) BOOST_NOEXCEPT + BOOST_MOVE_FORCEINLINE T&& forward(typename ::boost::move_detail::remove_reference<T>::type&& t) BOOST_NOEXCEPT { //"boost::forward<T> error: 'T' is a lvalue reference, can't forward as rvalue."; BOOST_STATIC_ASSERT(!boost::move_detail::is_lvalue_reference<T>::value); @@ -273,17 +274,17 @@ //Old move approach, lvalues could bind to rvalue references template <class T> - inline T&& move_if_not_lvalue_reference(typename ::boost::move_detail::identity<T>::type&& t) BOOST_NOEXCEPT + BOOST_MOVE_FORCEINLINE T&& move_if_not_lvalue_reference(typename ::boost::move_detail::identity<T>::type&& t) BOOST_NOEXCEPT { return t; } #else //Old move template <class T> - inline T&& move_if_not_lvalue_reference(typename ::boost::move_detail::remove_reference<T>::type& t) BOOST_NOEXCEPT + BOOST_MOVE_FORCEINLINE T&& move_if_not_lvalue_reference(typename ::boost::move_detail::remove_reference<T>::type& t) BOOST_NOEXCEPT { return static_cast<T&&>(t); } template <class T> - inline T&& move_if_not_lvalue_reference(typename ::boost::move_detail::remove_reference<T>::type&& t) BOOST_NOEXCEPT + BOOST_MOVE_FORCEINLINE T&& move_if_not_lvalue_reference(typename ::boost::move_detail::remove_reference<T>::type&& t) BOOST_NOEXCEPT { //"boost::forward<T> error: 'T' is a lvalue reference, can't forward as rvalue."; BOOST_STATIC_ASSERT(!boost::move_detail::is_lvalue_reference<T>::value); |