From 1d0a12dc55776a8209d4dea67b2a485923dbfdf5 Mon Sep 17 00:00:00 2001 From: Jonathan Wakely Date: Sat, 17 Jan 2015 03:15:52 +0000 Subject: [PATCH] DR 488 PR libstdc++/58357 DR 488 PR libstdc++/58357 * include/bits/algorithmfwd.h (rotate): Return an iterator. * include/bits/stl_algo.h (rotate, __rotate): Likewise. * testsuite/25_algorithms/rotate/dr488.cc: New. * testsuite/25_algorithms/rotate/check_type.cc: Adjust function type. * testsuite/25_algorithms/rotate/requirements/explicit_instantiation/ 2.cc: Likewise. * testsuite/25_algorithms/rotate/requirements/explicit_instantiation/ pod.cc: Likewise. From-SVN: r219793 --- libstdc++-v3/ChangeLog | 13 ++++ libstdc++-v3/include/bits/algorithmfwd.h | 2 +- libstdc++-v3/include/bits/stl_algo.h | 58 +++++++++----- .../25_algorithms/rotate/check_type.cc | 6 +- .../testsuite/25_algorithms/rotate/dr488.cc | 77 +++++++++++++++++++ .../requirements/explicit_instantiation/2.cc | 2 +- .../explicit_instantiation/pod.cc | 2 +- 7 files changed, 134 insertions(+), 26 deletions(-) create mode 100644 libstdc++-v3/testsuite/25_algorithms/rotate/dr488.cc diff --git a/libstdc++-v3/ChangeLog b/libstdc++-v3/ChangeLog index 1dc68e7f5e0..4b151e9663b 100644 --- a/libstdc++-v3/ChangeLog +++ b/libstdc++-v3/ChangeLog @@ -1,3 +1,16 @@ +2015-01-17 Jonathan Wakely + + DR 488 + PR libstdc++/58357 + * include/bits/algorithmfwd.h (rotate): Return an iterator. + * include/bits/stl_algo.h (rotate, __rotate): Likewise. + * testsuite/25_algorithms/rotate/dr488.cc: New. + * testsuite/25_algorithms/rotate/check_type.cc: Adjust function type. + * testsuite/25_algorithms/rotate/requirements/explicit_instantiation/ + 2.cc: Likewise. + * testsuite/25_algorithms/rotate/requirements/explicit_instantiation/ + pod.cc: Likewise. + 2015-01-17 Jonathan Wakely PR libstdc++/60940 diff --git a/libstdc++-v3/include/bits/algorithmfwd.h b/libstdc++-v3/include/bits/algorithmfwd.h index 283c5e6851f..11361bb948a 100644 --- a/libstdc++-v3/include/bits/algorithmfwd.h +++ b/libstdc++-v3/include/bits/algorithmfwd.h @@ -531,7 +531,7 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION reverse_copy(_BIter, _BIter, _OIter); template - void + _FIter rotate(_FIter, _FIter, _FIter); template diff --git a/libstdc++-v3/include/bits/stl_algo.h b/libstdc++-v3/include/bits/stl_algo.h index da642e6766d..3325b9499cc 100644 --- a/libstdc++-v3/include/bits/stl_algo.h +++ b/libstdc++-v3/include/bits/stl_algo.h @@ -1239,14 +1239,16 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION /// This is a helper function for the rotate algorithm. template - void + _ForwardIterator __rotate(_ForwardIterator __first, _ForwardIterator __middle, _ForwardIterator __last, forward_iterator_tag) { - if (__first == __middle || __last == __middle) - return; + if (__first == __middle) + return __last; + else if (__last == __middle) + return __first; _ForwardIterator __first2 = __middle; do @@ -1259,6 +1261,8 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION } while (__first2 != __last); + _ForwardIterator __ret = __first; + __first2 = __middle; while (__first2 != __last) @@ -1271,11 +1275,12 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION else if (__first2 == __last) __first2 = __middle; } + return __ret; } /// This is a helper function for the rotate algorithm. template - void + _BidirectionalIterator __rotate(_BidirectionalIterator __first, _BidirectionalIterator __middle, _BidirectionalIterator __last, @@ -1285,8 +1290,10 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION __glibcxx_function_requires(_Mutable_BidirectionalIteratorConcept< _BidirectionalIterator>) - if (__first == __middle || __last == __middle) - return; + if (__first == __middle) + return __last; + else if (__last == __middle) + return __first; std::__reverse(__first, __middle, bidirectional_iterator_tag()); std::__reverse(__middle, __last, bidirectional_iterator_tag()); @@ -1298,14 +1305,20 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION } if (__first == __middle) - std::__reverse(__middle, __last, bidirectional_iterator_tag()); + { + std::__reverse(__middle, __last, bidirectional_iterator_tag()); + return __last; + } else - std::__reverse(__first, __middle, bidirectional_iterator_tag()); + { + std::__reverse(__first, __middle, bidirectional_iterator_tag()); + return __first; + } } /// This is a helper function for the rotate algorithm. template - void + _RandomAccessIterator __rotate(_RandomAccessIterator __first, _RandomAccessIterator __middle, _RandomAccessIterator __last, @@ -1315,8 +1328,10 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept< _RandomAccessIterator>) - if (__first == __middle || __last == __middle) - return; + if (__first == __middle) + return __last; + else if (__last == __middle) + return __first; typedef typename iterator_traits<_RandomAccessIterator>::difference_type _Distance; @@ -1329,10 +1344,11 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION if (__k == __n - __k) { std::swap_ranges(__first, __middle, __middle); - return; + return __middle; } _RandomAccessIterator __p = __first; + _RandomAccessIterator __ret = __first + (__last - __middle); for (;;) { @@ -1343,7 +1359,7 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION _ValueType __t = _GLIBCXX_MOVE(*__p); _GLIBCXX_MOVE3(__p + 1, __p + __n, __p); *(__p + __n - 1) = _GLIBCXX_MOVE(__t); - return; + return __ret; } _RandomAccessIterator __q = __p + __k; for (_Distance __i = 0; __i < __n - __k; ++ __i) @@ -1354,7 +1370,7 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION } __n %= __k; if (__n == 0) - return; + return __ret; std::swap(__n, __k); __k = __n - __k; } @@ -1366,7 +1382,7 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION _ValueType __t = _GLIBCXX_MOVE(*(__p + __n - 1)); _GLIBCXX_MOVE_BACKWARD3(__p, __p + __n - 1, __p + __n); *__p = _GLIBCXX_MOVE(__t); - return; + return __ret; } _RandomAccessIterator __q = __p + __n; __p = __q - __k; @@ -1378,19 +1394,21 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION } __n %= __k; if (__n == 0) - return; + return __ret; std::swap(__n, __k); } } } + // _GLIBCXX_RESOLVE_LIB_DEFECTS + // DR 488. rotate throws away useful information /** * @brief Rotate the elements of a sequence. * @ingroup mutating_algorithms * @param __first A forward iterator. * @param __middle A forward iterator. * @param __last A forward iterator. - * @return Nothing. + * @return first + (last - middle). * * Rotates the elements of the range @p [__first,__last) by * @p (__middle - __first) positions so that the element at @p __middle @@ -1406,7 +1424,7 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION * for each @p n in the range @p [0,__last-__first). */ template - inline void + inline _ForwardIterator rotate(_ForwardIterator __first, _ForwardIterator __middle, _ForwardIterator __last) { @@ -1416,8 +1434,8 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION __glibcxx_requires_valid_range(__first, __middle); __glibcxx_requires_valid_range(__middle, __last); - std::__rotate(__first, __middle, __last, - std::__iterator_category(__first)); + return std::__rotate(__first, __middle, __last, + std::__iterator_category(__first)); } /** diff --git a/libstdc++-v3/testsuite/25_algorithms/rotate/check_type.cc b/libstdc++-v3/testsuite/25_algorithms/rotate/check_type.cc index f4643640b9e..9d4c3828a38 100644 --- a/libstdc++-v3/testsuite/25_algorithms/rotate/check_type.cc +++ b/libstdc++-v3/testsuite/25_algorithms/rotate/check_type.cc @@ -26,19 +26,19 @@ struct X { }; bool operator<(X,X) { return true;} -void +__gnu_test::forward_iterator_wrapper test1(__gnu_test::forward_iterator_wrapper& begin, __gnu_test::forward_iterator_wrapper& middle, __gnu_test::forward_iterator_wrapper& end) { return std::rotate(begin,middle,end); } -void +__gnu_test::bidirectional_iterator_wrapper test1(__gnu_test::bidirectional_iterator_wrapper& begin, __gnu_test::bidirectional_iterator_wrapper& middle, __gnu_test::bidirectional_iterator_wrapper& end) { return std::rotate(begin,middle,end); } -void +__gnu_test::random_access_iterator_wrapper test1(__gnu_test::random_access_iterator_wrapper& begin, __gnu_test::random_access_iterator_wrapper& middle, __gnu_test::random_access_iterator_wrapper& end) diff --git a/libstdc++-v3/testsuite/25_algorithms/rotate/dr488.cc b/libstdc++-v3/testsuite/25_algorithms/rotate/dr488.cc new file mode 100644 index 00000000000..60bd03308ef --- /dev/null +++ b/libstdc++-v3/testsuite/25_algorithms/rotate/dr488.cc @@ -0,0 +1,77 @@ +// Copyright (C) 2015 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++11" } + +#include +#include +#include +#include +#include +#include + +template +void +test(Container& c) +{ + int size = std::distance(c.begin(), c.end()); + for (int i=0; i < size; ++i) + { + auto first = c.begin(), middle = std::next(first, i), last = c.end(); + auto r = std::rotate(first, middle, last); + auto expected = std::next(first, std::distance(middle, last)); + VERIFY( r == expected ); + } +} + +void +test01() +{ + // test random access iterators + std::vector v{ 0, 1, 2, 3, 4 }; + test(v); + v.push_back(5); + test(v); +} + +void +test02() +{ + // test bidirectional iterators + std::list l{ 0, 1, 2, 3, 4 }; + test(l); + l.push_back(5); + test(l); +} + +void +test03() +{ + // test forward iterators + std::forward_list l{ 0, 1, 2, 3, 4 }; + test(l); + l.push_front(5); + test(l); +} + +int +main() +{ + test01(); + test02(); + test03(); +} diff --git a/libstdc++-v3/testsuite/25_algorithms/rotate/requirements/explicit_instantiation/2.cc b/libstdc++-v3/testsuite/25_algorithms/rotate/requirements/explicit_instantiation/2.cc index d48e6537498..ec8c917801e 100644 --- a/libstdc++-v3/testsuite/25_algorithms/rotate/requirements/explicit_instantiation/2.cc +++ b/libstdc++-v3/testsuite/25_algorithms/rotate/requirements/explicit_instantiation/2.cc @@ -30,5 +30,5 @@ namespace std typedef NonDefaultConstructible value_type; typedef value_type* iterator_type; - template void rotate(iterator_type, iterator_type, iterator_type); + template iterator_type rotate(iterator_type, iterator_type, iterator_type); } diff --git a/libstdc++-v3/testsuite/25_algorithms/rotate/requirements/explicit_instantiation/pod.cc b/libstdc++-v3/testsuite/25_algorithms/rotate/requirements/explicit_instantiation/pod.cc index 5804c6326c2..c24ee70c0c8 100644 --- a/libstdc++-v3/testsuite/25_algorithms/rotate/requirements/explicit_instantiation/pod.cc +++ b/libstdc++-v3/testsuite/25_algorithms/rotate/requirements/explicit_instantiation/pod.cc @@ -30,5 +30,5 @@ namespace std typedef pod_int value_type; typedef value_type* iterator_type; - template void rotate(iterator_type, iterator_type, iterator_type); + template iterator_type rotate(iterator_type, iterator_type, iterator_type); } -- 2.30.2