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