src/corelib/concurrent/qtconcurrentmap.cpp

   1 /****************************************************************************
   2 **
   3 ** Copyright (C) 2010 Nokia Corporation and/or its subsidiary(-ies).
   4 ** All rights reserved.
   5 ** Contact: Nokia Corporation (qt-info@nokia.com)
   6 **
   7 ** This file is part of the QtCore module of the Qt Toolkit.
   8 **
   9 ** $QT_BEGIN_LICENSE:LGPL$
  10 ** No Commercial Usage
  11 ** This file contains pre-release code and may not be distributed.
  12 ** You may use this file in accordance with the terms and conditions
  13 ** contained in the Technology Preview License Agreement accompanying
  14 ** this package.
  15 **
  16 ** GNU Lesser General Public License Usage
  17 ** Alternatively, this file may be used under the terms of the GNU Lesser
  18 ** General Public License version 2.1 as published by the Free Software
  19 ** Foundation and appearing in the file LICENSE.LGPL included in the
  20 ** packaging of this file.  Please review the following information to
  21 ** ensure the GNU Lesser General Public License version 2.1 requirements
  22 ** will be met: http://www.gnu.org/licenses/old-licenses/lgpl-2.1.html.
  23 **
  24 ** In addition, as a special exception, Nokia gives you certain additional
  25 ** rights.  These rights are described in the Nokia Qt LGPL Exception
  26 ** version 1.1, included in the file LGPL_EXCEPTION.txt in this package.
  27 **
  28 ** If you have questions regarding the use of this file, please contact
  29 ** Nokia at qt-info@nokia.com.
  30 **
  31 **
  32 **
  33 **
  34 **
  35 **
  36 **
  37 **
  38 ** $QT_END_LICENSE$
  39 **
  40 ****************************************************************************/
  41
  42 /*!
  43     \namespace QtConcurrent
  44     \inmodule QtCore
  45     \since 4.4
  46     \brief The QtConcurrent namespace provides high-level APIs that make it
  47     possible to write multi-threaded programs without using low-level
  48     threading primitives.
  49
  50     See the \l {Concurrent Programming}{Qt Concurrent} chapter in
  51     the \l{threads.html}{threading} documentation.
  52
  53     \inheaderfile QtCore
  54     \ingroup thread
  55 */
  56
  57 /*!
  58     \namespace QtConcurrent::internal
  59     \internal
  60
  61     \brief The QtConcurrent::internal namespace contains QtConcurrent
  62     implementation details.
  63 */
  64
  65 /*!
  66     \enum QtConcurrent::ReduceOption
  67     This enum specifies the order of which results from the map or filter
  68     function are passed to the reduce function.
  69
  70     \value UnorderedReduce Reduction is done in an arbitrary order.
  71     \value OrderedReduce Reduction is done in the order of the
  72     original sequence.
  73     \value SequentialReduce Reduction is done sequentally: only one
  74     thread will enter the reduce function at a time. (Parallel reduction
  75     might be supported in a future version of Qt Concurrent.)
  76 */
  77
  78 /*!
  79     \headerfile <QtConcurrentMap>
  80     \title Concurrent Map and Map-Reduce
  81     \ingroup thread
  82
  83     \brief The <QtConcurrentMap> header provides concurrent Map and MapReduce.
  84
  85     These functions are a part of the \l {Concurrent Programming}{Qt Concurrent} framework.
  86
  87     The QtConcurrent::map(), QtConcurrent::mapped() and
  88     QtConcurrent::mappedReduced() functions run computations in parallel on
  89     the items in a sequence such as a QList or a QVector. QtConcurrent::map()
  90     modifies a sequence in-place, QtConcurrent::mapped() returns a new
  91     sequence containing the modified content, and QtConcurrent::mappedReduced()
  92     returns a single result.
  93
  94     Each of the above functions has a blocking variant that returns
  95     the final result instead of a QFuture. You use them in the same
  96     way as the asynchronous variants.
  97
  98     \snippet doc/src/snippets/code/src_corelib_concurrent_qtconcurrentmap.cpp 7
  99
 100     Note that the result types above are not QFuture objects, but real result
 101     types (in this case, QList<QImage> and QImage).
 102
 103     \section1 Concurrent Map
 104
 105     QtConcurrent::mapped() takes an input sequence and a map function. This map
 106     function is then called for each item in the sequence, and a new sequence
 107     containing the return values from the map function is returned.
 108
 109     The map function must be of the form:
 110
 111     \snippet doc/src/snippets/code/src_corelib_concurrent_qtconcurrentmap.cpp 0
 112
 113     T and U can be any type (and they can even be the same type), but T must
 114     match the type stored in the sequence. The function returns the modified
 115     or \e mapped content.
 116
 117     This example shows how to apply a scale function to all the items
 118     in a sequence:
 119
 120     \snippet doc/src/snippets/code/src_corelib_concurrent_qtconcurrentmap.cpp 1
 121
 122     The results of the map are made available through QFuture.  See the
 123     QFuture and QFutureWatcher documentation for more information on how to
 124     use QFuture in your applications.
 125
 126     If you want to modify a sequence in-place, use QtConcurrent::map(). The
 127     map function must then be of the form:
 128
 129     \snippet doc/src/snippets/code/src_corelib_concurrent_qtconcurrentmap.cpp 2
 130
 131     Note that the return value and return type of the map function are not
 132     used.
 133
 134     Using QtConcurrent::map() is similar to using QtConcurrent::mapped():
 135
 136     \snippet doc/src/snippets/code/src_corelib_concurrent_qtconcurrentmap.cpp 3
 137
 138     Since the sequence is modified in place, QtConcurrent::map() does not
 139     return any results via QFuture. However, you can still use QFuture and
 140     QFutureWatcher to monitor the status of the map.
 141
 142     \section1 Concurrent Map-Reduce
 143
 144     QtConcurrent::mappedReduced() is similar to QtConcurrent::mapped(), but
 145     instead of returning a sequence with the new results, the results are
 146     combined into a single value using a reduce function.
 147
 148     The reduce function must be of the form:
 149
 150     \snippet doc/src/snippets/code/src_corelib_concurrent_qtconcurrentmap.cpp 4
 151
 152     T is the type of the final result, U is the return type of the map
 153     function. Note that the return value and return type of the reduce
 154     function are not used.
 155
 156     Call QtConcurrent::mappedReduced() like this:
 157
 158     \snippet doc/src/snippets/code/src_corelib_concurrent_qtconcurrentmap.cpp 5
 159
 160     The reduce function will be called once for each result returned by the map
 161     function, and should merge the \e{intermediate} into the \e{result}
 162     variable.  QtConcurrent::mappedReduced() guarantees that only one thread
 163     will call reduce at a time, so using a mutex to lock the result variable
 164     is not neccesary. The QtConcurrent::ReduceOptions enum provides a way to
 165     control the order in which the reduction is done. If
 166     QtConcurrent::UnorderedReduce is used (the default), the order is
 167     undefined, while QtConcurrent::OrderedReduce ensures that the reduction
 168     is done in the order of the original sequence.
 169
 170     \section1 Additional API Features
 171
 172     \section2 Using Iterators instead of Sequence
 173
 174     Each of the above functions has a variant that takes an iterator range
 175     instead of a sequence. You use them in the same way as the sequence
 176     variants:
 177
 178     \snippet doc/src/snippets/code/src_corelib_concurrent_qtconcurrentmap.cpp 6
 179
 180     \section2 Blocking Variants
 181
 182     Each of the above functions has a blocking variant that returns
 183     the final result instead of a QFuture. You use them in the same
 184     way as the asynchronous variants.
 185
 186     \snippet doc/src/snippets/code/src_corelib_concurrent_qtconcurrentmap.cpp 7
 187
 188     Note that the result types above are not QFuture objects, but real result
 189     types (in this case, QList<QImage> and QImage).
 190
 191     \section2 Using Member Functions
 192
 193     QtConcurrent::map(), QtConcurrent::mapped(), and
 194     QtConcurrent::mappedReduced() accept pointers to member functions.
 195     The member function class type must match the type stored in the sequence:
 196
 197     \snippet doc/src/snippets/code/src_corelib_concurrent_qtconcurrentmap.cpp 8
 198
 199     Note that when using QtConcurrent::mappedReduced(), you can mix the use of
 200     normal and member functions freely:
 201
 202     \snippet doc/src/snippets/code/src_corelib_concurrent_qtconcurrentmap.cpp 9
 203
 204     \section2 Using Function Objects
 205
 206     QtConcurrent::map(), QtConcurrent::mapped(), and
 207     QtConcurrent::mappedReduced() accept function objects, which can be used to
 208     add state to a function call. The result_type typedef must define the
 209     result type of the function call operator:
 210
 211     \snippet doc/src/snippets/code/src_corelib_concurrent_qtconcurrentmap.cpp 14
 212
 213     \section2 Using Bound Function Arguments
 214
 215     Note that Qt does not provide support for bound functions. This is
 216     provided by 3rd party libraries like
 217     \l{http://www.boost.org/libs/bind/bind.html}{Boost} or
 218     \l{http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2005/n1836.pdf}{C++
 219     TR1 Library Extensions}.
 220
 221     If you want to use a map function that takes more than one argument you can
 222     use boost::bind() or std::tr1::bind() to transform it onto a function that
 223     takes one argument.
 224
 225     As an example, we'll use QImage::scaledToWidth():
 226
 227     \snippet doc/src/snippets/code/src_corelib_concurrent_qtconcurrentmap.cpp 10
 228
 229     scaledToWidth takes three arguments (including the "this" pointer) and
 230     can't be used with QtConcurrent::mapped() directly, because
 231     QtConcurrent::mapped() expects a function that takes one argument. To use
 232     QImage::scaledToWidth() with QtConcurrent::mapped() we have to provide a
 233     value for the \e{width} and the \e{transformation mode}:
 234
 235     \snippet doc/src/snippets/code/src_corelib_concurrent_qtconcurrentmap.cpp 11
 236
 237     The return value from boost::bind() is a function object (functor) with
 238     the following signature:
 239
 240     \snippet doc/src/snippets/code/src_corelib_concurrent_qtconcurrentmap.cpp 12
 241
 242     This matches what QtConcurrent::mapped() expects, and the complete example
 243     becomes:
 244
 245     \snippet doc/src/snippets/code/src_corelib_concurrent_qtconcurrentmap.cpp 13
 246 */
 247
 248 /*!
 249     \fn QFuture<void> QtConcurrent::map(Sequence &sequence, MapFunction function)
 250     \relates <QtConcurrentMap>
 251
 252     Calls \a function once for each item in \a sequence. The \a function is
 253     passed a reference to the item, so that any modifications done to the item
 254     will appear in \a sequence.
 255 */
 256
 257 /*!
 258     \fn QFuture<void> QtConcurrent::map(Iterator begin, Iterator end, MapFunction function)
 259     \relates <QtConcurrentMap>
 260
 261     Calls \a function once for each item from \a begin to \a end. The
 262     \a function is passed a reference to the item, so that any modifications
 263     done to the item will appear in the sequence which the iterators belong to.
 264 */
 265
 266 /*!
 267     \fn QFuture<T> QtConcurrent::mapped(const Sequence &sequence, MapFunction function)
 268     \relates <QtConcurrentMap>
 269
 270     Calls \a function once for each item in \a sequence and returns a future
 271     with each mapped item as a result. You can use QFuture::const_iterator or
 272     QFutureIterator to iterate through the results.
 273 */
 274
 275 /*!
 276     \fn QFuture<T> QtConcurrent::mapped(ConstIterator begin, ConstIterator end, MapFunction function)
 277     \relates <QtConcurrentMap>
 278
 279     Calls \a function once for each item from \a begin to \a end and returns a
 280     future with each mapped item as a result. You can use
 281     QFuture::const_iterator or QFutureIterator to iterate through the results.
 282 */
 283
 284 /*!
 285     \fn QFuture<T> QtConcurrent::mappedReduced(const Sequence &sequence,
 286     MapFunction mapFunction, ReduceFunction reduceFunction,
 287     QtConcurrent::ReduceOptions reduceOptions)
 288
 289     \relates <QtConcurrentMap>
 290
 291     Calls \a mapFunction once for each item in \a sequence. The return value of
 292     each \a mapFunction is passed to \a reduceFunction.
 293
 294     Note that while \a mapFunction is called concurrently, only one thread at a
 295     time will call \a reduceFunction. The order in which \a reduceFunction is
 296     called is determined by \a reduceOptions.
 297 */
 298
 299 /*!
 300     \fn QFuture<T> QtConcurrent::mappedReduced(ConstIterator begin,
 301     ConstIterator end, MapFunction mapFunction, ReduceFunction reduceFunction,
 302     QtConcurrent::ReduceOptions reduceOptions)
 303
 304     \relates <QtConcurrentMap>
 305
 306     Calls \a mapFunction once for each item from \a begin to \a end. The return
 307     value of each \a mapFunction is passed to \a reduceFunction.
 308
 309     Note that while \a mapFunction is called concurrently, only one thread at a
 310     time will call \a reduceFunction. By default, the order in which
 311     \a reduceFunction is called is undefined.
 312
 313     \note QtConcurrent::OrderedReduce results in the ordered reduction.
 314 */
 315
 316 /*!
 317   \fn void QtConcurrent::blockingMap(Sequence &sequence, MapFunction function)
 318
 319   Calls \a function once for each item in \a sequence. The \a function is
 320   passed a reference to the item, so that any modifications done to the item
 321   will appear in \a sequence.
 322
 323   \note This function will block until all items in the sequence have been processed.
 324
 325   \sa map()
 326 */
 327
 328 /*!
 329   \fn void QtConcurrent::blockingMap(Iterator begin, Iterator end, MapFunction function)
 330
 331   Calls \a function once for each item from \a begin to \a end. The
 332   \a function is passed a reference to the item, so that any modifications
 333   done to the item will appear in the sequence which the iterators belong to.
 334
 335   \note This function will block until the iterator reaches the end of the
 336   sequence being processed.
 337
 338   \sa map()
 339 */
 340
 341 /*!
 342   \fn T QtConcurrent::blockingMapped(const Sequence &sequence, MapFunction function)
 343
 344   Calls \a function once for each item in \a sequence and returns a Sequence containing
 345   the results. The type of the results will match the type returned my the MapFunction.
 346
 347   \note This function will block until all items in the sequence have been processed.
 348
 349   \sa mapped()
 350 */
 351
 352 /*!
 353   \fn T QtConcurrent::blockingMapped(ConstIterator begin, ConstIterator end, MapFunction function)
 354
 355   Calls \a function once for each item from \a begin to \a end and returns a
 356   container with the results. Specify the type of container as the a template
 357   argument, like this:
 358
 359   \code
 360      QList<int> ints = QtConcurrent::blockingMapped<QList<int> >(beginIterator, endIterator, fn);
 361   \endcode
 362
 363   \note This function will block until the iterator reaches the end of the
 364   sequence being processed.
 365
 366   \sa mapped()
 367 */
 368
 369 /*!
 370   \fn T QtConcurrent::blockingMappedReduced(const Sequence &sequence, MapFunction mapFunction, ReduceFunction reduceFunction, QtConcurrent::ReduceOptions reduceOptions)
 371
 372   \relates <QtConcurrentMap>
 373
 374   Calls \a mapFunction once for each item in \a sequence. The return value of
 375   each \a mapFunction is passed to \a reduceFunction.
 376
 377   Note that while \a mapFunction is called concurrently, only one thread at a
 378   time will call \a reduceFunction. The order in which \a reduceFunction is
 379   called is determined by \a reduceOptions.
 380
 381   \note This function will block until all items in the sequence have been processed.
 382
 383   \sa mapped()
 384 */
 385
 386 /*!
 387   \fn T QtConcurrent::blockingMappedReduced(ConstIterator begin, ConstIterator end, MapFunction mapFunction, ReduceFunction reduceFunction, QtConcurrent::ReduceOptions reduceOptions)
 388
 389   \relates <QtConcurrentMap>
 390
 391   Calls \a mapFunction once for each item from \a begin to \a end. The return
 392   value of each \a mapFunction is passed to \a reduceFunction.
 393
 394   Note that while \a mapFunction is called concurrently, only one thread at a
 395   time will call \a reduceFunction. The order in which \a reduceFunction is
 396   called is undefined.
 397
 398   \note This function will block until the iterator reaches the end of the
 399   sequence being processed.
 400
 401   \sa blockingMappedReduced()
 402 */