vendor/libc++/libc++-release_370-r246257

1 files changed, 93 insertions, 81 deletions

diff --git a/include/algorithm b/include/algorithm
index 02cbc816f61f..7b0c53e05a5a 100644
--- a/include/algorithm
+++ b/include/algorithm
@@ -521,11 +521,11 @@ template <class RandomAccessIterator, class Compare>
 
 template <class ForwardIterator>
     ForwardIterator
-    min_element(ForwardIterator first, ForwardIterator last);
+    min_element(ForwardIterator first, ForwardIterator last);  // constexpr in C++14
 
 template <class ForwardIterator, class Compare>
     ForwardIterator
-    min_element(ForwardIterator first, ForwardIterator last, Compare comp);
+    min_element(ForwardIterator first, ForwardIterator last, Compare comp);  // constexpr in C++14
 
 template <class T>
     const T&
@@ -545,11 +545,11 @@ template<class T, class Compare>
 
 template <class ForwardIterator>
     ForwardIterator
-    max_element(ForwardIterator first, ForwardIterator last);
+    max_element(ForwardIterator first, ForwardIterator last);  // constexpr in C++14
 
 template <class ForwardIterator, class Compare>
     ForwardIterator
-    max_element(ForwardIterator first, ForwardIterator last, Compare comp);
+    max_element(ForwardIterator first, ForwardIterator last, Compare comp);  // constexpr in C++14
 
 template <class T>
     const T&
@@ -569,11 +569,11 @@ template<class T, class Compare>
 
 template<class ForwardIterator>
     pair<ForwardIterator, ForwardIterator>
-    minmax_element(ForwardIterator first, ForwardIterator last);
+    minmax_element(ForwardIterator first, ForwardIterator last);   // constexpr in C++14
 
 template<class ForwardIterator, class Compare>
     pair<ForwardIterator, ForwardIterator>
-    minmax_element(ForwardIterator first, ForwardIterator last, Compare comp);
+    minmax_element(ForwardIterator first, ForwardIterator last, Compare comp);   // constexpr in C++14
 
 template<class T>
     pair<const T&, const T&>
@@ -1672,7 +1672,8 @@ search_n(_ForwardIterator __first, _ForwardIterator __last,
          _Size __count, const _Tp& __value_, _BinaryPredicate __pred)
 {
     return _VSTD::__search_n<typename add_lvalue_reference<_BinaryPredicate>::type>
-           (__first, __last, __count, __value_, __pred, typename iterator_traits<_ForwardIterator>::iterator_category());
+           (__first, __last, __convert_to_integral(__count), __value_, __pred,
+           typename iterator_traits<_ForwardIterator>::iterator_category());
 }
 
 template <class _ForwardIterator, class _Size, class _Tp>
@@ -1681,7 +1682,8 @@ _ForwardIterator
 search_n(_ForwardIterator __first, _ForwardIterator __last, _Size __count, const _Tp& __value_)
 {
     typedef typename iterator_traits<_ForwardIterator>::value_type __v;
-    return _VSTD::search_n(__first, __last, __count, __value_, __equal_to<__v, _Tp>());
+    return _VSTD::search_n(__first, __last, __convert_to_integral(__count),
+                           __value_, __equal_to<__v, _Tp>());
 }
 
 // copy
@@ -1761,7 +1763,8 @@ typename enable_if
 __copy(_Tp* __first, _Tp* __last, _Up* __result)
 {
     const size_t __n = static_cast<size_t>(__last - __first);
-    _VSTD::memmove(__result, __first, __n * sizeof(_Up));
+    if (__n > 0)
+        _VSTD::memmove(__result, __first, __n * sizeof(_Up));
     return __result + __n;
 }
 
@@ -1796,8 +1799,11 @@ typename enable_if
 __copy_backward(_Tp* __first, _Tp* __last, _Up* __result)
 {
     const size_t __n = static_cast<size_t>(__last - __first);
-    __result -= __n;
-    _VSTD::memmove(__result, __first, __n * sizeof(_Up));
+    if (__n > 0)
+    {
+        __result -= __n;
+        _VSTD::memmove(__result, __first, __n * sizeof(_Up));
+    }
     return __result;
 }
 
