1 // Copyright (c) 2015 Amanieu d'Antras
2 //
3 // Permission is hereby granted, free of charge, to any person obtaining a copy
4 // of this software and associated documentation files (the "Software"), to deal
5 // in the Software without restriction, including without limitation the rights
6 // to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
7 // copies of the Software, and to permit persons to whom the Software is
8 // furnished to do so, subject to the following conditions:
9 //
10 // The above copyright notice and this permission notice shall be included in
11 // all copies or substantial portions of the Software.
12 //
13 // THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
14 // IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
15 // FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
16 // AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
17 // LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
18 // OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN
19 // THE SOFTWARE.
20
21 #ifndef ASYNCXX_H_
22 # error "Do not include this header directly, include <async++.h> instead."
23 #endif
24
25 namespace async {
26 namespace detail {
27
28 // Default map function which simply passes its parameter through unmodified
29 struct default_map {
30 template<typename T>
operatordefault_map31 T&& operator()(T&& x) const
32 {
33 return std::forward<T>(x);
34 }
35 };
36
37 // Internal implementation of parallel_map_reduce that only accepts a
38 // partitioner argument.
39 template<typename Sched, typename Partitioner, typename Result, typename MapFunc, typename ReduceFunc>
internal_parallel_map_reduce(Sched & sched,Partitioner partitioner,Result init,const MapFunc & map,const ReduceFunc & reduce)40 Result internal_parallel_map_reduce(Sched& sched, Partitioner partitioner, Result init, const MapFunc& map, const ReduceFunc& reduce)
41 {
42 // Split the partition, run inline if no more splits are possible
43 auto subpart = partitioner.split();
44 if (subpart.begin() == subpart.end()) {
45 Result out = init;
46 for (auto&& i: partitioner)
47 out = reduce(std::move(out), map(std::forward<decltype(i)>(i)));
48 return out;
49 }
50
51 // Run the function over each half in parallel
52 auto&& t = async::local_spawn(sched, [&sched, &subpart, init, &map, &reduce] {
53 return detail::internal_parallel_map_reduce(sched, std::move(subpart), init, map, reduce);
54 });
55 Result out = detail::internal_parallel_map_reduce(sched, std::move(partitioner), init, map, reduce);
56 return reduce(std::move(out), t.get());
57 }
58
59 } // namespace detail
60
61 // Run a function for each element in a range and then reduce the results of that function to a single value
62 template<typename Sched, typename Range, typename Result, typename MapFunc, typename ReduceFunc>
parallel_map_reduce(Sched & sched,Range && range,Result init,const MapFunc & map,const ReduceFunc & reduce)63 Result parallel_map_reduce(Sched& sched, Range&& range, Result init, const MapFunc& map, const ReduceFunc& reduce)
64 {
65 return detail::internal_parallel_map_reduce(sched, async::to_partitioner(std::forward<Range>(range)), init, map, reduce);
66 }
67
68 // Overload with default scheduler
69 template<typename Range, typename Result, typename MapFunc, typename ReduceFunc>
parallel_map_reduce(Range && range,Result init,const MapFunc & map,const ReduceFunc & reduce)70 Result parallel_map_reduce(Range&& range, Result init, const MapFunc& map, const ReduceFunc& reduce)
71 {
72 return async::parallel_map_reduce(::async::default_scheduler(), range, init, map, reduce);
73 }
74
75 // Overloads with std::initializer_list
76 template<typename Sched, typename T, typename Result, typename MapFunc, typename ReduceFunc>
parallel_map_reduce(Sched & sched,std::initializer_list<T> range,Result init,const MapFunc & map,const ReduceFunc & reduce)77 Result parallel_map_reduce(Sched& sched, std::initializer_list<T> range, Result init, const MapFunc& map, const ReduceFunc& reduce)
78 {
79 return async::parallel_map_reduce(sched, async::make_range(range.begin(), range.end()), init, map, reduce);
80 }
81 template<typename T, typename Result, typename MapFunc, typename ReduceFunc>
parallel_map_reduce(std::initializer_list<T> range,Result init,const MapFunc & map,const ReduceFunc & reduce)82 Result parallel_map_reduce(std::initializer_list<T> range, Result init, const MapFunc& map, const ReduceFunc& reduce)
83 {
84 return async::parallel_map_reduce(async::make_range(range.begin(), range.end()), init, map, reduce);
85 }
86
87 // Variant with identity map operation
88 template<typename Sched, typename Range, typename Result, typename ReduceFunc>
parallel_reduce(Sched & sched,Range && range,Result init,const ReduceFunc & reduce)89 Result parallel_reduce(Sched& sched, Range&& range, Result init, const ReduceFunc& reduce)
90 {
91 return async::parallel_map_reduce(sched, range, init, detail::default_map(), reduce);
92 }
93 template<typename Range, typename Result, typename ReduceFunc>
parallel_reduce(Range && range,Result init,const ReduceFunc & reduce)94 Result parallel_reduce(Range&& range, Result init, const ReduceFunc& reduce)
95 {
96 return async::parallel_reduce(::async::default_scheduler(), range, init, reduce);
97 }
98 template<typename Sched, typename T, typename Result, typename ReduceFunc>
parallel_reduce(Sched & sched,std::initializer_list<T> range,Result init,const ReduceFunc & reduce)99 Result parallel_reduce(Sched& sched, std::initializer_list<T> range, Result init, const ReduceFunc& reduce)
100 {
101 return async::parallel_reduce(sched, async::make_range(range.begin(), range.end()), init, reduce);
102 }
103 template<typename T, typename Result, typename ReduceFunc>
parallel_reduce(std::initializer_list<T> range,Result init,const ReduceFunc & reduce)104 Result parallel_reduce(std::initializer_list<T> range, Result init, const ReduceFunc& reduce)
105 {
106 return async::parallel_reduce(async::make_range(range.begin(), range.end()), init, reduce);
107 }
108
109 } // namespace async
110