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