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

   1 //---------------------------------------------------------------------------//
   2 // Copyright (c) 2013 Kyle Lutz <kyle.r.lutz@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_SORT_HPP
  12 #define BOOST_COMPUTE_ALGORITHM_SORT_HPP
  13
  14 #include <iterator>
  15
  16 #include <boost/utility/enable_if.hpp>
  17
  18 #include <boost/compute/system.hpp>
  19 #include <boost/compute/command_queue.hpp>
  20 #include <boost/compute/algorithm/detail/merge_sort_on_cpu.hpp>
  21 #include <boost/compute/algorithm/detail/merge_sort_on_gpu.hpp>
  22 #include <boost/compute/algorithm/detail/radix_sort.hpp>
  23 #include <boost/compute/algorithm/detail/insertion_sort.hpp>
  24 #include <boost/compute/algorithm/reverse.hpp>
  25 #include <boost/compute/container/mapped_view.hpp>
  26 #include <boost/compute/detail/iterator_range_size.hpp>
  27 #include <boost/compute/iterator/buffer_iterator.hpp>
  28 #include <boost/compute/type_traits/is_device_iterator.hpp>
  29
  30 namespace boost {
  31 namespace compute {
  32 namespace detail {
  33
  34 template<class T>
  35 inline void dispatch_gpu_sort(buffer_iterator<T> first,
  36                               buffer_iterator<T> last,
  37                               less<T>,
  38                               command_queue &queue,
  39                               typename boost::enable_if_c<
  40                                   is_radix_sortable<T>::value
  41                               >::type* = 0)
  42 {
  43     size_t count = detail::iterator_range_size(first, last);
  44
  45     if(count < 2){
  46         // nothing to do
  47         return;
  48     }
  49     else if(count <= 32){
  50         ::boost::compute::detail::serial_insertion_sort(first, last, queue);
  51     }
  52     else {
  53         ::boost::compute::detail::radix_sort(first, last, queue);
  54     }
  55 }
  56
  57 template<class T>
  58 inline void dispatch_gpu_sort(buffer_iterator<T> first,
  59                               buffer_iterator<T> last,
  60                               greater<T> compare,
  61                               command_queue &queue,
  62                               typename boost::enable_if_c<
  63                                   is_radix_sortable<T>::value
  64                               >::type* = 0)
  65 {
  66     size_t count = detail::iterator_range_size(first, last);
  67
  68     if(count < 2){
  69         // nothing to do
  70         return;
  71     }
  72     else if(count <= 32){
  73         ::boost::compute::detail::serial_insertion_sort(
  74             first, last, compare, queue
  75         );
  76     }
  77     else {
  78         // radix sorts in descending order
  79         ::boost::compute::detail::radix_sort(first, last, false, queue);
  80     }
  81 }
  82
  83 template<class Iterator, class Compare>
  84 inline void dispatch_gpu_sort(Iterator first,
  85                               Iterator last,
  86                               Compare compare,
  87                               command_queue &queue)
  88 {
  89     size_t count = detail::iterator_range_size(first, last);
  90
  91     if(count < 2){
  92         // nothing to do
  93         return;
  94     }
  95     else if(count <= 32){
  96         ::boost::compute::detail::serial_insertion_sort(
  97             first, last, compare, queue
  98         );
  99     }
 100     else {
 101         ::boost::compute::detail::merge_sort_on_gpu(
 102             first, last, compare, queue
 103         );
 104     }
 105 }
 106
 107 // sort() for device iterators
 108 template<class Iterator, class Compare>
 109 inline void dispatch_sort(Iterator first,
 110                           Iterator last,
 111                           Compare compare,
 112                           command_queue &queue,
 113                           typename boost::enable_if<
 114                               is_device_iterator<Iterator>
 115                           >::type* = 0)
 116 {
 117     if(queue.get_device().type() & device::gpu) {
 118         dispatch_gpu_sort(first, last, compare, queue);
 119         return;
 120     }
 121     ::boost::compute::detail::merge_sort_on_cpu(first, last, compare, queue);
 122 }
 123
 124 // sort() for host iterators
 125 template<class Iterator, class Compare>
 126 inline void dispatch_sort(Iterator first,
 127                           Iterator last,
 128                           Compare compare,
 129                           command_queue &queue,
 130                           typename boost::disable_if<
 131                               is_device_iterator<Iterator>
 132                           >::type* = 0)
 133 {
 134     typedef typename std::iterator_traits<Iterator>::value_type T;
 135
 136     size_t size = static_cast<size_t>(std::distance(first, last));
 137
 138     // create mapped buffer
 139     mapped_view<T> view(
 140         boost::addressof(*first), size, queue.get_context()
 141     );
 142
 143     // sort mapped buffer
 144     dispatch_sort(view.begin(), view.end(), compare, queue);
 145
 146     // return results to host
 147     view.map(queue);
 148 }
 149
 150 } // end detail namespace
 151
 152 /// Sorts the values in the range [\p first, \p last) according to
 153 /// \p compare.
 154 ///
 155 /// \param first first element in the range to sort
 156 /// \param last last element in the range to sort
 157 /// \param compare comparison function (by default \c less)
 158 /// \param queue command queue to perform the operation
 159 ///
 160 /// For example, to sort a vector on the device:
 161 /// \code
 162 /// // create vector on the device with data
 163 /// float data[] = { 2.f, 4.f, 1.f, 3.f };
 164 /// boost::compute::vector<float> vec(data, data + 4, queue);
 165 ///
 166 /// // sort the vector on the device
 167 /// boost::compute::sort(vec.begin(), vec.end(), queue);
 168 /// \endcode
 169 ///
 170 /// The sort() algorithm can also be directly used with host iterators. This
 171 /// example will automatically transfer the data to the device, sort it, and
 172 /// then transfer the data back to the host:
 173 /// \code
 174 /// std::vector<int> data = { 9, 3, 2, 5, 1, 4, 6, 7 };
 175 ///
 176 /// boost::compute::sort(data.begin(), data.end(), queue);
 177 /// \endcode
 178 ///
 179 /// Space complexity: \Omega(n)
 180 ///
 181 /// \see is_sorted()
 182 template<class Iterator, class Compare>
 183 inline void sort(Iterator first,
 184                  Iterator last,
 185                  Compare compare,
 186                  command_queue &queue = system::default_queue())
 187 {
 188     ::boost::compute::detail::dispatch_sort(first, last, compare, queue);
 189 }
 190
 191 /// \overload
 192 template<class Iterator>
 193 inline void sort(Iterator first,
 194                  Iterator last,
 195                  command_queue &queue = system::default_queue())
 196 {
 197     typedef typename std::iterator_traits<Iterator>::value_type value_type;
 198
 199     ::boost::compute::sort(
 200         first, last, ::boost::compute::less<value_type>(), queue
 201     );
 202 }
 203
 204 } // end compute namespace
 205 } // end boost namespace
 206
 207 #endif // BOOST_COMPUTE_ALGORITHM_SORT_HPP