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/iterator_operations.h> 15#include <__algorithm/min_element.h> 16#include <__algorithm/partial_sort.h> 17#include <__algorithm/unwrap_iter.h> 18#include <__config> 19#include <__debug> 20#include <__debug_utils/randomize_range.h> 21#include <__functional/operations.h> 22#include <__functional/ranges_operations.h> 23#include <__iterator/iterator_traits.h> 24#include <__memory/destruct_n.h> 25#include <__memory/unique_ptr.h> 26#include <__type_traits/is_arithmetic.h> 27#include <__type_traits/is_trivially_copy_assignable.h> 28#include <__type_traits/is_trivially_copy_constructible.h> 29#include <__utility/move.h> 30#include <bit> 31#include <climits> 32#include <cstdint> 33 34#if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER) 35# pragma GCC system_header 36#endif 37 38_LIBCPP_BEGIN_NAMESPACE_STD 39 40// Wraps an algorithm policy tag and a comparator in a single struct, used to pass the policy tag around without 41// changing the number of template arguments (to keep the ABI stable). This is only used for the "range" policy tag. 42// 43// To create an object of this type, use `_WrapAlgPolicy<T, C>::type` -- see the specialization below for the rationale. 44template <class _PolicyT, class _CompT, class = void> 45struct _WrapAlgPolicy { 46 using type = _WrapAlgPolicy; 47 48 using _AlgPolicy = _PolicyT; 49 using _Comp = _CompT; 50 _Comp& __comp; 51 52 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX14 53 _WrapAlgPolicy(_Comp& __c) : __comp(__c) {} 54}; 55 56// Specialization for the "classic" policy tag that avoids creating a struct and simply defines an alias for the 57// comparator. When unwrapping, a pristine comparator is always considered to have the "classic" tag attached. Passing 58// the pristine comparator where possible allows using template instantiations from the dylib. 59template <class _PolicyT, class _CompT> 60struct _WrapAlgPolicy<_PolicyT, _CompT, __enable_if_t<std::is_same<_PolicyT, _ClassicAlgPolicy>::value> > { 61 using type = _CompT; 62}; 63 64// Unwraps a pristine functor (e.g. `std::less`) as if it were wrapped using `_WrapAlgPolicy`. The policy tag is always 65// set to "classic". 66template <class _CompT> 67struct _UnwrapAlgPolicy { 68 using _AlgPolicy = _ClassicAlgPolicy; 69 using _Comp = _CompT; 70 71 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX14 static 72 _Comp __get_comp(_Comp __comp) { return __comp; } 73}; 74 75// Unwraps a `_WrapAlgPolicy` struct. 76template <class... _Ts> 77struct _UnwrapAlgPolicy<_WrapAlgPolicy<_Ts...> > { 78 using _Wrapped = _WrapAlgPolicy<_Ts...>; 79 using _AlgPolicy = typename _Wrapped::_AlgPolicy; 80 using _Comp = typename _Wrapped::_Comp; 81 82 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX14 static 83 _Comp __get_comp(_Wrapped& __w) { return __w.__comp; } 84}; 85 86// stable, 2-3 compares, 0-2 swaps 87 88template <class _AlgPolicy, class _Compare, class _ForwardIterator> 89_LIBCPP_HIDE_FROM_ABI 90_LIBCPP_CONSTEXPR_SINCE_CXX14 unsigned __sort3(_ForwardIterator __x, _ForwardIterator __y, _ForwardIterator __z, 91 _Compare __c) { 92 using _Ops = _IterOps<_AlgPolicy>; 93 94 unsigned __r = 0; 95 if (!__c(*__y, *__x)) // if x <= y 96 { 97 if (!__c(*__z, *__y)) // if y <= z 98 return __r; // x <= y && y <= z 99 // x <= y && y > z 100 _Ops::iter_swap(__y, __z); // x <= z && y < z 101 __r = 1; 102 if (__c(*__y, *__x)) // if x > y 103 { 104 _Ops::iter_swap(__x, __y); // x < y && y <= z 105 __r = 2; 106 } 107 return __r; // x <= y && y < z 108 } 109 if (__c(*__z, *__y)) // x > y, if y > z 110 { 111 _Ops::iter_swap(__x, __z); // x < y && y < z 112 __r = 1; 113 return __r; 114 } 115 _Ops::iter_swap(__x, __y); // x > y && y <= z 116 __r = 1; // x < y && x <= z 117 if (__c(*__z, *__y)) // if y > z 118 { 119 _Ops::iter_swap(__y, __z); // x <= y && y < z 120 __r = 2; 121 } 122 return __r; 123} // x <= y && y <= z 124 125// stable, 3-6 compares, 0-5 swaps 126 127template <class _AlgPolicy, class _Compare, class _ForwardIterator> 128_LIBCPP_HIDE_FROM_ABI 129unsigned __sort4(_ForwardIterator __x1, _ForwardIterator __x2, _ForwardIterator __x3, _ForwardIterator __x4, 130 _Compare __c) { 131 using _Ops = _IterOps<_AlgPolicy>; 132 133 unsigned __r = std::__sort3<_AlgPolicy, _Compare>(__x1, __x2, __x3, __c); 134 if (__c(*__x4, *__x3)) { 135 _Ops::iter_swap(__x3, __x4); 136 ++__r; 137 if (__c(*__x3, *__x2)) { 138 _Ops::iter_swap(__x2, __x3); 139 ++__r; 140 if (__c(*__x2, *__x1)) { 141 _Ops::iter_swap(__x1, __x2); 142 ++__r; 143 } 144 } 145 } 146 return __r; 147} 148 149// stable, 4-10 compares, 0-9 swaps 150 151template <class _WrappedComp, class _ForwardIterator> 152_LIBCPP_HIDDEN unsigned __sort5(_ForwardIterator __x1, _ForwardIterator __x2, _ForwardIterator __x3, 153 _ForwardIterator __x4, _ForwardIterator __x5, _WrappedComp __wrapped_comp) { 154 using _Unwrap = _UnwrapAlgPolicy<_WrappedComp>; 155 using _AlgPolicy = typename _Unwrap::_AlgPolicy; 156 using _Ops = _IterOps<_AlgPolicy>; 157 158 using _Compare = typename _Unwrap::_Comp; 159 _Compare __c = _Unwrap::__get_comp(__wrapped_comp); 160 161 unsigned __r = std::__sort4<_AlgPolicy, _Compare>(__x1, __x2, __x3, __x4, __c); 162 if (__c(*__x5, *__x4)) { 163 _Ops::iter_swap(__x4, __x5); 164 ++__r; 165 if (__c(*__x4, *__x3)) { 166 _Ops::iter_swap(__x3, __x4); 167 ++__r; 168 if (__c(*__x3, *__x2)) { 169 _Ops::iter_swap(__x2, __x3); 170 ++__r; 171 if (__c(*__x2, *__x1)) { 172 _Ops::iter_swap(__x1, __x2); 173 ++__r; 174 } 175 } 176 } 177 } 178 return __r; 179} 180 181template <class _AlgPolicy, class _Compare, class _ForwardIterator> 182_LIBCPP_HIDE_FROM_ABI unsigned __sort5_wrap_policy( 183 _ForwardIterator __x1, _ForwardIterator __x2, _ForwardIterator __x3, _ForwardIterator __x4, _ForwardIterator __x5, 184 _Compare __c) { 185 using _WrappedComp = typename _WrapAlgPolicy<_AlgPolicy, _Compare>::type; 186 _WrappedComp __wrapped_comp(__c); 187 return std::__sort5<_WrappedComp>( 188 std::move(__x1), std::move(__x2), std::move(__x3), std::move(__x4), std::move(__x5), __wrapped_comp); 189} 190 191// The comparator being simple is a prerequisite for using the branchless optimization. 192template <class _Tp> 193struct __is_simple_comparator : false_type {}; 194template <class _Tp> 195struct __is_simple_comparator<__less<_Tp>&> : true_type {}; 196template <class _Tp> 197struct __is_simple_comparator<less<_Tp>&> : true_type {}; 198template <class _Tp> 199struct __is_simple_comparator<greater<_Tp>&> : true_type {}; 200#if _LIBCPP_STD_VER > 17 201template <> 202struct __is_simple_comparator<ranges::less&> : true_type {}; 203template <> 204struct __is_simple_comparator<ranges::greater&> : true_type {}; 205#endif 206 207template <class _Compare, class _Iter, class _Tp = typename iterator_traits<_Iter>::value_type> 208using __use_branchless_sort = 209 integral_constant<bool, __is_cpp17_contiguous_iterator<_Iter>::value && sizeof(_Tp) <= sizeof(void*) && 210 is_arithmetic<_Tp>::value && __is_simple_comparator<_Compare>::value>; 211 212// Ensures that __c(*__x, *__y) is true by swapping *__x and *__y if necessary. 213template <class _Compare, class _RandomAccessIterator> 214inline _LIBCPP_HIDE_FROM_ABI void __cond_swap(_RandomAccessIterator __x, _RandomAccessIterator __y, _Compare __c) { 215 // Note: this function behaves correctly even with proxy iterators (because it relies on `value_type`). 216 using value_type = typename iterator_traits<_RandomAccessIterator>::value_type; 217 bool __r = __c(*__x, *__y); 218 value_type __tmp = __r ? *__x : *__y; 219 *__y = __r ? *__y : *__x; 220 *__x = __tmp; 221} 222 223// Ensures that *__x, *__y and *__z are ordered according to the comparator __c, 224// under the assumption that *__y and *__z are already ordered. 225template <class _Compare, class _RandomAccessIterator> 226inline _LIBCPP_HIDE_FROM_ABI void __partially_sorted_swap(_RandomAccessIterator __x, _RandomAccessIterator __y, 227 _RandomAccessIterator __z, _Compare __c) { 228 // Note: this function behaves correctly even with proxy iterators (because it relies on `value_type`). 229 using value_type = typename iterator_traits<_RandomAccessIterator>::value_type; 230 bool __r = __c(*__z, *__x); 231 value_type __tmp = __r ? *__z : *__x; 232 *__z = __r ? *__x : *__z; 233 __r = __c(__tmp, *__y); 234 *__x = __r ? *__x : *__y; 235 *__y = __r ? *__y : __tmp; 236} 237 238template <class, class _Compare, class _RandomAccessIterator> 239inline _LIBCPP_HIDE_FROM_ABI __enable_if_t<__use_branchless_sort<_Compare, _RandomAccessIterator>::value, void> 240__sort3_maybe_branchless(_RandomAccessIterator __x1, _RandomAccessIterator __x2, _RandomAccessIterator __x3, 241 _Compare __c) { 242 std::__cond_swap<_Compare>(__x2, __x3, __c); 243 std::__partially_sorted_swap<_Compare>(__x1, __x2, __x3, __c); 244} 245 246template <class _AlgPolicy, class _Compare, class _RandomAccessIterator> 247inline _LIBCPP_HIDE_FROM_ABI __enable_if_t<!__use_branchless_sort<_Compare, _RandomAccessIterator>::value, void> 248__sort3_maybe_branchless(_RandomAccessIterator __x1, _RandomAccessIterator __x2, _RandomAccessIterator __x3, 249 _Compare __c) { 250 std::__sort3<_AlgPolicy, _Compare>(__x1, __x2, __x3, __c); 251} 252 253template <class, class _Compare, class _RandomAccessIterator> 254inline _LIBCPP_HIDE_FROM_ABI __enable_if_t<__use_branchless_sort<_Compare, _RandomAccessIterator>::value, void> 255__sort4_maybe_branchless(_RandomAccessIterator __x1, _RandomAccessIterator __x2, _RandomAccessIterator __x3, 256 _RandomAccessIterator __x4, _Compare __c) { 257 std::__cond_swap<_Compare>(__x1, __x3, __c); 258 std::__cond_swap<_Compare>(__x2, __x4, __c); 259 std::__cond_swap<_Compare>(__x1, __x2, __c); 260 std::__cond_swap<_Compare>(__x3, __x4, __c); 261 std::__cond_swap<_Compare>(__x2, __x3, __c); 262} 263 264template <class _AlgPolicy, class _Compare, class _RandomAccessIterator> 265inline _LIBCPP_HIDE_FROM_ABI __enable_if_t<!__use_branchless_sort<_Compare, _RandomAccessIterator>::value, void> 266__sort4_maybe_branchless(_RandomAccessIterator __x1, _RandomAccessIterator __x2, _RandomAccessIterator __x3, 267 _RandomAccessIterator __x4, _Compare __c) { 268 std::__sort4<_AlgPolicy, _Compare>(__x1, __x2, __x3, __x4, __c); 269} 270 271template <class, class _Compare, class _RandomAccessIterator> 272inline _LIBCPP_HIDE_FROM_ABI __enable_if_t<__use_branchless_sort<_Compare, _RandomAccessIterator>::value, void> 273__sort5_maybe_branchless(_RandomAccessIterator __x1, _RandomAccessIterator __x2, _RandomAccessIterator __x3, 274 _RandomAccessIterator __x4, _RandomAccessIterator __x5, _Compare __c) { 275 std::__cond_swap<_Compare>(__x1, __x2, __c); 276 std::__cond_swap<_Compare>(__x4, __x5, __c); 277 std::__partially_sorted_swap<_Compare>(__x3, __x4, __x5, __c); 278 std::__cond_swap<_Compare>(__x2, __x5, __c); 279 std::__partially_sorted_swap<_Compare>(__x1, __x3, __x4, __c); 280 std::__partially_sorted_swap<_Compare>(__x2, __x3, __x4, __c); 281} 282 283template <class _AlgPolicy, class _Compare, class _RandomAccessIterator> 284inline _LIBCPP_HIDE_FROM_ABI __enable_if_t<!__use_branchless_sort<_Compare, _RandomAccessIterator>::value, void> 285__sort5_maybe_branchless(_RandomAccessIterator __x1, _RandomAccessIterator __x2, _RandomAccessIterator __x3, 286 _RandomAccessIterator __x4, _RandomAccessIterator __x5, _Compare __c) { 287 std::__sort5_wrap_policy<_AlgPolicy, _Compare>(__x1, __x2, __x3, __x4, __x5, __c); 288} 289 290// Assumes size > 0 291template <class _AlgPolicy, class _Compare, class _BidirectionalIterator> 292_LIBCPP_HIDE_FROM_ABI 293_LIBCPP_CONSTEXPR_SINCE_CXX14 void __selection_sort(_BidirectionalIterator __first, _BidirectionalIterator __last, 294 _Compare __comp) { 295 _BidirectionalIterator __lm1 = __last; 296 for (--__lm1; __first != __lm1; ++__first) { 297 _BidirectionalIterator __i = std::__min_element<_Compare>(__first, __last, __comp); 298 if (__i != __first) 299 _IterOps<_AlgPolicy>::iter_swap(__first, __i); 300 } 301} 302 303template <class _AlgPolicy, class _Compare, class _BidirectionalIterator> 304_LIBCPP_HIDE_FROM_ABI 305void __insertion_sort(_BidirectionalIterator __first, _BidirectionalIterator __last, _Compare __comp) { 306 using _Ops = _IterOps<_AlgPolicy>; 307 308 typedef typename iterator_traits<_BidirectionalIterator>::value_type value_type; 309 if (__first != __last) { 310 _BidirectionalIterator __i = __first; 311 for (++__i; __i != __last; ++__i) { 312 _BidirectionalIterator __j = __i; 313 value_type __t(_Ops::__iter_move(__j)); 314 for (_BidirectionalIterator __k = __i; __k != __first && __comp(__t, *--__k); --__j) 315 *__j = _Ops::__iter_move(__k); 316 *__j = std::move(__t); 317 } 318 } 319} 320 321template <class _AlgPolicy, class _Compare, class _RandomAccessIterator> 322_LIBCPP_HIDE_FROM_ABI 323void __insertion_sort_3(_RandomAccessIterator __first, _RandomAccessIterator __last, _Compare __comp) { 324 using _Ops = _IterOps<_AlgPolicy>; 325 326 typedef typename iterator_traits<_RandomAccessIterator>::difference_type difference_type; 327 typedef typename iterator_traits<_RandomAccessIterator>::value_type value_type; 328 _RandomAccessIterator __j = __first + difference_type(2); 329 std::__sort3_maybe_branchless<_AlgPolicy, _Compare>(__first, __first + difference_type(1), __j, __comp); 330 for (_RandomAccessIterator __i = __j + difference_type(1); __i != __last; ++__i) { 331 if (__comp(*__i, *__j)) { 332 value_type __t(_Ops::__iter_move(__i)); 333 _RandomAccessIterator __k = __j; 334 __j = __i; 335 do { 336 *__j = _Ops::__iter_move(__k); 337 __j = __k; 338 } while (__j != __first && __comp(__t, *--__k)); 339 *__j = std::move(__t); 340 } 341 __j = __i; 342 } 343} 344 345template <class _WrappedComp, class _RandomAccessIterator> 346_LIBCPP_HIDDEN bool __insertion_sort_incomplete( 347 _RandomAccessIterator __first, _RandomAccessIterator __last, _WrappedComp __wrapped_comp) { 348 using _Unwrap = _UnwrapAlgPolicy<_WrappedComp>; 349 using _AlgPolicy = typename _Unwrap::_AlgPolicy; 350 using _Ops = _IterOps<_AlgPolicy>; 351 352 using _Compare = typename _Unwrap::_Comp; 353 _Compare __comp = _Unwrap::__get_comp(__wrapped_comp); 354 355 typedef typename iterator_traits<_RandomAccessIterator>::difference_type difference_type; 356 switch (__last - __first) { 357 case 0: 358 case 1: 359 return true; 360 case 2: 361 if (__comp(*--__last, *__first)) 362 _IterOps<_AlgPolicy>::iter_swap(__first, __last); 363 return true; 364 case 3: 365 std::__sort3_maybe_branchless<_AlgPolicy, _Compare>(__first, __first + difference_type(1), --__last, __comp); 366 return true; 367 case 4: 368 std::__sort4_maybe_branchless<_AlgPolicy, _Compare>( 369 __first, __first + difference_type(1), __first + difference_type(2), --__last, __comp); 370 return true; 371 case 5: 372 std::__sort5_maybe_branchless<_AlgPolicy, _Compare>( 373 __first, __first + difference_type(1), __first + difference_type(2), __first + difference_type(3), 374 --__last, __comp); 375 return true; 376 } 377 typedef typename iterator_traits<_RandomAccessIterator>::value_type value_type; 378 _RandomAccessIterator __j = __first + difference_type(2); 379 std::__sort3_maybe_branchless<_AlgPolicy, _Compare>(__first, __first + difference_type(1), __j, __comp); 380 const unsigned __limit = 8; 381 unsigned __count = 0; 382 for (_RandomAccessIterator __i = __j + difference_type(1); __i != __last; ++__i) { 383 if (__comp(*__i, *__j)) { 384 value_type __t(_Ops::__iter_move(__i)); 385 _RandomAccessIterator __k = __j; 386 __j = __i; 387 do { 388 *__j = _Ops::__iter_move(__k); 389 __j = __k; 390 } while (__j != __first && __comp(__t, *--__k)); 391 *__j = std::move(__t); 392 if (++__count == __limit) 393 return ++__i == __last; 394 } 395 __j = __i; 396 } 397 return true; 398} 399 400template <class _AlgPolicy, class _Compare, class _BidirectionalIterator> 401_LIBCPP_HIDE_FROM_ABI 402void __insertion_sort_move(_BidirectionalIterator __first1, _BidirectionalIterator __last1, 403 typename iterator_traits<_BidirectionalIterator>::value_type* __first2, _Compare __comp) { 404 using _Ops = _IterOps<_AlgPolicy>; 405 406 typedef typename iterator_traits<_BidirectionalIterator>::value_type value_type; 407 if (__first1 != __last1) { 408 __destruct_n __d(0); 409 unique_ptr<value_type, __destruct_n&> __h(__first2, __d); 410 value_type* __last2 = __first2; 411 ::new ((void*)__last2) value_type(_Ops::__iter_move(__first1)); 412 __d.template __incr<value_type>(); 413 for (++__last2; ++__first1 != __last1; ++__last2) { 414 value_type* __j2 = __last2; 415 value_type* __i2 = __j2; 416 if (__comp(*__first1, *--__i2)) { 417 ::new ((void*)__j2) value_type(std::move(*__i2)); 418 __d.template __incr<value_type>(); 419 for (--__j2; __i2 != __first2 && __comp(*__first1, *--__i2); --__j2) 420 *__j2 = std::move(*__i2); 421 *__j2 = _Ops::__iter_move(__first1); 422 } else { 423 ::new ((void*)__j2) value_type(_Ops::__iter_move(__first1)); 424 __d.template __incr<value_type>(); 425 } 426 } 427 __h.release(); 428 } 429} 430 431template <class _AlgPolicy, class _Compare, class _RandomAccessIterator> 432void __introsort(_RandomAccessIterator __first, _RandomAccessIterator __last, _Compare __comp, 433 typename iterator_traits<_RandomAccessIterator>::difference_type __depth) { 434 using _Ops = _IterOps<_AlgPolicy>; 435 436 typedef typename iterator_traits<_RandomAccessIterator>::difference_type difference_type; 437 typedef typename iterator_traits<_RandomAccessIterator>::value_type value_type; 438 const difference_type __limit = 439 is_trivially_copy_constructible<value_type>::value && is_trivially_copy_assignable<value_type>::value ? 30 : 6; 440 while (true) { 441 __restart: 442 difference_type __len = __last - __first; 443 switch (__len) { 444 case 0: 445 case 1: 446 return; 447 case 2: 448 if (__comp(*--__last, *__first)) 449 _IterOps<_AlgPolicy>::iter_swap(__first, __last); 450 return; 451 case 3: 452 std::__sort3_maybe_branchless<_AlgPolicy, _Compare>(__first, __first + difference_type(1), --__last, __comp); 453 return; 454 case 4: 455 std::__sort4_maybe_branchless<_AlgPolicy, _Compare>( 456 __first, __first + difference_type(1), __first + difference_type(2), --__last, __comp); 457 return; 458 case 5: 459 std::__sort5_maybe_branchless<_AlgPolicy, _Compare>( 460 __first, __first + difference_type(1), __first + difference_type(2), __first + difference_type(3), 461 --__last, __comp); 462 return; 463 } 464 if (__len <= __limit) { 465 std::__insertion_sort_3<_AlgPolicy, _Compare>(__first, __last, __comp); 466 return; 467 } 468 // __len > 5 469 if (__depth == 0) { 470 // Fallback to heap sort as Introsort suggests. 471 std::__partial_sort<_AlgPolicy, _Compare>(__first, __last, __last, __comp); 472 return; 473 } 474 --__depth; 475 _RandomAccessIterator __m = __first; 476 _RandomAccessIterator __lm1 = __last; 477 --__lm1; 478 unsigned __n_swaps; 479 { 480 difference_type __delta; 481 if (__len >= 1000) { 482 __delta = __len / 2; 483 __m += __delta; 484 __delta /= 2; 485 __n_swaps = std::__sort5_wrap_policy<_AlgPolicy, _Compare>( 486 __first, __first + __delta, __m, __m + __delta, __lm1, __comp); 487 } else { 488 __delta = __len / 2; 489 __m += __delta; 490 __n_swaps = std::__sort3<_AlgPolicy, _Compare>(__first, __m, __lm1, __comp); 491 } 492 } 493 // *__m is median 494 // partition [__first, __m) < *__m and *__m <= [__m, __last) 495 // (this inhibits tossing elements equivalent to __m around unnecessarily) 496 _RandomAccessIterator __i = __first; 497 _RandomAccessIterator __j = __lm1; 498 // j points beyond range to be tested, *__m is known to be <= *__lm1 499 // The search going up is known to be guarded but the search coming down isn't. 500 // Prime the downward search with a guard. 501 if (!__comp(*__i, *__m)) // if *__first == *__m 502 { 503 // *__first == *__m, *__first doesn't go in first part 504 // manually guard downward moving __j against __i 505 while (true) { 506 if (__i == --__j) { 507 // *__first == *__m, *__m <= all other elements 508 // Parition instead into [__first, __i) == *__first and *__first < [__i, __last) 509 ++__i; // __first + 1 510 __j = __last; 511 if (!__comp(*__first, *--__j)) // we need a guard if *__first == *(__last-1) 512 { 513 while (true) { 514 if (__i == __j) 515 return; // [__first, __last) all equivalent elements 516 if (__comp(*__first, *__i)) { 517 _Ops::iter_swap(__i, __j); 518 ++__n_swaps; 519 ++__i; 520 break; 521 } 522 ++__i; 523 } 524 } 525 // [__first, __i) == *__first and *__first < [__j, __last) and __j == __last - 1 526 if (__i == __j) 527 return; 528 while (true) { 529 while (!__comp(*__first, *__i)) 530 ++__i; 531 while (__comp(*__first, *--__j)) 532 ; 533 if (__i >= __j) 534 break; 535 _Ops::iter_swap(__i, __j); 536 ++__n_swaps; 537 ++__i; 538 } 539 // [__first, __i) == *__first and *__first < [__i, __last) 540 // The first part is sorted, sort the second part 541 // std::__sort<_Compare>(__i, __last, __comp); 542 __first = __i; 543 goto __restart; 544 } 545 if (__comp(*__j, *__m)) { 546 _Ops::iter_swap(__i, __j); 547 ++__n_swaps; 548 break; // found guard for downward moving __j, now use unguarded partition 549 } 550 } 551 } 552 // It is known that *__i < *__m 553 ++__i; 554 // j points beyond range to be tested, *__m is known to be <= *__lm1 555 // if not yet partitioned... 556 if (__i < __j) { 557 // known that *(__i - 1) < *__m 558 // known that __i <= __m 559 while (true) { 560 // __m still guards upward moving __i 561 while (__comp(*__i, *__m)) 562 ++__i; 563 // It is now known that a guard exists for downward moving __j 564 while (!__comp(*--__j, *__m)) 565 ; 566 if (__i > __j) 567 break; 568 _Ops::iter_swap(__i, __j); 569 ++__n_swaps; 570 // It is known that __m != __j 571 // If __m just moved, follow it 572 if (__m == __i) 573 __m = __j; 574 ++__i; 575 } 576 } 577 // [__first, __i) < *__m and *__m <= [__i, __last) 578 if (__i != __m && __comp(*__m, *__i)) { 579 _Ops::iter_swap(__i, __m); 580 ++__n_swaps; 581 } 582 // [__first, __i) < *__i and *__i <= [__i+1, __last) 583 // If we were given a perfect partition, see if insertion sort is quick... 584 if (__n_swaps == 0) { 585 using _WrappedComp = typename _WrapAlgPolicy<_AlgPolicy, _Compare>::type; 586 _WrappedComp __wrapped_comp(__comp); 587 bool __fs = std::__insertion_sort_incomplete<_WrappedComp>(__first, __i, __wrapped_comp); 588 if (std::__insertion_sort_incomplete<_WrappedComp>(__i + difference_type(1), __last, __wrapped_comp)) { 589 if (__fs) 590 return; 591 __last = __i; 592 continue; 593 } else { 594 if (__fs) { 595 __first = ++__i; 596 continue; 597 } 598 } 599 } 600 // sort smaller range with recursive call and larger with tail recursion elimination 601 if (__i - __first < __last - __i) { 602 std::__introsort<_AlgPolicy, _Compare>(__first, __i, __comp, __depth); 603 __first = ++__i; 604 } else { 605 std::__introsort<_AlgPolicy, _Compare>(__i + difference_type(1), __last, __comp, __depth); 606 __last = __i; 607 } 608 } 609} 610 611template <typename _Number> 612inline _LIBCPP_HIDE_FROM_ABI _Number __log2i(_Number __n) { 613 if (__n == 0) 614 return 0; 615 if (sizeof(__n) <= sizeof(unsigned)) 616 return sizeof(unsigned) * CHAR_BIT - 1 - __libcpp_clz(static_cast<unsigned>(__n)); 617 if (sizeof(__n) <= sizeof(unsigned long)) 618 return sizeof(unsigned long) * CHAR_BIT - 1 - __libcpp_clz(static_cast<unsigned long>(__n)); 619 if (sizeof(__n) <= sizeof(unsigned long long)) 620 return sizeof(unsigned long long) * CHAR_BIT - 1 - __libcpp_clz(static_cast<unsigned long long>(__n)); 621 622 _Number __log2 = 0; 623 while (__n > 1) { 624 __log2++; 625 __n >>= 1; 626 } 627 return __log2; 628} 629 630template <class _WrappedComp, class _RandomAccessIterator> 631_LIBCPP_HIDDEN void __sort(_RandomAccessIterator __first, _RandomAccessIterator __last, _WrappedComp __wrapped_comp) { 632 typedef typename iterator_traits<_RandomAccessIterator>::difference_type difference_type; 633 difference_type __depth_limit = 2 * std::__log2i(__last - __first); 634 635 using _Unwrap = _UnwrapAlgPolicy<_WrappedComp>; 636 using _AlgPolicy = typename _Unwrap::_AlgPolicy; 637 using _Compare = typename _Unwrap::_Comp; 638 _Compare __comp = _Unwrap::__get_comp(__wrapped_comp); 639 std::__introsort<_AlgPolicy, _Compare>(__first, __last, __comp, __depth_limit); 640} 641 642template <class _Compare, class _Tp> 643inline _LIBCPP_INLINE_VISIBILITY void __sort(_Tp** __first, _Tp** __last, __less<_Tp*>&) { 644 __less<uintptr_t> __comp; 645 std::__sort<__less<uintptr_t>&, uintptr_t*>((uintptr_t*)__first, (uintptr_t*)__last, __comp); 646} 647 648extern template _LIBCPP_FUNC_VIS void __sort<__less<char>&, char*>(char*, char*, __less<char>&); 649#ifndef _LIBCPP_HAS_NO_WIDE_CHARACTERS 650extern template _LIBCPP_FUNC_VIS void __sort<__less<wchar_t>&, wchar_t*>(wchar_t*, wchar_t*, __less<wchar_t>&); 651#endif 652extern template _LIBCPP_FUNC_VIS void __sort<__less<signed char>&, signed char*>(signed char*, signed char*, __less<signed char>&); 653extern template _LIBCPP_FUNC_VIS void __sort<__less<unsigned char>&, unsigned char*>(unsigned char*, unsigned char*, __less<unsigned char>&); 654extern template _LIBCPP_FUNC_VIS void __sort<__less<short>&, short*>(short*, short*, __less<short>&); 655extern template _LIBCPP_FUNC_VIS void __sort<__less<unsigned short>&, unsigned short*>(unsigned short*, unsigned short*, __less<unsigned short>&); 656extern template _LIBCPP_FUNC_VIS void __sort<__less<int>&, int*>(int*, int*, __less<int>&); 657extern template _LIBCPP_FUNC_VIS void __sort<__less<unsigned>&, unsigned*>(unsigned*, unsigned*, __less<unsigned>&); 658extern template _LIBCPP_FUNC_VIS void __sort<__less<long>&, long*>(long*, long*, __less<long>&); 659extern template _LIBCPP_FUNC_VIS void __sort<__less<unsigned long>&, unsigned long*>(unsigned long*, unsigned long*, __less<unsigned long>&); 660extern template _LIBCPP_FUNC_VIS void __sort<__less<long long>&, long long*>(long long*, long long*, __less<long long>&); 661extern template _LIBCPP_FUNC_VIS void __sort<__less<unsigned long long>&, unsigned long long*>(unsigned long long*, unsigned long long*, __less<unsigned long long>&); 662extern template _LIBCPP_FUNC_VIS void __sort<__less<float>&, float*>(float*, float*, __less<float>&); 663extern template _LIBCPP_FUNC_VIS void __sort<__less<double>&, double*>(double*, double*, __less<double>&); 664extern template _LIBCPP_FUNC_VIS void __sort<__less<long double>&, long double*>(long double*, long double*, __less<long double>&); 665 666extern template _LIBCPP_FUNC_VIS bool __insertion_sort_incomplete<__less<char>&, char*>(char*, char*, __less<char>&); 667#ifndef _LIBCPP_HAS_NO_WIDE_CHARACTERS 668extern template _LIBCPP_FUNC_VIS bool __insertion_sort_incomplete<__less<wchar_t>&, wchar_t*>(wchar_t*, wchar_t*, __less<wchar_t>&); 669#endif 670extern template _LIBCPP_FUNC_VIS bool __insertion_sort_incomplete<__less<signed char>&, signed char*>(signed char*, signed char*, __less<signed char>&); 671extern template _LIBCPP_FUNC_VIS bool __insertion_sort_incomplete<__less<unsigned char>&, unsigned char*>(unsigned char*, unsigned char*, __less<unsigned char>&); 672extern template _LIBCPP_FUNC_VIS bool __insertion_sort_incomplete<__less<short>&, short*>(short*, short*, __less<short>&); 673extern template _LIBCPP_FUNC_VIS bool __insertion_sort_incomplete<__less<unsigned short>&, unsigned short*>(unsigned short*, unsigned short*, __less<unsigned short>&); 674extern template _LIBCPP_FUNC_VIS bool __insertion_sort_incomplete<__less<int>&, int*>(int*, int*, __less<int>&); 675extern template _LIBCPP_FUNC_VIS bool __insertion_sort_incomplete<__less<unsigned>&, unsigned*>(unsigned*, unsigned*, __less<unsigned>&); 676extern template _LIBCPP_FUNC_VIS bool __insertion_sort_incomplete<__less<long>&, long*>(long*, long*, __less<long>&); 677extern template _LIBCPP_FUNC_VIS bool __insertion_sort_incomplete<__less<unsigned long>&, unsigned long*>(unsigned long*, unsigned long*, __less<unsigned long>&); 678extern template _LIBCPP_FUNC_VIS bool __insertion_sort_incomplete<__less<long long>&, long long*>(long long*, long long*, __less<long long>&); 679extern template _LIBCPP_FUNC_VIS bool __insertion_sort_incomplete<__less<unsigned long long>&, unsigned long long*>(unsigned long long*, unsigned long long*, __less<unsigned long long>&); 680extern template _LIBCPP_FUNC_VIS bool __insertion_sort_incomplete<__less<float>&, float*>(float*, float*, __less<float>&); 681extern template _LIBCPP_FUNC_VIS bool __insertion_sort_incomplete<__less<double>&, double*>(double*, double*, __less<double>&); 682extern template _LIBCPP_FUNC_VIS bool __insertion_sort_incomplete<__less<long double>&, long double*>(long double*, long double*, __less<long double>&); 683 684extern template _LIBCPP_FUNC_VIS unsigned __sort5<__less<long double>&, long double*>(long double*, long double*, long double*, long double*, long double*, __less<long double>&); 685 686template <class _AlgPolicy, class _RandomAccessIterator, class _Comp> 687inline _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20 688void __sort_impl(_RandomAccessIterator __first, _RandomAccessIterator __last, _Comp& __comp) { 689 std::__debug_randomize_range<_AlgPolicy>(__first, __last); 690 691 using _Comp_ref = __comp_ref_type<_Comp>; 692 if (__libcpp_is_constant_evaluated()) { 693 std::__partial_sort<_AlgPolicy>(__first, __last, __last, __comp); 694 695 } else { 696 using _WrappedComp = typename _WrapAlgPolicy<_AlgPolicy, _Comp_ref>::type; 697 _Comp_ref __comp_ref(__comp); 698 _WrappedComp __wrapped_comp(__comp_ref); 699 std::__sort<_WrappedComp>(std::__unwrap_iter(__first), std::__unwrap_iter(__last), __wrapped_comp); 700 } 701} 702 703template <class _RandomAccessIterator, class _Comp> 704inline _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20 705void sort(_RandomAccessIterator __first, _RandomAccessIterator __last, _Comp __comp) { 706 std::__sort_impl<_ClassicAlgPolicy>(std::move(__first), std::move(__last), __comp); 707} 708 709template <class _RandomAccessIterator> 710inline _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20 711void sort(_RandomAccessIterator __first, _RandomAccessIterator __last) { 712 std::sort(__first, __last, __less<typename iterator_traits<_RandomAccessIterator>::value_type>()); 713} 714 715_LIBCPP_END_NAMESPACE_STD 716 717#endif // _LIBCPP___ALGORITHM_SORT_H 718