1// Copyright (C) 2016 The Qt Company Ltd.
2// SPDX-License-Identifier: LicenseRef-Qt-Commercial OR LGPL-3.0-only OR GPL-2.0-only OR GPL-3.0-only
3
4#ifndef QTCONCURRENT_FILTERKERNEL_H
5#define QTCONCURRENT_FILTERKERNEL_H
6
7#include <QtConcurrent/qtconcurrent_global.h>
8
9#if !defined(QT_NO_CONCURRENT) || defined (Q_QDOC)
10
11#include <QtConcurrent/qtconcurrentiteratekernel.h>
12#include <QtConcurrent/qtconcurrentmapkernel.h>
13#include <QtConcurrent/qtconcurrentreducekernel.h>
14
15QT_BEGIN_NAMESPACE
16
17
18
19namespace QtConcurrent {
20
21template <typename T>
22struct qValueType
23{
24 typedef typename T::value_type value_type;
25};
26
27template <typename T>
28struct qValueType<const T*>
29{
30 typedef T value_type;
31};
32
33template <typename T>
34struct qValueType<T*>
35{
36 typedef T value_type;
37};
38
39// Implementation of filter
40template <typename Sequence, typename KeepFunctor, typename ReduceFunctor>
41class FilterKernel : public IterateKernel<typename Sequence::const_iterator, void>
42{
43 typedef ReduceKernel<ReduceFunctor, Sequence, typename Sequence::value_type> Reducer;
44 typedef IterateKernel<typename Sequence::const_iterator, void> IterateKernelType;
45 typedef void T;
46
47 Sequence reducedResult;
48 Sequence &sequence;
49 KeepFunctor keep;
50 ReduceFunctor reduce;
51 Reducer reducer;
52
53public:
54 template <typename Keep = KeepFunctor, typename Reduce = ReduceFunctor>
55 FilterKernel(QThreadPool *pool, Sequence &_sequence, Keep &&_keep, Reduce &&_reduce)
56 : IterateKernelType(pool, const_cast<const Sequence &>(_sequence).begin(),
57 const_cast<const Sequence &>(_sequence).end()), reducedResult(),
58 sequence(_sequence),
59 keep(std::forward<Keep>(_keep)),
60 reduce(std::forward<Reduce>(_reduce)),
61 reducer(pool, OrderedReduce)
62 { }
63
64 bool runIteration(typename Sequence::const_iterator it, int index, T *) override
65 {
66 IntermediateResults<typename Sequence::value_type> results;
67 results.begin = index;
68 results.end = index + 1;
69
70 if (std::invoke(keep, *it))
71 results.vector.append(*it);
72
73 reducer.runReduce(reduce, reducedResult, results);
74 return false;
75 }
76
77 bool runIterations(typename Sequence::const_iterator sequenceBeginIterator, int begin, int end, T *) override
78 {
79 IntermediateResults<typename Sequence::value_type> results;
80 results.begin = begin;
81 results.end = end;
82 results.vector.reserve(end - begin);
83
84
85 typename Sequence::const_iterator it = sequenceBeginIterator;
86 std::advance(it, begin);
87 for (int i = begin; i < end; ++i) {
88 if (std::invoke(keep, *it))
89 results.vector.append(*it);
90 std::advance(it, 1);
91 }
92
93 reducer.runReduce(reduce, reducedResult, results);
94 return false;
95 }
96
97 void finish() override
98 {
99 reducer.finish(reduce, reducedResult);
100 sequence = std::move(reducedResult);
101 }
102
103 inline bool shouldThrottleThread() override
104 {
105 return IterateKernelType::shouldThrottleThread() || reducer.shouldThrottle();
106 }
107
108 inline bool shouldStartThread() override
109 {
110 return IterateKernelType::shouldStartThread() && reducer.shouldStartThread();
111 }
112
113 typedef void ReturnType;
114 typedef void ResultType;
115};
116
117// Implementation of filter-reduce
118template <typename ReducedResultType,
119 typename Iterator,
120 typename KeepFunctor,
121 typename ReduceFunctor,
122 typename Reducer = ReduceKernel<ReduceFunctor,
123 ReducedResultType,
124 typename qValueType<Iterator>::value_type> >
125class FilteredReducedKernel : public IterateKernel<Iterator, ReducedResultType>
126{
127 ReducedResultType &reducedResult;
128 KeepFunctor keep;
129 ReduceFunctor reduce;
130 Reducer reducer;
131 typedef IterateKernel<Iterator, ReducedResultType> IterateKernelType;
132
133public:
134 template<typename Keep = KeepFunctor, typename Reduce = ReduceFunctor>
135 FilteredReducedKernel(QThreadPool *pool, Iterator begin, Iterator end, Keep &&_keep,
136 Reduce &&_reduce, ReduceOptions reduceOption)
137 : IterateKernelType(pool, begin, end),
138 reducedResult(this->defaultValue.value),
139 keep(std::forward<Keep>(_keep)),
140 reduce(std::forward<Reduce>(_reduce)),
141 reducer(pool, reduceOption)
142 { }
143
144 template <typename Keep = KeepFunctor, typename Reduce = ReduceFunctor>
145 FilteredReducedKernel(QThreadPool *pool, Iterator begin, Iterator end, Keep &&_keep,
146 Reduce &&_reduce, ReducedResultType &&initialValue,
147 ReduceOptions reduceOption)
148 : IterateKernelType(pool, begin, end, std::forward<ReducedResultType>(initialValue)),
149 reducedResult(this->defaultValue.value),
150 keep(std::forward<Keep>(_keep)),
151 reduce(std::forward<Reduce>(_reduce)),
152 reducer(pool, reduceOption)
153 {
154 }
155
156 bool runIteration(Iterator it, int index, ReducedResultType *) override
157 {
158 IntermediateResults<typename qValueType<Iterator>::value_type> results;
159 results.begin = index;
160 results.end = index + 1;
161
162 if (std::invoke(keep, *it))
163 results.vector.append(*it);
164
165 reducer.runReduce(reduce, reducedResult, results);
166 return false;
167 }
168
169 bool runIterations(Iterator sequenceBeginIterator, int begin, int end, ReducedResultType *) override
170 {
171 IntermediateResults<typename qValueType<Iterator>::value_type> results;
172 results.begin = begin;
173 results.end = end;
174 results.vector.reserve(end - begin);
175
176 Iterator it = sequenceBeginIterator;
177 std::advance(it, begin);
178 for (int i = begin; i < end; ++i) {
179 if (std::invoke(keep, *it))
180 results.vector.append(*it);
181 std::advance(it, 1);
182 }
183
184 reducer.runReduce(reduce, reducedResult, results);
185 return false;
186 }
187
188 void finish() override
189 {
190 reducer.finish(reduce, reducedResult);
191 }
192
193 inline bool shouldThrottleThread() override
194 {
195 return IterateKernelType::shouldThrottleThread() || reducer.shouldThrottle();
196 }
197
198 inline bool shouldStartThread() override
199 {
200 return IterateKernelType::shouldStartThread() && reducer.shouldStartThread();
201 }
202
203 typedef ReducedResultType ReturnType;
204 typedef ReducedResultType ResultType;
205 ReducedResultType *result() override
206 {
207 return &reducedResult;
208 }
209};
210
211// Implementation of filter that reports individual results via QFutureInterface
212template <typename Iterator, typename KeepFunctor>
213class FilteredEachKernel : public IterateKernel<Iterator, typename qValueType<Iterator>::value_type>
214{
215 typedef typename qValueType<Iterator>::value_type T;
216 typedef IterateKernel<Iterator, T> IterateKernelType;
217
218 KeepFunctor keep;
219
220public:
221 typedef T ReturnType;
222 typedef T ResultType;
223
224 template <typename Keep = KeepFunctor>
225 FilteredEachKernel(QThreadPool *pool, Iterator begin, Iterator end, Keep &&_keep)
226 : IterateKernelType(pool, begin, end), keep(std::forward<Keep>(_keep))
227 { }
228
229 void start() override
230 {
231 if (this->futureInterface)
232 this->futureInterface->setFilterMode(true);
233 IterateKernelType::start();
234 }
235
236 bool runIteration(Iterator it, int index, T *) override
237 {
238 if (std::invoke(keep, *it))
239 this->reportResult(&(*it), index);
240 else
241 this->reportResult(nullptr, index);
242 return false;
243 }
244
245 bool runIterations(Iterator sequenceBeginIterator, int begin, int end, T *) override
246 {
247 const int count = end - begin;
248 IntermediateResults<typename qValueType<Iterator>::value_type> results;
249 results.begin = begin;
250 results.end = end;
251 results.vector.reserve(count);
252
253 Iterator it = sequenceBeginIterator;
254 std::advance(it, begin);
255 for (int i = begin; i < end; ++i) {
256 if (std::invoke(keep, *it))
257 results.vector.append(*it);
258 std::advance(it, 1);
259 }
260
261 this->reportResults(results.vector, begin, count);
262 return false;
263 }
264};
265
266//! [QtConcurrent-2]
267template <typename Iterator, typename KeepFunctor>
268inline
269ThreadEngineStarter<typename qValueType<Iterator>::value_type>
270startFiltered(QThreadPool *pool, Iterator begin, Iterator end, KeepFunctor &&functor)
271{
272 return startThreadEngine(new FilteredEachKernel<Iterator, std::decay_t<KeepFunctor>>
273 (pool, begin, end, std::forward<KeepFunctor>(functor)));
274}
275
276//! [QtConcurrent-3]
277template <typename Sequence, typename KeepFunctor>
278inline decltype(auto) startFiltered(QThreadPool *pool, Sequence &&sequence, KeepFunctor &&functor)
279{
280 using DecayedSequence = std::decay_t<Sequence>;
281 using DecayedFunctor = std::decay_t<KeepFunctor>;
282 using SequenceHolderType = SequenceHolder1<DecayedSequence,
283 FilteredEachKernel<typename DecayedSequence::const_iterator, DecayedFunctor>,
284 DecayedFunctor>;
285 return startThreadEngine(new SequenceHolderType(pool, std::forward<Sequence>(sequence),
286 std::forward<KeepFunctor>(functor)));
287}
288
289//! [QtConcurrent-4]
290template <typename ResultType, typename Sequence, typename MapFunctor, typename ReduceFunctor>
291inline ThreadEngineStarter<ResultType> startFilteredReduced(QThreadPool *pool,
292 Sequence &&sequence,
293 MapFunctor &&mapFunctor,
294 ReduceFunctor &&reduceFunctor,
295 ReduceOptions options)
296{
297 using DecayedSequence = std::decay_t<Sequence>;
298 using DecayedMapFunctor = std::decay_t<MapFunctor>;
299 using DecayedReduceFunctor = std::decay_t<ReduceFunctor>;
300 using Iterator = typename DecayedSequence::const_iterator;
301 using Reducer = ReduceKernel<DecayedReduceFunctor, ResultType,
302 typename qValueType<Iterator>::value_type>;
303 using FilteredReduceType = FilteredReducedKernel<ResultType, Iterator, DecayedMapFunctor,
304 DecayedReduceFunctor, Reducer>;
305 using SequenceHolderType = SequenceHolder2<DecayedSequence, FilteredReduceType,
306 DecayedMapFunctor, DecayedReduceFunctor>;
307 return startThreadEngine(new SequenceHolderType(pool, std::forward<Sequence>(sequence),
308 std::forward<MapFunctor>(mapFunctor),
309 std::forward<ReduceFunctor>(reduceFunctor),
310 options));
311}
312
313
314//! [QtConcurrent-5]
315template <typename ResultType, typename Iterator, typename MapFunctor, typename ReduceFunctor>
316inline ThreadEngineStarter<ResultType> startFilteredReduced(QThreadPool *pool,
317 Iterator begin,
318 Iterator end,
319 MapFunctor &&mapFunctor,
320 ReduceFunctor &&reduceFunctor,
321 ReduceOptions options)
322{
323 using Reducer = ReduceKernel<std::decay_t<ReduceFunctor>, ResultType,
324 typename qValueType<Iterator>::value_type>;
325 using FilteredReduceType = FilteredReducedKernel<ResultType, Iterator, std::decay_t<MapFunctor>,
326 std::decay_t<ReduceFunctor>, Reducer>;
327 return startThreadEngine(
328 new FilteredReduceType(pool, begin, end, std::forward<MapFunctor>(mapFunctor),
329 std::forward<ReduceFunctor>(reduceFunctor), options));
330}
331
332// Repeat the two functions above, but now with an initial value!
333//! [QtConcurrent-6]
334template <typename ResultType, typename Sequence, typename MapFunctor, typename ReduceFunctor>
335inline ThreadEngineStarter<ResultType> startFilteredReduced(QThreadPool *pool,
336 Sequence &&sequence,
337 MapFunctor &&mapFunctor,
338 ReduceFunctor &&reduceFunctor,
339 ResultType &&initialValue,
340 ReduceOptions options)
341{
342 using DecayedSequence = std::decay_t<Sequence>;
343 using DecayedMapFunctor = std::decay_t<MapFunctor>;
344 using DecayedReduceFunctor = std::decay_t<ReduceFunctor>;
345 using Iterator = typename DecayedSequence::const_iterator;
346 using Reducer = ReduceKernel<DecayedReduceFunctor, ResultType,
347 typename qValueType<Iterator>::value_type>;
348 using FilteredReduceType = FilteredReducedKernel<ResultType, Iterator, DecayedMapFunctor,
349 DecayedReduceFunctor, Reducer>;
350 using SequenceHolderType = SequenceHolder2<DecayedSequence, FilteredReduceType,
351 DecayedMapFunctor, DecayedReduceFunctor>;
352 return startThreadEngine(new SequenceHolderType(
353 pool, std::forward<Sequence>(sequence), std::forward<MapFunctor>(mapFunctor),
354 std::forward<ReduceFunctor>(reduceFunctor), std::forward<ResultType>(initialValue),
355 options));
356}
357
358//! [QtConcurrent-7]
359template <typename ResultType, typename Iterator, typename MapFunctor, typename ReduceFunctor>
360inline ThreadEngineStarter<ResultType> startFilteredReduced(QThreadPool *pool,
361 Iterator begin,
362 Iterator end,
363 MapFunctor &&mapFunctor,
364 ReduceFunctor &&reduceFunctor,
365 ResultType &&initialValue,
366 ReduceOptions options)
367{
368 using Reducer = ReduceKernel<std::decay_t<ReduceFunctor>, ResultType,
369 typename qValueType<Iterator>::value_type>;
370 using FilteredReduceType = FilteredReducedKernel<ResultType, Iterator, std::decay_t<MapFunctor>,
371 std::decay_t<ReduceFunctor>, Reducer>;
372 return startThreadEngine(
373 new FilteredReduceType(pool, begin, end, std::forward<MapFunctor>(mapFunctor),
374 std::forward<ReduceFunctor>(reduceFunctor),
375 std::forward<ResultType>(initialValue), options));
376}
377
378
379} // namespace QtConcurrent
380
381
382QT_END_NAMESPACE
383
384#endif // QT_NO_CONCURRENT
385
386#endif
387

source code of qtbase/src/concurrent/qtconcurrentfilterkernel.h