155714Skris//===----------------------------------------------------------------------===// 255714Skris// 355714Skris// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. 455714Skris// See https://llvm.org/LICENSE.txt for license information. 555714Skris// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception 655714Skris// 755714Skris//===----------------------------------------------------------------------===// 8280304Sjkim 955714Skris#ifndef _LIBCPP___ALGORITHM_SORT_H 1055714Skris#define _LIBCPP___ALGORITHM_SORT_H 1155714Skris 1255714Skris#include <__algorithm/comp.h> 1355714Skris#include <__algorithm/comp_ref_type.h> 1455714Skris#include <__algorithm/iter_swap.h> 15280304Sjkim#include <__algorithm/iterator_operations.h> 1655714Skris#include <__algorithm/min_element.h> 1755714Skris#include <__algorithm/partial_sort.h> 1855714Skris#include <__algorithm/unwrap_iter.h> 1955714Skris#include <__assert> 2055714Skris#include <__bit/blsr.h> 2155714Skris#include <__bit/countl.h> 22280304Sjkim#include <__bit/countr.h> 2355714Skris#include <__config> 2455714Skris#include <__debug_utils/randomize_range.h> 2555714Skris#include <__debug_utils/strict_weak_ordering_check.h> 2655714Skris#include <__functional/operations.h> 2755714Skris#include <__functional/ranges_operations.h> 2855714Skris#include <__iterator/iterator_traits.h> 2955714Skris#include <__type_traits/conditional.h> 3055714Skris#include <__type_traits/disjunction.h> 3155714Skris#include <__type_traits/is_arithmetic.h> 3255714Skris#include <__type_traits/is_constant_evaluated.h> 3355714Skris#include <__utility/move.h> 3455714Skris#include <__utility/pair.h> 3555714Skris#include <climits> 3655714Skris#include <cstdint> 37280304Sjkim 3855714Skris#if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER) 3955714Skris# pragma GCC system_header 40280304Sjkim#endif 4155714Skris 4255714Skris_LIBCPP_PUSH_MACROS 4355714Skris#include <__undef_macros> 4455714Skris 4555714Skris_LIBCPP_BEGIN_NAMESPACE_STD 4655714Skris 4755714Skris// stable, 2-3 compares, 0-2 swaps 4855714Skris 4955714Skristemplate <class _AlgPolicy, class _Compare, class _ForwardIterator> 5055714Skris_LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX14 unsigned 5155714Skris__sort3(_ForwardIterator __x, _ForwardIterator __y, _ForwardIterator __z, _Compare __c) { 52280304Sjkim using _Ops = _IterOps<_AlgPolicy>; 5355714Skris 5455714Skris unsigned __r = 0; 5555714Skris if (!__c(*__y, *__x)) // if x <= y 5655714Skris { 5755714Skris if (!__c(*__z, *__y)) // if y <= z 5889840Skris return __r; // x <= y && y <= z 5989840Skris // x <= y && y > z 6089840Skris _Ops::iter_swap(__y, __z); // x <= z && y < z 6189840Skris __r = 1; 6289840Skris if (__c(*__y, *__x)) // if x > y 6389840Skris { 6489840Skris _Ops::iter_swap(__x, __y); // x < y && y <= z 6589840Skris __r = 2; 66280304Sjkim } 6789840Skris return __r; // x <= y && y < z 6889840Skris } 6989840Skris if (__c(*__z, *__y)) // x > y, if y > z 7089840Skris { 7189840Skris _Ops::iter_swap(__x, __z); // x < y && y < z 7289840Skris __r = 1; 7389840Skris return __r; 7489840Skris } 7589840Skris _Ops::iter_swap(__x, __y); // x > y && y <= z 7689840Skris __r = 1; // x < y && x <= z 7789840Skris if (__c(*__z, *__y)) // if y > z 7889840Skris { 7989840Skris _Ops::iter_swap(__y, __z); // x <= y && y < z 8089840Skris __r = 2; 8189840Skris } 8289840Skris return __r; 8389840Skris} // x <= y && y <= z 8489840Skris 8589840Skris// stable, 3-6 compares, 0-5 swaps 8689840Skris 8789840Skristemplate <class _AlgPolicy, class _Compare, class _ForwardIterator> 8889840Skris_LIBCPP_HIDE_FROM_ABI void 8989840Skris__sort4(_ForwardIterator __x1, _ForwardIterator __x2, _ForwardIterator __x3, _ForwardIterator __x4, _Compare __c) { 9089840Skris using _Ops = _IterOps<_AlgPolicy>; 9189840Skris std::__sort3<_AlgPolicy, _Compare>(__x1, __x2, __x3, __c); 9289840Skris if (__c(*__x4, *__x3)) { 9389840Skris _Ops::iter_swap(__x3, __x4); 9489840Skris if (__c(*__x3, *__x2)) { 9589840Skris _Ops::iter_swap(__x2, __x3); 9689840Skris if (__c(*__x2, *__x1)) { 9789840Skris _Ops::iter_swap(__x1, __x2); 9889840Skris } 9989840Skris } 10089840Skris } 10189840Skris} 10289840Skris 10389840Skris// stable, 4-10 compares, 0-9 swaps 10489840Skris 10589840Skristemplate <class _AlgPolicy, class _Comp, class _ForwardIterator> 10689840Skris_LIBCPP_HIDE_FROM_ABI void 10789840Skris__sort5(_ForwardIterator __x1, 10889840Skris _ForwardIterator __x2, 10989840Skris _ForwardIterator __x3, 11089840Skris _ForwardIterator __x4, 11155714Skris _ForwardIterator __x5, 11259194Skris _Comp __comp) { 113110007Smarkm using _Ops = _IterOps<_AlgPolicy>; 114284285Sjkim 115280304Sjkim std::__sort4<_AlgPolicy, _Comp>(__x1, __x2, __x3, __x4, __comp); 116280304Sjkim if (__comp(*__x5, *__x4)) { 117280304Sjkim _Ops::iter_swap(__x4, __x5); 118280304Sjkim if (__comp(*__x4, *__x3)) { 119280304Sjkim _Ops::iter_swap(__x3, __x4); 12055714Skris if (__comp(*__x3, *__x2)) { 121238405Sjkim _Ops::iter_swap(__x2, __x3); 12255714Skris if (__comp(*__x2, *__x1)) { 12355714Skris _Ops::iter_swap(__x1, __x2); 124280304Sjkim } 12555714Skris } 12655714Skris } 12755714Skris } 12855714Skris} 12955714Skris 130280304Sjkim// The comparator being simple is a prerequisite for using the branchless optimization. 131280304Sjkimtemplate <class _Tp> 13255714Skrisstruct __is_simple_comparator : false_type {}; 133238405Sjkimtemplate <> 134280304Sjkimstruct __is_simple_comparator<__less<>&> : true_type {}; 135280304Sjkimtemplate <class _Tp> 136280304Sjkimstruct __is_simple_comparator<less<_Tp>&> : true_type {}; 137280304Sjkimtemplate <class _Tp> 138280304Sjkimstruct __is_simple_comparator<greater<_Tp>&> : true_type {}; 139280304Sjkim#if _LIBCPP_STD_VER >= 20 14055714Skristemplate <> 141160817Ssimonstruct __is_simple_comparator<ranges::less&> : true_type {}; 142280304Sjkimtemplate <> 143280304Sjkimstruct __is_simple_comparator<ranges::greater&> : true_type {}; 14455714Skris#endif 14555714Skris 146280304Sjkimtemplate <class _Compare, class _Iter, class _Tp = typename iterator_traits<_Iter>::value_type> 147280304Sjkimusing __use_branchless_sort = 148280304Sjkim integral_constant<bool, 149280304Sjkim __libcpp_is_contiguous_iterator<_Iter>::value && sizeof(_Tp) <= sizeof(void*) && 150280304Sjkim is_arithmetic<_Tp>::value && __is_simple_comparator<_Compare>::value>; 151280304Sjkim 152280304Sjkimnamespace __detail { 15355714Skris 154280304Sjkim// Size in bits for the bitset in use. 155280304Sjkimenum { __block_size = sizeof(uint64_t) * 8 }; 156280304Sjkim 15755714Skris} // namespace __detail 158280304Sjkim 159280304Sjkim// Ensures that __c(*__x, *__y) is true by swapping *__x and *__y if necessary. 160280304Sjkimtemplate <class _Compare, class _RandomAccessIterator> 161280304Sjkiminline _LIBCPP_HIDE_FROM_ABI void __cond_swap(_RandomAccessIterator __x, _RandomAccessIterator __y, _Compare __c) { 16255714Skris // Note: this function behaves correctly even with proxy iterators (because it relies on `value_type`). 163280304Sjkim using value_type = typename iterator_traits<_RandomAccessIterator>::value_type; 164280304Sjkim bool __r = __c(*__x, *__y); 165280304Sjkim value_type __tmp = __r ? *__x : *__y; 166280304Sjkim *__y = __r ? *__y : *__x; 16755714Skris *__x = __tmp; 168280304Sjkim} 169280304Sjkim 170280304Sjkim// Ensures that *__x, *__y and *__z are ordered according to the comparator __c, 171280304Sjkim// under the assumption that *__y and *__z are already ordered. 17255714Skristemplate <class _Compare, class _RandomAccessIterator> 173280304Sjkiminline _LIBCPP_HIDE_FROM_ABI void 174280304Sjkim__partially_sorted_swap(_RandomAccessIterator __x, _RandomAccessIterator __y, _RandomAccessIterator __z, _Compare __c) { 175280304Sjkim // Note: this function behaves correctly even with proxy iterators (because it relies on `value_type`). 17655714Skris using value_type = typename iterator_traits<_RandomAccessIterator>::value_type; 177280304Sjkim bool __r = __c(*__z, *__x); 178280304Sjkim value_type __tmp = __r ? *__z : *__x; 179280304Sjkim *__z = __r ? *__x : *__z; 180280304Sjkim __r = __c(__tmp, *__y); 181280304Sjkim *__x = __r ? *__x : *__y; 18255714Skris *__y = __r ? *__y : __tmp; 183280304Sjkim} 184280304Sjkim 185280304Sjkimtemplate <class, 18655714Skris class _Compare, 187280304Sjkim class _RandomAccessIterator, 188280304Sjkim __enable_if_t<__use_branchless_sort<_Compare, _RandomAccessIterator>::value, int> = 0> 18955714Skrisinline _LIBCPP_HIDE_FROM_ABI void __sort3_maybe_branchless( 190280304Sjkim _RandomAccessIterator __x1, _RandomAccessIterator __x2, _RandomAccessIterator __x3, _Compare __c) { 191280304Sjkim std::__cond_swap<_Compare>(__x2, __x3, __c); 192280304Sjkim std::__partially_sorted_swap<_Compare>(__x1, __x2, __x3, __c); 193280304Sjkim} 194280304Sjkim 195280304Sjkimtemplate <class _AlgPolicy, 196280304Sjkim class _Compare, 197280304Sjkim class _RandomAccessIterator, 198280304Sjkim __enable_if_t<!__use_branchless_sort<_Compare, _RandomAccessIterator>::value, int> = 0> 199280304Sjkiminline _LIBCPP_HIDE_FROM_ABI void __sort3_maybe_branchless( 200280304Sjkim _RandomAccessIterator __x1, _RandomAccessIterator __x2, _RandomAccessIterator __x3, _Compare __c) { 201280304Sjkim std::__sort3<_AlgPolicy, _Compare>(__x1, __x2, __x3, __c); 202280304Sjkim} 203280304Sjkim 204280304Sjkimtemplate <class, 205280304Sjkim class _Compare, 206280304Sjkim class _RandomAccessIterator, 207280304Sjkim __enable_if_t<__use_branchless_sort<_Compare, _RandomAccessIterator>::value, int> = 0> 20855714Skrisinline _LIBCPP_HIDE_FROM_ABI void __sort4_maybe_branchless( 209280304Sjkim _RandomAccessIterator __x1, 210280304Sjkim _RandomAccessIterator __x2, 211280304Sjkim _RandomAccessIterator __x3, 212280304Sjkim _RandomAccessIterator __x4, 213280304Sjkim _Compare __c) { 214280304Sjkim std::__cond_swap<_Compare>(__x1, __x3, __c); 215280304Sjkim std::__cond_swap<_Compare>(__x2, __x4, __c); 216280304Sjkim std::__cond_swap<_Compare>(__x1, __x2, __c); 217280304Sjkim std::__cond_swap<_Compare>(__x3, __x4, __c); 218280304Sjkim std::__cond_swap<_Compare>(__x2, __x3, __c); 21955714Skris} 220280304Sjkim 221280304Sjkimtemplate <class _AlgPolicy, 222280304Sjkim class _Compare, 223280304Sjkim class _RandomAccessIterator, 224280304Sjkim __enable_if_t<!__use_branchless_sort<_Compare, _RandomAccessIterator>::value, int> = 0> 225280304Sjkiminline _LIBCPP_HIDE_FROM_ABI void __sort4_maybe_branchless( 226280304Sjkim _RandomAccessIterator __x1, 227280304Sjkim _RandomAccessIterator __x2, 228280304Sjkim _RandomAccessIterator __x3, 229280304Sjkim _RandomAccessIterator __x4, 230280304Sjkim _Compare __c) { 231280304Sjkim std::__sort4<_AlgPolicy, _Compare>(__x1, __x2, __x3, __x4, __c); 232280304Sjkim} 233280304Sjkim 234280304Sjkimtemplate <class _AlgPolicy, 235280304Sjkim class _Compare, 236280304Sjkim class _RandomAccessIterator, 237280304Sjkim __enable_if_t<__use_branchless_sort<_Compare, _RandomAccessIterator>::value, int> = 0> 238280304Sjkiminline _LIBCPP_HIDE_FROM_ABI void __sort5_maybe_branchless( 239280304Sjkim _RandomAccessIterator __x1, 240280304Sjkim _RandomAccessIterator __x2, 24155714Skris _RandomAccessIterator __x3, 242280304Sjkim _RandomAccessIterator __x4, 243280304Sjkim _RandomAccessIterator __x5, 244280304Sjkim _Compare __c) { 245280304Sjkim std::__cond_swap<_Compare>(__x1, __x2, __c); 246280304Sjkim std::__cond_swap<_Compare>(__x4, __x5, __c); 247280304Sjkim std::__partially_sorted_swap<_Compare>(__x3, __x4, __x5, __c); 248280304Sjkim std::__cond_swap<_Compare>(__x2, __x5, __c); 249280304Sjkim std::__partially_sorted_swap<_Compare>(__x1, __x3, __x4, __c); 250280304Sjkim std::__partially_sorted_swap<_Compare>(__x2, __x3, __x4, __c); 251280304Sjkim} 252280304Sjkim 253280304Sjkimtemplate <class _AlgPolicy, 25455714Skris class _Compare, 255280304Sjkim class _RandomAccessIterator, 256280304Sjkim __enable_if_t<!__use_branchless_sort<_Compare, _RandomAccessIterator>::value, int> = 0> 257280304Sjkiminline _LIBCPP_HIDE_FROM_ABI void __sort5_maybe_branchless( 258280304Sjkim _RandomAccessIterator __x1, 259280304Sjkim _RandomAccessIterator __x2, 260280304Sjkim _RandomAccessIterator __x3, 261280304Sjkim _RandomAccessIterator __x4, 262280304Sjkim _RandomAccessIterator __x5, 263280304Sjkim _Compare __c) { 264280304Sjkim std::__sort5<_AlgPolicy, _Compare, _RandomAccessIterator>( 265280304Sjkim std::move(__x1), std::move(__x2), std::move(__x3), std::move(__x4), std::move(__x5), __c); 266280304Sjkim} 267280304Sjkim 268280304Sjkim// Assumes size > 0 269280304Sjkimtemplate <class _AlgPolicy, class _Compare, class _BidirectionalIterator> 270280304Sjkim_LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX14 void 271280304Sjkim__selection_sort(_BidirectionalIterator __first, _BidirectionalIterator __last, _Compare __comp) { 272280304Sjkim _BidirectionalIterator __lm1 = __last; 27355714Skris for (--__lm1; __first != __lm1; ++__first) { 274280304Sjkim _BidirectionalIterator __i = std::__min_element<_Compare>(__first, __last, __comp); 275280304Sjkim if (__i != __first) 276280304Sjkim _IterOps<_AlgPolicy>::iter_swap(__first, __i); 277280304Sjkim } 278280304Sjkim} 279280304Sjkim 280280304Sjkim// Sort the iterator range [__first, __last) using the comparator __comp using 281280304Sjkim// the insertion sort algorithm. 282280304Sjkimtemplate <class _AlgPolicy, class _Compare, class _BidirectionalIterator> 283280304Sjkim_LIBCPP_HIDE_FROM_ABI void 284280304Sjkim__insertion_sort(_BidirectionalIterator __first, _BidirectionalIterator __last, _Compare __comp) { 285280304Sjkim using _Ops = _IterOps<_AlgPolicy>; 28655714Skris 287280304Sjkim typedef typename iterator_traits<_BidirectionalIterator>::value_type value_type; 288280304Sjkim if (__first == __last) 28955714Skris return; 290280304Sjkim _BidirectionalIterator __i = __first; 291280304Sjkim for (++__i; __i != __last; ++__i) { 29255714Skris _BidirectionalIterator __j = __i; 293280304Sjkim --__j; 294280304Sjkim if (__comp(*__i, *__j)) { 295280304Sjkim value_type __t(_Ops::__iter_move(__i)); 296280304Sjkim _BidirectionalIterator __k = __j; 297280304Sjkim __j = __i; 298280304Sjkim do { 299280304Sjkim *__j = _Ops::__iter_move(__k); 300280304Sjkim __j = __k; 30155714Skris } while (__j != __first && __comp(__t, *--__k)); 302280304Sjkim *__j = std::move(__t); 303280304Sjkim } 304280304Sjkim } 305280304Sjkim} 306280304Sjkim 307280304Sjkim// Sort the iterator range [__first, __last) using the comparator __comp using 308280304Sjkim// the insertion sort algorithm. Insertion sort has two loops, outer and inner. 309280304Sjkim// The implementation below has no bounds check (unguarded) for the inner loop. 310280304Sjkim// Assumes that there is an element in the position (__first - 1) and that each 311280304Sjkim// element in the input range is greater or equal to the element at __first - 1. 312280304Sjkimtemplate <class _AlgPolicy, class _Compare, class _RandomAccessIterator> 313280304Sjkim_LIBCPP_HIDE_FROM_ABI void 314280304Sjkim__insertion_sort_unguarded(_RandomAccessIterator const __first, _RandomAccessIterator __last, _Compare __comp) { 315280304Sjkim using _Ops = _IterOps<_AlgPolicy>; 316280304Sjkim typedef typename iterator_traits<_RandomAccessIterator>::difference_type difference_type; 317280304Sjkim typedef typename iterator_traits<_RandomAccessIterator>::value_type value_type; 318280304Sjkim if (__first == __last) 319280304Sjkim return; 320280304Sjkim const _RandomAccessIterator __leftmost = __first - difference_type(1); 321280304Sjkim (void)__leftmost; // can be unused when assertions are disabled 322280304Sjkim for (_RandomAccessIterator __i = __first + difference_type(1); __i != __last; ++__i) { 32355714Skris _RandomAccessIterator __j = __i - difference_type(1); 324280304Sjkim if (__comp(*__i, *__j)) { 325280304Sjkim value_type __t(_Ops::__iter_move(__i)); 326280304Sjkim _RandomAccessIterator __k = __j; 327280304Sjkim __j = __i; 328280304Sjkim do { 329280304Sjkim *__j = _Ops::__iter_move(__k); 330280304Sjkim __j = __k; 331280304Sjkim _LIBCPP_ASSERT_VALID_ELEMENT_ACCESS( 33255714Skris __k != __leftmost, 333280304Sjkim "Would read out of bounds, does your comparator satisfy the strict-weak ordering requirement?"); 334280304Sjkim } while (__comp(__t, *--__k)); // No need for bounds check due to the assumption stated above. 335280304Sjkim *__j = std::move(__t); 336280304Sjkim } 337280304Sjkim } 338280304Sjkim} 33955714Skris 340280304Sjkimtemplate <class _AlgPolicy, class _Comp, class _RandomAccessIterator> 34155714Skris_LIBCPP_HIDE_FROM_ABI bool 342280304Sjkim__insertion_sort_incomplete(_RandomAccessIterator __first, _RandomAccessIterator __last, _Comp __comp) { 343280304Sjkim using _Ops = _IterOps<_AlgPolicy>; 344280304Sjkim 34555714Skris typedef typename iterator_traits<_RandomAccessIterator>::difference_type difference_type; 346280304Sjkim switch (__last - __first) { 347280304Sjkim case 0: 34855714Skris case 1: 349280304Sjkim return true; 350280304Sjkim case 2: 35155714Skris if (__comp(*--__last, *__first)) 352280304Sjkim _Ops::iter_swap(__first, __last); 353280304Sjkim return true; 354280304Sjkim case 3: 355280304Sjkim std::__sort3_maybe_branchless<_AlgPolicy, _Comp>(__first, __first + difference_type(1), --__last, __comp); 356280304Sjkim return true; 357280304Sjkim case 4: 35855714Skris std::__sort4_maybe_branchless<_AlgPolicy, _Comp>( 359280304Sjkim __first, __first + difference_type(1), __first + difference_type(2), --__last, __comp); 360280304Sjkim return true; 361280304Sjkim case 5: 362280304Sjkim std::__sort5_maybe_branchless<_AlgPolicy, _Comp>( 363280304Sjkim __first, 364280304Sjkim __first + difference_type(1), 365280304Sjkim __first + difference_type(2), 366280304Sjkim __first + difference_type(3), 367280304Sjkim --__last, 368280304Sjkim __comp); 369280304Sjkim return true; 370280304Sjkim } 371280304Sjkim typedef typename iterator_traits<_RandomAccessIterator>::value_type value_type; 372280304Sjkim _RandomAccessIterator __j = __first + difference_type(2); 37355714Skris std::__sort3_maybe_branchless<_AlgPolicy, _Comp>(__first, __first + difference_type(1), __j, __comp); 374280304Sjkim const unsigned __limit = 8; 375280304Sjkim unsigned __count = 0; 376284285Sjkim for (_RandomAccessIterator __i = __j + difference_type(1); __i != __last; ++__i) { 377280304Sjkim if (__comp(*__i, *__j)) { 378280304Sjkim value_type __t(_Ops::__iter_move(__i)); 379280304Sjkim _RandomAccessIterator __k = __j; 380280304Sjkim __j = __i; 381280304Sjkim do { 382284285Sjkim *__j = _Ops::__iter_move(__k); 383284285Sjkim __j = __k; 384284285Sjkim } while (__j != __first && __comp(__t, *--__k)); 38555714Skris *__j = std::move(__t); 386280304Sjkim if (++__count == __limit) 387280304Sjkim return ++__i == __last; 388280304Sjkim } 38955714Skris __j = __i; 390280304Sjkim } 391280304Sjkim return true; 392280304Sjkim} 39389840Skris 394280304Sjkimtemplate <class _AlgPolicy, class _RandomAccessIterator> 395280304Sjkiminline _LIBCPP_HIDE_FROM_ABI void __swap_bitmap_pos( 396280304Sjkim _RandomAccessIterator __first, _RandomAccessIterator __last, uint64_t& __left_bitset, uint64_t& __right_bitset) { 397280304Sjkim using _Ops = _IterOps<_AlgPolicy>; 398280304Sjkim typedef typename std::iterator_traits<_RandomAccessIterator>::difference_type difference_type; 399280304Sjkim // Swap one pair on each iteration as long as both bitsets have at least one 400280304Sjkim // element for swapping. 401280304Sjkim while (__left_bitset != 0 && __right_bitset != 0) { 402280304Sjkim difference_type __tz_left = __libcpp_ctz(__left_bitset); 40355714Skris __left_bitset = __libcpp_blsr(__left_bitset); 404280304Sjkim difference_type __tz_right = __libcpp_ctz(__right_bitset); 405295016Sjkim __right_bitset = __libcpp_blsr(__right_bitset); 406280304Sjkim _Ops::iter_swap(__first + __tz_left, __last - __tz_right); 407280304Sjkim } 408280304Sjkim} 409280304Sjkim 410280304Sjkimtemplate <class _Compare, 41155714Skris class _RandomAccessIterator, 412280304Sjkim class _ValueType = typename iterator_traits<_RandomAccessIterator>::value_type> 413280304Sjkiminline _LIBCPP_HIDE_FROM_ABI void 414280304Sjkim__populate_left_bitset(_RandomAccessIterator __first, _Compare __comp, _ValueType& __pivot, uint64_t& __left_bitset) { 415280304Sjkim // Possible vectorization. With a proper "-march" flag, the following loop 416280304Sjkim // will be compiled into a set of SIMD instructions. 417280304Sjkim _RandomAccessIterator __iter = __first; 418280304Sjkim for (int __j = 0; __j < __detail::__block_size;) { 419280304Sjkim bool __comp_result = !__comp(*__iter, __pivot); 420280304Sjkim __left_bitset |= (static_cast<uint64_t>(__comp_result) << __j); 421280304Sjkim __j++; 422280304Sjkim ++__iter; 423280304Sjkim } 424280304Sjkim} 425280304Sjkim 42655714Skristemplate <class _Compare, 427280304Sjkim class _RandomAccessIterator, 428280304Sjkim class _ValueType = typename iterator_traits<_RandomAccessIterator>::value_type> 429280304Sjkiminline _LIBCPP_HIDE_FROM_ABI void 430280304Sjkim__populate_right_bitset(_RandomAccessIterator __lm1, _Compare __comp, _ValueType& __pivot, uint64_t& __right_bitset) { 431280304Sjkim // Possible vectorization. With a proper "-march" flag, the following loop 432280304Sjkim // will be compiled into a set of SIMD instructions. 433280304Sjkim _RandomAccessIterator __iter = __lm1; 434280304Sjkim for (int __j = 0; __j < __detail::__block_size;) { 435280304Sjkim bool __comp_result = __comp(*__iter, __pivot); 436280304Sjkim __right_bitset |= (static_cast<uint64_t>(__comp_result) << __j); 437280304Sjkim __j++; 438280304Sjkim --__iter; 439280304Sjkim } 440280304Sjkim} 441280304Sjkim 442280304Sjkimtemplate <class _AlgPolicy, 443280304Sjkim class _Compare, 444280304Sjkim class _RandomAccessIterator, 445280304Sjkim class _ValueType = typename iterator_traits<_RandomAccessIterator>::value_type> 446280304Sjkiminline _LIBCPP_HIDE_FROM_ABI void __bitset_partition_partial_blocks( 447280304Sjkim _RandomAccessIterator& __first, 448280304Sjkim _RandomAccessIterator& __lm1, 449280304Sjkim _Compare __comp, 450280304Sjkim _ValueType& __pivot, 451280304Sjkim uint64_t& __left_bitset, 452280304Sjkim uint64_t& __right_bitset) { 45355714Skris typedef typename std::iterator_traits<_RandomAccessIterator>::difference_type difference_type; 454280304Sjkim difference_type __remaining_len = __lm1 - __first + 1; 455280304Sjkim difference_type __l_size; 45655714Skris difference_type __r_size; 457280304Sjkim if (__left_bitset == 0 && __right_bitset == 0) { 458280304Sjkim __l_size = __remaining_len / 2; 459280304Sjkim __r_size = __remaining_len - __l_size; 460280304Sjkim } else if (__left_bitset == 0) { 461280304Sjkim // We know at least one side is a full block. 46255714Skris __l_size = __remaining_len - __detail::__block_size; 463280304Sjkim __r_size = __detail::__block_size; 46455714Skris } else { // if (__right_bitset == 0) 465280304Sjkim __l_size = __detail::__block_size; 466280304Sjkim __r_size = __remaining_len - __detail::__block_size; 467280304Sjkim } 468280304Sjkim // Record the comparison outcomes for the elements currently on the left side. 469280304Sjkim if (__left_bitset == 0) { 470280304Sjkim _RandomAccessIterator __iter = __first; 47155714Skris for (int __j = 0; __j < __l_size; __j++) { 472280304Sjkim bool __comp_result = !__comp(*__iter, __pivot); 473280304Sjkim __left_bitset |= (static_cast<uint64_t>(__comp_result) << __j); 474280304Sjkim ++__iter; 475280304Sjkim } 476280304Sjkim } 477280304Sjkim // Record the comparison outcomes for the elements currently on the right 478280304Sjkim // side. 479280304Sjkim if (__right_bitset == 0) { 480280304Sjkim _RandomAccessIterator __iter = __lm1; 481280304Sjkim for (int __j = 0; __j < __r_size; __j++) { 482280304Sjkim bool __comp_result = __comp(*__iter, __pivot); 483280304Sjkim __right_bitset |= (static_cast<uint64_t>(__comp_result) << __j); 484280304Sjkim --__iter; 485284285Sjkim } 486284285Sjkim } 487284285Sjkim std::__swap_bitmap_pos<_AlgPolicy, _RandomAccessIterator>(__first, __lm1, __left_bitset, __right_bitset); 488280304Sjkim __first += (__left_bitset == 0) ? __l_size : 0; 489284285Sjkim __lm1 -= (__right_bitset == 0) ? __r_size : 0; 490284285Sjkim} 491280304Sjkim 492284285Sjkimtemplate <class _AlgPolicy, class _RandomAccessIterator> 493284285Sjkiminline _LIBCPP_HIDE_FROM_ABI void __swap_bitmap_pos_within( 494284285Sjkim _RandomAccessIterator& __first, _RandomAccessIterator& __lm1, uint64_t& __left_bitset, uint64_t& __right_bitset) { 495284285Sjkim using _Ops = _IterOps<_AlgPolicy>; 496284285Sjkim typedef typename std::iterator_traits<_RandomAccessIterator>::difference_type difference_type; 497284285Sjkim if (__left_bitset) { 498284285Sjkim // Swap within the left side. Need to find set positions in the reverse 499284285Sjkim // order. 500284285Sjkim while (__left_bitset != 0) { 501284285Sjkim difference_type __tz_left = __detail::__block_size - 1 - __libcpp_clz(__left_bitset); 502284285Sjkim __left_bitset &= (static_cast<uint64_t>(1) << __tz_left) - 1; 503284285Sjkim _RandomAccessIterator __it = __first + __tz_left; 504284285Sjkim if (__it != __lm1) { 505284285Sjkim _Ops::iter_swap(__it, __lm1); 506284285Sjkim } 507280304Sjkim --__lm1; 508280304Sjkim } 509280304Sjkim __first = __lm1 + difference_type(1); 510280304Sjkim } else if (__right_bitset) { 511280304Sjkim // Swap within the right side. Need to find set positions in the reverse 512280304Sjkim // order. 513280304Sjkim while (__right_bitset != 0) { 514280304Sjkim difference_type __tz_right = __detail::__block_size - 1 - __libcpp_clz(__right_bitset); 515284285Sjkim __right_bitset &= (static_cast<uint64_t>(1) << __tz_right) - 1; 516280304Sjkim _RandomAccessIterator __it = __lm1 - __tz_right; 517280304Sjkim if (__it != __first) { 518280304Sjkim _Ops::iter_swap(__it, __first); 519280304Sjkim } 520280304Sjkim ++__first; 521284285Sjkim } 522284285Sjkim } 523284285Sjkim} 524284285Sjkim 525284285Sjkim// Partition [__first, __last) using the comparator __comp. *__first has the 526284285Sjkim// chosen pivot. Elements that are equivalent are kept to the left of the 527284285Sjkim// pivot. Returns the iterator for the pivot and a bool value which is true if 528284285Sjkim// the provided range is already sorted, false otherwise. We assume that the 529306196Sjkim// length of the range is at least three elements. 530306196Sjkim// 531284285Sjkim// __bitset_partition uses bitsets for storing outcomes of the comparisons 532284285Sjkim// between the pivot and other elements. 533280304Sjkimtemplate <class _AlgPolicy, class _RandomAccessIterator, class _Compare> 534280266Sdelphij_LIBCPP_HIDE_FROM_ABI std::pair<_RandomAccessIterator, bool> 535280266Sdelphij__bitset_partition(_RandomAccessIterator __first, _RandomAccessIterator __last, _Compare __comp) { 536280266Sdelphij using _Ops = _IterOps<_AlgPolicy>; 537280266Sdelphij typedef typename std::iterator_traits<_RandomAccessIterator>::value_type value_type; 538284285Sjkim typedef typename std::iterator_traits<_RandomAccessIterator>::difference_type difference_type; 539280304Sjkim _LIBCPP_ASSERT_INTERNAL(__last - __first >= difference_type(3), ""); 540280304Sjkim const _RandomAccessIterator __begin = __first; // used for bounds checking, those are not moved around 541280304Sjkim const _RandomAccessIterator __end = __last; 542280304Sjkim (void)__end; // 543284285Sjkim 544284285Sjkim value_type __pivot(_Ops::__iter_move(__first)); 545284285Sjkim // Find the first element greater than the pivot. 546284285Sjkim if (__comp(__pivot, *(__last - difference_type(1)))) { 547284285Sjkim // Not guarded since we know the last element is greater than the pivot. 548280304Sjkim do { 54955714Skris ++__first; 550284285Sjkim _LIBCPP_ASSERT_VALID_ELEMENT_ACCESS( 551284285Sjkim __first != __end, 552284285Sjkim "Would read out of bounds, does your comparator satisfy the strict-weak ordering requirement?"); 553101621Snectar } while (!__comp(__pivot, *__first)); 554284285Sjkim } else { 555280304Sjkim while (++__first < __last && !__comp(__pivot, *__first)) { 55655714Skris } 55755714Skris } 558280304Sjkim // Find the last element less than or equal to the pivot. 559280304Sjkim if (__first < __last) { 560280304Sjkim // It will be always guarded because __introsort will do the median-of-three 561280304Sjkim // before calling this. 562280304Sjkim do { 563280304Sjkim _LIBCPP_ASSERT_VALID_ELEMENT_ACCESS( 564280304Sjkim __last != __begin, 565280304Sjkim "Would read out of bounds, does your comparator satisfy the strict-weak ordering requirement?"); 56655714Skris --__last; 567280304Sjkim } while (__comp(__pivot, *__last)); 568280304Sjkim } 569280304Sjkim // If the first element greater than the pivot is at or after the 570280304Sjkim // last element less than or equal to the pivot, then we have covered the 571280304Sjkim // entire range without swapping elements. This implies the range is already 572280304Sjkim // partitioned. 573280304Sjkim bool __already_partitioned = __first >= __last; 574280304Sjkim if (!__already_partitioned) { 57555714Skris _Ops::iter_swap(__first, __last); 576280304Sjkim ++__first; 577280304Sjkim } 578280304Sjkim 579280304Sjkim // In [__first, __last) __last is not inclusive. From now on, it uses last 580280304Sjkim // minus one to be inclusive on both sides. 581280304Sjkim _RandomAccessIterator __lm1 = __last - difference_type(1); 58255714Skris uint64_t __left_bitset = 0; 583280304Sjkim uint64_t __right_bitset = 0; 584280304Sjkim 585280304Sjkim // Reminder: length = __lm1 - __first + 1. 586280304Sjkim while (__lm1 - __first >= 2 * __detail::__block_size - 1) { 587280304Sjkim // Record the comparison outcomes for the elements currently on the left 588280304Sjkim // side. 589280304Sjkim if (__left_bitset == 0) 590280304Sjkim std::__populate_left_bitset<_Compare>(__first, __comp, __pivot, __left_bitset); 591280304Sjkim // Record the comparison outcomes for the elements currently on the right 592280304Sjkim // side. 593280304Sjkim if (__right_bitset == 0) 594280304Sjkim std::__populate_right_bitset<_Compare>(__lm1, __comp, __pivot, __right_bitset); 595280304Sjkim // Swap the elements recorded to be the candidates for swapping in the 596280304Sjkim // bitsets. 597280304Sjkim std::__swap_bitmap_pos<_AlgPolicy, _RandomAccessIterator>(__first, __lm1, __left_bitset, __right_bitset); 598295016Sjkim // Only advance the iterator if all the elements that need to be moved to 599295016Sjkim // other side were moved. 600295016Sjkim __first += (__left_bitset == 0) ? difference_type(__detail::__block_size) : difference_type(0); 601295016Sjkim __lm1 -= (__right_bitset == 0) ? difference_type(__detail::__block_size) : difference_type(0); 602295016Sjkim } 603280304Sjkim // Now, we have a less-than a block worth of elements on at least one of the 604280304Sjkim // sides. 605280304Sjkim std::__bitset_partition_partial_blocks<_AlgPolicy, _Compare>( 606280304Sjkim __first, __lm1, __comp, __pivot, __left_bitset, __right_bitset); 607280304Sjkim // At least one the bitsets would be empty. For the non-empty one, we need to 608280304Sjkim // properly partition the elements that appear within that bitset. 609280304Sjkim std::__swap_bitmap_pos_within<_AlgPolicy>(__first, __lm1, __left_bitset, __right_bitset); 610280304Sjkim 611280304Sjkim // Move the pivot to its correct position. 612280304Sjkim _RandomAccessIterator __pivot_pos = __first - difference_type(1); 61355714Skris if (__begin != __pivot_pos) { 614280304Sjkim *__begin = _Ops::__iter_move(__pivot_pos); 615280304Sjkim } 616280304Sjkim *__pivot_pos = std::move(__pivot); 617280304Sjkim return std::make_pair(__pivot_pos, __already_partitioned); 618280304Sjkim} 619280304Sjkim 620280304Sjkim// Partition [__first, __last) using the comparator __comp. *__first has the 621280304Sjkim// chosen pivot. Elements that are equivalent are kept to the right of the 622280304Sjkim// pivot. Returns the iterator for the pivot and a bool value which is true if 623280304Sjkim// the provided range is already sorted, false otherwise. We assume that the 624280304Sjkim// length of the range is at least three elements. 625280304Sjkimtemplate <class _AlgPolicy, class _RandomAccessIterator, class _Compare> 626280304Sjkim_LIBCPP_HIDE_FROM_ABI std::pair<_RandomAccessIterator, bool> 627280304Sjkim__partition_with_equals_on_right(_RandomAccessIterator __first, _RandomAccessIterator __last, _Compare __comp) { 628280304Sjkim using _Ops = _IterOps<_AlgPolicy>; 629280304Sjkim typedef typename iterator_traits<_RandomAccessIterator>::difference_type difference_type; 630280304Sjkim typedef typename std::iterator_traits<_RandomAccessIterator>::value_type value_type; 631280304Sjkim _LIBCPP_ASSERT_INTERNAL(__last - __first >= difference_type(3), ""); 632280304Sjkim const _RandomAccessIterator __begin = __first; // used for bounds checking, those are not moved around 633280304Sjkim const _RandomAccessIterator __end = __last; 634280304Sjkim (void)__end; // 63555714Skris value_type __pivot(_Ops::__iter_move(__first)); 636280304Sjkim // Find the first element greater or equal to the pivot. It will be always 637280304Sjkim // guarded because __introsort will do the median-of-three before calling 638280304Sjkim // this. 639280304Sjkim do { 640280304Sjkim ++__first; 641280304Sjkim _LIBCPP_ASSERT_VALID_ELEMENT_ACCESS( 642280304Sjkim __first != __end, 643280304Sjkim "Would read out of bounds, does your comparator satisfy the strict-weak ordering requirement?"); 644280304Sjkim } while (__comp(*__first, __pivot)); 645280304Sjkim 646280304Sjkim // Find the last element less than the pivot. 64755714Skris if (__begin == __first - difference_type(1)) { 648280304Sjkim while (__first < __last && !__comp(*--__last, __pivot)) 649280304Sjkim ; 650280304Sjkim } else { 651280304Sjkim // Guarded. 652280304Sjkim do { 653280304Sjkim _LIBCPP_ASSERT_VALID_ELEMENT_ACCESS( 654280304Sjkim __last != __begin, 655280304Sjkim "Would read out of bounds, does your comparator satisfy the strict-weak ordering requirement?"); 656280304Sjkim --__last; 657280304Sjkim } while (!__comp(*__last, __pivot)); 658280304Sjkim } 659280304Sjkim 660280304Sjkim // If the first element greater than or equal to the pivot is at or after the 661280304Sjkim // last element less than the pivot, then we have covered the entire range 662280304Sjkim // without swapping elements. This implies the range is already partitioned. 663280304Sjkim bool __already_partitioned = __first >= __last; 664280304Sjkim // Go through the remaining elements. Swap pairs of elements (one to the 665280304Sjkim // right of the pivot and the other to left of the pivot) that are not on the 666280304Sjkim // correct side of the pivot. 66755714Skris while (__first < __last) { 668280304Sjkim _Ops::iter_swap(__first, __last); 669280304Sjkim do { 670280304Sjkim ++__first; 671280304Sjkim _LIBCPP_ASSERT_VALID_ELEMENT_ACCESS( 672280304Sjkim __first != __end, 673280304Sjkim "Would read out of bounds, does your comparator satisfy the strict-weak ordering requirement?"); 67455714Skris } while (__comp(*__first, __pivot)); 675280304Sjkim do { 676280304Sjkim _LIBCPP_ASSERT_VALID_ELEMENT_ACCESS( 677280304Sjkim __last != __begin, 678280304Sjkim "Would read out of bounds, does your comparator satisfy the strict-weak ordering requirement?"); 679280304Sjkim --__last; 68055714Skris } while (!__comp(*__last, __pivot)); 681280304Sjkim } 68255714Skris // Move the pivot to its correct position. 683280304Sjkim _RandomAccessIterator __pivot_pos = __first - difference_type(1); 684280304Sjkim if (__begin != __pivot_pos) { 685280304Sjkim *__begin = _Ops::__iter_move(__pivot_pos); 686280304Sjkim } 687280304Sjkim *__pivot_pos = std::move(__pivot); 688280304Sjkim return std::make_pair(__pivot_pos, __already_partitioned); 689280304Sjkim} 690280304Sjkim 691280304Sjkim// Similar to the above function. Elements equivalent to the pivot are put to 692295016Sjkim// the left of the pivot. Returns the iterator to the pivot element. 693295016Sjkimtemplate <class _AlgPolicy, class _RandomAccessIterator, class _Compare> 694280304Sjkim_LIBCPP_HIDE_FROM_ABI _RandomAccessIterator 695295016Sjkim__partition_with_equals_on_left(_RandomAccessIterator __first, _RandomAccessIterator __last, _Compare __comp) { 696295016Sjkim using _Ops = _IterOps<_AlgPolicy>; 697295016Sjkim typedef typename iterator_traits<_RandomAccessIterator>::difference_type difference_type; 698280304Sjkim typedef typename std::iterator_traits<_RandomAccessIterator>::value_type value_type; 699280304Sjkim // TODO(LLVM18): Make __begin const, see https://reviews.llvm.org/D147089#4349748 700280304Sjkim _RandomAccessIterator __begin = __first; // used for bounds checking, those are not moved around 701280304Sjkim const _RandomAccessIterator __end = __last; 702280304Sjkim (void)__end; // 703280304Sjkim value_type __pivot(_Ops::__iter_move(__first)); 704280304Sjkim if (__comp(__pivot, *(__last - difference_type(1)))) { 705280304Sjkim // Guarded. 706295016Sjkim do { 707295016Sjkim ++__first; 708295016Sjkim _LIBCPP_ASSERT_VALID_ELEMENT_ACCESS( 709295016Sjkim __first != __end, 710295016Sjkim "Would read out of bounds, does your comparator satisfy the strict-weak ordering requirement?"); 711295016Sjkim } while (!__comp(__pivot, *__first)); 712295016Sjkim } else { 713280304Sjkim while (++__first < __last && !__comp(__pivot, *__first)) { 714280304Sjkim } 715280304Sjkim } 716280304Sjkim 717280304Sjkim if (__first < __last) { 718280304Sjkim // It will be always guarded because __introsort will do the 719280304Sjkim // median-of-three before calling this. 720280304Sjkim do { 721280304Sjkim _LIBCPP_ASSERT_VALID_ELEMENT_ACCESS( 72255714Skris __last != __begin, 723280304Sjkim "Would read out of bounds, does your comparator satisfy the strict-weak ordering requirement?"); 724280304Sjkim --__last; 72555714Skris } while (__comp(__pivot, *__last)); 726280304Sjkim } 727280304Sjkim while (__first < __last) { 728280304Sjkim _Ops::iter_swap(__first, __last); 729280304Sjkim do { 730280304Sjkim ++__first; 731280304Sjkim _LIBCPP_ASSERT_VALID_ELEMENT_ACCESS( 732280304Sjkim __first != __end, 733280304Sjkim "Would read out of bounds, does your comparator satisfy the strict-weak ordering requirement?"); 734280304Sjkim } while (!__comp(__pivot, *__first)); 735280304Sjkim do { 736280304Sjkim _LIBCPP_ASSERT_VALID_ELEMENT_ACCESS( 737280304Sjkim __last != __begin, 738280304Sjkim "Would read out of bounds, does your comparator satisfy the strict-weak ordering requirement?"); 73955714Skris --__last; 740280304Sjkim } while (__comp(__pivot, *__last)); 741280304Sjkim } 742280304Sjkim _RandomAccessIterator __pivot_pos = __first - difference_type(1); 74355714Skris if (__begin != __pivot_pos) { 744280304Sjkim *__begin = _Ops::__iter_move(__pivot_pos); 745280304Sjkim } 746280304Sjkim *__pivot_pos = std::move(__pivot); 747280304Sjkim return __first; 748280304Sjkim} 749280304Sjkim 750280304Sjkim// The main sorting function. Implements introsort combined with other ideas: 751280304Sjkim// - option of using block quick sort for partitioning, 752280304Sjkim// - guarded and unguarded insertion sort for small lengths, 753280304Sjkim// - Tuckey's ninther technique for computing the pivot, 754280304Sjkim// - check on whether partition was not required. 755280304Sjkim// The implementation is partly based on Orson Peters' pattern-defeating 756280304Sjkim// quicksort, published at: <https://github.com/orlp/pdqsort>. 757280304Sjkimtemplate <class _AlgPolicy, class _Compare, class _RandomAccessIterator, bool _UseBitSetPartition> 758280304Sjkimvoid __introsort(_RandomAccessIterator __first, 759280304Sjkim _RandomAccessIterator __last, 760280304Sjkim _Compare __comp, 761280304Sjkim typename iterator_traits<_RandomAccessIterator>::difference_type __depth, 762280304Sjkim bool __leftmost = true) { 763280304Sjkim using _Ops = _IterOps<_AlgPolicy>; 764280304Sjkim typedef typename iterator_traits<_RandomAccessIterator>::difference_type difference_type; 765280304Sjkim using _Comp_ref = __comp_ref_type<_Compare>; 766280304Sjkim // Upper bound for using insertion sort for sorting. 767280304Sjkim _LIBCPP_CONSTEXPR difference_type __limit = 24; 768280304Sjkim // Lower bound for using Tuckey's ninther technique for median computation. 769280304Sjkim _LIBCPP_CONSTEXPR difference_type __ninther_threshold = 128; 77055714Skris while (true) { 771280304Sjkim difference_type __len = __last - __first; 772280304Sjkim switch (__len) { 773280304Sjkim case 0: 774280304Sjkim case 1: 775280304Sjkim return; 776280304Sjkim case 2: 777280304Sjkim if (__comp(*--__last, *__first)) 778280304Sjkim _Ops::iter_swap(__first, __last); 779280304Sjkim return; 780280304Sjkim case 3: 781280304Sjkim std::__sort3_maybe_branchless<_AlgPolicy, _Compare>(__first, __first + difference_type(1), --__last, __comp); 782280304Sjkim return; 783280304Sjkim case 4: 784280304Sjkim std::__sort4_maybe_branchless<_AlgPolicy, _Compare>( 785280304Sjkim __first, __first + difference_type(1), __first + difference_type(2), --__last, __comp); 786280304Sjkim return; 787280304Sjkim case 5: 788280304Sjkim std::__sort5_maybe_branchless<_AlgPolicy, _Compare>( 78955714Skris __first, 790280304Sjkim __first + difference_type(1), 791280304Sjkim __first + difference_type(2), 792280304Sjkim __first + difference_type(3), 793280304Sjkim --__last, 794280304Sjkim __comp); 79555714Skris return; 796280304Sjkim } 797280304Sjkim // Use insertion sort if the length of the range is below the specified limit. 798280304Sjkim if (__len < __limit) { 799280304Sjkim if (__leftmost) { 800280304Sjkim std::__insertion_sort<_AlgPolicy, _Compare>(__first, __last, __comp); 801280304Sjkim } else { 802280304Sjkim std::__insertion_sort_unguarded<_AlgPolicy, _Compare>(__first, __last, __comp); 803280304Sjkim } 804280304Sjkim return; 805280304Sjkim } 806280304Sjkim if (__depth == 0) { 807280304Sjkim // Fallback to heap sort as Introsort suggests. 808280304Sjkim std::__partial_sort<_AlgPolicy, _Compare>(__first, __last, __last, __comp); 809280304Sjkim return; 81055714Skris } 811280304Sjkim --__depth; 812280304Sjkim { 813280304Sjkim difference_type __half_len = __len / 2; 814280304Sjkim // Use Tuckey's ninther technique or median of 3 for pivot selection 815280304Sjkim // depending on the length of the range being sorted. 816280304Sjkim if (__len > __ninther_threshold) { 817280304Sjkim std::__sort3<_AlgPolicy, _Compare>(__first, __first + __half_len, __last - difference_type(1), __comp); 81855714Skris std::__sort3<_AlgPolicy, _Compare>( 819280304Sjkim __first + difference_type(1), __first + (__half_len - 1), __last - difference_type(2), __comp); 820280304Sjkim std::__sort3<_AlgPolicy, _Compare>( 821280304Sjkim __first + difference_type(2), __first + (__half_len + 1), __last - difference_type(3), __comp); 822306196Sjkim std::__sort3<_AlgPolicy, _Compare>( 823280304Sjkim __first + (__half_len - 1), __first + __half_len, __first + (__half_len + 1), __comp); 824280304Sjkim _Ops::iter_swap(__first, __first + __half_len); 825280304Sjkim } else { 82655714Skris std::__sort3<_AlgPolicy, _Compare>(__first + __half_len, __first, __last - difference_type(1), __comp); 827280304Sjkim } 828280304Sjkim } 829280304Sjkim // The elements to the left of the current iterator range are already 830280304Sjkim // sorted. If the current iterator range to be sorted is not the 831280304Sjkim // leftmost part of the entire iterator range and the pivot is same as 832280304Sjkim // the highest element in the range to the left, then we know that all 833280304Sjkim // the elements in the range [first, pivot] would be equal to the pivot, 834280304Sjkim // assuming the equal elements are put on the left side when 835280304Sjkim // partitioned. This also means that we do not need to sort the left 836280304Sjkim // side of the partition. 837280304Sjkim if (!__leftmost && !__comp(*(__first - difference_type(1)), *__first)) { 838280304Sjkim __first = std::__partition_with_equals_on_left<_AlgPolicy, _RandomAccessIterator, _Comp_ref>( 839280304Sjkim __first, __last, _Comp_ref(__comp)); 840280304Sjkim continue; 841280304Sjkim } 842280304Sjkim // Use bitset partition only if asked for. 843280304Sjkim auto __ret = _UseBitSetPartition 844280304Sjkim ? std::__bitset_partition<_AlgPolicy, _RandomAccessIterator, _Compare>(__first, __last, __comp) 84555714Skris : std::__partition_with_equals_on_right<_AlgPolicy, _RandomAccessIterator, _Compare>( 846280304Sjkim __first, __last, __comp); 847280304Sjkim _RandomAccessIterator __i = __ret.first; 848280304Sjkim // [__first, __i) < *__i and *__i <= [__i+1, __last) 849280304Sjkim // If we were given a perfect partition, see if insertion sort is quick... 85055714Skris if (__ret.second) { 851280304Sjkim bool __fs = std::__insertion_sort_incomplete<_AlgPolicy, _Compare>(__first, __i, __comp); 852280304Sjkim if (std::__insertion_sort_incomplete<_AlgPolicy, _Compare>(__i + difference_type(1), __last, __comp)) { 853280304Sjkim if (__fs) 854280304Sjkim return; 855280304Sjkim __last = __i; 856280304Sjkim continue; 85755714Skris } else { 858280304Sjkim if (__fs) { 859280304Sjkim __first = ++__i; 860280304Sjkim continue; 861280304Sjkim } 862280304Sjkim } 863280304Sjkim } 864280304Sjkim // Sort the left partiton recursively and the right partition with tail recursion elimination. 865280304Sjkim std::__introsort<_AlgPolicy, _Compare, _RandomAccessIterator, _UseBitSetPartition>( 866280304Sjkim __first, __i, __comp, __depth, __leftmost); 867280304Sjkim __leftmost = false; 868280304Sjkim __first = ++__i; 869280304Sjkim } 870280304Sjkim} 871280304Sjkim 872280304Sjkimtemplate <typename _Number> 87355714Skrisinline _LIBCPP_HIDE_FROM_ABI _Number __log2i(_Number __n) { 874280304Sjkim if (__n == 0) 875280304Sjkim return 0; 876280304Sjkim if (sizeof(__n) <= sizeof(unsigned)) 877280304Sjkim return sizeof(unsigned) * CHAR_BIT - 1 - __libcpp_clz(static_cast<unsigned>(__n)); 878280304Sjkim if (sizeof(__n) <= sizeof(unsigned long)) 879280304Sjkim return sizeof(unsigned long) * CHAR_BIT - 1 - __libcpp_clz(static_cast<unsigned long>(__n)); 880280304Sjkim if (sizeof(__n) <= sizeof(unsigned long long)) 881280304Sjkim return sizeof(unsigned long long) * CHAR_BIT - 1 - __libcpp_clz(static_cast<unsigned long long>(__n)); 882280304Sjkim 883280304Sjkim _Number __log2 = 0; 884280304Sjkim while (__n > 1) { 885280304Sjkim __log2++; 886280304Sjkim __n >>= 1; 887280304Sjkim } 888280304Sjkim return __log2; 889280304Sjkim} 890280304Sjkim 891280304Sjkimtemplate <class _Comp, class _RandomAccessIterator> 892280304Sjkimvoid __sort(_RandomAccessIterator, _RandomAccessIterator, _Comp); 893280304Sjkim 894280304Sjkimextern template _LIBCPP_EXPORTED_FROM_ABI void __sort<__less<char>&, char*>(char*, char*, __less<char>&); 895280304Sjkim#ifndef _LIBCPP_HAS_NO_WIDE_CHARACTERS 896280304Sjkimextern template _LIBCPP_EXPORTED_FROM_ABI void __sort<__less<wchar_t>&, wchar_t*>(wchar_t*, wchar_t*, __less<wchar_t>&); 897280304Sjkim#endif 89855714Skrisextern template _LIBCPP_EXPORTED_FROM_ABI void 89955714Skris__sort<__less<signed char>&, signed char*>(signed char*, signed char*, __less<signed char>&); 900280304Sjkimextern template _LIBCPP_EXPORTED_FROM_ABI void 901280304Sjkim__sort<__less<unsigned char>&, unsigned char*>(unsigned char*, unsigned char*, __less<unsigned char>&); 90255714Skrisextern template _LIBCPP_EXPORTED_FROM_ABI void __sort<__less<short>&, short*>(short*, short*, __less<short>&); 903280304Sjkimextern template _LIBCPP_EXPORTED_FROM_ABI void 904280304Sjkim__sort<__less<unsigned short>&, unsigned short*>(unsigned short*, unsigned short*, __less<unsigned short>&); 905280304Sjkimextern template _LIBCPP_EXPORTED_FROM_ABI void __sort<__less<int>&, int*>(int*, int*, __less<int>&); 906280304Sjkimextern template _LIBCPP_EXPORTED_FROM_ABI void 907280304Sjkim__sort<__less<unsigned>&, unsigned*>(unsigned*, unsigned*, __less<unsigned>&); 908280304Sjkimextern template _LIBCPP_EXPORTED_FROM_ABI void __sort<__less<long>&, long*>(long*, long*, __less<long>&); 909280304Sjkimextern template _LIBCPP_EXPORTED_FROM_ABI void 910280304Sjkim__sort<__less<unsigned long>&, unsigned long*>(unsigned long*, unsigned long*, __less<unsigned long>&); 911280304Sjkimextern template _LIBCPP_EXPORTED_FROM_ABI void 91255714Skris__sort<__less<long long>&, long long*>(long long*, long long*, __less<long long>&); 913280304Sjkimextern template _LIBCPP_EXPORTED_FROM_ABI void __sort<__less<unsigned long long>&, unsigned long long*>( 914280304Sjkim unsigned long long*, unsigned long long*, __less<unsigned long long>&); 915280304Sjkimextern template _LIBCPP_EXPORTED_FROM_ABI void __sort<__less<float>&, float*>(float*, float*, __less<float>&); 916280304Sjkimextern template _LIBCPP_EXPORTED_FROM_ABI void __sort<__less<double>&, double*>(double*, double*, __less<double>&); 917280304Sjkimextern template _LIBCPP_EXPORTED_FROM_ABI void 918280304Sjkim__sort<__less<long double>&, long double*>(long double*, long double*, __less<long double>&); 91955714Skris 92055714Skristemplate <class _AlgPolicy, class _RandomAccessIterator, class _Comp> 921280304Sjkim_LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20 void 922280304Sjkim__sort_dispatch(_RandomAccessIterator __first, _RandomAccessIterator __last, _Comp& __comp) { 92355714Skris typedef typename iterator_traits<_RandomAccessIterator>::difference_type difference_type; 924280304Sjkim difference_type __depth_limit = 2 * std::__log2i(__last - __first); 925280304Sjkim 926280304Sjkim // Only use bitset partitioning for arithmetic types. We should also check 92755714Skris // that the default comparator is in use so that we are sure that there are no 928280304Sjkim // branches in the comparator. 929280304Sjkim std::__introsort<_AlgPolicy, 930280304Sjkim _Comp&, 931280304Sjkim _RandomAccessIterator, 932280304Sjkim __use_branchless_sort<_Comp, _RandomAccessIterator>::value>(__first, __last, __comp, __depth_limit); 933280304Sjkim} 934280304Sjkim 93555714Skristemplate <class _Type, class... _Options> 936280304Sjkimusing __is_any_of = _Or<is_same<_Type, _Options>...>; 937280304Sjkim 938280304Sjkimtemplate <class _Type> 939280304Sjkimusing __sort_is_specialized_in_library = __is_any_of< 94055714Skris _Type, 941280304Sjkim char, 942280304Sjkim#ifndef _LIBCPP_HAS_NO_WIDE_CHARACTERS 943280304Sjkim wchar_t, 94455714Skris#endif 94555714Skris signed char, 94655714Skris unsigned char, 947280304Sjkim short, 948280304Sjkim unsigned short, 949280304Sjkim int, 950280304Sjkim unsigned int, 951280304Sjkim long, 952280304Sjkim unsigned long, 953280304Sjkim long long, 954280304Sjkim unsigned long long, 95555714Skris float, 956280304Sjkim double, 957280304Sjkim long double>; 958280304Sjkim 959280304Sjkimtemplate <class _AlgPolicy, class _Type, __enable_if_t<__sort_is_specialized_in_library<_Type>::value, int> = 0> 960280304Sjkim_LIBCPP_HIDE_FROM_ABI void __sort_dispatch(_Type* __first, _Type* __last, __less<>&) { 961306196Sjkim __less<_Type> __comp; 962280304Sjkim std::__sort<__less<_Type>&, _Type*>(__first, __last, __comp); 963280304Sjkim} 96455714Skris 965280304Sjkimtemplate <class _AlgPolicy, class _Type, __enable_if_t<__sort_is_specialized_in_library<_Type>::value, int> = 0> 966280304Sjkim_LIBCPP_HIDE_FROM_ABI void __sort_dispatch(_Type* __first, _Type* __last, less<_Type>&) { 967280304Sjkim __less<_Type> __comp; 968280304Sjkim std::__sort<__less<_Type>&, _Type*>(__first, __last, __comp); 96955714Skris} 970280304Sjkim 971280304Sjkim#if _LIBCPP_STD_VER >= 14 972280304Sjkimtemplate <class _AlgPolicy, class _Type, __enable_if_t<__sort_is_specialized_in_library<_Type>::value, int> = 0> 973280304Sjkim_LIBCPP_HIDE_FROM_ABI void __sort_dispatch(_Type* __first, _Type* __last, less<>&) { 974280304Sjkim __less<_Type> __comp; 975280304Sjkim std::__sort<__less<_Type>&, _Type*>(__first, __last, __comp); 97655714Skris} 977280304Sjkim#endif 978280304Sjkim 979280304Sjkim#if _LIBCPP_STD_VER >= 20 98055714Skristemplate <class _AlgPolicy, class _Type, __enable_if_t<__sort_is_specialized_in_library<_Type>::value, int> = 0> 981280304Sjkim_LIBCPP_HIDE_FROM_ABI void __sort_dispatch(_Type* __first, _Type* __last, ranges::less&) { 982280304Sjkim __less<_Type> __comp; 983280304Sjkim std::__sort<__less<_Type>&, _Type*>(__first, __last, __comp); 984280304Sjkim} 985280304Sjkim#endif 986280304Sjkim 987280304Sjkimtemplate <class _AlgPolicy, class _RandomAccessIterator, class _Comp> 988280304Sjkiminline _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20 void 989280304Sjkim__sort_impl(_RandomAccessIterator __first, _RandomAccessIterator __last, _Comp& __comp) { 990280304Sjkim std::__debug_randomize_range<_AlgPolicy>(__first, __last); 991280304Sjkim 992280304Sjkim if (__libcpp_is_constant_evaluated()) { 993280304Sjkim std::__partial_sort<_AlgPolicy>( 99455714Skris std::__unwrap_iter(__first), std::__unwrap_iter(__last), std::__unwrap_iter(__last), __comp); 995280304Sjkim } else { 996280304Sjkim std::__sort_dispatch<_AlgPolicy>(std::__unwrap_iter(__first), std::__unwrap_iter(__last), __comp); 997280304Sjkim } 998280304Sjkim std::__check_strict_weak_ordering_sorted(std::__unwrap_iter(__first), std::__unwrap_iter(__last), __comp); 999280304Sjkim} 1000280304Sjkim 1001280304Sjkimtemplate <class _RandomAccessIterator, class _Comp> 1002280304Sjkiminline _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20 void 1003280304Sjkimsort(_RandomAccessIterator __first, _RandomAccessIterator __last, _Comp __comp) { 1004280304Sjkim std::__sort_impl<_ClassicAlgPolicy>(std::move(__first), std::move(__last), __comp); 1005280304Sjkim} 100689840Skris 1007280304Sjkimtemplate <class _RandomAccessIterator> 1008280304Sjkiminline _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20 void 1009280304Sjkimsort(_RandomAccessIterator __first, _RandomAccessIterator __last) { 1010280304Sjkim std::sort(__first, __last, __less<>()); 1011280304Sjkim} 1012110007Smarkm 1013280304Sjkim_LIBCPP_END_NAMESPACE_STD 1014280304Sjkim 1015280304Sjkim_LIBCPP_POP_MACROS 1016280304Sjkim 101789840Skris#endif // _LIBCPP___ALGORITHM_SORT_H 1018280304Sjkim