]>
Commit | Line | Data |
---|---|---|
11fdf7f2 TL |
1 | ////////////////////////////////////////////////////////////////////////////// |
2 | // | |
3 | // (C) Copyright Orson Peters 2017. | |
4 | // (C) Copyright Ion Gaztanaga 2017-2018. | |
5 | // Distributed under the Boost Software License, Version 1.0. | |
6 | // (See accompanying file LICENSE_1_0.txt or copy at | |
7 | // http://www.boost.org/LICENSE_1_0.txt) | |
8 | // | |
9 | // See http://www.boost.org/libs/move for documentation. | |
10 | // | |
11 | ////////////////////////////////////////////////////////////////////////////// | |
12 | // | |
13 | // This implementation of Pattern-defeating quicksort (pdqsort) was written | |
14 | // by Orson Peters, and discussed in the Boost mailing list: | |
15 | // http://boost.2283326.n4.nabble.com/sort-pdqsort-td4691031.html | |
16 | // | |
17 | // This implementation is the adaptation by Ion Gaztanaga of code originally in GitHub | |
18 | // with permission from the author to relicense it under the Boost Software License | |
19 | // (see the Boost mailing list for details). | |
20 | // | |
21 | // The original copyright statement is pasted here for completeness: | |
22 | // | |
23 | // pdqsort.h - Pattern-defeating quicksort. | |
24 | // Copyright (c) 2015 Orson Peters | |
25 | // This software is provided 'as-is', without any express or implied warranty. In no event will the | |
26 | // authors be held liable for any damages arising from the use of this software. | |
27 | // Permission is granted to anyone to use this software for any purpose, including commercial | |
28 | // applications, and to alter it and redistribute it freely, subject to the following restrictions: | |
29 | // 1. The origin of this software must not be misrepresented; you must not claim that you wrote the | |
30 | // original software. If you use this software in a product, an acknowledgment in the product | |
31 | // documentation would be appreciated but is not required. | |
32 | // 2. Altered source versions must be plainly marked as such, and must not be misrepresented as | |
33 | // being the original software. | |
34 | // 3. This notice may not be removed or altered from any source distribution. | |
35 | // | |
36 | ////////////////////////////////////////////////////////////////////////////// | |
37 | ||
38 | #ifndef BOOST_MOVE_ALGO_PDQSORT_HPP | |
39 | #define BOOST_MOVE_ALGO_PDQSORT_HPP | |
40 | ||
41 | #ifndef BOOST_CONFIG_HPP | |
42 | # include <boost/config.hpp> | |
43 | #endif | |
44 | # | |
45 | #if defined(BOOST_HAS_PRAGMA_ONCE) | |
46 | # pragma once | |
47 | #endif | |
48 | ||
49 | #include <boost/move/detail/config_begin.hpp> | |
1e59de90 | 50 | |
11fdf7f2 TL |
51 | #include <boost/move/detail/workaround.hpp> |
52 | #include <boost/move/utility_core.hpp> | |
53 | #include <boost/move/algo/detail/insertion_sort.hpp> | |
54 | #include <boost/move/algo/detail/heap_sort.hpp> | |
55 | #include <boost/move/detail/iterator_traits.hpp> | |
56 | ||
57 | #include <boost/move/adl_move_swap.hpp> | |
58 | #include <cstddef> | |
59 | ||
1e59de90 TL |
60 | #if defined(BOOST_CLANG) || (defined(BOOST_GCC) && (BOOST_GCC >= 40600)) |
61 | #pragma GCC diagnostic push | |
62 | #pragma GCC diagnostic ignored "-Wsign-conversion" | |
63 | #endif | |
64 | ||
11fdf7f2 TL |
65 | namespace boost { |
66 | namespace movelib { | |
67 | ||
68 | namespace pdqsort_detail { | |
69 | ||
70 | //A simple pair implementation to avoid including <utility> | |
71 | template<class T1, class T2> | |
72 | struct pair | |
73 | { | |
74 | pair() | |
75 | {} | |
76 | ||
77 | pair(const T1 &t1, const T2 &t2) | |
78 | : first(t1), second(t2) | |
79 | {} | |
80 | ||
81 | T1 first; | |
82 | T2 second; | |
83 | }; | |
84 | ||
85 | enum { | |
86 | // Partitions below this size are sorted using insertion sort. | |
87 | insertion_sort_threshold = 24, | |
88 | ||
89 | // Partitions above this size use Tukey's ninther to select the pivot. | |
90 | ninther_threshold = 128, | |
91 | ||
92 | // When we detect an already sorted partition, attempt an insertion sort that allows this | |
93 | // amount of element moves before giving up. | |
94 | partial_insertion_sort_limit = 8, | |
95 | ||
96 | // Must be multiple of 8 due to loop unrolling, and < 256 to fit in unsigned char. | |
97 | block_size = 64, | |
98 | ||
99 | // Cacheline size, assumes power of two. | |
100 | cacheline_size = 64 | |
101 | ||
102 | }; | |
103 | ||
104 | // Returns floor(log2(n)), assumes n > 0. | |
105 | template<class Unsigned> | |
106 | Unsigned log2(Unsigned n) { | |
107 | Unsigned log = 0; | |
108 | while (n >>= 1) ++log; | |
109 | return log; | |
110 | } | |
111 | ||
112 | // Attempts to use insertion sort on [begin, end). Will return false if more than | |
113 | // partial_insertion_sort_limit elements were moved, and abort sorting. Otherwise it will | |
114 | // successfully sort and return true. | |
115 | template<class Iter, class Compare> | |
116 | inline bool partial_insertion_sort(Iter begin, Iter end, Compare comp) { | |
117 | typedef typename boost::movelib::iterator_traits<Iter>::value_type T; | |
1e59de90 | 118 | typedef typename boost::movelib:: iter_size<Iter>::type size_type; |
11fdf7f2 TL |
119 | if (begin == end) return true; |
120 | ||
121 | size_type limit = 0; | |
122 | for (Iter cur = begin + 1; cur != end; ++cur) { | |
123 | if (limit > partial_insertion_sort_limit) return false; | |
124 | ||
125 | Iter sift = cur; | |
126 | Iter sift_1 = cur - 1; | |
127 | ||
128 | // Compare first so we can avoid 2 moves for an element already positioned correctly. | |
129 | if (comp(*sift, *sift_1)) { | |
130 | T tmp = boost::move(*sift); | |
131 | ||
132 | do { *sift-- = boost::move(*sift_1); } | |
133 | while (sift != begin && comp(tmp, *--sift_1)); | |
134 | ||
135 | *sift = boost::move(tmp); | |
136 | limit += size_type(cur - sift); | |
137 | } | |
138 | } | |
139 | ||
140 | return true; | |
141 | } | |
142 | ||
143 | template<class Iter, class Compare> | |
144 | inline void sort2(Iter a, Iter b, Compare comp) { | |
145 | if (comp(*b, *a)) boost::adl_move_iter_swap(a, b); | |
146 | } | |
147 | ||
148 | // Sorts the elements *a, *b and *c using comparison function comp. | |
149 | template<class Iter, class Compare> | |
150 | inline void sort3(Iter a, Iter b, Iter c, Compare comp) { | |
151 | sort2(a, b, comp); | |
152 | sort2(b, c, comp); | |
153 | sort2(a, b, comp); | |
154 | } | |
155 | ||
156 | // Partitions [begin, end) around pivot *begin using comparison function comp. Elements equal | |
157 | // to the pivot are put in the right-hand partition. Returns the position of the pivot after | |
158 | // partitioning and whether the passed sequence already was correctly partitioned. Assumes the | |
159 | // pivot is a median of at least 3 elements and that [begin, end) is at least | |
160 | // insertion_sort_threshold long. | |
161 | template<class Iter, class Compare> | |
162 | pdqsort_detail::pair<Iter, bool> partition_right(Iter begin, Iter end, Compare comp) { | |
163 | typedef typename boost::movelib::iterator_traits<Iter>::value_type T; | |
164 | ||
165 | // Move pivot into local for speed. | |
166 | T pivot(boost::move(*begin)); | |
167 | ||
168 | Iter first = begin; | |
169 | Iter last = end; | |
170 | ||
171 | // Find the first element greater than or equal than the pivot (the median of 3 guarantees | |
172 | // this exists). | |
173 | while (comp(*++first, pivot)); | |
174 | ||
175 | // Find the first element strictly smaller than the pivot. We have to guard this search if | |
176 | // there was no element before *first. | |
177 | if (first - 1 == begin) while (first < last && !comp(*--last, pivot)); | |
178 | else while ( !comp(*--last, pivot)); | |
179 | ||
180 | // If the first pair of elements that should be swapped to partition are the same element, | |
181 | // the passed in sequence already was correctly partitioned. | |
182 | bool already_partitioned = first >= last; | |
183 | ||
184 | // Keep swapping pairs of elements that are on the wrong side of the pivot. Previously | |
185 | // swapped pairs guard the searches, which is why the first iteration is special-cased | |
186 | // above. | |
187 | while (first < last) { | |
188 | boost::adl_move_iter_swap(first, last); | |
189 | while (comp(*++first, pivot)); | |
190 | while (!comp(*--last, pivot)); | |
191 | } | |
192 | ||
193 | // Put the pivot in the right place. | |
194 | Iter pivot_pos = first - 1; | |
195 | *begin = boost::move(*pivot_pos); | |
196 | *pivot_pos = boost::move(pivot); | |
197 | ||
198 | return pdqsort_detail::pair<Iter, bool>(pivot_pos, already_partitioned); | |
199 | } | |
200 | ||
201 | // Similar function to the one above, except elements equal to the pivot are put to the left of | |
202 | // the pivot and it doesn't check or return if the passed sequence already was partitioned. | |
203 | // Since this is rarely used (the many equal case), and in that case pdqsort already has O(n) | |
204 | // performance, no block quicksort is applied here for simplicity. | |
205 | template<class Iter, class Compare> | |
206 | inline Iter partition_left(Iter begin, Iter end, Compare comp) { | |
207 | typedef typename boost::movelib::iterator_traits<Iter>::value_type T; | |
208 | ||
209 | T pivot(boost::move(*begin)); | |
210 | Iter first = begin; | |
211 | Iter last = end; | |
212 | ||
213 | while (comp(pivot, *--last)); | |
214 | ||
215 | if (last + 1 == end) while (first < last && !comp(pivot, *++first)); | |
216 | else while ( !comp(pivot, *++first)); | |
217 | ||
218 | while (first < last) { | |
219 | boost::adl_move_iter_swap(first, last); | |
220 | while (comp(pivot, *--last)); | |
221 | while (!comp(pivot, *++first)); | |
222 | } | |
223 | ||
224 | Iter pivot_pos = last; | |
225 | *begin = boost::move(*pivot_pos); | |
226 | *pivot_pos = boost::move(pivot); | |
227 | ||
228 | return pivot_pos; | |
229 | } | |
230 | ||
231 | ||
232 | template<class Iter, class Compare> | |
233 | void pdqsort_loop( Iter begin, Iter end, Compare comp | |
1e59de90 | 234 | , typename boost::movelib:: iter_size<Iter>::type bad_allowed |
11fdf7f2 TL |
235 | , bool leftmost = true) |
236 | { | |
1e59de90 | 237 | typedef typename boost::movelib:: iter_size<Iter>::type size_type; |
11fdf7f2 TL |
238 | |
239 | // Use a while loop for tail recursion elimination. | |
240 | while (true) { | |
241 | size_type size = size_type(end - begin); | |
242 | ||
243 | // Insertion sort is faster for small arrays. | |
244 | if (size < insertion_sort_threshold) { | |
245 | insertion_sort(begin, end, comp); | |
246 | return; | |
247 | } | |
248 | ||
249 | // Choose pivot as median of 3 or pseudomedian of 9. | |
250 | size_type s2 = size / 2; | |
251 | if (size > ninther_threshold) { | |
252 | sort3(begin, begin + s2, end - 1, comp); | |
253 | sort3(begin + 1, begin + (s2 - 1), end - 2, comp); | |
254 | sort3(begin + 2, begin + (s2 + 1), end - 3, comp); | |
255 | sort3(begin + (s2 - 1), begin + s2, begin + (s2 + 1), comp); | |
256 | boost::adl_move_iter_swap(begin, begin + s2); | |
257 | } else sort3(begin + s2, begin, end - 1, comp); | |
258 | ||
259 | // If *(begin - 1) is the end of the right partition of a previous partition operation | |
260 | // there is no element in [begin, end) that is smaller than *(begin - 1). Then if our | |
261 | // pivot compares equal to *(begin - 1) we change strategy, putting equal elements in | |
262 | // the left partition, greater elements in the right partition. We do not have to | |
263 | // recurse on the left partition, since it's sorted (all equal). | |
264 | if (!leftmost && !comp(*(begin - 1), *begin)) { | |
265 | begin = partition_left(begin, end, comp) + 1; | |
266 | continue; | |
267 | } | |
268 | ||
269 | // Partition and get results. | |
270 | pdqsort_detail::pair<Iter, bool> part_result = partition_right(begin, end, comp); | |
271 | Iter pivot_pos = part_result.first; | |
272 | bool already_partitioned = part_result.second; | |
273 | ||
274 | // Check for a highly unbalanced partition. | |
275 | size_type l_size = size_type(pivot_pos - begin); | |
276 | size_type r_size = size_type(end - (pivot_pos + 1)); | |
277 | bool highly_unbalanced = l_size < size / 8 || r_size < size / 8; | |
278 | ||
279 | // If we got a highly unbalanced partition we shuffle elements to break many patterns. | |
280 | if (highly_unbalanced) { | |
281 | // If we had too many bad partitions, switch to heapsort to guarantee O(n log n). | |
282 | if (--bad_allowed == 0) { | |
283 | boost::movelib::heap_sort(begin, end, comp); | |
284 | return; | |
285 | } | |
286 | ||
287 | if (l_size >= insertion_sort_threshold) { | |
288 | boost::adl_move_iter_swap(begin, begin + l_size / 4); | |
289 | boost::adl_move_iter_swap(pivot_pos - 1, pivot_pos - l_size / 4); | |
290 | ||
291 | if (l_size > ninther_threshold) { | |
292 | boost::adl_move_iter_swap(begin + 1, begin + (l_size / 4 + 1)); | |
293 | boost::adl_move_iter_swap(begin + 2, begin + (l_size / 4 + 2)); | |
294 | boost::adl_move_iter_swap(pivot_pos - 2, pivot_pos - (l_size / 4 + 1)); | |
295 | boost::adl_move_iter_swap(pivot_pos - 3, pivot_pos - (l_size / 4 + 2)); | |
296 | } | |
297 | } | |
298 | ||
299 | if (r_size >= insertion_sort_threshold) { | |
300 | boost::adl_move_iter_swap(pivot_pos + 1, pivot_pos + (1 + r_size / 4)); | |
301 | boost::adl_move_iter_swap(end - 1, end - r_size / 4); | |
302 | ||
303 | if (r_size > ninther_threshold) { | |
304 | boost::adl_move_iter_swap(pivot_pos + 2, pivot_pos + (2 + r_size / 4)); | |
305 | boost::adl_move_iter_swap(pivot_pos + 3, pivot_pos + (3 + r_size / 4)); | |
306 | boost::adl_move_iter_swap(end - 2, end - (1 + r_size / 4)); | |
307 | boost::adl_move_iter_swap(end - 3, end - (2 + r_size / 4)); | |
308 | } | |
309 | } | |
310 | } else { | |
311 | // If we were decently balanced and we tried to sort an already partitioned | |
312 | // sequence try to use insertion sort. | |
313 | if (already_partitioned && partial_insertion_sort(begin, pivot_pos, comp) | |
314 | && partial_insertion_sort(pivot_pos + 1, end, comp)) return; | |
315 | } | |
316 | ||
317 | // Sort the left partition first using recursion and do tail recursion elimination for | |
318 | // the right-hand partition. | |
319 | pdqsort_loop<Iter, Compare>(begin, pivot_pos, comp, bad_allowed, leftmost); | |
320 | begin = pivot_pos + 1; | |
321 | leftmost = false; | |
322 | } | |
323 | } | |
324 | } | |
325 | ||
326 | ||
327 | template<class Iter, class Compare> | |
328 | void pdqsort(Iter begin, Iter end, Compare comp) | |
329 | { | |
330 | if (begin == end) return; | |
1e59de90 | 331 | typedef typename boost::movelib:: iter_size<Iter>::type size_type; |
11fdf7f2 TL |
332 | pdqsort_detail::pdqsort_loop<Iter, Compare>(begin, end, comp, pdqsort_detail::log2(size_type(end - begin))); |
333 | } | |
334 | ||
335 | } //namespace movelib { | |
336 | } //namespace boost { | |
337 | ||
1e59de90 TL |
338 | #if defined(BOOST_CLANG) || (defined(BOOST_GCC) && (BOOST_GCC >= 40600)) |
339 | #pragma GCC diagnostic pop | |
340 | #endif | |
341 | ||
11fdf7f2 TL |
342 | #include <boost/move/detail/config_end.hpp> |
343 | ||
344 | #endif //BOOST_MOVE_ALGO_PDQSORT_HPP |