c++-gtk-utils
parallel.h
Go to the documentation of this file.
1 /* Copyright (C) 2013 to 2015 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 ArgRefType, class DiffType, class Iterator>
75 void for_each_cb_func(const Cgu::Callback::SafeFunctorArg<ArgRefType>& 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 ArgRefType, class DestType>
86 void transform1_func(const FType& func,
87  ArgRefType arg,
88  DestType& res) {
89  res = func(arg);
90 }
91 
92 
93 template <class ArgRefType, class DestType, class DiffType, class SourceIterator>
94 void transform1_cb_func(const Cgu::Callback::SafeFunctorArg<ArgRefType, 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 Arg1RefType,
112  class Arg2RefType, class DestType>
113 void transform2_func(const FType& func,
114  Arg1RefType arg1,
115  Arg2RefType arg2,
116  DestType& res) {
117  res = func(arg1, arg2);
118 }
119 
120 
121 template <class Arg1RefType, class Arg2RefType, class DestType,
122  class DiffType, class SourceIterator1, class SourceIterator2>
123 void transform2_cb_func(const Cgu::Callback::SafeFunctorArg<Arg1RefType, Arg2RefType, 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  * @sa Cgu::IntIter
157  *
158  * This function applies a callable object to each element of a
159  * container in the range ['first', 'last'), by executing each such
160  * application as a task of a Thread::TaskManager object. Tasks are
161  * added to the Thread::TaskManager object in the order in which the
162  * respective elements appear in the container (and if a task mutates
163  * its argument, it will do so in respect of the correct element of
164  * the container), but no other ordering arises, and the tasks will
165  * execute in parallel to the extent that the Thread::TaskManager
166  * object has sufficient threads available to do so.
167  *
168  * Apart from that, and that this function returns void, it does the
169  * same as std::for_each(). It can mutate container elements if the
170  * callable object takes its argument by non-const reference. It will
171  * not return until the callable object has been applied to all of the
172  * elements in the range ['first', 'last').
173  *
174  * This function can be called by a task running on the same
175  * TaskManager object. However if that is done, as the task would end
176  * up blocking on its sub-tasks, the maximum number of threads running
177  * on the TaskManager object should be incremented by one temporarily
178  * while this function is executing using the TaskManager::IncHandle
179  * scoped handle class in order to prevent any deadlock through thread
180  * starvation. (Another approach where a result is to be delivered to
181  * a glib main loop is to call this function in a task running on a
182  * Cgu::Thread::Future object and to set a 'when' callback on the
183  * future object which passes the result to the main loop.)
184  *
185  * @param tm The Thread::TaskManager object on which the tasks will
186  * run.
187  * @param first The beginning of the range to which 'func' is to be
188  * applied.
189  * @param last One past the last element to which 'func' is to be
190  * applied.
191  * @param func A callable object to be applied to each element in the
192  * range ['first', 'last'), such as formed by a lambda expression or
193  * the result of std::bind. It should take a single unbound argument
194  * of the value type of the container to which 'first' and 'last'
195  * relate or a const or non-const reference to that type. Any return
196  * value is discarded. If an exception propagates from 'func', the
197  * exception will be consumed while the for each loop is running, and
198  * an attempt will still be made to apply 'func' to all remaining
199  * elements in the range ['first', 'last'), and only after that
200  * attempt has completed will the exception Cgu::Thread::ParallelError
201  * be thrown.
202  * @exception std::bad_alloc This exception will be thrown if memory
203  * is exhausted and the system throws in that case. (On systems with
204  * over-commit/lazy-commit combined with virtual memory (swap), it is
205  * rarely useful to check for memory exhaustion). If this exception
206  * is thrown, some tasks may nonetheless have already started by
207  * virtue of the call to this function, but subsequent ones will not.
208  * @exception Cgu::Thread::TaskError This exception will be thrown if
209  * stop_all() has previously been called on the Thread::TaskManager
210  * object, or if another thread calls stop_all() after this method is
211  * called but before it has returned. It will also be thrown if the
212  * Thread::TaskManager object's is_error() method would return true
213  * because its internal thread pool loop implementation has thrown
214  * std::bad_alloc, or a thread has failed to start correctly because
215  * pthread has run out of resources. (On systems with
216  * over-commit/lazy-commit combined with virtual memory (swap), it is
217  * rarely useful to check for memory exhaustion, and if a reasonable
218  * maximum thread count has been chosen for the Thread::TaskManager
219  * object pthread should not run out of other resources, but there may
220  * be some specialized cases where the return value of is_error() is
221  * useful.) If this exception is thrown, some tasks may nonetheless
222  * have already started by virtue of the call to this function.
223  * @exception Cgu::Thread::ParallelError This exception will be thrown
224  * if an exception propagates from the 'func' callable object when it
225  * executes on being applied to one or more elements of the container.
226  * Such an exception will not stop an attempt being made to apply
227  * 'func' (successfully or unsuccessfully) to all elements in the
228  * range ['first', 'last'). Cgu::Thread::ParallelError will be thrown
229  * after such attempted application has finished.
230  * @exception Cgu::Thread::MutexError This exception will be thrown if
231  * initialization of a mutex used by this function fails. (It is
232  * often not worth checking for this, as it means either memory is
233  * exhausted or pthread has run out of other resources to create new
234  * mutexes.) If this exception is thrown, no tasks will start.
235  * @exception Cgu::Thread::CondError This exception will be thrown if
236  * initialization of a condition variable used by this function fails.
237  * (It is often not worth checking for this, as it means either memory
238  * is exhausted or pthread has run out of other resources to create
239  * new condition variables.) If this exception is thrown, no tasks
240  * will start.
241  * @note 1. An exception might also be thrown if the copy or move
242  * constructor of the 'func' callable objects throws. If such an
243  * exception is thrown, no tasks will start.
244  * @note 2. Prior to version 2.0.27 and 2.2.10, this function could
245  * not take a source iterator to const. This was fixed in versions
246  * 2.0.27 and 2.2.10.
247  *
248  * Since 2.0.19/2.2.2
249  */
250 template <class Iterator, class Func>
252  Iterator first,
253  Iterator last,
254  Func&& func) {
255 
256  typedef typename std::iterator_traits<Iterator>::reference ArgRefType;
257  typedef typename std::iterator_traits<Iterator>::difference_type DiffType;
258 
259  Mutex mutex;
260  Cond cond;
261  DiffType start_count = 0;
262  DiffType done_count = 0;
263  bool error = false;
264 
265  // construct SafeFunctorArg objects so that they can be shared
266  // between different tasks
268  Cgu::Callback::lambda<ArgRefType>(std::forward<Func>(func))
269  };
271  Cgu::Callback::make(&ParallelHelper2::fail_func<DiffType>,
272  &mutex,
273  &cond,
274  &error,
275  &done_count)
276  };
277 
278  for (; first != last; ++first, ++start_count) {
279  std::unique_ptr<const Cgu::Callback::Callback> task_cb(
280  Cgu::Callback::make_ref(&ParallelHelper2::for_each_cb_func<ArgRefType, DiffType, Iterator>,
281  s_task,
282  first,
283  &mutex,
284  &cond,
285  &done_count)
286  );
287  std::unique_ptr<const Cgu::Callback::Callback> fail_cb(
288  Cgu::Callback::lambda<>([s_fail] () {s_fail();})
289  );
290 
291  tm.add_task(std::move(task_cb), std::move(fail_cb));
292  }
293 
294  Mutex::Lock l{mutex};
295  while (start_count > done_count) cond.wait(mutex);
296  if (error) throw ParallelError();
297 }
298 
299 /**
300  * \#include <c++-gtk-utils/parallel.h>
301  * @sa Cgu::IntIter
302  *
303  * This function maps over a container in the range ['first', 'last'),
304  * applying a unary callable object to each element of the container
305  * in that range and storing the result in the destination range, by
306  * executing each such application as a task of a Thread::TaskManager
307  * object. Tasks are added to the Thread::TaskManager object in the
308  * order in which the respective elements appear in the source
309  * container, and the final result appears in the destination
310  * container in the same order as the source range from which it is
311  * generated (including if a back_inserter iterator is used), but no
312  * other ordering arises, and the tasks will execute in parallel to
313  * the extent that the Thread::TaskManager object has sufficient
314  * threads available to do so.
315  *
316  * Apart from that, this function does the same as the version of
317  * std::transform() taking a unary function, except that it returns
318  * void (see Thread::parallel_transform_partial() for a function which
319  * returns a destination iterator and an iterator to the source
320  * range). It will not return until the callable object has been
321  * applied to all of the elements in the range ['first', 'last').
322  *
323  * This function can be called by a task running on the same
324  * TaskManager object, perhaps with a view to delivering a result
325  * asynchronously to a glib main loop. However if that is done, as
326  * the task would end up blocking on its sub-tasks, the maximum number
327  * of threads running on the TaskManager object should be incremented
328  * by one temporarily while this function is executing using the
329  * TaskManager::IncHandle scoped handle class in order to prevent any
330  * deadlock through thread starvation. (Another approach where a
331  * result is to be delivered to a glib main loop is to call this
332  * function in a task running on a Cgu::Thread::Future object and to
333  * set a 'when' callback on the future object which passes the result
334  * to the main loop.)
335  *
336  * A task can carry out a map-reduce operation by passing the result
337  * of calling this function to std::accumulate() to perform a
338  * fold-left or fold-right on that result.
339  *
340  * A separate overload of this function takes a binary callable
341  * object.
342  *
343  * Here is a trivial example of a map-reduce operation which maps over
344  * a vector by multiplying each element by 2 in separate tasks, and
345  * then folds-left using std::accumulate() (std::accumulate() can fold
346  * using any callable object, but in this example the default of
347  * addition is used):
348  *
349  * @code
350  * using namespace Cgu;
351  * std::vector<int> v{1, 2, 3, 4, 5};
352  * Thread::TaskManager tm;
353  *
354  * Thread::parallel_transform(tm,
355  * v.begin(),
356  * v.end(),
357  * v.begin(),
358  * [] (int elt) {return elt * 2;});
359  * // res will be equal to 30
360  * int res = std::accumulate(v.begin(), v.end(), 0);
361  * @endcode
362  *
363  * @param tm The Thread::TaskManager object on which the tasks will
364  * run.
365  * @param first The beginning of the range to which 'func' is to be
366  * applied.
367  * @param last One past the last element to which 'func' is to be
368  * applied.
369  * @param dest The beginning of the range to which the result of
370  * applying 'func' to the elements in the range ['first', 'last') is
371  * to be stored. As in the case of std::transform, this can overlap
372  * with or be the same as the source range. It may also be an insert
373  * iterator.
374  * @param func A unary callable object to be applied to each element
375  * in the range ['first', 'last'), such as formed by a lambda
376  * expression or the result of std::bind. It should take a single
377  * unbound argument of the value type of the container to which
378  * 'first' and 'last' relate or a const or non-const reference to that
379  * type. If an exception propagates from 'func', the exception will
380  * be consumed while the transform loop is running, and an attempt
381  * will still be made to apply 'func' to all remaining elements in the
382  * range ['first', 'last'), and only after that attempt has completed
383  * will the exception Cgu::Thread::ParallelError be thrown.
384  * @exception std::bad_alloc This exception will be thrown if memory
385  * is exhausted and the system throws in that case. (On systems with
386  * over-commit/lazy-commit combined with virtual memory (swap), it is
387  * rarely useful to check for memory exhaustion). If this exception
388  * is thrown, some tasks may nonetheless have already started by
389  * virtue of the call to this function, but subsequent ones will not.
390  * @exception Cgu::Thread::TaskError This exception will be thrown if
391  * stop_all() has previously been called on the Thread::TaskManager
392  * object, or if another thread calls stop_all() after this method is
393  * called but before it has returned. It will also be thrown if the
394  * Thread::TaskManager object's is_error() method would return true
395  * because its internal thread pool loop implementation has thrown
396  * std::bad_alloc, or a thread has failed to start correctly because
397  * pthread has run out of resources. (On systems with
398  * over-commit/lazy-commit combined with virtual memory (swap), it is
399  * rarely useful to check for memory exhaustion, and if a reasonable
400  * maximum thread count has been chosen for the Thread::TaskManager
401  * object pthread should not run out of other resources, but there may
402  * be some specialized cases where the return value of is_error() is
403  * useful.) If this exception is thrown, some tasks may nonetheless
404  * have already started by virtue of the call to this function.
405  * @exception Cgu::Thread::ParallelError This exception will be thrown
406  * if an exception propagates from the 'func' callable object when it
407  * executes on being applied to one or more elements of the source
408  * container. Such an exception will not stop an attempt being made
409  * to apply 'func' (successfully or unsuccessfully) to all elements in
410  * the range ['first', 'last'). Cgu::Thread::ParallelError will be
411  * thrown after such attempted application has finished.
412  * @exception Cgu::Thread::MutexError This exception will be thrown if
413  * initialization of a mutex used by this function fails. (It is
414  * often not worth checking for this, as it means either memory is
415  * exhausted or pthread has run out of other resources to create new
416  * mutexes.) If this exception is thrown, no tasks will start.
417  * @exception Cgu::Thread::CondError This exception will be thrown if
418  * initialization of a condition variable used by this function fails.
419  * (It is often not worth checking for this, as it means either memory
420  * is exhausted or pthread has run out of other resources to create
421  * new condition variables.) If this exception is thrown, no tasks
422  * will start.
423  * @note 1. An exception might also be thrown if the copy or move
424  * constructor of the 'func' callable objects throws. If such an
425  * exception is thrown, no tasks will start.
426  * @note 2. Prior to version 2.0.27 and 2.2.10, this function could
427  * not take a source iterator to const. This was fixed in versions
428  * 2.0.27 and 2.2.10.
429  *
430  * Since 2.0.19/2.2.2
431  */
432 template <class SourceIterator, class DestIterator, class Func>
434  SourceIterator first,
435  SourceIterator last,
436  DestIterator dest,
437  Func&& func) {
438 
439  if (first == last) return;
440 
441  typedef typename std::iterator_traits<SourceIterator>::reference ArgRefType;
442  typedef typename std::iterator_traits<SourceIterator>::difference_type DiffType;
443  typedef typename std::remove_const<typename std::remove_reference<Func>::type>::type FType;
444  // this function will fail to compile if DestType is a reference
445  // type: that is a feature, not a bug, as a function returning a
446  // reference lacks referential transparency, is unlikely to be
447  // thread-safe and is unsuitable for use as a task function
448  typedef decltype(func(*first)) DestType;
449 
450  Mutex mutex;
451  Cond cond;
452  DiffType start_count = 0;
453  DiffType done_count = 0;
454  bool error = false;
455 
456  // intermediate results have to be held in an array so destination
457  // ordering can be enforced when using insert interators. This
458  // causes some inefficiency for non-random access iterators
459  std::unique_ptr<DestType[]> results(new DestType[std::distance(first, last)]);
460 
461  // construct SafeFunctorArg objects so that they can be shared
462  // between different tasks
464  Cgu::Callback::make_ref(&ParallelHelper2::transform1_func<FType, ArgRefType, DestType>,
465  std::forward<Func>(func))
466  };
468  Cgu::Callback::make(&ParallelHelper2::fail_func<DiffType>,
469  &mutex,
470  &cond,
471  &error,
472  &done_count)
473  };
474 
475  for (; first != last; ++first, ++start_count) {
476  std::unique_ptr<const Cgu::Callback::Callback> task_cb(
477  Cgu::Callback::lambda<>(std::bind(&ParallelHelper2::transform1_cb_func<ArgRefType, DestType, DiffType, SourceIterator>,
478  s_task,
479  first,
480  &mutex,
481  &cond,
482  &done_count,
483  results.get(),
484  start_count))
485  );
486  std::unique_ptr<const Cgu::Callback::Callback> fail_cb(
487  Cgu::Callback::lambda<>([s_fail] () {s_fail();})
488  );
489 
490  tm.add_task(std::move(task_cb), std::move(fail_cb));
491  }
492 
493  Mutex::Lock l{mutex};
494  while (start_count > done_count) cond.wait(mutex);
495  if (error) throw ParallelError();
496  for (DiffType index = 0; index < start_count; ++dest, ++index) {
497  *dest = std::move(results[index]);
498  }
499 }
500 
501 /**
502  * \#include <c++-gtk-utils/parallel.h>
503  * @sa Cgu::IntIter
504  *
505  * This function maps over two containers, one in the range ['first1',
506  * 'last1') and the other beginning at 'first2', applying a binary
507  * callable object to each element of the containers in those ranges
508  * and storing the result in the destination range, by executing each
509  * such application as a task of a Thread::TaskManager object. Tasks
510  * are added to the Thread::TaskManager object in the order in which
511  * the respective elements appear in the source containers, and the
512  * final result appears in the destination container in the same order
513  * as the source ranges from which it is generated (including if a
514  * back_inserter iterator is used), but no other ordering arises, and
515  * the tasks will execute in parallel to the extent that the
516  * Thread::TaskManager object has sufficient threads available to do
517  * so.
518  *
519  * Apart from that, this function does the same as the version of
520  * std::transform() taking a binary function, except that it returns
521  * void (see Thread::parallel_transform_partial() for a function which
522  * returns a destination iterator and iterators to the source ranges).
523  * It will not return until the callable object has been applied to
524  * all of the elements in the source ranges.
525  *
526  * This function can be called by a task running on the same
527  * TaskManager object, perhaps with a view to delivering a result
528  * asynchronously to a glib main loop. However if that is done, as
529  * the task would end up blocking on its sub-tasks, the maximum number
530  * of threads running on the TaskManager object should be incremented
531  * by one temporarily while this function is executing using the
532  * TaskManager::IncHandle scoped handle class in order to prevent any
533  * deadlock through thread starvation. (Another approach where a
534  * result is to be delivered to a glib main loop is to call this
535  * function in a task running on a Cgu::Thread::Future object and to
536  * set a 'when' callback on the future object which passes the result
537  * to the main loop.)
538  *
539  * A task can carry out a map-reduce operation by passing the result
540  * of calling this function to std::accumulate() to perform a
541  * fold-left or fold-right on that result.
542  *
543  * A separate overload of this function takes a unary callable object.
544  *
545  * Here is a trivial example of a map-reduce operation which maps over
546  * two vectors by adding respective elements of the vectors in
547  * separate tasks, and then folds-left using std::accumulate()
548  * (std::accumulate() can fold using any callable object, but in this
549  * example the default of addition is used):
550  *
551  * @code
552  * using namespace Cgu;
553  * std::vector<int> v1{2, 4, 6, 8, 10};
554  * std::vector<int> v2{10, 20, 30, 40, 50};
555  * std::vector<int> v3;
556  * Thread::TaskManager tm;
557  *
558  * Thread::parallel_transform(tm,
559  * v1.begin(),
560  * v1.end(),
561  * v2.begin(),
562  * std::back_inserter(v3),
563  * std::plus<int>());
564  * // res will be equal to 180
565  * int res = std::accumulate(v3.begin(), v3.end(), 0);
566  * @endcode
567  *
568  * @param tm The Thread::TaskManager object on which the tasks will
569  * run.
570  * @param first1 The beginning of the range which is to be passed as
571  * the first argument of 'func'.
572  * @param last1 One past the last element of the range which is to be
573  * passed as the first argument of 'func'.
574  * @param first2 The beginning of the range which is to be passed as
575  * the second argument of 'func'.
576  * @param dest The beginning of the range to which the result of
577  * applying 'func' to the elements in the source ranges is to be
578  * stored. As in the case of std::transform, this can overlap with or
579  * be the same as one of the source ranges. It may also be an insert
580  * iterator.
581  * @param func A binary callable object to be applied to each element
582  * in the source ranges, such as formed by a lambda expression or the
583  * result of std::bind. It should take two unbound arguments of the
584  * value types of the containers to which 'first1' and 'first2' relate
585  * or const or non-const references to those types. If an exception
586  * propagates from 'func', the exception will be consumed while the
587  * transform loop is running, and an attempt will still be made to
588  * apply 'func' to all remaining elements of the source ranges, and
589  * only after that attempt has completed will the exception
590  * Cgu::Thread::ParallelError be thrown.
591  * @exception std::bad_alloc This exception will be thrown if memory
592  * is exhausted and the system throws in that case. (On systems with
593  * over-commit/lazy-commit combined with virtual memory (swap), it is
594  * rarely useful to check for memory exhaustion). If this exception
595  * is thrown, some tasks may nonetheless have already started by
596  * virtue of the call to this function, but subsequent ones will not.
597  * @exception Cgu::Thread::TaskError This exception will be thrown if
598  * stop_all() has previously been called on the Thread::TaskManager
599  * object, or if another thread calls stop_all() after this method is
600  * called but before it has returned. It will also be thrown if the
601  * Thread::TaskManager object's is_error() method would return true
602  * because its internal thread pool loop implementation has thrown
603  * std::bad_alloc, or a thread has failed to start correctly because
604  * pthread has run out of resources. (On systems with
605  * over-commit/lazy-commit combined with virtual memory (swap), it is
606  * rarely useful to check for memory exhaustion, and if a reasonable
607  * maximum thread count has been chosen for the Thread::TaskManager
608  * object pthread should not run out of other resources, but there may
609  * be some specialized cases where the return value of is_error() is
610  * useful.) If this exception is thrown, some tasks may nonetheless
611  * have already started by virtue of the call to this function.
612  * @exception Cgu::Thread::ParallelError This exception will be thrown
613  * if an exception propagates from the 'func' callable object when it
614  * executes on being applied to one or more elements of the source
615  * ranges. Such an exception will not stop an attempt being made to
616  * apply 'func' (successfully or unsuccessfully) to all elements in
617  * the source ranges. Cgu::Thread::ParallelError will be thrown after
618  * such attempted application has finished.
619  * @exception Cgu::Thread::MutexError This exception will be thrown if
620  * initialization of a mutex used by this function fails. (It is
621  * often not worth checking for this, as it means either memory is
622  * exhausted or pthread has run out of other resources to create new
623  * mutexes.) If this exception is thrown, no tasks will start.
624  * @exception Cgu::Thread::CondError This exception will be thrown if
625  * initialization of a condition variable used by this function fails.
626  * (It is often not worth checking for this, as it means either memory
627  * is exhausted or pthread has run out of other resources to create
628  * new condition variables.) If this exception is thrown, no tasks
629  * will start.
630  * @note 1. An exception might also be thrown if the copy or move
631  * constructor of the 'func' callable objects throws. If such an
632  * exception is thrown, no tasks will start.
633  * @note 2. Prior to version 2.0.27 and 2.2.10, this function could
634  * not take a source iterator to const. This was fixed in versions
635  * 2.0.27 and 2.2.10.
636  *
637  * Since 2.0.19/2.2.2
638  */
639 template <class SourceIterator1, class SourceIterator2, class DestIterator, class Func>
641  SourceIterator1 first1,
642  SourceIterator1 last1,
643  SourceIterator2 first2,
644  DestIterator dest,
645  Func&& func) {
646 
647  if (first1 == last1) return;
648 
649  typedef typename std::iterator_traits<SourceIterator1>::reference Arg1RefType;
650  typedef typename std::iterator_traits<SourceIterator1>::difference_type DiffType;
651  typedef typename std::iterator_traits<SourceIterator2>::reference Arg2RefType;
652  typedef typename std::remove_const<typename std::remove_reference<Func>::type>::type FType;
653  // this function will fail to compile if DestType is a reference
654  // type: that is a feature, not a bug, as a function returning a
655  // reference lacks referential transparency, is unlikely to be
656  // thread-safe and is unsuitable for use as a task function
657  typedef decltype(func(*first1, *first2)) DestType;
658 
659  Mutex mutex;
660  Cond cond;
661  DiffType start_count = 0;
662  DiffType done_count = 0;
663  bool error = false;
664 
665  // intermediate results have to be held in an array so destination
666  // ordering can be enforced when using insert interators. This
667  // causes some inefficiency for non-random access iterators
668  std::unique_ptr<DestType[]> results(new DestType[std::distance(first1, last1)]);
669 
670  // construct SafeFunctorArg objects so that they can be shared
671  // between different tasks
673  Cgu::Callback::make_ref(&ParallelHelper2::transform2_func<FType, Arg1RefType, Arg2RefType, DestType>,
674  std::forward<Func>(func))
675  };
677  Cgu::Callback::make(&ParallelHelper2::fail_func<DiffType>,
678  &mutex,
679  &cond,
680  &error,
681  &done_count)
682  };
683 
684  for (; first1 != last1; ++first1, ++first2, ++start_count) {
685  std::unique_ptr<const Cgu::Callback::Callback> task_cb(
686  Cgu::Callback::lambda<>(std::bind(&ParallelHelper2::transform2_cb_func<Arg1RefType, Arg2RefType, DestType, DiffType, SourceIterator1, SourceIterator2>,
687  s_task,
688  first1,
689  first2,
690  &mutex,
691  &cond,
692  &done_count,
693  results.get(),
694  start_count))
695  );
696  std::unique_ptr<const Cgu::Callback::Callback> fail_cb(
697  Cgu::Callback::lambda<>([s_fail] () {s_fail();})
698  );
699 
700  tm.add_task(std::move(task_cb), std::move(fail_cb));
701  }
702 
703  Mutex::Lock l{mutex};
704  while (start_count > done_count) cond.wait(mutex);
705  if (error) throw ParallelError();
706  for (DiffType index = 0; index < start_count; ++dest, ++index) {
707  *dest = std::move(results[index]);
708  }
709 }
710 
711 /**
712  * \#include <c++-gtk-utils/parallel.h>
713  * @sa Cgu::IntIter
714  *
715  * This function applies a callable object to each element of a
716  * container in the range ['first', 'last') subject to a maximum, by
717  * executing each such application as a task of a Thread::TaskManager
718  * object. Tasks are added to the Thread::TaskManager object in the
719  * order in which the respective elements appear in the container (and
720  * if a task mutates its argument, it will do so in respect of the
721  * correct element of the container), but no other ordering arises,
722  * and the tasks will execute in parallel to the extent that the
723  * Thread::TaskManager object has sufficient threads available to do
724  * so.
725  *
726  * This function does the same as Thread::parallel_for_each(), except
727  * that it returns an iterator to the element past the last element to
728  * which the callable object has been applied, and it has a 'max'
729  * parameter to limit the maximum number of elements to which the
730  * callable object will be applied on any one call to this function
731  * even if the range ['first', 'last') is greater than this maximum.
732  * Whether this limitation has had effect on any one call can be
733  * tested by checking whether the return value is equal to the 'last'
734  * parameter. If it is not, a further call to this function can be
735  * made.
736  *
737  * The main purpose of this additional function is to enable the
738  * application of the callable object to the elements of a container
739  * to be dealt with in chunks, possibly to enable other tasks to be
740  * interleaved at reasonable intervals. For a container which does
741  * not support random access iterators, the 'last' parameter can be
742  * set to, say, the end of the container and the chunk size set with
743  * the 'max' paramater, with the return value being used as the
744  * 'first' parameter for subsequent calls to this function. This
745  * avoids having to increment the iterator for each "chunk" by
746  * stepping through the container by hand. In this usage, it
747  * therefore represents a minor efficiency improvement.
748  *
749  * @param tm The Thread::TaskManager object on which the tasks will
750  * run.
751  * @param first The beginning of the range to which 'func' is to be
752  * applied.
753  * @param last One past the last element to which 'func' is to be
754  * applied, subject to any maximum specified as the 'max' parameter.
755  * @param max The maximum number of elements of the source container
756  * to which 'func' will be applied on this call. It is not an error
757  * if it is greater than the distance between 'first' and 'last'. If
758  * it is equal to or greater than that distance, it follows that the
759  * iterator returned will be equal to 'last'. The same results if
760  * 'max' is a negative number (in that case no maximum will take
761  * effect and each element in the range ['first', 'last') will have
762  * 'func' applied to it).
763  * @param func A callable object to be applied (subject to the
764  * maximum) to each element in the range ['first', 'last'), such as
765  * formed by a lambda expression or the result of std::bind. It
766  * should take a single unbound argument of the value type of the
767  * container to which 'first' and 'last' relate or a const or
768  * non-const reference to that type. Any return value is discarded.
769  * If an exception propagates from 'func', the exception will be
770  * consumed while the for each loop is running, and an attempt will
771  * still be made to apply 'func' to all remaining elements in the
772  * range ['first', 'last') subject to the maximum, and only after that
773  * attempt has completed will the exception Cgu::Thread::ParallelError
774  * be thrown.
775  * @return An iterator representing the element past the last element
776  * of the range to which 'func' was applied, which may be passed as
777  * the 'first' argument of a subsequent call to this function.
778  * @exception std::bad_alloc This exception will be thrown if memory
779  * is exhausted and the system throws in that case. (On systems with
780  * over-commit/lazy-commit combined with virtual memory (swap), it is
781  * rarely useful to check for memory exhaustion). If this exception
782  * is thrown, some tasks may nonetheless have already started by
783  * virtue of the call to this function, but subsequent ones will not.
784  * @exception Cgu::Thread::TaskError This exception will be thrown if
785  * stop_all() has previously been called on the Thread::TaskManager
786  * object, or if another thread calls stop_all() after this method is
787  * called but before it has returned. It will also be thrown if the
788  * Thread::TaskManager object's is_error() method would return true
789  * because its internal thread pool loop implementation has thrown
790  * std::bad_alloc, or a thread has failed to start correctly because
791  * pthread has run out of resources. (On systems with
792  * over-commit/lazy-commit combined with virtual memory (swap), it is
793  * rarely useful to check for memory exhaustion, and if a reasonable
794  * maximum thread count has been chosen for the Thread::TaskManager
795  * object pthread should not run out of other resources, but there may
796  * be some specialized cases where the return value of is_error() is
797  * useful.) If this exception is thrown, some tasks may nonetheless
798  * have already started by virtue of the call to this function.
799  * @exception Cgu::Thread::ParallelError This exception will be thrown
800  * if an exception propagates from the 'func' callable object when it
801  * executes on being applied to one or more elements of the container.
802  * Such an exception will not stop an attempt being made to apply
803  * 'func' (successfully or unsuccessfully) to all elements in the
804  * range ['first', 'last') subject to the maximum.
805  * Cgu::Thread::ParallelError will be thrown after such attempted
806  * application has finished.
807  * @exception Cgu::Thread::MutexError This exception will be thrown if
808  * initialization of a mutex used by this function fails. (It is
809  * often not worth checking for this, as it means either memory is
810  * exhausted or pthread has run out of other resources to create new
811  * mutexes.) If this exception is thrown, no tasks will start.
812  * @exception Cgu::Thread::CondError This exception will be thrown if
813  * initialization of a condition variable used by this function fails.
814  * (It is often not worth checking for this, as it means either memory
815  * is exhausted or pthread has run out of other resources to create
816  * new condition variables.) If this exception is thrown, no tasks
817  * will start.
818  * @note 1. An exception might also be thrown if the copy or move
819  * constructor of the 'func' callable objects throws. If such an
820  * exception is thrown, no tasks will start.
821  * @note 2. Prior to version 2.0.27 and 2.2.10, this function could
822  * not take a source iterator to const. This was fixed in versions
823  * 2.0.27 and 2.2.10.
824  *
825  * Since 2.0.20/2.2.3
826  */
827 template <class Iterator, class Func>
829  Iterator first,
830  Iterator last,
831  int max,
832  Func&& func) {
833 
834  if (first == last || !max) return first;
835 
836  typedef typename std::iterator_traits<Iterator>::reference ArgRefType;
837  typedef typename std::iterator_traits<Iterator>::difference_type DiffType;
838 
839  Mutex mutex;
840  Cond cond;
841  DiffType start_count = 0;
842  DiffType done_count = 0;
843  bool error = false;
844 
845  // a specialization of std::numeric_limits::max() for all arithmetic
846  // types is required by §3.9.1/8 of the standard. The iterator
847  // difference type must be a signed integer type (§24.2.1/1). All
848  // signed integer types are arithmetic types (§3.9.1/2, §3.9.1/7 and
849  // §3.9.1/8).
850  const DiffType local_max =
851  (max >= 0) ? max : std::numeric_limits<DiffType>::max();
852 
853  // construct SafeFunctorArg objects so that they can be shared
854  // between different tasks
856  Cgu::Callback::lambda<ArgRefType>(std::forward<Func>(func))
857  };
859  Cgu::Callback::make(&ParallelHelper2::fail_func<DiffType>,
860  &mutex,
861  &cond,
862  &error,
863  &done_count)
864  };
865 
866  for (; first != last && start_count < local_max; ++first, ++start_count) {
867  std::unique_ptr<const Cgu::Callback::Callback> task_cb(
868  Cgu::Callback::make_ref(&ParallelHelper2::for_each_cb_func<ArgRefType, DiffType, Iterator>,
869  s_task,
870  first,
871  &mutex,
872  &cond,
873  &done_count)
874  );
875  std::unique_ptr<const Cgu::Callback::Callback> fail_cb(
876  Cgu::Callback::lambda<>([s_fail] () {s_fail();})
877  );
878 
879  tm.add_task(std::move(task_cb), std::move(fail_cb));
880  }
881 
882  Mutex::Lock l{mutex};
883  while (start_count > done_count) cond.wait(mutex);
884  if (error) throw ParallelError();
885  return first;
886 }
887 
888 /**
889  * \#include <c++-gtk-utils/parallel.h>
890  * @sa Cgu::IntIter
891  *
892  * This function maps over a container in the range ['first', 'last')
893  * subject to a maximum, applying a unary callable object to each
894  * element of the container in that range (subject to the maximum) and
895  * storing the result in the destination range, by executing each such
896  * application as a task of a Thread::TaskManager object. Tasks are
897  * added to the Thread::TaskManager object in the order in which the
898  * respective elements appear in the source container, and the final
899  * result appears in the destination container in the same order as
900  * the source range from which it is generated (including if a
901  * back_inserter iterator is used), but no other ordering arises, and
902  * the tasks will execute in parallel to the extent that the
903  * Thread::TaskManager object has sufficient threads available to do
904  * so.
905  *
906  * A separate overload of this function takes a binary callable
907  * object.
908  *
909  * This function does the same as the version of
910  * Thread::parallel_transform() taking a unary callable object, except
911  * that it returns a std::pair object containing an iterator to the
912  * element past the last element of the source range transformed, and
913  * a destination iterator to the element past the last element stored
914  * in the destination range, and it has a 'max' parameter to limit the
915  * maximum number of elements which will be so transformed on any one
916  * call to this function. Whether this limitation has had effect on
917  * any one call can be tested by checking whether the first value of
918  * the pair returned is equal to the 'last' parameter. If it is not,
919  * a further call to this function can be made.
920  *
921  * The main purpose of this additional function is to enable the
922  * parallel transform of the elements of a container to be dealt with
923  * in chunks, possibly to enable other tasks to be interleaved at
924  * reasonable intervals. For source or destination containers which
925  * do not support random access iterators, the 'last' parameter can be
926  * set to, say, the end of the container and the chunk size set with
927  * the 'max' paramater, with the values of the returned pair being
928  * used as the 'first' and 'dest' parameters for subsequent calls to
929  * this function. This avoids having to increment the source and
930  * destination iterators for each "chunk" by stepping through the
931  * respective containers by hand. In this usage, it therefore
932  * represents a minor efficiency improvement.
933  *
934  * @param tm The Thread::TaskManager object on which the tasks will
935  * run.
936  * @param first The beginning of the range to which 'func' is to be
937  * applied.
938  * @param last One past the last element to which 'func' is to be
939  * applied, subject to any maximum specified as the 'max' parameter.
940  * @param dest The beginning of the range to which the result of
941  * applying 'func' to the elements in the source range is to be
942  * stored. As in the case of std::transform, this can overlap with or
943  * be the same as the source range. It may also be an insert
944  * iterator.
945  * @param max The maximum number of elements of the source container
946  * which will be transformed on this call. It is not an error if it
947  * is greater than the distance between 'first' and 'last'. If it is
948  * equal to or greater than that distance, it follows that the first
949  * value of the pair returned by this function will be equal to
950  * 'last'. The same results if 'max' is a negative number (in that
951  * case no maximum will take effect and all elements in the range
952  * ['first', 'last') will be transformed), so passing -1 might be
953  * useful as a means of obtaining a destination iterator (the second
954  * value) for other purposes, particularly where it is not a random
955  * access iterator).
956  * @param func A unary callable object to be applied (subject to the
957  * maximum) to each element in the range ['first', 'last'), such as
958  * formed by a lambda expression or the result of std::bind. It
959  * should take a single unbound argument of the value type of the
960  * container to which 'first' and 'last' relate or a const or
961  * non-const reference to that type. If an exception propagates from
962  * 'func', the exception will be consumed while the transform loop is
963  * running, and an attempt will still be made to apply 'func' to all
964  * remaining elements in the range ['first', 'last') subject to the
965  * maximum, and only after that attempt has completed will the
966  * exception Cgu::Thread::ParallelError be thrown.
967  * @return A std::pair object. Its first member is an iterator
968  * representing the element past the last element of the source range
969  * transformed, which may be passed as the 'first' argument of a
970  * subsequent call to this function; and its second member is an
971  * iterator representing the element past the last element stored in
972  * the destination range, which may be passed as the 'dest' argument
973  * of the subsequent call.
974  * @exception std::bad_alloc This exception will be thrown if memory
975  * is exhausted and the system throws in that case. (On systems with
976  * over-commit/lazy-commit combined with virtual memory (swap), it is
977  * rarely useful to check for memory exhaustion). If this exception
978  * is thrown, some tasks may nonetheless have already started by
979  * virtue of the call to this function, but subsequent ones will not.
980  * @exception Cgu::Thread::TaskError This exception will be thrown if
981  * stop_all() has previously been called on the Thread::TaskManager
982  * object, or if another thread calls stop_all() after this method is
983  * called but before it has returned. It will also be thrown if the
984  * Thread::TaskManager object's is_error() method would return true
985  * because its internal thread pool loop implementation has thrown
986  * std::bad_alloc, or a thread has failed to start correctly because
987  * pthread has run out of resources. (On systems with
988  * over-commit/lazy-commit combined with virtual memory (swap), it is
989  * rarely useful to check for memory exhaustion, and if a reasonable
990  * maximum thread count has been chosen for the Thread::TaskManager
991  * object pthread should not run out of other resources, but there may
992  * be some specialized cases where the return value of is_error() is
993  * useful.) If this exception is thrown, some tasks may nonetheless
994  * have already started by virtue of the call to this function.
995  * @exception Cgu::Thread::ParallelError This exception will be thrown
996  * if an exception propagates from the 'func' callable object when it
997  * executes on being applied to one or more elements of the source
998  * container. Such an exception will not stop an attempt being made
999  * to apply 'func' (successfully or unsuccessfully) to all elements in
1000  * the range ['first', 'last') subject to the maximum.
1001  * Cgu::Thread::ParallelError will be thrown after such attempted
1002  * application has finished.
1003  * @exception Cgu::Thread::MutexError This exception will be thrown if
1004  * initialization of a mutex used by this function fails. (It is
1005  * often not worth checking for this, as it means either memory is
1006  * exhausted or pthread has run out of other resources to create new
1007  * mutexes.) If this exception is thrown, no tasks will start.
1008  * @exception Cgu::Thread::CondError This exception will be thrown if
1009  * initialization of a condition variable used by this function fails.
1010  * (It is often not worth checking for this, as it means either memory
1011  * is exhausted or pthread has run out of other resources to create
1012  * new condition variables.) If this exception is thrown, no tasks
1013  * will start.
1014  * @note 1. An exception might also be thrown if the copy or move
1015  * constructor of the 'func' callable objects throws. If such an
1016  * exception is thrown, no tasks will start.
1017  * @note 2. Prior to version 2.0.27 and 2.2.10, this function could
1018  * not take a source iterator to const. This was fixed in versions
1019  * 2.0.27 and 2.2.10.
1020  *
1021  * Since 2.0.20/2.2.3
1022  */
1023 template <class SourceIterator, class DestIterator, class Func>
1024 std::pair<SourceIterator, DestIterator>
1026  SourceIterator first,
1027  SourceIterator last,
1028  DestIterator dest,
1029  int max,
1030  Func&& func) {
1031 
1032  if (first == last || !max) return {first, dest};
1033 
1034  typedef typename std::iterator_traits<SourceIterator>::reference ArgRefType;
1035  typedef typename std::iterator_traits<SourceIterator>::difference_type DiffType;
1036  typedef typename std::remove_const<typename std::remove_reference<Func>::type>::type FType;
1037  // this function will fail to compile if DestType is a reference
1038  // type: that is a feature, not a bug, as a function returning a
1039  // reference lacks referential transparency, is unlikely to be
1040  // thread-safe and is unsuitable for use as a task function
1041  typedef decltype(func(*first)) DestType;
1042 
1043  Mutex mutex;
1044  Cond cond;
1045  DiffType start_count = 0;
1046  DiffType done_count = 0;
1047  bool error = false;
1048 
1049  // a specialization of std::numeric_limits::max() for all arithmetic
1050  // types is required by §3.9.1/8 of the standard. The iterator
1051  // difference type must be a signed integer type (§24.2.1/1). All
1052  // signed integer types are arithmetic types (§3.9.1/2, §3.9.1/7 and
1053  // §3.9.1/8).
1054  const DiffType local_max =
1055  (max >= 0) ? max : std::numeric_limits<DiffType>::max();
1056 
1057  // intermediate results have to be held in an array so destination
1058  // ordering can be enforced when using insert interators. This
1059  // causes some inefficiency for non-random access iterators
1060  std::unique_ptr<DestType[]> results(new DestType[std::min(local_max,
1061  std::distance(first, last))]);
1062 
1063  // construct SafeFunctorArg objects so that they can be shared
1064  // between different tasks
1066  Cgu::Callback::make_ref(&ParallelHelper2::transform1_func<FType, ArgRefType, DestType>,
1067  std::forward<Func>(func))
1068  };
1070  Cgu::Callback::make(&ParallelHelper2::fail_func<DiffType>,
1071  &mutex,
1072  &cond,
1073  &error,
1074  &done_count)
1075  };
1076 
1077  for (; first != last && start_count < local_max; ++first, ++start_count) {
1078  std::unique_ptr<const Cgu::Callback::Callback> task_cb(
1079  Cgu::Callback::lambda<>(std::bind(&ParallelHelper2::transform1_cb_func<ArgRefType, DestType, DiffType, SourceIterator>,
1080  s_task,
1081  first,
1082  &mutex,
1083  &cond,
1084  &done_count,
1085  results.get(),
1086  start_count))
1087  );
1088  std::unique_ptr<const Cgu::Callback::Callback> fail_cb(
1089  Cgu::Callback::lambda<>([s_fail] () {s_fail();})
1090  );
1091 
1092  tm.add_task(std::move(task_cb), std::move(fail_cb));
1093  }
1094 
1095  Mutex::Lock l{mutex};
1096  while (start_count > done_count) cond.wait(mutex);
1097  if (error) throw ParallelError();
1098  for (DiffType index = 0; index < start_count; ++dest, ++index) {
1099  *dest = std::move(results[index]);
1100  }
1101  return {first, dest};
1102 }
1103 
1104 /**
1105  * \#include <c++-gtk-utils/parallel.h>
1106  * @sa Cgu::IntIter
1107  *
1108  * This function maps over two containers, one in the range ['first1',
1109  * 'last1') subject to a maximum, and the other beginning at 'first2',
1110  * applying a binary callable object to each element of the containers
1111  * in those ranges (subject to the maximum) and storing the result in
1112  * the destination range, by executing each such application as a task
1113  * of a Thread::TaskManager object. Tasks are added to the
1114  * Thread::TaskManager object in the order in which the respective
1115  * elements appear in the source containers, and the final result
1116  * appears in the destination container in the same order as the
1117  * source ranges from which it is generated (including if a
1118  * back_inserter iterator is used), but no other ordering arises, and
1119  * the tasks will execute in parallel to the extent that the
1120  * Thread::TaskManager object has sufficient threads available to do
1121  * so.
1122  *
1123  * A separate overload of this function takes a unary callable object.
1124  *
1125  * This function does the same as the version of
1126  * Thread::parallel_transform() taking a binary callable object,
1127  * except that it returns a std::tuple object containing iterators to
1128  * the element past the last elements of the source ranges
1129  * transformed, and a destination iterator to the element past the
1130  * last element stored in the destination range, and it has a 'max'
1131  * parameter to limit the maximum number of elements which will be so
1132  * transformed on any one call to this function. Whether this
1133  * limitation has had effect on any one call can be tested by checking
1134  * whether the first value of the tuple returned is equal to the
1135  * 'last' parameter. If it is not, a further call to this function
1136  * can be made.
1137  *
1138  * The main purpose of this additional function is to enable the
1139  * parallel transform of the elements of a container to be dealt with
1140  * in chunks, possibly to enable other tasks to be interleaved at
1141  * reasonable intervals. For source or destination containers which
1142  * do not support random access iterators, the 'last' parameter can be
1143  * set to, say, the end of the container and the chunk size set with
1144  * the 'max' paramater, with the values of the returned tuple being
1145  * used as the 'first1', 'first2' and 'dest' parameters for subsequent
1146  * calls to this function. This avoids having to increment the source
1147  * and destination iterators for each "chunk" by stepping through the
1148  * respective containers by hand. In this usage, it therefore
1149  * represents a minor efficiency improvement.
1150  *
1151  * @param tm The Thread::TaskManager object on which the tasks will
1152  * run.
1153  * @param first1 The beginning of the range which is to be passed as
1154  * the first argument of 'func'.
1155  * @param last1 One past the last element of the range which is to be
1156  * passed as the first argument of 'func', subject to any maximum
1157  * specified as the 'max' parameter.
1158  * @param first2 The beginning of the range which is to be passed as
1159  * the second argument of 'func'.
1160  * @param dest The beginning of the range to which the result of
1161  * applying 'func' to the elements in the source ranges is to be
1162  * stored. As in the case of std::transform, this can overlap with or
1163  * be the same as one of the source ranges. It may also be an insert
1164  * iterator.
1165  * @param max The maximum number of elements of the source containers
1166  * which will be transformed on this call. It is not an error if it
1167  * is greater than the distance between 'first1' and 'last1'. If it
1168  * is equal to or greater than that distance, it follows that the
1169  * first value of the tuple returned by this function will be equal to
1170  * 'last1'. The same results if 'max' is a negative number (in that
1171  * case no maximum will take effect and all elements in the range
1172  * ['first1', 'last1') will be transformed), so passing -1 might be
1173  * useful as a means of obtaining a second source iterator (the second
1174  * value of the tuple) or destination iterator (the third value) for
1175  * other purposes, particularly where they are not random access
1176  * iterators.
1177  * @param func A binary callable object to be applied (subject to the
1178  * maximum) to each element in the source ranges, such as formed by a
1179  * lambda expression or the result of std::bind. It should take two
1180  * unbound arguments of the value types of the containers to which
1181  * 'first1' and 'first2' relate or const or non-const references to
1182  * those types. If an exception propagates from 'func', the exception
1183  * will be consumed while the transform loop is running, and an
1184  * attempt will still be made to apply 'func' to all remaining
1185  * elements of the source ranges subject to the maximum, and only
1186  * after that attempt has completed will the exception
1187  * Cgu::Thread::ParallelError be thrown.
1188  * @return A std::tuple object. Its first value is an iterator
1189  * representing the element past the last element of the first source
1190  * range transformed, which may be passed as the 'first1' argument of
1191  * a subsequent call to this function; its second value is an iterator
1192  * representing the element past the last element of the second source
1193  * range transformed, which may be passed as the 'first2' argument of
1194  * the subsequent call; and its third value is an iterator
1195  * representing the element past the last element stored in the
1196  * destination range, which may be passed as the 'dest' argument of
1197  * the subsequent call.
1198  * @exception std::bad_alloc This exception will be thrown if memory
1199  * is exhausted and the system throws in that case. (On systems with
1200  * over-commit/lazy-commit combined with virtual memory (swap), it is
1201  * rarely useful to check for memory exhaustion). If this exception
1202  * is thrown, some tasks may nonetheless have already started by
1203  * virtue of the call to this function, but subsequent ones will not.
1204  * @exception Cgu::Thread::TaskError This exception will be thrown if
1205  * stop_all() has previously been called on the Thread::TaskManager
1206  * object, or if another thread calls stop_all() after this method is
1207  * called but before it has returned. It will also be thrown if the
1208  * Thread::TaskManager object's is_error() method would return true
1209  * because its internal thread pool loop implementation has thrown
1210  * std::bad_alloc, or a thread has failed to start correctly because
1211  * pthread has run out of resources. (On systems with
1212  * over-commit/lazy-commit combined with virtual memory (swap), it is
1213  * rarely useful to check for memory exhaustion, and if a reasonable
1214  * maximum thread count has been chosen for the Thread::TaskManager
1215  * object pthread should not run out of other resources, but there may
1216  * be some specialized cases where the return value of is_error() is
1217  * useful.) If this exception is thrown, some tasks may nonetheless
1218  * have already started by virtue of the call to this function.
1219  * @exception Cgu::Thread::ParallelError This exception will be thrown
1220  * if an exception propagates from the 'func' callable object when it
1221  * executes on being applied to one or more elements of the source
1222  * ranges. Such an exception will not stop an attempt being made to
1223  * apply 'func' (successfully or unsuccessfully) to all elements in
1224  * the source ranges subject to the maximum.
1225  * Cgu::Thread::ParallelError will be thrown after such attempted
1226  * application has finished.
1227  * @exception Cgu::Thread::MutexError This exception will be thrown if
1228  * initialization of a mutex used by this function fails. (It is
1229  * often not worth checking for this, as it means either memory is
1230  * exhausted or pthread has run out of other resources to create new
1231  * mutexes.) If this exception is thrown, no tasks will start.
1232  * @exception Cgu::Thread::CondError This exception will be thrown if
1233  * initialization of a condition variable used by this function fails.
1234  * (It is often not worth checking for this, as it means either memory
1235  * is exhausted or pthread has run out of other resources to create
1236  * new condition variables.) If this exception is thrown, no tasks
1237  * will start.
1238  * @note 1. An exception might also be thrown if the copy or move
1239  * constructor of the 'func' callable objects throws. If such an
1240  * exception is thrown, no tasks will start.
1241  * @note 2. Prior to version 2.0.27 and 2.2.10, this function could
1242  * not take a source iterator to const. This was fixed in versions
1243  * 2.0.27 and 2.2.10.
1244  *
1245  * Since 2.0.20/2.2.3
1246  */
1247 template <class SourceIterator1, class SourceIterator2, class DestIterator, class Func>
1248 std::tuple<SourceIterator1, SourceIterator2, DestIterator>
1250  SourceIterator1 first1,
1251  SourceIterator1 last1,
1252  SourceIterator2 first2,
1253  DestIterator dest,
1254  int max,
1255  Func&& func) {
1256 
1257  if (first1 == last1 || !max) return std::make_tuple(first1, first2, dest);
1258 
1259  typedef typename std::iterator_traits<SourceIterator1>::reference Arg1RefType;
1260  typedef typename std::iterator_traits<SourceIterator1>::difference_type DiffType;
1261  typedef typename std::iterator_traits<SourceIterator2>::reference Arg2RefType;
1262  typedef typename std::remove_const<typename std::remove_reference<Func>::type>::type FType;
1263  // this function will fail to compile if DestType is a reference
1264  // type: that is a feature, not a bug, as a function returning a
1265  // reference lacks referential transparency, is unlikely to be
1266  // thread-safe and is unsuitable for use as a task function
1267  typedef decltype(func(*first1, *first2)) DestType;
1268 
1269  Mutex mutex;
1270  Cond cond;
1271  DiffType start_count = 0;
1272  DiffType done_count = 0;
1273  bool error = false;
1274 
1275  // a specialization of std::numeric_limits::max() for all arithmetic
1276  // types is required by §3.9.1/8 of the standard. The iterator
1277  // difference type must be a signed integer type (§24.2.1/1). All
1278  // signed integer types are arithmetic types (§3.9.1/2, §3.9.1/7 and
1279  // §3.9.1/8).
1280  const DiffType local_max =
1281  (max >= 0) ? max : std::numeric_limits<DiffType>::max();
1282 
1283  // intermediate results have to be held in an array so destination
1284  // ordering can be enforced when using insert interators. This
1285  // causes some inefficiency for non-random access iterators
1286  std::unique_ptr<DestType[]> results(new DestType[std::min(local_max,
1287  std::distance(first1, last1))]);
1288 
1289  // construct SafeFunctorArg objects so that they can be shared
1290  // between different tasks
1292  Cgu::Callback::make_ref(&ParallelHelper2::transform2_func<FType, Arg1RefType, Arg2RefType, DestType>,
1293  std::forward<Func>(func))
1294  };
1296  Cgu::Callback::make(&ParallelHelper2::fail_func<DiffType>,
1297  &mutex,
1298  &cond,
1299  &error,
1300  &done_count)
1301  };
1302 
1303  for (; first1 != last1 && start_count < local_max; ++first1, ++first2, ++start_count) {
1304  std::unique_ptr<const Cgu::Callback::Callback> task_cb(
1305  Cgu::Callback::lambda<>(std::bind(&ParallelHelper2::transform2_cb_func<Arg1RefType, Arg2RefType, DestType, DiffType, SourceIterator1, SourceIterator2>,
1306  s_task,
1307  first1,
1308  first2,
1309  &mutex,
1310  &cond,
1311  &done_count,
1312  results.get(),
1313  start_count))
1314  );
1315  std::unique_ptr<const Cgu::Callback::Callback> fail_cb(
1316  Cgu::Callback::lambda<>([s_fail] () {s_fail();})
1317  );
1318 
1319  tm.add_task(std::move(task_cb), std::move(fail_cb));
1320  }
1321 
1322  Mutex::Lock l{mutex};
1323  while (start_count > done_count) cond.wait(mutex);
1324  if (error) throw ParallelError();
1325  for (DiffType index = 0; index < start_count; ++dest, ++index) {
1326  *dest = std::move(results[index]);
1327  }
1328  return std::make_tuple(first1, first2, dest);
1329 }
1330 
1331 } // namespace Thread
1332 
1333 /**
1334  * @defgroup IntIterHelpers IntIterHelpers
1335  *
1336  * @class IntIter parallel.h c++-gtk-utils/parallel.h
1337  * @brief An iterator class providing a lazy integer range over a virtual container.
1338  * @sa IntIterHelpers
1339  *
1340  * This class acts as an iterator which iterates over a range of
1341  * integers lazily, as if over a virtual container of incrementing
1342  * ints constructed using std::iota. It is principally intended for
1343  * use in constructing parallel for loops using
1344  * Cgu::Thread::parallel_for_each() or
1345  * Cgu::Thread::parallel_transform(), which is why it is in the
1346  * c++-gtk-utils/parallel.h header, but it can be used whenever a lazy
1347  * range of integers is required.
1348  *
1349  * It behaves as a random access iterator to const int, and has the
1350  * normal increment, decrement and other random access functions.
1351  * When used with Cgu::Thread::parallel_for_each() and
1352  * Cgu::Thread::parallel_transform(), because it acts as an iterator
1353  * to const int, the callable object passed to those functions must
1354  * take an int or const int& argument. Any IntIter object compares
1355  * equal to any other IntIter object which at the time in question
1356  * references the same int value, so it can be used as the beginning
1357  * iterator or end iterator of a range for a standard algorithm; and
1358  * one IntIter object is less than another IntIter object if it
1359  * references an int value less than the other, and so on as regards
1360  * the other comparison operators.
1361  *
1362  * Here is an example of its use with
1363  * Cgu::Thread::parallel_transform(), as a parallelized equivalent of
1364  * a for loop which increments a count integer on each iteration
1365  * through the loop. In this example, the count integer, as
1366  * incremented on each iteration, is squared and the result stored in
1367  * a std::vector object (in practice you would not want to use this
1368  * construction for such a trivial case as it would be slower than the
1369  * single threaded version - it is for use where some significant work
1370  * is done in the for loop, here represented by the lambda
1371  * expression):
1372  *
1373  * @code
1374  * using namespace Cgu;
1375  * std::vector<int> v;
1376  * Thread::TaskManager tm{4};
1377  * Thread::parallel_transform(tm,
1378  * IntIter{0}, // beginning of range
1379  * IntIter{10}, // one past end of range
1380  * std::back_inserter(v),
1381  * [](int i) {return i * i;});
1382  * for (auto elt: v) std::cout << elt << ' ';
1383  * std::cout << std::endl;
1384  * @endcode
1385  *
1386  * Although unlikely to be useful very often, the iterator can count
1387  * backwards using std::reverse_iterator:
1388  *
1389  * @code
1390  * using namespace Cgu;
1391  * typedef std::reverse_iterator<IntIter> RIntIter;
1392  * std::vector<int> v;
1393  * Thread::TaskManager tm{4};
1394  * Thread::parallel_transform(tm,
1395  * RIntIter{IntIter{10}}, // one past beginning of range
1396  * RIntIter{IntIter{0}}, // end of range
1397  * std::back_inserter(v),
1398  * [](int i) {return i * i;});
1399  * for (auto elt: v) std::cout << elt << ' ';
1400  * std::cout << std::endl;
1401  * @endcode
1402  *
1403  * @ingroup IntIterHelpers
1404  *
1405  * Since 2.0.27 and 2.2.10.
1406  */
1407 class IntIter {
1408 public:
1409  typedef int value_type;
1410  typedef int reference; // read only
1411  typedef void pointer; // read only
1412  typedef int difference_type;
1413  typedef std::random_access_iterator_tag iterator_category;
1414 private:
1415  int val;
1416 public:
1417  /**
1418  * This constructor acts as both a default constructor and an
1419  * initializing constructor. It does not throw.
1420  *
1421  * Since 2.0.27 and 2.2.10.
1422  */
1423  explicit IntIter(value_type val_ = 0) noexcept : val(val_) {}
1424 
1425  /**
1426  * The copy constructor does not throw.
1427  *
1428  * Since 2.0.27 and 2.2.10.
1429  */
1430  // gcc-4.6 will error if we make this noexcept
1431  IntIter(const IntIter&) = default;
1432 
1433  /**
1434  * The copy assignment operator does not throw. No locking is
1435  * carried out, so if the iterator is accessed in more than one
1436  * thread, the user must provide synchronization (but
1437  * Cgu::Thread::parallel_for_each(),
1438  * Cgu::Thread::parallel_for_each_partial(),
1439  * Cgu::Thread::parallel_transform() and
1440  * Cgu::Thread::parallel_transform_partial() only access source and
1441  * destination iterators in the thread which calls the functions, so
1442  * use of an IntIter object only by one of those functions does not
1443  * require synchronization).
1444  *
1445  * Since 2.0.27 and 2.2.10.
1446  */
1447  // gcc-4.6 will error if we make this noexcept
1448  IntIter& operator=(const IntIter&) = default;
1449 
1450  /**
1451  * The pre-increment operator does not throw. No locking is carried
1452  * out, so if the iterator is accessed in more than one thread, the
1453  * user must provide synchronization (but
1454  * Cgu::Thread::parallel_for_each(),
1455  * Cgu::Thread::parallel_for_each_partial(),
1456  * Cgu::Thread::parallel_transform() and
1457  * Cgu::Thread::parallel_transform_partial() only access source and
1458  * destination iterators in the thread which calls the functions, so
1459  * use of an IntIter object only by one of those functions does not
1460  * require synchronization).
1461  * @return A reference to the iterator after being incremented.
1462  *
1463  * Since 2.0.27 and 2.2.10.
1464  */
1465  IntIter& operator++() noexcept {++val; return *this;}
1466 
1467  /**
1468  * The post-increment operator does not throw. No locking is
1469  * carried out, so if the iterator is accessed in more than one
1470  * thread, the user must provide synchronization (but
1471  * Cgu::Thread::parallel_for_each(),
1472  * Cgu::Thread::parallel_for_each_partial(),
1473  * Cgu::Thread::parallel_transform() and
1474  * Cgu::Thread::parallel_transform_partial() only access source and
1475  * destination iterators in the thread which calls the functions, so
1476  * use of an IntIter object only by one of those functions does not
1477  * require synchronization).
1478  * @return A copy of the iterator prior to being incremented.
1479  *
1480  * Since 2.0.27 and 2.2.10.
1481  */
1482  IntIter operator++(int) noexcept {IntIter tmp = *this; ++val; return tmp;}
1483 
1484  /**
1485  * The pre-decrement operator does not throw. No locking is carried
1486  * out, so if the iterator is accessed in more than one thread, the
1487  * user must provide synchronization (but
1488  * Cgu::Thread::parallel_for_each(),
1489  * Cgu::Thread::parallel_for_each_partial(),
1490  * Cgu::Thread::parallel_transform() and
1491  * Cgu::Thread::parallel_transform_partial() only access source and
1492  * destination iterators in the thread which calls the functions, so
1493  * use of an IntIter object only by one of those functions does not
1494  * require synchronization).
1495  * @return A reference to the iterator after being decremented.
1496  *
1497  * Since 2.0.27 and 2.2.10.
1498  */
1499  IntIter& operator--() noexcept {--val; return *this;}
1500 
1501  /**
1502  * The post-decrement operator does not throw. No locking is
1503  * carried out, so if the iterator is accessed in more than one
1504  * thread, the user must provide synchronization (but
1505  * Cgu::Thread::parallel_for_each(),
1506  * Cgu::Thread::parallel_for_each_partial(),
1507  * Cgu::Thread::parallel_transform() and
1508  * Cgu::Thread::parallel_transform_partial() only access source and
1509  * destination iterators in the thread which calls the functions, so
1510  * use of an IntIter object only by one of those functions does not
1511  * require synchronization).
1512  * @return A copy of the iterator prior to being decremented.
1513  *
1514  * Since 2.0.27 and 2.2.10.
1515  */
1516  IntIter operator--(int) noexcept {IntIter tmp = *this; --val; return tmp;}
1517 
1518  /**
1519  * This operator adds the value of the argument to the integer value
1520  * currently represented by the iterator. It does not throw. No
1521  * locking is carried out, so if the iterator is accessed in more
1522  * than one thread, the user must provide synchronization (but
1523  * Cgu::Thread::parallel_for_each(),
1524  * Cgu::Thread::parallel_for_each_partial(),
1525  * Cgu::Thread::parallel_transform() and
1526  * Cgu::Thread::parallel_transform_partial() only access source and
1527  * destination iterators in the thread which calls the functions, so
1528  * use of an IntIter object only by one of those functions does not
1529  * require synchronization).
1530  * @return A reference to the iterator after addition.
1531  *
1532  * Since 2.0.27 and 2.2.10.
1533  */
1534  IntIter& operator+=(difference_type n) noexcept {val += n; return *this;}
1535 
1536  /**
1537  * This operator subtracts the value of the argument from the
1538  * integer value currently represented by the iterator. It does not
1539  * throw. No locking is carried out, so if the iterator is accessed
1540  * in more than one thread, the user must provide synchronization
1541  * (but Cgu::Thread::parallel_for_each(),
1542  * Cgu::Thread::parallel_for_each_partial(),
1543  * Cgu::Thread::parallel_transform() and
1544  * Cgu::Thread::parallel_transform_partial() only access source and
1545  * destination iterators in the thread which calls the functions, so
1546  * use of an IntIter object only by one of those functions does not
1547  * require synchronization).
1548  * @return A reference to the iterator after subtraction.
1549  *
1550  * Since 2.0.27 and 2.2.10.
1551  */
1552  IntIter& operator-=(difference_type n) noexcept {val -= n; return *this;}
1553 
1554  /**
1555  * The offset dereferencing operator does not throw. No locking is
1556  * carried out, so if the iterator is accessed in more than one
1557  * thread and one calls a non-const method, the user must provide
1558  * synchronization (but Cgu::Thread::parallel_for_each(),
1559  * Cgu::Thread::parallel_for_each_partial(),
1560  * Cgu::Thread::parallel_transform() and
1561  * Cgu::Thread::parallel_transform_partial() only access source and
1562  * destination iterators in the thread which calls the functions, so
1563  * use of an IntIter object only by one of those functions does not
1564  * require synchronization).
1565  * @return The integer value at the given offset.
1566  *
1567  * Since 2.0.27 and 2.2.10.
1568  */
1569  reference operator[](difference_type n) const noexcept {return val + n;}
1570 
1571  /**
1572  * The dereferencing operator does not throw. No locking is carried
1573  * out, so if the iterator is accessed in more than one thread and
1574  * one calls a non-const method, the user must provide
1575  * synchronization (but Cgu::Thread::parallel_for_each(),
1576  * Cgu::Thread::parallel_for_each_partial(),
1577  * Cgu::Thread::parallel_transform() and
1578  * Cgu::Thread::parallel_transform_partial() only access source and
1579  * destination iterators in the thread which calls the functions, so
1580  * use of an IntIter object only by one of those functions does not
1581  * require synchronization).
1582  * @return The integer value currently represented by the iterator.
1583  *
1584  * Since 2.0.27 and 2.2.10.
1585  */
1586  reference operator*() const noexcept {return val;}
1587 
1588 /* Only has effect if --with-glib-memory-slices-compat or
1589  * --with-glib-memory-slices-no-compat option picked */
1591 };
1592 
1593 /**
1594  * @ingroup IntIterHelpers
1595  *
1596  * This comparison operator does not throw. No locking is carried
1597  * out, so if one of the iterators is accessed in more than one thread
1598  * and a thread calls a non-const method, the user must provide
1599  * synchronization (but Cgu::Thread::parallel_for_each(),
1600  * Cgu::Thread::parallel_for_each_partial(),
1601  * Cgu::Thread::parallel_transform() and
1602  * Cgu::Thread::parallel_transform_partial() only access source and
1603  * destination iterators in the thread which calls those functions, so
1604  * use of an IntIter object only by one of those functions does not
1605  * require synchronization).
1606  *
1607  * Since 2.0.27 and 2.2.10.
1608  */
1609 inline bool operator==(IntIter iter1, IntIter iter2) noexcept {
1610  return *iter1 == *iter2;
1611 }
1612 
1613 /**
1614  * @ingroup IntIterHelpers
1615  *
1616  * This comparison operator does not throw. No locking is carried
1617  * out, so if one of the iterators is accessed in more than one thread
1618  * and a thread calls a non-const method, the user must provide
1619  * synchronization (but Cgu::Thread::parallel_for_each(),
1620  * Cgu::Thread::parallel_for_each_partial(),
1621  * Cgu::Thread::parallel_transform() and
1622  * Cgu::Thread::parallel_transform_partial() only access source and
1623  * destination iterators in the thread which calls those functions, so
1624  * use of an IntIter object only by one of those functions does not
1625  * require synchronization).
1626  *
1627  * Since 2.0.27 and 2.2.10.
1628  */
1629 inline bool operator!=(IntIter iter1, IntIter iter2) noexcept {
1630  return !(iter1 == iter2);
1631 }
1632 
1633 /**
1634  * @ingroup IntIterHelpers
1635  *
1636  * This comparison operator does not throw. No locking is carried
1637  * out, so if one of the iterators is accessed in more than one thread
1638  * and a thread calls a non-const method, the user must provide
1639  * synchronization (but Cgu::Thread::parallel_for_each(),
1640  * Cgu::Thread::parallel_for_each_partial(),
1641  * Cgu::Thread::parallel_transform() and
1642  * Cgu::Thread::parallel_transform_partial() only access source and
1643  * destination iterators in the thread which calls those functions, so
1644  * use of an IntIter object only by one of those functions does not
1645  * require synchronization).
1646  *
1647  * Since 2.0.27 and 2.2.10.
1648  */
1649 inline bool operator<(IntIter iter1, IntIter iter2) noexcept {
1650  return *iter1 < *iter2;
1651 }
1652 
1653 /**
1654  * @ingroup IntIterHelpers
1655  *
1656  * This comparison operator does not throw. No locking is carried
1657  * out, so if one of the iterators is accessed in more than one thread
1658  * and a thread calls a non-const method, the user must provide
1659  * synchronization (but Cgu::Thread::parallel_for_each(),
1660  * Cgu::Thread::parallel_for_each_partial(),
1661  * Cgu::Thread::parallel_transform() and
1662  * Cgu::Thread::parallel_transform_partial() only access source and
1663  * destination iterators in the thread which calls those functions, so
1664  * use of an IntIter object only by one of those functions does not
1665  * require synchronization).
1666  *
1667  * Since 2.0.27 and 2.2.10.
1668  */
1669 inline bool operator>(IntIter iter1, IntIter iter2) noexcept {
1670  return iter2 < iter1;
1671 }
1672 
1673 /**
1674  * @ingroup IntIterHelpers
1675  *
1676  * This comparison operator does not throw. No locking is carried
1677  * out, so if one of the iterators is accessed in more than one thread
1678  * and a thread calls a non-const method, the user must provide
1679  * synchronization (but Cgu::Thread::parallel_for_each(),
1680  * Cgu::Thread::parallel_for_each_partial(),
1681  * Cgu::Thread::parallel_transform() and
1682  * Cgu::Thread::parallel_transform_partial() only access source and
1683  * destination iterators in the thread which calls the functions, so
1684  * use of an IntIter object only by one of those functions does not
1685  * require synchronization).
1686  *
1687  * Since 2.0.27 and 2.2.10.
1688  */
1689 inline bool operator<=(IntIter iter1, IntIter iter2) noexcept {
1690  return !(iter1 > iter2);
1691 }
1692 
1693 /**
1694  * @ingroup IntIterHelpers
1695  *
1696  * This comparison operator does not throw. No locking is carried
1697  * out, so if one of the iterators is accessed in more than one thread
1698  * and a thread calls a non-const method, the user must provide
1699  * synchronization (but Cgu::Thread::parallel_for_each(),
1700  * Cgu::Thread::parallel_for_each_partial(),
1701  * Cgu::Thread::parallel_transform() and
1702  * Cgu::Thread::parallel_transform_partial() only access source and
1703  * destination iterators in the thread which calls those functions, so
1704  * use of an IntIter object only by one of those functions does not
1705  * require synchronization).
1706  *
1707  * Since 2.0.27 and 2.2.10.
1708  */
1709 inline bool operator>=(IntIter iter1, IntIter iter2) noexcept {
1710  return !(iter1 < iter2);
1711 }
1712 
1713 /**
1714  * @ingroup IntIterHelpers
1715  *
1716  * This operator does not throw. No locking is carried out, so if one
1717  * of the iterators is accessed in more than one thread and a thread
1718  * calls a non-const method, the user must provide synchronization
1719  * (but Cgu::Thread::parallel_for_each(),
1720  * Cgu::Thread::parallel_for_each_partial(),
1721  * Cgu::Thread::parallel_transform() and
1722  * Cgu::Thread::parallel_transform_partial() only access source and
1723  * destination iterators in the thread which calls those functions, so
1724  * use of an IntIter object only by one of those functions does not
1725  * require synchronization).
1726  *
1727  * Since 2.0.27 and 2.2.10.
1728  */
1729 inline IntIter::difference_type operator-(IntIter iter1, IntIter iter2) noexcept {
1730  return *iter1 - *iter2;
1731 }
1732 
1733 /**
1734  * @ingroup IntIterHelpers
1735  *
1736  * This operator does not throw. No locking is carried out, so if one
1737  * of the iterators is accessed in more than one thread and a thread
1738  * calls a non-const method, the user must provide synchronization
1739  * (but Cgu::Thread::parallel_for_each(),
1740  * Cgu::Thread::parallel_for_each_partial(),
1741  * Cgu::Thread::parallel_transform() and
1742  * Cgu::Thread::parallel_transform_partial() only access source and
1743  * destination iterators in the thread which calls those functions, so
1744  * use of an IntIter object only by one of those functions does not
1745  * require synchronization).
1746  *
1747  * Since 2.0.27 and 2.2.10.
1748  */
1750  return IntIter{*iter + n};
1751 }
1752 
1753 /**
1754  * @ingroup IntIterHelpers
1755  *
1756  * This operator does not throw. No locking is carried out, so if one
1757  * of the iterators is accessed in more than one thread and a thread
1758  * calls a non-const method, the user must provide synchronization
1759  * (but Cgu::Thread::parallel_for_each(),
1760  * Cgu::Thread::parallel_for_each_partial(),
1761  * Cgu::Thread::parallel_transform() and
1762  * Cgu::Thread::parallel_transform_partial() only access source and
1763  * destination iterators in the thread which calls those functions, so
1764  * use of an IntIter object only by one of those functions does not
1765  * require synchronization).
1766  *
1767  * Since 2.0.27 and 2.2.10.
1768  */
1770  return IntIter{*iter - n};
1771 }
1772 
1773 /**
1774  * @ingroup IntIterHelpers
1775  *
1776  * This operator does not throw. No locking is carried out, so if one
1777  * of the iterators is accessed in more than one thread and a thread
1778  * calls a non-const method, the user must provide synchronization
1779  * (but Cgu::Thread::parallel_for_each(),
1780  * Cgu::Thread::parallel_for_each_partial(),
1781  * Cgu::Thread::parallel_transform() and
1782  * Cgu::Thread::parallel_transform_partial() only access source and
1783  * destination iterators in the thread which calls those functions, so
1784  * use of an IntIter object only by one of those functions does not
1785  * require synchronization).
1786  *
1787  * Since 2.0.27 and 2.2.10.
1788  */
1790  return iter + n;
1791 }
1792 
1793 } // namespace Cgu
1794 
1795 #endif // CGU_PARALLEL_H