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