ceph/src/boost/boost/move/algo/detail/merge_sort.hpp

   1 //////////////////////////////////////////////////////////////////////////////
   2 //
   3 // (C) Copyright Ion Gaztanaga 2015-2016.
   4 // Distributed under the Boost Software License, Version 1.0.
   5 // (See accompanying file LICENSE_1_0.txt or copy at
   6 // http://www.boost.org/LICENSE_1_0.txt)
   7 //
   8 // See http://www.boost.org/libs/move for documentation.
   9 //
  10 //////////////////////////////////////////////////////////////////////////////
  11
  12 //! \file
  13
  14 #ifndef BOOST_MOVE_DETAIL_MERGE_SORT_HPP
  15 #define BOOST_MOVE_DETAIL_MERGE_SORT_HPP
  16
  17 #ifndef BOOST_CONFIG_HPP
  18 #  include <boost/config.hpp>
  19 #endif
  20 #
  21 #if defined(BOOST_HAS_PRAGMA_ONCE)
  22 #  pragma once
  23 #endif
  24
  25 #include <boost/move/detail/config_begin.hpp>
  26 #include <boost/move/detail/workaround.hpp>
  27
  28 #include <boost/move/utility_core.hpp>
  29 #include <boost/move/algo/move.hpp>
  30 #include <boost/move/algo/detail/merge.hpp>
  31 #include <boost/move/detail/iterator_traits.hpp>
  32 #include <boost/move/adl_move_swap.hpp>
  33 #include <boost/move/detail/destruct_n.hpp>
  34 #include <boost/move/algo/detail/insertion_sort.hpp>
  35 #include <cassert>
  36
  37 #if defined(BOOST_CLANG) || (defined(BOOST_GCC) && (BOOST_GCC >= 40600))
  38 #pragma GCC diagnostic push
  39 #pragma GCC diagnostic ignored "-Wsign-conversion"
  40 #endif
  41
  42 namespace boost {
  43 namespace movelib {
  44
  45 // @cond
  46
  47 static const unsigned MergeSortInsertionSortThreshold = 16;
  48
  49 template <class RandIt, class Compare>
  50 void inplace_stable_sort(RandIt first, RandIt last, Compare comp)
  51 {
  52    typedef typename iter_size<RandIt>::type  size_type;
  53    if (size_type(last - first) <= size_type(MergeSortInsertionSortThreshold)) {
  54       insertion_sort(first, last, comp);
  55       return;
  56    }
  57    RandIt middle = first + (last - first) / 2;
  58    inplace_stable_sort(first, middle, comp);
  59    inplace_stable_sort(middle, last, comp);
  60    merge_bufferless_ONlogN_recursive
  61       (first, middle, last, size_type(middle - first), size_type(last - middle), comp);
  62 }
  63
  64 // @endcond
  65
  66 template<class RandIt, class RandIt2, class Compare>
  67 void merge_sort_copy( RandIt first, RandIt last
  68                    , RandIt2 dest, Compare comp)
  69 {
  70    typedef typename iter_size<RandIt>::type         size_type;
  71
  72    size_type const count = size_type(last - first);
  73    if(count <= MergeSortInsertionSortThreshold){
  74       insertion_sort_copy(first, last, dest, comp);
  75    }
  76    else{
  77       size_type const half = size_type(count/2u);
  78       merge_sort_copy(first + half, last        , dest+half   , comp);
  79       merge_sort_copy(first       , first + half, first + half, comp);
  80       merge_with_right_placed
  81          ( first + half, first + half + half
  82          , dest, dest+half, dest + count
  83          , comp);
  84    }
  85 }
  86
  87 template<class RandIt, class RandItRaw, class Compare>
  88 void merge_sort_uninitialized_copy( RandIt first, RandIt last
  89                                  , RandItRaw uninitialized
  90                                  , Compare comp)
  91 {
  92    typedef typename iter_size<RandIt>::type       size_type;
  93    typedef typename iterator_traits<RandIt>::value_type value_type;
  94
  95    size_type const count = size_type(last - first);
  96    if(count <= MergeSortInsertionSortThreshold){
  97       insertion_sort_uninitialized_copy(first, last, uninitialized, comp);
  98    }
  99    else{
 100       size_type const half = count/2;
 101       merge_sort_uninitialized_copy(first + half, last, uninitialized + half, comp);
 102       destruct_n<value_type, RandItRaw> d(uninitialized+half);
 103       d.incr(size_type(count-half));
 104       merge_sort_copy(first, first + half, first + half, comp);
 105       uninitialized_merge_with_right_placed
 106          ( first + half, first + half + half
 107          , uninitialized, uninitialized+half, uninitialized+count
 108          , comp);
 109       d.release();
 110    }
 111 }
 112
 113 template<class RandIt, class RandItRaw, class Compare>
 114 void merge_sort( RandIt first, RandIt last, Compare comp
 115                , RandItRaw uninitialized)
 116 {
 117    typedef typename iter_size<RandIt>::type       size_type;
 118    typedef typename iterator_traits<RandIt>::value_type      value_type;
 119
 120    size_type const count = size_type(last - first);
 121    if(count <= MergeSortInsertionSortThreshold){
 122       insertion_sort(first, last, comp);
 123    }
 124    else{
 125       size_type const half = size_type(count/2u);
 126       size_type const rest = size_type(count -  half);
 127       RandIt const half_it = first + half;
 128       RandIt const rest_it = first + rest;
 129
 130       merge_sort_uninitialized_copy(half_it, last, uninitialized, comp);
 131       destruct_n<value_type, RandItRaw> d(uninitialized);
 132       d.incr(rest);
 133       merge_sort_copy(first, half_it, rest_it, comp);
 134       merge_with_right_placed
 135          ( uninitialized, uninitialized + rest
 136          , first, rest_it, last, antistable<Compare>(comp));
 137    }
 138 }
 139
 140 ///@cond
 141
 142 template<class RandIt, class RandItRaw, class Compare>
 143 void merge_sort_with_constructed_buffer( RandIt first, RandIt last, Compare comp, RandItRaw buffer)
 144 {
 145    typedef typename iter_size<RandIt>::type       size_type;
 146
 147    size_type const count = size_type(last - first);
 148    if(count <= MergeSortInsertionSortThreshold){
 149       insertion_sort(first, last, comp);
 150    }
 151    else{
 152       size_type const half = size_type(count/2);
 153       size_type const rest = size_type(count -  half);
 154       RandIt const half_it = first + half;
 155       RandIt const rest_it = first + rest;
 156
 157       merge_sort_copy(half_it, last, buffer, comp);
 158       merge_sort_copy(first, half_it, rest_it, comp);
 159       merge_with_right_placed
 160          (buffer, buffer + rest
 161          , first, rest_it, last, antistable<Compare>(comp));
 162    }
 163 }
 164
 165 template<typename RandIt, typename Pointer,
 166          typename Distance, typename Compare>
 167 void stable_sort_ONlogN_recursive(RandIt first, RandIt last, Pointer buffer, Distance buffer_size, Compare comp)
 168 {
 169    typedef typename iter_size<RandIt>::type  size_type;
 170    if (size_type(last - first) <= size_type(MergeSortInsertionSortThreshold)) {
 171       insertion_sort(first, last, comp);
 172    }
 173    else {
 174       const size_type len = size_type(last - first) / 2u;
 175       const RandIt middle = first + len;
 176       if (len > ((buffer_size+1)/2)){
 177          stable_sort_ONlogN_recursive(first, middle, buffer, buffer_size, comp);
 178          stable_sort_ONlogN_recursive(middle, last, buffer, buffer_size, comp);
 179       }
 180       else{
 181          merge_sort_with_constructed_buffer(first, middle, comp, buffer);
 182          merge_sort_with_constructed_buffer(middle, last, comp, buffer);
 183       }
 184       merge_adaptive_ONlogN_recursive(first, middle, last,
 185          size_type(middle - first),
 186          size_type(last - middle),
 187          buffer, buffer_size,
 188          comp);
 189    }
 190 }
 191
 192 template<typename BidirectionalIterator, typename Compare, typename RandRawIt>
 193 void stable_sort_adaptive_ONlogN2(BidirectionalIterator first,
 194                                            BidirectionalIterator last,
 195                                            Compare comp,
 196                                  RandRawIt uninitialized,
 197                                  std::size_t uninitialized_len)
 198 {
 199    typedef typename iterator_traits<BidirectionalIterator>::value_type  value_type;
 200
 201    ::boost::movelib::adaptive_xbuf<value_type, RandRawIt> xbuf(uninitialized, uninitialized_len);
 202    xbuf.initialize_until(uninitialized_len, *first);
 203    stable_sort_ONlogN_recursive(first, last, uninitialized, uninitialized_len, comp);
 204 }
 205
 206 ///@endcond
 207
 208 }} //namespace boost {  namespace movelib{
 209
 210 #if defined(BOOST_CLANG) || (defined(BOOST_GCC) && (BOOST_GCC >= 40600))
 211 #pragma GCC diagnostic pop
 212 #endif
 213
 214 #include <boost/move/detail/config_end.hpp>
 215
 216 #endif //#ifndef BOOST_MOVE_DETAIL_MERGE_SORT_HPP