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>
dispatch_gpu_sort(buffer_iterator<T> first,buffer_iterator<T> last,less<T>,command_queue & queue,typename boost::enable_if_c<is_radix_sortable<T>::value>::type * =0)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>
dispatch_gpu_sort(buffer_iterator<T> first,buffer_iterator<T> last,greater<T> compare,command_queue & queue,typename boost::enable_if_c<is_radix_sortable<T>::value>::type * =0)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>
dispatch_gpu_sort(Iterator first,Iterator last,Compare compare,command_queue & queue)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>
dispatch_sort(Iterator first,Iterator last,Compare compare,command_queue & queue,typename boost::enable_if<is_device_iterator<Iterator>>::type * =0)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>
dispatch_sort(Iterator first,Iterator last,Compare compare,command_queue & queue,typename boost::disable_if<is_device_iterator<Iterator>>::type * =0)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>
sort(Iterator first,Iterator last,Compare compare,command_queue & queue=system::default_queue ())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>
sort(Iterator first,Iterator last,command_queue & queue=system::default_queue ())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
208