1 /****************************************************************************
2 **
3 ** Copyright (C) 2016 The Qt Company Ltd.
4 ** Contact: https://www.qt.io/licensing/
5 **
6 ** This file is part of the QtConcurrent module of the Qt Toolkit.
7 **
8 ** $QT_BEGIN_LICENSE:LGPL$
9 ** Commercial License Usage
10 ** Licensees holding valid commercial Qt licenses may use this file in
11 ** accordance with the commercial license agreement provided with the
12 ** Software or, alternatively, in accordance with the terms contained in
13 ** a written agreement between you and The Qt Company. For licensing terms
14 ** and conditions see https://www.qt.io/terms-conditions. For further
15 ** information use the contact form at https://www.qt.io/contact-us.
16 **
17 ** GNU Lesser General Public License Usage
18 ** Alternatively, this file may be used under the terms of the GNU Lesser
19 ** General Public License version 3 as published by the Free Software
20 ** Foundation and appearing in the file LICENSE.LGPL3 included in the
21 ** packaging of this file. Please review the following information to
22 ** ensure the GNU Lesser General Public License version 3 requirements
23 ** will be met: https://www.gnu.org/licenses/lgpl-3.0.html.
24 **
25 ** GNU General Public License Usage
26 ** Alternatively, this file may be used under the terms of the GNU
27 ** General Public License version 2.0 or (at your option) the GNU General
28 ** Public license version 3 or any later version approved by the KDE Free
29 ** Qt Foundation. The licenses are as published by the Free Software
30 ** Foundation and appearing in the file LICENSE.GPL2 and LICENSE.GPL3
31 ** included in the packaging of this file. Please review the following
32 ** information to ensure the GNU General Public License requirements will
33 ** be met: https://www.gnu.org/licenses/gpl-2.0.html and
34 ** https://www.gnu.org/licenses/gpl-3.0.html.
35 **
36 ** $QT_END_LICENSE$
37 **
38 ****************************************************************************/
39 
40 #ifndef QTCONCURRENT_FILTERKERNEL_H
41 #define QTCONCURRENT_FILTERKERNEL_H
42 
43 #include <QtConcurrent/qtconcurrent_global.h>
44 
45 #if !defined(QT_NO_CONCURRENT) || defined (Q_CLANG_QDOC)
46 
47 #include <QtConcurrent/qtconcurrentiteratekernel.h>
48 #include <QtConcurrent/qtconcurrentmapkernel.h>
49 #include <QtConcurrent/qtconcurrentreducekernel.h>
50 
51 QT_BEGIN_NAMESPACE
52 
53 
54 
55 namespace QtConcurrent {
56 
57 template <typename T>
58 struct qValueType
59 {
60     typedef typename T::value_type value_type;
61 };
62 
63 template <typename T>
64 struct qValueType<const T*>
65 {
66     typedef T value_type;
67 };
68 
69 template <typename T>
70 struct qValueType<T*>
71 {
72     typedef T value_type;
73 };
74 
75 // Implementation of filter
76 template <typename Sequence, typename KeepFunctor, typename ReduceFunctor>
77 class FilterKernel : public IterateKernel<typename Sequence::const_iterator, void>
78 {
79     typedef ReduceKernel<ReduceFunctor, Sequence, typename Sequence::value_type> Reducer;
80     typedef IterateKernel<typename Sequence::const_iterator, void> IterateKernelType;
81     typedef typename ReduceFunctor::result_type T;
82 
83     Sequence reducedResult;
84     Sequence &sequence;
85     KeepFunctor keep;
86     ReduceFunctor reduce;
87     Reducer reducer;
88 
89 public:
90     FilterKernel(Sequence &_sequence, KeepFunctor _keep, ReduceFunctor _reduce)
91         : IterateKernelType(const_cast<const Sequence &>(_sequence).begin(), const_cast<const Sequence &>(_sequence).end()), reducedResult(),
92           sequence(_sequence),
93           keep(_keep),
94           reduce(_reduce),
95           reducer(OrderedReduce)
96     { }
97 
98     bool runIteration(typename Sequence::const_iterator it, int index, T *) override
99     {
100         IntermediateResults<typename Sequence::value_type> results;
101         results.begin = index;
102         results.end = index + 1;
103 
104             if (keep(*it))
105                 results.vector.append(*it);
106 
107             reducer.runReduce(reduce, reducedResult, results);
108             return false;
109     }
110 
111     bool runIterations(typename Sequence::const_iterator sequenceBeginIterator, int begin, int end, T *) override
112     {
113         IntermediateResults<typename Sequence::value_type> results;
114         results.begin = begin;
115         results.end = end;
116         results.vector.reserve(end - begin);
117 
118 
119         typename Sequence::const_iterator it = sequenceBeginIterator;
120         std::advance(it, begin);
121         for (int i = begin; i < end; ++i) {
122             if (keep(*it))
123                 results.vector.append(*it);
124             std::advance(it, 1);
125         }
126 
127         reducer.runReduce(reduce, reducedResult, results);
128         return false;
129     }
130 
131     void finish() override
132     {
133         reducer.finish(reduce, reducedResult);
134         sequence = reducedResult;
135     }
136 
137     inline bool shouldThrottleThread() override
138     {
139         return IterateKernelType::shouldThrottleThread() || reducer.shouldThrottle();
140     }
141 
142     inline bool shouldStartThread() override
143     {
144         return IterateKernelType::shouldStartThread() && reducer.shouldStartThread();
145     }
146 
147     typedef void ReturnType;
148     typedef void ResultType;
149 };
150 
151 // Implementation of filter-reduce
152 template <typename ReducedResultType,
153           typename Iterator,
154           typename KeepFunctor,
155           typename ReduceFunctor,
156           typename Reducer = ReduceKernel<ReduceFunctor,
157                                           ReducedResultType,
158                                           typename qValueType<Iterator>::value_type> >
159 class FilteredReducedKernel : public IterateKernel<Iterator, ReducedResultType>
160 {
161     ReducedResultType reducedResult;
162     KeepFunctor keep;
163     ReduceFunctor reduce;
164     Reducer reducer;
165     typedef IterateKernel<Iterator, ReducedResultType> IterateKernelType;
166 
167 public:
168     FilteredReducedKernel(Iterator begin,
169                           Iterator end,
170                           KeepFunctor _keep,
171                           ReduceFunctor _reduce,
172                           ReduceOptions reduceOption)
173         : IterateKernelType(begin, end), reducedResult(), keep(_keep), reduce(_reduce), reducer(reduceOption)
174     { }
175 
176 #if 0
177     FilteredReducedKernel(ReducedResultType initialValue,
178                           KeepFunctor keep,
179                           ReduceFunctor reduce,
180                           ReduceOption reduceOption)
181         : reducedResult(initialValue), keep(keep), reduce(reduce), reducer(reduceOption)
182     { }
183 #endif
184 
185     bool runIteration(Iterator it, int index, ReducedResultType *) override
186     {
187         IntermediateResults<typename qValueType<Iterator>::value_type> results;
188         results.begin = index;
189         results.end = index + 1;
190 
191         if (keep(*it))
192             results.vector.append(*it);
193 
194         reducer.runReduce(reduce, reducedResult, results);
195         return false;
196     }
197 
198     bool runIterations(Iterator sequenceBeginIterator, int begin, int end, ReducedResultType *) override
199     {
200         IntermediateResults<typename qValueType<Iterator>::value_type> results;
201         results.begin = begin;
202         results.end = end;
203         results.vector.reserve(end - begin);
204 
205         Iterator it = sequenceBeginIterator;
206         std::advance(it, begin);
207         for (int i = begin; i < end; ++i) {
208             if (keep(*it))
209                 results.vector.append(*it);
210             std::advance(it, 1);
211         }
212 
213         reducer.runReduce(reduce, reducedResult, results);
214         return false;
215     }
216 
217     void finish() override
218     {
219         reducer.finish(reduce, reducedResult);
220     }
221 
222     inline bool shouldThrottleThread() override
223     {
224         return IterateKernelType::shouldThrottleThread() || reducer.shouldThrottle();
225     }
226 
227     inline bool shouldStartThread() override
228     {
229         return IterateKernelType::shouldStartThread() && reducer.shouldStartThread();
230     }
231 
232     typedef ReducedResultType ReturnType;
233     typedef ReducedResultType ResultType;
234     ReducedResultType *result() override
235     {
236         return &reducedResult;
237     }
238 };
239 
240 // Implementation of filter that reports individual results via QFutureInterface
241 template <typename Iterator, typename KeepFunctor>
242 class FilteredEachKernel : public IterateKernel<Iterator, typename qValueType<Iterator>::value_type>
243 {
244     typedef typename qValueType<Iterator>::value_type T;
245     typedef IterateKernel<Iterator, T> IterateKernelType;
246 
247     KeepFunctor keep;
248 
249 public:
250     typedef T ReturnType;
251     typedef T ResultType;
252 
253     FilteredEachKernel(Iterator begin, Iterator end, KeepFunctor _keep)
254         : IterateKernelType(begin, end), keep(_keep)
255     { }
256 
257     void start() override
258     {
259         if (this->futureInterface)
260             this->futureInterface->setFilterMode(true);
261         IterateKernelType::start();
262     }
263 
264     bool runIteration(Iterator it, int index, T *) override
265     {
266         if (keep(*it))
267             this->reportResult(&(*it), index);
268         else
269             this->reportResult(nullptr, index);
270         return false;
271     }
272 
273     bool runIterations(Iterator sequenceBeginIterator, int begin, int end, T *) override
274     {
275         const int count = end - begin;
276         IntermediateResults<typename qValueType<Iterator>::value_type> results;
277         results.begin = begin;
278         results.end = end;
279         results.vector.reserve(count);
280 
281         Iterator it = sequenceBeginIterator;
282         std::advance(it, begin);
283         for (int i = begin; i < end; ++i) {
284             if (keep(*it))
285                 results.vector.append(*it);
286             std::advance(it, 1);
287         }
288 
289         this->reportResults(results.vector, begin, count);
290         return false;
291     }
292 };
293 
294 //! [QtConcurrent-2]
295 template <typename Iterator, typename KeepFunctor>
296 inline
297 ThreadEngineStarter<typename qValueType<Iterator>::value_type>
298 startFiltered(Iterator begin, Iterator end, KeepFunctor functor)
299 {
300     return startThreadEngine(new FilteredEachKernel<Iterator, KeepFunctor>(begin, end, functor));
301 }
302 
303 //! [QtConcurrent-3]
304 template <typename Sequence, typename KeepFunctor>
305 inline ThreadEngineStarter<typename Sequence::value_type>
306 startFiltered(const Sequence &sequence, KeepFunctor functor)
307 {
308     typedef SequenceHolder1<Sequence,
309                             FilteredEachKernel<typename Sequence::const_iterator, KeepFunctor>,
310                             KeepFunctor>
311         SequenceHolderType;
312         return startThreadEngine(new SequenceHolderType(sequence, functor));
313 }
314 
315 //! [QtConcurrent-4]
316 template <typename ResultType, typename Sequence, typename MapFunctor, typename ReduceFunctor>
317 inline ThreadEngineStarter<ResultType> startFilteredReduced(const Sequence & sequence,
318                                                            MapFunctor mapFunctor, ReduceFunctor reduceFunctor,
319                                                            ReduceOptions options)
320 {
321     typedef typename Sequence::const_iterator Iterator;
322     typedef ReduceKernel<ReduceFunctor, ResultType, typename qValueType<Iterator>::value_type > Reducer;
323     typedef FilteredReducedKernel<ResultType, Iterator, MapFunctor, ReduceFunctor, Reducer> FilteredReduceType;
324     typedef SequenceHolder2<Sequence, FilteredReduceType, MapFunctor, ReduceFunctor> SequenceHolderType;
325     return startThreadEngine(new SequenceHolderType(sequence, mapFunctor, reduceFunctor, options));
326 }
327 
328 
329 //! [QtConcurrent-5]
330 template <typename ResultType, typename Iterator, typename MapFunctor, typename ReduceFunctor>
331 inline ThreadEngineStarter<ResultType> startFilteredReduced(Iterator begin, Iterator end,
332                                                            MapFunctor mapFunctor, ReduceFunctor reduceFunctor,
333                                                            ReduceOptions options)
334 {
335     typedef ReduceKernel<ReduceFunctor, ResultType, typename qValueType<Iterator>::value_type> Reducer;
336     typedef FilteredReducedKernel<ResultType, Iterator, MapFunctor, ReduceFunctor, Reducer> FilteredReduceType;
337     return startThreadEngine(new FilteredReduceType(begin, end, mapFunctor, reduceFunctor, options));
338 }
339 
340 
341 } // namespace QtConcurrent
342 
343 
344 QT_END_NAMESPACE
345 
346 #endif // QT_NO_CONCURRENT
347 
348 #endif
349