Import libs 4 (#758)

1 files changed, 25 insertions, 19 deletions

diff --git a/contrib/libs/cxxsupp/libcxx/include/__algorithm/inplace_merge.h b/contrib/libs/cxxsupp/libcxx/include/__algorithm/inplace_merge.h
index 58919ddbae..7369786eeb 100644
--- a/contrib/libs/cxxsupp/libcxx/include/__algorithm/inplace_merge.h
+++ b/contrib/libs/cxxsupp/libcxx/include/__algorithm/inplace_merge.h
@@ -11,6 +11,7 @@
 
 #include <__algorithm/comp.h>
 #include <__algorithm/comp_ref_type.h>
+#include <__algorithm/iterator_operations.h>
 #include <__algorithm/lower_bound.h>
 #include <__algorithm/min.h>
 #include <__algorithm/move.h>
@@ -21,7 +22,6 @@
 #include <__iterator/distance.h>
 #include <__iterator/iterator_traits.h>
 #include <__iterator/reverse_iterator.h>
-#include <__utility/swap.h>
 #include <memory>
 
 #if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER)
@@ -53,7 +53,7 @@ public:
     bool operator()(const _T1& __x, const _T2& __y) {return __p_(__y, __x);}
 };
 
-template <class _Compare, class _InputIterator1, class _InputIterator2,
+template <class _AlgPolicy, class _Compare, class _InputIterator1, class _InputIterator2,
           class _OutputIterator>
 void __half_inplace_merge(_InputIterator1 __first1, _InputIterator1 __last1,
                           _InputIterator2 __first2, _InputIterator2 __last2,
@@ -63,25 +63,26 @@ void __half_inplace_merge(_InputIterator1 __first1, _InputIterator1 __last1,
     {
         if (__first2 == __last2)
         {
+            // TODO(alg-policy): pass `_AlgPolicy` once it's supported by `move`.
             _VSTD::move(__first1, __last1, __result);
             return;
         }
 
         if (__comp(*__first2, *__first1))
         {
-            *__result = _VSTD::move(*__first2);
+            *__result = _IterOps<_AlgPolicy>::__iter_move(__first2);
             ++__first2;
         }
         else
         {
-            *__result = _VSTD::move(*__first1);
+            *__result = _IterOps<_AlgPolicy>::__iter_move(__first1);
             ++__first1;
         }
     }
     // __first2 through __last2 are already in the right spot.
 }
 
-template <class _Compare, class _BidirectionalIterator>
+template <class _AlgPolicy, class _Compare, class _BidirectionalIterator>
 void
 __buffered_inplace_merge(_BidirectionalIterator __first, _BidirectionalIterator __middle, _BidirectionalIterator __last,
                 _Compare __comp, typename iterator_traits<_BidirectionalIterator>::difference_type __len1,
@@ -95,30 +96,32 @@ __buffered_inplace_merge(_BidirectionalIterator __first, _BidirectionalIterator
     {
         value_type* __p = __buff;
         for (_BidirectionalIterator __i = __first; __i != __middle; __d.template __incr<value_type>(), (void) ++__i, (void) ++__p)
-            ::new ((void*)__p) value_type(_VSTD::move(*__i));
-        _VSTD::__half_inplace_merge<_Compare>(__buff, __p, __middle, __last, __first, __comp);
+            ::new ((void*)__p) value_type(_IterOps<_AlgPolicy>::__iter_move(__i));
+        std::__half_inplace_merge<_AlgPolicy, _Compare>(__buff, __p, __middle, __last, __first, __comp);
     }
     else
     {
         value_type* __p = __buff;
         for (_BidirectionalIterator __i = __middle; __i != __last; __d.template __incr<value_type>(), (void) ++__i, (void) ++__p)
-            ::new ((void*)__p) value_type(_VSTD::move(*__i));
+            ::new ((void*)__p) value_type(_IterOps<_AlgPolicy>::__iter_move(__i));
         typedef reverse_iterator<_BidirectionalIterator> _RBi;
         typedef reverse_iterator<value_type*> _Rv;
         typedef __invert<_Compare> _Inverted;
-        _VSTD::__half_inplace_merge<_Inverted>(_Rv(__p), _Rv(__buff),
+        std::__half_inplace_merge<_AlgPolicy, _Inverted>(_Rv(__p), _Rv(__buff),
                                     _RBi(__middle), _RBi(__first),
                                     _RBi(__last), _Inverted(__comp));
     }
 }
 
-template <class _Compare, class _BidirectionalIterator>
+template <class _AlgPolicy, class _Compare, class _BidirectionalIterator>
 void
 __inplace_merge(_BidirectionalIterator __first, _BidirectionalIterator __middle, _BidirectionalIterator __last,
                 _Compare __comp, typename iterator_traits<_BidirectionalIterator>::difference_type __len1,
                                  typename iterator_traits<_BidirectionalIterator>::difference_type __len2,
                 typename iterator_traits<_BidirectionalIterator>::value_type* __buff, ptrdiff_t __buff_size)
 {
+    using _Ops = _IterOps<_AlgPolicy>;
+
     typedef typename iterator_traits<_BidirectionalIterator>::difference_type difference_type;
     while (true)
     {
@@ -126,7 +129,7 @@ __inplace_merge(_BidirectionalIterator __first, _BidirectionalIterator __middle,
         if (__len2 == 0)
             return;
         if (__len1 <= __buff_size || __len2 <= __buff_size)
-            return _VSTD::__buffered_inplace_merge<_Compare>
+            return std::__buffered_inplace_merge<_AlgPolicy, _Compare>
                    (__first, __middle, __last, __comp, __len1, __len2, __buff);
         // shrink [__first, __middle) as much as possible (with no moves), returning if it shrinks to 0
         for (; true; ++__first, (void) --__len1)
@@ -153,35 +156,37 @@ __inplace_merge(_BidirectionalIterator __first, _BidirectionalIterator __middle,
         {   // __len >= 1, __len2 >= 2
             __len21 = __len2 / 2;
             __m2 = __middle;
-            _VSTD::advance(__m2, __len21);
+            _Ops::advance(__m2, __len21);
             __m1 = _VSTD::__upper_bound<_Compare>(__first, __middle, *__m2, __comp);
-            __len11 = _VSTD::distance(__first, __m1);
+            __len11 = _Ops::distance(__first, __m1);
         }
         else
         {
             if (__len1 == 1)
             {   // __len1 >= __len2 && __len2 > 0, therefore __len2 == 1
                 // It is known *__first > *__middle
-                swap(*__first, *__middle);
+              _Ops::iter_swap(__first, __middle);
                 return;
             }
             // __len1 >= 2, __len2 >= 1
             __len11 = __len1 / 2;
             __m1 = __first;
-            _VSTD::advance(__m1, __len11);
+            _Ops::advance(__m1, __len11);
             __m2 = std::lower_bound(__middle, __last, *__m1, __comp);
-            __len21 = _VSTD::distance(__middle, __m2);
+            __len21 = _Ops::distance(__middle, __m2);
         }
         difference_type __len12 = __len1 - __len11;  // distance(__m1, __middle)
         difference_type __len22 = __len2 - __len21;  // distance(__m2, __last)
         // [__first, __m1) [__m1, __middle) [__middle, __m2) [__m2, __last)
         // swap middle two partitions
+        // TODO(alg-policy): pass `_AlgPolicy` once it's supported by `rotate`.
         __middle = _VSTD::rotate(__m1, __middle, __m2);
         // __len12 and __len21 now have swapped meanings
         // merge smaller range with recursive call and larger with tail recursion elimination
         if (__len11 + __len21 < __len12 + __len22)
         {
-            _VSTD::__inplace_merge<_Compare>(__first, __m1, __middle, __comp, __len11, __len21, __buff, __buff_size);
+            std::__inplace_merge<_AlgPolicy, _Compare>(
+                __first, __m1, __middle, __comp, __len11, __len21, __buff, __buff_size);
 //          _VSTD::__inplace_merge<_Compare>(__middle, __m2, __last, __comp, __len12, __len22, __buff, __buff_size);
             __first = __middle;
             __middle = __m2;
@@ -190,7 +195,8 @@ __inplace_merge(_BidirectionalIterator __first, _BidirectionalIterator __middle,
         }
         else
         {
-            _VSTD::__inplace_merge<_Compare>(__middle, __m2, __last, __comp, __len12, __len22, __buff, __buff_size);
+            std::__inplace_merge<_AlgPolicy, _Compare>(
+                __middle, __m2, __last, __comp, __len12, __len22, __buff, __buff_size);
 //          _VSTD::__inplace_merge<_Compare>(__first, __m1, __middle, __comp, __len11, __len21, __buff, __buff_size);
             __last = __middle;
             __middle = __m1;
@@ -217,7 +223,7 @@ _LIBCPP_SUPPRESS_DEPRECATED_PUSH
 _LIBCPP_SUPPRESS_DEPRECATED_POP
     unique_ptr<value_type, __return_temporary_buffer> __h(__buf.first);
     typedef typename __comp_ref_type<_Compare>::type _Comp_ref;
-    return _VSTD::__inplace_merge<_Comp_ref>(__first, __middle, __last, __comp, __len1, __len2,
+    return _VSTD::__inplace_merge<_ClassicAlgPolicy, _Comp_ref>(__first, __middle, __last, __comp, __len1, __len2,
                                             __buf.first, __buf.second);
 }