diff --git a/libcxx/include/CMakeLists.txt b/libcxx/include/CMakeLists.txt --- a/libcxx/include/CMakeLists.txt +++ b/libcxx/include/CMakeLists.txt @@ -1,5 +1,6 @@ set(files __algorithm/adjacent_find.h + __algorithm/algorithm_family.h __algorithm/all_of.h __algorithm/any_of.h __algorithm/binary_search.h diff --git a/libcxx/include/__algorithm/algorithm_family.h b/libcxx/include/__algorithm/algorithm_family.h new file mode 100644 --- /dev/null +++ b/libcxx/include/__algorithm/algorithm_family.h @@ -0,0 +1,52 @@ +//===----------------------------------------------------------------------===// +// +// 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_ALGORITHM_FAMILY_H +#define _LIBCPP___ALGORITHM_ALGORITHM_FAMILY_H + +#include <__algorithm/iterator_operations.h> +#include <__algorithm/move.h> +#include <__algorithm/ranges_move.h> +#include <__config> +#include <__utility/move.h> + +#if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER) +# pragma GCC system_header +#endif + +_LIBCPP_BEGIN_NAMESPACE_STD + +template +struct _AlgoFamily; + +#if _LIBCPP_STD_VER > 17 && !defined(_LIBCPP_HAS_NO_INCOMPLETE_RANGES) + +template <> +struct _AlgoFamily<_RangeAlgPolicy> { + static constexpr auto __move = ranges::move; +}; + +#endif + +template <> +struct _AlgoFamily<_ClassicAlgPolicy> { + + // move + template + _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_AFTER_CXX17 static _OutputIterator + __move(_InputIterator __first, _InputIterator __last, _OutputIterator __result) { + return std::move( + std::move(__first), + std::move(__last), + std::move(__result)); + } +}; + +_LIBCPP_END_NAMESPACE_STD + +#endif // _LIBCPP___ALGORITHM_ALGORITHM_FAMILY_H diff --git a/libcxx/include/__algorithm/inplace_merge.h b/libcxx/include/__algorithm/inplace_merge.h --- a/libcxx/include/__algorithm/inplace_merge.h +++ b/libcxx/include/__algorithm/inplace_merge.h @@ -9,6 +9,7 @@ #ifndef _LIBCPP___ALGORITHM_INPLACE_MERGE_H #define _LIBCPP___ALGORITHM_INPLACE_MERGE_H +#include <__algorithm/algorithm_family.h> #include <__algorithm/comp.h> #include <__algorithm/comp_ref_type.h> #include <__algorithm/iterator_operations.h> @@ -38,204 +39,199 @@ class __invert // invert the sense of a comparison { private: - _Predicate __p_; + _Predicate __p_; + public: - _LIBCPP_INLINE_VISIBILITY __invert() {} + _LIBCPP_HIDE_FROM_ABI __invert() {} - _LIBCPP_INLINE_VISIBILITY - explicit __invert(_Predicate __p) : __p_(__p) {} + _LIBCPP_HIDE_FROM_ABI explicit __invert(_Predicate __p) : __p_(__p) {} - template - _LIBCPP_INLINE_VISIBILITY - bool operator()(const _T1& __x) {return !__p_(__x);} + template + _LIBCPP_HIDE_FROM_ABI bool operator()(const _T1& __x) { + return !__p_(__x); + } - template - _LIBCPP_INLINE_VISIBILITY - bool operator()(const _T1& __x, const _T2& __y) {return __p_(__y, __x);} + template + _LIBCPP_HIDE_FROM_ABI bool operator()(const _T1& __x, const _T2& __y) { + return __p_(__y, __x); + } }; -template -void __half_inplace_merge(_InputIterator1 __first1, _InputIterator1 __last1, - _InputIterator2 __first2, _InputIterator2 __last2, - _OutputIterator __result, _Compare __comp) -{ - for (; __first1 != __last1; ++__result) - { - if (__first2 == __last2) - { - // TODO(alg-policy): pass `_AlgPolicy` once it's supported by `move`. - _VSTD::move(__first1, __last1, __result); - return; - } - - if (__comp(*__first2, *__first1)) - { - *__result = _IterOps<_AlgPolicy>::__iter_move(__first2); - ++__first2; - } - else - { - *__result = _IterOps<_AlgPolicy>::__iter_move(__first1); - ++__first1; - } +template < + class _AlgPolicy, + class _Compare, + class _InputIterator1, + class _Sent1, + class _InputIterator2, + class _Sent2, + class _OutputIterator> +_LIBCPP_HIDE_FROM_ABI void __half_inplace_merge( + _InputIterator1 __first1, + _Sent1 __last1, + _InputIterator2 __first2, + _Sent2 __last2, + _OutputIterator __result, + _Compare&& __comp) { + for (; __first1 != __last1; ++__result) { + if (__first2 == __last2) { + _AlgoFamily<_AlgPolicy>::__move(__first1, __last1, __result); + return; + } + + if (__comp(*__first2, *__first1)) { + *__result = _IterOps<_AlgPolicy>::__iter_move(__first2); + ++__first2; + } else { + *__result = _IterOps<_AlgPolicy>::__iter_move(__first1); + ++__first1; } - // __first2 through __last2 are already in the right spot. + } + // __first2 through __last2 are already in the right spot. } template -void -__buffered_inplace_merge(_BidirectionalIterator __first, _BidirectionalIterator __middle, _BidirectionalIterator __last, - _Compare __comp, typename iterator_traits<_BidirectionalIterator>::difference_type __len1, - typename iterator_traits<_BidirectionalIterator>::difference_type __len2, - typename iterator_traits<_BidirectionalIterator>::value_type* __buff) -{ - typedef typename iterator_traits<_BidirectionalIterator>::value_type value_type; - __destruct_n __d(0); - unique_ptr __h2(__buff, __d); - if (__len1 <= __len2) - { - value_type* __p = __buff; - for (_BidirectionalIterator __i = __first; __i != __middle; __d.template __incr(), (void) ++__i, (void) ++__p) - ::new ((void*)__p) value_type(_IterOps<_AlgPolicy>::__iter_move(__i)); - std::__half_inplace_merge<_AlgPolicy, _Compare>(__buff, __p, __middle, __last, __first, __comp); - } - else - { - value_type* __p = __buff; - for (_BidirectionalIterator __i = __middle; __i != __last; __d.template __incr(), (void) ++__i, (void) ++__p) - ::new ((void*)__p) value_type(_IterOps<_AlgPolicy>::__iter_move(__i)); - typedef __unconstrained_reverse_iterator<_BidirectionalIterator> _RBi; - typedef __unconstrained_reverse_iterator _Rv; - typedef __invert<_Compare> _Inverted; - std::__half_inplace_merge<_AlgPolicy, _Inverted>(_Rv(__p), _Rv(__buff), - _RBi(__middle), _RBi(__first), - _RBi(__last), _Inverted(__comp)); - } +_LIBCPP_HIDE_FROM_ABI void __buffered_inplace_merge( + _BidirectionalIterator __first, + _BidirectionalIterator __middle, + _BidirectionalIterator __last, + _Compare&& __comp, + typename iterator_traits<_BidirectionalIterator>::difference_type __len1, + typename iterator_traits<_BidirectionalIterator>::difference_type __len2, + typename iterator_traits<_BidirectionalIterator>::value_type* __buff) { + typedef typename iterator_traits<_BidirectionalIterator>::value_type value_type; + __destruct_n __d(0); + unique_ptr __h2(__buff, __d); + if (__len1 <= __len2) { + value_type* __p = __buff; + for (_BidirectionalIterator __i = __first; __i != __middle; + __d.template __incr(), (void)++__i, (void)++__p) + ::new ((void*)__p) value_type(_IterOps<_AlgPolicy>::__iter_move(__i)); + std::__half_inplace_merge<_AlgPolicy>(__buff, __p, __middle, __last, __first, __comp); + } else { + value_type* __p = __buff; + for (_BidirectionalIterator __i = __middle; __i != __last; + __d.template __incr(), (void)++__i, (void)++__p) + ::new ((void*)__p) value_type(_IterOps<_AlgPolicy>::__iter_move(__i)); + typedef __unconstrained_reverse_iterator<_BidirectionalIterator> _RBi; + typedef __unconstrained_reverse_iterator _Rv; + typedef __invert<_Compare> _Inverted; + std::__half_inplace_merge<_AlgPolicy>( + _Rv(__p), _Rv(__buff), _RBi(__middle), _RBi(__first), _RBi(__last), _Inverted(__comp)); + } } template -void -__inplace_merge(_BidirectionalIterator __first, _BidirectionalIterator __middle, _BidirectionalIterator __last, - _Compare __comp, typename iterator_traits<_BidirectionalIterator>::difference_type __len1, - typename iterator_traits<_BidirectionalIterator>::difference_type __len2, - typename iterator_traits<_BidirectionalIterator>::value_type* __buff, ptrdiff_t __buff_size) -{ - using _Ops = _IterOps<_AlgPolicy>; - - typedef typename iterator_traits<_BidirectionalIterator>::difference_type difference_type; - while (true) - { - // if __middle == __last, we're done - if (__len2 == 0) - return; - if (__len1 <= __buff_size || __len2 <= __buff_size) - return std::__buffered_inplace_merge<_AlgPolicy, _Compare> - (__first, __middle, __last, __comp, __len1, __len2, __buff); - // shrink [__first, __middle) as much as possible (with no moves), returning if it shrinks to 0 - for (; true; ++__first, (void) --__len1) - { - if (__len1 == 0) - return; - if (__comp(*__middle, *__first)) - break; - } - // __first < __middle < __last - // *__first > *__middle - // partition [__first, __m1) [__m1, __middle) [__middle, __m2) [__m2, __last) such that - // all elements in: - // [__first, __m1) <= [__middle, __m2) - // [__middle, __m2) < [__m1, __middle) - // [__m1, __middle) <= [__m2, __last) - // and __m1 or __m2 is in the middle of its range - _BidirectionalIterator __m1; // "median" of [__first, __middle) - _BidirectionalIterator __m2; // "median" of [__middle, __last) - difference_type __len11; // distance(__first, __m1) - difference_type __len21; // distance(__middle, __m2) - // binary search smaller range - if (__len1 < __len2) - { // __len >= 1, __len2 >= 2 - __len21 = __len2 / 2; - __m2 = __middle; - _Ops::advance(__m2, __len21); - // TODO: replace _ClassicAlgPolicy and __identity with _AlgPolicy and projection - __m1 = std::__upper_bound<_ClassicAlgPolicy>(__first, __middle, *__m2, __comp, std::__identity()); - __len11 = _Ops::distance(__first, __m1); - } - else - { - if (__len1 == 1) - { // __len1 >= __len2 && __len2 > 0, therefore __len2 == 1 - // It is known *__first > *__middle - _Ops::iter_swap(__first, __middle); - return; - } - // __len1 >= 2, __len2 >= 1 - __len11 = __len1 / 2; - __m1 = __first; - _Ops::advance(__m1, __len11); - __m2 = std::lower_bound(__middle, __last, *__m1, __comp); - __len21 = _Ops::distance(__middle, __m2); - } - difference_type __len12 = __len1 - __len11; // distance(__m1, __middle) - difference_type __len22 = __len2 - __len21; // distance(__m2, __last) - // [__first, __m1) [__m1, __middle) [__middle, __m2) [__m2, __last) - // swap middle two partitions - // TODO(alg-policy): pass `_AlgPolicy` once it's supported by `rotate`. - __middle = _VSTD::rotate(__m1, __middle, __m2); - // __len12 and __len21 now have swapped meanings - // merge smaller range with recursive call and larger with tail recursion elimination - if (__len11 + __len21 < __len12 + __len22) - { - std::__inplace_merge<_AlgPolicy, _Compare>( - __first, __m1, __middle, __comp, __len11, __len21, __buff, __buff_size); -// _VSTD::__inplace_merge<_Compare>(__middle, __m2, __last, __comp, __len12, __len22, __buff, __buff_size); - __first = __middle; - __middle = __m2; - __len1 = __len12; - __len2 = __len22; - } - else - { - std::__inplace_merge<_AlgPolicy, _Compare>( - __middle, __m2, __last, __comp, __len12, __len22, __buff, __buff_size); -// _VSTD::__inplace_merge<_Compare>(__first, __m1, __middle, __comp, __len11, __len21, __buff, __buff_size); - __last = __middle; - __middle = __m1; - __len1 = __len11; - __len2 = __len21; - } + void __inplace_merge( + _BidirectionalIterator __first, + _BidirectionalIterator __middle, + _BidirectionalIterator __last, + _Compare&& __comp, + typename iterator_traits<_BidirectionalIterator>::difference_type __len1, + typename iterator_traits<_BidirectionalIterator>::difference_type __len2, + typename iterator_traits<_BidirectionalIterator>::value_type* __buff, + ptrdiff_t __buff_size) { + using _Ops = _IterOps<_AlgPolicy>; + + typedef typename iterator_traits<_BidirectionalIterator>::difference_type difference_type; + while (true) { + // if __middle == __last, we're done + if (__len2 == 0) + return; + if (__len1 <= __buff_size || __len2 <= __buff_size) + return std::__buffered_inplace_merge<_AlgPolicy>(__first, __middle, __last, __comp, __len1, __len2, __buff); + // shrink [__first, __middle) as much as possible (with no moves), returning if it shrinks to 0 + for (; true; ++__first, (void)--__len1) { + if (__len1 == 0) + return; + if (__comp(*__middle, *__first)) + break; + } + // __first < __middle < __last + // *__first > *__middle + // partition [__first, __m1) [__m1, __middle) [__middle, __m2) [__m2, __last) such that + // all elements in: + // [__first, __m1) <= [__middle, __m2) + // [__middle, __m2) < [__m1, __middle) + // [__m1, __middle) <= [__m2, __last) + // and __m1 or __m2 is in the middle of its range + _BidirectionalIterator __m1; // "median" of [__first, __middle) + _BidirectionalIterator __m2; // "median" of [__middle, __last) + difference_type __len11; // distance(__first, __m1) + difference_type __len21; // distance(__middle, __m2) + // binary search smaller range + if (__len1 < __len2) { // __len >= 1, __len2 >= 2 + __len21 = __len2 / 2; + __m2 = __middle; + _Ops::advance(__m2, __len21); + // TODO: replace _ClassicAlgPolicy and __identity with _AlgPolicy and projection + __m1 = std::__upper_bound<_ClassicAlgPolicy>(__first, __middle, *__m2, __comp, std::__identity()); + __len11 = _Ops::distance(__first, __m1); + } else { + if (__len1 == 1) { // __len1 >= __len2 && __len2 > 0, therefore __len2 == 1 + // It is known *__first > *__middle + _Ops::iter_swap(__first, __middle); + return; + } + // __len1 >= 2, __len2 >= 1 + __len11 = __len1 / 2; + __m1 = __first; + _Ops::advance(__m1, __len11); + __m2 = std::lower_bound(__middle, __last, *__m1, __comp); + __len21 = _Ops::distance(__middle, __m2); } + difference_type __len12 = __len1 - __len11; // distance(__m1, __middle) + difference_type __len22 = __len2 - __len21; // distance(__m2, __last) + // [__first, __m1) [__m1, __middle) [__middle, __m2) [__m2, __last) + // swap middle two partitions + // TODO(alg-policy): pass `_AlgPolicy` once it's supported by `rotate`. + __middle = _VSTD::rotate(__m1, __middle, __m2); + // __len12 and __len21 now have swapped meanings + // merge smaller range with recursive call and larger with tail recursion elimination + if (__len11 + __len21 < __len12 + __len22) { + std::__inplace_merge<_AlgPolicy>(__first, __m1, __middle, __comp, __len11, __len21, __buff, __buff_size); + __first = __middle; + __middle = __m2; + __len1 = __len12; + __len2 = __len22; + } else { + std::__inplace_merge<_AlgPolicy>(__middle, __m2, __last, __comp, __len12, __len22, __buff, __buff_size); + __last = __middle; + __middle = __m1; + __len1 = __len11; + __len2 = __len21; + } + } +} + +template +_LIBCPP_HIDE_FROM_ABI void __inplace_merge( + _BidirectionalIterator __first, _BidirectionalIterator __middle, _BidirectionalIterator __last, _Compare&& __comp) { + typedef typename iterator_traits<_BidirectionalIterator>::value_type value_type; + typedef typename iterator_traits<_BidirectionalIterator>::difference_type difference_type; + difference_type __len1 = _IterOps<_AlgPolicy>::distance(__first, __middle); + difference_type __len2 = _IterOps<_AlgPolicy>::distance(__middle, __last); + difference_type __buf_size = _VSTD::min(__len1, __len2); + // TODO: Remove the use of std::get_temporary_buffer + _LIBCPP_SUPPRESS_DEPRECATED_PUSH + pair __buf = _VSTD::get_temporary_buffer(__buf_size); + _LIBCPP_SUPPRESS_DEPRECATED_POP + unique_ptr __h(__buf.first); + std::__inplace_merge<_AlgPolicy>( + std::move(__first), std::move(__middle), std::move(__last), __comp, __len1, __len2, __buf.first, __buf.second); } template -inline _LIBCPP_INLINE_VISIBILITY -void -inplace_merge(_BidirectionalIterator __first, _BidirectionalIterator __middle, _BidirectionalIterator __last, - _Compare __comp) -{ - typedef typename iterator_traits<_BidirectionalIterator>::value_type value_type; - typedef typename iterator_traits<_BidirectionalIterator>::difference_type difference_type; - difference_type __len1 = _VSTD::distance(__first, __middle); - difference_type __len2 = _VSTD::distance(__middle, __last); - difference_type __buf_size = _VSTD::min(__len1, __len2); -// TODO: Remove the use of std::get_temporary_buffer -_LIBCPP_SUPPRESS_DEPRECATED_PUSH - pair __buf = _VSTD::get_temporary_buffer(__buf_size); -_LIBCPP_SUPPRESS_DEPRECATED_POP - unique_ptr __h(__buf.first); - typedef typename __comp_ref_type<_Compare>::type _Comp_ref; - return _VSTD::__inplace_merge<_ClassicAlgPolicy, _Comp_ref>(__first, __middle, __last, __comp, __len1, __len2, - __buf.first, __buf.second); +inline _LIBCPP_HIDE_FROM_ABI void inplace_merge( + _BidirectionalIterator __first, _BidirectionalIterator __middle, _BidirectionalIterator __last, _Compare __comp) { + typedef typename __comp_ref_type<_Compare>::type _Comp_ref; + std::__inplace_merge<_ClassicAlgPolicy>( + std::move(__first), std::move(__middle), std::move(__last), static_cast<_Comp_ref>(__comp)); } template -inline _LIBCPP_INLINE_VISIBILITY -void -inplace_merge(_BidirectionalIterator __first, _BidirectionalIterator __middle, _BidirectionalIterator __last) -{ - _VSTD::inplace_merge(__first, __middle, __last, - __less::value_type>()); +inline _LIBCPP_HIDE_FROM_ABI void +inplace_merge(_BidirectionalIterator __first, _BidirectionalIterator __middle, _BidirectionalIterator __last) { + std::inplace_merge(__first, __middle, __last, __less::value_type>()); } _LIBCPP_END_NAMESPACE_STD diff --git a/libcxx/include/__algorithm/ranges_inplace_merge.h b/libcxx/include/__algorithm/ranges_inplace_merge.h --- a/libcxx/include/__algorithm/ranges_inplace_merge.h +++ b/libcxx/include/__algorithm/ranges_inplace_merge.h @@ -10,6 +10,7 @@ #define _LIBCPP___ALGORITHM_RANGES_INPLACE_MERGE_H #include <__algorithm/inplace_merge.h> +#include <__algorithm/iterator_operations.h> #include <__algorithm/make_projected.h> #include <__config> #include <__functional/identity.h> @@ -17,6 +18,7 @@ #include <__functional/ranges_operations.h> #include <__iterator/concepts.h> #include <__iterator/iterator_traits.h> +#include <__iterator/next.h> #include <__iterator/projected.h> #include <__iterator/sortable.h> #include <__ranges/access.h> @@ -36,28 +38,38 @@ namespace ranges { namespace __inplace_merge { -struct __fn { + struct __fn { + template + _LIBCPP_HIDE_FROM_ABI static constexpr auto + __inplace_merge_impl(_Iter __first, _Iter __middle, _Sent __last, _Comp&& __comp, _Proj&& __proj) { + auto __last_iter = ranges::next(__middle, __last); + std::__inplace_merge<_RangeAlgPolicy>( + std::move(__first), std::move(__middle), __last_iter, ranges::__make_projected_comp(__comp, __proj)); + return __last_iter; + } - template _Sent, class _Comp = ranges::less, class _Proj = identity> - requires sortable<_Iter, _Comp, _Proj> - _LIBCPP_HIDE_FROM_ABI - _Iter operator()(_Iter __first, _Iter __middle, _Sent __last, _Comp __comp = {}, _Proj __proj = {}) const { - // TODO: implement - (void)__first; (void)__middle; (void)__last; (void)__comp; (void)__proj; - return {}; - } + template < + bidirectional_iterator _Iter, + sentinel_for<_Iter> _Sent, + class _Comp = ranges::less, + class _Proj = identity> + requires sortable<_Iter, _Comp, _Proj> + _LIBCPP_HIDE_FROM_ABI _Iter + operator()(_Iter __first, _Iter __middle, _Sent __last, _Comp __comp = {}, _Proj __proj = {}) const { + return __inplace_merge_impl( + std::move(__first), std::move(__middle), std::move(__last), std::move(__comp), std::move(__proj)); + } - template - requires sortable, _Comp, _Proj> - _LIBCPP_HIDE_FROM_ABI - borrowed_iterator_t<_Range> operator()(_Range&& __range, iterator_t<_Range> __middle, - _Comp __comp = {}, _Proj __proj = {}) const { - // TODO: implement - (void)__range; (void)__middle; (void)__comp; (void)__proj; - return {}; - } - -}; + template + requires sortable< + iterator_t<_Range>, + _Comp, + _Proj> _LIBCPP_HIDE_FROM_ABI borrowed_iterator_t<_Range> + operator()(_Range&& __range, iterator_t<_Range> __middle, _Comp __comp = {}, _Proj __proj = {}) const { + return __inplace_merge_impl( + ranges::begin(__range), std::move(__middle), ranges::end(__range), std::move(__comp), std::move(__proj)); + } + }; } // namespace __inplace_merge diff --git a/libcxx/include/__algorithm/stable_sort.h b/libcxx/include/__algorithm/stable_sort.h --- a/libcxx/include/__algorithm/stable_sort.h +++ b/libcxx/include/__algorithm/stable_sort.h @@ -203,7 +203,7 @@ } std::__stable_sort<_AlgPolicy, _Compare>(__first, __m, __comp, __l2, __buff, __buff_size); std::__stable_sort<_AlgPolicy, _Compare>(__m, __last, __comp, __len - __l2, __buff, __buff_size); - std::__inplace_merge<_AlgPolicy, _Compare>(__first, __m, __last, __comp, __l2, __len - __l2, __buff, __buff_size); + std::__inplace_merge<_AlgPolicy>(__first, __m, __last, __comp, __l2, __len - __l2, __buff, __buff_size); } template diff --git a/libcxx/include/algorithm b/libcxx/include/algorithm --- a/libcxx/include/algorithm +++ b/libcxx/include/algorithm @@ -774,7 +774,7 @@ set_symmetric_difference(I1 first1, S1 last1, I2 first2, S2 last2, O result, Comp comp = {}, Proj1 proj1 = {}, Proj2 proj2 = {}); // since C++20 - + template requires mergeable, iterator_t, O, Comp, Proj1, Proj2> @@ -787,13 +787,13 @@ indirect_strict_weak_order> Comp = ranges::less> constexpr subrange equal_range(I first, S last, const T& value, Comp comp = {}, Proj proj = {}); // since C++20 - + template, Proj>> Comp = ranges::less> constexpr borrowed_subrange_t equal_range(R&& r, const T& value, Comp comp = {}, Proj proj = {}); // since C++20 - + template using set_union_result = in_in_out_result; // since C++20 @@ -818,13 +818,24 @@ ranges::less> constexpr bool includes(I1 first1, S1 last1, I2 first2, S2 last2, Comp comp = {}, Proj1 proj1 = {}, Proj2 proj2 = {}); // Since C++20 - + template, Proj1>, projected, Proj2>> Comp = ranges::less> constexpr bool includes(R1&& r1, R2&& r2, Comp comp = {}, Proj1 proj1 = {}, Proj2 proj2 = {}); // Since C++20 + + template S, class Comp = ranges::less, + class Proj = identity> + requires sortable + I inplace_merge(I first, I middle, S last, Comp comp = {}, Proj proj = {}); // Since C++20 + + template + requires sortable, Comp, Proj> + borrowed_iterator_t + inplace_merge(R&& r, iterator_t middle, Comp comp = {}, + Proj proj = {}); // Since C++20 } constexpr bool // constexpr in C++20 @@ -1575,6 +1586,7 @@ #include <__algorithm/ranges_find_if_not.h> #include <__algorithm/ranges_for_each.h> #include <__algorithm/ranges_for_each_n.h> +#include <__algorithm/ranges_inplace_merge.h> #include <__algorithm/ranges_includes.h> #include <__algorithm/ranges_is_partitioned.h> #include <__algorithm/ranges_is_sorted.h> diff --git a/libcxx/include/module.modulemap.in b/libcxx/include/module.modulemap.in --- a/libcxx/include/module.modulemap.in +++ b/libcxx/include/module.modulemap.in @@ -239,6 +239,7 @@ module __algorithm { module adjacent_find { private header "__algorithm/adjacent_find.h" } + module algorithm_family { private header "__algorithm/algorithm_family.h" } module all_of { private header "__algorithm/all_of.h" } module any_of { private header "__algorithm/any_of.h" } module binary_search { private header "__algorithm/binary_search.h" } diff --git a/libcxx/test/libcxx/private_headers.verify.cpp b/libcxx/test/libcxx/private_headers.verify.cpp --- a/libcxx/test/libcxx/private_headers.verify.cpp +++ b/libcxx/test/libcxx/private_headers.verify.cpp @@ -37,6 +37,7 @@ // DO NOT MANUALLY EDIT ANYTHING BETWEEN THE MARKERS BELOW // GENERATED-MARKER #include <__algorithm/adjacent_find.h> // expected-error@*:* {{use of private header from outside its module: '__algorithm/adjacent_find.h'}} +#include <__algorithm/algorithm_family.h> // expected-error@*:* {{use of private header from outside its module: '__algorithm/algorithm_family.h'}} #include <__algorithm/all_of.h> // expected-error@*:* {{use of private header from outside its module: '__algorithm/all_of.h'}} #include <__algorithm/any_of.h> // expected-error@*:* {{use of private header from outside its module: '__algorithm/any_of.h'}} #include <__algorithm/binary_search.h> // expected-error@*:* {{use of private header from outside its module: '__algorithm/binary_search.h'}} diff --git a/libcxx/test/std/algorithms/alg.sorting/alg.merge/ranges_inplace_merge.pass.cpp b/libcxx/test/std/algorithms/alg.sorting/alg.merge/ranges_inplace_merge.pass.cpp --- a/libcxx/test/std/algorithms/alg.sorting/alg.merge/ranges_inplace_merge.pass.cpp +++ b/libcxx/test/std/algorithms/alg.sorting/alg.merge/ranges_inplace_merge.pass.cpp @@ -31,7 +31,23 @@ #include "almost_satisfies_types.h" #include "test_iterators.h" -// TODO: SFINAE tests. +template < + class Iter = int*, + class Middle = int*, + class Sent = int*, + class Comp = std::ranges::less, + class Proj = std::identity> +concept HasInplaceMergeIter = + requires(Iter&& iter, Middle&& mid, Sent&& sent, Comp&& comp, Proj&& proj) { + std::ranges::inplace_merge( + std::forward(iter), + std::forward(mid), + std::forward(sent), + std::forward(comp), + std::forward(proj)); + }; + +static_assert(HasInplaceMergeIter); constexpr bool test() { // TODO: main tests. diff --git a/llvm/utils/gn/secondary/libcxx/include/BUILD.gn b/llvm/utils/gn/secondary/libcxx/include/BUILD.gn --- a/llvm/utils/gn/secondary/libcxx/include/BUILD.gn +++ b/llvm/utils/gn/secondary/libcxx/include/BUILD.gn @@ -69,6 +69,7 @@ copy("copy_headers") { sources = [ "__algorithm/adjacent_find.h", + "__algorithm/algorithm_family.h", "__algorithm/all_of.h", "__algorithm/any_of.h", "__algorithm/binary_search.h",