From: "François Dumont" <frs.dumont@gmail.com>
To: libstdc++ <libstdc++@gcc.gnu.org>
Cc: gcc-patches <gcc-patches@gcc.gnu.org>
Subject: [PATCH] Move std::search into algobase.h
Date: Wed, 31 May 2023 19:39:28 +0200 [thread overview]
Message-ID: <01f2b9e7-14e8-12a7-c275-7e48e3bd94df@gmail.com> (raw)
[-- Attachment #1: Type: text/plain, Size: 1243 bytes --]
libstdc++: Reduce <functional> inclusion to <stl_algobase.h>
Move the std::search definition from stl_algo.h to stl_algobase.h and use
the later in <functional>.
For consistency also move std::__parallel::search and associated helpers
from
<parallel/stl_algo.h> to <parallel/stl_algobase.h> 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 <stl_algo.h> include by
<stl_algobase.h>.
* 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 <bits/stl_algo.h> and
<parallel/algorithm>
includes. Include <bits/stl_algobase.h>.
Tested under Linux x86_64.
Ok to commit ?
François
[-- Attachment #2: search_algo.patch --]
[-- Type: text/x-patch, Size: 13921 bytes --]
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.
next reply other threads:[~2023-05-31 17:39 UTC|newest]
Thread overview: 12+ messages / expand[flat|nested] mbox.gz Atom feed top
2023-05-31 17:39 François Dumont [this message]
2023-05-31 17:55 ` Jonathan Wakely
2023-06-01 11:52 ` Rainer Orth
2023-06-01 12:05 ` Jonathan Wakely
2023-06-01 13:50 ` François Dumont
2023-06-01 20:36 ` François Dumont
2023-06-01 21:57 ` Jonathan Wakely
2023-06-02 7:33 ` François Dumont
2023-06-02 7:43 ` Jonathan Wakely
2023-06-02 9:47 ` François Dumont
2023-06-02 11:30 ` Jonathan Wakely
2023-06-02 12:34 ` Jonathan Wakely
Reply instructions:
You may reply publicly to this message via plain-text email
using any one of the following methods:
* Save the following mbox file, import it into your mail client,
and reply-to-all from there: mbox
Avoid top-posting and favor interleaved quoting:
https://en.wikipedia.org/wiki/Posting_style#Interleaved_style
* Reply using the --to, --cc, and --in-reply-to
switches of git-send-email(1):
git send-email \
--in-reply-to=01f2b9e7-14e8-12a7-c275-7e48e3bd94df@gmail.com \
--to=frs.dumont@gmail.com \
--cc=gcc-patches@gcc.gnu.org \
--cc=libstdc++@gcc.gnu.org \
/path/to/YOUR_REPLY
https://kernel.org/pub/software/scm/git/docs/git-send-email.html
* If your mail client supports setting the In-Reply-To header
via mailto: links, try the mailto: link
Be sure your reply has a Subject: header at the top and a blank line
before the message body.
This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox;
as well as URLs for read-only IMAP folder(s) and NNTP newsgroup(s).