import new upstream nautilus stable release 14.2.8

[ceph.git] / ceph / src / boost / boost / move / algo / detail / merge_sort.hpp

diff --git a/ceph/src/boost/boost/move/algo/detail/merge_sort.hpp b/ceph/src/boost/boost/move/algo/detail/merge_sort.hpp
index 62d185acb63877e2c72366f86d89c70c763ca411..34bbd2e2a8880f2aee910f7c166a64916e23e732 100644 (file)
--- a/ceph/src/boost/boost/move/algo/detail/merge_sort.hpp
+++ b/ceph/src/boost/boost/move/algo/detail/merge_sort.hpp
@@ -132,6 +132,74 @@ void merge_sort( RandIt first, RandIt last, Compare comp
    }
 }
 
+///@cond
+
+template<class RandIt, class RandItRaw, class Compare>
+void merge_sort_with_constructed_buffer( RandIt first, RandIt last, Compare comp, RandItRaw buffer)
+{
+   typedef typename iterator_traits<RandIt>::size_type  size_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_copy(half_it, last, buffer, comp);
+      merge_sort_copy(first, half_it, rest_it, comp);
+      merge_with_right_placed
+         (buffer, buffer + rest
+         , first, rest_it, last, antistable<Compare>(comp));
+   }
+}
+
+template<typename RandIt, typename Pointer,
+         typename Distance, typename Compare>
+void stable_sort_ONlogN_recursive(RandIt first, RandIt last, Pointer buffer, Distance buffer_size, Compare comp)
+{
+   typedef typename iterator_traits<RandIt>::size_type  size_type;
+   if (size_type(last - first) <= size_type(MergeSortInsertionSortThreshold)) {
+      insertion_sort(first, last, comp);
+   }
+   else {
+      const size_type len = (last - first) / 2;
+      const RandIt middle = first + len;
+      if (len > ((buffer_size+1)/2)){
+         stable_sort_ONlogN_recursive(first, middle, buffer, buffer_size, comp);
+         stable_sort_ONlogN_recursive(middle, last, buffer, buffer_size, comp);
+      }
+      else{
+         merge_sort_with_constructed_buffer(first, middle, comp, buffer);
+         merge_sort_with_constructed_buffer(middle, last, comp, buffer);
+      }
+      merge_adaptive_ONlogN_recursive(first, middle, last,
+         size_type(middle - first),
+         size_type(last - middle),
+         buffer, buffer_size,
+         comp);
+   }
+}
+
+template<typename BidirectionalIterator, typename Compare, typename RandRawIt>
+void stable_sort_adaptive_ONlogN2(BidirectionalIterator first,
+                                          BidirectionalIterator last,
+                                          Compare comp,
+                                 RandRawIt uninitialized,
+                                 std::size_t uninitialized_len)
+{
+   typedef typename iterator_traits<BidirectionalIterator>::value_type  value_type;
+
+   ::boost::movelib::adaptive_xbuf<value_type, RandRawIt> xbuf(uninitialized, uninitialized_len);
+   xbuf.initialize_until(uninitialized_len, *first);
+   stable_sort_ONlogN_recursive(first, last, uninitialized, uninitialized_len, comp);
+}
+
+///@endcond
+
 }} //namespace boost {  namespace movelib{
 
 #include <boost/move/detail/config_end.hpp>