[PATCH 2/5] libstdc++: Move ranges algos used by <ranges> into ranges_util.h
Patrick Palka
ppalka@redhat.com
Thu Jun 17 15:22:03 GMT 2021
The <ranges> 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 <ranges> as well, but
that algorithm is more complicated compared to the other copied ones.
So rather than additionally copying ranges::search into <ranges>, this
patch splits out all the ranges algos used by <ranges> (including
ranges::search) from ranges_algo.h to ranges_util.h, and deletes the
simplified copies in <ranges>. This seems like the best place for
these algorithms, as ranges_util.h is included only from <ranges> 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.
---
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<input_iterator _Iter, sentinel_for<_Iter> _Sent, typename _Tp,
- typename _Proj = identity>
- requires indirect_binary_predicate<ranges::equal_to,
- projected<_Iter, _Proj>, 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<input_range _Range, typename _Tp, typename _Proj = identity>
- requires indirect_binary_predicate<ranges::equal_to,
- projected<iterator_t<_Range>, _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<input_iterator _Iter, sentinel_for<_Iter> _Sent,
- typename _Proj = identity,
- indirect_unary_predicate<projected<_Iter, _Proj>> _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<input_range _Range, typename _Proj = identity,
- indirect_unary_predicate<projected<iterator_t<_Range>, _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<input_iterator _Iter, sentinel_for<_Iter> _Sent,
- typename _Proj = identity,
- indirect_unary_predicate<projected<_Iter, _Proj>> _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<input_range _Range, typename _Proj = identity,
- indirect_unary_predicate<projected<iterator_t<_Range>, _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 <bits/ranges_util.h>.
struct __find_first_of_fn
{
@@ -421,134 +337,7 @@ namespace ranges
inline constexpr __count_if_fn count_if{};
- template<typename _Iter1, typename _Iter2>
- struct in_in_result
- {
- [[no_unique_address]] _Iter1 in1;
- [[no_unique_address]] _Iter2 in2;
-
- template<typename _IIter1, typename _IIter2>
- requires convertible_to<const _Iter1&, _IIter1>
- && convertible_to<const _Iter2&, _IIter2>
- constexpr
- operator in_in_result<_IIter1, _IIter2>() const &
- { return {in1, in2}; }
-
- template<typename _IIter1, typename _IIter2>
- requires convertible_to<_Iter1, _IIter1>
- && convertible_to<_Iter2, _IIter2>
- constexpr
- operator in_in_result<_IIter1, _IIter2>() &&
- { return {std::move(in1), std::move(in2)}; }
- };
-
- template<typename _Iter1, typename _Iter2>
- using mismatch_result = in_in_result<_Iter1, _Iter2>;
-
- struct __mismatch_fn
- {
- template<input_iterator _Iter1, sentinel_for<_Iter1> _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<input_range _Range1, input_range _Range2,
- typename _Pred = ranges::equal_to,
- typename _Proj1 = identity, typename _Proj2 = identity>
- requires indirectly_comparable<iterator_t<_Range1>, iterator_t<_Range2>,
- _Pred, _Proj1, _Proj2>
- constexpr mismatch_result<iterator_t<_Range1>, 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<forward_iterator _Iter1, sentinel_for<_Iter1> _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<forward_range _Range1, forward_range _Range2,
- typename _Pred = ranges::equal_to,
- typename _Proj1 = identity, typename _Proj2 = identity>
- requires indirectly_comparable<iterator_t<_Range1>, 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 <bits/ranges_util.h>.
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<borrowed_range<_Range>,
subrange<iterator_t<_Range>>,
dangling>;
+} // namespace ranges
+
+// The following ranges algorithms are used by <ranges>, and are defined here
+// so that <ranges> can avoid including all of <bits/ranges_algo.h>.
+namespace ranges
+{
+ struct __find_fn
+ {
+ template<input_iterator _Iter, sentinel_for<_Iter> _Sent, typename _Tp,
+ typename _Proj = identity>
+ requires indirect_binary_predicate<ranges::equal_to,
+ projected<_Iter, _Proj>, 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<input_range _Range, typename _Tp, typename _Proj = identity>
+ requires indirect_binary_predicate<ranges::equal_to,
+ projected<iterator_t<_Range>, _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<input_iterator _Iter, sentinel_for<_Iter> _Sent,
+ typename _Proj = identity,
+ indirect_unary_predicate<projected<_Iter, _Proj>> _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<input_range _Range, typename _Proj = identity,
+ indirect_unary_predicate<projected<iterator_t<_Range>, _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<input_iterator _Iter, sentinel_for<_Iter> _Sent,
+ typename _Proj = identity,
+ indirect_unary_predicate<projected<_Iter, _Proj>> _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<input_range _Range, typename _Proj = identity,
+ indirect_unary_predicate<projected<iterator_t<_Range>, _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<typename _Iter1, typename _Iter2>
+ struct in_in_result
+ {
+ [[no_unique_address]] _Iter1 in1;
+ [[no_unique_address]] _Iter2 in2;
+
+ template<typename _IIter1, typename _IIter2>
+ requires convertible_to<const _Iter1&, _IIter1>
+ && convertible_to<const _Iter2&, _IIter2>
+ constexpr
+ operator in_in_result<_IIter1, _IIter2>() const &
+ { return {in1, in2}; }
+
+ template<typename _IIter1, typename _IIter2>
+ requires convertible_to<_Iter1, _IIter1>
+ && convertible_to<_Iter2, _IIter2>
+ constexpr
+ operator in_in_result<_IIter1, _IIter2>() &&
+ { return {std::move(in1), std::move(in2)}; }
+ };
+
+ template<typename _Iter1, typename _Iter2>
+ using mismatch_result = in_in_result<_Iter1, _Iter2>;
+
+ struct __mismatch_fn
+ {
+ template<input_iterator _Iter1, sentinel_for<_Iter1> _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<input_range _Range1, input_range _Range2,
+ typename _Pred = ranges::equal_to,
+ typename _Proj1 = identity, typename _Proj2 = identity>
+ requires indirectly_comparable<iterator_t<_Range1>, iterator_t<_Range2>,
+ _Pred, _Proj1, _Proj2>
+ constexpr mismatch_result<iterator_t<_Range1>, 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<forward_iterator _Iter1, sentinel_for<_Iter1> _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<forward_range _Range1, forward_range _Range2,
+ typename _Pred = ranges::equal_to,
+ typename _Proj1 = identity, typename _Proj2 = identity>
+ requires indirectly_comparable<iterator_t<_Range1>, 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<typename _Iter, typename _Sent, typename _Tp>
- constexpr _Iter
- find(_Iter __first, _Sent __last, const _Tp& __value)
- {
- while (__first != __last
- && !(bool)(*__first == __value))
- ++__first;
- return __first;
- }
-
- template<typename _Iter, typename _Sent, typename _Pred>
- constexpr _Iter
- find_if(_Iter __first, _Sent __last, _Pred __pred)
- {
- while (__first != __last
- && !(bool)std::__invoke(__pred, *__first))
- ++__first;
- return __first;
- }
-
- template<typename _Iter, typename _Sent, typename _Pred>
- constexpr _Iter
- find_if_not(_Iter __first, _Sent __last, _Pred __pred)
- {
- while (__first != __last
- && (bool)std::__invoke(__pred, *__first))
- ++__first;
- return __first;
- }
-
- template<typename _Iter1, typename _Sent1, typename _Iter2, typename _Sent2>
- 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<typename _Tp>
@@ -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;
--
2.32.0.93.g670b81a890
More information about the Gcc-patches
mailing list