1 //---------------------------------------------------------------------------//
2 // Copyright (c) 2016 Jakub Szuppe <j.szuppe@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_STABLE_SORT_BY_KEY_HPP
12 #define BOOST_COMPUTE_ALGORITHM_STABLE_SORT_BY_KEY_HPP
13
14 #include <iterator>
15
16 #include <boost/static_assert.hpp>
17
18 #include <boost/compute/system.hpp>
19 #include <boost/compute/command_queue.hpp>
20 #include <boost/compute/algorithm/sort_by_key.hpp>
21 #include <boost/compute/detail/iterator_range_size.hpp>
22 #include <boost/compute/type_traits/is_device_iterator.hpp>
23
24 namespace boost {
25 namespace compute {
26
27 namespace detail {
28
29 template<class KeyIterator, class ValueIterator>
30 inline void
dispatch_gpu_ssort_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)31 dispatch_gpu_ssort_by_key(KeyIterator keys_first,
32 KeyIterator keys_last,
33 ValueIterator values_first,
34 less<typename std::iterator_traits<KeyIterator>::value_type> compare,
35 command_queue &queue,
36 typename boost::enable_if_c<
37 is_radix_sortable<
38 typename std::iterator_traits<KeyIterator>::value_type
39 >::value
40 >::type* = 0)
41 {
42 size_t count = detail::iterator_range_size(keys_first, keys_last);
43
44 if(count < 32){
45 detail::serial_insertion_sort_by_key(
46 keys_first, keys_last, values_first, compare, queue
47 );
48 }
49 else {
50 detail::radix_sort_by_key(
51 keys_first, keys_last, values_first, queue
52 );
53 }
54 }
55
56 template<class KeyIterator, class ValueIterator>
57 inline void
dispatch_gpu_ssort_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)58 dispatch_gpu_ssort_by_key(KeyIterator keys_first,
59 KeyIterator keys_last,
60 ValueIterator values_first,
61 greater<typename std::iterator_traits<KeyIterator>::value_type> compare,
62 command_queue &queue,
63 typename boost::enable_if_c<
64 is_radix_sortable<
65 typename std::iterator_traits<KeyIterator>::value_type
66 >::value
67 >::type* = 0)
68 {
69 size_t count = detail::iterator_range_size(keys_first, keys_last);
70
71 if(count < 32){
72 detail::serial_insertion_sort_by_key(
73 keys_first, keys_last, values_first, compare, queue
74 );
75 }
76 else {
77 // radix sorts in descending order
78 detail::radix_sort_by_key(
79 keys_first, keys_last, values_first, false, queue
80 );
81 }
82 }
83
84 template<class KeyIterator, class ValueIterator, class Compare>
dispatch_gpu_ssort_by_key(KeyIterator keys_first,KeyIterator keys_last,ValueIterator values_first,Compare compare,command_queue & queue)85 inline void dispatch_gpu_ssort_by_key(KeyIterator keys_first,
86 KeyIterator keys_last,
87 ValueIterator values_first,
88 Compare compare,
89 command_queue &queue)
90 {
91 size_t count = detail::iterator_range_size(keys_first, keys_last);
92
93 if(count < 32){
94 detail::serial_insertion_sort_by_key(
95 keys_first, keys_last, values_first,
96 compare, queue
97 );
98 } else {
99 detail::merge_sort_by_key_on_gpu(
100 keys_first, keys_last, values_first,
101 compare, true /* stable */, queue
102 );
103 }
104 }
105
106 template<class KeyIterator, class ValueIterator, class Compare>
dispatch_ssort_by_key(KeyIterator keys_first,KeyIterator keys_last,ValueIterator values_first,Compare compare,command_queue & queue)107 inline void dispatch_ssort_by_key(KeyIterator keys_first,
108 KeyIterator keys_last,
109 ValueIterator values_first,
110 Compare compare,
111 command_queue &queue)
112 {
113 if(queue.get_device().type() & device::gpu) {
114 dispatch_gpu_ssort_by_key(
115 keys_first, keys_last, values_first, compare, queue
116 );
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 stable 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>
stable_sort_by_key(KeyIterator keys_first,KeyIterator keys_last,ValueIterator values_first,Compare compare,command_queue & queue=system::default_queue ())136 inline void stable_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_ssort_by_key(
145 keys_first, keys_last, values_first, compare, queue
146 );
147 }
148
149 /// \overload
150 template<class KeyIterator, class ValueIterator>
stable_sort_by_key(KeyIterator keys_first,KeyIterator keys_last,ValueIterator values_first,command_queue & queue=system::default_queue ())151 inline void stable_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::stable_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_STABLE_SORT_BY_KEY_HPP
169