ceph/src/boost/boost/compute/iterator/strided_iterator.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_ITERATOR_STRIDED_ITERATOR_HPP
  12 #define BOOST_COMPUTE_ITERATOR_STRIDED_ITERATOR_HPP
  13
  14 #include <cstddef>
  15 #include <iterator>
  16
  17 #include <boost/config.hpp>
  18 #include <boost/iterator/iterator_adaptor.hpp>
  19
  20 #include <boost/compute/functional.hpp>
  21 #include <boost/compute/detail/meta_kernel.hpp>
  22 #include <boost/compute/detail/is_buffer_iterator.hpp>
  23 #include <boost/compute/detail/read_write_single_value.hpp>
  24 #include <boost/compute/iterator/detail/get_base_iterator_buffer.hpp>
  25 #include <boost/compute/type_traits/is_device_iterator.hpp>
  26 #include <boost/compute/type_traits/result_of.hpp>
  27
  28 namespace boost {
  29 namespace compute {
  30
  31 // forward declaration for strided_iterator
  32 template<class Iterator>
  33 class strided_iterator;
  34
  35 namespace detail {
  36
  37 // helper class which defines the iterator_adaptor super-class
  38 // type for strided_iterator
  39 template<class Iterator>
  40 class strided_iterator_base
  41 {
  42 public:
  43     typedef ::boost::iterator_adaptor<
  44         ::boost::compute::strided_iterator<Iterator>,
  45         Iterator,
  46         typename std::iterator_traits<Iterator>::value_type,
  47         typename std::iterator_traits<Iterator>::iterator_category
  48     > type;
  49 };
  50
  51 // helper class for including stride value in index expression
  52 template<class IndexExpr, class Stride>
  53 struct stride_expr
  54 {
  55     stride_expr(const IndexExpr &expr, const Stride &stride)
  56         : m_index_expr(expr),
  57           m_stride(stride)
  58     {
  59     }
  60
  61     const IndexExpr m_index_expr;
  62     const Stride m_stride;
  63 };
  64
  65 template<class IndexExpr, class Stride>
  66 inline stride_expr<IndexExpr, Stride> make_stride_expr(const IndexExpr &expr,
  67                                                        const Stride &stride)
  68 {
  69     return stride_expr<IndexExpr, Stride>(expr, stride);
  70 }
  71
  72 template<class IndexExpr, class Stride>
  73 inline meta_kernel& operator<<(meta_kernel &kernel,
  74                                const stride_expr<IndexExpr, Stride> &expr)
  75 {
  76     // (expr.m_stride * (expr.m_index_expr))
  77     return kernel << "(" << static_cast<ulong_>(expr.m_stride)
  78                   << " * (" << expr.m_index_expr << "))";
  79 }
  80
  81 template<class Iterator, class Stride, class IndexExpr>
  82 struct strided_iterator_index_expr
  83 {
  84     typedef typename std::iterator_traits<Iterator>::value_type result_type;
  85
  86     strided_iterator_index_expr(const Iterator &input_iter,
  87                                 const Stride &stride,
  88                                 const IndexExpr &index_expr)
  89         : m_input_iter(input_iter),
  90           m_stride(stride),
  91           m_index_expr(index_expr)
  92     {
  93     }
  94
  95     const Iterator m_input_iter;
  96     const Stride m_stride;
  97     const IndexExpr m_index_expr;
  98 };
  99
 100 template<class Iterator, class Stride, class IndexExpr>
 101 inline meta_kernel& operator<<(meta_kernel &kernel,
 102                                const strided_iterator_index_expr<Iterator,
 103                                                                  Stride,
 104                                                                  IndexExpr> &expr)
 105 {
 106     return kernel << expr.m_input_iter[make_stride_expr(expr.m_index_expr, expr.m_stride)];
 107 }
 108
 109 } // end detail namespace
 110
 111 /// \class strided_iterator
 112 /// \brief An iterator adaptor with adjustable iteration step.
 113 ///
 114 /// The strided iterator adaptor skips over multiple elements each time
 115 /// it is incremented or decremented.
 116 ///
 117 /// \see buffer_iterator, make_strided_iterator(), make_strided_iterator_end()
 118 template<class Iterator>
 119 class strided_iterator :
 120     public detail::strided_iterator_base<Iterator>::type
 121 {
 122 public:
 123     typedef typename
 124         detail::strided_iterator_base<Iterator>::type super_type;
 125     typedef typename super_type::value_type value_type;
 126     typedef typename super_type::reference reference;
 127     typedef typename super_type::base_type base_type;
 128     typedef typename super_type::difference_type difference_type;
 129
 130     strided_iterator(Iterator iterator, difference_type stride)
 131         : super_type(iterator),
 132           m_stride(static_cast<difference_type>(stride))
 133     {
 134         // stride must be greater than zero
 135         BOOST_ASSERT_MSG(stride > 0, "Stride must be greater than zero");
 136     }
 137
 138     strided_iterator(const strided_iterator<Iterator> &other)
 139         : super_type(other.base()),
 140           m_stride(other.m_stride)
 141     {
 142     }
 143
 144     strided_iterator<Iterator>&
 145     operator=(const strided_iterator<Iterator> &other)
 146     {
 147         if(this != &other){
 148             super_type::operator=(other);
 149
 150             m_stride = other.m_stride;
 151         }
 152
 153         return *this;
 154     }
 155
 156     ~strided_iterator()
 157     {
 158     }
 159
 160     size_t get_index() const
 161     {
 162         return super_type::base().get_index();
 163     }
 164
 165     const buffer& get_buffer() const
 166     {
 167         return detail::get_base_iterator_buffer(*this);
 168     }
 169
 170     template<class IndexExpression>
 171     detail::strided_iterator_index_expr<Iterator, difference_type, IndexExpression>
 172     operator[](const IndexExpression &expr) const
 173     {
 174         typedef
 175             typename detail::strided_iterator_index_expr<Iterator,
 176                                                          difference_type,
 177                                                          IndexExpression>
 178             StridedIndexExprType;
 179         return StridedIndexExprType(super_type::base(),m_stride, expr);
 180     }
 181
 182 private:
 183     friend class ::boost::iterator_core_access;
 184
 185     reference dereference() const
 186     {
 187         return reference();
 188     }
 189
 190     bool equal(const strided_iterator<Iterator> &other) const
 191     {
 192         return (other.m_stride == m_stride)
 193                    && (other.base_reference() == this->base_reference());
 194     }
 195
 196     void increment()
 197     {
 198         std::advance(super_type::base_reference(), m_stride);
 199     }
 200
 201     void decrement()
 202     {
 203         std::advance(super_type::base_reference(),-m_stride);
 204     }
 205
 206     void advance(typename super_type::difference_type n)
 207     {
 208         std::advance(super_type::base_reference(), n * m_stride);
 209     }
 210
 211     difference_type distance_to(const strided_iterator<Iterator> &other) const
 212     {
 213         return std::distance(this->base_reference(), other.base_reference()) / m_stride;
 214     }
 215
 216 private:
 217     difference_type m_stride;
 218 };
 219
 220 /// Returns a strided_iterator for \p iterator with \p stride.
 221 ///
 222 /// \param iterator the underlying iterator
 223 /// \param stride the iteration step for strided_iterator
 224 ///
 225 /// \return a \c strided_iterator for \p iterator with \p stride.
 226 ///
 227 /// For example, to create an iterator which iterates over every other
 228 /// element in a \c vector<int>:
 229 /// \code
 230 /// auto strided_iterator = make_strided_iterator(vec.begin(), 2);
 231 /// \endcode
 232 template<class Iterator>
 233 inline strided_iterator<Iterator>
 234 make_strided_iterator(Iterator iterator,
 235                       typename std::iterator_traits<Iterator>::difference_type stride)
 236 {
 237     return strided_iterator<Iterator>(iterator, stride);
 238 }
 239
 240 /// Returns a strided_iterator which refers to element that would follow
 241 /// the last element accessible through strided_iterator for \p first iterator
 242 /// with \p stride.
 243 ///
 244 /// Parameter \p stride must be greater than zero.
 245 ///
 246 /// \param first the iterator referring to the first element accessible
 247 ///        through strided_iterator for \p first with \p stride
 248 /// \param last the iterator referring to the last element that may be
 249 ////       accessible through strided_iterator for \p first with \p stride
 250 /// \param stride the iteration step
 251 ///
 252 /// \return a \c strided_iterator referring to element that would follow
 253 ///         the last element accessible through strided_iterator for \p first
 254 ///         iterator with \p stride.
 255 ///
 256 /// It can be helpful when iterating over strided_iterator:
 257 /// \code
 258 /// // vec.size() may not be divisible by 3
 259 /// auto strided_iterator_begin = make_strided_iterator(vec.begin(), 3);
 260 /// auto strided_iterator_end = make_strided_iterator_end(vec.begin(), vec.end(), 3);
 261 ///
 262 /// // copy every 3rd element to result
 263 /// boost::compute::copy(
 264 ///         strided_iterator_begin,
 265 ///         strided_iterator_end,
 266 ///         result.begin(),
 267 ///         queue
 268 /// );
 269 /// \endcode
 270 template<class Iterator>
 271 strided_iterator<Iterator>
 272 make_strided_iterator_end(Iterator first,
 273                           Iterator last,
 274                           typename std::iterator_traits<Iterator>::difference_type stride)
 275 {
 276     typedef typename std::iterator_traits<Iterator>::difference_type difference_type;
 277
 278     // calculate distance from end to the last element that would be
 279     // accessible through strided_iterator.
 280     difference_type range = std::distance(first, last);
 281     difference_type d = (range - 1) / stride;
 282     d *= stride;
 283     d -= range;
 284     // advance from end to the element that would follow the last
 285     // accessible element
 286     Iterator end_for_strided_iterator = last;
 287     std::advance(end_for_strided_iterator, d + stride);
 288     return strided_iterator<Iterator>(end_for_strided_iterator, stride);
 289 }
 290
 291 /// \internal_ (is_device_iterator specialization for strided_iterator)
 292 template<class Iterator>
 293 struct is_device_iterator<strided_iterator<Iterator> > : boost::true_type {};
 294
 295 } // end compute namespace
 296 } // end boost namespace
 297
 298 #endif // BOOST_COMPUTE_ITERATOR_STRIDED_ITERATOR_HPP