https://gcc.gnu.org/g:2a56f3c539b782b15ee76d5752921800ccc53eef
commit r16-2042-g2a56f3c539b782b15ee76d5752921800ccc53eef Author: Patrick Palka <ppa...@redhat.com> Date: Sun Jul 6 14:49:34 2025 -0400 libstdc++: Implement ranges::shift_left/right from P2440R1 The implementation is just a copy of std::shift_left/right with the following changes: - check bidirectional_iterator instead of iterator_category - cope with __last being a distinct sentinel type - for shift_left, return the subrange {__first, X} instead of X - for shift_right, return the subrange {X, ranges::next(__first, __last)} instead of X - use the ranges:: versions of move_backward, move and iter_swap - don't bother std::move'ing any iterators, it's unnecessary since all iterators are forward, it's visually noisy, and in earlier versions of this patch it introduced subtle use-after-move bugs In passing also use the __glibcxx_shift macro to guard the std::shift_left/right implementations. libstdc++-v3/ChangeLog: * include/bits/ranges_algo.h (shift_left, shift_right): Guard with __glibcxx_shift >= 201806L. (ranges::__shift_left_fn, ranges::shift_left): Define for C++23. (ranges::__shift_right_fn, ranges::shift_right): Likewise. * include/bits/version.def (shift): Update for C++23. * include/bits/version.h: Regenerate. * src/c++23/std.cc.in: Add ranges::shift_left/right. * testsuite/25_algorithms/shift_left/constrained.cc: New test, based off of 1.cc. * testsuite/25_algorithms/shift_right/constrained.cc: New test, based off of 1.cc. Reviewed-by: Jonathan Wakely <jwak...@redhat.com> Diff: --- libstdc++-v3/include/bits/ranges_algo.h | 115 +++++++++++++++++++++ libstdc++-v3/include/bits/version.def | 4 + libstdc++-v3/include/bits/version.h | 7 +- libstdc++-v3/src/c++23/std.cc.in | 8 +- .../25_algorithms/shift_left/constrained.cc | 105 +++++++++++++++++++ .../25_algorithms/shift_right/constrained.cc | 104 +++++++++++++++++++ 6 files changed, 340 insertions(+), 3 deletions(-) diff --git a/libstdc++-v3/include/bits/ranges_algo.h b/libstdc++-v3/include/bits/ranges_algo.h index cf369c5d4dde..9f8945a7133a 100644 --- a/libstdc++-v3/include/bits/ranges_algo.h +++ b/libstdc++-v3/include/bits/ranges_algo.h @@ -5218,6 +5218,7 @@ namespace ranges #endif // __glibcxx_ranges_fold } // namespace ranges +#if __glibcxx_shift >= 201806L // C++ >= 20 template<typename _ForwardIterator> constexpr _ForwardIterator shift_left(_ForwardIterator __first, _ForwardIterator __last, @@ -5308,6 +5309,120 @@ namespace ranges } } } +#endif + +namespace ranges +{ +#if __glibcxx_shift >= 202202L // C++ >= 23 + struct __shift_left_fn + { + template<permutable _Iter, sentinel_for<_Iter> _Sent> + constexpr subrange<_Iter> + operator()(_Iter __first, _Sent __last, iter_difference_t<_Iter> __n) const + { + __glibcxx_assert(__n >= 0); + if (__n == 0) + return {__first, ranges::next(__first, __last)}; + + auto __mid = ranges::next(__first, __n, __last); + if (__mid == __last) + return {__first, __first}; + return {__first, ranges::move(__mid, __last, __first).out}; + } + + template<forward_range _Range> + requires permutable<iterator_t<_Range>> + constexpr borrowed_subrange_t<_Range> + operator()(_Range&& __r, range_difference_t<_Range> __n) const + { return (*this)(ranges::begin(__r), ranges::end(__r), __n); } + }; + + inline constexpr __shift_left_fn shift_left{}; + + struct __shift_right_fn + { + template<permutable _Iter, sentinel_for<_Iter> _Sent> + constexpr subrange<_Iter> + operator()(_Iter __first, _Sent __last, iter_difference_t<_Iter> __n) const + { + __glibcxx_assert(__n >= 0); + if (__n == 0) + return {__first, ranges::next(__first, __last)}; + + if constexpr (bidirectional_iterator<_Iter> && same_as<_Iter, _Sent>) + { + auto __mid = ranges::next(__last, -__n, __first); + if (__mid == __first) + return {__last, __last}; + + return {ranges::move_backward(__first, __mid, __last).out, __last}; + } + else + { + auto __result = ranges::next(__first, __n, __last); + if (__result == __last) + return {__result, __result}; + + auto __dest_head = __first, __dest_tail = __result; + while (__dest_head != __result) + { + if (__dest_tail == __last) + { + // If we get here, then we must have + // 2*n >= distance(__first, __last) + // i.e. we are shifting out at least half of the range. In + // this case we can safely perform the shift with a single + // move. + auto __lasti = ranges::move(__first, __dest_head, __result).out; + // __glibcxx_assert(__lasti == __last); + return {__result, __lasti}; + } + ++__dest_head; + ++__dest_tail; + } + + for (;;) + { + // At the start of each iteration of this outer loop, the range + // [__first, __result) contains those elements that after shifting + // the whole range right by __n, should end up in + // [__dest_head, __dest_tail) in order. + + // The below inner loop swaps the elements of [__first, __result) + // and [__dest_head, __dest_tail), while simultaneously shifting + // the latter range by __n. + auto __cursor = __first; + while (__cursor != __result) + { + if (__dest_tail == __last) + { + // At this point the ranges [__first, result) and + // [__dest_head, dest_tail) are disjoint, so we can safely + // move the remaining elements. + __dest_head = ranges::move(__cursor, __result, __dest_head).out; + auto __lasti = ranges::move(__first, __cursor, __dest_head).out; + // __glibcxx_assert(__lasti == __last); + return {__result, __lasti}; + } + ranges::iter_swap(__cursor, __dest_head); + ++__dest_head; + ++__dest_tail; + ++__cursor; + } + } + } + } + + template<forward_range _Range> + requires permutable<iterator_t<_Range>> + constexpr borrowed_subrange_t<_Range> + operator()(_Range&& __r, range_difference_t<_Range> __n) const + { return (*this)(ranges::begin(__r), ranges::end(__r), __n); } + }; + + inline constexpr __shift_right_fn shift_right{}; +#endif // C++23 +} // namespace ranges _GLIBCXX_END_NAMESPACE_VERSION } // namespace std diff --git a/libstdc++-v3/include/bits/version.def b/libstdc++-v3/include/bits/version.def index 5d5758bf2033..64f8190d240b 100644 --- a/libstdc++-v3/include/bits/version.def +++ b/libstdc++-v3/include/bits/version.def @@ -1091,6 +1091,10 @@ ftms = { ftms = { name = shift; + values = { + v = 202202; + cxxmin = 23; + }; values = { v = 201806; cxxmin = 20; diff --git a/libstdc++-v3/include/bits/version.h b/libstdc++-v3/include/bits/version.h index 2b00e8419b3a..744246a9938a 100644 --- a/libstdc++-v3/include/bits/version.h +++ b/libstdc++-v3/include/bits/version.h @@ -1224,7 +1224,12 @@ #undef __glibcxx_want_constexpr_utility #if !defined(__cpp_lib_shift) -# if (__cplusplus >= 202002L) +# if (__cplusplus >= 202100L) +# define __glibcxx_shift 202202L +# if defined(__glibcxx_want_all) || defined(__glibcxx_want_shift) +# define __cpp_lib_shift 202202L +# endif +# elif (__cplusplus >= 202002L) # define __glibcxx_shift 201806L # if defined(__glibcxx_want_all) || defined(__glibcxx_want_shift) # define __cpp_lib_shift 201806L diff --git a/libstdc++-v3/src/c++23/std.cc.in b/libstdc++-v3/src/c++23/std.cc.in index 483b6c62443c..86e6d88904b3 100644 --- a/libstdc++-v3/src/c++23/std.cc.in +++ b/libstdc++-v3/src/c++23/std.cc.in @@ -278,10 +278,14 @@ export namespace std } using std::shift_left; namespace ranges - {} + { + using std::ranges::shift_left; + } using std::shift_right; namespace ranges - {} + { + using std::ranges::shift_right; + } using std::sort; namespace ranges { diff --git a/libstdc++-v3/testsuite/25_algorithms/shift_left/constrained.cc b/libstdc++-v3/testsuite/25_algorithms/shift_left/constrained.cc new file mode 100644 index 000000000000..73d061439885 --- /dev/null +++ b/libstdc++-v3/testsuite/25_algorithms/shift_left/constrained.cc @@ -0,0 +1,105 @@ +// Copyright (C) 2020-2025 Free Software Foundation, Inc. +// +// This file is part of the GNU ISO C++ Library. This library is free +// software; you can redistribute it and/or modify it under the +// terms of the GNU General Public License as published by the +// Free Software Foundation; either version 3, or (at your option) +// any later version. + +// This library is distributed in the hope that it will be useful, +// but WITHOUT ANY WARRANTY; without even the implied warranty of +// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the +// GNU General Public License for more details. + +// You should have received a copy of the GNU General Public License along +// with this library; see the file COPYING3. If not see +// <http://www.gnu.org/licenses/>. + +// { dg-do run { target c++23 } } +// This test is based on shift_left/1.cc. + +#include <algorithm> +#include <testsuite_hooks.h> +#include <testsuite_iterators.h> + +using __gnu_test::test_range; +using __gnu_test::forward_iterator_wrapper; +using __gnu_test::bidirectional_iterator_wrapper; +using __gnu_test::random_access_iterator_wrapper; + +struct X +{ + int a = -1; + bool moved_from = false; + + X() = default; + + X(int a) + : a(a) + { } + + X(const X&) = delete; + X& operator=(const X&) = delete; + + X(X&& other) + { + if (this != &other) + *this = std::move(other); + } + + X& + operator=(X&& other) + { + a = other.a; + other.moved_from = true; + moved_from = false; + return *this; + } +}; + +template<int N, template<typename> typename Wrapper> +void +test01() +{ + for (int n = 0; n < N+5; n++) + { + X x[N]; + for (int i = 0; i < N; i++) + x[i] = X{i}; + test_range<X, Wrapper> rx(x); + auto [first,out] = std::ranges::shift_left(rx.begin(), rx.end(), n); + VERIFY( first == rx.begin() ); + if (n < N) + { + VERIFY( out.ptr == x+(N-n) ); + for (int i = 0; i < N-n; i++) + { + VERIFY( x[i].a == n+i ); + VERIFY( !x[i].moved_from ); + } + for (int i = std::max(n, N-n); i < N; i++) + VERIFY( x[i].moved_from ); + } + else + { + VERIFY( out.ptr == x ); + for (int i = 0; i < N; i++) + { + VERIFY( x[i].a == i ); + VERIFY( !x[i].moved_from ); + } + } + } +} + +int +main() +{ + test01<23, forward_iterator_wrapper>(); + test01<23, bidirectional_iterator_wrapper>(); + test01<23, random_access_iterator_wrapper>(); + + test01<24, forward_iterator_wrapper>(); + test01<24, bidirectional_iterator_wrapper>(); + test01<24, random_access_iterator_wrapper>(); +} diff --git a/libstdc++-v3/testsuite/25_algorithms/shift_right/constrained.cc b/libstdc++-v3/testsuite/25_algorithms/shift_right/constrained.cc new file mode 100644 index 000000000000..0d53707237e4 --- /dev/null +++ b/libstdc++-v3/testsuite/25_algorithms/shift_right/constrained.cc @@ -0,0 +1,104 @@ +// Copyright (C) 2020-2025 Free Software Foundation, Inc. +// +// This file is part of the GNU ISO C++ Library. This library is free +// software; you can redistribute it and/or modify it under the +// terms of the GNU General Public License as published by the +// Free Software Foundation; either version 3, or (at your option) +// any later version. + +// This library is distributed in the hope that it will be useful, +// but WITHOUT ANY WARRANTY; without even the implied warranty of +// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the +// GNU General Public License for more details. + +// You should have received a copy of the GNU General Public License along +// with this library; see the file COPYING3. If not see +// <http://www.gnu.org/licenses/>. + +// { dg-do run { target c++23 } } +// This test is based on shift_right/1.cc. + +#include <algorithm> +#include <testsuite_hooks.h> +#include <testsuite_iterators.h> + +using __gnu_test::test_range; +using __gnu_test::forward_iterator_wrapper; +using __gnu_test::bidirectional_iterator_wrapper; +using __gnu_test::random_access_iterator_wrapper; + +struct X +{ + int a = -1; + bool moved_from = false; + + X() = default; + + X(int a) + : a(a) + { } + + X(const X&) = delete; + X& operator=(const X&) = delete; + + X(X&& other) + { + if (this != &other) + *this = std::move(other); + } + + X& + operator=(X&& other) + { + a = other.a; + other.moved_from = true; + moved_from = false; + return *this; + } +}; + +template<int N, template<typename> typename Wrapper> +void +test01() +{ + for (int n = 0; n < N+5; n++) + { + X x[N]; + for (int i = 0; i < N; i++) + x[i] = X(i); + test_range<X, Wrapper> rx(x); + auto [out,last] = std::ranges::shift_right(rx.begin(), rx.end(), n); + VERIFY( last == rx.end() ); + if (n < N) + { + VERIFY( out.ptr == x+n ); + for (int i = n; i < N; i++) + VERIFY( x[i].a == i-n ); + for (int i = 0; i < std::min(n, N-n); i++) + VERIFY( x[i].moved_from ); + for (int i = std::min(n, N-n); i < std::max(n, N-n); i++) + VERIFY( !x[i].moved_from ); + } + else + { + VERIFY( out.ptr == x+N ); + for (int i = 0; i < N; i++) + { + VERIFY( x[i].a == i ); + VERIFY( !x[i].moved_from ); + } + } + } +} + +int +main() +{ + test01<23, forward_iterator_wrapper>(); + test01<23, bidirectional_iterator_wrapper>(); + test01<23, random_access_iterator_wrapper>(); + + test01<24, forward_iterator_wrapper>(); + test01<24, bidirectional_iterator_wrapper>(); + test01<24, random_access_iterator_wrapper>(); +}