diff options
Diffstat (limited to 'contrib/llvm-project/libcxx/include/__algorithm/find_end.h')
| -rw-r--r-- | contrib/llvm-project/libcxx/include/__algorithm/find_end.h | 181 |
1 files changed, 130 insertions, 51 deletions
diff --git a/contrib/llvm-project/libcxx/include/__algorithm/find_end.h b/contrib/llvm-project/libcxx/include/__algorithm/find_end.h index 0220c0939711..65e9f29b1c1f 100644 --- a/contrib/llvm-project/libcxx/include/__algorithm/find_end.h +++ b/contrib/llvm-project/libcxx/include/__algorithm/find_end.h @@ -11,8 +11,16 @@ #define _LIBCPP___ALGORITHM_FIND_END_OF_H #include <__algorithm/comp.h> +#include <__algorithm/iterator_operations.h> +#include <__algorithm/search.h> #include <__config> +#include <__functional/identity.h> +#include <__iterator/advance.h> #include <__iterator/iterator_traits.h> +#include <__iterator/next.h> +#include <__iterator/reverse_iterator.h> +#include <__utility/pair.h> +#include <type_traits> #if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER) # pragma GCC system_header @@ -20,35 +28,52 @@ _LIBCPP_BEGIN_NAMESPACE_STD -template <class _BinaryPredicate, class _ForwardIterator1, class _ForwardIterator2> -_LIBCPP_CONSTEXPR_AFTER_CXX17 _ForwardIterator1 __find_end(_ForwardIterator1 __first1, _ForwardIterator1 __last1, - _ForwardIterator2 __first2, _ForwardIterator2 __last2, - _BinaryPredicate __pred, forward_iterator_tag, - forward_iterator_tag) { +template < + class _AlgPolicy, + class _Iter1, + class _Sent1, + class _Iter2, + class _Sent2, + class _Pred, + class _Proj1, + class _Proj2> +_LIBCPP_HIDE_FROM_ABI inline _LIBCPP_CONSTEXPR_AFTER_CXX11 pair<_Iter1, _Iter1> __find_end_impl( + _Iter1 __first1, + _Sent1 __last1, + _Iter2 __first2, + _Sent2 __last2, + _Pred& __pred, + _Proj1& __proj1, + _Proj2& __proj2, + forward_iterator_tag, + forward_iterator_tag) { // modeled after search algorithm - _ForwardIterator1 __r = __last1; // __last1 is the "default" answer + _Iter1 __match_first = _IterOps<_AlgPolicy>::next(__first1, __last1); // __last1 is the "default" answer + _Iter1 __match_last = __match_first; if (__first2 == __last2) - return __r; + return pair<_Iter1, _Iter1>(__match_last, __match_last); while (true) { while (true) { - if (__first1 == __last1) // if source exhausted return last correct answer - return __r; // (or __last1 if never found) - if (__pred(*__first1, *__first2)) + if (__first1 == __last1) // if source exhausted return last correct answer (or __last1 if never found) + return pair<_Iter1, _Iter1>(__match_first, __match_last); + if (std::__invoke(__pred, std::__invoke(__proj1, *__first1), std::__invoke(__proj2, *__first2))) break; ++__first1; } // *__first1 matches *__first2, now match elements after here - _ForwardIterator1 __m1 = __first1; - _ForwardIterator2 __m2 = __first2; + _Iter1 __m1 = __first1; + _Iter2 __m2 = __first2; while (true) { if (++__m2 == __last2) { // Pattern exhaused, record answer and search for another one - __r = __first1; + __match_first = __first1; + __match_last = ++__m1; ++__first1; break; } if (++__m1 == __last1) // Source exhausted, return last answer - return __r; - if (!__pred(*__m1, *__m2)) // mismatch, restart with a new __first + return pair<_Iter1, _Iter1>(__match_first, __match_last); + // mismatch, restart with a new __first + if (!std::__invoke(__pred, std::__invoke(__proj1, *__m1), std::__invoke(__proj2, *__m2))) { ++__first1; break; @@ -57,33 +82,52 @@ _LIBCPP_CONSTEXPR_AFTER_CXX17 _ForwardIterator1 __find_end(_ForwardIterator1 __f } } -template <class _BinaryPredicate, class _BidirectionalIterator1, class _BidirectionalIterator2> -_LIBCPP_CONSTEXPR_AFTER_CXX17 _BidirectionalIterator1 __find_end( - _BidirectionalIterator1 __first1, _BidirectionalIterator1 __last1, _BidirectionalIterator2 __first2, - _BidirectionalIterator2 __last2, _BinaryPredicate __pred, bidirectional_iterator_tag, bidirectional_iterator_tag) { +template < + class _IterOps, + class _Pred, + class _Iter1, + class _Sent1, + class _Iter2, + class _Sent2, + class _Proj1, + class _Proj2> +_LIBCPP_CONSTEXPR_AFTER_CXX17 _Iter1 __find_end( + _Iter1 __first1, + _Sent1 __sent1, + _Iter2 __first2, + _Sent2 __sent2, + _Pred& __pred, + _Proj1& __proj1, + _Proj2& __proj2, + bidirectional_iterator_tag, + bidirectional_iterator_tag) { + auto __last1 = _IterOps::next(__first1, __sent1); + auto __last2 = _IterOps::next(__first2, __sent2); // modeled after search algorithm (in reverse) if (__first2 == __last2) return __last1; // Everything matches an empty sequence - _BidirectionalIterator1 __l1 = __last1; - _BidirectionalIterator2 __l2 = __last2; + _Iter1 __l1 = __last1; + _Iter2 __l2 = __last2; --__l2; while (true) { // Find last element in sequence 1 that matchs *(__last2-1), with a mininum of loop checks while (true) { if (__first1 == __l1) // return __last1 if no element matches *__first2 return __last1; - if (__pred(*--__l1, *__l2)) + if (std::__invoke(__pred, std::__invoke(__proj1, *--__l1), std::__invoke(__proj2, *__l2))) break; } // *__l1 matches *__l2, now match elements before here - _BidirectionalIterator1 __m1 = __l1; - _BidirectionalIterator2 __m2 = __l2; + _Iter1 __m1 = __l1; + _Iter2 __m2 = __l2; while (true) { if (__m2 == __first2) // If pattern exhausted, __m1 is the answer (works for 1 element pattern) return __m1; if (__m1 == __first1) // Otherwise if source exhaused, pattern not found return __last1; - if (!__pred(*--__m1, *--__m2)) // if there is a mismatch, restart with a new __l1 + + // if there is a mismatch, restart with a new __l1 + if (!std::__invoke(__pred, std::__invoke(__proj1, *--__m1), std::__invoke(__proj2, *--__m2))) { break; } // else there is a match, check next elements @@ -91,37 +135,53 @@ _LIBCPP_CONSTEXPR_AFTER_CXX17 _BidirectionalIterator1 __find_end( } } -template <class _BinaryPredicate, class _RandomAccessIterator1, class _RandomAccessIterator2> -_LIBCPP_CONSTEXPR_AFTER_CXX11 _RandomAccessIterator1 __find_end( - _RandomAccessIterator1 __first1, _RandomAccessIterator1 __last1, _RandomAccessIterator2 __first2, - _RandomAccessIterator2 __last2, _BinaryPredicate __pred, random_access_iterator_tag, random_access_iterator_tag) { - typedef typename iterator_traits<_RandomAccessIterator1>::difference_type _D1; - typedef typename iterator_traits<_RandomAccessIterator2>::difference_type _D2; +template < + class _AlgPolicy, + class _Pred, + class _Iter1, + class _Sent1, + class _Iter2, + class _Sent2, + class _Proj1, + class _Proj2> +_LIBCPP_CONSTEXPR_AFTER_CXX11 _Iter1 __find_end( + _Iter1 __first1, + _Sent1 __sent1, + _Iter2 __first2, + _Sent2 __sent2, + _Pred& __pred, + _Proj1& __proj1, + _Proj2& __proj2, + random_access_iterator_tag, + random_access_iterator_tag) { + typedef typename iterator_traits<_Iter1>::difference_type _D1; + auto __last1 = _IterOps<_AlgPolicy>::next(__first1, __sent1); + auto __last2 = _IterOps<_AlgPolicy>::next(__first2, __sent2); // Take advantage of knowing source and pattern lengths. Stop short when source is smaller than pattern - _D2 __len2 = __last2 - __first2; + auto __len2 = __last2 - __first2; if (__len2 == 0) return __last1; - _D1 __len1 = __last1 - __first1; + auto __len1 = __last1 - __first1; if (__len1 < __len2) return __last1; - const _RandomAccessIterator1 __s = __first1 + _D1(__len2 - 1); // End of pattern match can't go before here - _RandomAccessIterator1 __l1 = __last1; - _RandomAccessIterator2 __l2 = __last2; + const _Iter1 __s = __first1 + _D1(__len2 - 1); // End of pattern match can't go before here + _Iter1 __l1 = __last1; + _Iter2 __l2 = __last2; --__l2; while (true) { while (true) { if (__s == __l1) return __last1; - if (__pred(*--__l1, *__l2)) + if (std::__invoke(__pred, std::__invoke(__proj1, *--__l1), std::__invoke(__proj2, *__l2))) break; } - _RandomAccessIterator1 __m1 = __l1; - _RandomAccessIterator2 __m2 = __l2; + _Iter1 __m1 = __l1; + _Iter2 __m2 = __l2; while (true) { if (__m2 == __first2) return __m1; // no need to check range on __m1 because __s guarantees we have enough source - if (!__pred(*--__m1, *--__m2)) { + if (!std::__invoke(__pred, std::__invoke(__proj1, *--__m1), std::__invoke(*--__m2))) { break; } } @@ -129,20 +189,39 @@ _LIBCPP_CONSTEXPR_AFTER_CXX11 _RandomAccessIterator1 __find_end( } template <class _ForwardIterator1, class _ForwardIterator2, class _BinaryPredicate> -_LIBCPP_NODISCARD_EXT inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17 _ForwardIterator1 -find_end(_ForwardIterator1 __first1, _ForwardIterator1 __last1, _ForwardIterator2 __first2, _ForwardIterator2 __last2, - _BinaryPredicate __pred) { - return _VSTD::__find_end<_BinaryPredicate&>( - __first1, __last1, __first2, __last2, __pred, typename iterator_traits<_ForwardIterator1>::iterator_category(), - typename iterator_traits<_ForwardIterator2>::iterator_category()); +_LIBCPP_NODISCARD inline _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_AFTER_CXX11 +_ForwardIterator1 __find_end_classic(_ForwardIterator1 __first1, _ForwardIterator1 __last1, + _ForwardIterator2 __first2, _ForwardIterator2 __last2, + _BinaryPredicate& __pred) { + auto __proj = __identity(); + return std::__find_end_impl<_ClassicAlgPolicy>( + __first1, + __last1, + __first2, + __last2, + __pred, + __proj, + __proj, + typename iterator_traits<_ForwardIterator1>::iterator_category(), + typename iterator_traits<_ForwardIterator2>::iterator_category()) + .first; +} + +template <class _ForwardIterator1, class _ForwardIterator2, class _BinaryPredicate> +_LIBCPP_NODISCARD_EXT inline _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_AFTER_CXX17 +_ForwardIterator1 find_end(_ForwardIterator1 __first1, _ForwardIterator1 __last1, + _ForwardIterator2 __first2, _ForwardIterator2 __last2, + _BinaryPredicate __pred) { + return std::__find_end_classic(__first1, __last1, __first2, __last2, __pred); } template <class _ForwardIterator1, class _ForwardIterator2> -_LIBCPP_NODISCARD_EXT inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17 _ForwardIterator1 -find_end(_ForwardIterator1 __first1, _ForwardIterator1 __last1, _ForwardIterator2 __first2, _ForwardIterator2 __last2) { - typedef typename iterator_traits<_ForwardIterator1>::value_type __v1; - typedef typename iterator_traits<_ForwardIterator2>::value_type __v2; - return _VSTD::find_end(__first1, __last1, __first2, __last2, __equal_to<__v1, __v2>()); +_LIBCPP_NODISCARD_EXT inline _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_AFTER_CXX17 +_ForwardIterator1 find_end(_ForwardIterator1 __first1, _ForwardIterator1 __last1, + _ForwardIterator2 __first2, _ForwardIterator2 __last2) { + using __v1 = typename iterator_traits<_ForwardIterator1>::value_type; + using __v2 = typename iterator_traits<_ForwardIterator2>::value_type; + return std::find_end(__first1, __last1, __first2, __last2, __equal_to<__v1, __v2>()); } _LIBCPP_END_NAMESPACE_STD |