Warning: This file is not a C or C++ file. It does not have highlighting.

1//===----------------------------------------------------------------------===//
2//
3// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
4// See https://llvm.org/LICENSE.txt for license information.
5// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
6//
7//===----------------------------------------------------------------------===//
8
9#ifndef _LIBCPP___CXX03___ALGORITHM_SORT_H
10#define _LIBCPP___CXX03___ALGORITHM_SORT_H
11
12#include <__cxx03/__algorithm/comp.h>
13#include <__cxx03/__algorithm/comp_ref_type.h>
14#include <__cxx03/__algorithm/iter_swap.h>
15#include <__cxx03/__algorithm/iterator_operations.h>
16#include <__cxx03/__algorithm/min_element.h>
17#include <__cxx03/__algorithm/partial_sort.h>
18#include <__cxx03/__algorithm/unwrap_iter.h>
19#include <__cxx03/__assert>
20#include <__cxx03/__bit/blsr.h>
21#include <__cxx03/__bit/countl.h>
22#include <__cxx03/__bit/countr.h>
23#include <__cxx03/__config>
24#include <__cxx03/__debug_utils/randomize_range.h>
25#include <__cxx03/__debug_utils/strict_weak_ordering_check.h>
26#include <__cxx03/__functional/operations.h>
27#include <__cxx03/__iterator/iterator_traits.h>
28#include <__cxx03/__type_traits/conditional.h>
29#include <__cxx03/__type_traits/disjunction.h>
30#include <__cxx03/__type_traits/is_arithmetic.h>
31#include <__cxx03/__type_traits/is_constant_evaluated.h>
32#include <__cxx03/__utility/move.h>
33#include <__cxx03/__utility/pair.h>
34#include <__cxx03/climits>
35#include <__cxx03/cstdint>
36
37#if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER)
38# pragma GCC system_header
39#endif
40
41_LIBCPP_PUSH_MACROS
42#include <__cxx03/__undef_macros>
43
44_LIBCPP_BEGIN_NAMESPACE_STD
45
46// stable, 2-3 compares, 0-2 swaps
47
48template <class _AlgPolicy, class _Compare, class _ForwardIterator>
49_LIBCPP_HIDE_FROM_ABI unsigned __sort3(_ForwardIterator __x, _ForwardIterator __y, _ForwardIterator __z, _Compare __c) {
50 using _Ops = _IterOps<_AlgPolicy>;
51
52 unsigned __r = 0;
53 if (!__c(*__y, *__x)) // if x <= y
54 {
55 if (!__c(*__z, *__y)) // if y <= z
56 return __r; // x <= y && y <= z
57 // x <= y && y > z
58 _Ops::iter_swap(__y, __z); // x <= z && y < z
59 __r = 1;
60 if (__c(*__y, *__x)) // if x > y
61 {
62 _Ops::iter_swap(__x, __y); // x < y && y <= z
63 __r = 2;
64 }
65 return __r; // x <= y && y < z
66 }
67 if (__c(*__z, *__y)) // x > y, if y > z
68 {
69 _Ops::iter_swap(__x, __z); // x < y && y < z
70 __r = 1;
71 return __r;
72 }
73 _Ops::iter_swap(__x, __y); // x > y && y <= z
74 __r = 1; // x < y && x <= z
75 if (__c(*__z, *__y)) // if y > z
76 {
77 _Ops::iter_swap(__y, __z); // x <= y && y < z
78 __r = 2;
79 }
80 return __r;
81} // x <= y && y <= z
82
83// stable, 3-6 compares, 0-5 swaps
84
85template <class _AlgPolicy, class _Compare, class _ForwardIterator>
86_LIBCPP_HIDE_FROM_ABI void
87__sort4(_ForwardIterator __x1, _ForwardIterator __x2, _ForwardIterator __x3, _ForwardIterator __x4, _Compare __c) {
88 using _Ops = _IterOps<_AlgPolicy>;
89 std::__sort3<_AlgPolicy, _Compare>(__x1, __x2, __x3, __c);
90 if (__c(*__x4, *__x3)) {
91 _Ops::iter_swap(__x3, __x4);
92 if (__c(*__x3, *__x2)) {
93 _Ops::iter_swap(__x2, __x3);
94 if (__c(*__x2, *__x1)) {
95 _Ops::iter_swap(__x1, __x2);
96 }
97 }
98 }
99}
100
101// stable, 4-10 compares, 0-9 swaps
102
103template <class _AlgPolicy, class _Comp, class _ForwardIterator>
104_LIBCPP_HIDE_FROM_ABI void
105__sort5(_ForwardIterator __x1,
106 _ForwardIterator __x2,
107 _ForwardIterator __x3,
108 _ForwardIterator __x4,
109 _ForwardIterator __x5,
110 _Comp __comp) {
111 using _Ops = _IterOps<_AlgPolicy>;
112
113 std::__sort4<_AlgPolicy, _Comp>(__x1, __x2, __x3, __x4, __comp);
114 if (__comp(*__x5, *__x4)) {
115 _Ops::iter_swap(__x4, __x5);
116 if (__comp(*__x4, *__x3)) {
117 _Ops::iter_swap(__x3, __x4);
118 if (__comp(*__x3, *__x2)) {
119 _Ops::iter_swap(__x2, __x3);
120 if (__comp(*__x2, *__x1)) {
121 _Ops::iter_swap(__x1, __x2);
122 }
123 }
124 }
125 }
126}
127
128// The comparator being simple is a prerequisite for using the branchless optimization.
129template <class _Tp>
130struct __is_simple_comparator : false_type {};
131template <>
132struct __is_simple_comparator<__less<>&> : true_type {};
133template <class _Tp>
134struct __is_simple_comparator<less<_Tp>&> : true_type {};
135template <class _Tp>
136struct __is_simple_comparator<greater<_Tp>&> : true_type {};
137
138template <class _Compare, class _Iter, class _Tp = typename iterator_traits<_Iter>::value_type>
139using __use_branchless_sort =
140 integral_constant<bool,
141 __libcpp_is_contiguous_iterator<_Iter>::value && sizeof(_Tp) <= sizeof(void*) &&
142 is_arithmetic<_Tp>::value && __is_simple_comparator<_Compare>::value>;
143
144namespace __detail {
145
146// Size in bits for the bitset in use.
147enum { __block_size = sizeof(uint64_t) * 8 };
148
149} // namespace __detail
150
151// Ensures that __c(*__x, *__y) is true by swapping *__x and *__y if necessary.
152template <class _Compare, class _RandomAccessIterator>
153inline _LIBCPP_HIDE_FROM_ABI void __cond_swap(_RandomAccessIterator __x, _RandomAccessIterator __y, _Compare __c) {
154 // Note: this function behaves correctly even with proxy iterators (because it relies on `value_type`).
155 using value_type = typename iterator_traits<_RandomAccessIterator>::value_type;
156 bool __r = __c(*__x, *__y);
157 value_type __tmp = __r ? *__x : *__y;
158 *__y = __r ? *__y : *__x;
159 *__x = __tmp;
160}
161
162// Ensures that *__x, *__y and *__z are ordered according to the comparator __c,
163// under the assumption that *__y and *__z are already ordered.
164template <class _Compare, class _RandomAccessIterator>
165inline _LIBCPP_HIDE_FROM_ABI void
166__partially_sorted_swap(_RandomAccessIterator __x, _RandomAccessIterator __y, _RandomAccessIterator __z, _Compare __c) {
167 // Note: this function behaves correctly even with proxy iterators (because it relies on `value_type`).
168 using value_type = typename iterator_traits<_RandomAccessIterator>::value_type;
169 bool __r = __c(*__z, *__x);
170 value_type __tmp = __r ? *__z : *__x;
171 *__z = __r ? *__x : *__z;
172 __r = __c(__tmp, *__y);
173 *__x = __r ? *__x : *__y;
174 *__y = __r ? *__y : __tmp;
175}
176
177template <class,
178 class _Compare,
179 class _RandomAccessIterator,
180 __enable_if_t<__use_branchless_sort<_Compare, _RandomAccessIterator>::value, int> = 0>
181inline _LIBCPP_HIDE_FROM_ABI void __sort3_maybe_branchless(
182 _RandomAccessIterator __x1, _RandomAccessIterator __x2, _RandomAccessIterator __x3, _Compare __c) {
183 std::__cond_swap<_Compare>(__x2, __x3, __c);
184 std::__partially_sorted_swap<_Compare>(__x1, __x2, __x3, __c);
185}
186
187template <class _AlgPolicy,
188 class _Compare,
189 class _RandomAccessIterator,
190 __enable_if_t<!__use_branchless_sort<_Compare, _RandomAccessIterator>::value, int> = 0>
191inline _LIBCPP_HIDE_FROM_ABI void __sort3_maybe_branchless(
192 _RandomAccessIterator __x1, _RandomAccessIterator __x2, _RandomAccessIterator __x3, _Compare __c) {
193 std::__sort3<_AlgPolicy, _Compare>(__x1, __x2, __x3, __c);
194}
195
196template <class,
197 class _Compare,
198 class _RandomAccessIterator,
199 __enable_if_t<__use_branchless_sort<_Compare, _RandomAccessIterator>::value, int> = 0>
200inline _LIBCPP_HIDE_FROM_ABI void __sort4_maybe_branchless(
201 _RandomAccessIterator __x1,
202 _RandomAccessIterator __x2,
203 _RandomAccessIterator __x3,
204 _RandomAccessIterator __x4,
205 _Compare __c) {
206 std::__cond_swap<_Compare>(__x1, __x3, __c);
207 std::__cond_swap<_Compare>(__x2, __x4, __c);
208 std::__cond_swap<_Compare>(__x1, __x2, __c);
209 std::__cond_swap<_Compare>(__x3, __x4, __c);
210 std::__cond_swap<_Compare>(__x2, __x3, __c);
211}
212
213template <class _AlgPolicy,
214 class _Compare,
215 class _RandomAccessIterator,
216 __enable_if_t<!__use_branchless_sort<_Compare, _RandomAccessIterator>::value, int> = 0>
217inline _LIBCPP_HIDE_FROM_ABI void __sort4_maybe_branchless(
218 _RandomAccessIterator __x1,
219 _RandomAccessIterator __x2,
220 _RandomAccessIterator __x3,
221 _RandomAccessIterator __x4,
222 _Compare __c) {
223 std::__sort4<_AlgPolicy, _Compare>(__x1, __x2, __x3, __x4, __c);
224}
225
226template <class _AlgPolicy,
227 class _Compare,
228 class _RandomAccessIterator,
229 __enable_if_t<__use_branchless_sort<_Compare, _RandomAccessIterator>::value, int> = 0>
230inline _LIBCPP_HIDE_FROM_ABI void __sort5_maybe_branchless(
231 _RandomAccessIterator __x1,
232 _RandomAccessIterator __x2,
233 _RandomAccessIterator __x3,
234 _RandomAccessIterator __x4,
235 _RandomAccessIterator __x5,
236 _Compare __c) {
237 std::__cond_swap<_Compare>(__x1, __x2, __c);
238 std::__cond_swap<_Compare>(__x4, __x5, __c);
239 std::__partially_sorted_swap<_Compare>(__x3, __x4, __x5, __c);
240 std::__cond_swap<_Compare>(__x2, __x5, __c);
241 std::__partially_sorted_swap<_Compare>(__x1, __x3, __x4, __c);
242 std::__partially_sorted_swap<_Compare>(__x2, __x3, __x4, __c);
243}
244
245template <class _AlgPolicy,
246 class _Compare,
247 class _RandomAccessIterator,
248 __enable_if_t<!__use_branchless_sort<_Compare, _RandomAccessIterator>::value, int> = 0>
249inline _LIBCPP_HIDE_FROM_ABI void __sort5_maybe_branchless(
250 _RandomAccessIterator __x1,
251 _RandomAccessIterator __x2,
252 _RandomAccessIterator __x3,
253 _RandomAccessIterator __x4,
254 _RandomAccessIterator __x5,
255 _Compare __c) {
256 std::__sort5<_AlgPolicy, _Compare, _RandomAccessIterator>(
257 std::move(__x1), std::move(__x2), std::move(__x3), std::move(__x4), std::move(__x5), __c);
258}
259
260// Assumes size > 0
261template <class _AlgPolicy, class _Compare, class _BidirectionalIterator>
262_LIBCPP_HIDE_FROM_ABI void
263__selection_sort(_BidirectionalIterator __first, _BidirectionalIterator __last, _Compare __comp) {
264 _BidirectionalIterator __lm1 = __last;
265 for (--__lm1; __first != __lm1; ++__first) {
266 _BidirectionalIterator __i = std::__min_element<_Compare>(__first, __last, __comp);
267 if (__i != __first)
268 _IterOps<_AlgPolicy>::iter_swap(__first, __i);
269 }
270}
271
272// Sort the iterator range [__first, __last) using the comparator __comp using
273// the insertion sort algorithm.
274template <class _AlgPolicy, class _Compare, class _BidirectionalIterator>
275_LIBCPP_HIDE_FROM_ABI void
276__insertion_sort(_BidirectionalIterator __first, _BidirectionalIterator __last, _Compare __comp) {
277 using _Ops = _IterOps<_AlgPolicy>;
278
279 typedef typename iterator_traits<_BidirectionalIterator>::value_type value_type;
280 if (__first == __last)
281 return;
282 _BidirectionalIterator __i = __first;
283 for (++__i; __i != __last; ++__i) {
284 _BidirectionalIterator __j = __i;
285 --__j;
286 if (__comp(*__i, *__j)) {
287 value_type __t(_Ops::__iter_move(__i));
288 _BidirectionalIterator __k = __j;
289 __j = __i;
290 do {
291 *__j = _Ops::__iter_move(__k);
292 __j = __k;
293 } while (__j != __first && __comp(__t, *--__k));
294 *__j = std::move(__t);
295 }
296 }
297}
298
299// Sort the iterator range [__first, __last) using the comparator __comp using
300// the insertion sort algorithm. Insertion sort has two loops, outer and inner.
301// The implementation below has no bounds check (unguarded) for the inner loop.
302// Assumes that there is an element in the position (__first - 1) and that each
303// element in the input range is greater or equal to the element at __first - 1.
304template <class _AlgPolicy, class _Compare, class _RandomAccessIterator>
305_LIBCPP_HIDE_FROM_ABI void
306__insertion_sort_unguarded(_RandomAccessIterator const __first, _RandomAccessIterator __last, _Compare __comp) {
307 using _Ops = _IterOps<_AlgPolicy>;
308 typedef typename iterator_traits<_RandomAccessIterator>::difference_type difference_type;
309 typedef typename iterator_traits<_RandomAccessIterator>::value_type value_type;
310 if (__first == __last)
311 return;
312 const _RandomAccessIterator __leftmost = __first - difference_type(1);
313 (void)__leftmost; // can be unused when assertions are disabled
314 for (_RandomAccessIterator __i = __first + difference_type(1); __i != __last; ++__i) {
315 _RandomAccessIterator __j = __i - difference_type(1);
316 if (__comp(*__i, *__j)) {
317 value_type __t(_Ops::__iter_move(__i));
318 _RandomAccessIterator __k = __j;
319 __j = __i;
320 do {
321 *__j = _Ops::__iter_move(__k);
322 __j = __k;
323 _LIBCPP_ASSERT_VALID_ELEMENT_ACCESS(
324 __k != __leftmost,
325 "Would read out of bounds, does your comparator satisfy the strict-weak ordering requirement?");
326 } while (__comp(__t, *--__k)); // No need for bounds check due to the assumption stated above.
327 *__j = std::move(__t);
328 }
329 }
330}
331
332template <class _AlgPolicy, class _Comp, class _RandomAccessIterator>
333_LIBCPP_HIDE_FROM_ABI bool
334__insertion_sort_incomplete(_RandomAccessIterator __first, _RandomAccessIterator __last, _Comp __comp) {
335 using _Ops = _IterOps<_AlgPolicy>;
336
337 typedef typename iterator_traits<_RandomAccessIterator>::difference_type difference_type;
338 switch (__last - __first) {
339 case 0:
340 case 1:
341 return true;
342 case 2:
343 if (__comp(*--__last, *__first))
344 _Ops::iter_swap(__first, __last);
345 return true;
346 case 3:
347 std::__sort3_maybe_branchless<_AlgPolicy, _Comp>(__first, __first + difference_type(1), --__last, __comp);
348 return true;
349 case 4:
350 std::__sort4_maybe_branchless<_AlgPolicy, _Comp>(
351 __first, __first + difference_type(1), __first + difference_type(2), --__last, __comp);
352 return true;
353 case 5:
354 std::__sort5_maybe_branchless<_AlgPolicy, _Comp>(
355 __first,
356 __first + difference_type(1),
357 __first + difference_type(2),
358 __first + difference_type(3),
359 --__last,
360 __comp);
361 return true;
362 }
363 typedef typename iterator_traits<_RandomAccessIterator>::value_type value_type;
364 _RandomAccessIterator __j = __first + difference_type(2);
365 std::__sort3_maybe_branchless<_AlgPolicy, _Comp>(__first, __first + difference_type(1), __j, __comp);
366 const unsigned __limit = 8;
367 unsigned __count = 0;
368 for (_RandomAccessIterator __i = __j + difference_type(1); __i != __last; ++__i) {
369 if (__comp(*__i, *__j)) {
370 value_type __t(_Ops::__iter_move(__i));
371 _RandomAccessIterator __k = __j;
372 __j = __i;
373 do {
374 *__j = _Ops::__iter_move(__k);
375 __j = __k;
376 } while (__j != __first && __comp(__t, *--__k));
377 *__j = std::move(__t);
378 if (++__count == __limit)
379 return ++__i == __last;
380 }
381 __j = __i;
382 }
383 return true;
384}
385
386template <class _AlgPolicy, class _RandomAccessIterator>
387inline _LIBCPP_HIDE_FROM_ABI void __swap_bitmap_pos(
388 _RandomAccessIterator __first, _RandomAccessIterator __last, uint64_t& __left_bitset, uint64_t& __right_bitset) {
389 using _Ops = _IterOps<_AlgPolicy>;
390 typedef typename std::iterator_traits<_RandomAccessIterator>::difference_type difference_type;
391 // Swap one pair on each iteration as long as both bitsets have at least one
392 // element for swapping.
393 while (__left_bitset != 0 && __right_bitset != 0) {
394 difference_type __tz_left = __libcpp_ctz(__left_bitset);
395 __left_bitset = __libcpp_blsr(__left_bitset);
396 difference_type __tz_right = __libcpp_ctz(__right_bitset);
397 __right_bitset = __libcpp_blsr(__right_bitset);
398 _Ops::iter_swap(__first + __tz_left, __last - __tz_right);
399 }
400}
401
402template <class _Compare,
403 class _RandomAccessIterator,
404 class _ValueType = typename iterator_traits<_RandomAccessIterator>::value_type>
405inline _LIBCPP_HIDE_FROM_ABI void
406__populate_left_bitset(_RandomAccessIterator __first, _Compare __comp, _ValueType& __pivot, uint64_t& __left_bitset) {
407 // Possible vectorization. With a proper "-march" flag, the following loop
408 // will be compiled into a set of SIMD instructions.
409 _RandomAccessIterator __iter = __first;
410 for (int __j = 0; __j < __detail::__block_size;) {
411 bool __comp_result = !__comp(*__iter, __pivot);
412 __left_bitset |= (static_cast<uint64_t>(__comp_result) << __j);
413 __j++;
414 ++__iter;
415 }
416}
417
418template <class _Compare,
419 class _RandomAccessIterator,
420 class _ValueType = typename iterator_traits<_RandomAccessIterator>::value_type>
421inline _LIBCPP_HIDE_FROM_ABI void
422__populate_right_bitset(_RandomAccessIterator __lm1, _Compare __comp, _ValueType& __pivot, uint64_t& __right_bitset) {
423 // Possible vectorization. With a proper "-march" flag, the following loop
424 // will be compiled into a set of SIMD instructions.
425 _RandomAccessIterator __iter = __lm1;
426 for (int __j = 0; __j < __detail::__block_size;) {
427 bool __comp_result = __comp(*__iter, __pivot);
428 __right_bitset |= (static_cast<uint64_t>(__comp_result) << __j);
429 __j++;
430 --__iter;
431 }
432}
433
434template <class _AlgPolicy,
435 class _Compare,
436 class _RandomAccessIterator,
437 class _ValueType = typename iterator_traits<_RandomAccessIterator>::value_type>
438inline _LIBCPP_HIDE_FROM_ABI void __bitset_partition_partial_blocks(
439 _RandomAccessIterator& __first,
440 _RandomAccessIterator& __lm1,
441 _Compare __comp,
442 _ValueType& __pivot,
443 uint64_t& __left_bitset,
444 uint64_t& __right_bitset) {
445 typedef typename std::iterator_traits<_RandomAccessIterator>::difference_type difference_type;
446 difference_type __remaining_len = __lm1 - __first + 1;
447 difference_type __l_size;
448 difference_type __r_size;
449 if (__left_bitset == 0 && __right_bitset == 0) {
450 __l_size = __remaining_len / 2;
451 __r_size = __remaining_len - __l_size;
452 } else if (__left_bitset == 0) {
453 // We know at least one side is a full block.
454 __l_size = __remaining_len - __detail::__block_size;
455 __r_size = __detail::__block_size;
456 } else { // if (__right_bitset == 0)
457 __l_size = __detail::__block_size;
458 __r_size = __remaining_len - __detail::__block_size;
459 }
460 // Record the comparison outcomes for the elements currently on the left side.
461 if (__left_bitset == 0) {
462 _RandomAccessIterator __iter = __first;
463 for (int __j = 0; __j < __l_size; __j++) {
464 bool __comp_result = !__comp(*__iter, __pivot);
465 __left_bitset |= (static_cast<uint64_t>(__comp_result) << __j);
466 ++__iter;
467 }
468 }
469 // Record the comparison outcomes for the elements currently on the right
470 // side.
471 if (__right_bitset == 0) {
472 _RandomAccessIterator __iter = __lm1;
473 for (int __j = 0; __j < __r_size; __j++) {
474 bool __comp_result = __comp(*__iter, __pivot);
475 __right_bitset |= (static_cast<uint64_t>(__comp_result) << __j);
476 --__iter;
477 }
478 }
479 std::__swap_bitmap_pos<_AlgPolicy, _RandomAccessIterator>(__first, __lm1, __left_bitset, __right_bitset);
480 __first += (__left_bitset == 0) ? __l_size : 0;
481 __lm1 -= (__right_bitset == 0) ? __r_size : 0;
482}
483
484template <class _AlgPolicy, class _RandomAccessIterator>
485inline _LIBCPP_HIDE_FROM_ABI void __swap_bitmap_pos_within(
486 _RandomAccessIterator& __first, _RandomAccessIterator& __lm1, uint64_t& __left_bitset, uint64_t& __right_bitset) {
487 using _Ops = _IterOps<_AlgPolicy>;
488 typedef typename std::iterator_traits<_RandomAccessIterator>::difference_type difference_type;
489 if (__left_bitset) {
490 // Swap within the left side. Need to find set positions in the reverse
491 // order.
492 while (__left_bitset != 0) {
493 difference_type __tz_left = __detail::__block_size - 1 - __libcpp_clz(__left_bitset);
494 __left_bitset &= (static_cast<uint64_t>(1) << __tz_left) - 1;
495 _RandomAccessIterator __it = __first + __tz_left;
496 if (__it != __lm1) {
497 _Ops::iter_swap(__it, __lm1);
498 }
499 --__lm1;
500 }
501 __first = __lm1 + difference_type(1);
502 } else if (__right_bitset) {
503 // Swap within the right side. Need to find set positions in the reverse
504 // order.
505 while (__right_bitset != 0) {
506 difference_type __tz_right = __detail::__block_size - 1 - __libcpp_clz(__right_bitset);
507 __right_bitset &= (static_cast<uint64_t>(1) << __tz_right) - 1;
508 _RandomAccessIterator __it = __lm1 - __tz_right;
509 if (__it != __first) {
510 _Ops::iter_swap(__it, __first);
511 }
512 ++__first;
513 }
514 }
515}
516
517// Partition [__first, __last) using the comparator __comp. *__first has the
518// chosen pivot. Elements that are equivalent are kept to the left of the
519// pivot. Returns the iterator for the pivot and a bool value which is true if
520// the provided range is already sorted, false otherwise. We assume that the
521// length of the range is at least three elements.
522//
523// __bitset_partition uses bitsets for storing outcomes of the comparisons
524// between the pivot and other elements.
525template <class _AlgPolicy, class _RandomAccessIterator, class _Compare>
526_LIBCPP_HIDE_FROM_ABI std::pair<_RandomAccessIterator, bool>
527__bitset_partition(_RandomAccessIterator __first, _RandomAccessIterator __last, _Compare __comp) {
528 using _Ops = _IterOps<_AlgPolicy>;
529 typedef typename std::iterator_traits<_RandomAccessIterator>::value_type value_type;
530 typedef typename std::iterator_traits<_RandomAccessIterator>::difference_type difference_type;
531 _LIBCPP_ASSERT_INTERNAL(__last - __first >= difference_type(3), "");
532 const _RandomAccessIterator __begin = __first; // used for bounds checking, those are not moved around
533 const _RandomAccessIterator __end = __last;
534 (void)__end; //
535
536 value_type __pivot(_Ops::__iter_move(__first));
537 // Find the first element greater than the pivot.
538 if (__comp(__pivot, *(__last - difference_type(1)))) {
539 // Not guarded since we know the last element is greater than the pivot.
540 do {
541 ++__first;
542 _LIBCPP_ASSERT_VALID_ELEMENT_ACCESS(
543 __first != __end,
544 "Would read out of bounds, does your comparator satisfy the strict-weak ordering requirement?");
545 } while (!__comp(__pivot, *__first));
546 } else {
547 while (++__first < __last && !__comp(__pivot, *__first)) {
548 }
549 }
550 // Find the last element less than or equal to the pivot.
551 if (__first < __last) {
552 // It will be always guarded because __introsort will do the median-of-three
553 // before calling this.
554 do {
555 _LIBCPP_ASSERT_VALID_ELEMENT_ACCESS(
556 __last != __begin,
557 "Would read out of bounds, does your comparator satisfy the strict-weak ordering requirement?");
558 --__last;
559 } while (__comp(__pivot, *__last));
560 }
561 // If the first element greater than the pivot is at or after the
562 // last element less than or equal to the pivot, then we have covered the
563 // entire range without swapping elements. This implies the range is already
564 // partitioned.
565 bool __already_partitioned = __first >= __last;
566 if (!__already_partitioned) {
567 _Ops::iter_swap(__first, __last);
568 ++__first;
569 }
570
571 // In [__first, __last) __last is not inclusive. From now on, it uses last
572 // minus one to be inclusive on both sides.
573 _RandomAccessIterator __lm1 = __last - difference_type(1);
574 uint64_t __left_bitset = 0;
575 uint64_t __right_bitset = 0;
576
577 // Reminder: length = __lm1 - __first + 1.
578 while (__lm1 - __first >= 2 * __detail::__block_size - 1) {
579 // Record the comparison outcomes for the elements currently on the left
580 // side.
581 if (__left_bitset == 0)
582 std::__populate_left_bitset<_Compare>(__first, __comp, __pivot, __left_bitset);
583 // Record the comparison outcomes for the elements currently on the right
584 // side.
585 if (__right_bitset == 0)
586 std::__populate_right_bitset<_Compare>(__lm1, __comp, __pivot, __right_bitset);
587 // Swap the elements recorded to be the candidates for swapping in the
588 // bitsets.
589 std::__swap_bitmap_pos<_AlgPolicy, _RandomAccessIterator>(__first, __lm1, __left_bitset, __right_bitset);
590 // Only advance the iterator if all the elements that need to be moved to
591 // other side were moved.
592 __first += (__left_bitset == 0) ? difference_type(__detail::__block_size) : difference_type(0);
593 __lm1 -= (__right_bitset == 0) ? difference_type(__detail::__block_size) : difference_type(0);
594 }
595 // Now, we have a less-than a block worth of elements on at least one of the
596 // sides.
597 std::__bitset_partition_partial_blocks<_AlgPolicy, _Compare>(
598 __first, __lm1, __comp, __pivot, __left_bitset, __right_bitset);
599 // At least one the bitsets would be empty. For the non-empty one, we need to
600 // properly partition the elements that appear within that bitset.
601 std::__swap_bitmap_pos_within<_AlgPolicy>(__first, __lm1, __left_bitset, __right_bitset);
602
603 // Move the pivot to its correct position.
604 _RandomAccessIterator __pivot_pos = __first - difference_type(1);
605 if (__begin != __pivot_pos) {
606 *__begin = _Ops::__iter_move(__pivot_pos);
607 }
608 *__pivot_pos = std::move(__pivot);
609 return std::make_pair(__pivot_pos, __already_partitioned);
610}
611
612// Partition [__first, __last) using the comparator __comp. *__first has the
613// chosen pivot. Elements that are equivalent are kept to the right of the
614// pivot. Returns the iterator for the pivot and a bool value which is true if
615// the provided range is already sorted, false otherwise. We assume that the
616// length of the range is at least three elements.
617template <class _AlgPolicy, class _RandomAccessIterator, class _Compare>
618_LIBCPP_HIDE_FROM_ABI std::pair<_RandomAccessIterator, bool>
619__partition_with_equals_on_right(_RandomAccessIterator __first, _RandomAccessIterator __last, _Compare __comp) {
620 using _Ops = _IterOps<_AlgPolicy>;
621 typedef typename iterator_traits<_RandomAccessIterator>::difference_type difference_type;
622 typedef typename std::iterator_traits<_RandomAccessIterator>::value_type value_type;
623 _LIBCPP_ASSERT_INTERNAL(__last - __first >= difference_type(3), "");
624 const _RandomAccessIterator __begin = __first; // used for bounds checking, those are not moved around
625 const _RandomAccessIterator __end = __last;
626 (void)__end; //
627 value_type __pivot(_Ops::__iter_move(__first));
628 // Find the first element greater or equal to the pivot. It will be always
629 // guarded because __introsort will do the median-of-three before calling
630 // this.
631 do {
632 ++__first;
633 _LIBCPP_ASSERT_VALID_ELEMENT_ACCESS(
634 __first != __end,
635 "Would read out of bounds, does your comparator satisfy the strict-weak ordering requirement?");
636 } while (__comp(*__first, __pivot));
637
638 // Find the last element less than the pivot.
639 if (__begin == __first - difference_type(1)) {
640 while (__first < __last && !__comp(*--__last, __pivot))
641 ;
642 } else {
643 // Guarded.
644 do {
645 _LIBCPP_ASSERT_VALID_ELEMENT_ACCESS(
646 __last != __begin,
647 "Would read out of bounds, does your comparator satisfy the strict-weak ordering requirement?");
648 --__last;
649 } while (!__comp(*__last, __pivot));
650 }
651
652 // If the first element greater than or equal to the pivot is at or after the
653 // last element less than the pivot, then we have covered the entire range
654 // without swapping elements. This implies the range is already partitioned.
655 bool __already_partitioned = __first >= __last;
656 // Go through the remaining elements. Swap pairs of elements (one to the
657 // right of the pivot and the other to left of the pivot) that are not on the
658 // correct side of the pivot.
659 while (__first < __last) {
660 _Ops::iter_swap(__first, __last);
661 do {
662 ++__first;
663 _LIBCPP_ASSERT_VALID_ELEMENT_ACCESS(
664 __first != __end,
665 "Would read out of bounds, does your comparator satisfy the strict-weak ordering requirement?");
666 } while (__comp(*__first, __pivot));
667 do {
668 _LIBCPP_ASSERT_VALID_ELEMENT_ACCESS(
669 __last != __begin,
670 "Would read out of bounds, does your comparator satisfy the strict-weak ordering requirement?");
671 --__last;
672 } while (!__comp(*__last, __pivot));
673 }
674 // Move the pivot to its correct position.
675 _RandomAccessIterator __pivot_pos = __first - difference_type(1);
676 if (__begin != __pivot_pos) {
677 *__begin = _Ops::__iter_move(__pivot_pos);
678 }
679 *__pivot_pos = std::move(__pivot);
680 return std::make_pair(__pivot_pos, __already_partitioned);
681}
682
683// Similar to the above function. Elements equivalent to the pivot are put to
684// the left of the pivot. Returns the iterator to the pivot element.
685template <class _AlgPolicy, class _RandomAccessIterator, class _Compare>
686_LIBCPP_HIDE_FROM_ABI _RandomAccessIterator
687__partition_with_equals_on_left(_RandomAccessIterator __first, _RandomAccessIterator __last, _Compare __comp) {
688 using _Ops = _IterOps<_AlgPolicy>;
689 typedef typename iterator_traits<_RandomAccessIterator>::difference_type difference_type;
690 typedef typename std::iterator_traits<_RandomAccessIterator>::value_type value_type;
691 const _RandomAccessIterator __begin = __first; // used for bounds checking, those are not moved around
692 const _RandomAccessIterator __end = __last;
693 (void)__end; //
694 value_type __pivot(_Ops::__iter_move(__first));
695 if (__comp(__pivot, *(__last - difference_type(1)))) {
696 // Guarded.
697 do {
698 ++__first;
699 _LIBCPP_ASSERT_VALID_ELEMENT_ACCESS(
700 __first != __end,
701 "Would read out of bounds, does your comparator satisfy the strict-weak ordering requirement?");
702 } while (!__comp(__pivot, *__first));
703 } else {
704 while (++__first < __last && !__comp(__pivot, *__first)) {
705 }
706 }
707
708 if (__first < __last) {
709 // It will be always guarded because __introsort will do the
710 // median-of-three before calling this.
711 do {
712 _LIBCPP_ASSERT_VALID_ELEMENT_ACCESS(
713 __last != __begin,
714 "Would read out of bounds, does your comparator satisfy the strict-weak ordering requirement?");
715 --__last;
716 } while (__comp(__pivot, *__last));
717 }
718 while (__first < __last) {
719 _Ops::iter_swap(__first, __last);
720 do {
721 ++__first;
722 _LIBCPP_ASSERT_VALID_ELEMENT_ACCESS(
723 __first != __end,
724 "Would read out of bounds, does your comparator satisfy the strict-weak ordering requirement?");
725 } while (!__comp(__pivot, *__first));
726 do {
727 _LIBCPP_ASSERT_VALID_ELEMENT_ACCESS(
728 __last != __begin,
729 "Would read out of bounds, does your comparator satisfy the strict-weak ordering requirement?");
730 --__last;
731 } while (__comp(__pivot, *__last));
732 }
733 _RandomAccessIterator __pivot_pos = __first - difference_type(1);
734 if (__begin != __pivot_pos) {
735 *__begin = _Ops::__iter_move(__pivot_pos);
736 }
737 *__pivot_pos = std::move(__pivot);
738 return __first;
739}
740
741// The main sorting function. Implements introsort combined with other ideas:
742// - option of using block quick sort for partitioning,
743// - guarded and unguarded insertion sort for small lengths,
744// - Tuckey's ninther technique for computing the pivot,
745// - check on whether partition was not required.
746// The implementation is partly based on Orson Peters' pattern-defeating
747// quicksort, published at: <https://github.com/orlp/pdqsort>.
748template <class _AlgPolicy, class _Compare, class _RandomAccessIterator, bool _UseBitSetPartition>
749void __introsort(_RandomAccessIterator __first,
750 _RandomAccessIterator __last,
751 _Compare __comp,
752 typename iterator_traits<_RandomAccessIterator>::difference_type __depth,
753 bool __leftmost = true) {
754 using _Ops = _IterOps<_AlgPolicy>;
755 typedef typename iterator_traits<_RandomAccessIterator>::difference_type difference_type;
756 using _Comp_ref = __comp_ref_type<_Compare>;
757 // Upper bound for using insertion sort for sorting.
758 difference_type __limit = 24;
759 // Lower bound for using Tuckey's ninther technique for median computation.
760 difference_type __ninther_threshold = 128;
761 while (true) {
762 difference_type __len = __last - __first;
763 switch (__len) {
764 case 0:
765 case 1:
766 return;
767 case 2:
768 if (__comp(*--__last, *__first))
769 _Ops::iter_swap(__first, __last);
770 return;
771 case 3:
772 std::__sort3_maybe_branchless<_AlgPolicy, _Compare>(__first, __first + difference_type(1), --__last, __comp);
773 return;
774 case 4:
775 std::__sort4_maybe_branchless<_AlgPolicy, _Compare>(
776 __first, __first + difference_type(1), __first + difference_type(2), --__last, __comp);
777 return;
778 case 5:
779 std::__sort5_maybe_branchless<_AlgPolicy, _Compare>(
780 __first,
781 __first + difference_type(1),
782 __first + difference_type(2),
783 __first + difference_type(3),
784 --__last,
785 __comp);
786 return;
787 }
788 // Use insertion sort if the length of the range is below the specified limit.
789 if (__len < __limit) {
790 if (__leftmost) {
791 std::__insertion_sort<_AlgPolicy, _Compare>(__first, __last, __comp);
792 } else {
793 std::__insertion_sort_unguarded<_AlgPolicy, _Compare>(__first, __last, __comp);
794 }
795 return;
796 }
797 if (__depth == 0) {
798 // Fallback to heap sort as Introsort suggests.
799 std::__partial_sort<_AlgPolicy, _Compare>(__first, __last, __last, __comp);
800 return;
801 }
802 --__depth;
803 {
804 difference_type __half_len = __len / 2;
805 // Use Tuckey's ninther technique or median of 3 for pivot selection
806 // depending on the length of the range being sorted.
807 if (__len > __ninther_threshold) {
808 std::__sort3<_AlgPolicy, _Compare>(__first, __first + __half_len, __last - difference_type(1), __comp);
809 std::__sort3<_AlgPolicy, _Compare>(
810 __first + difference_type(1), __first + (__half_len - 1), __last - difference_type(2), __comp);
811 std::__sort3<_AlgPolicy, _Compare>(
812 __first + difference_type(2), __first + (__half_len + 1), __last - difference_type(3), __comp);
813 std::__sort3<_AlgPolicy, _Compare>(
814 __first + (__half_len - 1), __first + __half_len, __first + (__half_len + 1), __comp);
815 _Ops::iter_swap(__first, __first + __half_len);
816 } else {
817 std::__sort3<_AlgPolicy, _Compare>(__first + __half_len, __first, __last - difference_type(1), __comp);
818 }
819 }
820 // The elements to the left of the current iterator range are already
821 // sorted. If the current iterator range to be sorted is not the
822 // leftmost part of the entire iterator range and the pivot is same as
823 // the highest element in the range to the left, then we know that all
824 // the elements in the range [first, pivot] would be equal to the pivot,
825 // assuming the equal elements are put on the left side when
826 // partitioned. This also means that we do not need to sort the left
827 // side of the partition.
828 if (!__leftmost && !__comp(*(__first - difference_type(1)), *__first)) {
829 __first = std::__partition_with_equals_on_left<_AlgPolicy, _RandomAccessIterator, _Comp_ref>(
830 __first, __last, _Comp_ref(__comp));
831 continue;
832 }
833 // Use bitset partition only if asked for.
834 auto __ret = _UseBitSetPartition
835 ? std::__bitset_partition<_AlgPolicy, _RandomAccessIterator, _Compare>(__first, __last, __comp)
836 : std::__partition_with_equals_on_right<_AlgPolicy, _RandomAccessIterator, _Compare>(
837 __first, __last, __comp);
838 _RandomAccessIterator __i = __ret.first;
839 // [__first, __i) < *__i and *__i <= [__i+1, __last)
840 // If we were given a perfect partition, see if insertion sort is quick...
841 if (__ret.second) {
842 bool __fs = std::__insertion_sort_incomplete<_AlgPolicy, _Compare>(__first, __i, __comp);
843 if (std::__insertion_sort_incomplete<_AlgPolicy, _Compare>(__i + difference_type(1), __last, __comp)) {
844 if (__fs)
845 return;
846 __last = __i;
847 continue;
848 } else {
849 if (__fs) {
850 __first = ++__i;
851 continue;
852 }
853 }
854 }
855 // Sort the left partiton recursively and the right partition with tail recursion elimination.
856 std::__introsort<_AlgPolicy, _Compare, _RandomAccessIterator, _UseBitSetPartition>(
857 __first, __i, __comp, __depth, __leftmost);
858 __leftmost = false;
859 __first = ++__i;
860 }
861}
862
863template <typename _Number>
864inline _LIBCPP_HIDE_FROM_ABI _Number __log2i(_Number __n) {
865 if (__n == 0)
866 return 0;
867 if (sizeof(__n) <= sizeof(unsigned))
868 return sizeof(unsigned) * CHAR_BIT - 1 - __libcpp_clz(static_cast<unsigned>(__n));
869 if (sizeof(__n) <= sizeof(unsigned long))
870 return sizeof(unsigned long) * CHAR_BIT - 1 - __libcpp_clz(static_cast<unsigned long>(__n));
871 if (sizeof(__n) <= sizeof(unsigned long long))
872 return sizeof(unsigned long long) * CHAR_BIT - 1 - __libcpp_clz(static_cast<unsigned long long>(__n));
873
874 _Number __log2 = 0;
875 while (__n > 1) {
876 __log2++;
877 __n >>= 1;
878 }
879 return __log2;
880}
881
882template <class _Comp, class _RandomAccessIterator>
883void __sort(_RandomAccessIterator, _RandomAccessIterator, _Comp);
884
885extern template _LIBCPP_EXPORTED_FROM_ABI void __sort<__less<char>&, char*>(char*, char*, __less<char>&);
886#ifndef _LIBCPP_HAS_NO_WIDE_CHARACTERS
887extern template _LIBCPP_EXPORTED_FROM_ABI void __sort<__less<wchar_t>&, wchar_t*>(wchar_t*, wchar_t*, __less<wchar_t>&);
888#endif
889extern template _LIBCPP_EXPORTED_FROM_ABI void
890__sort<__less<signed char>&, signed char*>(signed char*, signed char*, __less<signed char>&);
891extern template _LIBCPP_EXPORTED_FROM_ABI void
892__sort<__less<unsigned char>&, unsigned char*>(unsigned char*, unsigned char*, __less<unsigned char>&);
893extern template _LIBCPP_EXPORTED_FROM_ABI void __sort<__less<short>&, short*>(short*, short*, __less<short>&);
894extern template _LIBCPP_EXPORTED_FROM_ABI void
895__sort<__less<unsigned short>&, unsigned short*>(unsigned short*, unsigned short*, __less<unsigned short>&);
896extern template _LIBCPP_EXPORTED_FROM_ABI void __sort<__less<int>&, int*>(int*, int*, __less<int>&);
897extern template _LIBCPP_EXPORTED_FROM_ABI void
898__sort<__less<unsigned>&, unsigned*>(unsigned*, unsigned*, __less<unsigned>&);
899extern template _LIBCPP_EXPORTED_FROM_ABI void __sort<__less<long>&, long*>(long*, long*, __less<long>&);
900extern template _LIBCPP_EXPORTED_FROM_ABI void
901__sort<__less<unsigned long>&, unsigned long*>(unsigned long*, unsigned long*, __less<unsigned long>&);
902extern template _LIBCPP_EXPORTED_FROM_ABI void
903__sort<__less<long long>&, long long*>(long long*, long long*, __less<long long>&);
904extern template _LIBCPP_EXPORTED_FROM_ABI void __sort<__less<unsigned long long>&, unsigned long long*>(
905 unsigned long long*, unsigned long long*, __less<unsigned long long>&);
906extern template _LIBCPP_EXPORTED_FROM_ABI void __sort<__less<float>&, float*>(float*, float*, __less<float>&);
907extern template _LIBCPP_EXPORTED_FROM_ABI void __sort<__less<double>&, double*>(double*, double*, __less<double>&);
908extern template _LIBCPP_EXPORTED_FROM_ABI void
909__sort<__less<long double>&, long double*>(long double*, long double*, __less<long double>&);
910
911template <class _AlgPolicy, class _RandomAccessIterator, class _Comp>
912_LIBCPP_HIDE_FROM_ABI void __sort_dispatch(_RandomAccessIterator __first, _RandomAccessIterator __last, _Comp& __comp) {
913 typedef typename iterator_traits<_RandomAccessIterator>::difference_type difference_type;
914 difference_type __depth_limit = 2 * std::__log2i(__last - __first);
915
916 // Only use bitset partitioning for arithmetic types. We should also check
917 // that the default comparator is in use so that we are sure that there are no
918 // branches in the comparator.
919 std::__introsort<_AlgPolicy,
920 _Comp&,
921 _RandomAccessIterator,
922 __use_branchless_sort<_Comp, _RandomAccessIterator>::value>(__first, __last, __comp, __depth_limit);
923}
924
925template <class _Type, class... _Options>
926using __is_any_of = _Or<is_same<_Type, _Options>...>;
927
928template <class _Type>
929using __sort_is_specialized_in_library = __is_any_of<
930 _Type,
931 char,
932#ifndef _LIBCPP_HAS_NO_WIDE_CHARACTERS
933 wchar_t,
934#endif
935 signed char,
936 unsigned char,
937 short,
938 unsigned short,
939 int,
940 unsigned int,
941 long,
942 unsigned long,
943 long long,
944 unsigned long long,
945 float,
946 double,
947 long double>;
948
949template <class _AlgPolicy, class _Type, __enable_if_t<__sort_is_specialized_in_library<_Type>::value, int> = 0>
950_LIBCPP_HIDE_FROM_ABI void __sort_dispatch(_Type* __first, _Type* __last, __less<>&) {
951 __less<_Type> __comp;
952 std::__sort<__less<_Type>&, _Type*>(__first, __last, __comp);
953}
954
955template <class _AlgPolicy, class _Type, __enable_if_t<__sort_is_specialized_in_library<_Type>::value, int> = 0>
956_LIBCPP_HIDE_FROM_ABI void __sort_dispatch(_Type* __first, _Type* __last, less<_Type>&) {
957 __less<_Type> __comp;
958 std::__sort<__less<_Type>&, _Type*>(__first, __last, __comp);
959}
960
961template <class _AlgPolicy, class _RandomAccessIterator, class _Comp>
962inline _LIBCPP_HIDE_FROM_ABI void
963__sort_impl(_RandomAccessIterator __first, _RandomAccessIterator __last, _Comp& __comp) {
964 std::__debug_randomize_range<_AlgPolicy>(__first, __last);
965
966 if (__libcpp_is_constant_evaluated()) {
967 std::__partial_sort<_AlgPolicy>(
968 std::__unwrap_iter(__first), std::__unwrap_iter(__last), std::__unwrap_iter(__last), __comp);
969 } else {
970 std::__sort_dispatch<_AlgPolicy>(std::__unwrap_iter(__first), std::__unwrap_iter(__last), __comp);
971 }
972 std::__check_strict_weak_ordering_sorted(std::__unwrap_iter(__first), std::__unwrap_iter(__last), __comp);
973}
974
975template <class _RandomAccessIterator, class _Comp>
976inline _LIBCPP_HIDE_FROM_ABI void sort(_RandomAccessIterator __first, _RandomAccessIterator __last, _Comp __comp) {
977 std::__sort_impl<_ClassicAlgPolicy>(std::move(__first), std::move(__last), __comp);
978}
979
980template <class _RandomAccessIterator>
981inline _LIBCPP_HIDE_FROM_ABI void sort(_RandomAccessIterator __first, _RandomAccessIterator __last) {
982 std::sort(__first, __last, __less<>());
983}
984
985_LIBCPP_END_NAMESPACE_STD
986
987_LIBCPP_POP_MACROS
988
989#endif // _LIBCPP___CXX03___ALGORITHM_SORT_H
990

Warning: This file is not a C or C++ file. It does not have highlighting.

source code of libcxx/include/__cxx03/__algorithm/sort.h