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. 44 template <class _PolicyT, class _CompT, class = void> 45 struct _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 _WrapAlgPolicy_WrapAlgPolicy53 _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. 59 template <class _PolicyT, class _CompT> 60 struct _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". 66 template <class _CompT> 67 struct _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. 76 template <class... _Ts> 77 struct _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 88 template <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 127 template <class _AlgPolicy, class _Compare, class _ForwardIterator> 128 _LIBCPP_HIDE_FROM_ABI 129 unsigned __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 151 template <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 181 template <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. 192 template <class _Tp> 193 struct __is_simple_comparator : false_type {}; 194 template <class _Tp> 195 struct __is_simple_comparator<__less<_Tp>&> : true_type {}; 196 template <class _Tp> 197 struct __is_simple_comparator<less<_Tp>&> : true_type {}; 198 template <class _Tp> 199 struct __is_simple_comparator<greater<_Tp>&> : true_type {}; 200 #if _LIBCPP_STD_VER > 17 201 template <> 202 struct __is_simple_comparator<ranges::less&> : true_type {}; 203 template <> 204 struct __is_simple_comparator<ranges::greater&> : true_type {}; 205 #endif 206 207 template <class _Compare, class _Iter, class _Tp = typename iterator_traits<_Iter>::value_type> 208 using __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. 213 template <class _Compare, class _RandomAccessIterator> 214 inline _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. 225 template <class _Compare, class _RandomAccessIterator> 226 inline _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 238 template <class, class _Compare, class _RandomAccessIterator> 239 inline _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 246 template <class _AlgPolicy, class _Compare, class _RandomAccessIterator> 247 inline _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 253 template <class, class _Compare, class _RandomAccessIterator> 254 inline _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 264 template <class _AlgPolicy, class _Compare, class _RandomAccessIterator> 265 inline _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 271 template <class, class _Compare, class _RandomAccessIterator> 272 inline _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 283 template <class _AlgPolicy, class _Compare, class _RandomAccessIterator> 284 inline _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 291 template <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 303 template <class _AlgPolicy, class _Compare, class _BidirectionalIterator> 304 _LIBCPP_HIDE_FROM_ABI 305 void __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 321 template <class _AlgPolicy, class _Compare, class _RandomAccessIterator> 322 _LIBCPP_HIDE_FROM_ABI 323 void __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 345 template <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 400 template <class _AlgPolicy, class _Compare, class _BidirectionalIterator> 401 _LIBCPP_HIDE_FROM_ABI 402 void __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 431 template <class _AlgPolicy, class _Compare, class _RandomAccessIterator> 432 void __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 611 template <typename _Number> 612 inline _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 630 template <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 642 template <class _Compare, class _Tp> 643 inline _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 648 extern template _LIBCPP_FUNC_VIS void __sort<__less<char>&, char*>(char*, char*, __less<char>&); 649 #ifndef _LIBCPP_HAS_NO_WIDE_CHARACTERS 650 extern template _LIBCPP_FUNC_VIS void __sort<__less<wchar_t>&, wchar_t*>(wchar_t*, wchar_t*, __less<wchar_t>&); 651 #endif 652 extern template _LIBCPP_FUNC_VIS void __sort<__less<signed char>&, signed char*>(signed char*, signed char*, __less<signed char>&); 653 extern template _LIBCPP_FUNC_VIS void __sort<__less<unsigned char>&, unsigned char*>(unsigned char*, unsigned char*, __less<unsigned char>&); 654 extern template _LIBCPP_FUNC_VIS void __sort<__less<short>&, short*>(short*, short*, __less<short>&); 655 extern template _LIBCPP_FUNC_VIS void __sort<__less<unsigned short>&, unsigned short*>(unsigned short*, unsigned short*, __less<unsigned short>&); 656 extern template _LIBCPP_FUNC_VIS void __sort<__less<int>&, int*>(int*, int*, __less<int>&); 657 extern template _LIBCPP_FUNC_VIS void __sort<__less<unsigned>&, unsigned*>(unsigned*, unsigned*, __less<unsigned>&); 658 extern template _LIBCPP_FUNC_VIS void __sort<__less<long>&, long*>(long*, long*, __less<long>&); 659 extern template _LIBCPP_FUNC_VIS void __sort<__less<unsigned long>&, unsigned long*>(unsigned long*, unsigned long*, __less<unsigned long>&); 660 extern template _LIBCPP_FUNC_VIS void __sort<__less<long long>&, long long*>(long long*, long long*, __less<long long>&); 661 extern template _LIBCPP_FUNC_VIS void __sort<__less<unsigned long long>&, unsigned long long*>(unsigned long long*, unsigned long long*, __less<unsigned long long>&); 662 extern template _LIBCPP_FUNC_VIS void __sort<__less<float>&, float*>(float*, float*, __less<float>&); 663 extern template _LIBCPP_FUNC_VIS void __sort<__less<double>&, double*>(double*, double*, __less<double>&); 664 extern template _LIBCPP_FUNC_VIS void __sort<__less<long double>&, long double*>(long double*, long double*, __less<long double>&); 665 666 extern template _LIBCPP_FUNC_VIS bool __insertion_sort_incomplete<__less<char>&, char*>(char*, char*, __less<char>&); 667 #ifndef _LIBCPP_HAS_NO_WIDE_CHARACTERS 668 extern template _LIBCPP_FUNC_VIS bool __insertion_sort_incomplete<__less<wchar_t>&, wchar_t*>(wchar_t*, wchar_t*, __less<wchar_t>&); 669 #endif 670 extern template _LIBCPP_FUNC_VIS bool __insertion_sort_incomplete<__less<signed char>&, signed char*>(signed char*, signed char*, __less<signed char>&); 671 extern template _LIBCPP_FUNC_VIS bool __insertion_sort_incomplete<__less<unsigned char>&, unsigned char*>(unsigned char*, unsigned char*, __less<unsigned char>&); 672 extern template _LIBCPP_FUNC_VIS bool __insertion_sort_incomplete<__less<short>&, short*>(short*, short*, __less<short>&); 673 extern template _LIBCPP_FUNC_VIS bool __insertion_sort_incomplete<__less<unsigned short>&, unsigned short*>(unsigned short*, unsigned short*, __less<unsigned short>&); 674 extern template _LIBCPP_FUNC_VIS bool __insertion_sort_incomplete<__less<int>&, int*>(int*, int*, __less<int>&); 675 extern template _LIBCPP_FUNC_VIS bool __insertion_sort_incomplete<__less<unsigned>&, unsigned*>(unsigned*, unsigned*, __less<unsigned>&); 676 extern template _LIBCPP_FUNC_VIS bool __insertion_sort_incomplete<__less<long>&, long*>(long*, long*, __less<long>&); 677 extern template _LIBCPP_FUNC_VIS bool __insertion_sort_incomplete<__less<unsigned long>&, unsigned long*>(unsigned long*, unsigned long*, __less<unsigned long>&); 678 extern template _LIBCPP_FUNC_VIS bool __insertion_sort_incomplete<__less<long long>&, long long*>(long long*, long long*, __less<long long>&); 679 extern 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>&); 680 extern template _LIBCPP_FUNC_VIS bool __insertion_sort_incomplete<__less<float>&, float*>(float*, float*, __less<float>&); 681 extern template _LIBCPP_FUNC_VIS bool __insertion_sort_incomplete<__less<double>&, double*>(double*, double*, __less<double>&); 682 extern template _LIBCPP_FUNC_VIS bool __insertion_sort_incomplete<__less<long double>&, long double*>(long double*, long double*, __less<long double>&); 683 684 extern 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 686 template <class _AlgPolicy, class _RandomAccessIterator, class _Comp> 687 inline _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20 688 void __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 703 template <class _RandomAccessIterator, class _Comp> 704 inline _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20 705 void sort(_RandomAccessIterator __first, _RandomAccessIterator __last, _Comp __comp) { 706 std::__sort_impl<_ClassicAlgPolicy>(std::move(__first), std::move(__last), __comp); 707 } 708 709 template <class _RandomAccessIterator> 710 inline _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20 711 void 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