diff options
Diffstat (limited to 'lib/libcxx/include/__algorithm')
96 files changed, 466 insertions, 654 deletions
diff --git a/lib/libcxx/include/__algorithm/adjacent_find.h b/lib/libcxx/include/__algorithm/adjacent_find.h index 0a2aa055c1..29ad83f968 100644 --- a/lib/libcxx/include/__algorithm/adjacent_find.h +++ b/lib/libcxx/include/__algorithm/adjacent_find.h @@ -10,17 +10,14 @@ #ifndef _LIBCPP___ALGORITHM_ADJACENT_FIND_H #define _LIBCPP___ALGORITHM_ADJACENT_FIND_H -#include <__config> #include <__algorithm/comp.h> +#include <__config> #include <__iterator/iterator_traits.h> #if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER) #pragma GCC system_header #endif -_LIBCPP_PUSH_MACROS -#include <__undef_macros> - _LIBCPP_BEGIN_NAMESPACE_STD template <class _ForwardIterator, class _BinaryPredicate> @@ -46,6 +43,4 @@ adjacent_find(_ForwardIterator __first, _ForwardIterator __last) { _LIBCPP_END_NAMESPACE_STD -_LIBCPP_POP_MACROS - #endif // _LIBCPP___ALGORITHM_ADJACENT_FIND_H diff --git a/lib/libcxx/include/__algorithm/all_of.h b/lib/libcxx/include/__algorithm/all_of.h index 7d6ed50859..817a4bc89c 100644 --- a/lib/libcxx/include/__algorithm/all_of.h +++ b/lib/libcxx/include/__algorithm/all_of.h @@ -16,9 +16,6 @@ #pragma GCC system_header #endif -_LIBCPP_PUSH_MACROS -#include <__undef_macros> - _LIBCPP_BEGIN_NAMESPACE_STD template <class _InputIterator, class _Predicate> @@ -32,6 +29,4 @@ all_of(_InputIterator __first, _InputIterator __last, _Predicate __pred) { _LIBCPP_END_NAMESPACE_STD -_LIBCPP_POP_MACROS - #endif // _LIBCPP___ALGORITHM_ALL_OF_H diff --git a/lib/libcxx/include/__algorithm/any_of.h b/lib/libcxx/include/__algorithm/any_of.h index d5a6c094a6..f4116d9130 100644 --- a/lib/libcxx/include/__algorithm/any_of.h +++ b/lib/libcxx/include/__algorithm/any_of.h @@ -16,9 +16,6 @@ #pragma GCC system_header #endif -_LIBCPP_PUSH_MACROS -#include <__undef_macros> - _LIBCPP_BEGIN_NAMESPACE_STD template <class _InputIterator, class _Predicate> @@ -32,6 +29,4 @@ any_of(_InputIterator __first, _InputIterator __last, _Predicate __pred) { _LIBCPP_END_NAMESPACE_STD -_LIBCPP_POP_MACROS - #endif // _LIBCPP___ALGORITHM_ANY_OF_H diff --git a/lib/libcxx/include/__algorithm/binary_search.h b/lib/libcxx/include/__algorithm/binary_search.h index 766f5da162..2558dd0b27 100644 --- a/lib/libcxx/include/__algorithm/binary_search.h +++ b/lib/libcxx/include/__algorithm/binary_search.h @@ -9,19 +9,16 @@ #ifndef _LIBCPP___ALGORITHM_BINARY_SEARCH_H #define _LIBCPP___ALGORITHM_BINARY_SEARCH_H -#include <__config> #include <__algorithm/comp.h> -#include <__algorithm/lower_bound.h> #include <__algorithm/comp_ref_type.h> +#include <__algorithm/lower_bound.h> +#include <__config> #include <__iterator/iterator_traits.h> #if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER) #pragma GCC system_header #endif -_LIBCPP_PUSH_MACROS -#include <__undef_macros> - _LIBCPP_BEGIN_NAMESPACE_STD template <class _Compare, class _ForwardIterator, class _Tp> @@ -53,9 +50,6 @@ binary_search(_ForwardIterator __first, _ForwardIterator __last, const _Tp& __va __less<typename iterator_traits<_ForwardIterator>::value_type, _Tp>()); } - _LIBCPP_END_NAMESPACE_STD -_LIBCPP_POP_MACROS - #endif // _LIBCPP___ALGORITHM_BINARY_SEARCH_H diff --git a/lib/libcxx/include/__algorithm/clamp.h b/lib/libcxx/include/__algorithm/clamp.h index f8eba03cf8..a51c1015be 100644 --- a/lib/libcxx/include/__algorithm/clamp.h +++ b/lib/libcxx/include/__algorithm/clamp.h @@ -9,21 +9,17 @@ #ifndef _LIBCPP___ALGORITHM_CLAMP_H #define _LIBCPP___ALGORITHM_CLAMP_H +#include <__algorithm/comp.h> #include <__config> #include <__debug> -#include <__algorithm/comp.h> #if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER) #pragma GCC system_header #endif -_LIBCPP_PUSH_MACROS -#include <__undef_macros> - _LIBCPP_BEGIN_NAMESPACE_STD #if _LIBCPP_STD_VER > 14 -// clamp template<class _Tp, class _Compare> _LIBCPP_NODISCARD_EXT inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR @@ -47,6 +43,4 @@ clamp(const _Tp& __v, const _Tp& __lo, const _Tp& __hi) _LIBCPP_END_NAMESPACE_STD -_LIBCPP_POP_MACROS - #endif // _LIBCPP___ALGORITHM_CLAMP_H diff --git a/lib/libcxx/include/__algorithm/comp.h b/lib/libcxx/include/__algorithm/comp.h index 2039cf7b39..b3f971e4f0 100644 --- a/lib/libcxx/include/__algorithm/comp.h +++ b/lib/libcxx/include/__algorithm/comp.h @@ -15,9 +15,6 @@ #pragma GCC system_header #endif -_LIBCPP_PUSH_MACROS -#include <__undef_macros> - _LIBCPP_BEGIN_NAMESPACE_STD // I'd like to replace these with _VSTD::equal_to<void>, but can't because: @@ -92,6 +89,4 @@ struct __less<_T1, const _T1> _LIBCPP_END_NAMESPACE_STD -_LIBCPP_POP_MACROS - #endif // _LIBCPP___ALGORITHM_COMP_H diff --git a/lib/libcxx/include/__algorithm/comp_ref_type.h b/lib/libcxx/include/__algorithm/comp_ref_type.h index b3bca82c09..0802d2496f 100644 --- a/lib/libcxx/include/__algorithm/comp_ref_type.h +++ b/lib/libcxx/include/__algorithm/comp_ref_type.h @@ -10,15 +10,16 @@ #define _LIBCPP___ALGORITHM_COMP_REF_TYPE_H #include <__config> -#include <type_traits> + +#ifdef _LIBCPP_DEBUG +# include <__debug> +# include <__utility/declval.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 #ifdef _LIBCPP_DEBUG @@ -27,11 +28,11 @@ template <class _Compare> struct __debug_less { _Compare &__comp_; - _LIBCPP_CONSTEXPR_AFTER_CXX17 + _LIBCPP_CONSTEXPR_AFTER_CXX11 __debug_less(_Compare& __c) : __comp_(__c) {} template <class _Tp, class _Up> - _LIBCPP_CONSTEXPR_AFTER_CXX17 + _LIBCPP_CONSTEXPR_AFTER_CXX11 bool operator()(const _Tp& __x, const _Up& __y) { bool __r = __comp_(__x, __y); @@ -41,7 +42,7 @@ struct __debug_less } template <class _Tp, class _Up> - _LIBCPP_CONSTEXPR_AFTER_CXX17 + _LIBCPP_CONSTEXPR_AFTER_CXX11 bool operator()(_Tp& __x, _Up& __y) { bool __r = __comp_(__x, __y); @@ -51,7 +52,7 @@ struct __debug_less } template <class _LHS, class _RHS> - _LIBCPP_CONSTEXPR_AFTER_CXX17 + _LIBCPP_CONSTEXPR_AFTER_CXX11 inline _LIBCPP_INLINE_VISIBILITY decltype((void)declval<_Compare&>()( declval<_LHS &>(), declval<_RHS &>())) @@ -61,7 +62,7 @@ struct __debug_less } template <class _LHS, class _RHS> - _LIBCPP_CONSTEXPR_AFTER_CXX17 + _LIBCPP_CONSTEXPR_AFTER_CXX11 inline _LIBCPP_INLINE_VISIBILITY void __do_compare_assert(long, _LHS &, _RHS &) {} }; @@ -73,15 +74,12 @@ struct __comp_ref_type { // Pass the comparator by lvalue reference. Or in debug mode, using a // debugging wrapper that stores a reference. #ifndef _LIBCPP_DEBUG - typedef typename add_lvalue_reference<_Comp>::type type; + typedef _Comp& type; #else typedef __debug_less<_Comp> type; #endif }; - _LIBCPP_END_NAMESPACE_STD -_LIBCPP_POP_MACROS - #endif // _LIBCPP___ALGORITHM_COMP_REF_TYPE_H diff --git a/lib/libcxx/include/__algorithm/copy.h b/lib/libcxx/include/__algorithm/copy.h index 9db7434c04..65f0e0b0ef 100644 --- a/lib/libcxx/include/__algorithm/copy.h +++ b/lib/libcxx/include/__algorithm/copy.h @@ -9,8 +9,8 @@ #ifndef _LIBCPP___ALGORITHM_COPY_H #define _LIBCPP___ALGORITHM_COPY_H -#include <__config> #include <__algorithm/unwrap_iter.h> +#include <__config> #include <__iterator/iterator_traits.h> #include <cstring> #include <type_traits> @@ -19,9 +19,6 @@ #pragma GCC system_header #endif -_LIBCPP_PUSH_MACROS -#include <__undef_macros> - _LIBCPP_BEGIN_NAMESPACE_STD // copy @@ -77,6 +74,4 @@ copy(_InputIterator __first, _InputIterator __last, _OutputIterator __result) _LIBCPP_END_NAMESPACE_STD -_LIBCPP_POP_MACROS - #endif // _LIBCPP___ALGORITHM_COPY_H diff --git a/lib/libcxx/include/__algorithm/copy_backward.h b/lib/libcxx/include/__algorithm/copy_backward.h index 03a9c5f2d0..ac733290ab 100644 --- a/lib/libcxx/include/__algorithm/copy_backward.h +++ b/lib/libcxx/include/__algorithm/copy_backward.h @@ -9,8 +9,8 @@ #ifndef _LIBCPP___ALGORITHM_COPY_BACKWARD_H #define _LIBCPP___ALGORITHM_COPY_BACKWARD_H -#include <__config> #include <__algorithm/unwrap_iter.h> +#include <__config> #include <__iterator/iterator_traits.h> #include <cstring> #include <type_traits> @@ -19,9 +19,6 @@ #pragma GCC system_header #endif -_LIBCPP_PUSH_MACROS -#include <__undef_macros> - _LIBCPP_BEGIN_NAMESPACE_STD template <class _BidirectionalIterator, class _OutputIterator> @@ -79,6 +76,4 @@ copy_backward(_BidirectionalIterator1 __first, _BidirectionalIterator1 __last, _LIBCPP_END_NAMESPACE_STD -_LIBCPP_POP_MACROS - #endif // _LIBCPP___ALGORITHM_COPY_BACKWARD_H diff --git a/lib/libcxx/include/__algorithm/copy_if.h b/lib/libcxx/include/__algorithm/copy_if.h index 153304c7a7..d32514d999 100644 --- a/lib/libcxx/include/__algorithm/copy_if.h +++ b/lib/libcxx/include/__algorithm/copy_if.h @@ -10,18 +10,11 @@ #define _LIBCPP___ALGORITHM_COPY_IF_H #include <__config> -#include <__algorithm/unwrap_iter.h> -#include <__iterator/iterator_traits.h> -#include <cstring> -#include <type_traits> #if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER) #pragma GCC system_header #endif -_LIBCPP_PUSH_MACROS -#include <__undef_macros> - _LIBCPP_BEGIN_NAMESPACE_STD template<class _InputIterator, class _OutputIterator, class _Predicate> @@ -43,6 +36,4 @@ copy_if(_InputIterator __first, _InputIterator __last, _LIBCPP_END_NAMESPACE_STD -_LIBCPP_POP_MACROS - #endif // _LIBCPP___ALGORITHM_COPY_IF_H diff --git a/lib/libcxx/include/__algorithm/copy_n.h b/lib/libcxx/include/__algorithm/copy_n.h index bbfeb8686f..cdcc0d50db 100644 --- a/lib/libcxx/include/__algorithm/copy_n.h +++ b/lib/libcxx/include/__algorithm/copy_n.h @@ -9,20 +9,15 @@ #ifndef _LIBCPP___ALGORITHM_COPY_N_H #define _LIBCPP___ALGORITHM_COPY_N_H -#include <__config> #include <__algorithm/copy.h> -#include <__algorithm/unwrap_iter.h> +#include <__config> #include <__iterator/iterator_traits.h> -#include <cstring> #include <type_traits> #if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER) #pragma GCC system_header #endif -_LIBCPP_PUSH_MACROS -#include <__undef_macros> - _LIBCPP_BEGIN_NAMESPACE_STD template<class _InputIterator, class _Size, class _OutputIterator> @@ -60,13 +55,12 @@ typename enable_if >::type copy_n(_InputIterator __first, _Size __orig_n, _OutputIterator __result) { + typedef typename iterator_traits<_InputIterator>::difference_type difference_type; typedef decltype(_VSTD::__convert_to_integral(__orig_n)) _IntegralSize; _IntegralSize __n = __orig_n; - return _VSTD::copy(__first, __first + __n, __result); + return _VSTD::copy(__first, __first + difference_type(__n), __result); } _LIBCPP_END_NAMESPACE_STD -_LIBCPP_POP_MACROS - #endif // _LIBCPP___ALGORITHM_COPY_N_H diff --git a/lib/libcxx/include/__algorithm/count.h b/lib/libcxx/include/__algorithm/count.h index 7f2d1954cd..81a2c186f8 100644 --- a/lib/libcxx/include/__algorithm/count.h +++ b/lib/libcxx/include/__algorithm/count.h @@ -17,9 +17,6 @@ #pragma GCC system_header #endif -_LIBCPP_PUSH_MACROS -#include <__undef_macros> - _LIBCPP_BEGIN_NAMESPACE_STD template <class _InputIterator, class _Tp> @@ -35,6 +32,4 @@ _LIBCPP_NODISCARD_EXT inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_C _LIBCPP_END_NAMESPACE_STD -_LIBCPP_POP_MACROS - #endif // _LIBCPP___ALGORITHM_COUNT_H diff --git a/lib/libcxx/include/__algorithm/count_if.h b/lib/libcxx/include/__algorithm/count_if.h index a5efffb926..00f5d671da 100644 --- a/lib/libcxx/include/__algorithm/count_if.h +++ b/lib/libcxx/include/__algorithm/count_if.h @@ -17,9 +17,6 @@ #pragma GCC system_header #endif -_LIBCPP_PUSH_MACROS -#include <__undef_macros> - _LIBCPP_BEGIN_NAMESPACE_STD template <class _InputIterator, class _Predicate> @@ -35,6 +32,4 @@ _LIBCPP_NODISCARD_EXT inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_C _LIBCPP_END_NAMESPACE_STD -_LIBCPP_POP_MACROS - #endif // _LIBCPP___ALGORITHM_COUNT_IF_H diff --git a/lib/libcxx/include/__algorithm/equal.h b/lib/libcxx/include/__algorithm/equal.h index bc67559819..4c9ad05ad6 100644 --- a/lib/libcxx/include/__algorithm/equal.h +++ b/lib/libcxx/include/__algorithm/equal.h @@ -10,18 +10,15 @@ #ifndef _LIBCPP___ALGORITHM_EQUAL_H #define _LIBCPP___ALGORITHM_EQUAL_H -#include <__config> #include <__algorithm/comp.h> +#include <__config> +#include <__iterator/distance.h> #include <__iterator/iterator_traits.h> -#include <iterator> // FIXME: replace with <__iterator/distance.h> when it lands #if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER) #pragma GCC system_header #endif -_LIBCPP_PUSH_MACROS -#include <__undef_macros> - _LIBCPP_BEGIN_NAMESPACE_STD template <class _InputIterator1, class _InputIterator2, class _BinaryPredicate> @@ -60,14 +57,14 @@ __equal(_RandomAccessIterator1 __first1, _RandomAccessIterator1 __last1, _Random if (_VSTD::distance(__first1, __last1) != _VSTD::distance(__first2, __last2)) return false; return _VSTD::equal<_RandomAccessIterator1, _RandomAccessIterator2, - typename add_lvalue_reference<_BinaryPredicate>::type>(__first1, __last1, __first2, __pred); + _BinaryPredicate&>(__first1, __last1, __first2, __pred); } template <class _InputIterator1, class _InputIterator2, class _BinaryPredicate> _LIBCPP_NODISCARD_EXT inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17 bool equal(_InputIterator1 __first1, _InputIterator1 __last1, _InputIterator2 __first2, _InputIterator2 __last2, _BinaryPredicate __pred) { - return _VSTD::__equal<typename add_lvalue_reference<_BinaryPredicate>::type>( + return _VSTD::__equal<_BinaryPredicate&>( __first1, __last1, __first2, __last2, __pred, typename iterator_traits<_InputIterator1>::iterator_category(), typename iterator_traits<_InputIterator2>::iterator_category()); } @@ -85,6 +82,4 @@ equal(_InputIterator1 __first1, _InputIterator1 __last1, _InputIterator2 __first _LIBCPP_END_NAMESPACE_STD -_LIBCPP_POP_MACROS - #endif // _LIBCPP___ALGORITHM_EQUAL_H diff --git a/lib/libcxx/include/__algorithm/equal_range.h b/lib/libcxx/include/__algorithm/equal_range.h index 9694dae950..e13f0bdd96 100644 --- a/lib/libcxx/include/__algorithm/equal_range.h +++ b/lib/libcxx/include/__algorithm/equal_range.h @@ -9,21 +9,18 @@ #ifndef _LIBCPP___ALGORITHM_EQUAL_RANGE_H #define _LIBCPP___ALGORITHM_EQUAL_RANGE_H -#include <__config> #include <__algorithm/comp.h> #include <__algorithm/comp_ref_type.h> #include <__algorithm/half_positive.h> #include <__algorithm/lower_bound.h> #include <__algorithm/upper_bound.h> +#include <__config> #include <iterator> #if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER) #pragma GCC system_header #endif -_LIBCPP_PUSH_MACROS -#include <__undef_macros> - _LIBCPP_BEGIN_NAMESPACE_STD template <class _Compare, class _ForwardIterator, class _Tp> @@ -82,6 +79,4 @@ equal_range(_ForwardIterator __first, _ForwardIterator __last, const _Tp& __valu _LIBCPP_END_NAMESPACE_STD -_LIBCPP_POP_MACROS - #endif // _LIBCPP___ALGORITHM_EQUAL_RANGE_H diff --git a/lib/libcxx/include/__algorithm/fill.h b/lib/libcxx/include/__algorithm/fill.h index 4fefe86536..0cb36b02c8 100644 --- a/lib/libcxx/include/__algorithm/fill.h +++ b/lib/libcxx/include/__algorithm/fill.h @@ -9,8 +9,8 @@ #ifndef _LIBCPP___ALGORITHM_FILL_H #define _LIBCPP___ALGORITHM_FILL_H -#include <__config> #include <__algorithm/fill_n.h> +#include <__config> #include <__iterator/iterator_traits.h> #include <type_traits> @@ -18,9 +18,6 @@ #pragma GCC system_header #endif -_LIBCPP_PUSH_MACROS -#include <__undef_macros> - _LIBCPP_BEGIN_NAMESPACE_STD template <class _ForwardIterator, class _Tp> @@ -50,6 +47,4 @@ fill(_ForwardIterator __first, _ForwardIterator __last, const _Tp& __value_) _LIBCPP_END_NAMESPACE_STD -_LIBCPP_POP_MACROS - #endif // _LIBCPP___ALGORITHM_FILL_H diff --git a/lib/libcxx/include/__algorithm/fill_n.h b/lib/libcxx/include/__algorithm/fill_n.h index 34a245edb5..857ac14157 100644 --- a/lib/libcxx/include/__algorithm/fill_n.h +++ b/lib/libcxx/include/__algorithm/fill_n.h @@ -17,9 +17,6 @@ #pragma GCC system_header #endif -_LIBCPP_PUSH_MACROS -#include <__undef_macros> - _LIBCPP_BEGIN_NAMESPACE_STD template <class _OutputIterator, class _Size, class _Tp> @@ -42,6 +39,4 @@ fill_n(_OutputIterator __first, _Size __n, const _Tp& __value_) _LIBCPP_END_NAMESPACE_STD -_LIBCPP_POP_MACROS - #endif // _LIBCPP___ALGORITHM_FILL_N_H diff --git a/lib/libcxx/include/__algorithm/find.h b/lib/libcxx/include/__algorithm/find.h index bc593dc542..2a6dfbe41a 100644 --- a/lib/libcxx/include/__algorithm/find.h +++ b/lib/libcxx/include/__algorithm/find.h @@ -16,9 +16,6 @@ #pragma GCC system_header #endif -_LIBCPP_PUSH_MACROS -#include <__undef_macros> - _LIBCPP_BEGIN_NAMESPACE_STD template <class _InputIterator, class _Tp> @@ -32,6 +29,4 @@ find(_InputIterator __first, _InputIterator __last, const _Tp& __value_) { _LIBCPP_END_NAMESPACE_STD -_LIBCPP_POP_MACROS - #endif // _LIBCPP___ALGORITHM_FIND_H diff --git a/lib/libcxx/include/__algorithm/find_end.h b/lib/libcxx/include/__algorithm/find_end.h index f4277f003a..dd0f7d7ac0 100644 --- a/lib/libcxx/include/__algorithm/find_end.h +++ b/lib/libcxx/include/__algorithm/find_end.h @@ -10,18 +10,14 @@ #ifndef _LIBCPP___ALGORITHM_FIND_END_OF_H #define _LIBCPP___ALGORITHM_FIND_END_OF_H -#include <__config> #include <__algorithm/comp.h> +#include <__config> #include <__iterator/iterator_traits.h> -#include <type_traits> #if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER) #pragma GCC system_header #endif -_LIBCPP_PUSH_MACROS -#include <__undef_macros> - _LIBCPP_BEGIN_NAMESPACE_STD template <class _BinaryPredicate, class _ForwardIterator1, class _ForwardIterator2> @@ -99,14 +95,16 @@ template <class _BinaryPredicate, class _RandomAccessIterator1, class _RandomAcc _LIBCPP_CONSTEXPR_AFTER_CXX11 _RandomAccessIterator1 __find_end( _RandomAccessIterator1 __first1, _RandomAccessIterator1 __last1, _RandomAccessIterator2 __first2, _RandomAccessIterator2 __last2, _BinaryPredicate __pred, random_access_iterator_tag, random_access_iterator_tag) { + typedef typename iterator_traits<_RandomAccessIterator1>::difference_type _D1; + typedef typename iterator_traits<_RandomAccessIterator2>::difference_type _D2; // Take advantage of knowing source and pattern lengths. Stop short when source is smaller than pattern - typename iterator_traits<_RandomAccessIterator2>::difference_type __len2 = __last2 - __first2; + _D2 __len2 = __last2 - __first2; if (__len2 == 0) return __last1; - typename iterator_traits<_RandomAccessIterator1>::difference_type __len1 = __last1 - __first1; + _D1 __len1 = __last1 - __first1; if (__len1 < __len2) return __last1; - const _RandomAccessIterator1 __s = __first1 + (__len2 - 1); // End of pattern match can't go before here + const _RandomAccessIterator1 __s = __first1 + _D1(__len2 - 1); // End of pattern match can't go before here _RandomAccessIterator1 __l1 = __last1; _RandomAccessIterator2 __l2 = __last2; --__l2; @@ -134,7 +132,7 @@ template <class _ForwardIterator1, class _ForwardIterator2, class _BinaryPredica _LIBCPP_NODISCARD_EXT inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17 _ForwardIterator1 find_end(_ForwardIterator1 __first1, _ForwardIterator1 __last1, _ForwardIterator2 __first2, _ForwardIterator2 __last2, _BinaryPredicate __pred) { - return _VSTD::__find_end<typename add_lvalue_reference<_BinaryPredicate>::type>( + return _VSTD::__find_end<_BinaryPredicate&>( __first1, __last1, __first2, __last2, __pred, typename iterator_traits<_ForwardIterator1>::iterator_category(), typename iterator_traits<_ForwardIterator2>::iterator_category()); } @@ -149,6 +147,4 @@ find_end(_ForwardIterator1 __first1, _ForwardIterator1 __last1, _ForwardIterator _LIBCPP_END_NAMESPACE_STD -_LIBCPP_POP_MACROS - #endif // _LIBCPP___ALGORITHM_FIND_END_OF_H diff --git a/lib/libcxx/include/__algorithm/find_first_of.h b/lib/libcxx/include/__algorithm/find_first_of.h index d956c8dda2..69354f6176 100644 --- a/lib/libcxx/include/__algorithm/find_first_of.h +++ b/lib/libcxx/include/__algorithm/find_first_of.h @@ -10,17 +10,14 @@ #ifndef _LIBCPP___ALGORITHM_FIND_FIRST_OF_H #define _LIBCPP___ALGORITHM_FIND_FIRST_OF_H -#include <__config> #include <__algorithm/comp.h> +#include <__config> #include <__iterator/iterator_traits.h> #if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER) #pragma GCC system_header #endif -_LIBCPP_PUSH_MACROS -#include <__undef_macros> - _LIBCPP_BEGIN_NAMESPACE_STD template <class _ForwardIterator1, class _ForwardIterator2, class _BinaryPredicate> @@ -52,6 +49,4 @@ _LIBCPP_NODISCARD_EXT inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_C _LIBCPP_END_NAMESPACE_STD -_LIBCPP_POP_MACROS - #endif // _LIBCPP___ALGORITHM_FIND_FIRST_OF_H diff --git a/lib/libcxx/include/__algorithm/find_if.h b/lib/libcxx/include/__algorithm/find_if.h index 456cc5b0a3..a94196a16a 100644 --- a/lib/libcxx/include/__algorithm/find_if.h +++ b/lib/libcxx/include/__algorithm/find_if.h @@ -16,9 +16,6 @@ #pragma GCC system_header #endif -_LIBCPP_PUSH_MACROS -#include <__undef_macros> - _LIBCPP_BEGIN_NAMESPACE_STD template <class _InputIterator, class _Predicate> @@ -32,6 +29,4 @@ find_if(_InputIterator __first, _InputIterator __last, _Predicate __pred) { _LIBCPP_END_NAMESPACE_STD -_LIBCPP_POP_MACROS - #endif // _LIBCPP___ALGORITHM_FIND_IF_H diff --git a/lib/libcxx/include/__algorithm/find_if_not.h b/lib/libcxx/include/__algorithm/find_if_not.h index d7d25160cc..e057db5efa 100644 --- a/lib/libcxx/include/__algorithm/find_if_not.h +++ b/lib/libcxx/include/__algorithm/find_if_not.h @@ -16,9 +16,6 @@ #pragma GCC system_header #endif -_LIBCPP_PUSH_MACROS -#include <__undef_macros> - _LIBCPP_BEGIN_NAMESPACE_STD template <class _InputIterator, class _Predicate> @@ -32,6 +29,4 @@ find_if_not(_InputIterator __first, _InputIterator __last, _Predicate __pred) { _LIBCPP_END_NAMESPACE_STD -_LIBCPP_POP_MACROS - #endif // _LIBCPP___ALGORITHM_FIND_IF_NOT_H diff --git a/lib/libcxx/include/__algorithm/for_each.h b/lib/libcxx/include/__algorithm/for_each.h index e71a36a1de..1612ffa5c0 100644 --- a/lib/libcxx/include/__algorithm/for_each.h +++ b/lib/libcxx/include/__algorithm/for_each.h @@ -16,9 +16,6 @@ #pragma GCC system_header #endif -_LIBCPP_PUSH_MACROS -#include <__undef_macros> - _LIBCPP_BEGIN_NAMESPACE_STD template <class _InputIterator, class _Function> @@ -32,6 +29,4 @@ inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17 _Function for_eac _LIBCPP_END_NAMESPACE_STD -_LIBCPP_POP_MACROS - #endif // _LIBCPP___ALGORITHM_FOR_EACH_H diff --git a/lib/libcxx/include/__algorithm/for_each_n.h b/lib/libcxx/include/__algorithm/for_each_n.h index 77f6c86214..00e3fb9c1d 100644 --- a/lib/libcxx/include/__algorithm/for_each_n.h +++ b/lib/libcxx/include/__algorithm/for_each_n.h @@ -17,9 +17,6 @@ #pragma GCC system_header #endif -_LIBCPP_PUSH_MACROS -#include <__undef_macros> - _LIBCPP_BEGIN_NAMESPACE_STD #if _LIBCPP_STD_VER > 14 @@ -42,6 +39,4 @@ inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17 _InputIterator fo _LIBCPP_END_NAMESPACE_STD -_LIBCPP_POP_MACROS - #endif // _LIBCPP___ALGORITHM_FOR_EACH_N_H diff --git a/lib/libcxx/include/__algorithm/generate.h b/lib/libcxx/include/__algorithm/generate.h index d3e1133e2b..10834cdb74 100644 --- a/lib/libcxx/include/__algorithm/generate.h +++ b/lib/libcxx/include/__algorithm/generate.h @@ -15,9 +15,6 @@ #pragma GCC system_header #endif -_LIBCPP_PUSH_MACROS -#include <__undef_macros> - _LIBCPP_BEGIN_NAMESPACE_STD template <class _ForwardIterator, class _Generator> @@ -31,6 +28,4 @@ generate(_ForwardIterator __first, _ForwardIterator __last, _Generator __gen) _LIBCPP_END_NAMESPACE_STD -_LIBCPP_POP_MACROS - #endif // _LIBCPP___ALGORITHM_GENERATE_H diff --git a/lib/libcxx/include/__algorithm/generate_n.h b/lib/libcxx/include/__algorithm/generate_n.h index c312598586..595007cdd3 100644 --- a/lib/libcxx/include/__algorithm/generate_n.h +++ b/lib/libcxx/include/__algorithm/generate_n.h @@ -16,9 +16,6 @@ #pragma GCC system_header #endif -_LIBCPP_PUSH_MACROS -#include <__undef_macros> - _LIBCPP_BEGIN_NAMESPACE_STD template <class _OutputIterator, class _Size, class _Generator> @@ -35,6 +32,4 @@ generate_n(_OutputIterator __first, _Size __orig_n, _Generator __gen) _LIBCPP_END_NAMESPACE_STD -_LIBCPP_POP_MACROS - #endif // _LIBCPP___ALGORITHM_GENERATE_N_H diff --git a/lib/libcxx/include/__algorithm/half_positive.h b/lib/libcxx/include/__algorithm/half_positive.h index b03efc495b..5d36ff5da9 100644 --- a/lib/libcxx/include/__algorithm/half_positive.h +++ b/lib/libcxx/include/__algorithm/half_positive.h @@ -16,9 +16,6 @@ #pragma GCC system_header #endif -_LIBCPP_PUSH_MACROS -#include <__undef_macros> - _LIBCPP_BEGIN_NAMESPACE_STD // Perform division by two quickly for positive integers (llvm.org/PR39129) @@ -49,6 +46,4 @@ __half_positive(_Tp __value) _LIBCPP_END_NAMESPACE_STD -_LIBCPP_POP_MACROS - #endif // _LIBCPP___ALGORITHM_HALF_POSITIVE_H diff --git a/lib/libcxx/include/__algorithm/in_in_out_result.h b/lib/libcxx/include/__algorithm/in_in_out_result.h new file mode 100644 index 0000000000..8d29b7b69b --- /dev/null +++ b/lib/libcxx/include/__algorithm/in_in_out_result.h @@ -0,0 +1,54 @@ +// -*- C++ -*- +//===----------------------------------------------------------------------===// +// +// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. +// See https://llvm.org/LICENSE.txt for license information. +// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception +// +//===----------------------------------------------------------------------===// + +#ifndef _LIBCPP___ALGORITHM_IN_IN_OUT_RESULT_H +#define _LIBCPP___ALGORITHM_IN_IN_OUT_RESULT_H + +#include <__concepts/convertible_to.h> +#include <__config> +#include <__utility/move.h> + +#if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER) +#pragma GCC system_header +#endif + +_LIBCPP_BEGIN_NAMESPACE_STD + +#if !defined(_LIBCPP_HAS_NO_CONCEPTS) && !defined(_LIBCPP_HAS_NO_INCOMPLETE_RANGES) + +namespace ranges { + +template <class _I1, class _I2, class _O1> +struct in_in_out_result { + [[no_unique_address]] _I1 in1; + [[no_unique_address]] _I2 in2; + [[no_unique_address]] _O1 out; + + template <class _II1, class _II2, class _OO1> + requires convertible_to<const _I1&, _II1> && convertible_to<const _I2&, _II2> && convertible_to<const _O1&, _OO1> + _LIBCPP_HIDE_FROM_ABI constexpr + operator in_in_out_result<_II1, _II2, _OO1>() const& { + return {in1, in2, out}; + } + + template <class _II1, class _II2, class _OO1> + requires convertible_to<_I1, _II1> && convertible_to<_I2, _II2> && convertible_to<_O1, _OO1> + _LIBCPP_HIDE_FROM_ABI constexpr + operator in_in_out_result<_II1, _II2, _OO1>() && { + return {_VSTD::move(in1), _VSTD::move(in2), _VSTD::move(out)}; + } +}; + +} // namespace ranges + +#endif // !defined(_LIBCPP_HAS_NO_CONCEPTS) && !defined(_LIBCPP_HAS_NO_INCOMPLETE_RANGES) + +_LIBCPP_END_NAMESPACE_STD + +#endif // _LIBCPP___ALGORITHM_IN_IN_OUT_RESULT_H diff --git a/lib/libcxx/include/__algorithm/in_in_result.h b/lib/libcxx/include/__algorithm/in_in_result.h new file mode 100644 index 0000000000..c8fe43d039 --- /dev/null +++ b/lib/libcxx/include/__algorithm/in_in_result.h @@ -0,0 +1,51 @@ +// -*- C++ -*- +//===----------------------------------------------------------------------===// +// +// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. +// See https://llvm.org/LICENSE.txt for license information. +// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception +// +//===----------------------------------------------------------------------===// + +#ifndef _LIBCPP___ALGORITHM_IN_IN_RESULT_H +#define _LIBCPP___ALGORITHM_IN_IN_RESULT_H + +#include <__concepts/convertible_to.h> +#include <__config> +#include <__utility/move.h> + +#if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER) +#pragma GCC system_header +#endif + +_LIBCPP_BEGIN_NAMESPACE_STD + +#if !defined(_LIBCPP_HAS_NO_CONCEPTS) + +namespace ranges { + +template <class _I1, class _I2> +struct in_in_result { + [[no_unique_address]] _I1 in1; + [[no_unique_address]] _I2 in2; + + template <class _II1, class _II2> + requires convertible_to<const _I1&, _II1> && convertible_to<const _I2&, _II2> + _LIBCPP_HIDE_FROM_ABI constexpr + operator in_in_result<_II1, _II2>() const & { + return {in1, in2}; + } + + template <class _II1, class _II2> + requires convertible_to<_I1, _II1> && convertible_to<_I2, _II2> + _LIBCPP_HIDE_FROM_ABI constexpr + operator in_in_result<_II1, _II2>() && { return {_VSTD::move(in1), _VSTD::move(in2)}; } +}; + +} // namespace ranges + +#endif // !defined(_LIBCPP_HAS_NO_CONCEPTS) + +_LIBCPP_END_NAMESPACE_STD + +#endif // _LIBCPP___ALGORITHM_IN_IN_RESULT_H diff --git a/lib/libcxx/include/__algorithm/in_out_result.h b/lib/libcxx/include/__algorithm/in_out_result.h new file mode 100644 index 0000000000..dcf72d08dd --- /dev/null +++ b/lib/libcxx/include/__algorithm/in_out_result.h @@ -0,0 +1,54 @@ +// -*- C++ -*- +//===----------------------------------------------------------------------===// +// +// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. +// See https://llvm.org/LICENSE.txt for license information. +// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception +// +//===----------------------------------------------------------------------===// + +#ifndef _LIBCPP___ALGORITHM_IN_OUT_RESULT_H +#define _LIBCPP___ALGORITHM_IN_OUT_RESULT_H + +#include <__concepts/convertible_to.h> +#include <__config> +#include <__utility/move.h> + +#if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER) +#pragma GCC system_header +#endif + +_LIBCPP_BEGIN_NAMESPACE_STD + +#if !defined(_LIBCPP_HAS_NO_CONCEPTS) && !defined(_LIBCPP_HAS_NO_INCOMPLETE_RANGES) + +namespace ranges { + +template<class _InputIterator, class _OutputIterator> +struct in_out_result { + [[no_unique_address]] _InputIterator in; + [[no_unique_address]] _OutputIterator out; + + template <class _InputIterator2, class _OutputIterator2> + requires convertible_to<const _InputIterator&, _InputIterator2> && convertible_to<const _OutputIterator&, + _OutputIterator2> + _LIBCPP_HIDE_FROM_ABI + constexpr operator in_out_result<_InputIterator2, _OutputIterator2>() const & { + return {in, out}; + } + + template <class _InputIterator2, class _OutputIterator2> + requires convertible_to<_InputIterator, _InputIterator2> && convertible_to<_OutputIterator, _OutputIterator2> + _LIBCPP_HIDE_FROM_ABI + constexpr operator in_out_result<_InputIterator2, _OutputIterator2>() && { + return {_VSTD::move(in), _VSTD::move(out)}; + } +}; + +} // namespace ranges + +#endif // !defined(_LIBCPP_HAS_NO_CONCEPTS) && !defined(_LIBCPP_HAS_NO_INCOMPLETE_RANGES) + +_LIBCPP_END_NAMESPACE_STD + +#endif // _LIBCPP___ALGORITHM_IN_OUT_RESULT_H diff --git a/lib/libcxx/include/__algorithm/includes.h b/lib/libcxx/include/__algorithm/includes.h index ff298a5111..9d0bc694c0 100644 --- a/lib/libcxx/include/__algorithm/includes.h +++ b/lib/libcxx/include/__algorithm/includes.h @@ -9,18 +9,15 @@ #ifndef _LIBCPP___ALGORITHM_INCLUDES_H #define _LIBCPP___ALGORITHM_INCLUDES_H -#include <__config> #include <__algorithm/comp.h> #include <__algorithm/comp_ref_type.h> +#include <__config> #include <__iterator/iterator_traits.h> #if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER) #pragma GCC system_header #endif -_LIBCPP_PUSH_MACROS -#include <__undef_macros> - _LIBCPP_BEGIN_NAMESPACE_STD template <class _Compare, class _InputIterator1, class _InputIterator2> @@ -62,6 +59,4 @@ includes(_InputIterator1 __first1, _InputIterator1 __last1, _InputIterator2 __fi _LIBCPP_END_NAMESPACE_STD -_LIBCPP_POP_MACROS - #endif // _LIBCPP___ALGORITHM_INCLUDES_H diff --git a/lib/libcxx/include/__algorithm/inplace_merge.h b/lib/libcxx/include/__algorithm/inplace_merge.h index c74633a74c..e6f1efc011 100644 --- a/lib/libcxx/include/__algorithm/inplace_merge.h +++ b/lib/libcxx/include/__algorithm/inplace_merge.h @@ -9,14 +9,14 @@ #ifndef _LIBCPP___ALGORITHM_INPLACE_MERGE_H #define _LIBCPP___ALGORITHM_INPLACE_MERGE_H -#include <__config> -#include <__algorithm/comp_ref_type.h> #include <__algorithm/comp.h> +#include <__algorithm/comp_ref_type.h> #include <__algorithm/lower_bound.h> #include <__algorithm/min.h> #include <__algorithm/move.h> #include <__algorithm/rotate.h> #include <__algorithm/upper_bound.h> +#include <__config> #include <__iterator/iterator_traits.h> #include <__utility/swap.h> #include <memory> diff --git a/lib/libcxx/include/__algorithm/is_heap.h b/lib/libcxx/include/__algorithm/is_heap.h index bc3682d471..925ba8bfb8 100644 --- a/lib/libcxx/include/__algorithm/is_heap.h +++ b/lib/libcxx/include/__algorithm/is_heap.h @@ -9,18 +9,16 @@ #ifndef _LIBCPP___ALGORITHM_IS_HEAP_H #define _LIBCPP___ALGORITHM_IS_HEAP_H -#include <__config> #include <__algorithm/comp.h> +#include <__algorithm/comp_ref_type.h> #include <__algorithm/is_heap_until.h> +#include <__config> #include <__iterator/iterator_traits.h> #if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER) #pragma GCC system_header #endif -_LIBCPP_PUSH_MACROS -#include <__undef_macros> - _LIBCPP_BEGIN_NAMESPACE_STD template <class _RandomAccessIterator, class _Compare> @@ -29,7 +27,8 @@ _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17 bool is_heap(_RandomAccessIterator __first, _RandomAccessIterator __last, _Compare __comp) { - return _VSTD::is_heap_until(__first, __last, __comp) == __last; + typedef typename __comp_ref_type<_Compare>::type _Comp_ref; + return _VSTD::__is_heap_until<_Comp_ref>(__first, __last, __comp) == __last; } template<class _RandomAccessIterator> @@ -43,6 +42,4 @@ is_heap(_RandomAccessIterator __first, _RandomAccessIterator __last) _LIBCPP_END_NAMESPACE_STD -_LIBCPP_POP_MACROS - #endif // _LIBCPP___ALGORITHM_IS_HEAP_H diff --git a/lib/libcxx/include/__algorithm/is_heap_until.h b/lib/libcxx/include/__algorithm/is_heap_until.h index 8c52edb7d4..aa23b6d039 100644 --- a/lib/libcxx/include/__algorithm/is_heap_until.h +++ b/lib/libcxx/include/__algorithm/is_heap_until.h @@ -9,22 +9,20 @@ #ifndef _LIBCPP___ALGORITHM_IS_HEAP_UNTIL_H #define _LIBCPP___ALGORITHM_IS_HEAP_UNTIL_H -#include <__config> #include <__algorithm/comp.h> +#include <__algorithm/comp_ref_type.h> +#include <__config> #include <__iterator/iterator_traits.h> #if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER) #pragma GCC system_header #endif -_LIBCPP_PUSH_MACROS -#include <__undef_macros> - _LIBCPP_BEGIN_NAMESPACE_STD -template <class _RandomAccessIterator, class _Compare> -_LIBCPP_NODISCARD_EXT _LIBCPP_CONSTEXPR_AFTER_CXX17 _RandomAccessIterator -is_heap_until(_RandomAccessIterator __first, _RandomAccessIterator __last, _Compare __comp) +template <class _Compare, class _RandomAccessIterator> +_LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_AFTER_CXX17 _RandomAccessIterator +__is_heap_until(_RandomAccessIterator __first, _RandomAccessIterator __last, _Compare __comp) { typedef typename iterator_traits<_RandomAccessIterator>::difference_type difference_type; difference_type __len = __last - __first; @@ -49,17 +47,21 @@ is_heap_until(_RandomAccessIterator __first, _RandomAccessIterator __last, _Comp return __last; } +template <class _RandomAccessIterator, class _Compare> +_LIBCPP_NODISCARD_EXT inline _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_AFTER_CXX17 _RandomAccessIterator +is_heap_until(_RandomAccessIterator __first, _RandomAccessIterator __last, _Compare __comp) +{ + typedef typename __comp_ref_type<_Compare>::type _Comp_ref; + return _VSTD::__is_heap_until<_Comp_ref>(__first, __last, __comp); +} + template<class _RandomAccessIterator> -_LIBCPP_NODISCARD_EXT inline -_LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17 -_RandomAccessIterator +_LIBCPP_NODISCARD_EXT inline _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_AFTER_CXX17 _RandomAccessIterator is_heap_until(_RandomAccessIterator __first, _RandomAccessIterator __last) { - return _VSTD::is_heap_until(__first, __last, __less<typename iterator_traits<_RandomAccessIterator>::value_type>()); + return _VSTD::__is_heap_until(__first, __last, __less<typename iterator_traits<_RandomAccessIterator>::value_type>()); } _LIBCPP_END_NAMESPACE_STD -_LIBCPP_POP_MACROS - #endif // _LIBCPP___ALGORITHM_IS_HEAP_UNTIL_H diff --git a/lib/libcxx/include/__algorithm/is_partitioned.h b/lib/libcxx/include/__algorithm/is_partitioned.h index 43de6650cb..e5b2214aa0 100644 --- a/lib/libcxx/include/__algorithm/is_partitioned.h +++ b/lib/libcxx/include/__algorithm/is_partitioned.h @@ -15,9 +15,6 @@ #pragma GCC system_header #endif -_LIBCPP_PUSH_MACROS -#include <__undef_macros> - _LIBCPP_BEGIN_NAMESPACE_STD template <class _InputIterator, class _Predicate> @@ -38,6 +35,4 @@ is_partitioned(_InputIterator __first, _InputIterator __last, _Predicate __pred) _LIBCPP_END_NAMESPACE_STD -_LIBCPP_POP_MACROS - #endif // _LIBCPP___ALGORITHM_IS_PARTITIONED_H diff --git a/lib/libcxx/include/__algorithm/is_permutation.h b/lib/libcxx/include/__algorithm/is_permutation.h index 0545eb7637..344aa763ad 100644 --- a/lib/libcxx/include/__algorithm/is_permutation.h +++ b/lib/libcxx/include/__algorithm/is_permutation.h @@ -12,17 +12,14 @@ #include <__algorithm/comp.h> #include <__config> +#include <__iterator/distance.h> #include <__iterator/iterator_traits.h> #include <__iterator/next.h> -#include <iterator> // FIXME: replace with <__iterator/distance.h> when it lands #if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER) #pragma GCC system_header #endif -_LIBCPP_PUSH_MACROS -#include <__undef_macros> - _LIBCPP_BEGIN_NAMESPACE_STD template <class _ForwardIterator1, class _ForwardIterator2, class _BinaryPredicate> @@ -136,15 +133,14 @@ _LIBCPP_CONSTEXPR_AFTER_CXX17 bool __is_permutation(_RandomAccessIterator1 __fir if (_VSTD::distance(__first1, __last1) != _VSTD::distance(__first2, __last2)) return false; return _VSTD::is_permutation<_RandomAccessIterator1, _RandomAccessIterator2, - typename add_lvalue_reference<_BinaryPredicate>::type>(__first1, __last1, __first2, - __pred); + _BinaryPredicate&>(__first1, __last1, __first2, __pred); } template <class _ForwardIterator1, class _ForwardIterator2, class _BinaryPredicate> _LIBCPP_NODISCARD_EXT inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17 bool is_permutation(_ForwardIterator1 __first1, _ForwardIterator1 __last1, _ForwardIterator2 __first2, _ForwardIterator2 __last2, _BinaryPredicate __pred) { - return _VSTD::__is_permutation<typename add_lvalue_reference<_BinaryPredicate>::type>( + return _VSTD::__is_permutation<_BinaryPredicate&>( __first1, __last1, __first2, __last2, __pred, typename iterator_traits<_ForwardIterator1>::iterator_category(), typename iterator_traits<_ForwardIterator2>::iterator_category()); } @@ -163,6 +159,4 @@ is_permutation(_ForwardIterator1 __first1, _ForwardIterator1 __last1, _ForwardIt _LIBCPP_END_NAMESPACE_STD -_LIBCPP_POP_MACROS - #endif // _LIBCPP___ALGORITHM_IS_PERMUTATION_H diff --git a/lib/libcxx/include/__algorithm/is_sorted.h b/lib/libcxx/include/__algorithm/is_sorted.h index 30d8da0499..57953295a8 100644 --- a/lib/libcxx/include/__algorithm/is_sorted.h +++ b/lib/libcxx/include/__algorithm/is_sorted.h @@ -10,6 +10,7 @@ #define _LIBCPP___ALGORITHM_IS_SORTED_H #include <__algorithm/comp.h> +#include <__algorithm/comp_ref_type.h> #include <__algorithm/is_sorted_until.h> #include <__config> #include <__iterator/iterator_traits.h> @@ -18,9 +19,6 @@ #pragma GCC system_header #endif -_LIBCPP_PUSH_MACROS -#include <__undef_macros> - _LIBCPP_BEGIN_NAMESPACE_STD template <class _ForwardIterator, class _Compare> @@ -29,7 +27,8 @@ _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17 bool is_sorted(_ForwardIterator __first, _ForwardIterator __last, _Compare __comp) { - return _VSTD::is_sorted_until(__first, __last, __comp) == __last; + typedef typename __comp_ref_type<_Compare>::type _Comp_ref; + return _VSTD::__is_sorted_until<_Comp_ref>(__first, __last, __comp) == __last; } template<class _ForwardIterator> @@ -43,6 +42,4 @@ is_sorted(_ForwardIterator __first, _ForwardIterator __last) _LIBCPP_END_NAMESPACE_STD -_LIBCPP_POP_MACROS - #endif // _LIBCPP___ALGORITHM_IS_SORTED_H diff --git a/lib/libcxx/include/__algorithm/is_sorted_until.h b/lib/libcxx/include/__algorithm/is_sorted_until.h index a914b5a566..57cad47761 100644 --- a/lib/libcxx/include/__algorithm/is_sorted_until.h +++ b/lib/libcxx/include/__algorithm/is_sorted_until.h @@ -9,22 +9,20 @@ #ifndef _LIBCPP___ALGORITHM_IS_SORTED_UNTIL_H #define _LIBCPP___ALGORITHM_IS_SORTED_UNTIL_H -#include <__config> #include <__algorithm/comp.h> +#include <__algorithm/comp_ref_type.h> +#include <__config> #include <__iterator/iterator_traits.h> #if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER) #pragma GCC system_header #endif -_LIBCPP_PUSH_MACROS -#include <__undef_macros> - _LIBCPP_BEGIN_NAMESPACE_STD -template <class _ForwardIterator, class _Compare> -_LIBCPP_NODISCARD_EXT _LIBCPP_CONSTEXPR_AFTER_CXX17 _ForwardIterator -is_sorted_until(_ForwardIterator __first, _ForwardIterator __last, _Compare __comp) +template <class _Compare, class _ForwardIterator> +_LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_AFTER_CXX17 _ForwardIterator +__is_sorted_until(_ForwardIterator __first, _ForwardIterator __last, _Compare __comp) { if (__first != __last) { @@ -39,10 +37,16 @@ is_sorted_until(_ForwardIterator __first, _ForwardIterator __last, _Compare __co return __last; } +template <class _ForwardIterator, class _Compare> +_LIBCPP_NODISCARD_EXT inline _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_AFTER_CXX17 _ForwardIterator +is_sorted_until(_ForwardIterator __first, _ForwardIterator __last, _Compare __comp) +{ + typedef typename __comp_ref_type<_Compare>::type _Comp_ref; + return _VSTD::__is_sorted_until<_Comp_ref>(__first, __last, __comp); +} + template<class _ForwardIterator> -_LIBCPP_NODISCARD_EXT inline -_LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17 -_ForwardIterator +_LIBCPP_NODISCARD_EXT inline _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_AFTER_CXX17 _ForwardIterator is_sorted_until(_ForwardIterator __first, _ForwardIterator __last) { return _VSTD::is_sorted_until(__first, __last, __less<typename iterator_traits<_ForwardIterator>::value_type>()); @@ -50,6 +54,4 @@ is_sorted_until(_ForwardIterator __first, _ForwardIterator __last) _LIBCPP_END_NAMESPACE_STD -_LIBCPP_POP_MACROS - #endif // _LIBCPP___ALGORITHM_IS_SORTED_UNTIL_H diff --git a/lib/libcxx/include/__algorithm/iter_swap.h b/lib/libcxx/include/__algorithm/iter_swap.h index b63bce62cc..9f7d0d7763 100644 --- a/lib/libcxx/include/__algorithm/iter_swap.h +++ b/lib/libcxx/include/__algorithm/iter_swap.h @@ -17,9 +17,6 @@ #pragma GCC system_header #endif -_LIBCPP_PUSH_MACROS -#include <__undef_macros> - _LIBCPP_BEGIN_NAMESPACE_STD template <class _ForwardIterator1, class _ForwardIterator2> @@ -32,6 +29,4 @@ inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17 void iter_swap(_F _LIBCPP_END_NAMESPACE_STD -_LIBCPP_POP_MACROS - #endif // _LIBCPP___ALGORITHM_ITER_SWAP_H diff --git a/lib/libcxx/include/__algorithm/lexicographical_compare.h b/lib/libcxx/include/__algorithm/lexicographical_compare.h index 6e4a90bdc0..55a1da6201 100644 --- a/lib/libcxx/include/__algorithm/lexicographical_compare.h +++ b/lib/libcxx/include/__algorithm/lexicographical_compare.h @@ -9,18 +9,15 @@ #ifndef _LIBCPP___ALGORITHM_LEXICOGRAPHICAL_COMPARE_H #define _LIBCPP___ALGORITHM_LEXICOGRAPHICAL_COMPARE_H -#include <__config> #include <__algorithm/comp.h> #include <__algorithm/comp_ref_type.h> +#include <__config> #include <__iterator/iterator_traits.h> #if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER) #pragma GCC system_header #endif -_LIBCPP_PUSH_MACROS -#include <__undef_macros> - _LIBCPP_BEGIN_NAMESPACE_STD template <class _Compare, class _InputIterator1, class _InputIterator2> @@ -63,6 +60,4 @@ lexicographical_compare(_InputIterator1 __first1, _InputIterator1 __last1, _LIBCPP_END_NAMESPACE_STD -_LIBCPP_POP_MACROS - #endif // _LIBCPP___ALGORITHM_LEXICOGRAPHICAL_COMPARE_H diff --git a/lib/libcxx/include/__algorithm/lower_bound.h b/lib/libcxx/include/__algorithm/lower_bound.h index 1448c89633..663a0b1622 100644 --- a/lib/libcxx/include/__algorithm/lower_bound.h +++ b/lib/libcxx/include/__algorithm/lower_bound.h @@ -9,18 +9,15 @@ #ifndef _LIBCPP___ALGORITHM_LOWER_BOUND_H #define _LIBCPP___ALGORITHM_LOWER_BOUND_H -#include <__config> #include <__algorithm/comp.h> #include <__algorithm/half_positive.h> +#include <__config> #include <iterator> #if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER) #pragma GCC system_header #endif -_LIBCPP_PUSH_MACROS -#include <__undef_macros> - _LIBCPP_BEGIN_NAMESPACE_STD template <class _Compare, class _ForwardIterator, class _Tp> @@ -51,8 +48,7 @@ _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17 _ForwardIterator lower_bound(_ForwardIterator __first, _ForwardIterator __last, const _Tp& __value_, _Compare __comp) { - typedef typename add_lvalue_reference<_Compare>::type _Comp_ref; - return _VSTD::__lower_bound<_Comp_ref>(__first, __last, __value_, __comp); + return _VSTD::__lower_bound<_Compare&>(__first, __last, __value_, __comp); } template <class _ForwardIterator, class _Tp> @@ -67,6 +63,4 @@ lower_bound(_ForwardIterator __first, _ForwardIterator __last, const _Tp& __valu _LIBCPP_END_NAMESPACE_STD -_LIBCPP_POP_MACROS - #endif // _LIBCPP___ALGORITHM_LOWER_BOUND_H diff --git a/lib/libcxx/include/__algorithm/make_heap.h b/lib/libcxx/include/__algorithm/make_heap.h index eca4013cbd..f489addaf5 100644 --- a/lib/libcxx/include/__algorithm/make_heap.h +++ b/lib/libcxx/include/__algorithm/make_heap.h @@ -9,19 +9,16 @@ #ifndef _LIBCPP___ALGORITHM_MAKE_HEAP_H #define _LIBCPP___ALGORITHM_MAKE_HEAP_H -#include <__config> #include <__algorithm/comp.h> #include <__algorithm/comp_ref_type.h> #include <__algorithm/sift_down.h> +#include <__config> #include <__iterator/iterator_traits.h> #if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER) #pragma GCC system_header #endif -_LIBCPP_PUSH_MACROS -#include <__undef_macros> - _LIBCPP_BEGIN_NAMESPACE_STD template <class _Compare, class _RandomAccessIterator> @@ -35,7 +32,7 @@ __make_heap(_RandomAccessIterator __first, _RandomAccessIterator __last, _Compar // start from the first parent, there is no need to consider children for (difference_type __start = (__n - 2) / 2; __start >= 0; --__start) { - _VSTD::__sift_down<_Compare>(__first, __last, __comp, __n, __first + __start); + _VSTD::__sift_down<_Compare>(__first, __comp, __n, __first + __start); } } } @@ -59,6 +56,4 @@ make_heap(_RandomAccessIterator __first, _RandomAccessIterator __last) _LIBCPP_END_NAMESPACE_STD -_LIBCPP_POP_MACROS - #endif // _LIBCPP___ALGORITHM_MAKE_HEAP_H diff --git a/lib/libcxx/include/__algorithm/max.h b/lib/libcxx/include/__algorithm/max.h index 2fa97cad87..0bbc971e0a 100644 --- a/lib/libcxx/include/__algorithm/max.h +++ b/lib/libcxx/include/__algorithm/max.h @@ -9,9 +9,10 @@ #ifndef _LIBCPP___ALGORITHM_MAX_H #define _LIBCPP___ALGORITHM_MAX_H -#include <__config> #include <__algorithm/comp.h> +#include <__algorithm/comp_ref_type.h> #include <__algorithm/max_element.h> +#include <__config> #include <initializer_list> #if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER) @@ -49,7 +50,8 @@ _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX11 _Tp max(initializer_list<_Tp> __t, _Compare __comp) { - return *_VSTD::max_element(__t.begin(), __t.end(), __comp); + typedef typename __comp_ref_type<_Compare>::type _Comp_ref; + return *_VSTD::__max_element<_Comp_ref>(__t.begin(), __t.end(), __comp); } template<class _Tp> diff --git a/lib/libcxx/include/__algorithm/max_element.h b/lib/libcxx/include/__algorithm/max_element.h index b93b67eacf..db29372605 100644 --- a/lib/libcxx/include/__algorithm/max_element.h +++ b/lib/libcxx/include/__algorithm/max_element.h @@ -9,24 +9,20 @@ #ifndef _LIBCPP___ALGORITHM_MAX_ELEMENT_H #define _LIBCPP___ALGORITHM_MAX_ELEMENT_H -#include <__config> #include <__algorithm/comp.h> +#include <__algorithm/comp_ref_type.h> +#include <__config> #include <__iterator/iterator_traits.h> #if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER) #pragma GCC system_header #endif -_LIBCPP_PUSH_MACROS -#include <__undef_macros> - _LIBCPP_BEGIN_NAMESPACE_STD -template <class _ForwardIterator, class _Compare> -_LIBCPP_NODISCARD_EXT inline -_LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX11 -_ForwardIterator -max_element(_ForwardIterator __first, _ForwardIterator __last, _Compare __comp) +template <class _Compare, class _ForwardIterator> +inline _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_AFTER_CXX11 _ForwardIterator +__max_element(_ForwardIterator __first, _ForwardIterator __last, _Compare __comp) { static_assert(__is_cpp17_forward_iterator<_ForwardIterator>::value, "std::max_element requires a ForwardIterator"); @@ -40,11 +36,17 @@ max_element(_ForwardIterator __first, _ForwardIterator __last, _Compare __comp) return __first; } +template <class _ForwardIterator, class _Compare> +_LIBCPP_NODISCARD_EXT inline _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_AFTER_CXX11 _ForwardIterator +max_element(_ForwardIterator __first, _ForwardIterator __last, _Compare __comp) +{ + typedef typename __comp_ref_type<_Compare>::type _Comp_ref; + return _VSTD::__max_element<_Comp_ref>(__first, __last, __comp); +} + template <class _ForwardIterator> -_LIBCPP_NODISCARD_EXT inline -_LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX11 -_ForwardIterator +_LIBCPP_NODISCARD_EXT inline _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_AFTER_CXX11 _ForwardIterator max_element(_ForwardIterator __first, _ForwardIterator __last) { return _VSTD::max_element(__first, __last, @@ -53,6 +55,4 @@ max_element(_ForwardIterator __first, _ForwardIterator __last) _LIBCPP_END_NAMESPACE_STD -_LIBCPP_POP_MACROS - #endif // _LIBCPP___ALGORITHM_MAX_ELEMENT_H diff --git a/lib/libcxx/include/__algorithm/merge.h b/lib/libcxx/include/__algorithm/merge.h index ea53ad68f7..9182649377 100644 --- a/lib/libcxx/include/__algorithm/merge.h +++ b/lib/libcxx/include/__algorithm/merge.h @@ -9,19 +9,16 @@ #ifndef _LIBCPP___ALGORITHM_MERGE_H #define _LIBCPP___ALGORITHM_MERGE_H -#include <__config> #include <__algorithm/comp.h> #include <__algorithm/comp_ref_type.h> #include <__algorithm/copy.h> +#include <__config> #include <__iterator/iterator_traits.h> #if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER) #pragma GCC system_header #endif -_LIBCPP_PUSH_MACROS -#include <__undef_macros> - _LIBCPP_BEGIN_NAMESPACE_STD template <class _Compare, class _InputIterator1, class _InputIterator2, class _OutputIterator> @@ -71,6 +68,4 @@ merge(_InputIterator1 __first1, _InputIterator1 __last1, _LIBCPP_END_NAMESPACE_STD -_LIBCPP_POP_MACROS - #endif // _LIBCPP___ALGORITHM_MERGE_H diff --git a/lib/libcxx/include/__algorithm/min.h b/lib/libcxx/include/__algorithm/min.h index 9fea7f70a2..ed2d3b8782 100644 --- a/lib/libcxx/include/__algorithm/min.h +++ b/lib/libcxx/include/__algorithm/min.h @@ -9,9 +9,10 @@ #ifndef _LIBCPP___ALGORITHM_MIN_H #define _LIBCPP___ALGORITHM_MIN_H -#include <__config> #include <__algorithm/comp.h> +#include <__algorithm/comp_ref_type.h> #include <__algorithm/min_element.h> +#include <__config> #include <initializer_list> #if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER) @@ -49,7 +50,8 @@ _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX11 _Tp min(initializer_list<_Tp> __t, _Compare __comp) { - return *_VSTD::min_element(__t.begin(), __t.end(), __comp); + typedef typename __comp_ref_type<_Compare>::type _Comp_ref; + return *_VSTD::__min_element<_Comp_ref>(__t.begin(), __t.end(), __comp); } template<class _Tp> diff --git a/lib/libcxx/include/__algorithm/min_element.h b/lib/libcxx/include/__algorithm/min_element.h index 6bff140e5d..407c7f9333 100644 --- a/lib/libcxx/include/__algorithm/min_element.h +++ b/lib/libcxx/include/__algorithm/min_element.h @@ -9,24 +9,20 @@ #ifndef _LIBCPP___ALGORITHM_MIN_ELEMENT_H #define _LIBCPP___ALGORITHM_MIN_ELEMENT_H -#include <__config> #include <__algorithm/comp.h> +#include <__algorithm/comp_ref_type.h> +#include <__config> #include <__iterator/iterator_traits.h> #if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER) #pragma GCC system_header #endif -_LIBCPP_PUSH_MACROS -#include <__undef_macros> - _LIBCPP_BEGIN_NAMESPACE_STD -template <class _ForwardIterator, class _Compare> -_LIBCPP_NODISCARD_EXT inline -_LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX11 -_ForwardIterator -min_element(_ForwardIterator __first, _ForwardIterator __last, _Compare __comp) +template <class _Compare, class _ForwardIterator> +inline _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_AFTER_CXX11 _ForwardIterator +__min_element(_ForwardIterator __first, _ForwardIterator __last, _Compare __comp) { static_assert(__is_cpp17_forward_iterator<_ForwardIterator>::value, "std::min_element requires a ForwardIterator"); @@ -40,10 +36,16 @@ min_element(_ForwardIterator __first, _ForwardIterator __last, _Compare __comp) return __first; } +template <class _ForwardIterator, class _Compare> +_LIBCPP_NODISCARD_EXT inline _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_AFTER_CXX11 _ForwardIterator +min_element(_ForwardIterator __first, _ForwardIterator __last, _Compare __comp) +{ + typedef typename __comp_ref_type<_Compare>::type _Comp_ref; + return _VSTD::__min_element<_Comp_ref>(__first, __last, __comp); +} + template <class _ForwardIterator> -_LIBCPP_NODISCARD_EXT inline -_LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX11 -_ForwardIterator +_LIBCPP_NODISCARD_EXT inline _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_AFTER_CXX11 _ForwardIterator min_element(_ForwardIterator __first, _ForwardIterator __last) { return _VSTD::min_element(__first, __last, @@ -52,6 +54,4 @@ min_element(_ForwardIterator __first, _ForwardIterator __last) _LIBCPP_END_NAMESPACE_STD -_LIBCPP_POP_MACROS - #endif // _LIBCPP___ALGORITHM_MIN_ELEMENT_H diff --git a/lib/libcxx/include/__algorithm/minmax.h b/lib/libcxx/include/__algorithm/minmax.h index 63753f2fec..0bf88a70b8 100644 --- a/lib/libcxx/include/__algorithm/minmax.h +++ b/lib/libcxx/include/__algorithm/minmax.h @@ -9,19 +9,15 @@ #ifndef _LIBCPP___ALGORITHM_MINMAX_H #define _LIBCPP___ALGORITHM_MINMAX_H -#include <__config> #include <__algorithm/comp.h> +#include <__config> #include <initializer_list> #include <utility> - #if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER) #pragma GCC system_header #endif -_LIBCPP_PUSH_MACROS -#include <__undef_macros> - _LIBCPP_BEGIN_NAMESPACE_STD template<class _Tp, class _Compare> @@ -96,6 +92,4 @@ minmax(initializer_list<_Tp> __t) _LIBCPP_END_NAMESPACE_STD -_LIBCPP_POP_MACROS - #endif // _LIBCPP___ALGORITHM_MINMAX_H diff --git a/lib/libcxx/include/__algorithm/minmax_element.h b/lib/libcxx/include/__algorithm/minmax_element.h index 1eba006de9..5d76860384 100644 --- a/lib/libcxx/include/__algorithm/minmax_element.h +++ b/lib/libcxx/include/__algorithm/minmax_element.h @@ -9,8 +9,8 @@ #ifndef _LIBCPP___ALGORITHM_MINMAX_ELEMENT_H #define _LIBCPP___ALGORITHM_MINMAX_ELEMENT_H -#include <__config> #include <__algorithm/comp.h> +#include <__config> #include <__iterator/iterator_traits.h> #include <utility> @@ -18,9 +18,6 @@ #pragma GCC system_header #endif -_LIBCPP_PUSH_MACROS -#include <__undef_macros> - _LIBCPP_BEGIN_NAMESPACE_STD template <class _ForwardIterator, class _Compare> @@ -85,6 +82,4 @@ minmax_element(_ForwardIterator __first, _ForwardIterator __last) _LIBCPP_END_NAMESPACE_STD -_LIBCPP_POP_MACROS - #endif // _LIBCPP___ALGORITHM_MINMAX_ELEMENT_H diff --git a/lib/libcxx/include/__algorithm/mismatch.h b/lib/libcxx/include/__algorithm/mismatch.h index fdd2bc8c09..230ade03df 100644 --- a/lib/libcxx/include/__algorithm/mismatch.h +++ b/lib/libcxx/include/__algorithm/mismatch.h @@ -10,8 +10,8 @@ #ifndef _LIBCPP___ALGORITHM_MISMATCH_H #define _LIBCPP___ALGORITHM_MISMATCH_H -#include <__config> #include <__algorithm/comp.h> +#include <__config> #include <__iterator/iterator_traits.h> #include <utility> @@ -19,9 +19,6 @@ #pragma GCC system_header #endif -_LIBCPP_PUSH_MACROS -#include <__undef_macros> - _LIBCPP_BEGIN_NAMESPACE_STD template <class _InputIterator1, class _InputIterator2, class _BinaryPredicate> @@ -67,6 +64,4 @@ _LIBCPP_NODISCARD_EXT inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_END_NAMESPACE_STD -_LIBCPP_POP_MACROS - #endif // _LIBCPP___ALGORITHM_MISMATCH_H diff --git a/lib/libcxx/include/__algorithm/move.h b/lib/libcxx/include/__algorithm/move.h index f5fc74854f..fa118f4716 100644 --- a/lib/libcxx/include/__algorithm/move.h +++ b/lib/libcxx/include/__algorithm/move.h @@ -9,20 +9,17 @@ #ifndef _LIBCPP___ALGORITHM_MOVE_H #define _LIBCPP___ALGORITHM_MOVE_H -#include <__config> #include <__algorithm/unwrap_iter.h> +#include <__config> #include <__utility/move.h> #include <cstring> -#include <utility> #include <type_traits> +#include <utility> #if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER) #pragma GCC system_header #endif -_LIBCPP_PUSH_MACROS -#include <__undef_macros> - _LIBCPP_BEGIN_NAMESPACE_STD // move @@ -78,6 +75,4 @@ move(_InputIterator __first, _InputIterator __last, _OutputIterator __result) _LIBCPP_END_NAMESPACE_STD -_LIBCPP_POP_MACROS - #endif // _LIBCPP___ALGORITHM_MOVE_H diff --git a/lib/libcxx/include/__algorithm/move_backward.h b/lib/libcxx/include/__algorithm/move_backward.h index 1c93b98197..a4e3828b60 100644 --- a/lib/libcxx/include/__algorithm/move_backward.h +++ b/lib/libcxx/include/__algorithm/move_backward.h @@ -9,19 +9,16 @@ #ifndef _LIBCPP___ALGORITHM_MOVE_BACKWARD_H #define _LIBCPP___ALGORITHM_MOVE_BACKWARD_H -#include <__config> #include <__algorithm/unwrap_iter.h> +#include <__config> #include <cstring> -#include <utility> #include <type_traits> +#include <utility> #if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER) #pragma GCC system_header #endif -_LIBCPP_PUSH_MACROS -#include <__undef_macros> - _LIBCPP_BEGIN_NAMESPACE_STD template <class _InputIterator, class _OutputIterator> @@ -79,6 +76,4 @@ move_backward(_BidirectionalIterator1 __first, _BidirectionalIterator1 __last, _LIBCPP_END_NAMESPACE_STD -_LIBCPP_POP_MACROS - #endif // _LIBCPP___ALGORITHM_MOVE_BACKWARD_H diff --git a/lib/libcxx/include/__algorithm/next_permutation.h b/lib/libcxx/include/__algorithm/next_permutation.h index a337e5efa0..eb81cceb7b 100644 --- a/lib/libcxx/include/__algorithm/next_permutation.h +++ b/lib/libcxx/include/__algorithm/next_permutation.h @@ -9,10 +9,10 @@ #ifndef _LIBCPP___ALGORITHM_NEXT_PERMUTATION_H #define _LIBCPP___ALGORITHM_NEXT_PERMUTATION_H -#include <__config> #include <__algorithm/comp.h> #include <__algorithm/comp_ref_type.h> #include <__algorithm/reverse.h> +#include <__config> #include <__iterator/iterator_traits.h> #include <__utility/swap.h> @@ -20,9 +20,6 @@ #pragma GCC system_header #endif -_LIBCPP_PUSH_MACROS -#include <__undef_macros> - _LIBCPP_BEGIN_NAMESPACE_STD template <class _Compare, class _BidirectionalIterator> @@ -72,6 +69,4 @@ next_permutation(_BidirectionalIterator __first, _BidirectionalIterator __last) _LIBCPP_END_NAMESPACE_STD -_LIBCPP_POP_MACROS - #endif // _LIBCPP___ALGORITHM_NEXT_PERMUTATION_H diff --git a/lib/libcxx/include/__algorithm/none_of.h b/lib/libcxx/include/__algorithm/none_of.h index 285691520c..10339e2418 100644 --- a/lib/libcxx/include/__algorithm/none_of.h +++ b/lib/libcxx/include/__algorithm/none_of.h @@ -16,9 +16,6 @@ #pragma GCC system_header #endif -_LIBCPP_PUSH_MACROS -#include <__undef_macros> - _LIBCPP_BEGIN_NAMESPACE_STD template <class _InputIterator, class _Predicate> @@ -32,6 +29,4 @@ none_of(_InputIterator __first, _InputIterator __last, _Predicate __pred) { _LIBCPP_END_NAMESPACE_STD -_LIBCPP_POP_MACROS - #endif // _LIBCPP___ALGORITHM_NONE_OF_H diff --git a/lib/libcxx/include/__algorithm/nth_element.h b/lib/libcxx/include/__algorithm/nth_element.h index 67a03cfc37..3afbd6c618 100644 --- a/lib/libcxx/include/__algorithm/nth_element.h +++ b/lib/libcxx/include/__algorithm/nth_element.h @@ -9,20 +9,21 @@ #ifndef _LIBCPP___ALGORITHM_NTH_ELEMENT_H #define _LIBCPP___ALGORITHM_NTH_ELEMENT_H -#include <__config> #include <__algorithm/comp.h> #include <__algorithm/comp_ref_type.h> #include <__algorithm/sort.h> +#include <__config> #include <__iterator/iterator_traits.h> #include <__utility/swap.h> +#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 template<class _Compare, class _RandomAccessIterator> @@ -225,8 +226,13 @@ inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17 void nth_element(_RandomAccessIterator __first, _RandomAccessIterator __nth, _RandomAccessIterator __last, _Compare __comp) { - typedef typename __comp_ref_type<_Compare>::type _Comp_ref; - _VSTD::__nth_element<_Comp_ref>(__first, __nth, __last, __comp); + _LIBCPP_DEBUG_RANDOMIZE_RANGE(__first, __last); + typedef typename __comp_ref_type<_Compare>::type _Comp_ref; + _VSTD::__nth_element<_Comp_ref>(__first, __nth, __last, __comp); + _LIBCPP_DEBUG_RANDOMIZE_RANGE(__first, __nth); + if (__nth != __last) { + _LIBCPP_DEBUG_RANDOMIZE_RANGE(++__nth, __last); + } } template <class _RandomAccessIterator> @@ -239,6 +245,4 @@ nth_element(_RandomAccessIterator __first, _RandomAccessIterator __nth, _RandomA _LIBCPP_END_NAMESPACE_STD -_LIBCPP_POP_MACROS - #endif // _LIBCPP___ALGORITHM_NTH_ELEMENT_H diff --git a/lib/libcxx/include/__algorithm/partial_sort.h b/lib/libcxx/include/__algorithm/partial_sort.h index 4f9872c492..a92a7e5661 100644 --- a/lib/libcxx/include/__algorithm/partial_sort.h +++ b/lib/libcxx/include/__algorithm/partial_sort.h @@ -9,29 +9,32 @@ #ifndef _LIBCPP___ALGORITHM_PARTIAL_SORT_H #define _LIBCPP___ALGORITHM_PARTIAL_SORT_H -#include <__config> #include <__algorithm/comp.h> #include <__algorithm/comp_ref_type.h> #include <__algorithm/make_heap.h> #include <__algorithm/sift_down.h> #include <__algorithm/sort_heap.h> +#include <__config> #include <__iterator/iterator_traits.h> #include <__utility/swap.h> +#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 template <class _Compare, class _RandomAccessIterator> _LIBCPP_CONSTEXPR_AFTER_CXX17 void __partial_sort(_RandomAccessIterator __first, _RandomAccessIterator __middle, _RandomAccessIterator __last, - _Compare __comp) + _Compare __comp) { + if (__first == __middle) + return; _VSTD::__make_heap<_Compare>(__first, __middle, __comp); typename iterator_traits<_RandomAccessIterator>::difference_type __len = __middle - __first; for (_RandomAccessIterator __i = __middle; __i != __last; ++__i) @@ -39,7 +42,7 @@ __partial_sort(_RandomAccessIterator __first, _RandomAccessIterator __middle, _R if (__comp(*__i, *__first)) { swap(*__i, *__first); - _VSTD::__sift_down<_Compare>(__first, __middle, __comp, __len, __first); + _VSTD::__sift_down<_Compare>(__first, __comp, __len, __first); } } _VSTD::__sort_heap<_Compare>(__first, __middle, __comp); @@ -51,8 +54,10 @@ void partial_sort(_RandomAccessIterator __first, _RandomAccessIterator __middle, _RandomAccessIterator __last, _Compare __comp) { - typedef typename __comp_ref_type<_Compare>::type _Comp_ref; - _VSTD::__partial_sort<_Comp_ref>(__first, __middle, __last, __comp); + _LIBCPP_DEBUG_RANDOMIZE_RANGE(__first, __last); + typedef typename __comp_ref_type<_Compare>::type _Comp_ref; + _VSTD::__partial_sort<_Comp_ref>(__first, __middle, __last, __comp); + _LIBCPP_DEBUG_RANDOMIZE_RANGE(__middle, __last); } template <class _RandomAccessIterator> @@ -61,11 +66,9 @@ void partial_sort(_RandomAccessIterator __first, _RandomAccessIterator __middle, _RandomAccessIterator __last) { _VSTD::partial_sort(__first, __middle, __last, - __less<typename iterator_traits<_RandomAccessIterator>::value_type>()); + __less<typename iterator_traits<_RandomAccessIterator>::value_type>()); } _LIBCPP_END_NAMESPACE_STD -_LIBCPP_POP_MACROS - #endif // _LIBCPP___ALGORITHM_PARTIAL_SORT_H diff --git a/lib/libcxx/include/__algorithm/partial_sort_copy.h b/lib/libcxx/include/__algorithm/partial_sort_copy.h index 31a12615fa..67a62bae1f 100644 --- a/lib/libcxx/include/__algorithm/partial_sort_copy.h +++ b/lib/libcxx/include/__algorithm/partial_sort_copy.h @@ -9,22 +9,18 @@ #ifndef _LIBCPP___ALGORITHM_PARTIAL_SORT_COPY_H #define _LIBCPP___ALGORITHM_PARTIAL_SORT_COPY_H -#include <__config> #include <__algorithm/comp.h> #include <__algorithm/comp_ref_type.h> #include <__algorithm/make_heap.h> #include <__algorithm/sift_down.h> #include <__algorithm/sort_heap.h> +#include <__config> #include <__iterator/iterator_traits.h> -#include <type_traits> // swap #if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER) #pragma GCC system_header #endif -_LIBCPP_PUSH_MACROS -#include <__undef_macros> - _LIBCPP_BEGIN_NAMESPACE_STD template <class _Compare, class _InputIterator, class _RandomAccessIterator> @@ -43,7 +39,7 @@ __partial_sort_copy(_InputIterator __first, _InputIterator __last, if (__comp(*__first, *__result_first)) { *__result_first = *__first; - _VSTD::__sift_down<_Compare>(__result_first, __r, __comp, __len, __result_first); + _VSTD::__sift_down<_Compare>(__result_first, __comp, __len, __result_first); } _VSTD::__sort_heap<_Compare>(__result_first, __r, __comp); } @@ -72,6 +68,4 @@ partial_sort_copy(_InputIterator __first, _InputIterator __last, _LIBCPP_END_NAMESPACE_STD -_LIBCPP_POP_MACROS - #endif // _LIBCPP___ALGORITHM_PARTIAL_SORT_COPY_H diff --git a/lib/libcxx/include/__algorithm/partition.h b/lib/libcxx/include/__algorithm/partition.h index c859eaca28..131c5d3735 100644 --- a/lib/libcxx/include/__algorithm/partition.h +++ b/lib/libcxx/include/__algorithm/partition.h @@ -12,16 +12,11 @@ #include <__config> #include <__iterator/iterator_traits.h> #include <__utility/swap.h> -#include <utility> // pair -#include <type_traits> #if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER) #pragma GCC system_header #endif -_LIBCPP_PUSH_MACROS -#include <__undef_macros> - _LIBCPP_BEGIN_NAMESPACE_STD template <class _Predicate, class _ForwardIterator> @@ -77,12 +72,10 @@ inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17 _ForwardIterator partition(_ForwardIterator __first, _ForwardIterator __last, _Predicate __pred) { - return _VSTD::__partition<typename add_lvalue_reference<_Predicate>::type> - (__first, __last, __pred, typename iterator_traits<_ForwardIterator>::iterator_category()); + return _VSTD::__partition<_Predicate&>( + __first, __last, __pred, typename iterator_traits<_ForwardIterator>::iterator_category()); } _LIBCPP_END_NAMESPACE_STD -_LIBCPP_POP_MACROS - #endif // _LIBCPP___ALGORITHM_PARTITION_H diff --git a/lib/libcxx/include/__algorithm/partition_copy.h b/lib/libcxx/include/__algorithm/partition_copy.h index 445eacdfbe..d34944589b 100644 --- a/lib/libcxx/include/__algorithm/partition_copy.h +++ b/lib/libcxx/include/__algorithm/partition_copy.h @@ -17,9 +17,6 @@ #pragma GCC system_header #endif -_LIBCPP_PUSH_MACROS -#include <__undef_macros> - _LIBCPP_BEGIN_NAMESPACE_STD template <class _InputIterator, class _OutputIterator1, @@ -47,6 +44,4 @@ partition_copy(_InputIterator __first, _InputIterator __last, _LIBCPP_END_NAMESPACE_STD -_LIBCPP_POP_MACROS - #endif // _LIBCPP___ALGORITHM_PARTITION_COPY_H diff --git a/lib/libcxx/include/__algorithm/partition_point.h b/lib/libcxx/include/__algorithm/partition_point.h index 12ddacf9d7..18e6e6f681 100644 --- a/lib/libcxx/include/__algorithm/partition_point.h +++ b/lib/libcxx/include/__algorithm/partition_point.h @@ -9,17 +9,14 @@ #ifndef _LIBCPP___ALGORITHM_PARTITION_POINT_H #define _LIBCPP___ALGORITHM_PARTITION_POINT_H -#include <__config> #include <__algorithm/half_positive.h> +#include <__config> #include <iterator> #if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER) #pragma GCC system_header #endif -_LIBCPP_PUSH_MACROS -#include <__undef_macros> - _LIBCPP_BEGIN_NAMESPACE_STD template<class _ForwardIterator, class _Predicate> @@ -46,6 +43,4 @@ partition_point(_ForwardIterator __first, _ForwardIterator __last, _Predicate __ _LIBCPP_END_NAMESPACE_STD -_LIBCPP_POP_MACROS - #endif // _LIBCPP___ALGORITHM_PARTITION_POINT_H diff --git a/lib/libcxx/include/__algorithm/pop_heap.h b/lib/libcxx/include/__algorithm/pop_heap.h index 7ebbef25e0..c1cc8016ac 100644 --- a/lib/libcxx/include/__algorithm/pop_heap.h +++ b/lib/libcxx/include/__algorithm/pop_heap.h @@ -9,10 +9,10 @@ #ifndef _LIBCPP___ALGORITHM_POP_HEAP_H #define _LIBCPP___ALGORITHM_POP_HEAP_H -#include <__config> #include <__algorithm/comp.h> #include <__algorithm/comp_ref_type.h> #include <__algorithm/sift_down.h> +#include <__config> #include <__iterator/iterator_traits.h> #include <__utility/swap.h> @@ -20,9 +20,6 @@ #pragma GCC system_header #endif -_LIBCPP_PUSH_MACROS -#include <__undef_macros> - _LIBCPP_BEGIN_NAMESPACE_STD template <class _Compare, class _RandomAccessIterator> @@ -34,7 +31,7 @@ __pop_heap(_RandomAccessIterator __first, _RandomAccessIterator __last, _Compare if (__len > 1) { swap(*__first, *--__last); - _VSTD::__sift_down<_Compare>(__first, __last, __comp, __len - 1, __first); + _VSTD::__sift_down<_Compare>(__first, __comp, __len - 1, __first); } } @@ -57,6 +54,4 @@ pop_heap(_RandomAccessIterator __first, _RandomAccessIterator __last) _LIBCPP_END_NAMESPACE_STD -_LIBCPP_POP_MACROS - #endif // _LIBCPP___ALGORITHM_POP_HEAP_H diff --git a/lib/libcxx/include/__algorithm/prev_permutation.h b/lib/libcxx/include/__algorithm/prev_permutation.h index d6daa73ada..457c2695b3 100644 --- a/lib/libcxx/include/__algorithm/prev_permutation.h +++ b/lib/libcxx/include/__algorithm/prev_permutation.h @@ -9,10 +9,10 @@ #ifndef _LIBCPP___ALGORITHM_PREV_PERMUTATION_H #define _LIBCPP___ALGORITHM_PREV_PERMUTATION_H -#include <__config> #include <__algorithm/comp.h> #include <__algorithm/comp_ref_type.h> #include <__algorithm/reverse.h> +#include <__config> #include <__iterator/iterator_traits.h> #include <__utility/swap.h> @@ -20,9 +20,6 @@ #pragma GCC system_header #endif -_LIBCPP_PUSH_MACROS -#include <__undef_macros> - _LIBCPP_BEGIN_NAMESPACE_STD template <class _Compare, class _BidirectionalIterator> @@ -72,6 +69,4 @@ prev_permutation(_BidirectionalIterator __first, _BidirectionalIterator __last) _LIBCPP_END_NAMESPACE_STD -_LIBCPP_POP_MACROS - #endif // _LIBCPP___ALGORITHM_PREV_PERMUTATION_H diff --git a/lib/libcxx/include/__algorithm/push_heap.h b/lib/libcxx/include/__algorithm/push_heap.h index 82a7c123d8..864d419fa2 100644 --- a/lib/libcxx/include/__algorithm/push_heap.h +++ b/lib/libcxx/include/__algorithm/push_heap.h @@ -9,9 +9,9 @@ #ifndef _LIBCPP___ALGORITHM_PUSH_HEAP_H #define _LIBCPP___ALGORITHM_PUSH_HEAP_H -#include <__config> #include <__algorithm/comp.h> #include <__algorithm/comp_ref_type.h> +#include <__config> #include <__iterator/iterator_traits.h> #include <__utility/move.h> @@ -19,9 +19,6 @@ #pragma GCC system_header #endif -_LIBCPP_PUSH_MACROS -#include <__undef_macros> - _LIBCPP_BEGIN_NAMESPACE_STD template <class _Compare, class _RandomAccessIterator> @@ -70,6 +67,4 @@ push_heap(_RandomAccessIterator __first, _RandomAccessIterator __last) _LIBCPP_END_NAMESPACE_STD -_LIBCPP_POP_MACROS - #endif // _LIBCPP___ALGORITHM_PUSH_HEAP_H diff --git a/lib/libcxx/include/__algorithm/remove.h b/lib/libcxx/include/__algorithm/remove.h index 4717d7d973..681b9cc768 100644 --- a/lib/libcxx/include/__algorithm/remove.h +++ b/lib/libcxx/include/__algorithm/remove.h @@ -9,18 +9,15 @@ #ifndef _LIBCPP___ALGORITHM_REMOVE_H #define _LIBCPP___ALGORITHM_REMOVE_H -#include <__config> #include <__algorithm/find.h> #include <__algorithm/find_if.h> +#include <__config> #include <__utility/move.h> #if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER) #pragma GCC system_header #endif -_LIBCPP_PUSH_MACROS -#include <__undef_macros> - _LIBCPP_BEGIN_NAMESPACE_STD template <class _ForwardIterator, class _Tp> @@ -45,6 +42,4 @@ remove(_ForwardIterator __first, _ForwardIterator __last, const _Tp& __value_) _LIBCPP_END_NAMESPACE_STD -_LIBCPP_POP_MACROS - #endif // _LIBCPP___ALGORITHM_REMOVE_H diff --git a/lib/libcxx/include/__algorithm/remove_copy.h b/lib/libcxx/include/__algorithm/remove_copy.h index 5d2b640343..338ca94300 100644 --- a/lib/libcxx/include/__algorithm/remove_copy.h +++ b/lib/libcxx/include/__algorithm/remove_copy.h @@ -15,9 +15,6 @@ #pragma GCC system_header #endif -_LIBCPP_PUSH_MACROS -#include <__undef_macros> - _LIBCPP_BEGIN_NAMESPACE_STD template <class _InputIterator, class _OutputIterator, class _Tp> @@ -38,6 +35,4 @@ remove_copy(_InputIterator __first, _InputIterator __last, _OutputIterator __res _LIBCPP_END_NAMESPACE_STD -_LIBCPP_POP_MACROS - #endif // _LIBCPP___ALGORITHM_REMOVE_COPY_H diff --git a/lib/libcxx/include/__algorithm/remove_copy_if.h b/lib/libcxx/include/__algorithm/remove_copy_if.h index 44822564a5..a556387220 100644 --- a/lib/libcxx/include/__algorithm/remove_copy_if.h +++ b/lib/libcxx/include/__algorithm/remove_copy_if.h @@ -15,9 +15,6 @@ #pragma GCC system_header #endif -_LIBCPP_PUSH_MACROS -#include <__undef_macros> - _LIBCPP_BEGIN_NAMESPACE_STD template <class _InputIterator, class _OutputIterator, class _Predicate> @@ -38,6 +35,4 @@ remove_copy_if(_InputIterator __first, _InputIterator __last, _OutputIterator __ _LIBCPP_END_NAMESPACE_STD -_LIBCPP_POP_MACROS - #endif // _LIBCPP___ALGORITHM_REMOVE_COPY_IF_H diff --git a/lib/libcxx/include/__algorithm/remove_if.h b/lib/libcxx/include/__algorithm/remove_if.h index e506b4c67f..36f817cfa6 100644 --- a/lib/libcxx/include/__algorithm/remove_if.h +++ b/lib/libcxx/include/__algorithm/remove_if.h @@ -9,26 +9,21 @@ #ifndef _LIBCPP___ALGORITHM_REMOVE_IF_H #define _LIBCPP___ALGORITHM_REMOVE_IF_H -#include <__config> #include <__algorithm/find_if.h> +#include <__config> #include <utility> -#include <type_traits> #if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER) #pragma GCC system_header #endif -_LIBCPP_PUSH_MACROS -#include <__undef_macros> - _LIBCPP_BEGIN_NAMESPACE_STD template <class _ForwardIterator, class _Predicate> _LIBCPP_NODISCARD_EXT _LIBCPP_CONSTEXPR_AFTER_CXX17 _ForwardIterator remove_if(_ForwardIterator __first, _ForwardIterator __last, _Predicate __pred) { - __first = _VSTD::find_if<_ForwardIterator, typename add_lvalue_reference<_Predicate>::type> - (__first, __last, __pred); + __first = _VSTD::find_if<_ForwardIterator, _Predicate&>(__first, __last, __pred); if (__first != __last) { _ForwardIterator __i = __first; @@ -46,6 +41,4 @@ remove_if(_ForwardIterator __first, _ForwardIterator __last, _Predicate __pred) _LIBCPP_END_NAMESPACE_STD -_LIBCPP_POP_MACROS - #endif // _LIBCPP___ALGORITHM_REMOVE_IF_H diff --git a/lib/libcxx/include/__algorithm/replace.h b/lib/libcxx/include/__algorithm/replace.h index b723ffeeac..2bc96ffc87 100644 --- a/lib/libcxx/include/__algorithm/replace.h +++ b/lib/libcxx/include/__algorithm/replace.h @@ -15,9 +15,6 @@ #pragma GCC system_header #endif -_LIBCPP_PUSH_MACROS -#include <__undef_macros> - _LIBCPP_BEGIN_NAMESPACE_STD template <class _ForwardIterator, class _Tp> @@ -32,6 +29,4 @@ replace(_ForwardIterator __first, _ForwardIterator __last, const _Tp& __old_valu _LIBCPP_END_NAMESPACE_STD -_LIBCPP_POP_MACROS - #endif // _LIBCPP___ALGORITHM_REPLACE_H diff --git a/lib/libcxx/include/__algorithm/replace_copy.h b/lib/libcxx/include/__algorithm/replace_copy.h index 1923a57e42..c6c5fe32e8 100644 --- a/lib/libcxx/include/__algorithm/replace_copy.h +++ b/lib/libcxx/include/__algorithm/replace_copy.h @@ -15,9 +15,6 @@ #pragma GCC system_header #endif -_LIBCPP_PUSH_MACROS -#include <__undef_macros> - _LIBCPP_BEGIN_NAMESPACE_STD template <class _InputIterator, class _OutputIterator, class _Tp> @@ -36,6 +33,4 @@ replace_copy(_InputIterator __first, _InputIterator __last, _OutputIterator __re _LIBCPP_END_NAMESPACE_STD -_LIBCPP_POP_MACROS - #endif // _LIBCPP___ALGORITHM_REPLACE_COPY_H diff --git a/lib/libcxx/include/__algorithm/replace_copy_if.h b/lib/libcxx/include/__algorithm/replace_copy_if.h index 72b6f73697..274d8e630e 100644 --- a/lib/libcxx/include/__algorithm/replace_copy_if.h +++ b/lib/libcxx/include/__algorithm/replace_copy_if.h @@ -15,9 +15,6 @@ #pragma GCC system_header #endif -_LIBCPP_PUSH_MACROS -#include <__undef_macros> - _LIBCPP_BEGIN_NAMESPACE_STD template <class _InputIterator, class _OutputIterator, class _Predicate, class _Tp> @@ -36,6 +33,4 @@ replace_copy_if(_InputIterator __first, _InputIterator __last, _OutputIterator _ _LIBCPP_END_NAMESPACE_STD -_LIBCPP_POP_MACROS - #endif // _LIBCPP___ALGORITHM_REPLACE_COPY_IF_H diff --git a/lib/libcxx/include/__algorithm/replace_if.h b/lib/libcxx/include/__algorithm/replace_if.h index 49101a5ce1..bcc3feb2f5 100644 --- a/lib/libcxx/include/__algorithm/replace_if.h +++ b/lib/libcxx/include/__algorithm/replace_if.h @@ -15,9 +15,6 @@ #pragma GCC system_header #endif -_LIBCPP_PUSH_MACROS -#include <__undef_macros> - _LIBCPP_BEGIN_NAMESPACE_STD template <class _ForwardIterator, class _Predicate, class _Tp> @@ -32,6 +29,4 @@ replace_if(_ForwardIterator __first, _ForwardIterator __last, _Predicate __pred, _LIBCPP_END_NAMESPACE_STD -_LIBCPP_POP_MACROS - #endif // _LIBCPP___ALGORITHM_REPLACE_IF_H diff --git a/lib/libcxx/include/__algorithm/reverse.h b/lib/libcxx/include/__algorithm/reverse.h index e538de1147..1198aeaf41 100644 --- a/lib/libcxx/include/__algorithm/reverse.h +++ b/lib/libcxx/include/__algorithm/reverse.h @@ -9,17 +9,14 @@ #ifndef _LIBCPP___ALGORITHM_REVERSE_H #define _LIBCPP___ALGORITHM_REVERSE_H -#include <__config> #include <__algorithm/iter_swap.h> +#include <__config> #include <__iterator/iterator_traits.h> #if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER) #pragma GCC system_header #endif -_LIBCPP_PUSH_MACROS -#include <__undef_macros> - _LIBCPP_BEGIN_NAMESPACE_STD template <class _BidirectionalIterator> @@ -56,6 +53,4 @@ reverse(_BidirectionalIterator __first, _BidirectionalIterator __last) _LIBCPP_END_NAMESPACE_STD -_LIBCPP_POP_MACROS - #endif // _LIBCPP___ALGORITHM_REVERSE_H diff --git a/lib/libcxx/include/__algorithm/reverse_copy.h b/lib/libcxx/include/__algorithm/reverse_copy.h index 48ce60cf88..002c0344a7 100644 --- a/lib/libcxx/include/__algorithm/reverse_copy.h +++ b/lib/libcxx/include/__algorithm/reverse_copy.h @@ -15,9 +15,6 @@ #pragma GCC system_header #endif -_LIBCPP_PUSH_MACROS -#include <__undef_macros> - _LIBCPP_BEGIN_NAMESPACE_STD template <class _BidirectionalIterator, class _OutputIterator> @@ -32,6 +29,4 @@ reverse_copy(_BidirectionalIterator __first, _BidirectionalIterator __last, _Out _LIBCPP_END_NAMESPACE_STD -_LIBCPP_POP_MACROS - #endif // _LIBCPP___ALGORITHM_REVERSE_COPY_H diff --git a/lib/libcxx/include/__algorithm/rotate.h b/lib/libcxx/include/__algorithm/rotate.h index 0c9ccd7bf7..fd6d3e9c11 100644 --- a/lib/libcxx/include/__algorithm/rotate.h +++ b/lib/libcxx/include/__algorithm/rotate.h @@ -23,9 +23,6 @@ #pragma GCC system_header #endif -_LIBCPP_PUSH_MACROS -#include <__undef_macros> - _LIBCPP_BEGIN_NAMESPACE_STD template <class _ForwardIterator> @@ -200,6 +197,4 @@ rotate(_ForwardIterator __first, _ForwardIterator __middle, _ForwardIterator __l _LIBCPP_END_NAMESPACE_STD -_LIBCPP_POP_MACROS - #endif // _LIBCPP___ALGORITHM_ROTATE_H diff --git a/lib/libcxx/include/__algorithm/rotate_copy.h b/lib/libcxx/include/__algorithm/rotate_copy.h index d5ab7d3b51..f9e644c88d 100644 --- a/lib/libcxx/include/__algorithm/rotate_copy.h +++ b/lib/libcxx/include/__algorithm/rotate_copy.h @@ -9,18 +9,13 @@ #ifndef _LIBCPP___ALGORITHM_ROTATE_COPY_H #define _LIBCPP___ALGORITHM_ROTATE_COPY_H -#include <__config> #include <__algorithm/copy.h> -#include <iterator> -#include <type_traits> +#include <__config> #if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER) #pragma GCC system_header #endif -_LIBCPP_PUSH_MACROS -#include <__undef_macros> - _LIBCPP_BEGIN_NAMESPACE_STD template <class _ForwardIterator, class _OutputIterator> @@ -33,6 +28,4 @@ rotate_copy(_ForwardIterator __first, _ForwardIterator __middle, _ForwardIterato _LIBCPP_END_NAMESPACE_STD -_LIBCPP_POP_MACROS - #endif // _LIBCPP___ALGORITHM_ROTATE_COPY_H diff --git a/lib/libcxx/include/__algorithm/sample.h b/lib/libcxx/include/__algorithm/sample.h index 2aac6ffa8c..33264c4ea3 100644 --- a/lib/libcxx/include/__algorithm/sample.h +++ b/lib/libcxx/include/__algorithm/sample.h @@ -9,8 +9,9 @@ #ifndef _LIBCPP___ALGORITHM_SAMPLE_H #define _LIBCPP___ALGORITHM_SAMPLE_H -#include <__config> #include <__algorithm/min.h> +#include <__config> +#include <__debug> #include <__random/uniform_int_distribution.h> #include <iterator> diff --git a/lib/libcxx/include/__algorithm/search.h b/lib/libcxx/include/__algorithm/search.h index 008b8ebb04..cfaec0ed1e 100644 --- a/lib/libcxx/include/__algorithm/search.h +++ b/lib/libcxx/include/__algorithm/search.h @@ -13,16 +13,12 @@ #include <__algorithm/comp.h> #include <__config> #include <__iterator/iterator_traits.h> -#include <type_traits> #include <utility> #if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER) #pragma GCC system_header #endif -_LIBCPP_PUSH_MACROS -#include <__undef_macros> - _LIBCPP_BEGIN_NAMESPACE_STD template <class _BinaryPredicate, class _ForwardIterator1, class _ForwardIterator2> @@ -72,7 +68,7 @@ __search(_RandomAccessIterator1 __first1, _RandomAccessIterator1 __last1, _Rando const _D1 __len1 = __last1 - __first1; if (__len1 < __len2) return _VSTD::make_pair(__last1, __last1); - const _RandomAccessIterator1 __s = __last1 - (__len2 - 1); // Start of pattern match can't go beyond here + const _RandomAccessIterator1 __s = __last1 - _D1(__len2 - 1); // Start of pattern match can't go beyond here while (true) { while (true) { @@ -87,7 +83,7 @@ __search(_RandomAccessIterator1 __first1, _RandomAccessIterator1 __last1, _Rando _RandomAccessIterator2 __m2 = __first2; while (true) { if (++__m2 == __last2) - return _VSTD::make_pair(__first1, __first1 + __len2); + return _VSTD::make_pair(__first1, __first1 + _D1(__len2)); ++__m1; // no need to check range on __m1 because __s guarantees we have enough source if (!__pred(*__m1, *__m2)) { ++__first1; @@ -101,7 +97,7 @@ template <class _ForwardIterator1, class _ForwardIterator2, class _BinaryPredica _LIBCPP_NODISCARD_EXT inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17 _ForwardIterator1 search(_ForwardIterator1 __first1, _ForwardIterator1 __last1, _ForwardIterator2 __first2, _ForwardIterator2 __last2, _BinaryPredicate __pred) { - return _VSTD::__search<typename add_lvalue_reference<_BinaryPredicate>::type>( + return _VSTD::__search<_BinaryPredicate&>( __first1, __last1, __first2, __last2, __pred, typename iterator_traits<_ForwardIterator1>::iterator_category(), typename iterator_traits<_ForwardIterator2>::iterator_category()).first; @@ -126,6 +122,4 @@ search(_ForwardIterator __f, _ForwardIterator __l, const _Searcher& __s) { _LIBCPP_END_NAMESPACE_STD -_LIBCPP_POP_MACROS - #endif // _LIBCPP___ALGORITHM_SEARCH_H diff --git a/lib/libcxx/include/__algorithm/search_n.h b/lib/libcxx/include/__algorithm/search_n.h index 1584e8e613..e4576cc76a 100644 --- a/lib/libcxx/include/__algorithm/search_n.h +++ b/lib/libcxx/include/__algorithm/search_n.h @@ -10,18 +10,15 @@ #ifndef _LIBCPP___ALGORITHM_SEARCH_N_H #define _LIBCPP___ALGORITHM_SEARCH_N_H -#include <__config> #include <__algorithm/comp.h> +#include <__config> #include <__iterator/iterator_traits.h> -#include <type_traits> +#include <type_traits> // __convert_to_integral #if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER) #pragma GCC system_header #endif -_LIBCPP_PUSH_MACROS -#include <__undef_macros> - _LIBCPP_BEGIN_NAMESPACE_STD template <class _BinaryPredicate, class _ForwardIterator, class _Size, class _Tp> @@ -62,12 +59,13 @@ _LIBCPP_CONSTEXPR_AFTER_CXX17 _RandomAccessIterator __search_n(_RandomAccessIter _RandomAccessIterator __last, _Size __count, const _Tp& __value_, _BinaryPredicate __pred, random_access_iterator_tag) { + typedef typename iterator_traits<_RandomAccessIterator>::difference_type difference_type; if (__count <= 0) return __first; _Size __len = static_cast<_Size>(__last - __first); if (__len < __count) return __last; - const _RandomAccessIterator __s = __last - (__count - 1); // Start of pattern match can't go beyond here + const _RandomAccessIterator __s = __last - difference_type(__count - 1); // Start of pattern match can't go beyond here while (true) { // Find first element in sequence that matchs __value_, with a mininum of loop checks while (true) { @@ -97,7 +95,7 @@ _LIBCPP_CONSTEXPR_AFTER_CXX17 _RandomAccessIterator __search_n(_RandomAccessIter template <class _ForwardIterator, class _Size, class _Tp, class _BinaryPredicate> _LIBCPP_NODISCARD_EXT inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17 _ForwardIterator search_n( _ForwardIterator __first, _ForwardIterator __last, _Size __count, const _Tp& __value_, _BinaryPredicate __pred) { - return _VSTD::__search_n<typename add_lvalue_reference<_BinaryPredicate>::type>( + return _VSTD::__search_n<_BinaryPredicate&>( __first, __last, _VSTD::__convert_to_integral(__count), __value_, __pred, typename iterator_traits<_ForwardIterator>::iterator_category()); } @@ -111,6 +109,4 @@ search_n(_ForwardIterator __first, _ForwardIterator __last, _Size __count, const _LIBCPP_END_NAMESPACE_STD -_LIBCPP_POP_MACROS - #endif // _LIBCPP___ALGORITHM_SEARCH_N_H diff --git a/lib/libcxx/include/__algorithm/set_difference.h b/lib/libcxx/include/__algorithm/set_difference.h index f4c985d978..00f61e070b 100644 --- a/lib/libcxx/include/__algorithm/set_difference.h +++ b/lib/libcxx/include/__algorithm/set_difference.h @@ -9,19 +9,16 @@ #ifndef _LIBCPP___ALGORITHM_SET_DIFFERENCE_H #define _LIBCPP___ALGORITHM_SET_DIFFERENCE_H -#include <__config> #include <__algorithm/comp.h> #include <__algorithm/comp_ref_type.h> #include <__algorithm/copy.h> +#include <__config> #include <__iterator/iterator_traits.h> #if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER) #pragma GCC system_header #endif -_LIBCPP_PUSH_MACROS -#include <__undef_macros> - _LIBCPP_BEGIN_NAMESPACE_STD template <class _Compare, class _InputIterator1, class _InputIterator2, class _OutputIterator> @@ -72,6 +69,4 @@ set_difference(_InputIterator1 __first1, _InputIterator1 __last1, _LIBCPP_END_NAMESPACE_STD -_LIBCPP_POP_MACROS - #endif // _LIBCPP___ALGORITHM_SET_DIFFERENCE_H diff --git a/lib/libcxx/include/__algorithm/set_intersection.h b/lib/libcxx/include/__algorithm/set_intersection.h index 9d34b66c23..f6aa38217d 100644 --- a/lib/libcxx/include/__algorithm/set_intersection.h +++ b/lib/libcxx/include/__algorithm/set_intersection.h @@ -9,18 +9,15 @@ #ifndef _LIBCPP___ALGORITHM_SET_INTERSECTION_H #define _LIBCPP___ALGORITHM_SET_INTERSECTION_H -#include <__config> #include <__algorithm/comp.h> #include <__algorithm/comp_ref_type.h> +#include <__config> #include <__iterator/iterator_traits.h> #if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER) #pragma GCC system_header #endif -_LIBCPP_PUSH_MACROS -#include <__undef_macros> - _LIBCPP_BEGIN_NAMESPACE_STD template <class _Compare, class _InputIterator1, class _InputIterator2, class _OutputIterator> @@ -69,6 +66,4 @@ set_intersection(_InputIterator1 __first1, _InputIterator1 __last1, _LIBCPP_END_NAMESPACE_STD -_LIBCPP_POP_MACROS - #endif // _LIBCPP___ALGORITHM_SET_INTERSECTION_H diff --git a/lib/libcxx/include/__algorithm/set_symmetric_difference.h b/lib/libcxx/include/__algorithm/set_symmetric_difference.h index 5650b836a6..5b5c2acff7 100644 --- a/lib/libcxx/include/__algorithm/set_symmetric_difference.h +++ b/lib/libcxx/include/__algorithm/set_symmetric_difference.h @@ -9,19 +9,16 @@ #ifndef _LIBCPP___ALGORITHM_SET_SYMMETRIC_DIFFERENCE_H #define _LIBCPP___ALGORITHM_SET_SYMMETRIC_DIFFERENCE_H -#include <__config> #include <__algorithm/comp.h> #include <__algorithm/comp_ref_type.h> #include <__algorithm/copy.h> +#include <__config> #include <__iterator/iterator_traits.h> #if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER) #pragma GCC system_header #endif -_LIBCPP_PUSH_MACROS -#include <__undef_macros> - _LIBCPP_BEGIN_NAMESPACE_STD template <class _Compare, class _InputIterator1, class _InputIterator2, class _OutputIterator> @@ -77,6 +74,4 @@ set_symmetric_difference(_InputIterator1 __first1, _InputIterator1 __last1, _LIBCPP_END_NAMESPACE_STD -_LIBCPP_POP_MACROS - #endif // _LIBCPP___ALGORITHM_SET_SYMMETRIC_DIFFERENCE_H diff --git a/lib/libcxx/include/__algorithm/set_union.h b/lib/libcxx/include/__algorithm/set_union.h index c0874e9574..5b3e3af79b 100644 --- a/lib/libcxx/include/__algorithm/set_union.h +++ b/lib/libcxx/include/__algorithm/set_union.h @@ -9,19 +9,16 @@ #ifndef _LIBCPP___ALGORITHM_SET_UNION_H #define _LIBCPP___ALGORITHM_SET_UNION_H -#include <__config> #include <__algorithm/comp.h> #include <__algorithm/comp_ref_type.h> #include <__algorithm/copy.h> +#include <__config> #include <__iterator/iterator_traits.h> #if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER) #pragma GCC system_header #endif -_LIBCPP_PUSH_MACROS -#include <__undef_macros> - _LIBCPP_BEGIN_NAMESPACE_STD template <class _Compare, class _InputIterator1, class _InputIterator2, class _OutputIterator> @@ -72,6 +69,4 @@ set_union(_InputIterator1 __first1, _InputIterator1 __last1, _LIBCPP_END_NAMESPACE_STD -_LIBCPP_POP_MACROS - #endif // _LIBCPP___ALGORITHM_SET_UNION_H diff --git a/lib/libcxx/include/__algorithm/shift_left.h b/lib/libcxx/include/__algorithm/shift_left.h index 961b89cb00..0466a3188a 100644 --- a/lib/libcxx/include/__algorithm/shift_left.h +++ b/lib/libcxx/include/__algorithm/shift_left.h @@ -9,18 +9,15 @@ #ifndef _LIBCPP___ALGORITHM_SHIFT_LEFT_H #define _LIBCPP___ALGORITHM_SHIFT_LEFT_H -#include <__config> #include <__algorithm/move.h> +#include <__config> #include <__iterator/iterator_traits.h> -#include <type_traits> // swap +#include <type_traits> #if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER) #pragma GCC system_header #endif -_LIBCPP_PUSH_MACROS -#include <__undef_macros> - _LIBCPP_BEGIN_NAMESPACE_STD #if _LIBCPP_STD_VER > 17 @@ -56,6 +53,4 @@ shift_left(_ForwardIterator __first, _ForwardIterator __last, _LIBCPP_END_NAMESPACE_STD -_LIBCPP_POP_MACROS - #endif // _LIBCPP___ALGORITHM_SHIFT_LEFT_H diff --git a/lib/libcxx/include/__algorithm/shift_right.h b/lib/libcxx/include/__algorithm/shift_right.h index 5cb4195064..121712e855 100644 --- a/lib/libcxx/include/__algorithm/shift_right.h +++ b/lib/libcxx/include/__algorithm/shift_right.h @@ -9,20 +9,18 @@ #ifndef _LIBCPP___ALGORITHM_SHIFT_RIGHT_H #define _LIBCPP___ALGORITHM_SHIFT_RIGHT_H -#include <__config> #include <__algorithm/move.h> #include <__algorithm/move_backward.h> #include <__algorithm/swap_ranges.h> +#include <__config> #include <__iterator/iterator_traits.h> -#include <type_traits> // swap +#include <__utility/swap.h> +#include <type_traits> #if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER) #pragma GCC system_header #endif -_LIBCPP_PUSH_MACROS -#include <__undef_macros> - _LIBCPP_BEGIN_NAMESPACE_STD #if _LIBCPP_STD_VER > 17 @@ -101,6 +99,4 @@ shift_right(_ForwardIterator __first, _ForwardIterator __last, _LIBCPP_END_NAMESPACE_STD -_LIBCPP_POP_MACROS - #endif // _LIBCPP___ALGORITHM_SHIFT_RIGHT_H diff --git a/lib/libcxx/include/__algorithm/shuffle.h b/lib/libcxx/include/__algorithm/shuffle.h index 637fca5388..7f6ad50e24 100644 --- a/lib/libcxx/include/__algorithm/shuffle.h +++ b/lib/libcxx/include/__algorithm/shuffle.h @@ -25,6 +25,39 @@ _LIBCPP_PUSH_MACROS _LIBCPP_BEGIN_NAMESPACE_STD +class _LIBCPP_TYPE_VIS __libcpp_debug_randomizer { +public: + __libcpp_debug_randomizer() { + __state = __seed(); + __inc = __state + 0xda3e39cb94b95bdbULL; + __inc = (__inc << 1) | 1; + } + typedef uint_fast32_t result_type; + + static const result_type _Min = 0; + static const result_type _Max = 0xFFFFFFFF; + + _LIBCPP_HIDE_FROM_ABI result_type operator()() { + uint_fast64_t __oldstate = __state; + __state = __oldstate * 6364136223846793005ULL + __inc; + return __oldstate >> 32; + } + + static _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR result_type min() { return _Min; } + static _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR result_type max() { return _Max; } + +private: + uint_fast64_t __state; + uint_fast64_t __inc; + _LIBCPP_HIDE_FROM_ABI static uint_fast64_t __seed() { +#ifdef _LIBCPP_DEBUG_RANDOMIZE_UNSPECIFIED_STABILITY_SEED + return _LIBCPP_DEBUG_RANDOMIZE_UNSPECIFIED_STABILITY_SEED; +#else + static char __x; + return reinterpret_cast<uintptr_t>(&__x); +#endif + } +}; #if _LIBCPP_STD_VER <= 14 || defined(_LIBCPP_ENABLE_CXX17_REMOVED_RANDOM_SHUFFLE) \ || defined(_LIBCPP_BUILDING_LIBRARY) diff --git a/lib/libcxx/include/__algorithm/sift_down.h b/lib/libcxx/include/__algorithm/sift_down.h index dd4b54ed8e..bf5447698c 100644 --- a/lib/libcxx/include/__algorithm/sift_down.h +++ b/lib/libcxx/include/__algorithm/sift_down.h @@ -17,15 +17,11 @@ #pragma GCC system_header #endif -_LIBCPP_PUSH_MACROS -#include <__undef_macros> - _LIBCPP_BEGIN_NAMESPACE_STD template <class _Compare, class _RandomAccessIterator> _LIBCPP_CONSTEXPR_AFTER_CXX11 void -__sift_down(_RandomAccessIterator __first, _RandomAccessIterator /*__last*/, - _Compare __comp, +__sift_down(_RandomAccessIterator __first, _Compare __comp, typename iterator_traits<_RandomAccessIterator>::difference_type __len, _RandomAccessIterator __start) { @@ -41,7 +37,7 @@ __sift_down(_RandomAccessIterator __first, _RandomAccessIterator /*__last*/, __child = 2 * __child + 1; _RandomAccessIterator __child_i = __first + __child; - if ((__child + 1) < __len && __comp(*__child_i, *(__child_i + 1))) { + if ((__child + 1) < __len && __comp(*__child_i, *(__child_i + difference_type(1)))) { // right-child exists and is greater than left-child ++__child_i; ++__child; @@ -49,7 +45,7 @@ __sift_down(_RandomAccessIterator __first, _RandomAccessIterator /*__last*/, // check if we are in heap-order if (__comp(*__child_i, *__start)) - // we are, __start is larger than it's largest child + // we are, __start is larger than its largest child return; value_type __top(_VSTD::move(*__start)); @@ -66,7 +62,7 @@ __sift_down(_RandomAccessIterator __first, _RandomAccessIterator /*__last*/, __child = 2 * __child + 1; __child_i = __first + __child; - if ((__child + 1) < __len && __comp(*__child_i, *(__child_i + 1))) { + if ((__child + 1) < __len && __comp(*__child_i, *(__child_i + difference_type(1)))) { // right-child exists and is greater than left-child ++__child_i; ++__child; @@ -79,6 +75,4 @@ __sift_down(_RandomAccessIterator __first, _RandomAccessIterator /*__last*/, _LIBCPP_END_NAMESPACE_STD -_LIBCPP_POP_MACROS - #endif // _LIBCPP___ALGORITHM_SIFT_DOWN_H diff --git a/lib/libcxx/include/__algorithm/sort.h b/lib/libcxx/include/__algorithm/sort.h index 39ec21302d..5e09b28008 100644 --- a/lib/libcxx/include/__algorithm/sort.h +++ b/lib/libcxx/include/__algorithm/sort.h @@ -9,23 +9,23 @@ #ifndef _LIBCPP___ALGORITHM_SORT_H #define _LIBCPP___ALGORITHM_SORT_H -#include <__config> #include <__algorithm/comp.h> #include <__algorithm/comp_ref_type.h> #include <__algorithm/min_element.h> #include <__algorithm/partial_sort.h> #include <__algorithm/unwrap_iter.h> +#include <__config> #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 diff --git a/lib/libcxx/include/__algorithm/sort_heap.h b/lib/libcxx/include/__algorithm/sort_heap.h index aa8ef762ab..64291ff2e8 100644 --- a/lib/libcxx/include/__algorithm/sort_heap.h +++ b/lib/libcxx/include/__algorithm/sort_heap.h @@ -9,10 +9,10 @@ #ifndef _LIBCPP___ALGORITHM_SORT_HEAP_H #define _LIBCPP___ALGORITHM_SORT_HEAP_H -#include <__config> #include <__algorithm/comp.h> #include <__algorithm/comp_ref_type.h> #include <__algorithm/pop_heap.h> +#include <__config> #include <__iterator/iterator_traits.h> #include <type_traits> // swap @@ -20,9 +20,6 @@ #pragma GCC system_header #endif -_LIBCPP_PUSH_MACROS -#include <__undef_macros> - _LIBCPP_BEGIN_NAMESPACE_STD template <class _Compare, class _RandomAccessIterator> @@ -53,6 +50,4 @@ sort_heap(_RandomAccessIterator __first, _RandomAccessIterator __last) _LIBCPP_END_NAMESPACE_STD -_LIBCPP_POP_MACROS - #endif // _LIBCPP___ALGORITHM_SORT_HEAP_H diff --git a/lib/libcxx/include/__algorithm/stable_partition.h b/lib/libcxx/include/__algorithm/stable_partition.h index 931335f444..331f0fde77 100644 --- a/lib/libcxx/include/__algorithm/stable_partition.h +++ b/lib/libcxx/include/__algorithm/stable_partition.h @@ -9,8 +9,8 @@ #ifndef _LIBCPP___ALGORITHM_STABLE_PARTITION_H #define _LIBCPP___ALGORITHM_STABLE_PARTITION_H -#include <__config> #include <__algorithm/rotate.h> +#include <__config> #include <__iterator/iterator_traits.h> #include <__utility/swap.h> #include <memory> @@ -19,9 +19,6 @@ #pragma GCC system_header #endif -_LIBCPP_PUSH_MACROS -#include <__undef_macros> - _LIBCPP_BEGIN_NAMESPACE_STD template <class _Predicate, class _ForwardIterator, class _Distance, class _Pair> @@ -85,8 +82,7 @@ __stable_partition(_ForwardIterator __first, _ForwardIterator __last, _Predicate // recurse on [__first, __m), *__first know to be false // F????????????????? // f m l - typedef typename add_lvalue_reference<_Predicate>::type _PredRef; - _ForwardIterator __first_false = _VSTD::__stable_partition<_PredRef>(__first, __m, __pred, __len2, __p, __fit); + _ForwardIterator __first_false = _VSTD::__stable_partition<_Predicate&>(__first, __m, __pred, __len2, __p, __fit); // TTTFFFFF?????????? // f ff m l // recurse on [__m, __last], except increase __m until *(__m) is false, *__last know to be true @@ -101,7 +97,7 @@ __stable_partition(_ForwardIterator __first, _ForwardIterator __last, _Predicate } // TTTFFFFFTTTF?????? // f ff m m1 l - __second_false = _VSTD::__stable_partition<_PredRef>(__m1, __last, __pred, __len_half, __p, __fit); + __second_false = _VSTD::__stable_partition<_Predicate&>(__m1, __last, __pred, __len_half, __p, __fit); __second_half_done: // TTTFFFFFTTTTTFFFFF // f ff m sf l @@ -137,8 +133,7 @@ __stable_partition(_ForwardIterator __first, _ForwardIterator __last, _Predicate __p = _VSTD::get_temporary_buffer<value_type>(__len); __h.reset(__p.first); } - return _VSTD::__stable_partition<typename add_lvalue_reference<_Predicate>::type> - (__first, __last, __pred, __len, __p, forward_iterator_tag()); + return _VSTD::__stable_partition<_Predicate&>(__first, __last, __pred, __len, __p, forward_iterator_tag()); } template <class _Predicate, class _BidirectionalIterator, class _Distance, class _Pair> @@ -222,8 +217,7 @@ __stable_partition(_BidirectionalIterator __first, _BidirectionalIterator __last } // F???TFFF?????????T // f m1 m l - typedef typename add_lvalue_reference<_Predicate>::type _PredRef; - __first_false = _VSTD::__stable_partition<_PredRef>(__first, __m1, __pred, __len_half, __p, __bit); + __first_false = _VSTD::__stable_partition<_Predicate&>(__first, __m1, __pred, __len_half, __p, __bit); __first_half_done: // TTTFFFFF?????????T // f ff m l @@ -240,7 +234,7 @@ __first_half_done: } // TTTFFFFFTTTF?????T // f ff m m1 l - __second_false = _VSTD::__stable_partition<_PredRef>(__m1, __last, __pred, __len_half, __p, __bit); + __second_false = _VSTD::__stable_partition<_Predicate&>(__m1, __last, __pred, __len_half, __p, __bit); __second_half_done: // TTTFFFFFTTTTTFFFFF // f ff m sf l @@ -285,8 +279,7 @@ __stable_partition(_BidirectionalIterator __first, _BidirectionalIterator __last __p = _VSTD::get_temporary_buffer<value_type>(__len); __h.reset(__p.first); } - return _VSTD::__stable_partition<typename add_lvalue_reference<_Predicate>::type> - (__first, __last, __pred, __len, __p, bidirectional_iterator_tag()); + return _VSTD::__stable_partition<_Predicate&>(__first, __last, __pred, __len, __p, bidirectional_iterator_tag()); } template <class _ForwardIterator, class _Predicate> @@ -294,12 +287,9 @@ inline _LIBCPP_INLINE_VISIBILITY _ForwardIterator stable_partition(_ForwardIterator __first, _ForwardIterator __last, _Predicate __pred) { - return _VSTD::__stable_partition<typename add_lvalue_reference<_Predicate>::type> - (__first, __last, __pred, typename iterator_traits<_ForwardIterator>::iterator_category()); + return _VSTD::__stable_partition<_Predicate&>(__first, __last, __pred, typename iterator_traits<_ForwardIterator>::iterator_category()); } _LIBCPP_END_NAMESPACE_STD -_LIBCPP_POP_MACROS - #endif // _LIBCPP___ALGORITHM_STABLE_PARTITION_H diff --git a/lib/libcxx/include/__algorithm/stable_sort.h b/lib/libcxx/include/__algorithm/stable_sort.h index 32b239a0d7..4ae17e0e4d 100644 --- a/lib/libcxx/include/__algorithm/stable_sort.h +++ b/lib/libcxx/include/__algorithm/stable_sort.h @@ -9,23 +9,20 @@ #ifndef _LIBCPP___ALGORITHM_STABLE_SORT_H #define _LIBCPP___ALGORITHM_STABLE_SORT_H -#include <__config> #include <__algorithm/comp.h> #include <__algorithm/comp_ref_type.h> #include <__algorithm/inplace_merge.h> #include <__algorithm/sort.h> +#include <__config> #include <__iterator/iterator_traits.h> #include <__utility/swap.h> #include <memory> -#include <type_traits> // swap +#include <type_traits> #if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER) #pragma GCC system_header #endif -_LIBCPP_PUSH_MACROS -#include <__undef_macros> - _LIBCPP_BEGIN_NAMESPACE_STD template <class _Compare, class _InputIterator1, class _InputIterator2> @@ -41,14 +38,14 @@ __merge_move_construct(_InputIterator1 __first1, _InputIterator1 __last1, { if (__first1 == __last1) { - for (; __first2 != __last2; ++__first2, ++__result, (void)__d.template __incr<value_type>()) + for (; __first2 != __last2; ++__first2, (void) ++__result, __d.template __incr<value_type>()) ::new ((void*)__result) value_type(_VSTD::move(*__first2)); __h.release(); return; } if (__first2 == __last2) { - for (; __first1 != __last1; ++__first1, ++__result, (void)__d.template __incr<value_type>()) + for (; __first1 != __last1; ++__first1, (void) ++__result, __d.template __incr<value_type>()) ::new ((void*)__result) value_type(_VSTD::move(*__first1)); __h.release(); return; @@ -230,6 +227,4 @@ stable_sort(_RandomAccessIterator __first, _RandomAccessIterator __last) _LIBCPP_END_NAMESPACE_STD -_LIBCPP_POP_MACROS - #endif // _LIBCPP___ALGORITHM_STABLE_SORT_H diff --git a/lib/libcxx/include/__algorithm/swap_ranges.h b/lib/libcxx/include/__algorithm/swap_ranges.h index 3c72dbd24c..2b099c7361 100644 --- a/lib/libcxx/include/__algorithm/swap_ranges.h +++ b/lib/libcxx/include/__algorithm/swap_ranges.h @@ -17,9 +17,6 @@ #pragma GCC system_header #endif -_LIBCPP_PUSH_MACROS -#include <__undef_macros> - _LIBCPP_BEGIN_NAMESPACE_STD template <class _ForwardIterator1, class _ForwardIterator2> @@ -32,6 +29,4 @@ swap_ranges(_ForwardIterator1 __first1, _ForwardIterator1 __last1, _ForwardItera _LIBCPP_END_NAMESPACE_STD -_LIBCPP_POP_MACROS - #endif // _LIBCPP___ALGORITHM_SWAP_RANGES_H diff --git a/lib/libcxx/include/__algorithm/transform.h b/lib/libcxx/include/__algorithm/transform.h index 218f0f12ea..494cb7128d 100644 --- a/lib/libcxx/include/__algorithm/transform.h +++ b/lib/libcxx/include/__algorithm/transform.h @@ -15,9 +15,6 @@ #pragma GCC system_header #endif -_LIBCPP_PUSH_MACROS -#include <__undef_macros> - _LIBCPP_BEGIN_NAMESPACE_STD template <class _InputIterator, class _OutputIterator, class _UnaryOperation> @@ -43,6 +40,4 @@ transform(_InputIterator1 __first1, _InputIterator1 __last1, _InputIterator2 __f _LIBCPP_END_NAMESPACE_STD -_LIBCPP_POP_MACROS - #endif // _LIBCPP___ALGORITHM_TRANSFORM_H diff --git a/lib/libcxx/include/__algorithm/unique.h b/lib/libcxx/include/__algorithm/unique.h index fb6251a39a..e17ff1567f 100644 --- a/lib/libcxx/include/__algorithm/unique.h +++ b/lib/libcxx/include/__algorithm/unique.h @@ -9,20 +9,16 @@ #ifndef _LIBCPP___ALGORITHM_UNIQUE_H #define _LIBCPP___ALGORITHM_UNIQUE_H -#include <__config> -#include <__algorithm/comp.h> #include <__algorithm/adjacent_find.h> +#include <__algorithm/comp.h> +#include <__config> #include <__iterator/iterator_traits.h> #include <__utility/move.h> -#include <type_traits> #if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER) #pragma GCC system_header #endif -_LIBCPP_PUSH_MACROS -#include <__undef_macros> - _LIBCPP_BEGIN_NAMESPACE_STD // unique @@ -31,8 +27,7 @@ template <class _ForwardIterator, class _BinaryPredicate> _LIBCPP_NODISCARD_EXT _LIBCPP_CONSTEXPR_AFTER_CXX17 _ForwardIterator unique(_ForwardIterator __first, _ForwardIterator __last, _BinaryPredicate __pred) { - __first = _VSTD::adjacent_find<_ForwardIterator, typename add_lvalue_reference<_BinaryPredicate>::type> - (__first, __last, __pred); + __first = _VSTD::adjacent_find<_ForwardIterator, _BinaryPredicate&>(__first, __last, __pred); if (__first != __last) { // ... a a ? ... @@ -58,6 +53,4 @@ unique(_ForwardIterator __first, _ForwardIterator __last) _LIBCPP_END_NAMESPACE_STD -_LIBCPP_POP_MACROS - #endif // _LIBCPP___ALGORITHM_UNIQUE_H diff --git a/lib/libcxx/include/__algorithm/unique_copy.h b/lib/libcxx/include/__algorithm/unique_copy.h index 974a7c4df2..4833ae9b59 100644 --- a/lib/libcxx/include/__algorithm/unique_copy.h +++ b/lib/libcxx/include/__algorithm/unique_copy.h @@ -9,19 +9,15 @@ #ifndef _LIBCPP___ALGORITHM_UNIQUE_COPY_H #define _LIBCPP___ALGORITHM_UNIQUE_COPY_H -#include <__config> #include <__algorithm/comp.h> +#include <__config> #include <__iterator/iterator_traits.h> #include <utility> -#include <type_traits> #if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER) #pragma GCC system_header #endif -_LIBCPP_PUSH_MACROS -#include <__undef_macros> - _LIBCPP_BEGIN_NAMESPACE_STD template <class _BinaryPredicate, class _InputIterator, class _OutputIterator> @@ -91,8 +87,7 @@ inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17 _OutputIterator unique_copy(_InputIterator __first, _InputIterator __last, _OutputIterator __result, _BinaryPredicate __pred) { - return _VSTD::__unique_copy<typename add_lvalue_reference<_BinaryPredicate>::type> - (__first, __last, __result, __pred, + return _VSTD::__unique_copy<_BinaryPredicate&>(__first, __last, __result, __pred, typename iterator_traits<_InputIterator>::iterator_category(), typename iterator_traits<_OutputIterator>::iterator_category()); } @@ -109,6 +104,4 @@ unique_copy(_InputIterator __first, _InputIterator __last, _OutputIterator __res _LIBCPP_END_NAMESPACE_STD -_LIBCPP_POP_MACROS - #endif // _LIBCPP___ALGORITHM_UNIQUE_COPY_H diff --git a/lib/libcxx/include/__algorithm/unwrap_iter.h b/lib/libcxx/include/__algorithm/unwrap_iter.h index a45d45cdd8..35765330bb 100644 --- a/lib/libcxx/include/__algorithm/unwrap_iter.h +++ b/lib/libcxx/include/__algorithm/unwrap_iter.h @@ -10,17 +10,14 @@ #define _LIBCPP___ALGORITHM_UNWRAP_ITER_H #include <__config> -#include <iterator> #include <__memory/pointer_traits.h> +#include <iterator> #include <type_traits> #if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER) #pragma GCC system_header #endif -_LIBCPP_PUSH_MACROS -#include <__undef_macros> - _LIBCPP_BEGIN_NAMESPACE_STD // The job of __unwrap_iter is to lower contiguous iterators (such as @@ -67,12 +64,14 @@ __unwrap_iter(_Iter __i) _NOEXCEPT } template<class _OrigIter> +_LIBCPP_HIDE_FROM_ABI _OrigIter __rewrap_iter(_OrigIter, _OrigIter __result) { return __result; } template<class _OrigIter, class _UnwrappedIter> +_LIBCPP_HIDE_FROM_ABI _OrigIter __rewrap_iter(_OrigIter __first, _UnwrappedIter __result) { // Precondition: __result is reachable from __first @@ -82,6 +81,4 @@ _OrigIter __rewrap_iter(_OrigIter __first, _UnwrappedIter __result) _LIBCPP_END_NAMESPACE_STD -_LIBCPP_POP_MACROS - #endif // _LIBCPP___ALGORITHM_UNWRAP_ITER_H diff --git a/lib/libcxx/include/__algorithm/upper_bound.h b/lib/libcxx/include/__algorithm/upper_bound.h index 7be607f825..c064f1e35b 100644 --- a/lib/libcxx/include/__algorithm/upper_bound.h +++ b/lib/libcxx/include/__algorithm/upper_bound.h @@ -9,18 +9,15 @@ #ifndef _LIBCPP___ALGORITHM_UPPER_BOUND_H #define _LIBCPP___ALGORITHM_UPPER_BOUND_H -#include <__config> #include <__algorithm/comp.h> #include <__algorithm/half_positive.h> +#include <__config> #include <iterator> #if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER) #pragma GCC system_header #endif -_LIBCPP_PUSH_MACROS -#include <__undef_macros> - _LIBCPP_BEGIN_NAMESPACE_STD template <class _Compare, class _ForwardIterator, class _Tp> @@ -51,8 +48,7 @@ _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17 _ForwardIterator upper_bound(_ForwardIterator __first, _ForwardIterator __last, const _Tp& __value_, _Compare __comp) { - typedef typename add_lvalue_reference<_Compare>::type _Comp_ref; - return _VSTD::__upper_bound<_Comp_ref>(__first, __last, __value_, __comp); + return _VSTD::__upper_bound<_Compare&>(__first, __last, __value_, __comp); } template <class _ForwardIterator, class _Tp> @@ -67,6 +63,4 @@ upper_bound(_ForwardIterator __first, _ForwardIterator __last, const _Tp& __valu _LIBCPP_END_NAMESPACE_STD -_LIBCPP_POP_MACROS - #endif // _LIBCPP___ALGORITHM_UPPER_BOUND_H |