vendor/llvm-project/llvmorg-14-init-10186-gff7f2cfa959b

1 files changed, 61 insertions, 35 deletions

diff --git a/libcxx/include/__algorithm/sort.h b/libcxx/include/__algorithm/sort.h
index 39ec21302d20..bc127689a674 100644
--- a/libcxx/include/__algorithm/sort.h
+++ b/libcxx/include/__algorithm/sort.h
@@ -17,15 +17,15 @@
 #include <__algorithm/unwrap_iter.h>
 #include <__utility/swap.h>
 #include <memory>
-#include <type_traits> // swap
+
+#if defined(_LIBCPP_DEBUG_RANDOMIZE_UNSPECIFIED_STABILITY)
+#  include <__algorithm/shuffle.h>
+#endif
 
 #if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER)
 #pragma GCC system_header
 #endif
 
-_LIBCPP_PUSH_MACROS
-#include <__undef_macros>
-
 _LIBCPP_BEGIN_NAMESPACE_STD
 
 // stable, 2-3 compares, 0-2 swaps
@@ -131,9 +131,7 @@ __selection_sort(_BidirectionalIterator __first, _BidirectionalIterator __last,
     _BidirectionalIterator __lm1 = __last;
     for (--__lm1; __first != __lm1; ++__first)
     {
-        _BidirectionalIterator __i = _VSTD::min_element<_BidirectionalIterator,
-                                                        typename add_lvalue_reference<_Compare>::type>
-                                                       (__first, __last, __comp);
+        _BidirectionalIterator __i = _VSTD::min_element(__first, __last, __comp);
         if (__i != __first)
             swap(*__first, *__i);
     }
@@ -162,10 +160,11 @@ template <class _Compare, class _RandomAccessIterator>
 void
 __insertion_sort_3(_RandomAccessIterator __first, _RandomAccessIterator __last, _Compare __comp)
 {
+    typedef typename iterator_traits<_RandomAccessIterator>::difference_type difference_type;
     typedef typename iterator_traits<_RandomAccessIterator>::value_type value_type;
-    _RandomAccessIterator __j = __first+2;
-    _VSTD::__sort3<_Compare>(__first, __first+1, __j, __comp);
-    for (_RandomAccessIterator __i = __j+1; __i != __last; ++__i)
+    _RandomAccessIterator __j = __first+difference_type(2);
+    _VSTD::__sort3<_Compare>(__first, __first+difference_type(1), __j, __comp);
+    for (_RandomAccessIterator __i = __j+difference_type(1); __i != __last; ++__i)
     {
         if (__comp(*__i, *__j))
         {
@@ -187,6 +186,7 @@ template <class _Compare, class _RandomAccessIterator>
 bool
 __insertion_sort_incomplete(_RandomAccessIterator __first, _RandomAccessIterator __last, _Compare __comp)
 {
+    typedef typename iterator_traits<_RandomAccessIterator>::difference_type difference_type;
     switch (__last - __first)
     {
     case 0:
@@ -197,21 +197,21 @@ __insertion_sort_incomplete(_RandomAccessIterator __first, _RandomAccessIterator
             swap(*__first, *__last);
         return true;
     case 3:
-        _VSTD::__sort3<_Compare>(__first, __first+1, --__last, __comp);
+        _VSTD::__sort3<_Compare>(__first, __first+difference_type(1), --__last, __comp);
         return true;
     case 4:
-        _VSTD::__sort4<_Compare>(__first, __first+1, __first+2, --__last, __comp);
+        _VSTD::__sort4<_Compare>(__first, __first+difference_type(1), __first+difference_type(2), --__last, __comp);
         return true;
     case 5:
-        _VSTD::__sort5<_Compare>(__first, __first+1, __first+2, __first+3, --__last, __comp);
+        _VSTD::__sort5<_Compare>(__first, __first+difference_type(1), __first+difference_type(2), __first+difference_type(3), --__last, __comp);
         return true;
     }
     typedef typename iterator_traits<_RandomAccessIterator>::value_type value_type;
-    _RandomAccessIterator __j = __first+2;
-    _VSTD::__sort3<_Compare>(__first, __first+1, __j, __comp);
+    _RandomAccessIterator __j = __first+difference_type(2);
+    _VSTD::__sort3<_Compare>(__first, __first+difference_type(1), __j, __comp);
     const unsigned __limit = 8;
     unsigned __count = 0;
-    for (_RandomAccessIterator __i = __j+1; __i != __last; ++__i)
+    for (_RandomAccessIterator __i = __j+difference_type(1); __i != __last; ++__i)
     {
         if (__comp(*__i, *__j))
         {
@@ -269,7 +269,8 @@ __insertion_sort_move(_BidirectionalIterator __first1, _BidirectionalIterator __
 
 template <class _Compare, class _RandomAccessIterator>
 void
-__sort(_RandomAccessIterator __first, _RandomAccessIterator __last, _Compare __comp)
+__introsort(_RandomAccessIterator __first, _RandomAccessIterator __last, _Compare __comp,
+            typename iterator_traits<_RandomAccessIterator>::difference_type __depth)
 {
     typedef typename iterator_traits<_RandomAccessIterator>::difference_type difference_type;
     typedef typename iterator_traits<_RandomAccessIterator>::value_type value_type;
@@ -289,13 +290,13 @@ __sort(_RandomAccessIterator __first, _RandomAccessIterator __last, _Compare __c
                 swap(*__first, *__last);
             return;
         case 3:
-            _VSTD::__sort3<_Compare>(__first, __first+1, --__last, __comp);
+            _VSTD::__sort3<_Compare>(__first, __first+difference_type(1), --__last, __comp);
             return;
         case 4:
-            _VSTD::__sort4<_Compare>(__first, __first+1, __first+2, --__last, __comp);
+            _VSTD::__sort4<_Compare>(__first, __first+difference_type(1), __first+difference_type(2), --__last, __comp);
             return;
         case 5:
-            _VSTD::__sort5<_Compare>(__first, __first+1, __first+2, __first+3, --__last, __comp);
+            _VSTD::__sort5<_Compare>(__first, __first+difference_type(1), __first+difference_type(2), __first+difference_type(3), --__last, __comp);
             return;
         }
         if (__len <= __limit)
@@ -304,6 +305,13 @@ __sort(_RandomAccessIterator __first, _RandomAccessIterator __last, _Compare __c
             return;
         }
         // __len > 5
+        if (__depth == 0)
+        {
+          // Fallback to heap sort as Introsort suggests.
+          _VSTD::__partial_sort<_Compare>(__first, __last, __last, __comp);
+          return;
+        }
+        --__depth;
         _RandomAccessIterator __m = __first;
         _RandomAccessIterator __lm1 = __last;
         --__lm1;
@@ -427,7 +435,7 @@ __sort(_RandomAccessIterator __first, _RandomAccessIterator __last, _Compare __c
         if (__n_swaps == 0)
         {
             bool __fs = _VSTD::__insertion_sort_incomplete<_Compare>(__first, __i, __comp);
-            if (_VSTD::__insertion_sort_incomplete<_Compare>(__i+1, __last, __comp))
+            if (_VSTD::__insertion_sort_incomplete<_Compare>(__i+difference_type(1), __last, __comp))
             {
                 if (__fs)
                     return;
@@ -446,19 +454,34 @@ __sort(_RandomAccessIterator __first, _RandomAccessIterator __last, _Compare __c
         // sort smaller range with recursive call and larger with tail recursion elimination
         if (__i - __first < __last - __i)
         {
-            _VSTD::__sort<_Compare>(__first, __i, __comp);
-            // _VSTD::__sort<_Compare>(__i+1, __last, __comp);
-            __first = ++__i;
+          _VSTD::__introsort<_Compare>(__first, __i, __comp, __depth);
+          __first = ++__i;
         }
         else
         {
-            _VSTD::__sort<_Compare>(__i+1, __last, __comp);
-            // _VSTD::__sort<_Compare>(__first, __i, __comp);
-            __last = __i;
+          _VSTD::__introsort<_Compare>(__i + difference_type(1), __last, __comp, __depth);
+          __last = __i;
         }
     }
 }
 
+template <typename _Number>
+inline _LIBCPP_HIDE_FROM_ABI _Number __log2i(_Number __n) {
+  _Number __log2 = 0;
+  while (__n > 1) {
+    __log2++;
+    __n >>= 1;
+  }
+  return __log2;
+}
+
+template <class _Compare, class _RandomAccessIterator>
+void __sort(_RandomAccessIterator __first, _RandomAccessIterator __last, _Compare __comp) {
+  typedef typename iterator_traits<_RandomAccessIterator>::difference_type difference_type;
+  difference_type __depth_limit = 2 * __log2i(__last - __first);
+  _VSTD::__introsort<_Compare>(__first, __last, __comp, __depth_limit);
+}
+
 template <class _Compare, class _Tp>
 inline _LIBCPP_INLINE_VISIBILITY
 void
@@ -469,7 +492,9 @@ __sort(_Tp** __first, _Tp** __last, __less<_Tp*>&)
 }
 
 _LIBCPP_EXTERN_TEMPLATE(_LIBCPP_FUNC_VIS void __sort<__less<char>&, char*>(char*, char*, __less<char>&))
+#ifndef _LIBCPP_HAS_NO_WIDE_CHARACTERS
 _LIBCPP_EXTERN_TEMPLATE(_LIBCPP_FUNC_VIS void __sort<__less<wchar_t>&, wchar_t*>(wchar_t*, wchar_t*, __less<wchar_t>&))
+#endif
 _LIBCPP_EXTERN_TEMPLATE(_LIBCPP_FUNC_VIS void __sort<__less<signed char>&, signed char*>(signed char*, signed char*, __less<signed char>&))
 _LIBCPP_EXTERN_TEMPLATE(_LIBCPP_FUNC_VIS void __sort<__less<unsigned char>&, unsigned char*>(unsigned char*, unsigned char*, __less<unsigned char>&))
 _LIBCPP_EXTERN_TEMPLATE(_LIBCPP_FUNC_VIS void __sort<__less<short>&, short*>(short*, short*, __less<short>&))
@@ -485,7 +510,9 @@ _LIBCPP_EXTERN_TEMPLATE(_LIBCPP_FUNC_VIS void __sort<__less<double>&, double*>(d
 _LIBCPP_EXTERN_TEMPLATE(_LIBCPP_FUNC_VIS void __sort<__less<long double>&, long double*>(long double*, long double*, __less<long double>&))
 
 _LIBCPP_EXTERN_TEMPLATE(_LIBCPP_FUNC_VIS bool __insertion_sort_incomplete<__less<char>&, char*>(char*, char*, __less<char>&))
+#ifndef _LIBCPP_HAS_NO_WIDE_CHARACTERS
 _LIBCPP_EXTERN_TEMPLATE(_LIBCPP_FUNC_VIS bool __insertion_sort_incomplete<__less<wchar_t>&, wchar_t*>(wchar_t*, wchar_t*, __less<wchar_t>&))
+#endif
 _LIBCPP_EXTERN_TEMPLATE(_LIBCPP_FUNC_VIS bool __insertion_sort_incomplete<__less<signed char>&, signed char*>(signed char*, signed char*, __less<signed char>&))
 _LIBCPP_EXTERN_TEMPLATE(_LIBCPP_FUNC_VIS bool __insertion_sort_incomplete<__less<unsigned char>&, unsigned char*>(unsigned char*, unsigned char*, __less<unsigned char>&))
 _LIBCPP_EXTERN_TEMPLATE(_LIBCPP_FUNC_VIS bool __insertion_sort_incomplete<__less<short>&, short*>(short*, short*, __less<short>&))
@@ -507,12 +534,13 @@ inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17
 void
 sort(_RandomAccessIterator __first, _RandomAccessIterator __last, _Compare __comp)
 {
-    typedef typename __comp_ref_type<_Compare>::type _Comp_ref;
-    if (__libcpp_is_constant_evaluated()) {
-        _VSTD::__partial_sort<_Comp_ref>(__first, __last, __last, _Comp_ref(__comp));
-    } else {
-        _VSTD::__sort<_Comp_ref>(_VSTD::__unwrap_iter(__first), _VSTD::__unwrap_iter(__last), _Comp_ref(__comp));
-    }
+  _LIBCPP_DEBUG_RANDOMIZE_RANGE(__first, __last);
+  typedef typename __comp_ref_type<_Compare>::type _Comp_ref;
+  if (__libcpp_is_constant_evaluated()) {
+    _VSTD::__partial_sort<_Comp_ref>(__first, __last, __last, _Comp_ref(__comp));
+  } else {
+    _VSTD::__sort<_Comp_ref>(_VSTD::__unwrap_iter(__first), _VSTD::__unwrap_iter(__last), _Comp_ref(__comp));
+  }
 }
 
 template <class _RandomAccessIterator>
@@ -525,6 +553,4 @@ sort(_RandomAccessIterator __first, _RandomAccessIterator __last)
 
 _LIBCPP_END_NAMESPACE_STD
 
-_LIBCPP_POP_MACROS
-
 #endif // _LIBCPP___ALGORITHM_SORT_H