ceph/src/boost/boost/compute/algorithm/detail/serial_merge.hpp

   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_SERIAL_MERGE_HPP
  12 #define BOOST_COMPUTE_ALGORITHM_SERIAL_MERGE_HPP
  13
  14 #include <iterator>
  15
  16 #include <boost/compute/command_queue.hpp>
  17 #include <boost/compute/detail/meta_kernel.hpp>
  18 #include <boost/compute/detail/iterator_range_size.hpp>
  19
  20 namespace boost {
  21 namespace compute {
  22 namespace detail {
  23
  24 template<class InputIterator1,
  25          class InputIterator2,
  26          class OutputIterator,
  27          class Compare>
  28 inline OutputIterator serial_merge(InputIterator1 first1,
  29                                    InputIterator1 last1,
  30                                    InputIterator2 first2,
  31                                    InputIterator2 last2,
  32                                    OutputIterator result,
  33                                    Compare comp,
  34                                    command_queue &queue)
  35 {
  36     typedef typename
  37         std::iterator_traits<InputIterator1>::value_type
  38         input_type1;
  39     typedef typename
  40         std::iterator_traits<InputIterator2>::value_type
  41         input_type2;
  42     typedef typename
  43         std::iterator_traits<OutputIterator>::difference_type
  44         result_difference_type;
  45
  46     std::ptrdiff_t size1 = std::distance(first1, last1);
  47     std::ptrdiff_t size2 = std::distance(first2, last2);
  48
  49     meta_kernel k("serial_merge");
  50     k.add_set_arg<uint_>("size1", static_cast<uint_>(size1));
  51     k.add_set_arg<uint_>("size2", static_cast<uint_>(size2));
  52
  53     k <<
  54         "uint i = 0;\n" << // index in result range
  55         "uint j = 0;\n" << // index in first input range
  56         "uint k = 0;\n" << // index in second input range
  57
  58         // fetch initial values from each range
  59         k.decl<input_type1>("j_value") << " = " << first1[0] << ";\n" <<
  60         k.decl<input_type2>("k_value") << " = " << first2[0] << ";\n" <<
  61
  62         // merge values from both input ranges to the result range
  63         "while(j < size1 && k < size2){\n" <<
  64         "    if(" << comp(k.var<input_type1>("j_value"),
  65                           k.var<input_type2>("k_value")) << "){\n" <<
  66         "        " << result[k.var<uint_>("i++")] << " = j_value;\n" <<
  67         "        j_value = " << first1[k.var<uint_>("++j")] << ";\n" <<
  68         "    }\n" <<
  69         "    else{\n"
  70         "        " << result[k.var<uint_>("i++")] << " = k_value;\n"
  71         "        k_value = " << first2[k.var<uint_>("++k")] << ";\n" <<
  72         "    }\n"
  73         "}\n"
  74
  75         // copy any remaining values from first range
  76         "while(j < size1){\n" <<
  77             result[k.var<uint_>("i++")] << " = " <<
  78                first1[k.var<uint_>("j++")] << ";\n" <<
  79         "}\n"
  80
  81         // copy any remaining values from second range
  82         "while(k < size2){\n" <<
  83             result[k.var<uint_>("i++")] << " = " <<
  84                first2[k.var<uint_>("k++")] << ";\n" <<
  85         "}\n";
  86
  87     // run kernel
  88     k.exec(queue);
  89
  90     return result + static_cast<result_difference_type>(size1 + size2);
  91 }
  92
  93 } // end detail namespace
  94 } // end compute namespace
  95 } // end boost namespace
  96
  97 #endif // BOOST_COMPUTE_ALGORITHM_SERIAL_MERGE_HPP