From patchwork Sat Jan 17 03:16:07 2015 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Jonathan Wakely X-Patchwork-Id: 430091 Return-Path: X-Original-To: incoming@patchwork.ozlabs.org Delivered-To: patchwork-incoming@bilbo.ozlabs.org Received: from sourceware.org (server1.sourceware.org [209.132.180.131]) (using TLSv1.2 with cipher ECDHE-RSA-AES256-GCM-SHA384 (256/256 bits)) (No client certificate requested) by ozlabs.org (Postfix) with ESMTPS id 795D41401EB for ; Sat, 17 Jan 2015 14:16:47 +1100 (AEDT) DomainKey-Signature: a=rsa-sha1; c=nofws; d=gcc.gnu.org; h=list-id :list-unsubscribe:list-archive:list-post:list-help:sender:date :from:to:subject:message-id:mime-version:content-type; q=dns; s= default; b=hfGWQDa9F1/kNzINemDQtaP1xJIs8kkxzYdUxvB771UgorH1GppOR D8cnM21pgu2yDeatTCaHyzN0RbzFei/RJkQy1mCjrpqZoj/qRvTa38K3r3Gc6lw5 sMLaYMf06qhtLjwqKyIM1UqdzlPFpoQ4o6gPvjfnqAmgIwFGWBtcg0= DKIM-Signature: v=1; a=rsa-sha1; c=relaxed; d=gcc.gnu.org; h=list-id :list-unsubscribe:list-archive:list-post:list-help:sender:date :from:to:subject:message-id:mime-version:content-type; s= default; bh=Z/TaVMRSppcvlyM3mYpmJM3bXd0=; b=Vx8r7teftm9+ZrCYfcLB g2LUnHhztZdi9Vr192fWzOHPM8fYbM4yOd8Ix+h1TyeOmSrtLFyhqYvXqQM0nYmu B5tKJ9j/nfUDeYMfPErSdzWht3rGaaMep+U46Dam/Ms0sv0qasYz4Nm/96PxXpN/ 1mwnwWfJFn+YUBG6Wj4vDGc= Received: (qmail 23065 invoked by alias); 17 Jan 2015 03:16:38 -0000 Mailing-List: contact gcc-patches-help@gcc.gnu.org; run by ezmlm Precedence: bulk List-Id: List-Unsubscribe: List-Archive: List-Post: List-Help: Sender: gcc-patches-owner@gcc.gnu.org Delivered-To: mailing list gcc-patches@gcc.gnu.org Received: (qmail 22944 invoked by uid 89); 17 Jan 2015 03:16:25 -0000 Authentication-Results: sourceware.org; auth=none X-Virus-Found: No X-Spam-SWARE-Status: No, score=-2.0 required=5.0 tests=AWL, BAYES_00, SPF_HELO_PASS, SPF_PASS, T_RP_MATCHES_RCVD autolearn=ham version=3.3.2 X-Spam-User: qpsmtpd, 2 recipients X-HELO: mx1.redhat.com Received: from mx1.redhat.com (HELO mx1.redhat.com) (209.132.183.28) by sourceware.org (qpsmtpd/0.93/v0.84-503-g423c35a) with (AES256-GCM-SHA384 encrypted) ESMTPS; Sat, 17 Jan 2015 03:16:11 +0000 Received: from int-mx11.intmail.prod.int.phx2.redhat.com (int-mx11.intmail.prod.int.phx2.redhat.com [10.5.11.24]) by mx1.redhat.com (8.14.4/8.14.4) with ESMTP id t0H3G9pI031956 (version=TLSv1/SSLv3 cipher=DHE-RSA-AES256-GCM-SHA384 bits=256 verify=FAIL); Fri, 16 Jan 2015 22:16:09 -0500 Received: from localhost (ovpn-116-25.ams2.redhat.com [10.36.116.25]) by int-mx11.intmail.prod.int.phx2.redhat.com (8.14.4/8.14.4) with ESMTP id t0H3G8LR014838; Fri, 16 Jan 2015 22:16:09 -0500 Date: Sat, 17 Jan 2015 03:16:07 +0000 From: Jonathan Wakely To: libstdc++@gcc.gnu.org, gcc-patches@gcc.gnu.org Subject: [patch] libstdc++/58357 DR 488 std::rotate should return an iterator Message-ID: <20150117031607.GP3360@redhat.com> MIME-Version: 1.0 Content-Disposition: inline User-Agent: Mutt/1.5.23 (2014-03-12) http://cplusplus.github.io/LWG/lwg-defects.html#488 Tested x86_64-linux, committed to trunk. commit a5ae94562335d47358186f76ca71cc6cf0560ed8 Author: Jonathan Wakely Date: Tue Sep 23 00:11:26 2014 +0100 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. diff --git a/libstdc++-v3/include/bits/algorithmfwd.h b/libstdc++-v3/include/bits/algorithmfwd.h index 283c5e6..11361bb 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 da642e6..3325b94 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 f464364..9d4c382 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 0000000..60bd033 --- /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 d48e653..ec8c917 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 5804c63..c24ee70 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); }