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
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.
