include/QtConcurrent/qtconcurrentfilterkernel.h

0001 // Copyright (C) 2016 The Qt Company Ltd.
0002 // SPDX-License-Identifier: LicenseRef-Qt-Commercial OR LGPL-3.0-only OR GPL-2.0-only OR GPL-3.0-only
0003
0004 #ifndef QTCONCURRENT_FILTERKERNEL_H
0005 #define QTCONCURRENT_FILTERKERNEL_H
0006
0007 #include <QtConcurrent/qtconcurrent_global.h>
0008
0009 #if !defined(QT_NO_CONCURRENT) || defined (Q_QDOC)
0010
0011 #include <QtConcurrent/qtconcurrentiteratekernel.h>
0012 #include <QtConcurrent/qtconcurrentmapkernel.h>
0013 #include <QtConcurrent/qtconcurrentreducekernel.h>
0014
0015 QT_BEGIN_NAMESPACE
0016
0017
0018
0019 namespace QtConcurrent {
0020
0021 template <typename T>
0022 struct qValueType
0023 {
0024     typedef typename T::value_type value_type;
0025 };
0026
0027 template <typename T>
0028 struct qValueType<const T*>
0029 {
0030     typedef T value_type;
0031 };
0032
0033 template <typename T>
0034 struct qValueType<T*>
0035 {
0036     typedef T value_type;
0037 };
0038
0039 // Implementation of filter
0040 template <typename Sequence, typename KeepFunctor, typename ReduceFunctor>
0041 class FilterKernel : public IterateKernel<typename Sequence::const_iterator, void>
0042 {
0043     typedef ReduceKernel<ReduceFunctor, Sequence, typename Sequence::value_type> Reducer;
0044     typedef IterateKernel<typename Sequence::const_iterator, void> IterateKernelType;
0045     typedef void T;
0046
0047     Sequence reducedResult;
0048     Sequence &sequence;
0049     KeepFunctor keep;
0050     ReduceFunctor reduce;
0051     Reducer reducer;
0052
0053 public:
0054     template <typename Keep = KeepFunctor, typename Reduce = ReduceFunctor>
0055     FilterKernel(QThreadPool *pool, Sequence &_sequence, Keep &&_keep, Reduce &&_reduce)
0056         : IterateKernelType(pool, const_cast<const Sequence &>(_sequence).begin(),
0057                             const_cast<const Sequence &>(_sequence).end()), reducedResult(),
0058           sequence(_sequence),
0059           keep(std::forward<Keep>(_keep)),
0060           reduce(std::forward<Reduce>(_reduce)),
0061           reducer(pool, OrderedReduce)
0062     { }
0063
0064     bool runIteration(typename Sequence::const_iterator it, int index, T *) override
0065     {
0066         IntermediateResults<typename Sequence::value_type> results;
0067         results.begin = index;
0068         results.end = index + 1;
0069
0070         if (std::invoke(keep, *it))
0071             results.vector.append(*it);
0072
0073         reducer.runReduce(reduce, reducedResult, results);
0074         return false;
0075     }
0076
0077     bool runIterations(typename Sequence::const_iterator sequenceBeginIterator, int begin, int end, T *) override
0078     {
0079         IntermediateResults<typename Sequence::value_type> results;
0080         results.begin = begin;
0081         results.end = end;
0082         results.vector.reserve(end - begin);
0083
0084
0085         typename Sequence::const_iterator it = sequenceBeginIterator;
0086         std::advance(it, begin);
0087         for (int i = begin; i < end; ++i) {
0088             if (std::invoke(keep, *it))
0089                 results.vector.append(*it);
0090             std::advance(it, 1);
0091         }
0092
0093         reducer.runReduce(reduce, reducedResult, results);
0094         return false;
0095     }
0096
0097     void finish() override
0098     {
0099         reducer.finish(reduce, reducedResult);
0100         sequence = std::move(reducedResult);
0101     }
0102
0103     inline bool shouldThrottleThread() override
0104     {
0105         return IterateKernelType::shouldThrottleThread() || reducer.shouldThrottle();
0106     }
0107
0108     inline bool shouldStartThread() override
0109     {
0110         return IterateKernelType::shouldStartThread() && reducer.shouldStartThread();
0111     }
0112
0113     typedef void ReturnType;
0114     typedef void ResultType;
0115 };
0116
0117 // Implementation of filter-reduce
0118 template <typename ReducedResultType,
0119           typename Iterator,
0120           typename KeepFunctor,
0121           typename ReduceFunctor,
0122           typename Reducer = ReduceKernel<ReduceFunctor,
0123                                           ReducedResultType,
0124                                           typename qValueType<Iterator>::value_type> >
0125 class FilteredReducedKernel : public IterateKernel<Iterator, ReducedResultType>
0126 {
0127     ReducedResultType &reducedResult;
0128     KeepFunctor keep;
0129     ReduceFunctor reduce;
0130     Reducer reducer;
0131     typedef IterateKernel<Iterator, ReducedResultType> IterateKernelType;
0132
0133 public:
0134     template<typename Keep = KeepFunctor, typename Reduce = ReduceFunctor>
0135     FilteredReducedKernel(QThreadPool *pool, Iterator begin, Iterator end, Keep &&_keep,
0136                           Reduce &&_reduce, ReduceOptions reduceOption)
0137         : IterateKernelType(pool, begin, end),
0138           reducedResult(this->defaultValue.value),
0139           keep(std::forward<Keep>(_keep)),
0140           reduce(std::forward<Reduce>(_reduce)),
0141           reducer(pool, reduceOption)
0142     { }
0143
0144     template <typename Keep = KeepFunctor, typename Reduce = ReduceFunctor>
0145     FilteredReducedKernel(QThreadPool *pool, Iterator begin, Iterator end, Keep &&_keep,
0146                           Reduce &&_reduce, ReducedResultType &&initialValue,
0147                           ReduceOptions reduceOption)
0148         : IterateKernelType(pool, begin, end, std::forward<ReducedResultType>(initialValue)),
0149           reducedResult(this->defaultValue.value),
0150           keep(std::forward<Keep>(_keep)),
0151           reduce(std::forward<Reduce>(_reduce)),
0152           reducer(pool, reduceOption)
0153     {
0154     }
0155
0156     bool runIteration(Iterator it, int index, ReducedResultType *) override
0157     {
0158         IntermediateResults<typename qValueType<Iterator>::value_type> results;
0159         results.begin = index;
0160         results.end = index + 1;
0161
0162         if (std::invoke(keep, *it))
0163             results.vector.append(*it);
0164
0165         reducer.runReduce(reduce, reducedResult, results);
0166         return false;
0167     }
0168
0169     bool runIterations(Iterator sequenceBeginIterator, int begin, int end, ReducedResultType *) override
0170     {
0171         IntermediateResults<typename qValueType<Iterator>::value_type> results;
0172         results.begin = begin;
0173         results.end = end;
0174         results.vector.reserve(end - begin);
0175
0176         Iterator it = sequenceBeginIterator;
0177         std::advance(it, begin);
0178         for (int i = begin; i < end; ++i) {
0179             if (std::invoke(keep, *it))
0180                 results.vector.append(*it);
0181             std::advance(it, 1);
0182         }
0183
0184         reducer.runReduce(reduce, reducedResult, results);
0185         return false;
0186     }
0187
0188     void finish() override
0189     {
0190         reducer.finish(reduce, reducedResult);
0191     }
0192
0193     inline bool shouldThrottleThread() override
0194     {
0195         return IterateKernelType::shouldThrottleThread() || reducer.shouldThrottle();
0196     }
0197
0198     inline bool shouldStartThread() override
0199     {
0200         return IterateKernelType::shouldStartThread() && reducer.shouldStartThread();
0201     }
0202
0203     typedef ReducedResultType ReturnType;
0204     typedef ReducedResultType ResultType;
0205     ReducedResultType *result() override
0206     {
0207         return &reducedResult;
0208     }
0209 };
0210
0211 // Implementation of filter that reports individual results via QFutureInterface
0212 template <typename Iterator, typename KeepFunctor>
0213 class FilteredEachKernel : public IterateKernel<Iterator, typename qValueType<Iterator>::value_type>
0214 {
0215     typedef typename qValueType<Iterator>::value_type T;
0216     typedef IterateKernel<Iterator, T> IterateKernelType;
0217
0218     KeepFunctor keep;
0219
0220 public:
0221     typedef T ReturnType;
0222     typedef T ResultType;
0223
0224     template <typename Keep = KeepFunctor>
0225     FilteredEachKernel(QThreadPool *pool, Iterator begin, Iterator end, Keep &&_keep)
0226         : IterateKernelType(pool, begin, end), keep(std::forward<Keep>(_keep))
0227     { }
0228
0229     void start() override
0230     {
0231         if (this->futureInterface)
0232             this->futureInterface->setFilterMode(true);
0233         IterateKernelType::start();
0234     }
0235
0236     bool runIteration(Iterator it, int index, T *) override
0237     {
0238         if (std::invoke(keep, *it))
0239             this->reportResult(&(*it), index);
0240         else
0241             this->reportResult(nullptr, index);
0242         return false;
0243     }
0244
0245     bool runIterations(Iterator sequenceBeginIterator, int begin, int end, T *) override
0246     {
0247         const int count = end - begin;
0248         IntermediateResults<typename qValueType<Iterator>::value_type> results;
0249         results.begin = begin;
0250         results.end = end;
0251         results.vector.reserve(count);
0252
0253         Iterator it = sequenceBeginIterator;
0254         std::advance(it, begin);
0255         for (int i = begin; i < end; ++i) {
0256             if (std::invoke(keep, *it))
0257                 results.vector.append(*it);
0258             std::advance(it, 1);
0259         }
0260
0261         this->reportResults(results.vector, begin, count);
0262         return false;
0263     }
0264 };
0265
0266 //! [QtConcurrent-2]
0267 template <typename Iterator, typename KeepFunctor>
0268 inline
0269 ThreadEngineStarter<typename qValueType<Iterator>::value_type>
0270 startFiltered(QThreadPool *pool, Iterator begin, Iterator end, KeepFunctor &&functor)
0271 {
0272     return startThreadEngine(new FilteredEachKernel<Iterator, std::decay_t<KeepFunctor>>
0273                              (pool, begin, end, std::forward<KeepFunctor>(functor)));
0274 }
0275
0276 //! [QtConcurrent-3]
0277 template <typename Sequence, typename KeepFunctor>
0278 inline decltype(auto) startFiltered(QThreadPool *pool, Sequence &&sequence, KeepFunctor &&functor)
0279 {
0280     using DecayedSequence = std::decay_t<Sequence>;
0281     using DecayedFunctor = std::decay_t<KeepFunctor>;
0282     using SequenceHolderType = SequenceHolder1<DecayedSequence,
0283             FilteredEachKernel<typename DecayedSequence::const_iterator, DecayedFunctor>,
0284             DecayedFunctor>;
0285     return startThreadEngine(new SequenceHolderType(pool, std::forward<Sequence>(sequence),
0286                                                     std::forward<KeepFunctor>(functor)));
0287 }
0288
0289 //! [QtConcurrent-4]
0290 template <typename ResultType, typename Sequence, typename MapFunctor, typename ReduceFunctor>
0291 inline ThreadEngineStarter<ResultType> startFilteredReduced(QThreadPool *pool,
0292                                                             Sequence &&sequence,
0293                                                             MapFunctor &&mapFunctor,
0294                                                             ReduceFunctor &&reduceFunctor,
0295                                                             ReduceOptions options)
0296 {
0297     using DecayedSequence = std::decay_t<Sequence>;
0298     using DecayedMapFunctor = std::decay_t<MapFunctor>;
0299     using DecayedReduceFunctor = std::decay_t<ReduceFunctor>;
0300     using Iterator = typename DecayedSequence::const_iterator;
0301     using Reducer = ReduceKernel<DecayedReduceFunctor, ResultType,
0302                                  typename qValueType<Iterator>::value_type>;
0303     using FilteredReduceType = FilteredReducedKernel<ResultType, Iterator, DecayedMapFunctor,
0304                                                      DecayedReduceFunctor, Reducer>;
0305     using SequenceHolderType = SequenceHolder2<DecayedSequence, FilteredReduceType,
0306                                                DecayedMapFunctor, DecayedReduceFunctor>;
0307     return startThreadEngine(new SequenceHolderType(pool, std::forward<Sequence>(sequence),
0308                                                     std::forward<MapFunctor>(mapFunctor),
0309                                                     std::forward<ReduceFunctor>(reduceFunctor),
0310                                                     options));
0311 }
0312
0313
0314 //! [QtConcurrent-5]
0315 template <typename ResultType, typename Iterator, typename MapFunctor, typename ReduceFunctor>
0316 inline ThreadEngineStarter<ResultType> startFilteredReduced(QThreadPool *pool,
0317                                                             Iterator begin,
0318                                                             Iterator end,
0319                                                             MapFunctor &&mapFunctor,
0320                                                             ReduceFunctor &&reduceFunctor,
0321                                                             ReduceOptions options)
0322 {
0323     using Reducer = ReduceKernel<std::decay_t<ReduceFunctor>, ResultType,
0324                                  typename qValueType<Iterator>::value_type>;
0325     using FilteredReduceType = FilteredReducedKernel<ResultType, Iterator, std::decay_t<MapFunctor>,
0326                                                      std::decay_t<ReduceFunctor>, Reducer>;
0327     return startThreadEngine(
0328             new FilteredReduceType(pool, begin, end, std::forward<MapFunctor>(mapFunctor),
0329                                    std::forward<ReduceFunctor>(reduceFunctor), options));
0330 }
0331
0332 // Repeat the two functions above, but now with an initial value!
0333 //! [QtConcurrent-6]
0334 template <typename ResultType, typename Sequence, typename MapFunctor, typename ReduceFunctor>
0335 inline ThreadEngineStarter<ResultType> startFilteredReduced(QThreadPool *pool,
0336                                                             Sequence &&sequence,
0337                                                             MapFunctor &&mapFunctor,
0338                                                             ReduceFunctor &&reduceFunctor,
0339                                                             ResultType &&initialValue,
0340                                                             ReduceOptions options)
0341 {
0342     using DecayedSequence = std::decay_t<Sequence>;
0343     using DecayedMapFunctor = std::decay_t<MapFunctor>;
0344     using DecayedReduceFunctor = std::decay_t<ReduceFunctor>;
0345     using Iterator = typename DecayedSequence::const_iterator;
0346     using Reducer = ReduceKernel<DecayedReduceFunctor, ResultType,
0347                                  typename qValueType<Iterator>::value_type>;
0348     using FilteredReduceType = FilteredReducedKernel<ResultType, Iterator, DecayedMapFunctor,
0349                                                      DecayedReduceFunctor, Reducer>;
0350     using SequenceHolderType = SequenceHolder2<DecayedSequence, FilteredReduceType,
0351                                                DecayedMapFunctor, DecayedReduceFunctor>;
0352     return startThreadEngine(new SequenceHolderType(
0353             pool, std::forward<Sequence>(sequence), std::forward<MapFunctor>(mapFunctor),
0354             std::forward<ReduceFunctor>(reduceFunctor), std::forward<ResultType>(initialValue),
0355             options));
0356 }
0357
0358 //! [QtConcurrent-7]
0359 template <typename ResultType, typename Iterator, typename MapFunctor, typename ReduceFunctor>
0360 inline ThreadEngineStarter<ResultType> startFilteredReduced(QThreadPool *pool,
0361                                                             Iterator begin,
0362                                                             Iterator end,
0363                                                             MapFunctor &&mapFunctor,
0364                                                             ReduceFunctor &&reduceFunctor,
0365                                                             ResultType &&initialValue,
0366                                                             ReduceOptions options)
0367 {
0368     using Reducer = ReduceKernel<std::decay_t<ReduceFunctor>, ResultType,
0369                                  typename qValueType<Iterator>::value_type>;
0370     using FilteredReduceType = FilteredReducedKernel<ResultType, Iterator, std::decay_t<MapFunctor>,
0371                                                      std::decay_t<ReduceFunctor>, Reducer>;
0372     return startThreadEngine(
0373             new FilteredReduceType(pool, begin, end, std::forward<MapFunctor>(mapFunctor),
0374                                    std::forward<ReduceFunctor>(reduceFunctor),
0375                                    std::forward<ResultType>(initialValue), options));
0376 }
0377
0378
0379 } // namespace QtConcurrent
0380
0381
0382 QT_END_NAMESPACE
0383
0384 #endif // QT_NO_CONCURRENT
0385
0386 #endif