1*5f757f3fSDimitry Andric //===----------------------------------------------------------------------===//
2*5f757f3fSDimitry Andric //
3*5f757f3fSDimitry Andric // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
4*5f757f3fSDimitry Andric // See https://llvm.org/LICENSE.txt for license information.
5*5f757f3fSDimitry Andric // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
6*5f757f3fSDimitry Andric //
7*5f757f3fSDimitry Andric //===----------------------------------------------------------------------===//
8*5f757f3fSDimitry Andric
9*5f757f3fSDimitry Andric #ifndef _LIBCPP___ALGORITHM_FIND_SEGMENT_IF_H
10*5f757f3fSDimitry Andric #define _LIBCPP___ALGORITHM_FIND_SEGMENT_IF_H
11*5f757f3fSDimitry Andric
12*5f757f3fSDimitry Andric #include <__config>
13*5f757f3fSDimitry Andric #include <__iterator/segmented_iterator.h>
14*5f757f3fSDimitry Andric
15*5f757f3fSDimitry Andric #if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER)
16*5f757f3fSDimitry Andric # pragma GCC system_header
17*5f757f3fSDimitry Andric #endif
18*5f757f3fSDimitry Andric
19*5f757f3fSDimitry Andric _LIBCPP_BEGIN_NAMESPACE_STD
20*5f757f3fSDimitry Andric
21*5f757f3fSDimitry Andric // __find_segment_if is a utility function for optimizing iteration over segmented iterators linearly.
22*5f757f3fSDimitry Andric // [__first, __last) has to be a segmented range. __pred is expected to take a range of local iterators and the __proj.
23*5f757f3fSDimitry Andric // It returns an iterator to the first element that satisfies the predicate, or a one-past-the-end iterator if there was
24*5f757f3fSDimitry Andric // no match. __proj may be anything that should be passed to __pred, but is expected to be a projection to support
25*5f757f3fSDimitry Andric // ranges algorithms, or __identity for classic algorithms.
26*5f757f3fSDimitry Andric
27*5f757f3fSDimitry Andric template <class _SegmentedIterator, class _Pred, class _Proj>
28*5f757f3fSDimitry Andric _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX14 _SegmentedIterator
__find_segment_if(_SegmentedIterator __first,_SegmentedIterator __last,_Pred __pred,_Proj & __proj)29*5f757f3fSDimitry Andric __find_segment_if(_SegmentedIterator __first, _SegmentedIterator __last, _Pred __pred, _Proj& __proj) {
30*5f757f3fSDimitry Andric using _Traits = __segmented_iterator_traits<_SegmentedIterator>;
31*5f757f3fSDimitry Andric
32*5f757f3fSDimitry Andric auto __sfirst = _Traits::__segment(__first);
33*5f757f3fSDimitry Andric auto __slast = _Traits::__segment(__last);
34*5f757f3fSDimitry Andric
35*5f757f3fSDimitry Andric // We are in a single segment, so we might not be at the beginning or end
36*5f757f3fSDimitry Andric if (__sfirst == __slast)
37*5f757f3fSDimitry Andric return _Traits::__compose(__sfirst, __pred(_Traits::__local(__first), _Traits::__local(__last), __proj));
38*5f757f3fSDimitry Andric
39*5f757f3fSDimitry Andric { // We have more than one segment. Iterate over the first segment, since we might not start at the beginning
40*5f757f3fSDimitry Andric auto __llast = _Traits::__end(__sfirst);
41*5f757f3fSDimitry Andric auto __liter = __pred(_Traits::__local(__first), __llast, __proj);
42*5f757f3fSDimitry Andric if (__liter != __llast)
43*5f757f3fSDimitry Andric return _Traits::__compose(__sfirst, __liter);
44*5f757f3fSDimitry Andric }
45*5f757f3fSDimitry Andric ++__sfirst;
46*5f757f3fSDimitry Andric
47*5f757f3fSDimitry Andric // Iterate over the segments which are guaranteed to be completely in the range
48*5f757f3fSDimitry Andric while (__sfirst != __slast) {
49*5f757f3fSDimitry Andric auto __llast = _Traits::__end(__sfirst);
50*5f757f3fSDimitry Andric auto __liter = __pred(_Traits::__begin(__sfirst), _Traits::__end(__sfirst), __proj);
51*5f757f3fSDimitry Andric if (__liter != __llast)
52*5f757f3fSDimitry Andric return _Traits::__compose(__sfirst, __liter);
53*5f757f3fSDimitry Andric ++__sfirst;
54*5f757f3fSDimitry Andric }
55*5f757f3fSDimitry Andric
56*5f757f3fSDimitry Andric // Iterate over the last segment
57*5f757f3fSDimitry Andric return _Traits::__compose(__sfirst, __pred(_Traits::__begin(__sfirst), _Traits::__local(__last), __proj));
58*5f757f3fSDimitry Andric }
59*5f757f3fSDimitry Andric
60*5f757f3fSDimitry Andric _LIBCPP_END_NAMESPACE_STD
61*5f757f3fSDimitry Andric
62*5f757f3fSDimitry Andric #endif // _LIBCPP___ALGORITHM_FIND_SEGMENT_IF_H
63