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