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