ceph/src/boost/libs/compute/include/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/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/insertion_sort.hpp>
  23 #include <boost/compute/algorithm/detail/radix_sort.hpp>
  24 #include <boost/compute/algorithm/reverse.hpp>
  25 #include <boost/compute/detail/iterator_range_size.hpp>
  26
  27 namespace boost {
  28 namespace compute {
  29
  30 namespace detail {
  31
  32 template<class KeyIterator, class ValueIterator>
  33 inline void
  34 dispatch_gpu_sort_by_key(KeyIterator keys_first,
  35                          KeyIterator keys_last,
  36                          ValueIterator values_first,
  37                          less<typename std::iterator_traits<KeyIterator>::value_type> compare,
  38                          command_queue &queue,
  39                          typename boost::enable_if_c<
  40                              is_radix_sortable<
  41                                  typename std::iterator_traits<KeyIterator>::value_type
  42                              >::value
  43                          >::type* = 0)
  44 {
  45     size_t count = detail::iterator_range_size(keys_first, keys_last);
  46
  47     if(count < 32){
  48         detail::serial_insertion_sort_by_key(
  49             keys_first, keys_last, values_first, compare, queue
  50         );
  51     }
  52     else {
  53         detail::radix_sort_by_key(
  54             keys_first, keys_last, values_first, queue
  55         );
  56     }
  57 }
  58
  59 template<class KeyIterator, class ValueIterator>
  60 inline void
  61 dispatch_gpu_sort_by_key(KeyIterator keys_first,
  62                          KeyIterator keys_last,
  63                          ValueIterator values_first,
  64                          greater<typename std::iterator_traits<KeyIterator>::value_type> compare,
  65                          command_queue &queue,
  66                          typename boost::enable_if_c<
  67                              is_radix_sortable<
  68                                  typename std::iterator_traits<KeyIterator>::value_type
  69                              >::value
  70                          >::type* = 0)
  71 {
  72     size_t count = detail::iterator_range_size(keys_first, keys_last);
  73
  74     if(count < 32){
  75         detail::serial_insertion_sort_by_key(
  76             keys_first, keys_last, values_first, compare, queue
  77         );
  78     }
  79     else {
  80         // radix sorts in descending order
  81         detail::radix_sort_by_key(
  82             keys_first, keys_last, values_first, false, queue
  83         );
  84     }
  85 }
  86
  87 template<class KeyIterator, class ValueIterator, class Compare>
  88 inline void dispatch_gpu_sort_by_key(KeyIterator keys_first,
  89                                      KeyIterator keys_last,
  90                                      ValueIterator values_first,
  91                                      Compare compare,
  92                                      command_queue &queue)
  93 {
  94     size_t count = detail::iterator_range_size(keys_first, keys_last);
  95
  96     if(count < 32){
  97         detail::serial_insertion_sort_by_key(
  98             keys_first, keys_last, values_first, compare, queue
  99         );
 100     } else {
 101         detail::merge_sort_by_key_on_gpu(
 102             keys_first, keys_last, values_first, compare, queue
 103         );
 104     }
 105 }
 106
 107 template<class KeyIterator, class ValueIterator, class Compare>
 108 inline void dispatch_sort_by_key(KeyIterator keys_first,
 109                                  KeyIterator keys_last,
 110                                  ValueIterator values_first,
 111                                  Compare compare,
 112                                  command_queue &queue)
 113 {
 114     if(queue.get_device().type() & device::gpu) {
 115         dispatch_gpu_sort_by_key(keys_first, keys_last, values_first, compare, queue);
 116         return;
 117     }
 118     ::boost::compute::detail::merge_sort_by_key_on_cpu(
 119         keys_first, keys_last, values_first, compare, queue
 120     );
 121 }
 122
 123 } // end detail namespace
 124
 125 /// Performs a key-value sort using the keys in the range [\p keys_first,
 126 /// \p keys_last) on the values in the range [\p values_first,
 127 /// \p values_first \c + (\p keys_last \c - \p keys_first)) using \p compare.
 128 ///
 129 /// If no compare function is specified, \c less is used.
 130 ///
 131 /// \see sort()
 132 template<class KeyIterator, class ValueIterator, class Compare>
 133 inline void 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_sort_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 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::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_SORT_BY_KEY_HPP