From 44c85722dc6499c65264d1d45ffe01701053b067 Mon Sep 17 00:00:00 2001 From: =?utf8?q?Fran=C3=A7ois=20Dumont?= Date: Thu, 27 Feb 2020 19:08:40 +0100 Subject: [PATCH] libstdc++ Hastable: Move std::is_permutation to limit includes Move std::is_permutation algorithm with associated helpers to stl_algobase.h to remove stl_algo.h include from hashtable_policy.h and so reduce preprocess size of unordered_map and unordered_set headers. * include/bits/stl_algo.h (__find_if, __count_if, __is_permutation, std::is_permutation): Move... * include/bits/stl_algobase.h: ...here. * include/bits/hashtable_policy.h: Remove include. --- libstdc++-v3/ChangeLog | 7 + libstdc++-v3/include/bits/hashtable_policy.h | 3 +- libstdc++-v3/include/bits/stl_algo.h | 150 ------------------ libstdc++-v3/include/bits/stl_algobase.h | 153 +++++++++++++++++++ 4 files changed, 161 insertions(+), 152 deletions(-) diff --git a/libstdc++-v3/ChangeLog b/libstdc++-v3/ChangeLog index 85a0cf25c74..34615413280 100644 --- a/libstdc++-v3/ChangeLog +++ b/libstdc++-v3/ChangeLog @@ -1,3 +1,10 @@ +2020-02-29 François Dumont + + * include/bits/stl_algo.h + (__find_if, __count_if, __is_permutation, std::is_permutation): Move... + * include/bits/stl_algobase.h: ...here. + * include/bits/hashtable_policy.h: Remove include. + 2020-02-29 John David Anglin * testsuite/30_threads/stop_token/stop_callback.cc: Add libatomic diff --git a/libstdc++-v3/include/bits/hashtable_policy.h b/libstdc++-v3/include/bits/hashtable_policy.h index 22bc4472e32..ef120134914 100644 --- a/libstdc++-v3/include/bits/hashtable_policy.h +++ b/libstdc++-v3/include/bits/hashtable_policy.h @@ -33,8 +33,7 @@ #include // for std::tuple, std::forward_as_tuple #include // for std::numeric_limits -#include // for std::min. -#include // for std::is_permutation. +#include // for std::min, std::is_permutation. namespace std _GLIBCXX_VISIBILITY(default) { diff --git a/libstdc++-v3/include/bits/stl_algo.h b/libstdc++-v3/include/bits/stl_algo.h index 6503d1518d3..932ece55529 100644 --- a/libstdc++-v3/include/bits/stl_algo.h +++ b/libstdc++-v3/include/bits/stl_algo.h @@ -96,76 +96,6 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION std::iter_swap(__result, __b); } - /// This is an overload used by find algos for the Input Iterator case. - template - _GLIBCXX20_CONSTEXPR - inline _InputIterator - __find_if(_InputIterator __first, _InputIterator __last, - _Predicate __pred, input_iterator_tag) - { - while (__first != __last && !__pred(__first)) - ++__first; - return __first; - } - - /// This is an overload used by find algos for the RAI case. - template - _GLIBCXX20_CONSTEXPR - _RandomAccessIterator - __find_if(_RandomAccessIterator __first, _RandomAccessIterator __last, - _Predicate __pred, random_access_iterator_tag) - { - typename iterator_traits<_RandomAccessIterator>::difference_type - __trip_count = (__last - __first) >> 2; - - for (; __trip_count > 0; --__trip_count) - { - if (__pred(__first)) - return __first; - ++__first; - - if (__pred(__first)) - return __first; - ++__first; - - if (__pred(__first)) - return __first; - ++__first; - - if (__pred(__first)) - return __first; - ++__first; - } - - switch (__last - __first) - { - case 3: - if (__pred(__first)) - return __first; - ++__first; - case 2: - if (__pred(__first)) - return __first; - ++__first; - case 1: - if (__pred(__first)) - return __first; - ++__first; - case 0: - default: - return __last; - } - } - - template - _GLIBCXX20_CONSTEXPR - inline _Iterator - __find_if(_Iterator __first, _Iterator __last, _Predicate __pred) - { - return __find_if(__first, __last, __pred, - std::__iterator_category(__first)); - } - /// Provided for stable_partition to use. template _GLIBCXX20_CONSTEXPR @@ -3279,18 +3209,6 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION __new_value); } - template - _GLIBCXX20_CONSTEXPR - typename iterator_traits<_InputIterator>::difference_type - __count_if(_InputIterator __first, _InputIterator __last, _Predicate __pred) - { - typename iterator_traits<_InputIterator>::difference_type __n = 0; - for (; __first != __last; ++__first) - if (__pred(__first)) - ++__n; - return __n; - } - #if __cplusplus >= 201103L /** * @brief Determines whether the elements of a sequence are sorted. @@ -3588,74 +3506,6 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION return std::make_pair(*__p.first, *__p.second); } - template - _GLIBCXX20_CONSTEXPR - bool - __is_permutation(_ForwardIterator1 __first1, _ForwardIterator1 __last1, - _ForwardIterator2 __first2, _BinaryPredicate __pred) - { - // Efficiently compare identical prefixes: O(N) if sequences - // have the same elements in the same order. - for (; __first1 != __last1; ++__first1, (void)++__first2) - if (!__pred(__first1, __first2)) - break; - - if (__first1 == __last1) - return true; - - // Establish __last2 assuming equal ranges by iterating over the - // rest of the list. - _ForwardIterator2 __last2 = __first2; - std::advance(__last2, std::distance(__first1, __last1)); - for (_ForwardIterator1 __scan = __first1; __scan != __last1; ++__scan) - { - if (__scan != std::__find_if(__first1, __scan, - __gnu_cxx::__ops::__iter_comp_iter(__pred, __scan))) - continue; // We've seen this one before. - - auto __matches - = std::__count_if(__first2, __last2, - __gnu_cxx::__ops::__iter_comp_iter(__pred, __scan)); - if (0 == __matches || - std::__count_if(__scan, __last1, - __gnu_cxx::__ops::__iter_comp_iter(__pred, __scan)) - != __matches) - return false; - } - return true; - } - - /** - * @brief Checks whether a permutation of the second sequence is equal - * to the first sequence. - * @ingroup non_mutating_algorithms - * @param __first1 Start of first range. - * @param __last1 End of first range. - * @param __first2 Start of second range. - * @return true if there exists a permutation of the elements in the range - * [__first2, __first2 + (__last1 - __first1)), beginning with - * ForwardIterator2 begin, such that equal(__first1, __last1, begin) - * returns true; otherwise, returns false. - */ - template - _GLIBCXX20_CONSTEXPR - inline bool - is_permutation(_ForwardIterator1 __first1, _ForwardIterator1 __last1, - _ForwardIterator2 __first2) - { - // concept requirements - __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator1>) - __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator2>) - __glibcxx_function_requires(_EqualOpConcept< - typename iterator_traits<_ForwardIterator1>::value_type, - typename iterator_traits<_ForwardIterator2>::value_type>) - __glibcxx_requires_valid_range(__first1, __last1); - - return std::__is_permutation(__first1, __last1, __first2, - __gnu_cxx::__ops::__iter_equal_to_iter()); - } - /** * @brief Checks whether a permutation of the second sequence is equal * to the first sequence. diff --git a/libstdc++-v3/include/bits/stl_algobase.h b/libstdc++-v3/include/bits/stl_algobase.h index e4f7fa417ed..5ec2f25424d 100644 --- a/libstdc++-v3/include/bits/stl_algobase.h +++ b/libstdc++-v3/include/bits/stl_algobase.h @@ -1899,6 +1899,159 @@ _GLIBCXX_BEGIN_NAMESPACE_ALGO #endif _GLIBCXX_END_NAMESPACE_ALGO + + /// This is an overload used by find algos for the Input Iterator case. + template + _GLIBCXX20_CONSTEXPR + inline _InputIterator + __find_if(_InputIterator __first, _InputIterator __last, + _Predicate __pred, input_iterator_tag) + { + while (__first != __last && !__pred(__first)) + ++__first; + return __first; + } + + /// This is an overload used by find algos for the RAI case. + template + _GLIBCXX20_CONSTEXPR + _RandomAccessIterator + __find_if(_RandomAccessIterator __first, _RandomAccessIterator __last, + _Predicate __pred, random_access_iterator_tag) + { + typename iterator_traits<_RandomAccessIterator>::difference_type + __trip_count = (__last - __first) >> 2; + + for (; __trip_count > 0; --__trip_count) + { + if (__pred(__first)) + return __first; + ++__first; + + if (__pred(__first)) + return __first; + ++__first; + + if (__pred(__first)) + return __first; + ++__first; + + if (__pred(__first)) + return __first; + ++__first; + } + + switch (__last - __first) + { + case 3: + if (__pred(__first)) + return __first; + ++__first; + case 2: + if (__pred(__first)) + return __first; + ++__first; + case 1: + if (__pred(__first)) + return __first; + ++__first; + case 0: + default: + return __last; + } + } + + template + _GLIBCXX20_CONSTEXPR + inline _Iterator + __find_if(_Iterator __first, _Iterator __last, _Predicate __pred) + { + return __find_if(__first, __last, __pred, + std::__iterator_category(__first)); + } + + template + _GLIBCXX20_CONSTEXPR + typename iterator_traits<_InputIterator>::difference_type + __count_if(_InputIterator __first, _InputIterator __last, _Predicate __pred) + { + typename iterator_traits<_InputIterator>::difference_type __n = 0; + for (; __first != __last; ++__first) + if (__pred(__first)) + ++__n; + return __n; + } + +#if __cplusplus >= 201103L + template + _GLIBCXX20_CONSTEXPR + bool + __is_permutation(_ForwardIterator1 __first1, _ForwardIterator1 __last1, + _ForwardIterator2 __first2, _BinaryPredicate __pred) + { + // Efficiently compare identical prefixes: O(N) if sequences + // have the same elements in the same order. + for (; __first1 != __last1; ++__first1, (void)++__first2) + if (!__pred(__first1, __first2)) + break; + + if (__first1 == __last1) + return true; + + // Establish __last2 assuming equal ranges by iterating over the + // rest of the list. + _ForwardIterator2 __last2 = __first2; + std::advance(__last2, std::distance(__first1, __last1)); + for (_ForwardIterator1 __scan = __first1; __scan != __last1; ++__scan) + { + if (__scan != std::__find_if(__first1, __scan, + __gnu_cxx::__ops::__iter_comp_iter(__pred, __scan))) + continue; // We've seen this one before. + + auto __matches + = std::__count_if(__first2, __last2, + __gnu_cxx::__ops::__iter_comp_iter(__pred, __scan)); + if (0 == __matches || + std::__count_if(__scan, __last1, + __gnu_cxx::__ops::__iter_comp_iter(__pred, __scan)) + != __matches) + return false; + } + return true; + } + + /** + * @brief Checks whether a permutation of the second sequence is equal + * to the first sequence. + * @ingroup non_mutating_algorithms + * @param __first1 Start of first range. + * @param __last1 End of first range. + * @param __first2 Start of second range. + * @return true if there exists a permutation of the elements in the range + * [__first2, __first2 + (__last1 - __first1)), beginning with + * ForwardIterator2 begin, such that equal(__first1, __last1, begin) + * returns true; otherwise, returns false. + */ + template + _GLIBCXX20_CONSTEXPR + inline bool + is_permutation(_ForwardIterator1 __first1, _ForwardIterator1 __last1, + _ForwardIterator2 __first2) + { + // concept requirements + __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator1>) + __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator2>) + __glibcxx_function_requires(_EqualOpConcept< + typename iterator_traits<_ForwardIterator1>::value_type, + typename iterator_traits<_ForwardIterator2>::value_type>) + __glibcxx_requires_valid_range(__first1, __last1); + + return std::__is_permutation(__first1, __last1, __first2, + __gnu_cxx::__ops::__iter_equal_to_iter()); + } +#endif // C++11 + _GLIBCXX_END_NAMESPACE_VERSION } // namespace std -- 2.30.2