From patchwork Fri Feb 14 15:35:45 2020 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Patrick Palka X-Patchwork-Id: 1238123 Return-Path: X-Original-To: incoming@patchwork.ozlabs.org Delivered-To: patchwork-incoming@bilbo.ozlabs.org Authentication-Results: ozlabs.org; spf=pass (sender SPF authorized) smtp.mailfrom=gcc.gnu.org (client-ip=209.132.180.131; helo=sourceware.org; envelope-from=gcc-patches-return-519546-incoming=patchwork.ozlabs.org@gcc.gnu.org; receiver=) Authentication-Results: ozlabs.org; dmarc=fail (p=none dis=none) header.from=redhat.com Authentication-Results: ozlabs.org; dkim=pass (1024-bit key; unprotected) header.d=gcc.gnu.org header.i=@gcc.gnu.org header.a=rsa-sha1 header.s=default header.b=xeCSsoMh; dkim=fail reason="signature verification failed" (1024-bit key; unprotected) header.d=redhat.com header.i=@redhat.com header.a=rsa-sha256 header.s=mimecast20190719 header.b=W95a/1YZ; dkim-atps=neutral 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 48JyCQ309Mz9sNg for ; Sat, 15 Feb 2020 02:36:16 +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:from :to:cc:subject:date:message-id:mime-version:content-type :content-transfer-encoding; q=dns; s=default; b=TY2xEiqwV/yipDCS /8lOexfL9vnlolBA7mhbYrwXyVAc5P38TQjjCxpjlNec05EcNksGwfveDTVnnVRR NGSIrn0tAuag46IKynjV2i6muwLtFYmIFYAvtF1bKMeZm37g83lAEgVyTWPYTIHo c4lutyHL+U6XHDY7uFkgcsyhSRc= 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:from :to:cc:subject:date:message-id:mime-version:content-type :content-transfer-encoding; s=default; bh=Xa8s41JKRE3ZkU7iwl5j4e 6fxZQ=; b=xeCSsoMhZQB3BMdbLnbkaXlpRxPFIR2ZqhySPCuBlA7ZiELzCmyV9q XcOBGg+R/Gu0t0AgNd1awMGyaxgK2D3AqnILLr97l1rSCskcTT5hhO3n82mU5UKh MaCedRdN0fB9RFpOAkIIFIvAD8Njg+8Wv+Gh+SrXaHK1akagyhVBU= Received: (qmail 106406 invoked by alias); 14 Feb 2020 15:35:59 -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 106392 invoked by uid 89); 14 Feb 2020 15:35:58 -0000 Authentication-Results: sourceware.org; auth=none X-Spam-SWARE-Status: No, score=-23.9 required=5.0 tests=AWL, BAYES_00, GIT_PATCH_0, GIT_PATCH_1, GIT_PATCH_2, GIT_PATCH_3, RCVD_IN_DNSWL_NONE autolearn=unavailable version=3.3.1 spammy=simplest, sk:__is_no, site X-HELO: us-smtp-delivery-1.mimecast.com Received: from us-smtp-2.mimecast.com (HELO us-smtp-delivery-1.mimecast.com) (205.139.110.61) by sourceware.org (qpsmtpd/0.93/v0.84-503-g423c35a) with ESMTP; Fri, 14 Feb 2020 15:35:57 +0000 DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=redhat.com; s=mimecast20190719; t=1581694555; h=from:from:reply-to:subject:subject:date:date:message-id:message-id: to:to:cc:cc:mime-version:mime-version:content-type:content-type: content-transfer-encoding:content-transfer-encoding; bh=tqjWvv2nydV0u5KMU5Mk15qTxDm/2GYC2jguyjmrwJc=; b=W95a/1YZJBpt4taTpLjwbVs/eTqs/Qcc5rzgAyHqKfJppF235bMWddJPpH/aFwKI6YmARM OesXFF0tKFK+61ZfIGHPrfaKu25fkPrF7YfeZp8qY5whFtigx/ImksoO43BvZZrTT/RnXV xnDIVfPxRpKQ231WV1AJ6cGqFfA79mc= Received: from mail-qk1-f198.google.com (mail-qk1-f198.google.com [209.85.222.198]) (Using TLS) by relay.mimecast.com with ESMTP id us-mta-388-XY1YwOy0P36jrSaCx8TOJA-1; Fri, 14 Feb 2020 10:35:53 -0500 Received: by mail-qk1-f198.google.com with SMTP id r142so6419443qke.3 for ; Fri, 14 Feb 2020 07:35:53 -0800 (PST) Received: from localhost.localdomain (ool-457d493a.dyn.optonline.net. [69.125.73.58]) by smtp.gmail.com with ESMTPSA id n7sm3364919qkk.41.2020.02.14.07.35.51 (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Fri, 14 Feb 2020 07:35:51 -0800 (PST) From: Patrick Palka To: gcc-patches@gcc.gnu.org Cc: libstdc++@gcc.gnu.org, jwakely@redhat.com, Patrick Palka Subject: [PATCH 1/3] libstdc++: Fold some ranges algo subroutines into their only caller Date: Fri, 14 Feb 2020 10:35:45 -0500 Message-Id: <20200214153547.2390767-1-ppalka@redhat.com> MIME-Version: 1.0 X-Mimecast-Spam-Score: 0 X-Mimecast-Originator: redhat.com X-IsSubscribed: yes These subroutines have only a single call site, so it might be best and simplest to eliminate them before we convert the algos into function objects. libstdc++-v3/ChangeLog: * include/bits/ranges_algo.h (ranges::__find_end): Fold into ... (ranges::find_end): ... here. (ranges::__lexicographical_compare): Fold into ... (ranges::lexicographical_compare): ... here. * include/bits/ranges_algobase.h (ranges::__equal): Fold into ... (ranges::equal): ... here. --- libstdc++-v3/include/bits/ranges_algo.h | 104 ++++++++------------ libstdc++-v3/include/bits/ranges_algobase.h | 33 +++---- 2 files changed, 55 insertions(+), 82 deletions(-) diff --git a/libstdc++-v3/include/bits/ranges_algo.h b/libstdc++-v3/include/bits/ranges_algo.h index 84a02cabb80..6b6f4defdf5 100644 --- a/libstdc++-v3/include/bits/ranges_algo.h +++ b/libstdc++-v3/include/bits/ranges_algo.h @@ -513,40 +513,7 @@ namespace ranges std::move(__pred), std::move(__proj)); } - template _Sent1, - forward_iterator _Iter2, sentinel_for<_Iter2> _Sent2, - typename _Pred = ranges::equal_to, - typename _Proj1 = identity, typename _Proj2 = identity> - requires indirectly_comparable<_Iter1, _Iter2, _Pred, _Proj1, _Proj2> - constexpr subrange<_Iter1> - __find_end(_Iter1 __first1, _Sent1 __last1, - _Iter2 __first2, _Sent2 __last2, - _Pred __pred, _Proj1 __proj1, _Proj2 __proj2) - { - auto __i = ranges::next(__first1, __last1); - if (__first2 == __last2) - return {__i, __i}; - auto __result_begin = __i; - auto __result_end = __i; - for (;;) - { - auto __new_range = ranges::search(__first1, __last1, - __first2, __last2, - __pred, __proj1, __proj2); - auto __new_result_begin = ranges::begin(__new_range); - auto __new_result_end = ranges::end(__new_range); - if (__new_result_begin == __last1) - return {__result_begin, __result_end}; - else - { - __result_begin = __new_result_begin; - __result_end = __new_result_end; - __first1 = __result_begin; - ++__first1; - } - } - } template _Sent1, forward_iterator _Iter2, sentinel_for<_Iter2> _Sent2, @@ -578,9 +545,31 @@ namespace ranges return {__result_first, __result_last}; } else - return ranges::__find_end(__first1, __last1, __first2, __last2, - std::move(__pred), - std::move(__proj1), std::move(__proj2)); + { + auto __i = ranges::next(__first1, __last1); + if (__first2 == __last2) + return {__i, __i}; + + auto __result_begin = __i; + auto __result_end = __i; + for (;;) + { + auto __new_range = ranges::search(__first1, __last1, + __first2, __last2, + __pred, __proj1, __proj2); + auto __new_result_begin = ranges::begin(__new_range); + auto __new_result_end = ranges::end(__new_range); + if (__new_result_begin == __last1) + return {__result_begin, __result_end}; + else + { + __result_begin = __new_result_begin; + __result_end = __new_result_end; + __first1 = __result_begin; + ++__first1; + } + } + } } template _Sent1, input_iterator _Iter2, sentinel_for<_Iter2> _Sent2, - typename _Proj1, typename _Proj2, + typename _Proj1 = identity, typename _Proj2 = identity, indirect_strict_weak_order, - projected<_Iter2, _Proj2>> _Comp> + projected<_Iter2, _Proj2>> + _Comp = ranges::less> constexpr bool - __lexicographical_compare(_Iter1 __first1, _Sent1 __last1, - _Iter2 __first2, _Sent2 __last2, - _Comp __comp, _Proj1 __proj1, _Proj2 __proj2) + lexicographical_compare(_Iter1 __first1, _Sent1 __last1, + _Iter2 __first2, _Sent2 __last2, + _Comp __comp = {}, + _Proj1 __proj1 = {}, _Proj2 __proj2 = {}) { + if constexpr (__detail::__is_normal_iterator<_Iter1> + || __detail::__is_normal_iterator<_Iter2>) + return ranges::lexicographical_compare + (std::__niter_base(std::move(__first1)), + std::__niter_base(std::move(__last1)), + std::__niter_base(std::move(__first2)), + std::__niter_base(std::move(__last2)), + std::move(__comp), + std::move(__proj1), std::move(__proj2)); + constexpr bool __sized_iters = (sized_sentinel_for<_Sent1, _Iter1> && sized_sentinel_for<_Sent2, _Iter2>); @@ -2976,27 +2977,6 @@ namespace ranges return __first1 == __last1 && __first2 != __last2; } - template _Sent1, - input_iterator _Iter2, sentinel_for<_Iter2> _Sent2, - typename _Proj1 = identity, typename _Proj2 = identity, - indirect_strict_weak_order, - projected<_Iter2, _Proj2>> - _Comp = ranges::less> - constexpr bool - lexicographical_compare(_Iter1 __first1, _Sent1 __last1, - _Iter2 __first2, _Sent2 __last2, - _Comp __comp = {}, - _Proj1 __proj1 = {}, _Proj2 __proj2 = {}) - { - return (ranges::__lexicographical_compare - (std::__niter_base(std::move(__first1)), - std::__niter_base(std::move(__last1)), - std::__niter_base(std::move(__first2)), - std::__niter_base(std::move(__last2)), - std::move(__comp), - std::move(__proj1), std::move(__proj2))); - } - template, _Proj1>, diff --git a/libstdc++-v3/include/bits/ranges_algobase.h b/libstdc++-v3/include/bits/ranges_algobase.h index f63c032cf0b..813a5096ae0 100644 --- a/libstdc++-v3/include/bits/ranges_algobase.h +++ b/libstdc++-v3/include/bits/ranges_algobase.h @@ -73,14 +73,24 @@ namespace ranges template _Sent1, input_iterator _Iter2, sentinel_for<_Iter2> _Sent2, - typename _Pred, typename _Proj1, typename _Proj2> + typename _Pred = ranges::equal_to, + typename _Proj1 = identity, typename _Proj2 = identity> requires indirectly_comparable<_Iter1, _Iter2, _Pred, _Proj1, _Proj2> constexpr bool - __equal(_Iter1 __first1, _Sent1 __last1, _Iter2 __first2, _Sent2 __last2, - _Pred __pred, _Proj1 __proj1, _Proj2 __proj2) + equal(_Iter1 __first1, _Sent1 __last1, _Iter2 __first2, _Sent2 __last2, + _Pred __pred = {}, _Proj1 __proj1 = {}, _Proj2 __proj2 = {}) { // TODO: implement more specializations to at least have parity with // std::equal. + if constexpr (__detail::__is_normal_iterator<_Iter1> + || __detail::__is_normal_iterator<_Iter2>) + return ranges::equal(std::__niter_base(std::move(__first1)), + std::__niter_base(std::move(__last1)), + std::__niter_base(std::move(__first2)), + std::__niter_base(std::move(__last2)), + std::move(__pred), + std::move(__proj1), std::move(__proj2)); + constexpr bool __sized_iters = (sized_sentinel_for<_Sent1, _Iter1> && sized_sentinel_for<_Sent2, _Iter2>); @@ -129,23 +139,6 @@ namespace ranges } } - template _Sent1, - input_iterator _Iter2, sentinel_for<_Iter2> _Sent2, - typename _Pred = ranges::equal_to, - typename _Proj1 = identity, typename _Proj2 = identity> - requires indirectly_comparable<_Iter1, _Iter2, _Pred, _Proj1, _Proj2> - constexpr bool - equal(_Iter1 __first1, _Sent1 __last1, _Iter2 __first2, _Sent2 __last2, - _Pred __pred = {}, _Proj1 __proj1 = {}, _Proj2 __proj2 = {}) - { - return ranges::__equal(std::__niter_base(std::move(__first1)), - std::__niter_base(std::move(__last1)), - std::__niter_base(std::move(__first2)), - std::__niter_base(std::move(__last2)), - std::move(__pred), - std::move(__proj1), std::move(__proj2)); - } - template