diff options
Diffstat (limited to 'boost/move/algo/detail/adaptive_sort_merge.hpp')
| -rw-r--r-- | boost/move/algo/detail/adaptive_sort_merge.hpp | 1208 |
1 files changed, 214 insertions, 994 deletions
diff --git a/boost/move/algo/detail/adaptive_sort_merge.hpp b/boost/move/algo/detail/adaptive_sort_merge.hpp index 5085100ad0..1606fde66a 100644 --- a/boost/move/algo/detail/adaptive_sort_merge.hpp +++ b/boost/move/algo/detail/adaptive_sort_merge.hpp @@ -49,7 +49,9 @@ #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/heap_sort.hpp> #include <boost/move/algo/detail/merge.hpp> +#include <boost/move/algo/detail/is_sorted.hpp> #include <boost/assert.hpp> #include <boost/cstdint.hpp> @@ -84,11 +86,26 @@ #define BOOST_MOVE_ADAPTIVE_SORT_INVARIANT(L) #endif - - namespace boost { namespace movelib { +#if defined(BOOST_MOVE_ADAPTIVE_SORT_INVARIANTS) + +bool is_sorted(::order_perf_type *first, ::order_perf_type *last, ::order_type_less) +{ + if (first != last) { + const order_perf_type *next = first, *cur(first); + while (++next != last) { + if (!(cur->key < next->key || (cur->key == next->key && cur->val < next->val))) + return false; + cur = next; + } + } + return true; +} + +#endif //BOOST_MOVE_ADAPTIVE_SORT_INVARIANTS + namespace detail_adaptive { static const std::size_t AdaptiveSortInsertionSortThreshold = 16; @@ -113,51 +130,6 @@ const T &max_value(const T &a, const T &b) return a > b ? a : b; } -template<class ForwardIt, class Pred> -bool is_sorted(ForwardIt const first, ForwardIt last, Pred pred) -{ - if (first != last) { - ForwardIt next = first, cur(first); - while (++next != last) { - if (pred(*next, *cur)) - return false; - cur = next; - } - } - return true; -} - -#if defined(BOOST_MOVE_ADAPTIVE_SORT_INVARIANTS) - -bool is_sorted(::order_perf_type *first, ::order_perf_type *last, ::order_type_less) -{ - if (first != last) { - const order_perf_type *next = first, *cur(first); - while (++next != last) { - if (!(cur->key < next->key || (cur->key == next->key && cur->val < next->val))) - return false; - cur = next; - } - } - return true; -} - -#endif //BOOST_MOVE_ADAPTIVE_SORT_INVARIANTS - -template<class ForwardIt, class Pred> -bool is_sorted_and_unique(ForwardIt first, ForwardIt last, Pred pred) -{ - if (first != last) { - ForwardIt next = first; - while (++next != last) { - if (!pred(*first, *next)) - return false; - first = next; - } - } - return true; -} - template<class ForwardIt, class Pred, class V> typename iterator_traits<ForwardIt>::size_type count_if_with(ForwardIt first, ForwardIt last, Pred pred, const V &v) @@ -414,44 +386,6 @@ RandIt skip_until_merge } -template<class RandIt1, class RandIt2, class RandItB, class Compare, class Op> -RandItB op_buffered_partial_merge_to_range1_and_buffer - ( RandIt1 first1, RandIt1 const last1 - , RandIt2 &rfirst2, RandIt2 const last2 - , RandItB &rfirstb, Compare comp, Op op ) -{ - RandItB firstb = rfirstb; - RandItB lastb = firstb; - RandIt2 first2 = rfirst2; - - //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(first1 != last1 && first2 != last2){ - op(three_way_t(), first2++, first1++, lastb++); - - while(true){ - if(first1 == last1){ - break; - } - if(first2 == last2){ - lastb = op(forward_t(), first1, last1, firstb); - break; - } - if (comp(*first2, *firstb)) { - op(three_way_t(), first2++, first1++, lastb++); - } - else { - op(three_way_t(), firstb++, first1++, lastb++); - } - } - rfirst2 = first2; - rfirstb = firstb; - } - - return lastb; -} - template<class RandItKeys, class RandIt> void swap_and_update_key ( RandItKeys const key_next @@ -567,7 +501,7 @@ void merge_blocks_bufferless typedef typename iterator_traits<RandIt>::size_type size_type; size_type const key_count = needed_keys_count(n_block_a, n_block_b); (void)key_count; //BOOST_ASSERT(n_block_a || n_block_b); - BOOST_MOVE_ADAPTIVE_SORT_INVARIANT(is_sorted_and_unique(key_first, key_first + key_count, key_comp)); + BOOST_MOVE_ADAPTIVE_SORT_INVARIANT(boost::movelib::is_sorted_and_unique(key_first, key_first + key_count, key_comp)); BOOST_MOVE_ADAPTIVE_SORT_INVARIANT(!n_block_b || n_block_a == count_if_with(key_first, key_first + key_count, key_comp, key_first[n_block_a])); size_type n_bef_irreg2 = 0; @@ -890,11 +824,40 @@ void stable_sort( RandIt first, RandIt last, Compare comp, XBuf & xbuf) } template<class RandIt, class Comp, class XBuf> +void unstable_sort( RandIt first, RandIt last + , Comp comp + , XBuf & xbuf) +{ + heap_sort(first, last, comp);(void)xbuf; +} + +template<class RandIt, class Compare, class XBuf> +void stable_merge + ( RandIt first, RandIt const middle, RandIt last + , Compare comp + , XBuf &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 Comp, class XBuf> void initialize_keys( RandIt first, RandIt last , Comp comp , XBuf & xbuf) { - stable_sort(first, last, comp, xbuf); + unstable_sort(first, last, comp, xbuf); + BOOST_ASSERT(boost::movelib::is_sorted_and_unique(first, last, comp)); } template<class RandIt, class U> @@ -910,40 +873,6 @@ void initialize_keys( RandIt first, RandIt last } } -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) { @@ -994,43 +923,7 @@ void combine_params } } -template<class RandIt1, class RandIt2, class RandItB, class Compare, class Op> -RandItB op_buffered_partial_merge_and_swap_to_range1_and_buffer - ( RandIt1 first1, RandIt1 const last1 - , RandIt2 &rfirst2, RandIt2 const last2, RandIt2 &rfirst_min - , RandItB &rfirstb, Compare comp, Op op ) -{ - RandItB firstb = rfirstb; - RandItB lastb = firstb; - RandIt2 first2 = rfirst2; - //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(first1 != last1 && first2 != last2){ - RandIt2 first_min = rfirst_min; - op(four_way_t(), first2++, first_min++, first1++, lastb++); - - while(first1 != last1){ - if(first2 == last2){ - lastb = op(forward_t(), first1, last1, firstb); - break; - } - - if(comp(*first_min, *firstb)){ - op( four_way_t(), first2++, first_min++, first1++, lastb++); - } - else{ - op(three_way_t(), firstb++, first1++, lastb++); - } - } - rfirst2 = first2; - rfirstb = firstb; - rfirst_min = first_min; - } - - return lastb; -} ////////////////////////////////// // @@ -1072,10 +965,14 @@ OutputIt op_partial_merge } ////////////////////////////////// +////////////////////////////////// +////////////////////////////////// // -// partial_merge_and_swap +// op_partial_merge_and_save // ////////////////////////////////// +////////////////////////////////// +////////////////////////////////// template<class InputIt1, class InputIt2, class OutputIt, class Compare, class Op> OutputIt op_partial_merge_and_swap_impl (InputIt1 &r_first1, InputIt1 const last1, InputIt2 &r_first2, InputIt2 const last2, InputIt2 &r_first_min, OutputIt d_first, Compare comp, Op op) @@ -1111,6 +1008,82 @@ OutputIt op_partial_merge_and_swap : op_partial_merge_and_swap_impl(r_first1, last1, r_first2, last2, r_first_min, d_first, antistable<Compare>(comp), op); } +template<class RandIt1, class RandIt2, class RandItB, class Compare, class Op> +RandItB op_buffered_partial_merge_and_swap_to_range1_and_buffer + ( RandIt1 first1, RandIt1 const last1 + , RandIt2 &rfirst2, RandIt2 const last2, RandIt2 &rfirst_min + , RandItB &rfirstb, Compare comp, Op op ) +{ + RandItB firstb = rfirstb; + RandItB lastb = firstb; + RandIt2 first2 = rfirst2; + + //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(first1 != last1 && first2 != last2){ + RandIt2 first_min = rfirst_min; + op(four_way_t(), first2++, first_min++, first1++, lastb++); + + while(first1 != last1){ + if(first2 == last2){ + lastb = op(forward_t(), first1, last1, firstb); + break; + } + + if(comp(*first_min, *firstb)){ + op( four_way_t(), first2++, first_min++, first1++, lastb++); + } + else{ + op(three_way_t(), firstb++, first1++, lastb++); + } + } + rfirst2 = first2; + rfirstb = firstb; + rfirst_min = first_min; + } + + return lastb; +} + +template<class RandIt1, class RandIt2, class RandItB, class Compare, class Op> +RandItB op_buffered_partial_merge_to_range1_and_buffer + ( RandIt1 first1, RandIt1 const last1 + , RandIt2 &rfirst2, RandIt2 const last2 + , RandItB &rfirstb, Compare comp, Op op ) +{ + RandItB firstb = rfirstb; + RandItB lastb = firstb; + RandIt2 first2 = rfirst2; + + //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(first1 != last1 && first2 != last2){ + op(three_way_t(), first2++, first1++, lastb++); + + while(true){ + if(first1 == last1){ + break; + } + if(first2 == last2){ + lastb = op(forward_t(), first1, last1, firstb); + break; + } + if (comp(*first2, *firstb)) { + op(three_way_t(), first2++, first1++, lastb++); + } + else { + op(three_way_t(), firstb++, first1++, lastb++); + } + } + rfirst2 = first2; + rfirstb = firstb; + } + + return lastb; +} + template<class RandIt, class RandItBuf, class Compare, class Op> RandIt op_partial_merge_and_save_impl ( RandIt first1, RandIt const last1, RandIt &rfirst2, RandIt last2, RandIt first_min @@ -1162,7 +1135,15 @@ RandIt op_partial_merge_and_save ; } - +////////////////////////////////// +////////////////////////////////// +////////////////////////////////// +// +// op_merge_blocks_with_irreg +// +////////////////////////////////// +////////////////////////////////// +////////////////////////////////// template<class RandItKeys, class KeyCompare, class RandIt, class RandIt2, class OutputIt, class Compare, class Op> OutputIt op_merge_blocks_with_irreg @@ -1215,6 +1196,16 @@ OutputIt op_merge_blocks_with_irreg return dest; } +////////////////////////////////// +////////////////////////////////// +////////////////////////////////// +// +// op_merge_blocks_left/right +// +////////////////////////////////// +////////////////////////////////// +////////////////////////////////// + template<class RandItKeys, class KeyCompare, class RandIt, class Compare, class Op> void op_merge_blocks_left ( RandItKeys const key_first @@ -1230,7 +1221,7 @@ void op_merge_blocks_left typedef typename iterator_traits<RandIt>::size_type size_type; size_type const key_count = needed_keys_count(n_block_a, n_block_b); (void)key_count; // BOOST_ASSERT(n_block_a || n_block_b); - BOOST_MOVE_ADAPTIVE_SORT_INVARIANT(is_sorted_and_unique(key_first, key_first + key_count, key_comp)); + BOOST_MOVE_ADAPTIVE_SORT_INVARIANT(boost::movelib::is_sorted_and_unique(key_first, key_first + key_count, key_comp)); BOOST_MOVE_ADAPTIVE_SORT_INVARIANT(!n_block_b || n_block_a == count_if_with(key_first, key_first + key_count, key_comp, key_first[n_block_a])); size_type n_block_b_left = n_block_b; @@ -1394,7 +1385,6 @@ void merge_blocks_left } } - // 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 @@ -1426,6 +1416,15 @@ void merge_blocks_right , inverse<Compare>(comp), xbuf_used); } +////////////////////////////////// +////////////////////////////////// +////////////////////////////////// +// +// op_merge_blocks_with_buf +// +////////////////////////////////// +////////////////////////////////// +////////////////////////////////// template<class RandItKeys, class KeyCompare, class RandIt, class Compare, class Op, class RandItBuf> void op_merge_blocks_with_buf ( RandItKeys key_first @@ -1443,7 +1442,7 @@ void op_merge_blocks_with_buf typedef typename iterator_traits<RandIt>::size_type size_type; size_type const key_count = needed_keys_count(n_block_a, n_block_b); (void)key_count; //BOOST_ASSERT(n_block_a || n_block_b); - BOOST_MOVE_ADAPTIVE_SORT_INVARIANT(is_sorted_and_unique(key_first, key_first + key_count, key_comp)); + BOOST_MOVE_ADAPTIVE_SORT_INVARIANT(boost::movelib::is_sorted_and_unique(key_first, key_first + key_count, key_comp)); BOOST_MOVE_ADAPTIVE_SORT_INVARIANT(!n_block_b || n_block_a == count_if_with(key_first, key_first + key_count, key_comp, key_first[n_block_a])); size_type n_block_b_left = n_block_b; @@ -1552,29 +1551,15 @@ void op_merge_blocks_with_buf BOOST_MOVE_ADAPTIVE_SORT_INVARIANT(is_sorted(first, last_irr2, comp)); } -template<class RandItKeys, class KeyCompare, class RandIt, class Compare, class RandItBuf> -void merge_blocks_with_buf - ( RandItKeys key_first - , 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_block_a - , typename iterator_traits<RandIt>::size_type const n_block_b - , typename iterator_traits<RandIt>::size_type const l_irreg2 - , Compare comp - , RandItBuf const buf_first - , bool const xbuf_used) -{ - if(xbuf_used){ - op_merge_blocks_with_buf - (key_first, key_comp, first, l_block, l_irreg1, n_block_a, n_block_b, l_irreg2, comp, move_op(), buf_first); - } - else{ - op_merge_blocks_with_buf - (key_first, key_comp, first, l_block, l_irreg1, n_block_a, n_block_b, l_irreg2, comp, swap_op(), buf_first); - } -} +////////////////////////////////// +////////////////////////////////// +////////////////////////////////// +// +// op_insertion_sort_step_left/right +// +////////////////////////////////// +////////////////////////////////// +////////////////////////////////// template<class RandIt, class Compare, class Op> typename iterator_traits<RandIt>::size_type @@ -1596,6 +1581,41 @@ typename iterator_traits<RandIt>::size_type return s; } +template<class RandIt, class Compare, class Op> +void op_merge_right_step_once + ( 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); + } +} + + +////////////////////////////////// +////////////////////////////////// +////////////////////////////////// +// +// insertion_sort_step +// +////////////////////////////////// +////////////////////////////////// +////////////////////////////////// template<class RandIt, class Compare> typename iterator_traits<RandIt>::size_type insertion_sort_step @@ -1616,6 +1636,15 @@ typename iterator_traits<RandIt>::size_type return s; } +////////////////////////////////// +////////////////////////////////// +////////////////////////////////// +// +// op_merge_left_step_multiple +// +////////////////////////////////// +////////////////////////////////// +////////////////////////////////// template<class RandIt, class Compare, class Op> typename iterator_traits<RandIt>::size_type op_merge_left_step_multiple @@ -1651,815 +1680,6 @@ typename iterator_traits<RandIt>::size_type return l_merged; } -template<class RandIt, class Compare, class Op> -void op_merge_right_step_once - ( 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, class XBuf> -typename iterator_traits<RandIt>::size_type - adaptive_sort_build_blocks - ( RandIt const first - , typename iterator_traits<RandIt>::size_type const len - , typename iterator_traits<RandIt>::size_type const l_base - , typename iterator_traits<RandIt>::size_type const l_build_buf - , XBuf & 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; - - BOOST_ASSERT(l_build_buf); - //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_multiple - ( 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_multiple - (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_once(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_once(first, elements_in_blocks, l_build_buf, comp, swap_op()); - } - xbuf.clear(); - //2*l_build_buf or total already merged - return min_value(elements_in_blocks, 2*l_build_buf); -} - -template<class RandItKeys, class KeyCompare, class RandIt, class Compare, class XBuf> -void adaptive_sort_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 - , XBuf & xbuf - , Compare comp - , bool merge_left) -{ - (void)xbuf; - typedef typename iterator_traits<RandIt>::size_type size_type; - - size_type const l_reg_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_reg_combined; - RandIt combined_first = first; - - (void)l_total_combined; - BOOST_ASSERT(l_total_combined <= len); - - 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_reg_combined) { - //Now merge blocks - bool const is_last = combined_i==n_reg_combined; - size_type const l_cur_combined = is_last ? l_irreg_combined : l_reg_combined; - - range_xbuf<RandIt, move_op> rbuf( (use_buf && xbuf_used) ? (combined_first-l_block) : combined_first, combined_first); - size_type n_block_a, n_block_b, l_irreg1, l_irreg2; - combine_params( keys, key_comp, l_cur_combined - , l_prev_merged, l_block, rbuf - , n_block_a, n_block_b, l_irreg1, l_irreg2); //Outputs - BOOST_MOVE_ADAPTIVE_SORT_PRINT_L2(" A combpar: ", len + l_block); - BOOST_MOVE_ADAPTIVE_SORT_INVARIANT(is_sorted(combined_first, combined_first + n_block_a*l_block+l_irreg1, comp)); - BOOST_MOVE_ADAPTIVE_SORT_INVARIANT(is_sorted(combined_first + n_block_a*l_block+l_irreg1, combined_first + n_block_a*l_block+l_irreg1+n_block_b*l_block+l_irreg2, comp)); - if(!use_buf){ - merge_blocks_bufferless - (keys, key_comp, combined_first, l_block, 0u, n_block_a, n_block_b, l_irreg2, comp); - } - else{ - merge_blocks_left - (keys, key_comp, combined_first, l_block, 0u, n_block_a, n_block_b, l_irreg2, comp, xbuf_used); - } - BOOST_MOVE_ADAPTIVE_SORT_PRINT_L2(" After merge_blocks_L: ", len + l_block); - } - } - else{ - combined_first += l_reg_combined*(max_i-1); - for( size_type combined_i = max_i; combined_i--; combined_first -= l_reg_combined) { - bool const is_last = combined_i==n_reg_combined; - size_type const l_cur_combined = is_last ? l_irreg_combined : l_reg_combined; - - RandIt const combined_last(combined_first+l_cur_combined); - range_xbuf<RandIt, move_op> rbuf(combined_last, xbuf_used ? (combined_last+l_block) : combined_last); - size_type n_block_a, n_block_b, l_irreg1, l_irreg2; - combine_params( keys, key_comp, l_cur_combined - , l_prev_merged, l_block, rbuf - , n_block_a, n_block_b, l_irreg1, l_irreg2); //Outputs - BOOST_MOVE_ADAPTIVE_SORT_PRINT_L2(" A combpar: ", len + l_block); - BOOST_MOVE_ADAPTIVE_SORT_INVARIANT(is_sorted(combined_first, combined_first + n_block_a*l_block+l_irreg1, comp)); - BOOST_MOVE_ADAPTIVE_SORT_INVARIANT(is_sorted(combined_first + n_block_a*l_block+l_irreg1, combined_first + n_block_a*l_block+l_irreg1+n_block_b*l_block+l_irreg2, comp)); - merge_blocks_right - (keys, key_comp, combined_first, l_block, n_block_a, n_block_b, l_irreg2, comp, xbuf_used); - BOOST_MOVE_ADAPTIVE_SORT_PRINT_L2(" After merge_blocks_R: ", len + l_block); - } - } -} - -//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, class XBuf> -bool adaptive_sort_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 - , XBuf & 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){ - xbuf.move_assign(buffer, l_intbuf); - } - - bool prev_merge_left = true; - size_type l_prev_total_combined = l_merged, 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(n && 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_L2(" After move_data : ", l_data + l_intbuf); - } - - //Combine to form l_merged*2 segments - if(n_keys){ - adaptive_sort_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>(); - adaptive_sort_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_L1(is_merge_left ? " After comb blocks L: " : " After comb blocks R: ", 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, class XBuf> -void stable_merge - ( RandIt first, RandIt const middle, RandIt last - , Compare comp - , XBuf &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, class XBuf> -void adaptive_sort_final_merge( bool buffer_right - , RandIt const first - , typename iterator_traits<RandIt>::size_type const l_intbuf - , typename iterator_traits<RandIt>::size_type const n_keys - , typename iterator_traits<RandIt>::size_type const len - , XBuf & 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_L1(" After final_merge : ", len); -} - -template<class RandIt, class Compare, class Unsigned, class XBuf> -bool adaptive_sort_build_params - (RandIt first, Unsigned const len, Compare comp - , Unsigned &n_keys, Unsigned &l_intbuf, Unsigned &l_base, Unsigned &l_build_buf - , XBuf & 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)); - - //The internal buffer can be expanded if there is enough external memory - while(xbuf.capacity() >= l_intbuf*2){ - l_intbuf *= 2; - } - - //This is the minimum number of keys to implement the ideal algorithm - // - //l_intbuf is used as buffer plus the key count - size_type n_min_ideal_keys = l_intbuf-1; - while(n_min_ideal_keys >= (len-l_intbuf-n_min_ideal_keys)/l_intbuf){ - --n_min_ideal_keys; - } - n_min_ideal_keys += 1; - BOOST_ASSERT(n_min_ideal_keys <= l_intbuf); - - if(xbuf.template supports_aligned_trailing<size_type>(l_intbuf, (len-l_intbuf-1)/l_intbuf+1)){ - 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 - //will be backuped in the buffer during build_blocks. - bool const non_unique_buf = xbuf.capacity() >= l_intbuf; - size_type const to_collect = non_unique_buf ? n_min_ideal_keys : 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){ - l_build_buf = l_intbuf; - n_keys = n_min_ideal_keys; - } - else if(collected == 2*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 if(collected == (n_min_ideal_keys+l_intbuf)){ - l_build_buf = l_intbuf; - n_keys = n_min_ideal_keys; - } - //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. - else{ - BOOST_ASSERT(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; - } - //AdaptiveSortInsertionSortThreshold is always power of two so the minimum is power of two - l_base = min_value<Unsigned>(n_keys, AdaptiveSortInsertionSortThreshold); - l_intbuf = 0; - l_build_buf = n_keys; - } - BOOST_ASSERT((n_keys+l_intbuf) >= l_build_buf); - } - - return true; -} - -template<class RandIt, class Compare, class XBuf> -inline void adaptive_merge_combine_blocks( RandIt first - , typename iterator_traits<RandIt>::size_type len1 - , typename iterator_traits<RandIt>::size_type len2 - , typename iterator_traits<RandIt>::size_type collected - , typename iterator_traits<RandIt>::size_type n_keys - , typename iterator_traits<RandIt>::size_type l_block - , bool use_internal_buf - , bool xbuf_used - , Compare comp - , XBuf & xbuf - ) -{ - typedef typename iterator_traits<RandIt>::size_type size_type; - size_type const len = len1+len2; - size_type const l_combine = len-collected; - size_type const l_combine1 = len1-collected; - - if(n_keys){ - RandIt const first_data = first+collected; - RandIt const keys = first; - BOOST_MOVE_ADAPTIVE_SORT_PRINT_L2(" A combine: ", len); - if(xbuf_used){ - if(xbuf.size() < l_block){ - xbuf.initialize_until(l_block, *first); - } - BOOST_ASSERT(xbuf.size() >= l_block); - size_type n_block_a, n_block_b, l_irreg1, l_irreg2; - combine_params( keys, comp, l_combine - , l_combine1, l_block, xbuf - , n_block_a, n_block_b, l_irreg1, l_irreg2); //Outputs - merge_blocks_with_buf - (keys, comp, first_data, l_block, l_irreg1, n_block_a, n_block_b, l_irreg2, comp, xbuf.data(), xbuf_used); - BOOST_MOVE_ADAPTIVE_SORT_PRINT_L1(" A mrg xbf: ", len); - } - else{ - size_type n_block_a, n_block_b, l_irreg1, l_irreg2; - combine_params( keys, comp, l_combine - , l_combine1, l_block, xbuf - , n_block_a, n_block_b, l_irreg1, l_irreg2); //Outputs - if(use_internal_buf){ - merge_blocks_with_buf - (keys, comp, first_data, l_block, l_irreg1, n_block_a, n_block_b, l_irreg2, comp, first_data-l_block, xbuf_used); - BOOST_MOVE_ADAPTIVE_SORT_PRINT_L2(" A mrg buf: ", len); - } - else{ - merge_blocks_bufferless - (keys, comp, first_data, l_block, l_irreg1, n_block_a, n_block_b, l_irreg2, comp); - BOOST_MOVE_ADAPTIVE_SORT_PRINT_L1(" A mrg nbf: ", len); - } - } - } - else{ - xbuf.shrink_to_fit(l_block); - if(xbuf.size() < l_block){ - xbuf.initialize_until(l_block, *first); - } - size_type *const uint_keys = xbuf.template aligned_trailing<size_type>(l_block); - size_type n_block_a, n_block_b, l_irreg1, l_irreg2; - combine_params( uint_keys, less(), l_combine - , l_combine1, l_block, xbuf - , n_block_a, n_block_b, l_irreg1, l_irreg2, true); //Outputs - BOOST_MOVE_ADAPTIVE_SORT_PRINT_L2(" A combine: ", len); - BOOST_ASSERT(xbuf.size() >= l_block); - merge_blocks_with_buf - (uint_keys, less(), first, l_block, l_irreg1, n_block_a, n_block_b, l_irreg2, comp, xbuf.data(), true); - xbuf.clear(); - BOOST_MOVE_ADAPTIVE_SORT_PRINT_L1(" A mrg buf: ", len); - } -} - -template<class RandIt, class Compare, class XBuf> -inline void adaptive_merge_final_merge( RandIt first - , typename iterator_traits<RandIt>::size_type len1 - , typename iterator_traits<RandIt>::size_type len2 - , typename iterator_traits<RandIt>::size_type collected - , typename iterator_traits<RandIt>::size_type l_intbuf - , typename iterator_traits<RandIt>::size_type l_block - , bool use_internal_buf - , bool xbuf_used - , Compare comp - , XBuf & xbuf - ) -{ - typedef typename iterator_traits<RandIt>::size_type size_type; - (void)l_block; - size_type n_keys = collected-l_intbuf; - size_type len = len1+len2; - 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); - BOOST_MOVE_ADAPTIVE_SORT_PRINT_L2(" A key mrg: ", len); - } - } - else{ - xbuf.clear(); - stable_sort(first, first+collected, comp, xbuf); - BOOST_MOVE_ADAPTIVE_SORT_PRINT_L2(" A k/b srt: ", len); - stable_merge(first, first+collected, first+len, comp, xbuf); - BOOST_MOVE_ADAPTIVE_SORT_PRINT_L2(" A k/b mrg: ", len); - } - } - else{ - xbuf.clear(); - stable_sort(first, first+collected, comp, xbuf); - BOOST_MOVE_ADAPTIVE_SORT_PRINT_L2(" A k/b srt: ", len); - stable_merge(first, first+collected, first+len1+len2, comp, xbuf); - BOOST_MOVE_ADAPTIVE_SORT_PRINT_L2(" A k/b mrg: ", len); - } - BOOST_MOVE_ADAPTIVE_SORT_PRINT_L1(" A fin mrg: ", len); -} - -template<class SizeType, class Xbuf> -inline SizeType adaptive_merge_n_keys_intbuf(SizeType &rl_block, SizeType len1, SizeType len2, Xbuf & xbuf, SizeType &l_intbuf_inout) -{ - typedef SizeType size_type; - size_type l_block = rl_block; - size_type l_intbuf = xbuf.capacity() >= l_block ? 0u : l_block; - - while(xbuf.capacity() >= l_block*2){ - l_block *= 2; - } - - //This is the minimum number of keys to implement the ideal algorithm - size_type n_keys = len1/l_block+len2/l_block; - while(n_keys >= ((len1-l_intbuf-n_keys)/l_block + len2/l_block)){ - --n_keys; - } - ++n_keys; - BOOST_ASSERT(n_keys >= ((len1-l_intbuf-n_keys)/l_block + len2/l_block)); - - if(xbuf.template supports_aligned_trailing<size_type>(l_block, n_keys)){ - n_keys = 0u; - } - l_intbuf_inout = l_intbuf; - rl_block = l_block; - return n_keys; -} - -/////////////////////////////////////////////////////////////////////////////////////////// -/////////////////////////////////////////////////////////////////////////////////////////// -/////////////////////////////////////////////////////////////////////////////////////////// -/////////////////////////////////////////////////////////////////////////////////////////// -/////////////////////////////////////////////////////////////////////////////////////////// -/////////////////////////////////////////////////////////////////////////////////////////// -/////////////////////////////////////////////////////////////////////////////////////////// - -// Main explanation of the sort algorithm. -// -// csqrtlen = ceil(sqrt(len)); -// -// * First, 2*csqrtlen unique elements elements are extracted from elements to be -// sorted and placed in the beginning of the range. -// -// * Step "build_blocks": In this nearly-classic merge step, 2*csqrtlen unique elements -// will be used as auxiliary memory, so trailing len-2*csqrtlen elements are -// are grouped in blocks of sorted 4*csqrtlen elements. At the end of the step -// 2*csqrtlen unique elements are again the leading elements of the whole range. -// -// * Step "combine_blocks": pairs of previously formed blocks are merged with a different -// ("smart") algorithm to form blocks of 8*csqrtlen elements. This step is slower than the -// "build_blocks" step and repeated iteratively (forming blocks of 16*csqrtlen, 32*csqrtlen -// elements, etc) of until all trailing (len-2*csqrtlen) elements are merged. -// -// In "combine_blocks" len/csqrtlen elements used are as "keys" (markers) to -// know if elements belong to the first or second block to be merged and another -// leading csqrtlen elements are used as buffer. Explanation of the "combine_blocks" step: -// -// Iteratively until all trailing (len-2*csqrtlen) elements are merged: -// Iteratively for each pair of previously merged block: -// * Blocks are divided groups of csqrtlen elements and -// 2*merged_block/csqrtlen keys are sorted to be used as markers -// * Groups are selection-sorted by first or last element (depending whether they are going -// to be merged to left or right) and keys are reordered accordingly as an imitation-buffer. -// * Elements of each block pair are merged using the csqrtlen buffer taking into account -// if they belong to the first half or second half (marked by the key). -// -// * In the final merge step leading elements (2*csqrtlen) are sorted and merged with -// rotations with the rest of sorted elements in the "combine_blocks" step. -// -// Corner cases: -// -// * If no 2*csqrtlen elements can be extracted: -// -// * If csqrtlen+len/csqrtlen are extracted, then only csqrtlen elements are used -// as buffer in the "build_blocks" step forming blocks of 2*csqrtlen elements. This -// means that an additional "combine_blocks" step will be needed to merge all elements. -// -// * If no csqrtlen+len/csqrtlen elements can be extracted, but still more than a minimum, -// then reduces the number of elements used as buffer and keys in the "build_blocks" -// and "combine_blocks" steps. If "combine_blocks" has no enough keys due to this reduction -// then uses a rotation based smart merge. -// -// * If the minimum number of keys can't be extracted, a rotation-based sorting is performed. -// -// * If auxiliary memory is more or equal than ceil(len/2), half-copying mergesort is used. -// -// * If auxiliary memory is more than csqrtlen+n_keys*sizeof(std::size_t), -// then only csqrtlen elements need to be extracted and "combine_blocks" will use integral -// keys to combine blocks. -// -// * If auxiliary memory is available, the "build_blocks" will be extended to build bigger blocks -// using classic merge and "combine_blocks" will use bigger blocks when merging. -template<class RandIt, class Compare, class XBuf> -void adaptive_sort_impl - ( RandIt first - , typename iterator_traits<RandIt>::size_type const len - , Compare comp - , XBuf & 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); - } - else if((len-len/2) <= xbuf.capacity()){ - merge_sort(first, first+len, comp, xbuf.data()); - } - else{ - //Make sure it is at least four - 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; - - //Calculate and extract needed unique elements. If a minimum is not achieved - //fallback to a slow stable sort - if(!adaptive_sort_build_params(first, len, comp, n_keys, l_intbuf, l_base, l_build_buf, xbuf)){ - stable_sort(first, first+len, comp, xbuf); - } - else{ - BOOST_ASSERT(l_build_buf); - //Otherwise, continue the adaptive_sort - BOOST_MOVE_ADAPTIVE_SORT_PRINT_L1("\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 = adaptive_sort_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_L1(" After build_blocks: ", len); - - //Non-trivial merge - bool const buffer_right = adaptive_sort_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 - adaptive_sort_final_merge(buffer_right, first, l_intbuf, n_keys, len, xbuf, comp); - } - } -} - -// Main explanation of the merge algorithm. -// -// csqrtlen = ceil(sqrt(len)); -// -// * First, csqrtlen [to be used as buffer] + (len/csqrtlen - 1) [to be used as keys] => to_collect -// unique elements are extracted from elements to be sorted and placed in the beginning of the range. -// -// * Step "combine_blocks": the leading (len1-to_collect) elements plus trailing len2 elements -// are merged with a non-trivial ("smart") algorithm to form an ordered range trailing "len-to_collect" elements. -// -// Explanation of the "combine_blocks" step: -// -// * Trailing [first+to_collect, first+len1) elements are divided in groups of cqrtlen elements. -// Remaining elements that can't form a group are grouped in front of those elements. -// * Trailing [first+len1, first+len1+len2) elements are divided in groups of cqrtlen elements. -// Remaining elements that can't form a group are grouped in the back of those elements. -// * In parallel the following two steps are performed: -// * Groups are selection-sorted by first or last element (depending whether they are going -// to be merged to left or right) and keys are reordered accordingly as an imitation-buffer. -// * Elements of each block pair are merged using the csqrtlen buffer taking into account -// if they belong to the first half or second half (marked by the key). -// -// * In the final merge step leading "to_collect" elements are merged with rotations -// with the rest of merged elements in the "combine_blocks" step. -// -// Corner cases: -// -// * If no "to_collect" elements can be extracted: -// -// * If more than a minimum number of elements is extracted -// then reduces the number of elements used as buffer and keys in the -// and "combine_blocks" steps. If "combine_blocks" has no enough keys due to this reduction -// then uses a rotation based smart merge. -// -// * If the minimum number of keys can't be extracted, a rotation-based merge is performed. -// -// * If auxiliary memory is more or equal than min(len1, len2), a buffered merge is performed. -// -// * If the len1 or len2 are less than 2*csqrtlen then a rotation-based merge is performed. -// -// * If auxiliary memory is more than csqrtlen+n_keys*sizeof(std::size_t), -// then no csqrtlen need to be extracted and "combine_blocks" will use integral -// keys to combine blocks. -template<class RandIt, class Compare, class XBuf> -void adaptive_merge_impl - ( RandIt first - , typename iterator_traits<RandIt>::size_type const len1 - , typename iterator_traits<RandIt>::size_type const len2 - , Compare comp - , XBuf & 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)); - - //One range is not big enough to extract keys and the internal buffer so a - //rotation-based based merge will do just fine - if(len1 <= l_block*2 || len2 <= l_block*2){ - merge_bufferless(first, first+len1, first+len1+len2, comp); - return; - } - - //Detail the number of keys and internal buffer. If xbuf has enough memory, no - //internal buffer is needed so l_intbuf will remain 0. - size_type l_intbuf = 0; - size_type n_keys = adaptive_merge_n_keys_intbuf(l_block, len1, len2, xbuf, l_intbuf); - size_type const to_collect = l_intbuf+n_keys; - //Try to extract needed unique values from the first range - size_type const collected = collect_unique(first, first+len1, to_collect, comp, xbuf); - BOOST_MOVE_ADAPTIVE_SORT_PRINT_L1("\n A collect: ", len); - - //Not the minimum number of keys is not available on the first range, so fallback to rotations - if(collected != to_collect && collected < 4){ - merge_bufferless(first, first+collected, first+len1, comp); - merge_bufferless(first, first + len1, first + len1 + len2, comp); - return; - } - - //If not enough keys but more than minimum, adjust the internal buffer and key count - bool use_internal_buf = collected == to_collect; - if (!use_internal_buf){ - l_intbuf = 0u; - n_keys = collected; - l_block = lblock_for_combine(l_intbuf, n_keys, len, use_internal_buf); - //If use_internal_buf is false, then then internal buffer will be zero and rotation-based combination will be used - l_intbuf = use_internal_buf ? l_block : 0u; - } - - bool const xbuf_used = collected == to_collect && xbuf.capacity() >= l_block; - //Merge trailing elements using smart merges - adaptive_merge_combine_blocks(first, len1, len2, collected, n_keys, l_block, use_internal_buf, xbuf_used, comp, xbuf); - //Merge buffer and keys with the rest of the values - adaptive_merge_final_merge (first, len1, len2, collected, l_intbuf, l_block, use_internal_buf, xbuf_used, comp, xbuf); - } -} - } //namespace detail_adaptive { } //namespace movelib { |