Move std::search into algobase.h

Message ID	01f2b9e7-14e8-12a7-c275-7e48e3bd94df@gmail.com
State	New
Headers	show Return-Path: <gcc-patches-bounces+incoming=patchwork.ozlabs.org@gcc.gnu.org> DMARC-Filter: OpenDMARC Filter v1.4.2 sourceware.org 19A5A3858D20 Content-Type: multipart/mixed; boundary="------------Vo0ctiSIoYLtsNE0SKuxRmiu" 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++ <libstdc++@gcc.gnu.org> Cc: gcc-patches <gcc-patches@gcc.gnu.org> Subject: [PATCH] Move std::search into algobase.h Precedence: list From: =?utf-8?q?Fran=C3=A7ois_Dumont_via_Gcc-patches?= <gcc-patches@gcc.gnu.org> Reply-To: =?utf-8?q?Fran=C3=A7ois_Dumont?= <frs.dumont@gmail.com> Errors-To: gcc-patches-bounces+incoming=patchwork.ozlabs.org@gcc.gnu.org Sender: "Gcc-patches" <gcc-patches-bounces+incoming=patchwork.ozlabs.org@gcc.gnu.org>
Series	Move std::search into algobase.h \| expand Move std::search into algobase.h

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<typename _ForwardIterator1, typename _ForwardIterator2, - typename _BinaryPredicate> - _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<typename _ForwardIterator1, typename _ForwardIterator2, - typename _BinaryPredicate> - _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<typename _ForwardIterator1, typename _ForwardIterator2, + typename _BinaryPredicate> + _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<typename _ForwardIterator1, typename _ForwardIterator2, typename _BinaryPredicate> @@ -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<typename _ForwardIterator1, typename _ForwardIterator2, + typename _BinaryPredicate> + _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 <unordered_map> #include <vector> #include <array> -#include <bits/stl_algo.h> -#ifdef _GLIBCXX_PARALLEL -# include <parallel/algorithm> // For std::__parallel::search -#endif +#include <bits/stl_algobase.h> // std::max, std::search #include <experimental/bits/lfts_config.h> 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<typename _FIterator1, typename _FIterator2, - typename _BinaryPredicate> - 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<typename _RAIter1, typename _RAIter2, - typename _BinaryPredicate> - _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<typename _FIterator1, typename _FIterator2, - typename _BinaryPredicate, typename _IteratorTag1, - typename _IteratorTag2> - 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<typename _FIterator1, typename _FIterator2, - typename _BinaryPredicate> - 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<typename _FIterator1, typename _FIterator2, + typename _BinaryPredicate> + 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<typename _RAIter1, typename _RAIter2, + typename _BinaryPredicate> + _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<typename _FIterator1, typename _FIterator2, + typename _BinaryPredicate, typename _IteratorTag1, + typename _IteratorTag2> + 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<typename _FIterator1, typename _FIterator2, + typename _BinaryPredicate> + 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 <vector> # include <array> # endif -# include <bits/stl_algo.h> // std::search +# include <bits/stl_algobase.h> // std::search #endif #if __cplusplus >= 202002L # include <bits/ranges_cmp.h> // std::identity, ranges::equal_to etc.

Move std::search into algobase.h

Commit Message

Comments

Patch