From patchwork Sun Jul 7 11:29:58 2024 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Jonathan Wakely X-Patchwork-Id: 1957682 Return-Path: X-Original-To: incoming@patchwork.ozlabs.org Delivered-To: patchwork-incoming@legolas.ozlabs.org Authentication-Results: legolas.ozlabs.org; dkim=pass (1024-bit key; unprotected) header.d=redhat.com header.i=@redhat.com header.a=rsa-sha256 header.s=mimecast20190719 header.b=GRM1YytO; dkim-atps=neutral Authentication-Results: legolas.ozlabs.org; spf=pass (sender SPF authorized) smtp.mailfrom=gcc.gnu.org (client-ip=2620:52:3:1:0:246e:9693:128c; helo=server2.sourceware.org; envelope-from=gcc-patches-bounces~incoming=patchwork.ozlabs.org@gcc.gnu.org; receiver=patchwork.ozlabs.org) Received: from server2.sourceware.org (server2.sourceware.org [IPv6:2620:52:3:1:0:246e:9693:128c]) (using TLSv1.3 with cipher TLS_AES_256_GCM_SHA384 (256/256 bits) key-exchange X25519 server-signature ECDSA (secp384r1) server-digest SHA384) (No client certificate requested) by legolas.ozlabs.org (Postfix) with ESMTPS id 4WH4nJ4G9Zz1xr7 for ; Sun, 7 Jul 2024 21:30:44 +1000 (AEST) Received: from server2.sourceware.org (localhost [IPv6:::1]) by sourceware.org (Postfix) with ESMTP id D2D103882100 for ; Sun, 7 Jul 2024 11:30:41 +0000 (GMT) X-Original-To: gcc-patches@gcc.gnu.org Delivered-To: gcc-patches@gcc.gnu.org Received: from us-smtp-delivery-124.mimecast.com (us-smtp-delivery-124.mimecast.com [170.10.133.124]) by sourceware.org (Postfix) with ESMTPS id 08DC1384A423 for ; Sun, 7 Jul 2024 11:30:16 +0000 (GMT) DMARC-Filter: OpenDMARC Filter v1.4.2 sourceware.org 08DC1384A423 Authentication-Results: sourceware.org; dmarc=pass (p=none dis=none) header.from=redhat.com Authentication-Results: sourceware.org; spf=pass smtp.mailfrom=redhat.com ARC-Filter: OpenARC Filter v1.0.0 sourceware.org 08DC1384A423 Authentication-Results: server2.sourceware.org; arc=none smtp.remote-ip=170.10.133.124 ARC-Seal: i=1; a=rsa-sha256; d=sourceware.org; s=key; t=1720351817; cv=none; b=RIdD2uTcvWQp6HqZF+awDPsy19/H5l6MSl+AXSyXKx5c3o3vJzPqW+UDun51rU4LL8CnPOSa6GO/2goQAttUPV9np27Pg4jWET8Fgc0d/2dGZra/akzCKTjR2JGCK82amJbuF2ZZOK0k3BGsn8nbD2DkEEAPMszft+IeknMI/mU= ARC-Message-Signature: i=1; a=rsa-sha256; d=sourceware.org; s=key; t=1720351817; c=relaxed/simple; bh=PKkpbJYH8o+pcUv2h4jKRgaDqVkXRW/ziF4qbQxHroQ=; h=DKIM-Signature:From:To:Subject:Date:Message-ID:MIME-Version; b=BqapM4+jqcghpYRelJBostOCfSKqEJqf7ggodl/ChMe05GKOwsPACeBYLzrd8Q0SPS9cspPVnp8auz73K3okTEFqXWn95VDNePg0OUItrACtVs5roOWh5gDkmyV/oUPrPO60NQXE33sid4Wpk0VA46OKeaSzgFbWWIG21RD/C0U= ARC-Authentication-Results: i=1; server2.sourceware.org DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=redhat.com; s=mimecast20190719; t=1720351815; h=from:from:reply-to:subject:subject:date:date:message-id:message-id: to:to:cc:mime-version:mime-version:content-type:content-type: content-transfer-encoding:content-transfer-encoding; bh=naRKytXdN2iFcV3dk3FpMVG7lWcaoMBpV6Qp/OvPGvc=; b=GRM1YytOAoSU8KuiXvx4l14/M0r7GRkvoWX0M2HFkxE229xj3qSQzfZ9JXcdGWlbf3206Z KLGontKaT20LNkefqu8jZFX/t9M/wud0qnJKJMf1+aReRogqu2WAVF0hod8/KbWUFuvUBz rtypmCmKj88+E1BBZoj5uvKzLXMZ/Sg= Received: from mx-prod-mc-02.mail-002.prod.us-west-2.aws.redhat.com (ec2-54-186-198-63.us-west-2.compute.amazonaws.com [54.186.198.63]) by relay.mimecast.com with ESMTP with STARTTLS (version=TLSv1.3, cipher=TLS_AES_256_GCM_SHA384) id us-mta-474-M0nizb6MONG7Bi2Cjn1m1w-1; Sun, 07 Jul 2024 07:30:13 -0400 X-MC-Unique: M0nizb6MONG7Bi2Cjn1m1w-1 Received: from mx-prod-int-01.mail-002.prod.us-west-2.aws.redhat.com (mx-prod-int-01.mail-002.prod.us-west-2.aws.redhat.com [10.30.177.4]) (using TLSv1.3 with cipher TLS_AES_256_GCM_SHA384 (256/256 bits) key-exchange X25519 server-signature RSA-PSS (2048 bits) server-digest SHA256) (No client certificate requested) by mx-prod-mc-02.mail-002.prod.us-west-2.aws.redhat.com (Postfix) with ESMTPS id 9A1F9195609D; Sun, 7 Jul 2024 11:30:11 +0000 (UTC) Received: from localhost (unknown [10.42.28.19]) by mx-prod-int-01.mail-002.prod.us-west-2.aws.redhat.com (Postfix) with ESMTP id AC09B3000181; Sun, 7 Jul 2024 11:30:10 +0000 (UTC) From: Jonathan Wakely To: libstdc++@gcc.gnu.org, gcc-patches@gcc.gnu.org Subject: [committed] libstdc++: Fix std::find for non-contiguous iterators [PR115799] Date: Sun, 7 Jul 2024 12:29:58 +0100 Message-ID: <20240707113009.288827-1-jwakely@redhat.com> MIME-Version: 1.0 X-Scanned-By: MIMEDefang 3.4.1 on 10.30.177.4 X-Mimecast-Spam-Score: 0 X-Mimecast-Originator: redhat.com X-Spam-Status: No, score=-12.1 required=5.0 tests=BAYES_00, DKIMWL_WL_HIGH, DKIM_SIGNED, DKIM_VALID, DKIM_VALID_AU, DKIM_VALID_EF, GIT_PATCH_0, RCVD_IN_DNSWL_NONE, RCVD_IN_MSPIKE_H4, RCVD_IN_MSPIKE_WL, SPF_HELO_NONE, SPF_NONE, TXREP autolearn=ham autolearn_force=no version=3.4.6 X-Spam-Checker-Version: SpamAssassin 3.4.6 (2021-04-09) on server2.sourceware.org X-BeenThere: gcc-patches@gcc.gnu.org X-Mailman-Version: 2.1.30 Precedence: list List-Id: Gcc-patches mailing list List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , Errors-To: gcc-patches-bounces~incoming=patchwork.ozlabs.org@gcc.gnu.org Tested x86_64-linux. Pushed to trunk. -- >8 -- The r15-1857 change didn't correctly restrict the new optimization to contiguous iterators. libstdc++-v3/ChangeLog: PR libstdc++/115799 * include/bits/stl_algo.h (find): Use 'if constexpr' so that memchr optimization is a discarded statement for non-contiguous iterators. * testsuite/25_algorithms/find/bytes.cc: Check with input iterators. --- libstdc++-v3/include/bits/stl_algo.h | 44 +++++++++---------- .../testsuite/25_algorithms/find/bytes.cc | 7 +++ 2 files changed, 27 insertions(+), 24 deletions(-) diff --git a/libstdc++-v3/include/bits/stl_algo.h b/libstdc++-v3/include/bits/stl_algo.h index 45c3b591326..d250b2e04d4 100644 --- a/libstdc++-v3/include/bits/stl_algo.h +++ b/libstdc++-v3/include/bits/stl_algo.h @@ -3849,32 +3849,28 @@ _GLIBCXX_BEGIN_NAMESPACE_ALGO #if __cpp_if_constexpr && __glibcxx_type_trait_variable_templates using _ValT = typename iterator_traits<_InputIterator>::value_type; if constexpr (__can_use_memchr_for_find<_ValT, _Tp>) - { - // If converting the value to the 1-byte value_type alters its value, - // then it would not be found by std::find using equality comparison. - // We need to check this here, because otherwise something like - // memchr("a", 'a'+256, 1) would give a false positive match. - if (!(static_cast<_ValT>(__val) == __val)) - return __last; - else if (!__is_constant_evaluated()) - { - const void* __p0 = nullptr; - if constexpr (is_pointer_v) - __p0 = std::__niter_base(__first); + if constexpr (is_pointer_v #if __cpp_lib_concepts - else if constexpr (contiguous_iterator<_InputIterator>) - __p0 = std::to_address(__first); + || contiguous_iterator<_InputIterator> #endif - if (__p0) - { - const int __ival = static_cast(__val); - if (auto __n = std::distance(__first, __last); __n > 0) - if (auto __p1 = __builtin_memchr(__p0, __ival, __n)) - return __first + ((const char*)__p1 - (const char*)__p0); - return __last; - } - } - } + ) + { + // If conversion to the 1-byte value_type alters the value, + // it would not be found by std::find using equality comparison. + // We need to check this here, because otherwise something like + // memchr("a", 'a'+256, 1) would give a false positive match. + if (!(static_cast<_ValT>(__val) == __val)) + return __last; + else if (!__is_constant_evaluated()) + { + const void* __p0 = std::__to_address(__first); + const int __ival = static_cast(__val); + if (auto __n = std::distance(__first, __last); __n > 0) + if (auto __p1 = __builtin_memchr(__p0, __ival, __n)) + return __first + ((const char*)__p1 - (const char*)__p0); + return __last; + } + } #endif return std::__find_if(__first, __last, diff --git a/libstdc++-v3/testsuite/25_algorithms/find/bytes.cc b/libstdc++-v3/testsuite/25_algorithms/find/bytes.cc index f4ac5d4018d..e1d6c01ab21 100644 --- a/libstdc++-v3/testsuite/25_algorithms/find/bytes.cc +++ b/libstdc++-v3/testsuite/25_algorithms/find/bytes.cc @@ -3,6 +3,7 @@ #include #include // std::byte #include +#include // PR libstdc++/88545 made std::find use memchr as an optimization. // This test verifies that it didn't change any semantics. @@ -113,6 +114,12 @@ test_non_characters() #endif } +void +test_pr115799c2(__gnu_test::input_iterator_wrapper i) +{ + (void) std::find(i, i, 'a'); +} + int main() { test_char();