From c5eab4ed45e9762dfb8a58d2b5672d358467ad89 Mon Sep 17 00:00:00 2001 From: Patrick Palka Date: Fri, 21 Feb 2020 13:55:01 -0500 Subject: [PATCH] libstdc++: P0769R2 Add shift to This patch adds std::shift_left and std::shift_right as per P0769R2. Alhough these are STL-style algos, this patch places them in because they make use of some functions in the ranges namespace that are more easily reachable from than from , namely ranges::next. In order to place these algos in , we would need to include from which would undesirably increase the size of . libstdc++-v3/ChangeLog: P0769R2 Add shift to * include/bits/ranges_algo.h (shift_left, shift_right): New. * testsuite/25_algorithms/shift_left/1.cc: New test. * testsuite/25_algorithms/shift_right/1.cc: New test. --- libstdc++-v3/ChangeLog | 7 ++ libstdc++-v3/include/bits/ranges_algo.h | 92 ++++++++++++++++ .../testsuite/25_algorithms/shift_left/1.cc | 104 ++++++++++++++++++ .../testsuite/25_algorithms/shift_right/1.cc | 103 +++++++++++++++++ 4 files changed, 306 insertions(+) create mode 100644 libstdc++-v3/testsuite/25_algorithms/shift_left/1.cc create mode 100644 libstdc++-v3/testsuite/25_algorithms/shift_right/1.cc diff --git a/libstdc++-v3/ChangeLog b/libstdc++-v3/ChangeLog index eefb2a5bd42..9996c1955d0 100644 --- a/libstdc++-v3/ChangeLog +++ b/libstdc++-v3/ChangeLog @@ -1,3 +1,10 @@ +2020-02-24 Patrick Palka + + P0769R2 Add shift to + * include/bits/ranges_algo.h (shift_left, shift_right): New. + * testsuite/25_algorithms/shift_left/1.cc: New test. + * testsuite/25_algorithms/shift_right/1.cc: New test. + 2020-02-24 Jonathan Wakely * include/bits/stream_iterator.h (istream_iterator(default_sentinel_t)): diff --git a/libstdc++-v3/include/bits/ranges_algo.h b/libstdc++-v3/include/bits/ranges_algo.h index 7de1072abf0..7d7dbf04103 100644 --- a/libstdc++-v3/include/bits/ranges_algo.h +++ b/libstdc++-v3/include/bits/ranges_algo.h @@ -3683,6 +3683,98 @@ namespace ranges inline constexpr __prev_permutation_fn prev_permutation{}; } // namespace ranges + + template + constexpr ForwardIterator + shift_left(ForwardIterator __first, ForwardIterator __last, + typename iterator_traits::difference_type __n) + { + __glibcxx_assert(__n >= 0); + if (__n == 0) + return __last; + + auto __mid = ranges::next(__first, __n, __last); + if (__mid == __last) + return __first; + return std::move(std::move(__mid), std::move(__last), std::move(__first)); + } + + template + constexpr ForwardIterator + shift_right(ForwardIterator __first, ForwardIterator __last, + typename iterator_traits::difference_type __n) + { + __glibcxx_assert(__n >= 0); + if (__n == 0) + return __first; + + using _Cat = iterator_traits::iterator_category; + if constexpr (derived_from<_Cat, bidirectional_iterator_tag>) + { + auto __mid = ranges::next(__last, -__n, __first); + if (__mid == __first) + return __last; + + return std::move_backward(std::move(__first), std::move(__mid), + std::move(__last)); + } + else + { + auto __result = ranges::next(__first, __n, __last); + if (__result == __last) + return __last; + + 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. + std::move(std::move(__first), std::move(__dest_head), + std::move(__result)); + return __result; + } + ++__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 = std::move(__cursor, __result, + std::move(__dest_head)); + std::move(std::move(__first), std::move(__cursor), + std::move(__dest_head)); + return __result; + } + std::iter_swap(__cursor, __dest_head); + ++__dest_head; + ++__dest_tail; + ++__cursor; + } + } + } + } + _GLIBCXX_END_NAMESPACE_VERSION } // namespace std #endif // concepts diff --git a/libstdc++-v3/testsuite/25_algorithms/shift_left/1.cc b/libstdc++-v3/testsuite/25_algorithms/shift_left/1.cc new file mode 100644 index 00000000000..f7a716e0563 --- /dev/null +++ b/libstdc++-v3/testsuite/25_algorithms/shift_left/1.cc @@ -0,0 +1,104 @@ +// Copyright (C) 2020 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 +// . + +// { dg-options "-std=gnu++2a" } +// { dg-do run { target c++2a } } + +#include +#include +#include + +using __gnu_test::test_container; +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 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_container cx(x); + auto out = std::shift_left(cx.begin(), cx.end(), n); + 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/1.cc b/libstdc++-v3/testsuite/25_algorithms/shift_right/1.cc new file mode 100644 index 00000000000..cf736ea91b1 --- /dev/null +++ b/libstdc++-v3/testsuite/25_algorithms/shift_right/1.cc @@ -0,0 +1,103 @@ +// Copyright (C) 2020 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 +// . + +// { dg-options "-std=gnu++2a" } +// { dg-do run { target c++2a } } + +#include +#include +#include + +using __gnu_test::test_container; +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 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_container cx(x); + auto out = std::shift_right(cx.begin(), cx.end(), n); + 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>(); +} -- 2.30.2