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