From patchwork Wed May 31 17:39:28 2023 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 8bit X-Patchwork-Submitter: =?utf-8?q?Fran=C3=A7ois_Dumont?= X-Patchwork-Id: 1788469 Return-Path: X-Original-To: incoming@patchwork.ozlabs.org Delivered-To: patchwork-incoming@legolas.ozlabs.org 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=sourceware.org; envelope-from=gcc-patches-bounces+incoming=patchwork.ozlabs.org@gcc.gnu.org; receiver=) Authentication-Results: legolas.ozlabs.org; dkim=pass (1024-bit key; unprotected) header.d=gcc.gnu.org header.i=@gcc.gnu.org header.a=rsa-sha256 header.s=default header.b=wIuSi5DC; dkim-atps=neutral Received: from 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 (P-384) server-digest SHA384) (No client certificate requested) by legolas.ozlabs.org (Postfix) with ESMTPS id 4QWc3V0NVwz20Py for ; Thu, 1 Jun 2023 03:40:05 +1000 (AEST) Received: from server2.sourceware.org (localhost [IPv6:::1]) by sourceware.org (Postfix) with ESMTP id 1A25E3858C30 for ; Wed, 31 May 2023 17:40:03 +0000 (GMT) DKIM-Filter: OpenDKIM Filter v2.11.0 sourceware.org 1A25E3858C30 DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gcc.gnu.org; s=default; t=1685554803; bh=aboXIouKF8HexavfApNxanwNKi15eeADXOlcTVfP7O8=; h=Date:To:Cc:Subject:List-Id:List-Unsubscribe:List-Archive: List-Post:List-Help:List-Subscribe:From:Reply-To:From; b=wIuSi5DC4dLbyHU48L+QSYdtZsbfPzGPHjRzTHxjczj/ico8eoyBCpphZn7ZA87/O vF9pQv1HfdDzhFLo1vkOfSF4Dqnm1/PCFzZM+CxJ3f023zD6N9pkNcL/3X30m4nGKD kaldUUBO1aaUUocDTWeybduzArCIacLMRBkksnu0= X-Original-To: gcc-patches@gcc.gnu.org Delivered-To: gcc-patches@gcc.gnu.org Received: from mail-wr1-x42a.google.com (mail-wr1-x42a.google.com [IPv6:2a00:1450:4864:20::42a]) by sourceware.org (Postfix) with ESMTPS id 19A5A3858D20; Wed, 31 May 2023 17:39:38 +0000 (GMT) DMARC-Filter: OpenDMARC Filter v1.4.2 sourceware.org 19A5A3858D20 Received: by mail-wr1-x42a.google.com with SMTP id ffacd0b85a97d-30af86a96b4so1776811f8f.3; Wed, 31 May 2023 10:39:38 -0700 (PDT) X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20221208; t=1685554776; x=1688146776; h=subject:from:cc:to:content-language:user-agent:mime-version:date :message-id:x-gm-message-state:from:to:cc:subject:date:message-id :reply-to; bh=aboXIouKF8HexavfApNxanwNKi15eeADXOlcTVfP7O8=; b=hhlB5yvn4ulcpwaX4jU+Yn033363LiAfcdagrbI5s9AoL9X22D88eWxS3Blx4FGvCC cFHyFMOUgoKzio3aG2ethpsidQlBgtDrlehJkRzdMehF7m8K6aNOefiiHTOjmhNUKEV6 bMquv2xfDN2rx8rENkyW41mXdOQcOg+Nlq7cJ5DCtzSRz+sUTlxt89tyQb9Z/JiKxE0D ZFPfdSQfjZ2hMtEDnh6Wve40YyB4fh2W+bbmIvj8xkuxR9z+voDWMOcm5745P9Hpm6MM PaN5tCNYf/h1KUbF69Wjr0+h6M4sy68lpeGYv1tyLcPsybg42xUXPyGobJXERhj2tAzs 3luQ== X-Gm-Message-State: AC+VfDw/G/kvSIDtR2O72DfQfBBWl1cIGOO7cOxvub0+5bX5KQUBijSh M853OQYSrSL/hm8Tqg0w62XblAmS8bU= X-Google-Smtp-Source: ACHHUZ5FUtX7vhUQcKq6dg5JCuiDUdxC8eoWkJJm61zQOJQp96bwn7DgBVT62fUQ1nXWUdtHYZV97g== X-Received: by 2002:adf:f547:0:b0:30a:ea8b:447d with SMTP id j7-20020adff547000000b0030aea8b447dmr4342178wrp.40.1685554776166; Wed, 31 May 2023 10:39:36 -0700 (PDT) Received: from [10.16.2.152] ([89.207.171.98]) by smtp.gmail.com with ESMTPSA id f15-20020adff58f000000b002fae7408544sm7381429wro.108.2023.05.31.10.39.31 (version=TLS1_3 cipher=TLS_AES_128_GCM_SHA256 bits=128/128); Wed, 31 May 2023 10:39:35 -0700 (PDT) Message-ID: <01f2b9e7-14e8-12a7-c275-7e48e3bd94df@gmail.com> Date: Wed, 31 May 2023 19:39:28 +0200 MIME-Version: 1.0 User-Agent: Mozilla/5.0 (X11; Linux x86_64; rv:102.0) Gecko/20100101 Thunderbird/102.11.0 Content-Language: en-US To: libstdc++ Cc: gcc-patches Subject: [PATCH] Move std::search into algobase.h X-Spam-Status: No, score=-9.5 required=5.0 tests=BAYES_00, BODY_8BITS, DKIM_SIGNED, DKIM_VALID, DKIM_VALID_AU, DKIM_VALID_EF, FREEMAIL_FROM, GIT_PATCH_0, RCVD_IN_DNSWL_NONE, SPF_HELO_NONE, SPF_PASS, TXREP, T_SCC_BODY_TEXT_LINE 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.29 Precedence: list List-Id: Gcc-patches mailing list List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , X-Patchwork-Original-From: =?utf-8?q?Fran=C3=A7ois_Dumont_via_Gcc-patches?= From: =?utf-8?q?Fran=C3=A7ois_Dumont?= Reply-To: =?utf-8?q?Fran=C3=A7ois_Dumont?= Errors-To: gcc-patches-bounces+incoming=patchwork.ozlabs.org@gcc.gnu.org Sender: "Gcc-patches" libstdc++: Reduce inclusion to Move the std::search definition from stl_algo.h to stl_algobase.h and use the later in . For consistency also move std::__parallel::search and associated helpers from to so that std::__parallel::search is accessible along with std::search. libstdc++-v3/ChangeLog:             * include/bits/stl_algo.h             (std::__search, std::search(_FwdIt1, _FwdIt1, _FwdIt2, _FwdIt2, _BinPred)): Move...             * include/bits/stl_algobase.h: ...here.             * include/std/functional: Replace include by .             * include/parallel/algo.h (std::__parallel::search<_FIt1, _FIt2, _BinaryPred>)             (std::__parallel::__search_switch<_FIt1, _FIt2, _BinaryPred, _ItTag1, _ItTag2>):             Move...             * include/parallel/algobase.h: ...here.             * include/std/functional: Remove and             includes. Include . Tested under Linux x86_64. Ok to commit ? François diff --git a/libstdc++-v3/include/bits/stl_algo.h b/libstdc++-v3/include/bits/stl_algo.h index 54695490166..2c52ed51402 100644 --- a/libstdc++-v3/include/bits/stl_algo.h +++ b/libstdc++-v3/include/bits/stl_algo.h @@ -140,54 +140,6 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION // count // count_if // search - - template - _GLIBCXX20_CONSTEXPR - _ForwardIterator1 - __search(_ForwardIterator1 __first1, _ForwardIterator1 __last1, - _ForwardIterator2 __first2, _ForwardIterator2 __last2, - _BinaryPredicate __predicate) - { - // Test for empty ranges - if (__first1 == __last1 || __first2 == __last2) - return __first1; - - // Test for a pattern of length 1. - _ForwardIterator2 __p1(__first2); - if (++__p1 == __last2) - return std::__find_if(__first1, __last1, - __gnu_cxx::__ops::__iter_comp_iter(__predicate, __first2)); - - // General case. - _ForwardIterator1 __current = __first1; - - for (;;) - { - __first1 = - std::__find_if(__first1, __last1, - __gnu_cxx::__ops::__iter_comp_iter(__predicate, __first2)); - - if (__first1 == __last1) - return __last1; - - _ForwardIterator2 __p = __p1; - __current = __first1; - if (++__current == __last1) - return __last1; - - while (__predicate(__current, __p)) - { - if (++__p == __last2) - return __first1; - if (++__current == __last1) - return __last1; - } - ++__first1; - } - return __first1; - } - // search_n /** @@ -4147,48 +4099,6 @@ _GLIBCXX_BEGIN_NAMESPACE_ALGO __gnu_cxx::__ops::__iter_equal_to_iter()); } - /** - * @brief Search a sequence for a matching sub-sequence using a predicate. - * @ingroup non_mutating_algorithms - * @param __first1 A forward iterator. - * @param __last1 A forward iterator. - * @param __first2 A forward iterator. - * @param __last2 A forward iterator. - * @param __predicate A binary predicate. - * @return The first iterator @c i in the range - * @p [__first1,__last1-(__last2-__first2)) such that - * @p __predicate(*(i+N),*(__first2+N)) is true for each @c N in the range - * @p [0,__last2-__first2), or @p __last1 if no such iterator exists. - * - * Searches the range @p [__first1,__last1) for a sub-sequence that - * compares equal value-by-value with the sequence given by @p - * [__first2,__last2), using @p __predicate to determine equality, - * and returns an iterator to the first element of the - * sub-sequence, or @p __last1 if no such iterator exists. - * - * @see search(_ForwardIter1, _ForwardIter1, _ForwardIter2, _ForwardIter2) - */ - template - _GLIBCXX20_CONSTEXPR - inline _ForwardIterator1 - search(_ForwardIterator1 __first1, _ForwardIterator1 __last1, - _ForwardIterator2 __first2, _ForwardIterator2 __last2, - _BinaryPredicate __predicate) - { - // concept requirements - __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator1>) - __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator2>) - __glibcxx_function_requires(_BinaryPredicateConcept<_BinaryPredicate, - typename iterator_traits<_ForwardIterator1>::value_type, - typename iterator_traits<_ForwardIterator2>::value_type>) - __glibcxx_requires_valid_range(__first1, __last1); - __glibcxx_requires_valid_range(__first2, __last2); - - return std::__search(__first1, __last1, __first2, __last2, - __gnu_cxx::__ops::__iter_comp_iter(__predicate)); - } - /** * @brief Search a sequence for a number of consecutive values. * @ingroup non_mutating_algorithms diff --git a/libstdc++-v3/include/bits/stl_algobase.h b/libstdc++-v3/include/bits/stl_algobase.h index 4a6f8195d98..dd95e94f7e9 100644 --- a/libstdc++-v3/include/bits/stl_algobase.h +++ b/libstdc++-v3/include/bits/stl_algobase.h @@ -2150,6 +2150,53 @@ _GLIBCXX_END_NAMESPACE_ALGO return __result; } + template + _GLIBCXX20_CONSTEXPR + _ForwardIterator1 + __search(_ForwardIterator1 __first1, _ForwardIterator1 __last1, + _ForwardIterator2 __first2, _ForwardIterator2 __last2, + _BinaryPredicate __predicate) + { + // Test for empty ranges + if (__first1 == __last1 || __first2 == __last2) + return __first1; + + // Test for a pattern of length 1. + _ForwardIterator2 __p1(__first2); + if (++__p1 == __last2) + return std::__find_if(__first1, __last1, + __gnu_cxx::__ops::__iter_comp_iter(__predicate, __first2)); + + // General case. + _ForwardIterator1 __current = __first1; + + for (;;) + { + __first1 = + std::__find_if(__first1, __last1, + __gnu_cxx::__ops::__iter_comp_iter(__predicate, __first2)); + + if (__first1 == __last1) + return __last1; + + _ForwardIterator2 __p = __p1; + __current = __first1; + if (++__current == __last1) + return __last1; + + while (__predicate(__current, __p)) + { + if (++__p == __last2) + return __first1; + if (++__current == __last1) + return __last1; + } + ++__first1; + } + return __first1; + } + #if __cplusplus >= 201103L template @@ -2220,6 +2267,51 @@ _GLIBCXX_END_NAMESPACE_ALGO } #endif // C++11 +_GLIBCXX_BEGIN_NAMESPACE_ALGO + + /** + * @brief Search a sequence for a matching sub-sequence using a predicate. + * @ingroup non_mutating_algorithms + * @param __first1 A forward iterator. + * @param __last1 A forward iterator. + * @param __first2 A forward iterator. + * @param __last2 A forward iterator. + * @param __predicate A binary predicate. + * @return The first iterator @c i in the range + * @p [__first1,__last1-(__last2-__first2)) such that + * @p __predicate(*(i+N),*(__first2+N)) is true for each @c N in the range + * @p [0,__last2-__first2), or @p __last1 if no such iterator exists. + * + * Searches the range @p [__first1,__last1) for a sub-sequence that + * compares equal value-by-value with the sequence given by @p + * [__first2,__last2), using @p __predicate to determine equality, + * and returns an iterator to the first element of the + * sub-sequence, or @p __last1 if no such iterator exists. + * + * @see search(_ForwardIter1, _ForwardIter1, _ForwardIter2, _ForwardIter2) + */ + template + _GLIBCXX20_CONSTEXPR + inline _ForwardIterator1 + search(_ForwardIterator1 __first1, _ForwardIterator1 __last1, + _ForwardIterator2 __first2, _ForwardIterator2 __last2, + _BinaryPredicate __predicate) + { + // concept requirements + __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator1>) + __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator2>) + __glibcxx_function_requires(_BinaryPredicateConcept<_BinaryPredicate, + typename iterator_traits<_ForwardIterator1>::value_type, + typename iterator_traits<_ForwardIterator2>::value_type>) + __glibcxx_requires_valid_range(__first1, __last1); + __glibcxx_requires_valid_range(__first2, __last2); + + return std::__search(__first1, __last1, __first2, __last2, + __gnu_cxx::__ops::__iter_comp_iter(__predicate)); + } + +_GLIBCXX_END_NAMESPACE_ALGO _GLIBCXX_END_NAMESPACE_VERSION } // namespace std diff --git a/libstdc++-v3/include/experimental/functional b/libstdc++-v3/include/experimental/functional index ce9d4e0fece..26b8dd51aec 100644 --- a/libstdc++-v3/include/experimental/functional +++ b/libstdc++-v3/include/experimental/functional @@ -42,10 +42,7 @@ #include #include #include -#include -#ifdef _GLIBCXX_PARALLEL -# include // For std::__parallel::search -#endif +#include // std::max, std::search #include namespace std _GLIBCXX_VISIBILITY(default) diff --git a/libstdc++-v3/include/parallel/algo.h b/libstdc++-v3/include/parallel/algo.h index 43ed6c558ee..13ae7622aa6 100644 --- a/libstdc++-v3/include/parallel/algo.h +++ b/libstdc++-v3/include/parallel/algo.h @@ -996,59 +996,6 @@ namespace __parallel std::__iterator_category(__begin2)); } - // Public interface. - template - inline _FIterator1 - search(_FIterator1 __begin1, _FIterator1 __end1, - _FIterator2 __begin2, _FIterator2 __end2, - _BinaryPredicate __pred, __gnu_parallel::sequential_tag) - { return _GLIBCXX_STD_A::search( - __begin1, __end1, __begin2, __end2, __pred); } - - // Parallel algorithm for random access iterator. - template - _RAIter1 - __search_switch(_RAIter1 __begin1, _RAIter1 __end1, - _RAIter2 __begin2, _RAIter2 __end2, - _BinaryPredicate __pred, - random_access_iterator_tag, random_access_iterator_tag) - { - if (_GLIBCXX_PARALLEL_CONDITION( - static_cast<__gnu_parallel::_SequenceIndex>(__end1 - __begin1) - >= __gnu_parallel::_Settings::get().search_minimal_n)) - return __gnu_parallel::__search_template(__begin1, __end1, - __begin2, __end2, __pred); - else - return search(__begin1, __end1, __begin2, __end2, __pred, - __gnu_parallel::sequential_tag()); - } - - // Sequential fallback for input iterator case - template - inline _FIterator1 - __search_switch(_FIterator1 __begin1, _FIterator1 __end1, - _FIterator2 __begin2, _FIterator2 __end2, - _BinaryPredicate __pred, _IteratorTag1, _IteratorTag2) - { return search(__begin1, __end1, __begin2, __end2, __pred, - __gnu_parallel::sequential_tag()); } - - // Public interface - template - inline _FIterator1 - search(_FIterator1 __begin1, _FIterator1 __end1, - _FIterator2 __begin2, _FIterator2 __end2, - _BinaryPredicate __pred) - { - return __search_switch(__begin1, __end1, __begin2, __end2, __pred, - std::__iterator_category(__begin1), - std::__iterator_category(__begin2)); - } - #if __cplusplus >= 201703L /** @brief Search a sequence using a Searcher object. * diff --git a/libstdc++-v3/include/parallel/algobase.h b/libstdc++-v3/include/parallel/algobase.h index 0bc25a69f8a..4e4cc0fa0f2 100644 --- a/libstdc++-v3/include/parallel/algobase.h +++ b/libstdc++-v3/include/parallel/algobase.h @@ -470,7 +470,60 @@ namespace __parallel #if __cpp_lib_three_way_comparison using _GLIBCXX_STD_A::lexicographical_compare_three_way; #endif -} // end namespace -} // end namespace + + // Public interface. + template + inline _FIterator1 + search(_FIterator1 __begin1, _FIterator1 __end1, + _FIterator2 __begin2, _FIterator2 __end2, + _BinaryPredicate __pred, __gnu_parallel::sequential_tag) + { return _GLIBCXX_STD_A::search( + __begin1, __end1, __begin2, __end2, __pred); } + + // Parallel algorithm for random access iterator. + template + _RAIter1 + __search_switch(_RAIter1 __begin1, _RAIter1 __end1, + _RAIter2 __begin2, _RAIter2 __end2, + _BinaryPredicate __pred, + random_access_iterator_tag, random_access_iterator_tag) + { + if (_GLIBCXX_PARALLEL_CONDITION( + static_cast<__gnu_parallel::_SequenceIndex>(__end1 - __begin1) + >= __gnu_parallel::_Settings::get().search_minimal_n)) + return __gnu_parallel::__search_template(__begin1, __end1, + __begin2, __end2, __pred); + else + return search(__begin1, __end1, __begin2, __end2, __pred, + __gnu_parallel::sequential_tag()); + } + + // Sequential fallback for input iterator case + template + inline _FIterator1 + __search_switch(_FIterator1 __begin1, _FIterator1 __end1, + _FIterator2 __begin2, _FIterator2 __end2, + _BinaryPredicate __pred, _IteratorTag1, _IteratorTag2) + { return search(__begin1, __end1, __begin2, __end2, __pred, + __gnu_parallel::sequential_tag()); } + + // Public interface + template + inline _FIterator1 + search(_FIterator1 __begin1, _FIterator1 __end1, + _FIterator2 __begin2, _FIterator2 __end2, + _BinaryPredicate __pred) + { + return __search_switch(__begin1, __end1, __begin2, __end2, __pred, + std::__iterator_category(__begin1), + std::__iterator_category(__begin2)); + } +} // end namespace __parallel +} // end namespace std #endif /* _GLIBCXX_PARALLEL_ALGOBASE_H */ diff --git a/libstdc++-v3/include/std/functional b/libstdc++-v3/include/std/functional index c7c6a5a7924..4a4b8b2b2e6 100644 --- a/libstdc++-v3/include/std/functional +++ b/libstdc++-v3/include/std/functional @@ -64,7 +64,7 @@ # include # include # endif -# include // std::search +# include // std::search #endif #if __cplusplus >= 202002L # include // std::identity, ranges::equal_to etc.