diff options
author | Patrick Palka <ppalka@redhat.com> | 2020-02-21 13:55:01 -0500 |
---|---|---|
committer | Patrick Palka <ppalka@redhat.com> | 2020-02-24 10:08:57 -0500 |
commit | c5eab4ed45e9762dfb8a58d2b5672d358467ad89 (patch) | |
tree | ed6aeb75a5597310ddc61c3da5fd070698b5ab8f | |
parent | 027a3f1c38727a1ea0969088b0680b2f6bb1e977 (diff) | |
download | gcc-c5eab4ed45e9762dfb8a58d2b5672d358467ad89.zip gcc-c5eab4ed45e9762dfb8a58d2b5672d358467ad89.tar.gz gcc-c5eab4ed45e9762dfb8a58d2b5672d358467ad89.tar.bz2 |
libstdc++: P0769R2 Add shift to <algorithm>
This patch adds std::shift_left and std::shift_right as per P0769R2. Alhough
these are STL-style algos, this patch places them in <bits/ranges_algo.h>
because they make use of some functions in the ranges namespace that are more
easily reachable from <bits/ranges_algo.h> than from <bits/stl_algo.h>, namely
ranges::next. In order to place these algos in <bits/stl_algo.h>, we would need
to include <bits/range_access.h> from <bits/stl_algo.h> which would undesirably
increase the size of <bits/stl_algo.h>.
libstdc++-v3/ChangeLog:
P0769R2 Add shift to <algorithm>
* 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.
-rw-r--r-- | libstdc++-v3/ChangeLog | 7 | ||||
-rw-r--r-- | libstdc++-v3/include/bits/ranges_algo.h | 92 | ||||
-rw-r--r-- | libstdc++-v3/testsuite/25_algorithms/shift_left/1.cc | 104 | ||||
-rw-r--r-- | libstdc++-v3/testsuite/25_algorithms/shift_right/1.cc | 103 |
4 files changed, 306 insertions, 0 deletions
diff --git a/libstdc++-v3/ChangeLog b/libstdc++-v3/ChangeLog index eefb2a5..9996c19 100644 --- a/libstdc++-v3/ChangeLog +++ b/libstdc++-v3/ChangeLog @@ -1,3 +1,10 @@ +2020-02-24 Patrick Palka <ppalka@redhat.com> + + P0769R2 Add shift to <algorithm> + * 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 <jwakely@redhat.com> * 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 7de1072..7d7dbf0 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<class ForwardIterator> + constexpr ForwardIterator + shift_left(ForwardIterator __first, ForwardIterator __last, + typename iterator_traits<ForwardIterator>::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<class ForwardIterator> + constexpr ForwardIterator + shift_right(ForwardIterator __first, ForwardIterator __last, + typename iterator_traits<ForwardIterator>::difference_type __n) + { + __glibcxx_assert(__n >= 0); + if (__n == 0) + return __first; + + using _Cat = iterator_traits<ForwardIterator>::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 0000000..f7a716e --- /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 +// <http://www.gnu.org/licenses/>. + +// { dg-options "-std=gnu++2a" } +// { dg-do run { target c++2a } } + +#include <algorithm> +#include <testsuite_hooks.h> +#include <testsuite_iterators.h> + +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<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_container<X, Wrapper> 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 0000000..cf736ea --- /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 +// <http://www.gnu.org/licenses/>. + +// { dg-options "-std=gnu++2a" } +// { dg-do run { target c++2a } } + +#include <algorithm> +#include <testsuite_hooks.h> +#include <testsuite_iterators.h> + +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<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_container<X, Wrapper> 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>(); +} |