@@ -1839,8 +1845,10 @@ typename enable_if
    !__is_random_access_iterator<_InputIterator>::value,
     _OutputIterator
 >::type
-copy_n(_InputIterator __first, _Size __n, _OutputIterator __result)
+copy_n(_InputIterator __first, _Size __orig_n, _OutputIterator __result)
 {
+    typedef decltype(__convert_to_integral(__orig_n)) _IntegralSize;
+    _IntegralSize __n = __orig_n;
     if (__n > 0)
     {
         *__result = *__first;
@@ -1862,8 +1870,10 @@ typename enable_if
     __is_random_access_iterator<_InputIterator>::value,
     _OutputIterator
 >::type
-copy_n(_InputIterator __first, _Size __n, _OutputIterator __result)
+copy_n(_InputIterator __first, _Size __orig_n, _OutputIterator __result)
 {
+    typedef decltype(__convert_to_integral(__orig_n)) _IntegralSize;
+    _IntegralSize __n = __orig_n;
     return _VSTD::copy(__first, __first + __n, __result);
 }
 
@@ -1890,7 +1900,8 @@ typename enable_if
 __move(_Tp* __first, _Tp* __last, _Up* __result)
 {
     const size_t __n = static_cast<size_t>(__last - __first);
-    _VSTD::memmove(__result, __first, __n * sizeof(_Up));
+    if (__n > 0)
+        _VSTD::memmove(__result, __first, __n * sizeof(_Up));
     return __result + __n;
 }
 
@@ -1925,8 +1936,11 @@ typename enable_if
 __move_backward(_Tp* __first, _Tp* __last, _Up* __result)
 {
     const size_t __n = static_cast<size_t>(__last - __first);
-    __result -= __n;
-    _VSTD::memmove(__result, __first, __n * sizeof(_Up));
+    if (__n > 0)
+    {
+        __result -= __n;
+        _VSTD::memmove(__result, __first, __n * sizeof(_Up));
+    }
     return __result;
 }
 
@@ -2055,7 +2069,7 @@ inline _LIBCPP_INLINE_VISIBILITY
 _OutputIterator
 fill_n(_OutputIterator __first, _Size __n, const _Tp& __value_)
 {
-   return _VSTD::__fill_n(__first, __n, __value_);
+   return _VSTD::__fill_n(__first, __convert_to_integral(__n), __value_);
 }
 
 // fill
@@ -2101,8 +2115,10 @@ generate(_ForwardIterator __first, _ForwardIterator __last, _Generator __gen)
 template <class _OutputIterator, class _Size, class _Generator>
 inline _LIBCPP_INLINE_VISIBILITY
 _OutputIterator
-generate_n(_OutputIterator __first, _Size __n, _Generator __gen)
+generate_n(_OutputIterator __first, _Size __orig_n, _Generator __gen)
 {
+    typedef decltype(__convert_to_integral(__orig_n)) _IntegralSize;
+    _IntegralSize __n = __orig_n;
     for (; __n > 0; ++__first, (void) --__n)
         *__first = __gen();
     return __first;
@@ -2536,7 +2552,7 @@ rotate_copy(_ForwardIterator __first, _ForwardIterator __middle, _ForwardIterato
 template <class _ForwardIterator, class _Compare>
 inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX11
 _ForwardIterator
-__min_element(_ForwardIterator __first, _ForwardIterator __last, _Compare __comp)
+min_element(_ForwardIterator __first, _ForwardIterator __last, _Compare __comp)
 {
     if (__first != __last)
     {
@@ -2548,20 +2564,12 @@ __min_element(_ForwardIterator __first, _ForwardIterator __last, _Compare __comp
     return __first;
 }
 
-template <class _ForwardIterator, class _Compare>
-inline _LIBCPP_INLINE_VISIBILITY
-_ForwardIterator
-min_element(_ForwardIterator __first, _ForwardIterator __last, _Compare __comp)
-{
-    return __min_element(__first, __last, __comp);
-}
-
 template <class _ForwardIterator>
-inline _LIBCPP_INLINE_VISIBILITY
+inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX11
 _ForwardIterator
 min_element(_ForwardIterator __first, _ForwardIterator __last)
 {
-    return __min_element(__first, __last,
+    return _VSTD::min_element(__first, __last,
               __less<typename iterator_traits<_ForwardIterator>::value_type>());
 }
 
@@ -2590,7 +2598,7 @@ inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX11
 _Tp
 min(initializer_list<_Tp> __t, _Compare __comp)
 {
-    return *__min_element(__t.begin(), __t.end(), __comp);
+    return *_VSTD::min_element(__t.begin(), __t.end(), __comp);
 }
 
 template<class _Tp>
@@ -2598,7 +2606,7 @@ inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX11
 _Tp
 min(initializer_list<_Tp> __t)
 {
-    return *__min_element(__t.begin(), __t.end(), __less<_Tp>());
+    return *_VSTD::min_element(__t.begin(), __t.end(), __less<_Tp>());
 }
 
 #endif  // _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS
@@ -2608,7 +2616,7 @@ min(initializer_list<_Tp> __t)
 template <class _ForwardIterator, class _Compare>
 inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX11
 _ForwardIterator
-__max_element(_ForwardIterator __first, _ForwardIterator __last, _Compare __comp)
+max_element(_ForwardIterator __first, _ForwardIterator __last, _Compare __comp)
 {
     if (__first != __last)
     {
@@ -2621,20 +2629,12 @@ __max_element(_ForwardIterator __first, _ForwardIterator __last, _Compare __comp
 }
 
 
-template <class _ForwardIterator, class _Compare>
-inline _LIBCPP_INLINE_VISIBILITY
-_ForwardIterator
-max_element(_ForwardIterator __first, _ForwardIterator __last, _Compare __comp)
-{
-    return __max_element(__first, __last, __comp);
-}
-
 template <class _ForwardIterator>
-inline _LIBCPP_INLINE_VISIBILITY
+inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX11
 _ForwardIterator
 max_element(_ForwardIterator __first, _ForwardIterator __last)
 {
-    return __max_element(__first, __last,
+    return _VSTD::max_element(__first, __last,
               __less<typename iterator_traits<_ForwardIterator>::value_type>());
 }
 
@@ -2663,7 +2663,7 @@ inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX11
 _Tp
 max(initializer_list<_Tp> __t, _Compare __comp)
 {
-    return *__max_element(__t.begin(), __t.end(), __comp);
+    return *_VSTD::max_element(__t.begin(), __t.end(), __comp);
 }
 
 template<class _Tp>
@@ -2671,7 +2671,7 @@ inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX11
 _Tp
 max(initializer_list<_Tp> __t)
 {
-    return *__max_element(__t.begin(), __t.end(), __less<_Tp>());
+    return *_VSTD::max_element(__t.begin(), __t.end(), __less<_Tp>());
 }
 
 #endif  // _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS
@@ -2679,6 +2679,7 @@ max(initializer_list<_Tp> __t)
 // minmax_element
 
 template <class _ForwardIterator, class _Compare>
+_LIBCPP_CONSTEXPR_AFTER_CXX11
 std::pair<_ForwardIterator, _ForwardIterator>
 minmax_element(_ForwardIterator __first, _ForwardIterator __last, _Compare __comp)
 {
@@ -2726,7 +2727,7 @@ minmax_element(_ForwardIterator __first, _ForwardIterator __last, _Compare __com
 }
 
 template <class _ForwardIterator>
-inline _LIBCPP_INLINE_VISIBILITY
+inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX11
 std::pair<_ForwardIterator, _ForwardIterator>
 minmax_element(_ForwardIterator __first, _ForwardIterator __last)
 {
@@ -2763,7 +2764,7 @@ minmax(initializer_list<_Tp> __t, _Compare __comp)
     typedef typename initializer_list<_Tp>::const_iterator _Iter;
     _Iter __first = __t.begin();
     _Iter __last  = __t.end();
-    std::pair<_Tp, _Tp> __result ( *__first, *__first );
+    std::pair<_Tp, _Tp> __result(*__first, *__first);
 
     ++__first;
     if (__t.size() % 2 == 0)
@@ -2778,13 +2779,13 @@ minmax(initializer_list<_Tp> __t, _Compare __comp)
     while (__first != __last)
     {
         _Tp __prev = *__first++;
-        if (__comp(__prev, *__first)) {
-            if (__comp(__prev, __result.first))    __result.first  = __prev;
-            if (__comp(__result.second, *__first)) __result.second = *__first;
+        if (__comp(*__first, __prev)) {
+            if ( __comp(*__first, __result.first)) __result.first  = *__first;
+            if (!__comp(__prev, __result.second))  __result.second = __prev;
             }
         else {
-            if (__comp(*__first, __result.first)) __result.first  = *__first;
-            if (__comp(__result.second, __prev))  __result.second = __prev;
+            if ( __comp(__prev, __result.first))    __result.first  = __prev;
+            if (!__comp(*__first, __result.second)) __result.second = *__first;
             }
                 
         __first++;
@@ -3148,6 +3149,9 @@ is_partitioned(_InputIterator __first, _InputIterator __last, _Predicate __pred)
     for (; __first != __last; ++__first)
         if (!__pred(*__first))
             break;
+    if ( __first == __last )
+        return true;
+    ++__first;
     for (; __first != __last; ++__first)
         if (__pred(*__first))
             return false;
@@ -4357,6 +4361,34 @@ merge(_InputIterator1 __first1, _InputIterator1 __last1,
 
 // inplace_merge
 
+template <class _Compare, class _InputIterator1, class _InputIterator2,
+          class _OutputIterator>
+void __half_inplace_merge(_InputIterator1 __first1, _InputIterator1 __last1,
+                          _InputIterator2 __first2, _InputIterator2 __last2,
+                          _OutputIterator __result, _Compare __comp)
+{
+    for (; __first1 != __last1; ++__result)
+    {
+        if (__first2 == __last2)
+        {
+            _VSTD::move(__first1, __last1, __result);
+            return;
+        }
+
+        if (__comp(*__first2, *__first1))
+        {
+            *__result = _VSTD::move(*__first2);
+            ++__first2;
+        }
+        else
+        {
+            *__result = _VSTD::move(*__first1);
+            ++__first1;
+        }
+    }
+    // __first2 through __last2 are already in the right spot.
+}
+
 template <class _Compare, class _BidirectionalIterator>
 void
 __buffered_inplace_merge(_BidirectionalIterator __first, _BidirectionalIterator __middle, _BidirectionalIterator __last,
@@ -4365,8 +4397,6 @@ __buffered_inplace_merge(_BidirectionalIterator __first, _BidirectionalIterator
                 typename iterator_traits<_BidirectionalIterator>::value_type* __buff)
 {
     typedef typename iterator_traits<_BidirectionalIterator>::value_type value_type;
-    typedef typename iterator_traits<_BidirectionalIterator>::difference_type difference_type;
-    typedef typename iterator_traits<_BidirectionalIterator>::pointer pointer;
     __destruct_n __d(0);
     unique_ptr<value_type, __destruct_n&> __h2(__buff, __d);
     if (__len1 <= __len2)
@@ -4374,11 +4404,7 @@ __buffered_inplace_merge(_BidirectionalIterator __first, _BidirectionalIterator
         value_type* __p = __buff;
         for (_BidirectionalIterator __i = __first; __i != __middle; __d.__incr((value_type*)0), (void) ++__i, ++__p)
             ::new(__p) value_type(_VSTD::move(*__i));
-        __merge<_Compare>(move_iterator<value_type*>(__buff),
-                          move_iterator<value_type*>(__p),
-                          move_iterator<_BidirectionalIterator>(__middle),
-                          move_iterator<_BidirectionalIterator>(__last),
-                          __first, __comp);
+        __half_inplace_merge(__buff, __p, __middle, __last, __first, __comp);
     }
     else
     {
@@ -4387,9 +4413,9 @@ __buffered_inplace_merge(_BidirectionalIterator __first, _BidirectionalIterator
             ::new(__p) value_type(_VSTD::move(*__i));
         typedef reverse_iterator<_BidirectionalIterator> _RBi;
         typedef reverse_iterator<value_type*> _Rv;
-        __merge(move_iterator<_RBi>(_RBi(__middle)), move_iterator<_RBi>(_RBi(__first)),
-                move_iterator<_Rv>(_Rv(__p)), move_iterator<_Rv>(_Rv(__buff)),
-                _RBi(__last), __negate<_Compare>(__comp));
+        __half_inplace_merge(_Rv(__p), _Rv(__buff), 
+                             _RBi(__middle), _RBi(__first),
+                             _RBi(__last), __negate<_Compare>(__comp));
     }
 }
 
@@ -4400,13 +4426,15 @@ __inplace_merge(_BidirectionalIterator __first, _BidirectionalIterator __middle,
                                  typename iterator_traits<_BidirectionalIterator>::difference_type __len2,
                 typename iterator_traits<_BidirectionalIterator>::value_type* __buff, ptrdiff_t __buff_size)
 {
-    typedef typename iterator_traits<_BidirectionalIterator>::value_type value_type;
     typedef typename iterator_traits<_BidirectionalIterator>::difference_type difference_type;
     while (true)
     {
         // if __middle == __last, we're done
         if (__len2 == 0)
             return;
+        if (__len1 <= __buff_size || __len2 <= __buff_size)
+            return __buffered_inplace_merge<_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)
         {
@@ -4415,11 +4443,6 @@ __inplace_merge(_BidirectionalIterator __first, _BidirectionalIterator __middle,
             if (__comp(*__middle, *__first))
                 break;
         }
-        if (__len1 <= __buff_size || __len2 <= __buff_size)
-        {
-            __buffered_inplace_merge<_Compare>(__first, __middle, __last, __comp, __len1, __len2, __buff);
-            return;
-        }
         // __first < __middle < __last
         // *__first > *__middle
         // partition [__first, __m1) [__m1, __middle) [__middle, __m2) [__m2, __last) such that
@@ -4484,12 +4507,6 @@ __inplace_merge(_BidirectionalIterator __first, _BidirectionalIterator __middle,
     }
 }
 
-template <class _Tp>
-struct __inplace_merge_switch
-{
-    static const unsigned value = is_trivially_copy_assignable<_Tp>::value;
-};
-
 template <class _BidirectionalIterator, class _Compare>
 inline _LIBCPP_INLINE_VISIBILITY
 void
@@ -4501,13 +4518,9 @@ inplace_merge(_BidirectionalIterator __first, _BidirectionalIterator __middle, _
     difference_type __len1 = _VSTD::distance(__first, __middle);
     difference_type __len2 = _VSTD::distance(__middle, __last);
     difference_type __buf_size = _VSTD::min(__len1, __len2);
-    pair<value_type*, ptrdiff_t> __buf(0, 0);
-    unique_ptr<value_type, __return_temporary_buffer> __h;
-    if (__inplace_merge_switch<value_type>::value && __buf_size > 8)
-    {
-        __buf = _VSTD::get_temporary_buffer<value_type>(__buf_size);
-        __h.reset(__buf.first);
-    }
+    pair<value_type*, ptrdiff_t> __buf = _VSTD::get_temporary_buffer<value_type>(__buf_size);
+    unique_ptr<value_type, __return_temporary_buffer> __h(__buf.first);
+
 #ifdef _LIBCPP_DEBUG
     typedef typename add_lvalue_reference<__debug_less<_Compare> >::type _Comp_ref;
     __debug_less<_Compare> __c(__comp);
@@ -4799,7 +4812,6 @@ void
 __sift_up(_RandomAccessIterator __first, _RandomAccessIterator __last, _Compare __comp,
           typename iterator_traits<_RandomAccessIterator>::difference_type __len)
 {
-    typedef typename iterator_traits<_RandomAccessIterator>::difference_type difference_type;
     typedef typename iterator_traits<_RandomAccessIterator>::value_type value_type;
     if (__len > 1)
     {