From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: by sourceware.org (Postfix, from userid 1888) id 7D39A399C8BA; Fri, 18 Jun 2021 02:45:07 +0000 (GMT) DKIM-Filter: OpenDKIM Filter v2.11.0 sourceware.org 7D39A399C8BA MIME-Version: 1.0 Content-Transfer-Encoding: 7bit Content-Type: text/plain; charset="utf-8" From: Patrick Palka To: gcc-cvs@gcc.gnu.org, libstdc++-cvs@gcc.gnu.org Subject: [gcc r12-1607] libstdc++: Move ranges algos used by into ranges_util.h X-Act-Checkin: gcc X-Git-Author: Patrick Palka X-Git-Refname: refs/heads/master X-Git-Oldrev: 4b4f5666b4c2f3aab2a9f3d53d394e390b9b682d X-Git-Newrev: 2786064d91f46cbdb35a543a883155a3982b9478 Message-Id: <20210618024507.7D39A399C8BA@sourceware.org> Date: Fri, 18 Jun 2021 02:45:07 +0000 (GMT) X-BeenThere: libstdc++-cvs@gcc.gnu.org X-Mailman-Version: 2.1.29 Precedence: list List-Id: Libstdc++-cvs mailing list List-Unsubscribe: , List-Archive: List-Help: List-Subscribe: , X-List-Received-Date: Fri, 18 Jun 2021 02:45:07 -0000 https://gcc.gnu.org/g:2786064d91f46cbdb35a543a883155a3982b9478 commit r12-1607-g2786064d91f46cbdb35a543a883155a3982b9478 Author: Patrick Palka Date: Thu Jun 17 22:44:41 2021 -0400 libstdc++: Move ranges algos used by into ranges_util.h The header defines simplified copies of some ranges algorithms in order to avoid including the entirety of ranges_algo.h. A subsequent patch is going to want to use ranges::search in as well, and that algorithm is more complicated compared to the other copied ones. So rather than additionally copying ranges::search into , this patch splits out all the ranges algos used by (including ranges::search) from ranges_algo.h to ranges_util.h, and deletes the simplified copies in . This seems like the best place to put these algorithms, as ranges_util.h is currently included only from and ranges_algo.h. libstdc++-v3/ChangeLog: * include/bits/ranges_algo.h (__find_fn, find, __find_if_fn) (find_if, __find_if_not_fn, find_if_not, _in_in_result) (__mismatch_fn, mismatch, __search_fn, search): Move to ... * include/bits/ranges_util.h: ... here. * include/std/ranges (__detail::find, __detail::find_if) (__detail::find_if_not, __detail::mismatch): Remove. (filter_view): Use ranges::find_if instead. (drop_while_view): Use ranges::find_if_not instead. (split_view): Use ranges::find and ranges::mismatch instead. Diff: --- libstdc++-v3/include/bits/ranges_algo.h | 215 +------------------------------ libstdc++-v3/include/bits/ranges_util.h | 219 ++++++++++++++++++++++++++++++++ libstdc++-v3/include/std/ranges | 72 ++--------- 3 files changed, 233 insertions(+), 273 deletions(-) diff --git a/libstdc++-v3/include/bits/ranges_algo.h b/libstdc++-v3/include/bits/ranges_algo.h index ecf1378742d..9eeebff6525 100644 --- a/libstdc++-v3/include/bits/ranges_algo.h +++ b/libstdc++-v3/include/bits/ranges_algo.h @@ -234,91 +234,7 @@ namespace ranges inline constexpr __for_each_n_fn for_each_n{}; - struct __find_fn - { - template _Sent, typename _Tp, - typename _Proj = identity> - requires indirect_binary_predicate, const _Tp*> - constexpr _Iter - operator()(_Iter __first, _Sent __last, - const _Tp& __value, _Proj __proj = {}) const - { - while (__first != __last - && !(std::__invoke(__proj, *__first) == __value)) - ++__first; - return __first; - } - - template - requires indirect_binary_predicate, _Proj>, - const _Tp*> - constexpr borrowed_iterator_t<_Range> - operator()(_Range&& __r, const _Tp& __value, _Proj __proj = {}) const - { - return (*this)(ranges::begin(__r), ranges::end(__r), - __value, std::move(__proj)); - } - }; - - inline constexpr __find_fn find{}; - - struct __find_if_fn - { - template _Sent, - typename _Proj = identity, - indirect_unary_predicate> _Pred> - constexpr _Iter - operator()(_Iter __first, _Sent __last, - _Pred __pred, _Proj __proj = {}) const - { - while (__first != __last - && !(bool)std::__invoke(__pred, std::__invoke(__proj, *__first))) - ++__first; - return __first; - } - - template, _Proj>> - _Pred> - constexpr borrowed_iterator_t<_Range> - operator()(_Range&& __r, _Pred __pred, _Proj __proj = {}) const - { - return (*this)(ranges::begin(__r), ranges::end(__r), - std::move(__pred), std::move(__proj)); - } - }; - - inline constexpr __find_if_fn find_if{}; - - struct __find_if_not_fn - { - template _Sent, - typename _Proj = identity, - indirect_unary_predicate> _Pred> - constexpr _Iter - operator()(_Iter __first, _Sent __last, - _Pred __pred, _Proj __proj = {}) const - { - while (__first != __last - && (bool)std::__invoke(__pred, std::__invoke(__proj, *__first))) - ++__first; - return __first; - } - - template, _Proj>> - _Pred> - constexpr borrowed_iterator_t<_Range> - operator()(_Range&& __r, _Pred __pred, _Proj __proj = {}) const - { - return (*this)(ranges::begin(__r), ranges::end(__r), - std::move(__pred), std::move(__proj)); - } - }; - - inline constexpr __find_if_not_fn find_if_not{}; + // find, find_if and find_if_not are defined in . struct __find_first_of_fn { @@ -421,134 +337,7 @@ namespace ranges inline constexpr __count_if_fn count_if{}; - template - struct in_in_result - { - [[no_unique_address]] _Iter1 in1; - [[no_unique_address]] _Iter2 in2; - - template - requires convertible_to - && convertible_to - constexpr - operator in_in_result<_IIter1, _IIter2>() const & - { return {in1, in2}; } - - template - requires convertible_to<_Iter1, _IIter1> - && convertible_to<_Iter2, _IIter2> - constexpr - operator in_in_result<_IIter1, _IIter2>() && - { return {std::move(in1), std::move(in2)}; } - }; - - template - using mismatch_result = in_in_result<_Iter1, _Iter2>; - - struct __mismatch_fn - { - template _Sent1, - input_iterator _Iter2, sentinel_for<_Iter2> _Sent2, - typename _Pred = ranges::equal_to, - typename _Proj1 = identity, typename _Proj2 = identity> - requires indirectly_comparable<_Iter1, _Iter2, _Pred, _Proj1, _Proj2> - constexpr mismatch_result<_Iter1, _Iter2> - operator()(_Iter1 __first1, _Sent1 __last1, - _Iter2 __first2, _Sent2 __last2, _Pred __pred = {}, - _Proj1 __proj1 = {}, _Proj2 __proj2 = {}) const - { - while (__first1 != __last1 && __first2 != __last2 - && (bool)std::__invoke(__pred, - std::__invoke(__proj1, *__first1), - std::__invoke(__proj2, *__first2))) - { - ++__first1; - ++__first2; - } - return { std::move(__first1), std::move(__first2) }; - } - - template - requires indirectly_comparable, iterator_t<_Range2>, - _Pred, _Proj1, _Proj2> - constexpr mismatch_result, iterator_t<_Range2>> - operator()(_Range1&& __r1, _Range2&& __r2, _Pred __pred = {}, - _Proj1 __proj1 = {}, _Proj2 __proj2 = {}) const - { - return (*this)(ranges::begin(__r1), ranges::end(__r1), - ranges::begin(__r2), ranges::end(__r2), - std::move(__pred), - std::move(__proj1), std::move(__proj2)); - } - }; - - inline constexpr __mismatch_fn mismatch{}; - - struct __search_fn - { - template _Sent1, - forward_iterator _Iter2, sentinel_for<_Iter2> _Sent2, - typename _Pred = ranges::equal_to, - typename _Proj1 = identity, typename _Proj2 = identity> - requires indirectly_comparable<_Iter1, _Iter2, _Pred, _Proj1, _Proj2> - constexpr subrange<_Iter1> - operator()(_Iter1 __first1, _Sent1 __last1, - _Iter2 __first2, _Sent2 __last2, _Pred __pred = {}, - _Proj1 __proj1 = {}, _Proj2 __proj2 = {}) const - { - if (__first1 == __last1 || __first2 == __last2) - return {__first1, __first1}; - - for (;;) - { - for (;;) - { - if (__first1 == __last1) - return {__first1, __first1}; - if (std::__invoke(__pred, - std::__invoke(__proj1, *__first1), - std::__invoke(__proj2, *__first2))) - break; - ++__first1; - } - auto __cur1 = __first1; - auto __cur2 = __first2; - for (;;) - { - if (++__cur2 == __last2) - return {__first1, ++__cur1}; - if (++__cur1 == __last1) - return {__cur1, __cur1}; - if (!(bool)std::__invoke(__pred, - std::__invoke(__proj1, *__cur1), - std::__invoke(__proj2, *__cur2))) - { - ++__first1; - break; - } - } - } - } - - template - requires indirectly_comparable, iterator_t<_Range2>, - _Pred, _Proj1, _Proj2> - constexpr borrowed_subrange_t<_Range1> - operator()(_Range1&& __r1, _Range2&& __r2, _Pred __pred = {}, - _Proj1 __proj1 = {}, _Proj2 __proj2 = {}) const - { - return (*this)(ranges::begin(__r1), ranges::end(__r1), - ranges::begin(__r2), ranges::end(__r2), - std::move(__pred), - std::move(__proj1), std::move(__proj2)); - } - }; - - inline constexpr __search_fn search{}; + // in_in_result, mismatch and search are defined in . struct __search_n_fn { diff --git a/libstdc++-v3/include/bits/ranges_util.h b/libstdc++-v3/include/bits/ranges_util.h index d7b12b3d985..9a07079ac13 100644 --- a/libstdc++-v3/include/bits/ranges_util.h +++ b/libstdc++-v3/include/bits/ranges_util.h @@ -420,7 +420,226 @@ namespace ranges using borrowed_subrange_t = conditional_t, subrange>, dangling>; +} // namespace ranges + +// The following ranges algorithms are used by , and are defined here +// so that can avoid including all of . +namespace ranges +{ + struct __find_fn + { + template _Sent, typename _Tp, + typename _Proj = identity> + requires indirect_binary_predicate, const _Tp*> + constexpr _Iter + operator()(_Iter __first, _Sent __last, + const _Tp& __value, _Proj __proj = {}) const + { + while (__first != __last + && !(std::__invoke(__proj, *__first) == __value)) + ++__first; + return __first; + } + + template + requires indirect_binary_predicate, _Proj>, + const _Tp*> + constexpr borrowed_iterator_t<_Range> + operator()(_Range&& __r, const _Tp& __value, _Proj __proj = {}) const + { + return (*this)(ranges::begin(__r), ranges::end(__r), + __value, std::move(__proj)); + } + }; + + inline constexpr __find_fn find{}; + + struct __find_if_fn + { + template _Sent, + typename _Proj = identity, + indirect_unary_predicate> _Pred> + constexpr _Iter + operator()(_Iter __first, _Sent __last, + _Pred __pred, _Proj __proj = {}) const + { + while (__first != __last + && !(bool)std::__invoke(__pred, std::__invoke(__proj, *__first))) + ++__first; + return __first; + } + + template, _Proj>> + _Pred> + constexpr borrowed_iterator_t<_Range> + operator()(_Range&& __r, _Pred __pred, _Proj __proj = {}) const + { + return (*this)(ranges::begin(__r), ranges::end(__r), + std::move(__pred), std::move(__proj)); + } + }; + + inline constexpr __find_if_fn find_if{}; + + struct __find_if_not_fn + { + template _Sent, + typename _Proj = identity, + indirect_unary_predicate> _Pred> + constexpr _Iter + operator()(_Iter __first, _Sent __last, + _Pred __pred, _Proj __proj = {}) const + { + while (__first != __last + && (bool)std::__invoke(__pred, std::__invoke(__proj, *__first))) + ++__first; + return __first; + } + + template, _Proj>> + _Pred> + constexpr borrowed_iterator_t<_Range> + operator()(_Range&& __r, _Pred __pred, _Proj __proj = {}) const + { + return (*this)(ranges::begin(__r), ranges::end(__r), + std::move(__pred), std::move(__proj)); + } + }; + + inline constexpr __find_if_not_fn find_if_not{}; + + template + struct in_in_result + { + [[no_unique_address]] _Iter1 in1; + [[no_unique_address]] _Iter2 in2; + + template + requires convertible_to + && convertible_to + constexpr + operator in_in_result<_IIter1, _IIter2>() const & + { return {in1, in2}; } + + template + requires convertible_to<_Iter1, _IIter1> + && convertible_to<_Iter2, _IIter2> + constexpr + operator in_in_result<_IIter1, _IIter2>() && + { return {std::move(in1), std::move(in2)}; } + }; + + template + using mismatch_result = in_in_result<_Iter1, _Iter2>; + + struct __mismatch_fn + { + template _Sent1, + input_iterator _Iter2, sentinel_for<_Iter2> _Sent2, + typename _Pred = ranges::equal_to, + typename _Proj1 = identity, typename _Proj2 = identity> + requires indirectly_comparable<_Iter1, _Iter2, _Pred, _Proj1, _Proj2> + constexpr mismatch_result<_Iter1, _Iter2> + operator()(_Iter1 __first1, _Sent1 __last1, + _Iter2 __first2, _Sent2 __last2, _Pred __pred = {}, + _Proj1 __proj1 = {}, _Proj2 __proj2 = {}) const + { + while (__first1 != __last1 && __first2 != __last2 + && (bool)std::__invoke(__pred, + std::__invoke(__proj1, *__first1), + std::__invoke(__proj2, *__first2))) + { + ++__first1; + ++__first2; + } + return { std::move(__first1), std::move(__first2) }; + } + + template + requires indirectly_comparable, iterator_t<_Range2>, + _Pred, _Proj1, _Proj2> + constexpr mismatch_result, iterator_t<_Range2>> + operator()(_Range1&& __r1, _Range2&& __r2, _Pred __pred = {}, + _Proj1 __proj1 = {}, _Proj2 __proj2 = {}) const + { + return (*this)(ranges::begin(__r1), ranges::end(__r1), + ranges::begin(__r2), ranges::end(__r2), + std::move(__pred), + std::move(__proj1), std::move(__proj2)); + } + }; + + inline constexpr __mismatch_fn mismatch{}; + + struct __search_fn + { + template _Sent1, + forward_iterator _Iter2, sentinel_for<_Iter2> _Sent2, + typename _Pred = ranges::equal_to, + typename _Proj1 = identity, typename _Proj2 = identity> + requires indirectly_comparable<_Iter1, _Iter2, _Pred, _Proj1, _Proj2> + constexpr subrange<_Iter1> + operator()(_Iter1 __first1, _Sent1 __last1, + _Iter2 __first2, _Sent2 __last2, _Pred __pred = {}, + _Proj1 __proj1 = {}, _Proj2 __proj2 = {}) const + { + if (__first1 == __last1 || __first2 == __last2) + return {__first1, __first1}; + + for (;;) + { + for (;;) + { + if (__first1 == __last1) + return {__first1, __first1}; + if (std::__invoke(__pred, + std::__invoke(__proj1, *__first1), + std::__invoke(__proj2, *__first2))) + break; + ++__first1; + } + auto __cur1 = __first1; + auto __cur2 = __first2; + for (;;) + { + if (++__cur2 == __last2) + return {__first1, ++__cur1}; + if (++__cur1 == __last1) + return {__cur1, __cur1}; + if (!(bool)std::__invoke(__pred, + std::__invoke(__proj1, *__cur1), + std::__invoke(__proj2, *__cur2))) + { + ++__first1; + break; + } + } + } + } + + template + requires indirectly_comparable, iterator_t<_Range2>, + _Pred, _Proj1, _Proj2> + constexpr borrowed_subrange_t<_Range1> + operator()(_Range1&& __r1, _Range2&& __r2, _Pred __pred = {}, + _Proj1 __proj1 = {}, _Proj2 __proj2 = {}) const + { + return (*this)(ranges::begin(__r1), ranges::end(__r1), + ranges::begin(__r2), ranges::end(__r2), + std::move(__pred), + std::move(__proj1), std::move(__proj2)); + } + }; + inline constexpr __search_fn search{}; } // namespace ranges using ranges::get; diff --git a/libstdc++-v3/include/std/ranges b/libstdc++-v3/include/std/ranges index f96adf63d10..f93a880ff8a 100644 --- a/libstdc++-v3/include/std/ranges +++ b/libstdc++-v3/include/std/ranges @@ -1144,54 +1144,6 @@ namespace views::__adaptor using all_t = decltype(all(std::declval<_Range>())); } // namespace views - // The following simple algos are transcribed from ranges_algo.h to avoid - // having to include that entire header. - namespace __detail - { - template - constexpr _Iter - find(_Iter __first, _Sent __last, const _Tp& __value) - { - while (__first != __last - && !(bool)(*__first == __value)) - ++__first; - return __first; - } - - template - constexpr _Iter - find_if(_Iter __first, _Sent __last, _Pred __pred) - { - while (__first != __last - && !(bool)std::__invoke(__pred, *__first)) - ++__first; - return __first; - } - - template - constexpr _Iter - find_if_not(_Iter __first, _Sent __last, _Pred __pred) - { - while (__first != __last - && (bool)std::__invoke(__pred, *__first)) - ++__first; - return __first; - } - - template - constexpr pair<_Iter1, _Iter2> - mismatch(_Iter1 __first1, _Sent1 __last1, _Iter2 __first2, _Sent2 __last2) - { - while (__first1 != __last1 && __first2 != __last2 - && (bool)ranges::equal_to{}(*__first1, *__first2)) - { - ++__first1; - ++__first2; - } - return { std::move(__first1), std::move(__first2) }; - } - } // namespace __detail - namespace __detail { template @@ -1449,9 +1401,9 @@ namespace views::__adaptor constexpr _Iterator& operator++() { - _M_current = __detail::find_if(std::move(++_M_current), - ranges::end(_M_parent->_M_base), - std::ref(*_M_parent->_M_pred)); + _M_current = ranges::find_if(std::move(++_M_current), + ranges::end(_M_parent->_M_base), + std::ref(*_M_parent->_M_pred)); return *this; } @@ -1560,9 +1512,9 @@ namespace views::__adaptor return {this, _M_cached_begin._M_get(_M_base)}; __glibcxx_assert(_M_pred.has_value()); - auto __it = __detail::find_if(ranges::begin(_M_base), - ranges::end(_M_base), - std::ref(*_M_pred)); + auto __it = ranges::find_if(ranges::begin(_M_base), + ranges::end(_M_base), + std::ref(*_M_pred)); _M_cached_begin._M_set(_M_base, __it); return {this, std::move(__it)}; } @@ -2453,9 +2405,9 @@ namespace views::__adaptor return _M_cached_begin._M_get(_M_base); __glibcxx_assert(_M_pred.has_value()); - auto __it = __detail::find_if_not(ranges::begin(_M_base), - ranges::end(_M_base), - std::cref(*_M_pred)); + auto __it = ranges::find_if_not(ranges::begin(_M_base), + ranges::end(_M_base), + std::cref(*_M_pred)); _M_cached_begin._M_set(_M_base, __it); return __it; } @@ -3031,8 +2983,8 @@ namespace views::__adaptor ++__current(); else if constexpr (__detail::__tiny_range<_Pattern>) { - __current() = __detail::find(std::move(__current()), __end, - *__pbegin); + __current() = ranges::find(std::move(__current()), __end, + *__pbegin); if (__current() != __end) ++__current(); } @@ -3040,7 +2992,7 @@ namespace views::__adaptor do { auto [__b, __p] - = __detail::mismatch(__current(), __end, __pbegin, __pend); + = ranges::mismatch(__current(), __end, __pbegin, __pend); if (__p == __pend) { __current() = __b;