Changes in v2: Addressed Tomasz's review comments, namely: * Added explicit iter_difference_t casts * Made _S_impl member private * Optimized sized bidirectional case of ends_with * Rearranged control flow of starts_with::_S_impl
Still left to do: * Add tests for integer-class types * Still working on a better commit description ;) -- >8 -- libstdc++-v3/ChangeLog: * include/bits/ranges_algo.h (__starts_with_fn, starts_with): Define. (__ends_with_fn, ends_with): Define. * include/bits/version.def (ranges_starts_ends_with): Define. * include/bits/version.h: Regenerate. * include/std/algorithm: Provide __cpp_lib_ranges_starts_ends_with. * src/c++23/std.cc.in (ranges::starts_with): Export. (ranges::ends_with): Export. * testsuite/25_algorithms/ends_with/1.cc: New test. * testsuite/25_algorithms/starts_with/1.cc: New test. --- libstdc++-v3/include/bits/ranges_algo.h | 239 ++++++++++++++++++ libstdc++-v3/include/bits/version.def | 8 + libstdc++-v3/include/bits/version.h | 10 + libstdc++-v3/include/std/algorithm | 1 + libstdc++-v3/src/c++23/std.cc.in | 4 + .../testsuite/25_algorithms/ends_with/1.cc | 129 ++++++++++ .../testsuite/25_algorithms/starts_with/1.cc | 128 ++++++++++ 7 files changed, 519 insertions(+) create mode 100644 libstdc++-v3/testsuite/25_algorithms/ends_with/1.cc create mode 100644 libstdc++-v3/testsuite/25_algorithms/starts_with/1.cc diff --git a/libstdc++-v3/include/bits/ranges_algo.h b/libstdc++-v3/include/bits/ranges_algo.h index f36e7dd59911..f889257a8ee2 100644 --- a/libstdc++-v3/include/bits/ranges_algo.h +++ b/libstdc++-v3/include/bits/ranges_algo.h @@ -438,6 +438,245 @@ namespace ranges inline constexpr __search_n_fn search_n{}; +#if __glibcxx_ranges_starts_ends_with // C++ >= 23 + struct __starts_with_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 bool + operator()(_Iter1 __first1, _Sent1 __last1, + _Iter2 __first2, _Sent2 __last2, _Pred __pred = {}, + _Proj1 __proj1 = {}, _Proj2 __proj2 = {}) const + { + iter_difference_t<_Iter1> __n1 = -1; + iter_difference_t<_Iter2> __n2 = -1; + if constexpr (sized_sentinel_for<_Sent1, _Iter1>) + __n1 = __last1 - __first1; + if constexpr (sized_sentinel_for<_Sent2, _Iter2>) + __n2 = __last2 - __first2; + return _S_impl(std::move(__first1), __last1, __n1, + std::move(__first2), __last2, __n2, + std::move(__pred), + std::move(__proj1), std::move(__proj2)); + } + + 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 bool + operator()(_Range1&& __r1, _Range2&& __r2, _Pred __pred = {}, + _Proj1 __proj1 = {}, _Proj2 __proj2 = {}) const + { + range_difference_t<_Range1> __n1 = -1; + range_difference_t<_Range1> __n2 = -1; + if constexpr (sized_range<_Range1>) + __n1 = ranges::size(__r1); + if constexpr (sized_range<_Range2>) + __n2 = ranges::size(__r2); + return _S_impl(ranges::begin(__r1), ranges::end(__r1), __n1, + ranges::begin(__r2), ranges::end(__r2), __n2, + std::move(__pred), + std::move(__proj1), std::move(__proj2)); + } + + private: + template<typename _Iter1, typename _Sent1, typename _Iter2, typename _Sent2, + typename _Pred, + typename _Proj1, typename _Proj2> + static constexpr bool + _S_impl(_Iter1 __first1, _Sent1 __last1, iter_difference_t<_Iter1> __n1, + _Iter2 __first2, _Sent2 __last2, iter_difference_t<_Iter2> __n2, + _Pred __pred, + _Proj1 __proj1, _Proj2 __proj2) + { + if (__first2 == __last2) + return true; + else if (__n1 == -1 || __n2 == -1) + return ranges::mismatch(std::move(__first1), __last1, + std::move(__first2), __last2, + std::move(__pred), + std::move(__proj1), std::move(__proj2)).in2 == __last2; + else if (__n1 < __n2) + return false; + else + { + if constexpr (random_access_iterator<_Iter1>) + return ranges::equal(__first1, __first1 + iter_difference_t<_Iter1>(__n2), + std::move(__first2), __last2, + std::move(__pred), + std::move(__proj1), std::move(__proj2)); + else + return ranges::equal(counted_iterator(std::move(__first1), + iter_difference_t<_Iter2>(__n2)), + default_sentinel, + std::move(__first2), __last2, + std::move(__pred), + std::move(__proj1), std::move(__proj2)); + } + } + }; + + inline constexpr __starts_with_fn starts_with{}; + + struct __ends_with_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 (forward_iterator<_Iter1> || sized_sentinel_for<_Sent1, _Iter1>) + && (forward_iterator<_Iter2> || sized_sentinel_for<_Sent2, _Iter2>) + && indirectly_comparable<_Iter1, _Iter2, _Pred, _Proj1, _Proj2> + constexpr bool + operator()(_Iter1 __first1, _Sent1 __last1, + _Iter2 __first2, _Sent2 __last2, _Pred __pred = {}, + _Proj1 __proj1 = {}, _Proj2 __proj2 = {}) const + { + iter_difference_t<_Iter1> __n1 = -1; + iter_difference_t<_Iter2> __n2 = -1; + if constexpr (sized_sentinel_for<_Sent1, _Iter1>) + __n1 = __last1 - __first1; + if constexpr (sized_sentinel_for<_Sent2, _Iter2>) + __n2 = __last2 - __first2; + return _S_impl(std::move(__first1), __last1, __n1, + std::move(__first2), __last2, __n2, + std::move(__pred), + std::move(__proj1), std::move(__proj2)); + } + + template<input_range _Range1, input_range _Range2, + typename _Pred = ranges::equal_to, + typename _Proj1 = identity, typename _Proj2 = identity> + requires (forward_range<_Range1> || sized_range<_Range1>) + && (forward_range<_Range2> || sized_range<_Range2>) + && indirectly_comparable<iterator_t<_Range1>, iterator_t<_Range2>, + _Pred, _Proj1, _Proj2> + constexpr bool + operator()(_Range1&& __r1, _Range2&& __r2, _Pred __pred = {}, + _Proj1 __proj1 = {}, _Proj2 __proj2 = {}) const + { + range_difference_t<_Range1> __n1 = -1; + range_difference_t<_Range1> __n2 = -1; + if constexpr (sized_range<_Range1>) + __n1 = ranges::size(__r1); + if constexpr (sized_range<_Range2>) + __n2 = ranges::size(__r2); + return _S_impl(ranges::begin(__r1), ranges::end(__r1), __n1, + ranges::begin(__r2), ranges::end(__r2), __n2, + std::move(__pred), + std::move(__proj1), std::move(__proj2)); + } + + private: + template<typename _Iter1, typename _Sent1, + typename _Iter2, typename _Sent2, + typename _Pred, + typename _Proj1, typename _Proj2> + static constexpr bool + _S_impl(_Iter1 __first1, _Sent1 __last1, iter_difference_t<_Iter1> __n1, + _Iter2 __first2, _Sent2 __last2, iter_difference_t<_Iter2> __n2, + _Pred __pred, + _Proj1 __proj1, _Proj2 __proj2) + { + if (__first2 == __last2) + return true; + + if (__n2 == -1) + { + if constexpr (forward_iterator<_Iter2>) + __n2 = ranges::distance(__first2, __last2); + else + // Size is known and passed by the caller. + __builtin_unreachable(); + } + + if (__n1 != -1) + { + if (__n1 < __n2) + return false; + if constexpr (random_access_iterator<_Iter1> + || !(bidirectional_iterator<_Iter1> + && same_as<_Iter1, _Sent1>)) + { + ranges::advance(__first1, __n1 - iter_difference_t<_Iter1>(__n2)); + return ranges::equal(std::move(__first1), __last1, + std::move(__first2), __last2, + std::move(__pred), + std::move(__proj1), std::move(__proj2)); + } + } + + if constexpr (bidirectional_iterator<_Iter1>) + { + _Iter1 __it1 = ranges::next(__first1, __last1); + if (__n1 != -1) + ranges::advance(__it1, -iter_difference_t<_Iter1>(__n2), __first1); + else + { + // We can't use ranges::advance if the size of the haystack + // is unknown, since we need to detect and return false if + // it's smaller than the needle. + iter_difference_t<_Iter2> __m = __n2; + while (__m != 0 && __it1 != __first1) + { + --__m; + --__it1; + } + if (__m != 0) + return false; + } + return ranges::equal(__it1, __last1, + std::move(__first2), __last2, + std::move(__pred), + std::move(__proj1), std::move(__proj2)); + } + else if constexpr (forward_iterator<_Iter1>) + { + _Iter1 __prev_first1; + __n1 = 0; + while (true) + { + iter_difference_t<_Iter2> __m = __n2; + _Iter1 __it1 = __first1; + while (__m != 0 && __it1 != __last1) + { + ++__n1; + --__m; + ++__it1; + } + if (__m != 0) + { + // __glibcxx_assert(__it1 == __last1); + if (__n1 < __n2) + return false; + __first1 = ranges::next(__prev_first1, + iter_difference_t<_Iter1>(__n2 - __m)); + break; + } + __prev_first1 = __first1; + __first1 = __it1; + } + return ranges::equal(__first1, __last1, + std::move(__first2), __last2, + std::move(__pred), + std::move(__proj1), std::move(__proj2)); + } + else + // If __first1 is non-forward, it must be sized, so it was handled + // by the __n1 != -1 case earlier. + __builtin_unreachable(); + } + + }; + + inline constexpr __ends_with_fn ends_with{}; +#endif // __glibcxx_ranges_starts_ends_with + struct __find_end_fn { template<forward_iterator _Iter1, sentinel_for<_Iter1> _Sent1, diff --git a/libstdc++-v3/include/bits/version.def b/libstdc++-v3/include/bits/version.def index 6ca148f0488f..8db1967cc184 100644 --- a/libstdc++-v3/include/bits/version.def +++ b/libstdc++-v3/include/bits/version.def @@ -1660,6 +1660,14 @@ ftms = { }; }; +ftms = { + name = ranges_starts_ends_with; + values = { + v = 202106; + cxxmin = 23; + }; +}; + ftms = { name = constexpr_bitset; values = { diff --git a/libstdc++-v3/include/bits/version.h b/libstdc++-v3/include/bits/version.h index 48a090c14a3d..3749528633f2 100644 --- a/libstdc++-v3/include/bits/version.h +++ b/libstdc++-v3/include/bits/version.h @@ -1848,6 +1848,16 @@ #endif /* !defined(__cpp_lib_ranges_find_last) && defined(__glibcxx_want_ranges_find_last) */ #undef __glibcxx_want_ranges_find_last +#if !defined(__cpp_lib_ranges_starts_ends_with) +# if (__cplusplus >= 202100L) +# define __glibcxx_ranges_starts_ends_with 202106L +# if defined(__glibcxx_want_all) || defined(__glibcxx_want_ranges_starts_ends_with) +# define __cpp_lib_ranges_starts_ends_with 202106L +# endif +# endif +#endif /* !defined(__cpp_lib_ranges_starts_ends_with) && defined(__glibcxx_want_ranges_starts_ends_with) */ +#undef __glibcxx_want_ranges_starts_ends_with + #if !defined(__cpp_lib_constexpr_bitset) # if (__cplusplus >= 202100L) && _GLIBCXX_HOSTED && (__cpp_constexpr_dynamic_alloc) # define __glibcxx_constexpr_bitset 202202L diff --git a/libstdc++-v3/include/std/algorithm b/libstdc++-v3/include/std/algorithm index 321a5e22d86b..1563cdf2b17c 100644 --- a/libstdc++-v3/include/std/algorithm +++ b/libstdc++-v3/include/std/algorithm @@ -74,6 +74,7 @@ #define __glibcxx_want_ranges_contains #define __glibcxx_want_ranges_find_last #define __glibcxx_want_ranges_fold +#define __glibcxx_want_ranges_starts_ends_with #define __glibcxx_want_robust_nonmodifying_seq_ops #define __glibcxx_want_sample #define __glibcxx_want_shift diff --git a/libstdc++-v3/src/c++23/std.cc.in b/libstdc++-v3/src/c++23/std.cc.in index 417c8a1a5626..2e4b3f75234f 100644 --- a/libstdc++-v3/src/c++23/std.cc.in +++ b/libstdc++-v3/src/c++23/std.cc.in @@ -506,6 +506,10 @@ export namespace std using ranges::find_last; using ranges::find_last_if; using ranges::find_last_if_not; +#endif +#if __cpp_lib_ranges_starts_ends_with + using ranges::starts_with; + using ranges::ends_with; #endif } } diff --git a/libstdc++-v3/testsuite/25_algorithms/ends_with/1.cc b/libstdc++-v3/testsuite/25_algorithms/ends_with/1.cc new file mode 100644 index 000000000000..e5714101aecc --- /dev/null +++ b/libstdc++-v3/testsuite/25_algorithms/ends_with/1.cc @@ -0,0 +1,129 @@ +// { dg-do run { target c++23 } } + +#include <algorithm> + +#include <testsuite_hooks.h> +#include <testsuite_iterators.h> + +namespace ranges = std::ranges; + +template<typename Range1, typename Range2> +void +test01() +{ + int n[] = {1,2,3,4,5,6,7,8,9,10}; + + Range1 haystack(n, n+10); + Range2 needle(n+7, n+10); + VERIFY( ranges::ends_with(haystack, needle) ); + + haystack = Range1(n); + needle = Range2(n, n+10); + VERIFY( ranges::ends_with(haystack, needle) ); + + haystack = Range1(n); + needle = Range2(n+6, n+9); + VERIFY( !ranges::ends_with(haystack, needle) ); + + haystack = Range1(n); + needle = Range2(n+6, n+9); + VERIFY( ranges::ends_with(haystack, needle, + [](int n, int m) { return std::abs(n - m) <= 1; }) ); + + haystack = Range1(n); + needle = Range2(n+6, n+9); + VERIFY( ranges::ends_with(haystack, needle, + ranges::equal_to{}, + [](int n) { return n - 1; }) ); + + haystack = Range1(n); + needle = Range2(n+6, n+9); + VERIFY( ranges::ends_with(haystack, needle, + ranges::equal_to{}, + std::identity{}, + [](int n) { return n + 1; }) ); + + haystack = Range1(n, n+5); + needle = Range2(n, n+10); + VERIFY( !ranges::ends_with(haystack, needle) ); +} + +template<typename Range1, typename Range2> +void +test02() +{ + int n[] = {1,2,3,4,5,6,7,8,9,10}; + + Range1 haystack(n, n+10); + Range2 needle(n+7, n+10); + VERIFY( ranges::ends_with(haystack.begin(), haystack.end(), + needle.begin(), needle.end()) ); + + haystack = Range1(n); + needle = Range2(n, n+10); + VERIFY( ranges::ends_with(haystack.begin(), haystack.end(), + needle.begin(), needle.end()) ); + + haystack = Range1(n); + needle = Range2(n+6, n+9); + VERIFY( !ranges::ends_with(haystack.begin(), haystack.end(), + needle.begin(), needle.end()) ); + + haystack = Range1(n); + needle = Range2(n+6, n+9); + VERIFY( ranges::ends_with(haystack.begin(), haystack.end(), + needle.begin(), needle.end(), + [](int n, int m) { return std::abs(n - m) <= 1; }) ); + + haystack = Range1(n); + needle = Range2(n+6, n+9); + VERIFY( ranges::ends_with(haystack.begin(), haystack.end(), + needle.begin(), needle.end(), + ranges::equal_to{}, + [](int n) { return n - 1; }) ); + + haystack = Range1(n); + needle = Range2(n+6, n+9); + VERIFY( ranges::ends_with(haystack.begin(), haystack.end(), + needle.begin(), needle.end(), + ranges::equal_to{}, + std::identity{}, + [](int n) { return n + 1; }) ); + + haystack = Range1(n, n+5); + needle = Range2(n, n+10); + VERIFY( !ranges::ends_with(haystack.begin(), haystack.end(), + needle.begin(), needle.end()) ); + + haystack = Range1(n, n+5); + needle = Range2(n+10, n+10); + VERIFY( ranges::ends_with(haystack.begin(), haystack.end(), + needle.begin(), needle.end()) ); +} + +int +main() +{ + using namespace __gnu_test; + using forward = test_forward_range<int>; + using input_sized = test_input_sized_range<int>; + using input_sized_sent = test_sized_range_sized_sent<int, input_iterator_wrapper>; + using random_access = test_random_access_range<int>; + using random_access_sized = test_random_access_sized_range<int>; + using random_access_sized_sent = test_sized_range_sized_sent<int, random_access_iterator_wrapper>; + + test01<forward, forward>(); + test01<random_access, random_access>(); + test02<forward, forward>(); + test02<random_access, random_access>(); + + test01<input_sized, input_sized>(); + test01<random_access_sized, random_access_sized>(); + // test02<input_sized, input_sized>(); constraint violation + test02<random_access_sized, random_access_sized>(); + + test01<input_sized_sent, input_sized_sent>(); + test01<random_access_sized_sent, random_access_sized_sent>(); + test02<input_sized_sent, input_sized_sent>(); + test02<random_access_sized_sent, random_access_sized_sent>(); +} diff --git a/libstdc++-v3/testsuite/25_algorithms/starts_with/1.cc b/libstdc++-v3/testsuite/25_algorithms/starts_with/1.cc new file mode 100644 index 000000000000..805f31ea2b03 --- /dev/null +++ b/libstdc++-v3/testsuite/25_algorithms/starts_with/1.cc @@ -0,0 +1,128 @@ +// { dg-do run { target c++23 } } + +#include <algorithm> + +#include <testsuite_hooks.h> +#include <testsuite_iterators.h> + +namespace ranges = std::ranges; + +template<typename Range1, typename Range2> +void +test01() +{ + int n[] = {1,2,3,4,5,6,7,8,9,10}; + + Range1 haystack(n, n+10); + Range2 needle(n, n+3); + VERIFY( ranges::starts_with(haystack, needle) ); + + haystack = Range1(n); + needle = Range2(n, n+10); + VERIFY( ranges::starts_with(haystack, needle) ); + + haystack = Range1(n); + needle = Range2(n+1, n+4); + VERIFY( !ranges::starts_with(haystack, needle) ); + + haystack = Range1(n); + needle = Range2(n+1, n+4); + VERIFY( ranges::starts_with(haystack, needle, + [](int n, int m) { return std::abs(n - m) <= 1; }) ); + + haystack = Range1(n); + needle = Range2(n+1, n+4); + VERIFY( ranges::starts_with(haystack, needle, + ranges::equal_to{}, + [](int n) { return n + 1; }) ); + + haystack = Range1(n); + needle = Range2(n+1, n+4); + VERIFY( ranges::starts_with(haystack, needle, + ranges::equal_to{}, + std::identity{}, + [](int n) { return n - 1; }) ); + + haystack = Range1(n, n+5); + needle = Range2(n, n+10); + VERIFY( !ranges::starts_with(haystack, needle) ); + + haystack = Range1(n, n+5); + needle = Range2(n+10, n+10); + VERIFY( ranges::starts_with(haystack, needle) ); +} + +template<typename Range1, typename Range2> +void +test02() +{ + int n[] = {1,2,3,4,5,6,7,8,9,10}; + + Range1 haystack(n, n+10); + Range2 needle(n, n+3); + VERIFY( ranges::starts_with(haystack.begin(), haystack.end(), + needle.begin(), needle.end()) ); + + haystack = Range1(n); + needle = Range2(n, n+10); + VERIFY( ranges::starts_with(haystack.begin(), haystack.end(), + needle.begin(), needle.end()) ); + + haystack = Range1(n); + needle = Range2(n+1, n+4); + VERIFY( !ranges::starts_with(haystack.begin(), haystack.end(), + needle.begin(), needle.end()) ); + + haystack = Range1(n); + needle = Range2(n+1, n+4); + VERIFY( ranges::starts_with(haystack.begin(), haystack.end(), + needle.begin(), needle.end(), + [](int n, int m) { return std::abs(n - m) <= 1; }) ); + + haystack = Range1(n); + needle = Range2(n+1, n+4); + VERIFY( ranges::starts_with(haystack.begin(), haystack.end(), + needle.begin(), needle.end(), + ranges::equal_to{}, + [](int n) { return n + 1; }) ); + + haystack = Range1(n); + needle = Range2(n+1, n+4); + VERIFY( ranges::starts_with(haystack.begin(), haystack.end(), + needle.begin(), needle.end(), + ranges::equal_to{}, + std::identity{}, + [](int n) { return n - 1; }) ); + + haystack = Range1(n, n+5); + needle = Range2(n, n+10); + VERIFY( !ranges::starts_with(haystack.begin(), haystack.end(), + needle.begin(), needle.end()) ); +} + +int +main() +{ + using namespace __gnu_test; + using input = test_input_range<int>; + using input_sized = test_input_sized_range<int>; + using input_sized_sent = test_sized_range_sized_sent<int, input_iterator_wrapper>; + using random_access = test_random_access_range<int>; + using random_access_sized = test_random_access_sized_range<int>; + using random_access_sized_sent = test_sized_range_sized_sent<int, random_access_iterator_wrapper>; + + test01<input, input>(); + test01<random_access, random_access>(); + test02<input, input>(); + test02<random_access, random_access>(); + + test01<input_sized, input_sized>(); + test01<random_access_sized, random_access_sized>(); + test02<input_sized, input_sized>(); + test02<random_access_sized, random_access_sized>(); + + test01<input_sized_sent, input_sized_sent>(); + test01<random_access_sized_sent, random_access_sized_sent>(); + test02<input_sized_sent, input_sized_sent>(); + test02<random_access_sized_sent, random_access_sized_sent>(); +} -- 2.49.0.608.gcb96e1697a