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