ceph/src/boost/boost/compute/algorithm/reduce_by_key.hpp

   1 //---------------------------------------------------------------------------//
   2 // Copyright (c) 2015 Jakub Szuppe <j.szuppe@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_REDUCE_BY_KEY_HPP
  12 #define BOOST_COMPUTE_ALGORITHM_REDUCE_BY_KEY_HPP
  13
  14 #include <iterator>
  15 #include <utility>
  16
  17 #include <boost/compute/command_queue.hpp>
  18 #include <boost/compute/device.hpp>
  19 #include <boost/compute/functional.hpp>
  20 #include <boost/compute/system.hpp>
  21 #include <boost/compute/algorithm/detail/reduce_by_key.hpp>
  22
  23 namespace boost {
  24 namespace compute {
  25
  26 /// The \c reduce_by_key() algorithm performs reduction for each contiguous
  27 /// subsequence of values determinate by equivalent keys.
  28 ///
  29 /// Returns a pair of iterators at the end of the ranges [\p keys_result, keys_result_last)
  30 /// and [\p values_result, \p values_result_last).
  31 ///
  32 /// If no function is specified, \c plus will be used.
  33 /// If no predicate is specified, \c equal_to will be used.
  34 ///
  35 /// \param keys_first the first key
  36 /// \param keys_last the last key
  37 /// \param values_first the first input value
  38 /// \param keys_result iterator pointing to the key output
  39 /// \param values_result iterator pointing to the reduced value output
  40 /// \param function binary reduction function
  41 /// \param predicate binary predicate which returns true only if two keys are equal
  42 /// \param queue command queue to perform the operation
  43 ///
  44 /// The \c reduce_by_key() algorithm assumes that the binary reduction function
  45 /// is associative. When used with non-associative functions the result may
  46 /// be non-deterministic and vary in precision. Notably this affects the
  47 /// \c plus<float>() function as floating-point addition is not associative
  48 /// and may produce slightly different results than a serial algorithm.
  49 ///
  50 /// For example, to calculate the sum of the values for each key:
  51 ///
  52 /// \snippet test/test_reduce_by_key.cpp reduce_by_key_int
  53 ///
  54 /// Space complexity on GPUs: \Omega(2n)<br>
  55 /// Space complexity on CPUs: \Omega(1)
  56 ///
  57 /// \see reduce()
  58 template<class InputKeyIterator, class InputValueIterator,
  59          class OutputKeyIterator, class OutputValueIterator,
  60          class BinaryFunction, class BinaryPredicate>
  61 inline std::pair<OutputKeyIterator, OutputValueIterator>
  62 reduce_by_key(InputKeyIterator keys_first,
  63               InputKeyIterator keys_last,
  64               InputValueIterator values_first,
  65               OutputKeyIterator keys_result,
  66               OutputValueIterator values_result,
  67               BinaryFunction function,
  68               BinaryPredicate predicate,
  69               command_queue &queue = system::default_queue())
  70 {
  71     return detail::dispatch_reduce_by_key(keys_first, keys_last, values_first,
  72                                           keys_result, values_result,
  73                                           function, predicate,
  74                                           queue);
  75 }
  76
  77 /// \overload
  78 template<class InputKeyIterator, class InputValueIterator,
  79          class OutputKeyIterator, class OutputValueIterator,
  80          class BinaryFunction>
  81 inline std::pair<OutputKeyIterator, OutputValueIterator>
  82 reduce_by_key(InputKeyIterator keys_first,
  83               InputKeyIterator keys_last,
  84               InputValueIterator values_first,
  85               OutputKeyIterator keys_result,
  86               OutputValueIterator values_result,
  87               BinaryFunction function,
  88               command_queue &queue = system::default_queue())
  89 {
  90     typedef typename std::iterator_traits<InputKeyIterator>::value_type key_type;
  91
  92     return reduce_by_key(keys_first, keys_last, values_first,
  93                          keys_result, values_result,
  94                          function, equal_to<key_type>(),
  95                          queue);
  96 }
  97
  98 /// \overload
  99 template<class InputKeyIterator, class InputValueIterator,
 100          class OutputKeyIterator, class OutputValueIterator>
 101 inline std::pair<OutputKeyIterator, OutputValueIterator>
 102 reduce_by_key(InputKeyIterator keys_first,
 103               InputKeyIterator keys_last,
 104               InputValueIterator values_first,
 105               OutputKeyIterator keys_result,
 106               OutputValueIterator values_result,
 107               command_queue &queue = system::default_queue())
 108 {
 109     typedef typename std::iterator_traits<InputKeyIterator>::value_type key_type;
 110     typedef typename std::iterator_traits<InputValueIterator>::value_type value_type;
 111
 112     return reduce_by_key(keys_first, keys_last, values_first,
 113                          keys_result, values_result,
 114                          plus<value_type>(), equal_to<key_type>(),
 115                          queue);
 116 }
 117
 118 } // end compute namespace
 119 } // end boost namespace
 120
 121 #endif // BOOST_COMPUTE_ALGORITHM_REDUCE_BY_KEY_HPP