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
dispatch_gpu_sort_by_key(KeyIterator keys_first,KeyIterator keys_last,ValueIterator values_first,less<typename std::iterator_traits<KeyIterator>::value_type> compare,command_queue & queue,typename boost::enable_if_c<is_radix_sortable<typename std::iterator_traits<KeyIterator>::value_type>::value>::type * =0)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
dispatch_gpu_sort_by_key(KeyIterator keys_first,KeyIterator keys_last,ValueIterator values_first,greater<typename std::iterator_traits<KeyIterator>::value_type> compare,command_queue & queue,typename boost::enable_if_c<is_radix_sortable<typename std::iterator_traits<KeyIterator>::value_type>::value>::type * =0)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>
dispatch_gpu_sort_by_key(KeyIterator keys_first,KeyIterator keys_last,ValueIterator values_first,Compare compare,command_queue & queue)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>
dispatch_sort_by_key(KeyIterator keys_first,KeyIterator keys_last,ValueIterator values_first,Compare compare,command_queue & queue)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>
sort_by_key(KeyIterator keys_first,KeyIterator keys_last,ValueIterator values_first,Compare compare,command_queue & queue=system::default_queue ())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>
sort_by_key(KeyIterator keys_first,KeyIterator keys_last,ValueIterator values_first,command_queue & queue=system::default_queue ())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
169