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