c++-gtk-utils
parallel.h
Go to the documentation of this file.
1 /* Copyright (C) 2013 and 2014 Chris Vine
2 
3 The library comprised in this file or of which this file is part is
4 distributed by Chris Vine under the GNU Lesser General Public
5 License as follows:
6 
7  This library is free software; you can redistribute it and/or
8  modify it under the terms of the GNU Lesser General Public License
9  as published by the Free Software Foundation; either version 2.1 of
10  the License, or (at your option) any later version.
11 
12  This library is distributed in the hope that it will be useful, but
13  WITHOUT ANY WARRANTY; without even the implied warranty of
14  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
15  Lesser General Public License, version 2.1, for more details.
16 
17  You should have received a copy of the GNU Lesser General Public
18  License, version 2.1, along with this library (see the file LGPL.TXT
19  which came with this source code package in the c++-gtk-utils
20  sub-directory); if not, write to the Free Software Foundation, Inc.,
21  51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA.
22 
23 However, it is not intended that the object code of a program whose
24 source code instantiates a template from this file or uses macros or
25 inline functions (of any length) should by reason only of that
26 instantiation or use be subject to the restrictions of use in the GNU
27 Lesser General Public License. With that in mind, the words "and
28 macros, inline functions and instantiations of templates (of any
29 length)" shall be treated as substituted for the words "and small
30 macros and small inline functions (ten lines or less in length)" in
31 the fourth paragraph of section 5 of that licence. This does not
32 affect any other reason why object code may be subject to the
33 restrictions in that licence (nor for the avoidance of doubt does it
34 affect the application of section 2 of that licence to modifications
35 of the source code in this file).
36 
37 */
38 
39 #ifndef CGU_PARALLEL_H
40 #define CGU_PARALLEL_H
41 
42 #include <utility> // for std::move, std::forward and std::pair
43 #include <memory> // for std::unique_ptr
44 #include <iterator> // for std::iterator_traits and std::distance
45 #include <exception> // for std::exception
46 #include <functional> // for std::bind
47 #include <type_traits> // for std::remove_reference and std::remove_const
48 #include <limits> // for std::numeric_limits
49 #include <algorithm> // for std::min
50 #include <tuple>
51 
52 #include <c++-gtk-utils/callback.h>
54 #include <c++-gtk-utils/mutex.h>
56 
57 namespace Cgu {
58 
59 namespace Thread {
60 
61 struct ParallelError: public std::exception {
62  virtual const char* what() const throw() {return "ParallelError\n";}
63 };
64 
65 #ifndef DOXYGEN_PARSING
66 
67 // in version 2.2.2, this was the ParallelHelper namespace. Because
68 // the meaning of the DiffType* argument of these functions has
69 // changed in version 2.2.3 (it is incremented rather than
70 // decremented), this is now the ParallelHelper2 namespace so that no
71 // ODR issues arise on library linking with old binaries
72 namespace ParallelHelper2 {
73 
74 template <class ArgType, class DiffType, class Iterator>
75 void for_each_cb_func(const Cgu::Callback::SafeFunctorArg<ArgType&>& s_task,
76  Iterator iter,
77  Mutex* m, Cond* cond,
78  DiffType* done_count) {
79  s_task(*iter);
80  Mutex::Lock l{*m};
81  ++*done_count;
82  cond->signal();
83 }
84 
85 template <class FType, class ArgType, class DestType>
86 void transform1_func(const FType& func,
87  ArgType& arg,
88  DestType& res) {
89  res = func(arg);
90 }
91 
92 
93 template <class ArgType, class DestType, class DiffType, class SourceIterator>
94 void transform1_cb_func(const Cgu::Callback::SafeFunctorArg<ArgType&, DestType&>& s_task,
95  SourceIterator source_iter,
96  Mutex* m, Cond* cond,
97  DiffType* done_count,
98  DestType* results,
99  DiffType index) {
100  DestType res;
101  s_task(*source_iter, res);
102  Mutex::Lock l{*m};
103  // move to 'results' within the mutex because g++ <= 4.7 does not
104  // correctly implement the C++11 memory model on some 64 bit
105  // platforms (this is a slight pessimization for gcc >= 4.8)
106  results[index] = std::move(res);
107  ++*done_count;
108  cond->signal();
109 }
110 
111 template <class FType, class Arg1Type,
112  class Arg2Type, class DestType>
113 void transform2_func(const FType& func,
114  Arg1Type& arg1,
115  Arg2Type& arg2,
116  DestType& res) {
117  res = func(arg1, arg2);
118 }
119 
120 
121 template <class Arg1Type, class Arg2Type, class DestType,
122  class DiffType, class SourceIterator1, class SourceIterator2>
123 void transform2_cb_func(const Cgu::Callback::SafeFunctorArg<Arg1Type&, Arg2Type&, DestType&>& s_task,
124  SourceIterator1 source_iter1,
125  SourceIterator2 source_iter2,
126  Mutex* m, Cond* cond,
127  DiffType* done_count,
128  DestType* results,
129  DiffType index) {
130  DestType res;
131  s_task(*source_iter1, *source_iter2, res);
132  Mutex::Lock l{*m};
133  // move to 'results' within the mutex because g++ <= 4.7 does not
134  // correctly implement the C++11 memory model on some 64 bit
135  // platforms (this is a slight pessimization for gcc >= 4.8)
136  results[index] = std::move(res);
137  ++*done_count;
138  cond->signal();
139 }
140 
141 template <class DiffType>
142 void fail_func(Mutex* m, Cond* cond,
143  bool* error, DiffType* done_count) noexcept {
144  Mutex::Lock l{*m};
145  ++*done_count;
146  *error = true;
147  cond->signal();
148 }
149 
150 } // namespace ParallelHelper2
151 
152 #endif // DOXYGEN_PARSING
153 
154 /**
155  * \#include <c++-gtk-utils/parallel.h>
156  *
157  * This function applies a callable object to each element of a
158  * container in the range ['first', 'last'), by executing each such
159  * application as a task of a Thread::TaskManager object. Tasks are
160  * added to the Thread::TaskManager object in the order in which the
161  * respective elements appear in the container (and if a task mutates
162  * its argument, it will do so in respect of the correct element of
163  * the container), but no other ordering arises, and the tasks will
164  * execute in parallel to the extent that the Thread::TaskManager
165  * object has sufficient threads available to do so.
166  *
167  * Apart from that, and that this function returns void, it does the
168  * same as std::for_each(). It can mutate container elements if the
169  * callable object takes its argument by non-const reference. It will
170  * not return until the callable object has been applied to all of the
171  * elements in the range ['first', 'last').
172  *
173  * This function can be called by a task running on the same
174  * TaskManager object. However if that is done, as the task would end
175  * up blocking on its sub-tasks, the maximum number of threads running
176  * on the TaskManager object should be incremented by one temporarily
177  * while this function is executing using the TaskManager::IncHandle
178  * scoped handle class in order to prevent any deadlock through thread
179  * starvation.
180  *
181  * @param tm The Thread::TaskManager object on which the tasks will
182  * run.
183  * @param first The beginning of the range to which 'func' is to be
184  * applied.
185  * @param last One past the last element to which 'func' is to be
186  * applied.
187  * @param func A callable object to be applied to each element in the
188  * range ['first', 'last'), such as formed by a lambda expression or
189  * the result of std::bind. It should take a single unbound argument
190  * of the value type of the container to which 'first' and 'last'
191  * relate or a const or non-const reference to that type. Any return
192  * value is discarded. If an exception propagates from 'func', the
193  * exception will be consumed while the for each loop is running, and
194  * an attempt will still be made to apply 'func' to all remaining
195  * elements in the range ['first', 'last'), and only after that
196  * attempt has completed will the exception Cgu::Thread::ParallelError
197  * be thrown.
198  * @exception std::bad_alloc This exception will be thrown if memory
199  * is exhausted and the system throws in that case. (On systems with
200  * over-commit/lazy-commit combined with virtual memory (swap), it is
201  * rarely useful to check for memory exhaustion). If this exception
202  * is thrown, some tasks may nonetheless have already started by
203  * virtue of the call to this function, but subsequent ones will not.
204  * @exception Cgu::Thread::TaskError This exception will be thrown if
205  * stop_all() has previously been called on the Thread::TaskManager
206  * object, or if another thread calls stop_all() after this method is
207  * called but before it has returned. It will also be thrown if the
208  * Thread::TaskManager object's is_error() method would return true
209  * because its internal thread pool loop implementation has thrown
210  * std::bad_alloc, or a thread has failed to start correctly because
211  * pthread has run out of resources. (On systems with
212  * over-commit/lazy-commit combined with virtual memory (swap), it is
213  * rarely useful to check for memory exhaustion, and if a reasonable
214  * maximum thread count has been chosen for the Thread::TaskManager
215  * object pthread should not run out of other resources, but there may
216  * be some specialized cases where the return value of is_error() is
217  * useful.) If this exception is thrown, some tasks may nonetheless
218  * have already started by virtue of the call to this function.
219  * @exception Cgu::Thread::ParallelError This exception will be thrown
220  * if an exception propagates from the 'func' callable object when it
221  * executes on being applied to one or more elements of the container.
222  * Such an exception will not stop an attempt being made to apply
223  * 'func' (successfully or unsuccessfully) to all elements in the
224  * range ['first', 'last'). Cgu::Thread::ParallelError will be thrown
225  * after such attempted application has finished.
226  * @exception Cgu::Thread::MutexError This exception will be thrown if
227  * initialization of a mutex used by this function fails. (It is
228  * often not worth checking for this, as it means either memory is
229  * exhausted or pthread has run out of other resources to create new
230  * mutexes.) If this exception is thrown, no tasks will start.
231  * @exception Cgu::Thread::CondError This exception will be thrown if
232  * initialization of a condition variable used by this function fails.
233  * (It is often not worth checking for this, as it means either memory
234  * is exhausted or pthread has run out of other resources to create
235  * new condition variables.) If this exception is thrown, no tasks
236  * will start.
237  * @note An exception might also be thrown if the copy or move
238  * constructor of the 'func' callable objects throws. If such an
239  * exception is thrown, no tasks will start.
240  *
241  * Since 2.0.19/2.2.2
242  */
243 template <class Iterator, class Func>
245  Iterator first,
246  Iterator last,
247  Func&& func) {
248 
249  typedef typename std::iterator_traits<Iterator>::value_type ArgType;
250  typedef typename std::iterator_traits<Iterator>::difference_type DiffType;
251 
252  Mutex mutex;
253  Cond cond;
254  DiffType start_count = 0;
255  DiffType done_count = 0;
256  bool error = false;
257 
258  // construct SafeFunctorArg objects so that they can be shared
259  // between different tasks
261  Cgu::Callback::lambda<ArgType&>(std::forward<Func>(func))
262  };
264  Cgu::Callback::make(&ParallelHelper2::fail_func<DiffType>,
265  &mutex,
266  &cond,
267  &error,
268  &done_count)
269  };
270 
271  for (; first != last; ++first, ++start_count) {
272  std::unique_ptr<const Cgu::Callback::Callback> task_cb(
273  Cgu::Callback::make_ref(&ParallelHelper2::for_each_cb_func<ArgType, DiffType, Iterator>,
274  s_task,
275  first,
276  &mutex,
277  &cond,
278  &done_count)
279  );
280  std::unique_ptr<const Cgu::Callback::Callback> fail_cb(
281  Cgu::Callback::lambda<>([s_fail] () {s_fail();})
282  );
283 
284  tm.add_task(std::move(task_cb), std::move(fail_cb));
285  }
286 
287  Mutex::Lock l{mutex};
288  while (start_count > done_count) cond.wait(mutex);
289  if (error) throw ParallelError();
290 }
291 
292 /**
293  * \#include <c++-gtk-utils/parallel.h>
294  *
295  * This function maps over a container in the range ['first', 'last'),
296  * applying a unary callable object to each element of the container
297  * in that range and storing the result in the destination range, by
298  * executing each such application as a task of a Thread::TaskManager
299  * object. Tasks are added to the Thread::TaskManager object in the
300  * order in which the respective elements appear in the source
301  * container, and the final result appears in the destination
302  * container in the same order as the source range from which it is
303  * generated (including if a back_inserter iterator is used), but no
304  * other ordering arises, and the tasks will execute in parallel to
305  * the extent that the Thread::TaskManager object has sufficient
306  * threads available to do so.
307  *
308  * Apart from that, this function does the same as the version of
309  * std::transform() taking a unary function, except that it returns
310  * void (see Thread::parallel_transform_partial() for a function which
311  * returns a destination iterator and an iterator to the source
312  * range). It will not return until the callable object has been
313  * applied to all of the elements in the range ['first', 'last').
314  *
315  * This function can be called by a task running on the same
316  * TaskManager object, perhaps with a view to delivering a result
317  * asynchronously to a glib main loop. However if that is done, as
318  * the task would end up blocking on its sub-tasks, the maximum number
319  * of threads running on the TaskManager object should be incremented
320  * by one temporarily while this function is executing using the
321  * TaskManager::IncHandle scoped handle class in order to prevent any
322  * deadlock through thread starvation.
323  *
324  * A task can carry out a map-reduce operation by passing the result
325  * of calling this function to std::accumulate() to perform a
326  * fold-left or fold-right on that result.
327  *
328  * A separate overload of this function takes a binary callable
329  * object.
330  *
331  * Here is a trivial example of a map-reduce operation which maps over
332  * a vector by multiplying each element by 2 in separate tasks, and
333  * then folds-left using std::accumulate() (std::accumulate() can fold
334  * using any callable object, but in this example the default of
335  * addition is used):
336  *
337  * @code
338  * using namespace Cgu;
339  * std::vector<int> v{1, 2, 3, 4, 5};
340  * Thread::TaskManager tm;
341  *
342  * Thread::parallel_transform(tm,
343  * v.begin(),
344  * v.end(),
345  * v.begin(),
346  * [] (int elt) {return elt * 2;});
347  * // res will be equal to 30
348  * int res = std::accumulate(v.begin(), v.end(), 0);
349  * @endcode
350  *
351  * @param tm The Thread::TaskManager object on which the tasks will
352  * run.
353  * @param first The beginning of the range to which 'func' is to be
354  * applied.
355  * @param last One past the last element to which 'func' is to be
356  * applied.
357  * @param dest The beginning of the range to which the result of
358  * applying 'func' to the elements in the range ['first', 'last') is
359  * to be stored. As in the case of std::transform, this can overlap
360  * with or be the same as the source range. It may also be an insert
361  * iterator.
362  * @param func A unary callable object to be applied to each element
363  * in the range ['first', 'last'), such as formed by a lambda
364  * expression or the result of std::bind. It should take a single
365  * unbound argument of the value type of the container to which
366  * 'first' and 'last' relate or a const or non-const reference to that
367  * type. If an exception propagates from 'func', the exception will
368  * be consumed while the transform loop is running, and an attempt
369  * will still be made to apply 'func' to all remaining elements in the
370  * range ['first', 'last'), and only after that attempt has completed
371  * will the exception Cgu::Thread::ParallelError be thrown.
372  * @exception std::bad_alloc This exception will be thrown if memory
373  * is exhausted and the system throws in that case. (On systems with
374  * over-commit/lazy-commit combined with virtual memory (swap), it is
375  * rarely useful to check for memory exhaustion). If this exception
376  * is thrown, some tasks may nonetheless have already started by
377  * virtue of the call to this function, but subsequent ones will not.
378  * @exception Cgu::Thread::TaskError This exception will be thrown if
379  * stop_all() has previously been called on the Thread::TaskManager
380  * object, or if another thread calls stop_all() after this method is
381  * called but before it has returned. It will also be thrown if the
382  * Thread::TaskManager object's is_error() method would return true
383  * because its internal thread pool loop implementation has thrown
384  * std::bad_alloc, or a thread has failed to start correctly because
385  * pthread has run out of resources. (On systems with
386  * over-commit/lazy-commit combined with virtual memory (swap), it is
387  * rarely useful to check for memory exhaustion, and if a reasonable
388  * maximum thread count has been chosen for the Thread::TaskManager
389  * object pthread should not run out of other resources, but there may
390  * be some specialized cases where the return value of is_error() is
391  * useful.) If this exception is thrown, some tasks may nonetheless
392  * have already started by virtue of the call to this function.
393  * @exception Cgu::Thread::ParallelError This exception will be thrown
394  * if an exception propagates from the 'func' callable object when it
395  * executes on being applied to one or more elements of the source
396  * container. Such an exception will not stop an attempt being made
397  * to apply 'func' (successfully or unsuccessfully) to all elements in
398  * the range ['first', 'last'). Cgu::Thread::ParallelError will be
399  * thrown after such attempted application has finished.
400  * @exception Cgu::Thread::MutexError This exception will be thrown if
401  * initialization of a mutex used by this function fails. (It is
402  * often not worth checking for this, as it means either memory is
403  * exhausted or pthread has run out of other resources to create new
404  * mutexes.) If this exception is thrown, no tasks will start.
405  * @exception Cgu::Thread::CondError This exception will be thrown if
406  * initialization of a condition variable used by this function fails.
407  * (It is often not worth checking for this, as it means either memory
408  * is exhausted or pthread has run out of other resources to create
409  * new condition variables.) If this exception is thrown, no tasks
410  * will start.
411  * @note An exception might also be thrown if the copy or move
412  * constructor of the 'func' callable objects throws. If such an
413  * exception is thrown, no tasks will start.
414  *
415  * Since 2.0.19/2.2.2
416  */
417 template <class SourceIterator, class DestIterator, class Func>
419  SourceIterator first,
420  SourceIterator last,
421  DestIterator dest,
422  Func&& func) {
423 
424  if (first == last) return;
425 
426  typedef typename std::iterator_traits<SourceIterator>::value_type ArgType;
427  typedef typename std::iterator_traits<SourceIterator>::difference_type DiffType;
428  typedef typename std::remove_const<typename std::remove_reference<Func>::type>::type FType;
429  typedef decltype(func(*first)) DestType;
430 
431  Mutex mutex;
432  Cond cond;
433  DiffType start_count = 0;
434  DiffType done_count = 0;
435  bool error = false;
436 
437  // intermediate results have to be held in an array so destination
438  // ordering can be enforced when using insert interators. This
439  // causes some inefficiency for non-random access iterators
440  std::unique_ptr<DestType[]> results(new DestType[std::distance(first, last)]);
441 
442  // construct SafeFunctorArg objects so that they can be shared
443  // between different tasks
445  Cgu::Callback::make_ref(&ParallelHelper2::transform1_func<FType, ArgType, DestType>,
446  std::forward<Func>(func))
447  };
449  Cgu::Callback::make(&ParallelHelper2::fail_func<DiffType>,
450  &mutex,
451  &cond,
452  &error,
453  &done_count)
454  };
455 
456  for (; first != last; ++first, ++start_count) {
457  std::unique_ptr<const Cgu::Callback::Callback> task_cb(
458  Cgu::Callback::lambda<>(std::bind(&ParallelHelper2::transform1_cb_func<ArgType, DestType, DiffType, SourceIterator>,
459  s_task,
460  first,
461  &mutex,
462  &cond,
463  &done_count,
464  results.get(),
465  start_count))
466  );
467  std::unique_ptr<const Cgu::Callback::Callback> fail_cb(
468  Cgu::Callback::lambda<>([s_fail] () {s_fail();})
469  );
470 
471  tm.add_task(std::move(task_cb), std::move(fail_cb));
472  }
473 
474  Mutex::Lock l{mutex};
475  while (start_count > done_count) cond.wait(mutex);
476  if (error) throw ParallelError();
477  for (DiffType index = 0; index < start_count; ++dest, ++index) {
478  *dest = std::move(results[index]);
479  }
480 }
481 
482 /**
483  * \#include <c++-gtk-utils/parallel.h>
484  *
485  * This function maps over two containers, one in the range ['first1',
486  * 'last1') and the other beginning at 'first2', applying a binary
487  * callable object to each element of the containers in those ranges
488  * and storing the result in the destination range, by executing each
489  * such application as a task of a Thread::TaskManager object. Tasks
490  * are added to the Thread::TaskManager object in the order in which
491  * the respective elements appear in the source containers, and the
492  * final result appears in the destination container in the same order
493  * as the source ranges from which it is generated (including if a
494  * back_inserter iterator is used), but no other ordering arises, and
495  * the tasks will execute in parallel to the extent that the
496  * Thread::TaskManager object has sufficient threads available to do
497  * so.
498  *
499  * Apart from that, this function does the same as the version of
500  * std::transform() taking a binary function, except that it returns
501  * void (see Thread::parallel_transform_partial() for a function which
502  * returns a destination iterator and iterators to the source ranges).
503  * It will not return until the callable object has been applied to
504  * all of the elements in the source ranges.
505  *
506  * This function can be called by a task running on the same
507  * TaskManager object, perhaps with a view to delivering a result
508  * asynchronously to a glib main loop. However if that is done, as
509  * the task would end up blocking on its sub-tasks, the maximum number
510  * of threads running on the TaskManager object should be incremented
511  * by one temporarily while this function is executing using the
512  * TaskManager::IncHandle scoped handle class in order to prevent any
513  * deadlock through thread starvation.
514  *
515  * A task can carry out a map-reduce operation by passing the result
516  * of calling this function to std::accumulate() to perform a
517  * fold-left or fold-right on that result.
518  *
519  * A separate overload of this function takes a unary callable object.
520  *
521  * Here is a trivial example of a map-reduce operation which maps over
522  * two vectors by adding respective elements of the vectors in
523  * separate tasks, and then folds-left using std::accumulate()
524  * (std::accumulate() can fold using any callable object, but in this
525  * example the default of addition is used):
526  *
527  * @code
528  * using namespace Cgu;
529  * std::vector<int> v1{2, 4, 6, 8, 10};
530  * std::vector<int> v2{10, 20, 30, 40, 50};
531  * std::vector<int> v3;
532  * Thread::TaskManager tm;
533  *
534  * Thread::parallel_transform(tm,
535  * v1.begin(),
536  * v1.end(),
537  * v2.begin(),
538  * std::back_inserter(v3),
539  * std::plus<int>());
540  * // res will be equal to 180
541  * int res = std::accumulate(v3.begin(), v3.end(), 0);
542  * @endcode
543  *
544  * @param tm The Thread::TaskManager object on which the tasks will
545  * run.
546  * @param first1 The beginning of the range which is to be passed as
547  * the first argument of 'func'.
548  * @param last1 One past the last element of the range which is to be
549  * passed as the first argument of 'func'.
550  * @param first2 The beginning of the range which is to be passed as
551  * the second argument of 'func'.
552  * @param dest The beginning of the range to which the result of
553  * applying 'func' to the elements in the source ranges is to be
554  * stored. As in the case of std::transform, this can overlap with or
555  * be the same as one of the source ranges. It may also be an insert
556  * iterator.
557  * @param func A binary callable object to be applied to each element
558  * in the source ranges, such as formed by a lambda expression or the
559  * result of std::bind. It should take two unbound arguments of the
560  * value types of the containers to which 'first1' and 'first2' relate
561  * or const or non-const references to those types. If an exception
562  * propagates from 'func', the exception will be consumed while the
563  * transform loop is running, and an attempt will still be made to
564  * apply 'func' to all remaining elements of the source ranges, and
565  * only after that attempt has completed will the exception
566  * Cgu::Thread::ParallelError be thrown.
567  * @exception std::bad_alloc This exception will be thrown if memory
568  * is exhausted and the system throws in that case. (On systems with
569  * over-commit/lazy-commit combined with virtual memory (swap), it is
570  * rarely useful to check for memory exhaustion). If this exception
571  * is thrown, some tasks may nonetheless have already started by
572  * virtue of the call to this function, but subsequent ones will not.
573  * @exception Cgu::Thread::TaskError This exception will be thrown if
574  * stop_all() has previously been called on the Thread::TaskManager
575  * object, or if another thread calls stop_all() after this method is
576  * called but before it has returned. It will also be thrown if the
577  * Thread::TaskManager object's is_error() method would return true
578  * because its internal thread pool loop implementation has thrown
579  * std::bad_alloc, or a thread has failed to start correctly because
580  * pthread has run out of resources. (On systems with
581  * over-commit/lazy-commit combined with virtual memory (swap), it is
582  * rarely useful to check for memory exhaustion, and if a reasonable
583  * maximum thread count has been chosen for the Thread::TaskManager
584  * object pthread should not run out of other resources, but there may
585  * be some specialized cases where the return value of is_error() is
586  * useful.) If this exception is thrown, some tasks may nonetheless
587  * have already started by virtue of the call to this function.
588  * @exception Cgu::Thread::ParallelError This exception will be thrown
589  * if an exception propagates from the 'func' callable object when it
590  * executes on being applied to one or more elements of the source
591  * ranges. Such an exception will not stop an attempt being made to
592  * apply 'func' (successfully or unsuccessfully) to all elements in
593  * the source ranges. Cgu::Thread::ParallelError will be thrown after
594  * such attempted application has finished.
595  * @exception Cgu::Thread::MutexError This exception will be thrown if
596  * initialization of a mutex used by this function fails. (It is
597  * often not worth checking for this, as it means either memory is
598  * exhausted or pthread has run out of other resources to create new
599  * mutexes.) If this exception is thrown, no tasks will start.
600  * @exception Cgu::Thread::CondError This exception will be thrown if
601  * initialization of a condition variable used by this function fails.
602  * (It is often not worth checking for this, as it means either memory
603  * is exhausted or pthread has run out of other resources to create
604  * new condition variables.) If this exception is thrown, no tasks
605  * will start.
606  * @note An exception might also be thrown if the copy or move
607  * constructor of the 'func' callable objects throws. If such an
608  * exception is thrown, no tasks will start.
609  *
610  * Since 2.0.19/2.2.2
611  */
612 template <class SourceIterator1, class SourceIterator2, class DestIterator, class Func>
614  SourceIterator1 first1,
615  SourceIterator1 last1,
616  SourceIterator2 first2,
617  DestIterator dest,
618  Func&& func) {
619 
620  if (first1 == last1) return;
621 
622  typedef typename std::iterator_traits<SourceIterator1>::value_type Arg1Type;
623  typedef typename std::iterator_traits<SourceIterator1>::difference_type DiffType;
624  typedef typename std::iterator_traits<SourceIterator2>::value_type Arg2Type;
625  typedef typename std::remove_const<typename std::remove_reference<Func>::type>::type FType;
626  typedef decltype(func(*first1, *first2)) DestType;
627 
628  Mutex mutex;
629  Cond cond;
630  DiffType start_count = 0;
631  DiffType done_count = 0;
632  bool error = false;
633 
634  // intermediate results have to be held in an array so destination
635  // ordering can be enforced when using insert interators. This
636  // causes some inefficiency for non-random access iterators
637  std::unique_ptr<DestType[]> results(new DestType[std::distance(first1, last1)]);
638 
639  // construct SafeFunctorArg objects so that they can be shared
640  // between different tasks
642  Cgu::Callback::make_ref(&ParallelHelper2::transform2_func<FType, Arg1Type, Arg2Type, DestType>,
643  std::forward<Func>(func))
644  };
646  Cgu::Callback::make(&ParallelHelper2::fail_func<DiffType>,
647  &mutex,
648  &cond,
649  &error,
650  &done_count)
651  };
652 
653  for (; first1 != last1; ++first1, ++first2, ++start_count) {
654  std::unique_ptr<const Cgu::Callback::Callback> task_cb(
655  Cgu::Callback::lambda<>(std::bind(&ParallelHelper2::transform2_cb_func<Arg1Type, Arg2Type, DestType, DiffType, SourceIterator1, SourceIterator2>,
656  s_task,
657  first1,
658  first2,
659  &mutex,
660  &cond,
661  &done_count,
662  results.get(),
663  start_count))
664  );
665  std::unique_ptr<const Cgu::Callback::Callback> fail_cb(
666  Cgu::Callback::lambda<>([s_fail] () {s_fail();})
667  );
668 
669  tm.add_task(std::move(task_cb), std::move(fail_cb));
670  }
671 
672  Mutex::Lock l{mutex};
673  while (start_count > done_count) cond.wait(mutex);
674  if (error) throw ParallelError();
675  for (DiffType index = 0; index < start_count; ++dest, ++index) {
676  *dest = std::move(results[index]);
677  }
678 }
679 
680 /**
681  * \#include <c++-gtk-utils/parallel.h>
682  *
683  * This function applies a callable object to each element of a
684  * container in the range ['first', 'last') subject to a maximum, by
685  * executing each such application as a task of a Thread::TaskManager
686  * object. Tasks are added to the Thread::TaskManager object in the
687  * order in which the respective elements appear in the container (and
688  * if a task mutates its argument, it will do so in respect of the
689  * correct element of the container), but no other ordering arises,
690  * and the tasks will execute in parallel to the extent that the
691  * Thread::TaskManager object has sufficient threads available to do
692  * so.
693  *
694  * This function does the same as Thread::parallel_for_each(), except
695  * that it returns an iterator to the element past the last element to
696  * which the callable object has been applied, and it has a 'max'
697  * parameter to limit the maximum number of elements to which the
698  * callable object will be applied on any one call to this function
699  * even if the range ['first', 'last') is greater than this maximum.
700  * Whether this limitation has had effect on any one call can be
701  * tested by checking whether the return value is equal to the 'last'
702  * parameter. If it is not, a further call to this function can be
703  * made.
704  *
705  * The main purpose of this additional function is to enable the
706  * application of the callable object to the elements of a container
707  * to be dealt with in chunks, possibly to enable other tasks to be
708  * interleaved at reasonable intervals. For a container which does
709  * not support random access iterators, the 'last' parameter can be
710  * set to, say, the end of the container and the chunk size set with
711  * the 'max' paramater, with the return value being used as the
712  * 'first' parameter for subsequent calls to this function. This
713  * avoids having to increment the iterator for each "chunk" by
714  * stepping through the container by hand. In this usage, it
715  * therefore represents a minor efficiency improvement.
716  *
717  * @param tm The Thread::TaskManager object on which the tasks will
718  * run.
719  * @param first The beginning of the range to which 'func' is to be
720  * applied.
721  * @param last One past the last element to which 'func' is to be
722  * applied, subject to any maximum specified as the 'max' parameter.
723  * @param max The maximum number of elements of the source container
724  * to which 'func' will be applied on this call. It is not an error
725  * if it is greater than the distance between 'first' and 'last'. If
726  * it is equal to or greater than that distance, it follows that the
727  * iterator returned will be equal to 'last'. The same results if
728  * 'max' is a negative number (in that case no maximum will take
729  * effect and each element in the range ['first', 'last') will have
730  * 'func' applied to it).
731  * @param func A callable object to be applied (subject to the
732  * maximum) to each element in the range ['first', 'last'), such as
733  * formed by a lambda expression or the result of std::bind. It
734  * should take a single unbound argument of the value type of the
735  * container to which 'first' and 'last' relate or a const or
736  * non-const reference to that type. Any return value is discarded.
737  * If an exception propagates from 'func', the exception will be
738  * consumed while the for each loop is running, and an attempt will
739  * still be made to apply 'func' to all remaining elements in the
740  * range ['first', 'last') subject to the maximum, and only after that
741  * attempt has completed will the exception Cgu::Thread::ParallelError
742  * be thrown.
743  * @return An iterator representing the element past the last element
744  * of the range to which 'func' was applied, which may be passed as
745  * the 'first' argument of a subsequent call to this function.
746  * @exception std::bad_alloc This exception will be thrown if memory
747  * is exhausted and the system throws in that case. (On systems with
748  * over-commit/lazy-commit combined with virtual memory (swap), it is
749  * rarely useful to check for memory exhaustion). If this exception
750  * is thrown, some tasks may nonetheless have already started by
751  * virtue of the call to this function, but subsequent ones will not.
752  * @exception Cgu::Thread::TaskError This exception will be thrown if
753  * stop_all() has previously been called on the Thread::TaskManager
754  * object, or if another thread calls stop_all() after this method is
755  * called but before it has returned. It will also be thrown if the
756  * Thread::TaskManager object's is_error() method would return true
757  * because its internal thread pool loop implementation has thrown
758  * std::bad_alloc, or a thread has failed to start correctly because
759  * pthread has run out of resources. (On systems with
760  * over-commit/lazy-commit combined with virtual memory (swap), it is
761  * rarely useful to check for memory exhaustion, and if a reasonable
762  * maximum thread count has been chosen for the Thread::TaskManager
763  * object pthread should not run out of other resources, but there may
764  * be some specialized cases where the return value of is_error() is
765  * useful.) If this exception is thrown, some tasks may nonetheless
766  * have already started by virtue of the call to this function.
767  * @exception Cgu::Thread::ParallelError This exception will be thrown
768  * if an exception propagates from the 'func' callable object when it
769  * executes on being applied to one or more elements of the container.
770  * Such an exception will not stop an attempt being made to apply
771  * 'func' (successfully or unsuccessfully) to all elements in the
772  * range ['first', 'last') subject to the maximum.
773  * Cgu::Thread::ParallelError will be thrown after such attempted
774  * application has finished.
775  * @exception Cgu::Thread::MutexError This exception will be thrown if
776  * initialization of a mutex used by this function fails. (It is
777  * often not worth checking for this, as it means either memory is
778  * exhausted or pthread has run out of other resources to create new
779  * mutexes.) If this exception is thrown, no tasks will start.
780  * @exception Cgu::Thread::CondError This exception will be thrown if
781  * initialization of a condition variable used by this function fails.
782  * (It is often not worth checking for this, as it means either memory
783  * is exhausted or pthread has run out of other resources to create
784  * new condition variables.) If this exception is thrown, no tasks
785  * will start.
786  * @note An exception might also be thrown if the copy or move
787  * constructor of the 'func' callable objects throws. If such an
788  * exception is thrown, no tasks will start.
789  *
790  * Since 2.0.20/2.2.3
791  */
792 template <class Iterator, class Func>
794  Iterator first,
795  Iterator last,
796  int max,
797  Func&& func) {
798 
799  if (first == last || !max) return first;
800 
801  typedef typename std::iterator_traits<Iterator>::value_type ArgType;
802  typedef typename std::iterator_traits<Iterator>::difference_type DiffType;
803 
804  Mutex mutex;
805  Cond cond;
806  DiffType start_count = 0;
807  DiffType done_count = 0;
808  bool error = false;
809 
810  // a specialization of std::numeric_limits::max() for all arithmetic
811  // types is required by §3.9.1/8 of the standard. The iterator
812  // difference type must be a signed integer type (§24.2.1/1). All
813  // signed integer types are arithmetic types (§3.9.1/2, §3.9.1/7 and
814  // §3.9.1/8).
815  const DiffType local_max =
816  (max >= 0) ? max : std::numeric_limits<DiffType>::max();
817 
818  // construct SafeFunctorArg objects so that they can be shared
819  // between different tasks
821  Cgu::Callback::lambda<ArgType&>(std::forward<Func>(func))
822  };
824  Cgu::Callback::make(&ParallelHelper2::fail_func<DiffType>,
825  &mutex,
826  &cond,
827  &error,
828  &done_count)
829  };
830 
831  for (; first != last && start_count < local_max; ++first, ++start_count) {
832  std::unique_ptr<const Cgu::Callback::Callback> task_cb(
833  Cgu::Callback::make_ref(&ParallelHelper2::for_each_cb_func<ArgType, DiffType, Iterator>,
834  s_task,
835  first,
836  &mutex,
837  &cond,
838  &done_count)
839  );
840  std::unique_ptr<const Cgu::Callback::Callback> fail_cb(
841  Cgu::Callback::lambda<>([s_fail] () {s_fail();})
842  );
843 
844  tm.add_task(std::move(task_cb), std::move(fail_cb));
845  }
846 
847  Mutex::Lock l{mutex};
848  while (start_count > done_count) cond.wait(mutex);
849  if (error) throw ParallelError();
850  return first;
851 }
852 
853 /**
854  * \#include <c++-gtk-utils/parallel.h>
855  *
856  * This function maps over a container in the range ['first', 'last')
857  * subject to a maximum, applying a unary callable object to each
858  * element of the container in that range (subject to the maximum) and
859  * storing the result in the destination range, by executing each such
860  * application as a task of a Thread::TaskManager object. Tasks are
861  * added to the Thread::TaskManager object in the order in which the
862  * respective elements appear in the source container, and the final
863  * result appears in the destination container in the same order as
864  * the source range from which it is generated (including if a
865  * back_inserter iterator is used), but no other ordering arises, and
866  * the tasks will execute in parallel to the extent that the
867  * Thread::TaskManager object has sufficient threads available to do
868  * so.
869  *
870  * A separate overload of this function takes a binary callable
871  * object.
872  *
873  * This function does the same as the version of
874  * Thread::parallel_transform() taking a unary callable object, except
875  * that it returns a std::pair object containing an iterator to the
876  * element past the last element of the source range transformed, and
877  * a destination iterator to the element past the last element stored
878  * in the destination range, and it has a 'max' parameter to limit the
879  * maximum number of elements which will be so transformed on any one
880  * call to this function. Whether this limitation has had effect on
881  * any one call can be tested by checking whether the first value of
882  * the pair returned is equal to the 'last' parameter. If it is not,
883  * a further call to this function can be made.
884  *
885  * The main purpose of this additional function is to enable the
886  * parallel transform of the elements of a container to be dealt with
887  * in chunks, possibly to enable other tasks to be interleaved at
888  * reasonable intervals. For source or destination containers which
889  * do not support random access iterators, the 'last' parameter can be
890  * set to, say, the end of the container and the chunk size set with
891  * the 'max' paramater, with the values of the returned pair being
892  * used as the 'first' and 'dest' parameters for subsequent calls to
893  * this function. This avoids having to increment the source and
894  * destination iterators for each "chunk" by stepping through the
895  * respective containers by hand. In this usage, it therefore
896  * represents a minor efficiency improvement.
897  *
898  * @param tm The Thread::TaskManager object on which the tasks will
899  * run.
900  * @param first The beginning of the range to which 'func' is to be
901  * applied.
902  * @param last One past the last element to which 'func' is to be
903  * applied, subject to any maximum specified as the 'max' parameter.
904  * @param dest The beginning of the range to which the result of
905  * applying 'func' to the elements in the source range is to be
906  * stored. As in the case of std::transform, this can overlap with or
907  * be the same as the source range. It may also be an insert
908  * iterator.
909  * @param max The maximum number of elements of the source container
910  * which will be transformed on this call. It is not an error if it
911  * is greater than the distance between 'first' and 'last'. If it is
912  * equal to or greater than that distance, it follows that the first
913  * value of the pair returned by this function will be equal to
914  * 'last'. The same results if 'max' is a negative number (in that
915  * case no maximum will take effect and all elements in the range
916  * ['first', 'last') will be transformed), so passing -1 might be
917  * useful as a means of obtaining a destination iterator (the second
918  * value) for other purposes, particularly where it is not a random
919  * access iterator).
920  * @param func A unary callable object to be applied (subject to the
921  * maximum) to each element in the range ['first', 'last'), such as
922  * formed by a lambda expression or the result of std::bind. It
923  * should take a single unbound argument of the value type of the
924  * container to which 'first' and 'last' relate or a const or
925  * non-const reference to that type. If an exception propagates from
926  * 'func', the exception will be consumed while the transform loop is
927  * running, and an attempt will still be made to apply 'func' to all
928  * remaining elements in the range ['first', 'last') subject to the
929  * maximum, and only after that attempt has completed will the
930  * exception Cgu::Thread::ParallelError be thrown.
931  * @return A std::pair object. Its first member is an iterator
932  * representing the element past the last element of the source range
933  * transformed, which may be passed as the 'first' argument of a
934  * subsequent call to this function; and its second member is an
935  * iterator representing the element past the last element stored in
936  * the destination range, which may be passed as the 'dest' argument
937  * of the subsequent call.
938  * @exception std::bad_alloc This exception will be thrown if memory
939  * is exhausted and the system throws in that case. (On systems with
940  * over-commit/lazy-commit combined with virtual memory (swap), it is
941  * rarely useful to check for memory exhaustion). If this exception
942  * is thrown, some tasks may nonetheless have already started by
943  * virtue of the call to this function, but subsequent ones will not.
944  * @exception Cgu::Thread::TaskError This exception will be thrown if
945  * stop_all() has previously been called on the Thread::TaskManager
946  * object, or if another thread calls stop_all() after this method is
947  * called but before it has returned. It will also be thrown if the
948  * Thread::TaskManager object's is_error() method would return true
949  * because its internal thread pool loop implementation has thrown
950  * std::bad_alloc, or a thread has failed to start correctly because
951  * pthread has run out of resources. (On systems with
952  * over-commit/lazy-commit combined with virtual memory (swap), it is
953  * rarely useful to check for memory exhaustion, and if a reasonable
954  * maximum thread count has been chosen for the Thread::TaskManager
955  * object pthread should not run out of other resources, but there may
956  * be some specialized cases where the return value of is_error() is
957  * useful.) If this exception is thrown, some tasks may nonetheless
958  * have already started by virtue of the call to this function.
959  * @exception Cgu::Thread::ParallelError This exception will be thrown
960  * if an exception propagates from the 'func' callable object when it
961  * executes on being applied to one or more elements of the source
962  * container. Such an exception will not stop an attempt being made
963  * to apply 'func' (successfully or unsuccessfully) to all elements in
964  * the range ['first', 'last') subject to the maximum.
965  * Cgu::Thread::ParallelError will be thrown after such attempted
966  * application has finished.
967  * @exception Cgu::Thread::MutexError This exception will be thrown if
968  * initialization of a mutex used by this function fails. (It is
969  * often not worth checking for this, as it means either memory is
970  * exhausted or pthread has run out of other resources to create new
971  * mutexes.) If this exception is thrown, no tasks will start.
972  * @exception Cgu::Thread::CondError This exception will be thrown if
973  * initialization of a condition variable used by this function fails.
974  * (It is often not worth checking for this, as it means either memory
975  * is exhausted or pthread has run out of other resources to create
976  * new condition variables.) If this exception is thrown, no tasks
977  * will start.
978  * @note An exception might also be thrown if the copy or move
979  * constructor of the 'func' callable objects throws. If such an
980  * exception is thrown, no tasks will start.
981  *
982  * Since 2.0.20/2.2.3
983  */
984 template <class SourceIterator, class DestIterator, class Func>
985 std::pair<SourceIterator, DestIterator>
987  SourceIterator first,
988  SourceIterator last,
989  DestIterator dest,
990  int max,
991  Func&& func) {
992 
993  if (first == last || !max) return {first, dest};
994 
995  typedef typename std::iterator_traits<SourceIterator>::value_type ArgType;
996  typedef typename std::iterator_traits<SourceIterator>::difference_type DiffType;
997  typedef typename std::remove_const<typename std::remove_reference<Func>::type>::type FType;
998  typedef decltype(func(*first)) DestType;
999 
1000  Mutex mutex;
1001  Cond cond;
1002  DiffType start_count = 0;
1003  DiffType done_count = 0;
1004  bool error = false;
1005 
1006  // a specialization of std::numeric_limits::max() for all arithmetic
1007  // types is required by §3.9.1/8 of the standard. The iterator
1008  // difference type must be a signed integer type (§24.2.1/1). All
1009  // signed integer types are arithmetic types (§3.9.1/2, §3.9.1/7 and
1010  // §3.9.1/8).
1011  const DiffType local_max =
1012  (max >= 0) ? max : std::numeric_limits<DiffType>::max();
1013 
1014  // intermediate results have to be held in an array so destination
1015  // ordering can be enforced when using insert interators. This
1016  // causes some inefficiency for non-random access iterators
1017  std::unique_ptr<DestType[]> results(new DestType[std::min(local_max,
1018  std::distance(first, last))]);
1019 
1020  // construct SafeFunctorArg objects so that they can be shared
1021  // between different tasks
1023  Cgu::Callback::make_ref(&ParallelHelper2::transform1_func<FType, ArgType, DestType>,
1024  std::forward<Func>(func))
1025  };
1027  Cgu::Callback::make(&ParallelHelper2::fail_func<DiffType>,
1028  &mutex,
1029  &cond,
1030  &error,
1031  &done_count)
1032  };
1033 
1034  for (; first != last && start_count < local_max; ++first, ++start_count) {
1035  std::unique_ptr<const Cgu::Callback::Callback> task_cb(
1036  Cgu::Callback::lambda<>(std::bind(&ParallelHelper2::transform1_cb_func<ArgType, DestType, DiffType, SourceIterator>,
1037  s_task,
1038  first,
1039  &mutex,
1040  &cond,
1041  &done_count,
1042  results.get(),
1043  start_count))
1044  );
1045  std::unique_ptr<const Cgu::Callback::Callback> fail_cb(
1046  Cgu::Callback::lambda<>([s_fail] () {s_fail();})
1047  );
1048 
1049  tm.add_task(std::move(task_cb), std::move(fail_cb));
1050  }
1051 
1052  Mutex::Lock l{mutex};
1053  while (start_count > done_count) cond.wait(mutex);
1054  if (error) throw ParallelError();
1055  for (DiffType index = 0; index < start_count; ++dest, ++index) {
1056  *dest = std::move(results[index]);
1057  }
1058  return {first, dest};
1059 }
1060 
1061 /**
1062  * \#include <c++-gtk-utils/parallel.h>
1063  *
1064  * This function maps over two containers, one in the range ['first1',
1065  * 'last1') subject to a maximum, and the other beginning at 'first2',
1066  * applying a binary callable object to each element of the containers
1067  * in those ranges (subject to the maximum) and storing the result in
1068  * the destination range, by executing each such application as a task
1069  * of a Thread::TaskManager object. Tasks are added to the
1070  * Thread::TaskManager object in the order in which the respective
1071  * elements appear in the source containers, and the final result
1072  * appears in the destination container in the same order as the
1073  * source ranges from which it is generated (including if a
1074  * back_inserter iterator is used), but no other ordering arises, and
1075  * the tasks will execute in parallel to the extent that the
1076  * Thread::TaskManager object has sufficient threads available to do
1077  * so.
1078  *
1079  * A separate overload of this function takes a unary callable object.
1080  *
1081  * This function does the same as the version of
1082  * Thread::parallel_transform() taking a binary callable object,
1083  * except that it returns a std::tuple object containing iterators to
1084  * the element past the last elements of the source ranges
1085  * transformed, and a destination iterator to the element past the
1086  * last element stored in the destination range, and it has a 'max'
1087  * parameter to limit the maximum number of elements which will be so
1088  * transformed on any one call to this function. Whether this
1089  * limitation has had effect on any one call can be tested by checking
1090  * whether the first value of the tuple returned is equal to the
1091  * 'last' parameter. If it is not, a further call to this function
1092  * can be made.
1093  *
1094  * The main purpose of this additional function is to enable the
1095  * parallel transform of the elements of a container to be dealt with
1096  * in chunks, possibly to enable other tasks to be interleaved at
1097  * reasonable intervals. For source or destination containers which
1098  * do not support random access iterators, the 'last' parameter can be
1099  * set to, say, the end of the container and the chunk size set with
1100  * the 'max' paramater, with the values of the returned tuple being
1101  * used as the 'first1', 'first2' and 'dest' parameters for subsequent
1102  * calls to this function. This avoids having to increment the source
1103  * and destination iterators for each "chunk" by stepping through the
1104  * respective containers by hand. In this usage, it therefore
1105  * represents a minor efficiency improvement.
1106  *
1107  * @param tm The Thread::TaskManager object on which the tasks will
1108  * run.
1109  * @param first1 The beginning of the range which is to be passed as
1110  * the first argument of 'func'.
1111  * @param last1 One past the last element of the range which is to be
1112  * passed as the first argument of 'func', subject to any maximum
1113  * specified as the 'max' parameter.
1114  * @param first2 The beginning of the range which is to be passed as
1115  * the second argument of 'func'.
1116  * @param dest The beginning of the range to which the result of
1117  * applying 'func' to the elements in the source ranges is to be
1118  * stored. As in the case of std::transform, this can overlap with or
1119  * be the same as one of the source ranges. It may also be an insert
1120  * iterator.
1121  * @param max The maximum number of elements of the source containers
1122  * which will be transformed on this call. It is not an error if it
1123  * is greater than the distance between 'first1' and 'last1'. If it
1124  * is equal to or greater than that distance, it follows that the
1125  * first value of the tuple returned by this function will be equal to
1126  * 'last1'. The same results if 'max' is a negative number (in that
1127  * case no maximum will take effect and all elements in the range
1128  * ['first1', 'last1') will be transformed), so passing -1 might be
1129  * useful as a means of obtaining a second source iterator (the second
1130  * value of the tuple) or destination iterator (the third value) for
1131  * other purposes, particularly where they are not random access
1132  * iterators.
1133  * @param func A binary callable object to be applied (subject to the
1134  * maximum) to each element in the source ranges, such as formed by a
1135  * lambda expression or the result of std::bind. It should take two
1136  * unbound arguments of the value types of the containers to which
1137  * 'first1' and 'first2' relate or const or non-const references to
1138  * those types. If an exception propagates from 'func', the exception
1139  * will be consumed while the transform loop is running, and an
1140  * attempt will still be made to apply 'func' to all remaining
1141  * elements of the source ranges subject to the maximum, and only
1142  * after that attempt has completed will the exception
1143  * Cgu::Thread::ParallelError be thrown.
1144  * @return A std::tuple object. Its first value is an iterator
1145  * representing the element past the last element of the first source
1146  * range transformed, which may be passed as the 'first1' argument of
1147  * a subsequent call to this function; its second value is an iterator
1148  * representing the element past the last element of the second source
1149  * range transformed, which may be passed as the 'first2' argument of
1150  * the subsequent call; and its third value is an iterator
1151  * representing the element past the last element stored in the
1152  * destination range, which may be passed as the 'dest' argument of
1153  * the subsequent call.
1154  * @exception std::bad_alloc This exception will be thrown if memory
1155  * is exhausted and the system throws in that case. (On systems with
1156  * over-commit/lazy-commit combined with virtual memory (swap), it is
1157  * rarely useful to check for memory exhaustion). If this exception
1158  * is thrown, some tasks may nonetheless have already started by
1159  * virtue of the call to this function, but subsequent ones will not.
1160  * @exception Cgu::Thread::TaskError This exception will be thrown if
1161  * stop_all() has previously been called on the Thread::TaskManager
1162  * object, or if another thread calls stop_all() after this method is
1163  * called but before it has returned. It will also be thrown if the
1164  * Thread::TaskManager object's is_error() method would return true
1165  * because its internal thread pool loop implementation has thrown
1166  * std::bad_alloc, or a thread has failed to start correctly because
1167  * pthread has run out of resources. (On systems with
1168  * over-commit/lazy-commit combined with virtual memory (swap), it is
1169  * rarely useful to check for memory exhaustion, and if a reasonable
1170  * maximum thread count has been chosen for the Thread::TaskManager
1171  * object pthread should not run out of other resources, but there may
1172  * be some specialized cases where the return value of is_error() is
1173  * useful.) If this exception is thrown, some tasks may nonetheless
1174  * have already started by virtue of the call to this function.
1175  * @exception Cgu::Thread::ParallelError This exception will be thrown
1176  * if an exception propagates from the 'func' callable object when it
1177  * executes on being applied to one or more elements of the source
1178  * ranges. Such an exception will not stop an attempt being made to
1179  * apply 'func' (successfully or unsuccessfully) to all elements in
1180  * the source ranges subject to the maximum.
1181  * Cgu::Thread::ParallelError will be thrown after such attempted
1182  * application has finished.
1183  * @exception Cgu::Thread::MutexError This exception will be thrown if
1184  * initialization of a mutex used by this function fails. (It is
1185  * often not worth checking for this, as it means either memory is
1186  * exhausted or pthread has run out of other resources to create new
1187  * mutexes.) If this exception is thrown, no tasks will start.
1188  * @exception Cgu::Thread::CondError This exception will be thrown if
1189  * initialization of a condition variable used by this function fails.
1190  * (It is often not worth checking for this, as it means either memory
1191  * is exhausted or pthread has run out of other resources to create
1192  * new condition variables.) If this exception is thrown, no tasks
1193  * will start.
1194  * @note An exception might also be thrown if the copy or move
1195  * constructor of the 'func' callable objects throws. If such an
1196  * exception is thrown, no tasks will start.
1197  *
1198  * Since 2.0.20/2.2.3
1199  */
1200 template <class SourceIterator1, class SourceIterator2, class DestIterator, class Func>
1201 std::tuple<SourceIterator1, SourceIterator2, DestIterator>
1203  SourceIterator1 first1,
1204  SourceIterator1 last1,
1205  SourceIterator2 first2,
1206  DestIterator dest,
1207  int max,
1208  Func&& func) {
1209 
1210  if (first1 == last1 || !max) return std::make_tuple(first1, first2, dest);
1211 
1212  typedef typename std::iterator_traits<SourceIterator1>::value_type Arg1Type;
1213  typedef typename std::iterator_traits<SourceIterator1>::difference_type DiffType;
1214  typedef typename std::iterator_traits<SourceIterator2>::value_type Arg2Type;
1215  typedef typename std::remove_const<typename std::remove_reference<Func>::type>::type FType;
1216  typedef decltype(func(*first1, *first2)) DestType;
1217 
1218  Mutex mutex;
1219  Cond cond;
1220  DiffType start_count = 0;
1221  DiffType done_count = 0;
1222  bool error = false;
1223 
1224  // a specialization of std::numeric_limits::max() for all arithmetic
1225  // types is required by §3.9.1/8 of the standard. The iterator
1226  // difference type must be a signed integer type (§24.2.1/1). All
1227  // signed integer types are arithmetic types (§3.9.1/2, §3.9.1/7 and
1228  // §3.9.1/8).
1229  const DiffType local_max =
1230  (max >= 0) ? max : std::numeric_limits<DiffType>::max();
1231 
1232  // intermediate results have to be held in an array so destination
1233  // ordering can be enforced when using insert interators. This
1234  // causes some inefficiency for non-random access iterators
1235  std::unique_ptr<DestType[]> results(new DestType[std::min(local_max,
1236  std::distance(first1, last1))]);
1237 
1238  // construct SafeFunctorArg objects so that they can be shared
1239  // between different tasks
1241  Cgu::Callback::make_ref(&ParallelHelper2::transform2_func<FType, Arg1Type, Arg2Type, DestType>,
1242  std::forward<Func>(func))
1243  };
1245  Cgu::Callback::make(&ParallelHelper2::fail_func<DiffType>,
1246  &mutex,
1247  &cond,
1248  &error,
1249  &done_count)
1250  };
1251 
1252  for (; first1 != last1 && start_count < local_max; ++first1, ++first2, ++start_count) {
1253  std::unique_ptr<const Cgu::Callback::Callback> task_cb(
1254  Cgu::Callback::lambda<>(std::bind(&ParallelHelper2::transform2_cb_func<Arg1Type, Arg2Type, DestType, DiffType, SourceIterator1, SourceIterator2>,
1255  s_task,
1256  first1,
1257  first2,
1258  &mutex,
1259  &cond,
1260  &done_count,
1261  results.get(),
1262  start_count))
1263  );
1264  std::unique_ptr<const Cgu::Callback::Callback> fail_cb(
1265  Cgu::Callback::lambda<>([s_fail] () {s_fail();})
1266  );
1267 
1268  tm.add_task(std::move(task_cb), std::move(fail_cb));
1269  }
1270 
1271  Mutex::Lock l{mutex};
1272  while (start_count > done_count) cond.wait(mutex);
1273  if (error) throw ParallelError();
1274  for (DiffType index = 0; index < start_count; ++dest, ++index) {
1275  *dest = std::move(results[index]);
1276  }
1277  return std::make_tuple(first1, first2, dest);
1278 }
1279 
1280 } // namespace Thread
1281 
1282 } // namespace Cgu
1283 
1284 #endif // CGU_PARALLEL_H