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