ceph/src/boost/boost/compute/algorithm/stable_sort_by_key.hpp

   1 //---------------------------------------------------------------------------//
   2 // Copyright (c) 2016 Jakub Szuppe <j.szuppe@gmail.com>
   3 //
   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://boostorg.github.com/compute for more information.
   9 //---------------------------------------------------------------------------//
  10
  11 #ifndef BOOST_COMPUTE_ALGORITHM_STABLE_SORT_BY_KEY_HPP
  12 #define BOOST_COMPUTE_ALGORITHM_STABLE_SORT_BY_KEY_HPP
  13
  14 #include <iterator>
  15
  16 #include <boost/compute/system.hpp>
  17 #include <boost/compute/command_queue.hpp>
  18 #include <boost/compute/algorithm/sort_by_key.hpp>
  19 #include <boost/compute/detail/iterator_range_size.hpp>
  20
  21 namespace boost {
  22 namespace compute {
  23
  24 namespace detail {
  25
  26 template<class KeyIterator, class ValueIterator>
  27 inline void
  28 dispatch_gpu_ssort_by_key(KeyIterator keys_first,
  29                           KeyIterator keys_last,
  30                           ValueIterator values_first,
  31                           less<typename std::iterator_traits<KeyIterator>::value_type> compare,
  32                           command_queue &queue,
  33                           typename boost::enable_if_c<
  34                               is_radix_sortable<
  35                                   typename std::iterator_traits<KeyIterator>::value_type
  36                               >::value
  37                           >::type* = 0)
  38 {
  39     size_t count = detail::iterator_range_size(keys_first, keys_last);
  40
  41     if(count < 32){
  42         detail::serial_insertion_sort_by_key(
  43             keys_first, keys_last, values_first, compare, queue
  44         );
  45     }
  46     else {
  47         detail::radix_sort_by_key(
  48             keys_first, keys_last, values_first, queue
  49         );
  50     }
  51 }
  52
  53 template<class KeyIterator, class ValueIterator>
  54 inline void
  55 dispatch_gpu_ssort_by_key(KeyIterator keys_first,
  56                           KeyIterator keys_last,
  57                           ValueIterator values_first,
  58                           greater<typename std::iterator_traits<KeyIterator>::value_type> compare,
  59                           command_queue &queue,
  60                           typename boost::enable_if_c<
  61                               is_radix_sortable<
  62                                   typename std::iterator_traits<KeyIterator>::value_type
  63                               >::value
  64                           >::type* = 0)
  65 {
  66     size_t count = detail::iterator_range_size(keys_first, keys_last);
  67
  68     if(count < 32){
  69         detail::serial_insertion_sort_by_key(
  70             keys_first, keys_last, values_first, compare, queue
  71         );
  72     }
  73     else {
  74         // radix sorts in descending order
  75         detail::radix_sort_by_key(
  76             keys_first, keys_last, values_first, false, queue
  77         );
  78     }
  79 }
  80
  81 template<class KeyIterator, class ValueIterator, class Compare>
  82 inline void dispatch_gpu_ssort_by_key(KeyIterator keys_first,
  83                                       KeyIterator keys_last,
  84                                       ValueIterator values_first,
  85                                       Compare compare,
  86                                       command_queue &queue)
  87 {
  88     size_t count = detail::iterator_range_size(keys_first, keys_last);
  89
  90     if(count < 32){
  91         detail::serial_insertion_sort_by_key(
  92             keys_first, keys_last, values_first,
  93             compare, queue
  94         );
  95     } else {
  96         detail::merge_sort_by_key_on_gpu(
  97             keys_first, keys_last, values_first,
  98             compare, true /* stable */, queue
  99         );
 100     }
 101 }
 102
 103 template<class KeyIterator, class ValueIterator, class Compare>
 104 inline void dispatch_ssort_by_key(KeyIterator keys_first,
 105                                   KeyIterator keys_last,
 106                                   ValueIterator values_first,
 107                                   Compare compare,
 108                                   command_queue &queue)
 109 {
 110     if(queue.get_device().type() & device::gpu) {
 111         dispatch_gpu_ssort_by_key(
 112             keys_first, keys_last, values_first, compare, queue
 113         );
 114         return;
 115     }
 116     ::boost::compute::detail::merge_sort_by_key_on_cpu(
 117         keys_first, keys_last, values_first, compare, queue
 118     );
 119 }
 120
 121 } // end detail namespace
 122
 123 /// Performs a key-value stable sort using the keys in the range [\p keys_first,
 124 /// \p keys_last) on the values in the range [\p values_first,
 125 /// \p values_first \c + (\p keys_last \c - \p keys_first)) using \p compare.
 126 ///
 127 /// If no compare function is specified, \c less is used.
 128 ///
 129 /// Space complexity: \Omega(2n)
 130 ///
 131 /// \see sort()
 132 template<class KeyIterator, class ValueIterator, class Compare>
 133 inline void stable_sort_by_key(KeyIterator keys_first,
 134                                KeyIterator keys_last,
 135                                ValueIterator values_first,
 136                                Compare compare,
 137                                command_queue &queue = system::default_queue())
 138 {
 139     ::boost::compute::detail::dispatch_ssort_by_key(
 140         keys_first, keys_last, values_first, compare, queue
 141     );
 142 }
 143
 144 /// \overload
 145 template<class KeyIterator, class ValueIterator>
 146 inline void stable_sort_by_key(KeyIterator keys_first,
 147                                KeyIterator keys_last,
 148                                ValueIterator values_first,
 149                                command_queue &queue = system::default_queue())
 150 {
 151     typedef typename std::iterator_traits<KeyIterator>::value_type key_type;
 152
 153     ::boost::compute::stable_sort_by_key(
 154         keys_first, keys_last, values_first, less<key_type>(), queue
 155     );
 156 }
 157
 158 } // end compute namespace
 159 } // end boost namespace
 160
 161 #endif // BOOST_COMPUTE_ALGORITHM_STABLE_SORT_BY_KEY_HPP