From patchwork Mon Jun 17 00:48:09 2013 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Jonathan Wakely X-Patchwork-Id: 251754 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 with cipher DHE-RSA-AES256-SHA (256/256 bits)) (Client CN "localhost", Issuer "www.qmailtoaster.com" (not verified)) by ozlabs.org (Postfix) with ESMTPS id 046472C00B1 for ; Mon, 17 Jun 2013 10:48:19 +1000 (EST) DomainKey-Signature: a=rsa-sha1; c=nofws; d=gcc.gnu.org; h=list-id :list-unsubscribe:list-archive:list-post:list-help:sender :mime-version:in-reply-to:references:date:message-id:subject :from:to:cc:content-type; q=dns; s=default; b=BdhzwCX2R2bLJjrsR1 +9G7xTOcvxsCGs6k8XFGqekSDLe4etVzQCFzi32xEAM1ql4AqdjFVxUxuRdx2/qr PgDMgVNMbsD9TZ/5k8AhExQRek59sHVuq6mXqljmda6u3nagxd1T1f+gfZ7YsoT4 Y5hVTj/o/uFNhUeTd+hyzesI4= 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 :mime-version:in-reply-to:references:date:message-id:subject :from:to:cc:content-type; s=default; bh=UO/VzRcLX3QD2K7E+evZ7yec 1WY=; b=QgTiSkmXjOyIuRQPqMFIHsGiIUYpKSPnuZbxZ+1znu7Ug/8zMODQ7T8Z chLxxaBFG502mel/EpgZTX4xEmU5ICjTrgPEZp5LeVQwR8aXVJ4cpH8DDX6yD6NZ ylPLO+742n86fOoZKJiODeM2UWUehHBCfEJ6jC93egqV6G5tPpc= Received: (qmail 17660 invoked by alias); 17 Jun 2013 00:48:14 -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 17646 invoked by uid 89); 17 Jun 2013 00:48:13 -0000 X-Spam-SWARE-Status: No, score=-3.5 required=5.0 tests=AWL, BAYES_00, FREEMAIL_FROM, KHOP_THREADED, RCVD_IN_DNSWL_LOW, RCVD_IN_HOSTKARMA_YE, SPF_PASS autolearn=ham version=3.3.1 X-Spam-User: qpsmtpd, 2 recipients Received: from mail-lb0-f170.google.com (HELO mail-lb0-f170.google.com) (209.85.217.170) by sourceware.org (qpsmtpd/0.84/v0.84-167-ge50287c) with ESMTP; Mon, 17 Jun 2013 00:48:12 +0000 Received: by mail-lb0-f170.google.com with SMTP id t13so1994310lbd.1 for ; Sun, 16 Jun 2013 17:48:09 -0700 (PDT) MIME-Version: 1.0 X-Received: by 10.152.29.227 with SMTP id n3mr5546104lah.43.1371430089478; Sun, 16 Jun 2013 17:48:09 -0700 (PDT) Received: by 10.112.160.104 with HTTP; Sun, 16 Jun 2013 17:48:09 -0700 (PDT) In-Reply-To: References: <51B64E6C.4080408@bubblescope.net> Date: Mon, 17 Jun 2013 01:48:09 +0100 Message-ID: Subject: Re: [patch] C++14: N3671 Making non-modifying sequence operations more robust From: Jonathan Wakely To: Chris Jefferson , gcc-patches Cc: "libstdc++" X-Virus-Found: No On 15 June 2013 16:48, Jonathan Wakely wrote: > On 11 June 2013 00:11, Jonathan Wakely wrote: >> On 10 June 2013 23:08, Chris Jefferson wrote: >>> After we are in the 'if(__ra_iters)' case, and checked that __d1==__d2, >>> could dispatch to old-fashioned equal(__first1, __last1, __first2, >>> __binary_pred). This has the advantage that it saves repeatedly checking >>> __first2 != __last2 unnessasairly, and I suspect only having one loop >>> condition to check will give the compiler a better shot at optimising / >>> unrolling (although, I haven't checked that I will admit). >> >> Good idea, thanks, I'll make that change too. > > How's this? I made both the new std::equal() overloads defer to the > old ones when both sets of iterators are random access. That means > there's no need for the __equal2 class template, the memcmp special > case for pointers is handled by the old std::equal(). I'm committing the attached, which also fixes some silly typos in the new is_permutation overloads. Tested x86_64-linux. 2013-06-17 Jonathan Wakely Chris Jefferson * include/bits/stl_algobase.h (equal): Make C++14 overloads from N3671 dispatch to traditional std::equal for random-access iterators. (__equal2_aux, __equal2): Remove. (__equal::equal): Remove unused overloads. * include/bits/stl_algo.h (is_permutation): Fix typos. commit 0bf845495124778bad276447cd2ce12cb888f921 Author: Jonathan Wakely Date: Mon Jun 17 01:30:37 2013 +0100 2013-06-17 Jonathan Wakely Chris Jefferson * include/bits/stl_algobase.h (equal): Make C++14 overloads from N3671 dispatch to traditional std::equal for random-access iterators. (__equal2_aux, __equal2): Remove. (__equal::equal): Remove unused overloads. * include/bits/stl_algo.h (is_permutation): Fix typos. diff --git a/libstdc++-v3/include/bits/stl_algo.h b/libstdc++-v3/include/bits/stl_algo.h index e61f22b..9d6b466 100644 --- a/libstdc++-v3/include/bits/stl_algo.h +++ b/libstdc++-v3/include/bits/stl_algo.h @@ -4396,7 +4396,7 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION = typename iterator_traits<_ForwardIterator2>::iterator_category; using _It1_is_RA = is_same<_Cat1, random_access_iterator_tag>; using _It2_is_RA = is_same<_Cat2, random_access_iterator_tag>; - if (_It1_is_RA() && _It1_is_RA()) + if (_It1_is_RA() && _It2_is_RA()) { auto __d1 = std::distance(__first1, __last1); auto __d2 = std::distance(__first2, __last2); @@ -4456,7 +4456,7 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION = typename iterator_traits<_ForwardIterator2>::iterator_category; using _It1_is_RA = is_same<_Cat1, random_access_iterator_tag>; using _It2_is_RA = is_same<_Cat2, random_access_iterator_tag>; - constexpr bool __ra_iters = _It1_is_RA() && _It1_is_RA(); + constexpr bool __ra_iters = _It1_is_RA() && _It2_is_RA(); if (__ra_iters) { auto __d1 = std::distance(__first1, __last1); diff --git a/libstdc++-v3/include/bits/stl_algobase.h b/libstdc++-v3/include/bits/stl_algobase.h index 67f859b..e1daac2 100644 --- a/libstdc++-v3/include/bits/stl_algobase.h +++ b/libstdc++-v3/include/bits/stl_algobase.h @@ -798,19 +798,6 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION return false; return true; } - -#if __cplusplus > 201103L - template - static bool - equal(_II1 __first1, _II1 __last1, _II2 __first2, _II2 __last2) - { - for (; __first1 != __last1 && __first2 != __last2; - ++__first1, ++__first2) - if (!(*__first1 == *__first2)) - return false; - return true; - } -#endif }; template<> @@ -823,17 +810,6 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION return !__builtin_memcmp(__first1, __first2, sizeof(_Tp) * (__last1 - __first1)); } - -#if __cplusplus > 201103L - template - static bool - equal(const _Tp* __first1, const _Tp* __last1, const _Tp* __first2, - const _Tp* __last2) - { - return !__builtin_memcmp(__first1, __first2, sizeof(_Tp) - * (__last1 - __first1)); - } -#endif }; template @@ -851,66 +827,6 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION return std::__equal<__simple>::equal(__first1, __last1, __first2); } -#if __cplusplus > 201103L - template - struct __equal2 - { - template - using _IterCat = typename iterator_traits<_It>::iterator_category; - template - using _IsRA = is_same<_IterCat<_It>, random_access_iterator_tag>; - - template - static bool - equal(_II1 __first1, _II1 __last1, _II2 __first2, _II2 __last2) - { - constexpr bool __ra_iters = _IsRA<_II1>() && _IsRA<_II2>(); - if (__ra_iters) - { - auto __d1 = std::distance(__first1, __last1); - auto __d2 = std::distance(__first2, __last2); - if (__d1 != __d2) - return false; - } - for (; __first1 != __last1 && __first2 != __last2; - ++__first1, ++__first2) - if (!(*__first1 == *__first2)) - return false; - return __ra_iters || (__first1 == __last1 && __first2 == __last2); - } - }; - - template<> - struct __equal2 - { - template - static bool - equal(const _Tp* __first1, const _Tp* __last1, const _Tp* __first2, - const _Tp* __last2) - { - if ((__last1 - __first1) != (__last2 - __first2)) - return false; - return !__builtin_memcmp(__first1, __first2, sizeof(_Tp) - * (__last1 - __first1)); - } - }; - - template - inline bool - __equal2_aux(_II1 __first1, _II1 __last1, _II2 __first2, _II2 __last2) - { - typedef typename iterator_traits<_II1>::value_type _ValueType1; - typedef typename iterator_traits<_II2>::value_type _ValueType2; - const bool __simple = ((__is_integer<_ValueType1>::__value - || __is_pointer<_ValueType1>::__value) - && __is_pointer<_II1>::__value - && __is_pointer<_II2>::__value - && __are_same<_ValueType1, _ValueType2>::__value); - - return __equal2<__simple>::equal(__first1, __last1, __first2, __last2); - } -#endif - template struct __lc_rai { @@ -1174,10 +1090,23 @@ _GLIBCXX_BEGIN_NAMESPACE_ALGO __glibcxx_requires_valid_range(__first1, __last1); __glibcxx_requires_valid_range(__first2, __last2); - return std::__equal2_aux(std::__niter_base(__first1), - std::__niter_base(__last1), - std::__niter_base(__first2), - std::__niter_base(__last2)); + using _RATag = random_access_iterator_tag; + using _Cat1 = typename iterator_traits<_II1>::iterator_category; + using _Cat2 = typename iterator_traits<_II2>::iterator_category; + using _RAIters = __and_, is_same<_Cat2, _RATag>>; + if (_RAIters()) + { + auto __d1 = std::distance(__first1, __last1); + auto __d2 = std::distance(__first2, __last2); + if (__d1 != __d2) + return false; + return std::equal(__first1, __last1, __first2); + } + + for (; __first1 != __last1 && __first2 != __last2; ++__first1, ++__first2) + if (!(*__first1 == *__first2)) + return false; + return __first1 == __last1 && __first2 == __last2; } /** @@ -1207,23 +1136,23 @@ _GLIBCXX_BEGIN_NAMESPACE_ALGO __glibcxx_requires_valid_range(__first1, __last1); __glibcxx_requires_valid_range(__first2, __last2); + using _RATag = random_access_iterator_tag; using _Cat1 = typename iterator_traits<_IIter1>::iterator_category; using _Cat2 = typename iterator_traits<_IIter2>::iterator_category; - using _IIter1_is_RA = is_same<_Cat1, random_access_iterator_tag>; - using _IIter2_is_RA = is_same<_Cat2, random_access_iterator_tag>; - constexpr bool __ra_iters = _IIter1_is_RA() && _IIter1_is_RA(); - if (__ra_iters) + using _RAIters = __and_, is_same<_Cat2, _RATag>>; + if (_RAIters()) { auto __d1 = std::distance(__first1, __last1); auto __d2 = std::distance(__first2, __last2); if (__d1 != __d2) return false; + return std::equal(__first1, __last1, __first2, __binary_pred); } for (; __first1 != __last1 && __first2 != __last2; ++__first1, ++__first2) if (!bool(__binary_pred(*__first1, *__first2))) return false; - return __ra_iters || (__first1 == __last1 && __first2 == __last2); + return __first1 == __last1 && __first2 == __last2; } #endif