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 <__config> 13 #include <__algorithm/comp.h> 14 #include <__algorithm/comp_ref_type.h> 15 #include <__algorithm/min_element.h> 16 #include <__algorithm/partial_sort.h> 17 #include <__algorithm/unwrap_iter.h> 18 #include <__utility/swap.h> 19 #include <memory> 20 21 #if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER) 22 #pragma GCC system_header 23 #endif 24 25 _LIBCPP_PUSH_MACROS 26 #include <__undef_macros> 27 28 _LIBCPP_BEGIN_NAMESPACE_STD 29 30 // stable, 2-3 compares, 0-2 swaps 31 32 template <class _Compare, class _ForwardIterator> 33 _LIBCPP_CONSTEXPR_AFTER_CXX11 unsigned 34 __sort3(_ForwardIterator __x, _ForwardIterator __y, _ForwardIterator __z, _Compare __c) 35 { 36 unsigned __r = 0; 37 if (!__c(*__y, *__x)) // if x <= y 38 { 39 if (!__c(*__z, *__y)) // if y <= z 40 return __r; // x <= y && y <= z 41 // x <= y && y > z 42 swap(*__y, *__z); // x <= z && y < z 43 __r = 1; 44 if (__c(*__y, *__x)) // if x > y 45 { 46 swap(*__x, *__y); // x < y && y <= z 47 __r = 2; 48 } 49 return __r; // x <= y && y < z 50 } 51 if (__c(*__z, *__y)) // x > y, if y > z 52 { 53 swap(*__x, *__z); // x < y && y < z 54 __r = 1; 55 return __r; 56 } 57 swap(*__x, *__y); // x > y && y <= z 58 __r = 1; // x < y && x <= z 59 if (__c(*__z, *__y)) // if y > z 60 { 61 swap(*__y, *__z); // x <= y && y < z 62 __r = 2; 63 } 64 return __r; 65 } // x <= y && y <= z 66 67 // stable, 3-6 compares, 0-5 swaps 68 69 template <class _Compare, class _ForwardIterator> 70 unsigned 71 __sort4(_ForwardIterator __x1, _ForwardIterator __x2, _ForwardIterator __x3, 72 _ForwardIterator __x4, _Compare __c) 73 { 74 unsigned __r = _VSTD::__sort3<_Compare>(__x1, __x2, __x3, __c); 75 if (__c(*__x4, *__x3)) 76 { 77 swap(*__x3, *__x4); 78 ++__r; 79 if (__c(*__x3, *__x2)) 80 { 81 swap(*__x2, *__x3); 82 ++__r; 83 if (__c(*__x2, *__x1)) 84 { 85 swap(*__x1, *__x2); 86 ++__r; 87 } 88 } 89 } 90 return __r; 91 } 92 93 // stable, 4-10 compares, 0-9 swaps 94 95 template <class _Compare, class _ForwardIterator> 96 _LIBCPP_HIDDEN 97 unsigned 98 __sort5(_ForwardIterator __x1, _ForwardIterator __x2, _ForwardIterator __x3, 99 _ForwardIterator __x4, _ForwardIterator __x5, _Compare __c) 100 { 101 unsigned __r = _VSTD::__sort4<_Compare>(__x1, __x2, __x3, __x4, __c); 102 if (__c(*__x5, *__x4)) 103 { 104 swap(*__x4, *__x5); 105 ++__r; 106 if (__c(*__x4, *__x3)) 107 { 108 swap(*__x3, *__x4); 109 ++__r; 110 if (__c(*__x3, *__x2)) 111 { 112 swap(*__x2, *__x3); 113 ++__r; 114 if (__c(*__x2, *__x1)) 115 { 116 swap(*__x1, *__x2); 117 ++__r; 118 } 119 } 120 } 121 } 122 return __r; 123 } 124 125 // Assumes size > 0 126 template <class _Compare, class _BidirectionalIterator> 127 _LIBCPP_CONSTEXPR_AFTER_CXX11 void 128 __selection_sort(_BidirectionalIterator __first, _BidirectionalIterator __last, _Compare __comp) 129 { 130 _BidirectionalIterator __lm1 = __last; 131 for (--__lm1; __first != __lm1; ++__first) 132 { 133 _BidirectionalIterator __i = _VSTD::min_element<_BidirectionalIterator, _Compare&>(__first, __last, __comp); 134 if (__i != __first) 135 swap(*__first, *__i); 136 } 137 } 138 139 template <class _Compare, class _BidirectionalIterator> 140 void 141 __insertion_sort(_BidirectionalIterator __first, _BidirectionalIterator __last, _Compare __comp) 142 { 143 typedef typename iterator_traits<_BidirectionalIterator>::value_type value_type; 144 if (__first != __last) 145 { 146 _BidirectionalIterator __i = __first; 147 for (++__i; __i != __last; ++__i) 148 { 149 _BidirectionalIterator __j = __i; 150 value_type __t(_VSTD::move(*__j)); 151 for (_BidirectionalIterator __k = __i; __k != __first && __comp(__t, *--__k); --__j) 152 *__j = _VSTD::move(*__k); 153 *__j = _VSTD::move(__t); 154 } 155 } 156 } 157 158 template <class _Compare, class _RandomAccessIterator> 159 void 160 __insertion_sort_3(_RandomAccessIterator __first, _RandomAccessIterator __last, _Compare __comp) 161 { 162 typedef typename iterator_traits<_RandomAccessIterator>::value_type value_type; 163 _RandomAccessIterator __j = __first+2; 164 _VSTD::__sort3<_Compare>(__first, __first+1, __j, __comp); 165 for (_RandomAccessIterator __i = __j+1; __i != __last; ++__i) 166 { 167 if (__comp(*__i, *__j)) 168 { 169 value_type __t(_VSTD::move(*__i)); 170 _RandomAccessIterator __k = __j; 171 __j = __i; 172 do 173 { 174 *__j = _VSTD::move(*__k); 175 __j = __k; 176 } while (__j != __first && __comp(__t, *--__k)); 177 *__j = _VSTD::move(__t); 178 } 179 __j = __i; 180 } 181 } 182 183 template <class _Compare, class _RandomAccessIterator> 184 bool 185 __insertion_sort_incomplete(_RandomAccessIterator __first, _RandomAccessIterator __last, _Compare __comp) 186 { 187 switch (__last - __first) 188 { 189 case 0: 190 case 1: 191 return true; 192 case 2: 193 if (__comp(*--__last, *__first)) 194 swap(*__first, *__last); 195 return true; 196 case 3: 197 _VSTD::__sort3<_Compare>(__first, __first+1, --__last, __comp); 198 return true; 199 case 4: 200 _VSTD::__sort4<_Compare>(__first, __first+1, __first+2, --__last, __comp); 201 return true; 202 case 5: 203 _VSTD::__sort5<_Compare>(__first, __first+1, __first+2, __first+3, --__last, __comp); 204 return true; 205 } 206 typedef typename iterator_traits<_RandomAccessIterator>::value_type value_type; 207 _RandomAccessIterator __j = __first+2; 208 _VSTD::__sort3<_Compare>(__first, __first+1, __j, __comp); 209 const unsigned __limit = 8; 210 unsigned __count = 0; 211 for (_RandomAccessIterator __i = __j+1; __i != __last; ++__i) 212 { 213 if (__comp(*__i, *__j)) 214 { 215 value_type __t(_VSTD::move(*__i)); 216 _RandomAccessIterator __k = __j; 217 __j = __i; 218 do 219 { 220 *__j = _VSTD::move(*__k); 221 __j = __k; 222 } while (__j != __first && __comp(__t, *--__k)); 223 *__j = _VSTD::move(__t); 224 if (++__count == __limit) 225 return ++__i == __last; 226 } 227 __j = __i; 228 } 229 return true; 230 } 231 232 template <class _Compare, class _BidirectionalIterator> 233 void 234 __insertion_sort_move(_BidirectionalIterator __first1, _BidirectionalIterator __last1, 235 typename iterator_traits<_BidirectionalIterator>::value_type* __first2, _Compare __comp) 236 { 237 typedef typename iterator_traits<_BidirectionalIterator>::value_type value_type; 238 if (__first1 != __last1) 239 { 240 __destruct_n __d(0); 241 unique_ptr<value_type, __destruct_n&> __h(__first2, __d); 242 value_type* __last2 = __first2; 243 ::new ((void*)__last2) value_type(_VSTD::move(*__first1)); 244 __d.template __incr<value_type>(); 245 for (++__last2; ++__first1 != __last1; ++__last2) 246 { 247 value_type* __j2 = __last2; 248 value_type* __i2 = __j2; 249 if (__comp(*__first1, *--__i2)) 250 { 251 ::new ((void*)__j2) value_type(_VSTD::move(*__i2)); 252 __d.template __incr<value_type>(); 253 for (--__j2; __i2 != __first2 && __comp(*__first1, *--__i2); --__j2) 254 *__j2 = _VSTD::move(*__i2); 255 *__j2 = _VSTD::move(*__first1); 256 } 257 else 258 { 259 ::new ((void*)__j2) value_type(_VSTD::move(*__first1)); 260 __d.template __incr<value_type>(); 261 } 262 } 263 __h.release(); 264 } 265 } 266 267 template <class _Compare, class _RandomAccessIterator> 268 void 269 __sort(_RandomAccessIterator __first, _RandomAccessIterator __last, _Compare __comp) 270 { 271 typedef typename iterator_traits<_RandomAccessIterator>::difference_type difference_type; 272 typedef typename iterator_traits<_RandomAccessIterator>::value_type value_type; 273 const difference_type __limit = is_trivially_copy_constructible<value_type>::value && 274 is_trivially_copy_assignable<value_type>::value ? 30 : 6; 275 while (true) 276 { 277 __restart: 278 difference_type __len = __last - __first; 279 switch (__len) 280 { 281 case 0: 282 case 1: 283 return; 284 case 2: 285 if (__comp(*--__last, *__first)) 286 swap(*__first, *__last); 287 return; 288 case 3: 289 _VSTD::__sort3<_Compare>(__first, __first+1, --__last, __comp); 290 return; 291 case 4: 292 _VSTD::__sort4<_Compare>(__first, __first+1, __first+2, --__last, __comp); 293 return; 294 case 5: 295 _VSTD::__sort5<_Compare>(__first, __first+1, __first+2, __first+3, --__last, __comp); 296 return; 297 } 298 if (__len <= __limit) 299 { 300 _VSTD::__insertion_sort_3<_Compare>(__first, __last, __comp); 301 return; 302 } 303 // __len > 5 304 _RandomAccessIterator __m = __first; 305 _RandomAccessIterator __lm1 = __last; 306 --__lm1; 307 unsigned __n_swaps; 308 { 309 difference_type __delta; 310 if (__len >= 1000) 311 { 312 __delta = __len/2; 313 __m += __delta; 314 __delta /= 2; 315 __n_swaps = _VSTD::__sort5<_Compare>(__first, __first + __delta, __m, __m+__delta, __lm1, __comp); 316 } 317 else 318 { 319 __delta = __len/2; 320 __m += __delta; 321 __n_swaps = _VSTD::__sort3<_Compare>(__first, __m, __lm1, __comp); 322 } 323 } 324 // *__m is median 325 // partition [__first, __m) < *__m and *__m <= [__m, __last) 326 // (this inhibits tossing elements equivalent to __m around unnecessarily) 327 _RandomAccessIterator __i = __first; 328 _RandomAccessIterator __j = __lm1; 329 // j points beyond range to be tested, *__m is known to be <= *__lm1 330 // The search going up is known to be guarded but the search coming down isn't. 331 // Prime the downward search with a guard. 332 if (!__comp(*__i, *__m)) // if *__first == *__m 333 { 334 // *__first == *__m, *__first doesn't go in first part 335 // manually guard downward moving __j against __i 336 while (true) 337 { 338 if (__i == --__j) 339 { 340 // *__first == *__m, *__m <= all other elements 341 // Parition instead into [__first, __i) == *__first and *__first < [__i, __last) 342 ++__i; // __first + 1 343 __j = __last; 344 if (!__comp(*__first, *--__j)) // we need a guard if *__first == *(__last-1) 345 { 346 while (true) 347 { 348 if (__i == __j) 349 return; // [__first, __last) all equivalent elements 350 if (__comp(*__first, *__i)) 351 { 352 swap(*__i, *__j); 353 ++__n_swaps; 354 ++__i; 355 break; 356 } 357 ++__i; 358 } 359 } 360 // [__first, __i) == *__first and *__first < [__j, __last) and __j == __last - 1 361 if (__i == __j) 362 return; 363 while (true) 364 { 365 while (!__comp(*__first, *__i)) 366 ++__i; 367 while (__comp(*__first, *--__j)) 368 ; 369 if (__i >= __j) 370 break; 371 swap(*__i, *__j); 372 ++__n_swaps; 373 ++__i; 374 } 375 // [__first, __i) == *__first and *__first < [__i, __last) 376 // The first part is sorted, sort the second part 377 // _VSTD::__sort<_Compare>(__i, __last, __comp); 378 __first = __i; 379 goto __restart; 380 } 381 if (__comp(*__j, *__m)) 382 { 383 swap(*__i, *__j); 384 ++__n_swaps; 385 break; // found guard for downward moving __j, now use unguarded partition 386 } 387 } 388 } 389 // It is known that *__i < *__m 390 ++__i; 391 // j points beyond range to be tested, *__m is known to be <= *__lm1 392 // if not yet partitioned... 393 if (__i < __j) 394 { 395 // known that *(__i - 1) < *__m 396 // known that __i <= __m 397 while (true) 398 { 399 // __m still guards upward moving __i 400 while (__comp(*__i, *__m)) 401 ++__i; 402 // It is now known that a guard exists for downward moving __j 403 while (!__comp(*--__j, *__m)) 404 ; 405 if (__i > __j) 406 break; 407 swap(*__i, *__j); 408 ++__n_swaps; 409 // It is known that __m != __j 410 // If __m just moved, follow it 411 if (__m == __i) 412 __m = __j; 413 ++__i; 414 } 415 } 416 // [__first, __i) < *__m and *__m <= [__i, __last) 417 if (__i != __m && __comp(*__m, *__i)) 418 { 419 swap(*__i, *__m); 420 ++__n_swaps; 421 } 422 // [__first, __i) < *__i and *__i <= [__i+1, __last) 423 // If we were given a perfect partition, see if insertion sort is quick... 424 if (__n_swaps == 0) 425 { 426 bool __fs = _VSTD::__insertion_sort_incomplete<_Compare>(__first, __i, __comp); 427 if (_VSTD::__insertion_sort_incomplete<_Compare>(__i+1, __last, __comp)) 428 { 429 if (__fs) 430 return; 431 __last = __i; 432 continue; 433 } 434 else 435 { 436 if (__fs) 437 { 438 __first = ++__i; 439 continue; 440 } 441 } 442 } 443 // sort smaller range with recursive call and larger with tail recursion elimination 444 if (__i - __first < __last - __i) 445 { 446 _VSTD::__sort<_Compare>(__first, __i, __comp); 447 // _VSTD::__sort<_Compare>(__i+1, __last, __comp); 448 __first = ++__i; 449 } 450 else 451 { 452 _VSTD::__sort<_Compare>(__i+1, __last, __comp); 453 // _VSTD::__sort<_Compare>(__first, __i, __comp); 454 __last = __i; 455 } 456 } 457 } 458 459 template <class _Compare, class _Tp> 460 inline _LIBCPP_INLINE_VISIBILITY 461 void 462 __sort(_Tp** __first, _Tp** __last, __less<_Tp*>&) 463 { 464 __less<uintptr_t> __comp; 465 _VSTD::__sort<__less<uintptr_t>&, uintptr_t*>((uintptr_t*)__first, (uintptr_t*)__last, __comp); 466 } 467 468 _LIBCPP_EXTERN_TEMPLATE(_LIBCPP_FUNC_VIS void __sort<__less<char>&, char*>(char*, char*, __less<char>&)) 469 _LIBCPP_EXTERN_TEMPLATE(_LIBCPP_FUNC_VIS void __sort<__less<wchar_t>&, wchar_t*>(wchar_t*, wchar_t*, __less<wchar_t>&)) 470 _LIBCPP_EXTERN_TEMPLATE(_LIBCPP_FUNC_VIS void __sort<__less<signed char>&, signed char*>(signed char*, signed char*, __less<signed char>&)) 471 _LIBCPP_EXTERN_TEMPLATE(_LIBCPP_FUNC_VIS void __sort<__less<unsigned char>&, unsigned char*>(unsigned char*, unsigned char*, __less<unsigned char>&)) 472 _LIBCPP_EXTERN_TEMPLATE(_LIBCPP_FUNC_VIS void __sort<__less<short>&, short*>(short*, short*, __less<short>&)) 473 _LIBCPP_EXTERN_TEMPLATE(_LIBCPP_FUNC_VIS void __sort<__less<unsigned short>&, unsigned short*>(unsigned short*, unsigned short*, __less<unsigned short>&)) 474 _LIBCPP_EXTERN_TEMPLATE(_LIBCPP_FUNC_VIS void __sort<__less<int>&, int*>(int*, int*, __less<int>&)) 475 _LIBCPP_EXTERN_TEMPLATE(_LIBCPP_FUNC_VIS void __sort<__less<unsigned>&, unsigned*>(unsigned*, unsigned*, __less<unsigned>&)) 476 _LIBCPP_EXTERN_TEMPLATE(_LIBCPP_FUNC_VIS void __sort<__less<long>&, long*>(long*, long*, __less<long>&)) 477 _LIBCPP_EXTERN_TEMPLATE(_LIBCPP_FUNC_VIS void __sort<__less<unsigned long>&, unsigned long*>(unsigned long*, unsigned long*, __less<unsigned long>&)) 478 _LIBCPP_EXTERN_TEMPLATE(_LIBCPP_FUNC_VIS void __sort<__less<long long>&, long long*>(long long*, long long*, __less<long long>&)) 479 _LIBCPP_EXTERN_TEMPLATE(_LIBCPP_FUNC_VIS void __sort<__less<unsigned long long>&, unsigned long long*>(unsigned long long*, unsigned long long*, __less<unsigned long long>&)) 480 _LIBCPP_EXTERN_TEMPLATE(_LIBCPP_FUNC_VIS void __sort<__less<float>&, float*>(float*, float*, __less<float>&)) 481 _LIBCPP_EXTERN_TEMPLATE(_LIBCPP_FUNC_VIS void __sort<__less<double>&, double*>(double*, double*, __less<double>&)) 482 _LIBCPP_EXTERN_TEMPLATE(_LIBCPP_FUNC_VIS void __sort<__less<long double>&, long double*>(long double*, long double*, __less<long double>&)) 483 484 _LIBCPP_EXTERN_TEMPLATE(_LIBCPP_FUNC_VIS bool __insertion_sort_incomplete<__less<char>&, char*>(char*, char*, __less<char>&)) 485 _LIBCPP_EXTERN_TEMPLATE(_LIBCPP_FUNC_VIS bool __insertion_sort_incomplete<__less<wchar_t>&, wchar_t*>(wchar_t*, wchar_t*, __less<wchar_t>&)) 486 _LIBCPP_EXTERN_TEMPLATE(_LIBCPP_FUNC_VIS bool __insertion_sort_incomplete<__less<signed char>&, signed char*>(signed char*, signed char*, __less<signed char>&)) 487 _LIBCPP_EXTERN_TEMPLATE(_LIBCPP_FUNC_VIS bool __insertion_sort_incomplete<__less<unsigned char>&, unsigned char*>(unsigned char*, unsigned char*, __less<unsigned char>&)) 488 _LIBCPP_EXTERN_TEMPLATE(_LIBCPP_FUNC_VIS bool __insertion_sort_incomplete<__less<short>&, short*>(short*, short*, __less<short>&)) 489 _LIBCPP_EXTERN_TEMPLATE(_LIBCPP_FUNC_VIS bool __insertion_sort_incomplete<__less<unsigned short>&, unsigned short*>(unsigned short*, unsigned short*, __less<unsigned short>&)) 490 _LIBCPP_EXTERN_TEMPLATE(_LIBCPP_FUNC_VIS bool __insertion_sort_incomplete<__less<int>&, int*>(int*, int*, __less<int>&)) 491 _LIBCPP_EXTERN_TEMPLATE(_LIBCPP_FUNC_VIS bool __insertion_sort_incomplete<__less<unsigned>&, unsigned*>(unsigned*, unsigned*, __less<unsigned>&)) 492 _LIBCPP_EXTERN_TEMPLATE(_LIBCPP_FUNC_VIS bool __insertion_sort_incomplete<__less<long>&, long*>(long*, long*, __less<long>&)) 493 _LIBCPP_EXTERN_TEMPLATE(_LIBCPP_FUNC_VIS bool __insertion_sort_incomplete<__less<unsigned long>&, unsigned long*>(unsigned long*, unsigned long*, __less<unsigned long>&)) 494 _LIBCPP_EXTERN_TEMPLATE(_LIBCPP_FUNC_VIS bool __insertion_sort_incomplete<__less<long long>&, long long*>(long long*, long long*, __less<long long>&)) 495 _LIBCPP_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>&)) 496 _LIBCPP_EXTERN_TEMPLATE(_LIBCPP_FUNC_VIS bool __insertion_sort_incomplete<__less<float>&, float*>(float*, float*, __less<float>&)) 497 _LIBCPP_EXTERN_TEMPLATE(_LIBCPP_FUNC_VIS bool __insertion_sort_incomplete<__less<double>&, double*>(double*, double*, __less<double>&)) 498 _LIBCPP_EXTERN_TEMPLATE(_LIBCPP_FUNC_VIS bool __insertion_sort_incomplete<__less<long double>&, long double*>(long double*, long double*, __less<long double>&)) 499 500 _LIBCPP_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>&)) 501 502 template <class _RandomAccessIterator, class _Compare> 503 inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17 504 void 505 sort(_RandomAccessIterator __first, _RandomAccessIterator __last, _Compare __comp) 506 { 507 typedef typename __comp_ref_type<_Compare>::type _Comp_ref; 508 if (__libcpp_is_constant_evaluated()) { 509 _VSTD::__partial_sort<_Comp_ref>(__first, __last, __last, _Comp_ref(__comp)); 510 } else { 511 _VSTD::__sort<_Comp_ref>(_VSTD::__unwrap_iter(__first), _VSTD::__unwrap_iter(__last), _Comp_ref(__comp)); 512 } 513 } 514 515 template <class _RandomAccessIterator> 516 inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17 517 void 518 sort(_RandomAccessIterator __first, _RandomAccessIterator __last) 519 { 520 _VSTD::sort(__first, __last, __less<typename iterator_traits<_RandomAccessIterator>::value_type>()); 521 } 522 523 _LIBCPP_END_NAMESPACE_STD 524 525 _LIBCPP_POP_MACROS 526 527 #endif // _LIBCPP___ALGORITHM_SORT_H 528