Import libs 4 (#758)

1 files changed, 49 insertions, 36 deletions

diff --git a/contrib/libs/cxxsupp/libcxx/include/__algorithm/rotate.h b/contrib/libs/cxxsupp/libcxx/include/__algorithm/rotate.h
index c9ea5bad4c..fcf8444a65 100644
--- a/contrib/libs/cxxsupp/libcxx/include/__algorithm/rotate.h
+++ b/contrib/libs/cxxsupp/libcxx/include/__algorithm/rotate.h
@@ -9,6 +9,7 @@
 #ifndef _LIBCPP___ALGORITHM_ROTATE_H
 #define _LIBCPP___ALGORITHM_ROTATE_H
 
+#include <__algorithm/iterator_operations.h>
 #include <__algorithm/move.h>
 #include <__algorithm/move_backward.h>
 #include <__algorithm/swap_ranges.h>
@@ -26,37 +27,40 @@
 
 _LIBCPP_BEGIN_NAMESPACE_STD
 
-template <class _ForwardIterator>
+template <class _AlgPolicy, class _ForwardIterator>
 _LIBCPP_CONSTEXPR_AFTER_CXX11 _ForwardIterator
 __rotate_left(_ForwardIterator __first, _ForwardIterator __last)
 {
     typedef typename iterator_traits<_ForwardIterator>::value_type value_type;
-    value_type __tmp = _VSTD::move(*__first);
+    value_type __tmp = _IterOps<_AlgPolicy>::__iter_move(__first);
+    // TODO(ranges): pass `_AlgPolicy` to `move`.
     _ForwardIterator __lm1 = _VSTD::move(_VSTD::next(__first), __last, __first);
     *__lm1 = _VSTD::move(__tmp);
     return __lm1;
 }
 
-template <class _BidirectionalIterator>
+template <class _AlgPolicy, class _BidirectionalIterator>
 _LIBCPP_CONSTEXPR_AFTER_CXX11 _BidirectionalIterator
 __rotate_right(_BidirectionalIterator __first, _BidirectionalIterator __last)
 {
     typedef typename iterator_traits<_BidirectionalIterator>::value_type value_type;
+    // TODO(ranges): pass `_AlgPolicy` to `prev`.
     _BidirectionalIterator __lm1 = _VSTD::prev(__last);
-    value_type __tmp = _VSTD::move(*__lm1);
+    value_type __tmp = _IterOps<_AlgPolicy>::__iter_move(__lm1);
+    // TODO(ranges): pass `_AlgPolicy` to `move_backward`.
     _BidirectionalIterator __fp1 = _VSTD::move_backward(__first, __lm1, __last);
     *__first = _VSTD::move(__tmp);
     return __fp1;
 }
 
-template <class _ForwardIterator>
+template <class _AlgPolicy, class _ForwardIterator>
 _LIBCPP_CONSTEXPR_AFTER_CXX14 _ForwardIterator
 __rotate_forward(_ForwardIterator __first, _ForwardIterator __middle, _ForwardIterator __last)
 {
     _ForwardIterator __i = __middle;
     while (true)
     {
-        swap(*__first, *__i);
+        _IterOps<_AlgPolicy>::iter_swap(__first, __i);
         ++__first;
         if (++__i == __last)
             break;
@@ -69,7 +73,7 @@ __rotate_forward(_ForwardIterator __first, _ForwardIterator __middle, _ForwardIt
         __i = __middle;
         while (true)
         {
-            swap(*__first, *__i);
+            _IterOps<_AlgPolicy>::iter_swap(__first, __i);
             ++__first;
             if (++__i == __last)
             {
@@ -98,7 +102,7 @@ __algo_gcd(_Integral __x, _Integral __y)
     return __x;
 }
 
-template<typename _RandomAccessIterator>
+template <class _AlgPolicy, typename _RandomAccessIterator>
 _LIBCPP_CONSTEXPR_AFTER_CXX14 _RandomAccessIterator
 __rotate_gcd(_RandomAccessIterator __first, _RandomAccessIterator __middle, _RandomAccessIterator __last)
 {
@@ -109,18 +113,19 @@ __rotate_gcd(_RandomAccessIterator __first, _RandomAccessIterator __middle, _Ran
     const difference_type __m2 = __last - __middle;
     if (__m1 == __m2)
     {
+        // TODO(ranges): pass `_AlgPolicy` to `swap_ranges`.
         _VSTD::swap_ranges(__first, __middle, __middle);
         return __middle;
     }
     const difference_type __g = _VSTD::__algo_gcd(__m1, __m2);
     for (_RandomAccessIterator __p = __first + __g; __p != __first;)
     {
-        value_type __t(_VSTD::move(*--__p));
+        value_type __t(_IterOps<_AlgPolicy>::__iter_move(--__p));
         _RandomAccessIterator __p1 = __p;
         _RandomAccessIterator __p2 = __p1 + __m1;
         do
         {
-            *__p1 = _VSTD::move(*__p2);
+            *__p1 = _IterOps<_AlgPolicy>::__iter_move(__p2);
             __p1 = __p2;
             const difference_type __d = __last - __p2;
             if (__m1 < __d)
@@ -133,54 +138,66 @@ __rotate_gcd(_RandomAccessIterator __first, _RandomAccessIterator __middle, _Ran
     return __first + __m2;
 }
 
-template <class _ForwardIterator>
+template <class _AlgPolicy, class _ForwardIterator>
 inline _LIBCPP_INLINE_VISIBILITY
 _LIBCPP_CONSTEXPR_AFTER_CXX11 _ForwardIterator
-__rotate(_ForwardIterator __first, _ForwardIterator __middle, _ForwardIterator __last,
+__rotate_impl(_ForwardIterator __first, _ForwardIterator __middle, _ForwardIterator __last,
          _VSTD::forward_iterator_tag)
 {
     typedef typename iterator_traits<_ForwardIterator>::value_type value_type;
     if (is_trivially_move_assignable<value_type>::value)
     {
-        if (_VSTD::next(__first) == __middle)
-            return _VSTD::__rotate_left(__first, __last);
+        if (_IterOps<_AlgPolicy>::next(__first) == __middle)
+            return std::__rotate_left<_AlgPolicy>(__first, __last);
     }
-    return _VSTD::__rotate_forward(__first, __middle, __last);
+    return std::__rotate_forward<_AlgPolicy>(__first, __middle, __last);
 }
 
-template <class _BidirectionalIterator>
+template <class _AlgPolicy, class _BidirectionalIterator>
 inline _LIBCPP_INLINE_VISIBILITY
 _LIBCPP_CONSTEXPR_AFTER_CXX11 _BidirectionalIterator
-__rotate(_BidirectionalIterator __first, _BidirectionalIterator __middle, _BidirectionalIterator __last,
+__rotate_impl(_BidirectionalIterator __first, _BidirectionalIterator __middle, _BidirectionalIterator __last,
          bidirectional_iterator_tag)
 {
     typedef typename iterator_traits<_BidirectionalIterator>::value_type value_type;
     if (is_trivially_move_assignable<value_type>::value)
     {
-        if (_VSTD::next(__first) == __middle)
-            return _VSTD::__rotate_left(__first, __last);
-        if (_VSTD::next(__middle) == __last)
-            return _VSTD::__rotate_right(__first, __last);
+        if (_IterOps<_AlgPolicy>::next(__first) == __middle)
+            return std::__rotate_left<_AlgPolicy>(__first, __last);
+        if (_IterOps<_AlgPolicy>::next(__middle) == __last)
+            return std::__rotate_right<_AlgPolicy>(__first, __last);
     }
-    return _VSTD::__rotate_forward(__first, __middle, __last);
+    return std::__rotate_forward<_AlgPolicy>(__first, __middle, __last);
 }
 
-template <class _RandomAccessIterator>
+template <class _AlgPolicy, class _RandomAccessIterator>
 inline _LIBCPP_INLINE_VISIBILITY
 _LIBCPP_CONSTEXPR_AFTER_CXX11 _RandomAccessIterator
-__rotate(_RandomAccessIterator __first, _RandomAccessIterator __middle, _RandomAccessIterator __last,
+__rotate_impl(_RandomAccessIterator __first, _RandomAccessIterator __middle, _RandomAccessIterator __last,
          random_access_iterator_tag)
 {
     typedef typename iterator_traits<_RandomAccessIterator>::value_type value_type;
     if (is_trivially_move_assignable<value_type>::value)
     {
-        if (_VSTD::next(__first) == __middle)
-            return _VSTD::__rotate_left(__first, __last);
-        if (_VSTD::next(__middle) == __last)
-            return _VSTD::__rotate_right(__first, __last);
-        return _VSTD::__rotate_gcd(__first, __middle, __last);
+        if (_IterOps<_AlgPolicy>::next(__first) == __middle)
+            return std::__rotate_left<_AlgPolicy>(__first, __last);
+        if (_IterOps<_AlgPolicy>::next(__middle) == __last)
+            return std::__rotate_right<_AlgPolicy>(__first, __last);
+        return std::__rotate_gcd<_AlgPolicy>(__first, __middle, __last);
     }
-    return _VSTD::__rotate_forward(__first, __middle, __last);
+    return std::__rotate_forward<_AlgPolicy>(__first, __middle, __last);
+}
+
+template <class _AlgPolicy, class _RandomAccessIterator, class _IterCategory>
+_LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_AFTER_CXX11
+_RandomAccessIterator __rotate(_RandomAccessIterator __first, _RandomAccessIterator __middle,
+    _RandomAccessIterator __last, _IterCategory __iter_category) {
+  if (__first == __middle)
+      return __last;
+  if (__middle == __last)
+      return __first;
+
+  return std::__rotate_impl<_AlgPolicy>(std::move(__first), std::move(__middle), std::move(__last), __iter_category);
 }
 
 template <class _ForwardIterator>
@@ -188,12 +205,8 @@ inline _LIBCPP_INLINE_VISIBILITY
 _LIBCPP_CONSTEXPR_AFTER_CXX17 _ForwardIterator
 rotate(_ForwardIterator __first, _ForwardIterator __middle, _ForwardIterator __last)
 {
-    if (__first == __middle)
-        return __last;
-    if (__middle == __last)
-        return __first;
-    return _VSTD::__rotate(__first, __middle, __last,
-                           typename iterator_traits<_ForwardIterator>::iterator_category());
+  return std::__rotate<_ClassicAlgPolicy>(__first, __middle, __last,
+                                          typename iterator_traits<_ForwardIterator>::iterator_category());
 }
 
 _LIBCPP_END_NAMESPACE_STD