Embedded Multicore Building Blocks V1.0.0
merge_sort.h
1 /*
2  * Copyright (c) 2014-2017, Siemens AG. All rights reserved.
3  *
4  * Redistribution and use in source and binary forms, with or without
5  * modification, are permitted provided that the following conditions are met:
6  *
7  * 1. Redistributions of source code must retain the above copyright notice,
8  * this list of conditions and the following disclaimer.
9  *
10  * 2. Redistributions in binary form must reproduce the above copyright notice,
11  * this list of conditions and the following disclaimer in the documentation
12  * and/or other materials provided with the distribution.
13  *
14  * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS"
15  * AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
16  * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
17  * ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT HOLDER OR CONTRIBUTORS BE
18  * LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR
19  * CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF
20  * SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS
21  * INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN
22  * CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
23  * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE
24  * POSSIBILITY OF SUCH DAMAGE.
25  */
26 
27 #ifndef EMBB_ALGORITHMS_MERGE_SORT_H_
28 #define EMBB_ALGORITHMS_MERGE_SORT_H_
29 
30 #include <functional>
31 #include <embb/mtapi/job.h>
32 #include <embb/mtapi/execution_policy.h>
33 #include <embb/base/memory_allocation.h>
34 
35 namespace embb {
36 namespace algorithms {
37 
45 #ifdef DOXYGEN
46 
74 template<typename RAI, typename ComparisonFunction>
76  RAI first,
78  RAI last,
81  ComparisonFunction comparison
82  = std::less<typename std::iterator_traits<RAI>::value_type>(),
89  size_t block_size = 0
96  );
97 
124 template<typename RAI, typename RAITemp, typename ComparisonFunction>
125 void MergeSort(
126  RAI first,
128  RAI last,
130  RAITemp temporary_first,
133  ComparisonFunction comparison
134  = std::less<typename std::iterator_traits<RAI>::value_type>(),
141  size_t block_size = 0
148  );
149 
150 #else // DOXYGEN
151 
155 template<typename RAI, typename RAITemp>
156 void MergeSort(
157  RAI first,
158  RAI last,
159  RAITemp temporary_first,
160  embb::mtapi::Job comparison,
161  const embb::mtapi::ExecutionPolicy& policy,
162  size_t block_size
163  );
164 
168 template<typename RAI, typename RAITemp, typename ComparisonFunction>
169 void MergeSort(
170  RAI first,
171  RAI last,
172  RAITemp temporary_first,
173  ComparisonFunction comparison,
174  const embb::mtapi::ExecutionPolicy& policy,
175  size_t block_size
176  );
177 
181 template<typename RAI, typename ComparisonFunction>
182 void MergeSortAllocate(
183  RAI first,
184  RAI last,
185  ComparisonFunction comparison,
186  const embb::mtapi::ExecutionPolicy& policy,
187  size_t block_size
188  ) {
189  typedef base::Allocation Alloc;
190  typename std::iterator_traits<RAI>::difference_type distance = last - first;
191  typedef typename std::iterator_traits<RAI>::value_type value_type;
192  if (distance == 0) {
193  return;
194  } else if (distance < 0) {
195  EMBB_THROW(embb::base::ErrorException, "Negative range for MergeSort");
196  }
197  value_type* temporary = static_cast<value_type*>(
198  Alloc::Allocate(distance * sizeof(value_type)));
199 
200  EMBB_TRY {
201  MergeSort(first, last, temporary, comparison, policy, block_size);
202  } EMBB_CATCH (embb::base::ErrorException & e) {
203  // embb exception handling does not support catch(...) and rethrow yet.
204  Alloc::Free(temporary);
205 
206  // Rethrow only, if exceptions are enabled... Otherwise, the parameter
207  // e cannot be used, as it is not defined.
208 #ifdef EMBB_USE_EXCEPTIONS
209  EMBB_THROW(embb::base::ErrorException, e.what());
210 #endif
211  }
212  Alloc::Free(temporary);
213 }
214 
218 template<typename RAI>
219 void MergeSortAllocate(
220  RAI first,
221  RAI last
222  ) {
223  MergeSortAllocate(first, last,
224  std::less<typename std::iterator_traits<RAI>::value_type>(),
226 }
227 
231 template<typename RAI, typename ComparisonFunction>
232 void MergeSortAllocate(
233  RAI first,
234  RAI last,
235  ComparisonFunction comparison
236  ) {
237  MergeSortAllocate(first, last, comparison, embb::mtapi::ExecutionPolicy(), 0);
238 }
239 
243 template<typename RAI, typename ComparisonFunction>
244 void MergeSortAllocate(
245  RAI first,
246  RAI last,
247  ComparisonFunction comparison,
248  const embb::mtapi::ExecutionPolicy& policy
249  ) {
250  MergeSortAllocate(first, last, comparison, policy, 0);
251 }
252 
256 template<typename RAI, typename RAITemp>
257 void MergeSort(
258  RAI first,
259  RAI last,
260  RAITemp temporary_first
261  ) {
262  MergeSort(first, last, temporary_first,
263  std::less<typename std::iterator_traits<RAI>::value_type>(),
265 }
266 
270 template<typename RAI, typename RAITemp, typename ComparisonFunction>
271 void MergeSort(
272  RAI first,
273  RAI last,
274  RAITemp temporary_first,
275  ComparisonFunction comparison
276  ) {
277  MergeSort(first, last, temporary_first, comparison,
279 }
280 
284 template<typename RAI, typename RAITemp, typename ComparisonFunction>
285 void MergeSort(
286  RAI first,
287  RAI last,
288  RAITemp temporary_first,
289  ComparisonFunction comparison,
290  const embb::mtapi::ExecutionPolicy& policy
291  ) {
292  MergeSort(first, last, temporary_first, comparison, policy, 0);
293 }
294 
295 #endif // else DOXYGEN
296 
301 } // namespace algorithms
302 } // namespace embb
303 
304 #include<embb/algorithms/internal/merge_sort-inl.h>
305 
306 #endif // EMBB_ALGORITHMS_MERGE_SORT_H_
Definition: lock_free_mpmc_queue.h:40
void MergeSort(RAI first, RAI last, RAITemp temporary_first, ComparisonFunction comparison=std::less< typename std::iterator_traits< RAI >::value_type >(), const embb::mtapi::ExecutionPolicy &policy=embb::mtapi::ExecutionPolicy(), size_t block_size=0)
Sorts a range of elements using a parallel merge sort algorithm without implicit allocation of dynami...
Indicates a general error.
Definition: exceptions.h:264
Represents a collection of Actions.
Definition: job.h:41
Describes the execution policy of a parallel algorithm.
Definition: execution_policy.h:48
void MergeSortAllocate(RAI first, RAI last, ComparisonFunction comparison=std::less< typename std::iterator_traits< RAI >::value_type >(), const embb::mtapi::ExecutionPolicy &policy=embb::mtapi::ExecutionPolicy(), size_t block_size=0)
Sorts a range of elements using a parallel merge sort algorithm with implicit allocation of dynamic m...