]>
Commit | Line | Data |
---|---|---|
7c673cae FG |
1 | //---------------------------------------------------------------------------// |
2 | // Copyright (c) 2013 Kyle Lutz <kyle.r.lutz@gmail.com> | |
3 | // | |
4 | // Distributed under the Boost Software License, Version 1.0 | |
5 | // See accompanying file LICENSE_1_0.txt or copy at | |
6 | // http://www.boost.org/LICENSE_1_0.txt | |
7 | // | |
8 | // See http://boostorg.github.com/compute for more information. | |
9 | //---------------------------------------------------------------------------// | |
10 | ||
11 | #ifndef BOOST_COMPUTE_ALGORITHM_MERGE_HPP | |
12 | #define BOOST_COMPUTE_ALGORITHM_MERGE_HPP | |
13 | ||
14 | #include <boost/compute/system.hpp> | |
15 | #include <boost/compute/command_queue.hpp> | |
16 | #include <boost/compute/algorithm/copy.hpp> | |
17 | #include <boost/compute/algorithm/detail/merge_with_merge_path.hpp> | |
18 | #include <boost/compute/algorithm/detail/serial_merge.hpp> | |
19 | #include <boost/compute/detail/iterator_range_size.hpp> | |
20 | #include <boost/compute/detail/parameter_cache.hpp> | |
21 | ||
22 | namespace boost { | |
23 | namespace compute { | |
24 | ||
25 | /// Merges the sorted values in the range [\p first1, \p last1) with the sorted | |
26 | /// values in the range [\p first2, last2) and stores the result in the range | |
27 | /// beginning at \p result. Values are compared using the \p comp function. If | |
28 | /// no comparision function is given, \c less is used. | |
29 | /// | |
30 | /// \param first1 first element in the first range to merge | |
31 | /// \param last1 last element in the first range to merge | |
32 | /// \param first2 first element in the second range to merge | |
33 | /// \param last2 last element in the second range to merge | |
34 | /// \param result first element in the result range | |
35 | /// \param comp comparison function (by default \c less) | |
36 | /// \param queue command queue to perform the operation | |
37 | /// | |
38 | /// \return \c OutputIterator to the end of the result range | |
39 | /// | |
40 | /// \see inplace_merge() | |
41 | template<class InputIterator1, | |
42 | class InputIterator2, | |
43 | class OutputIterator, | |
44 | class Compare> | |
45 | inline OutputIterator merge(InputIterator1 first1, | |
46 | InputIterator1 last1, | |
47 | InputIterator2 first2, | |
48 | InputIterator2 last2, | |
49 | OutputIterator result, | |
50 | Compare comp, | |
51 | command_queue &queue = system::default_queue()) | |
52 | { | |
53 | typedef typename std::iterator_traits<InputIterator1>::value_type input1_type; | |
54 | typedef typename std::iterator_traits<InputIterator2>::value_type input2_type; | |
55 | typedef typename std::iterator_traits<OutputIterator>::value_type output_type; | |
56 | ||
57 | const device &device = queue.get_device(); | |
58 | ||
59 | std::string cache_key = | |
60 | std::string("__boost_merge_") + type_name<input1_type>() + "_" | |
61 | + type_name<input2_type>() + "_" + type_name<output_type>(); | |
62 | boost::shared_ptr<detail::parameter_cache> parameters = | |
63 | detail::parameter_cache::get_global_cache(device); | |
64 | ||
65 | // default serial merge threshold depends on device type | |
66 | size_t default_serial_merge_threshold = 32768; | |
67 | if(device.type() & device::gpu) { | |
68 | default_serial_merge_threshold = 2048; | |
69 | } | |
70 | ||
71 | // loading serial merge threshold parameter | |
72 | const size_t serial_merge_threshold = | |
73 | parameters->get(cache_key, "serial_merge_threshold", | |
74 | static_cast<uint_>(default_serial_merge_threshold)); | |
75 | ||
76 | // choosing merge algorithm | |
77 | const size_t total_count = | |
78 | detail::iterator_range_size(first1, last1) | |
79 | + detail::iterator_range_size(first2, last2); | |
80 | // for small inputs serial merge turns out to outperform | |
81 | // merge with merge path algorithm | |
82 | if(total_count <= serial_merge_threshold){ | |
83 | return detail::serial_merge(first1, last1, first2, last2, result, comp, queue); | |
84 | } | |
85 | return detail::merge_with_merge_path(first1, last1, first2, last2, result, comp, queue); | |
86 | } | |
87 | ||
88 | /// \overload | |
89 | template<class InputIterator1, class InputIterator2, class OutputIterator> | |
90 | inline OutputIterator merge(InputIterator1 first1, | |
91 | InputIterator1 last1, | |
92 | InputIterator2 first2, | |
93 | InputIterator2 last2, | |
94 | OutputIterator result, | |
95 | command_queue &queue = system::default_queue()) | |
96 | { | |
97 | typedef typename std::iterator_traits<InputIterator1>::value_type value_type; | |
98 | less<value_type> less_than; | |
99 | return merge(first1, last1, first2, last2, result, less_than, queue); | |
100 | } | |
101 | ||
102 | } // end compute namespace | |
103 | } // end boost namespace | |
104 | ||
105 | #endif // BOOST_COMPUTE_ALGORITHM_MERGE_HPP |