1 | /* |
2 | Copyright (c) 2017-2019 Intel Corporation |
3 | |
4 | Licensed under the Apache License, Version 2.0 (the "License"); |
5 | you may not use this file except in compliance with the License. |
6 | You may obtain a copy of the License at |
7 | |
8 | http://www.apache.org/licenses/LICENSE-2.0 |
9 | |
10 | Unless required by applicable law or agreed to in writing, software |
11 | distributed under the License is distributed on an "AS IS" BASIS, |
12 | WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. |
13 | See the License for the specific language governing permissions and |
14 | limitations under the License. |
15 | */ |
16 | |
17 | #ifndef __TBB_iterators_H |
18 | #define __TBB_iterators_H |
19 | |
20 | #include <iterator> |
21 | #include <limits> |
22 | |
23 | #include "tbb_config.h" |
24 | #include "tbb_stddef.h" |
25 | |
26 | #if __TBB_CPP11_PRESENT |
27 | |
28 | #include <type_traits> |
29 | |
30 | namespace tbb { |
31 | |
32 | template <typename IntType> |
33 | class counting_iterator { |
34 | __TBB_STATIC_ASSERT(std::numeric_limits<IntType>::is_integer, "Cannot instantiate counting_iterator with a non-integer type" ); |
35 | public: |
36 | typedef typename std::make_signed<IntType>::type difference_type; |
37 | typedef IntType value_type; |
38 | typedef const IntType* pointer; |
39 | typedef const IntType& reference; |
40 | typedef std::random_access_iterator_tag iterator_category; |
41 | |
42 | counting_iterator() : my_counter() {} |
43 | explicit counting_iterator(IntType init) : my_counter(init) {} |
44 | |
45 | reference operator*() const { return my_counter; } |
46 | value_type operator[](difference_type i) const { return *(*this + i); } |
47 | |
48 | difference_type operator-(const counting_iterator& it) const { return my_counter - it.my_counter; } |
49 | |
50 | counting_iterator& operator+=(difference_type forward) { my_counter += forward; return *this; } |
51 | counting_iterator& operator-=(difference_type backward) { return *this += -backward; } |
52 | counting_iterator& operator++() { return *this += 1; } |
53 | counting_iterator& operator--() { return *this -= 1; } |
54 | |
55 | counting_iterator operator++(int) { |
56 | counting_iterator it(*this); |
57 | ++(*this); |
58 | return it; |
59 | } |
60 | counting_iterator operator--(int) { |
61 | counting_iterator it(*this); |
62 | --(*this); |
63 | return it; |
64 | } |
65 | |
66 | counting_iterator operator-(difference_type backward) const { return counting_iterator(my_counter - backward); } |
67 | counting_iterator operator+(difference_type forward) const { return counting_iterator(my_counter + forward); } |
68 | friend counting_iterator operator+(difference_type forward, const counting_iterator it) { return it + forward; } |
69 | |
70 | bool operator==(const counting_iterator& it) const { return *this - it == 0; } |
71 | bool operator!=(const counting_iterator& it) const { return !(*this == it); } |
72 | bool operator<(const counting_iterator& it) const {return *this - it < 0; } |
73 | bool operator>(const counting_iterator& it) const { return it < *this; } |
74 | bool operator<=(const counting_iterator& it) const { return !(*this > it); } |
75 | bool operator>=(const counting_iterator& it) const { return !(*this < it); } |
76 | |
77 | private: |
78 | IntType my_counter; |
79 | }; |
80 | } //namespace tbb |
81 | |
82 | |
83 | #include <tuple> |
84 | |
85 | #include "internal/_template_helpers.h" // index_sequence, make_index_sequence |
86 | |
87 | namespace tbb { |
88 | namespace internal { |
89 | |
90 | template<size_t N> |
91 | struct tuple_util { |
92 | template<typename TupleType, typename DifferenceType> |
93 | static void increment(TupleType& it, DifferenceType forward) { |
94 | std::get<N-1>(it) += forward; |
95 | tuple_util<N-1>::increment(it, forward); |
96 | } |
97 | template<typename TupleType, typename DifferenceType> |
98 | static bool check_sync(const TupleType& it1, const TupleType& it2, DifferenceType val) { |
99 | if(std::get<N-1>(it1) - std::get<N-1>(it2) != val) |
100 | return false; |
101 | return tuple_util<N-1>::check_sync(it1, it2, val); |
102 | } |
103 | }; |
104 | |
105 | template<> |
106 | struct tuple_util<0> { |
107 | template<typename TupleType, typename DifferenceType> |
108 | static void increment(TupleType&, DifferenceType) {} |
109 | template<typename TupleType, typename DifferenceType> |
110 | static bool check_sync(const TupleType&, const TupleType&, DifferenceType) { return true;} |
111 | }; |
112 | |
113 | template <typename TupleReturnType> |
114 | struct make_references { |
115 | template <typename TupleType, std::size_t... Is> |
116 | TupleReturnType operator()(const TupleType& t, tbb::internal::index_sequence<Is...>) { |
117 | return std::tie( *std::get<Is>(t)... ); |
118 | } |
119 | }; |
120 | |
121 | // A simple wrapper over a tuple of references. |
122 | // The class is designed to hold a temporary tuple of reference |
123 | // after dereferencing a zip_iterator; in particular, it is needed |
124 | // to swap these rvalue tuples. Any other usage is not supported. |
125 | template<typename... T> |
126 | struct tuplewrapper : public std::tuple<typename std::enable_if<std::is_reference<T>::value, T&&>::type...> { |
127 | // In the context of this class, T is a reference, so T&& is a "forwarding reference" |
128 | typedef std::tuple<T&&...> base_type; |
129 | // Construct from the result of std::tie |
130 | tuplewrapper(const base_type& in) : base_type(in) {} |
131 | #if __INTEL_COMPILER |
132 | // ICC cannot generate copy ctor & assignment |
133 | tuplewrapper(const tuplewrapper& rhs) : base_type(rhs) {} |
134 | tuplewrapper& operator=(const tuplewrapper& rhs) { |
135 | *this = base_type(rhs); |
136 | return *this; |
137 | } |
138 | #endif |
139 | // Assign any tuple convertible to std::tuple<T&&...>: *it = a_tuple; |
140 | template<typename... U> |
141 | tuplewrapper& operator=(const std::tuple<U...>& other) { |
142 | base_type::operator=(other); |
143 | return *this; |
144 | } |
145 | #if _LIBCPP_VERSION |
146 | // (Necessary for libc++ tuples) Convert to a tuple of values: v = *it; |
147 | operator std::tuple<typename std::remove_reference<T>::type...>() { return base_type(*this); } |
148 | #endif |
149 | // Swap rvalue tuples: swap(*it1,*it2); |
150 | friend void swap(tuplewrapper&& a, tuplewrapper&& b) { |
151 | std::swap<T&&...>(a,b); |
152 | } |
153 | }; |
154 | |
155 | } //namespace internal |
156 | |
157 | template <typename... Types> |
158 | class zip_iterator { |
159 | __TBB_STATIC_ASSERT(sizeof...(Types), "Cannot instantiate zip_iterator with empty template parameter pack" ); |
160 | static const std::size_t num_types = sizeof...(Types); |
161 | typedef std::tuple<Types...> it_types; |
162 | public: |
163 | typedef typename std::make_signed<std::size_t>::type difference_type; |
164 | typedef std::tuple<typename std::iterator_traits<Types>::value_type...> value_type; |
165 | #if __INTEL_COMPILER && __INTEL_COMPILER < 1800 && _MSC_VER |
166 | typedef std::tuple<typename std::iterator_traits<Types>::reference...> reference; |
167 | #else |
168 | typedef tbb::internal::tuplewrapper<typename std::iterator_traits<Types>::reference...> reference; |
169 | #endif |
170 | typedef std::tuple<typename std::iterator_traits<Types>::pointer...> pointer; |
171 | typedef std::random_access_iterator_tag iterator_category; |
172 | |
173 | zip_iterator() : my_it() {} |
174 | explicit zip_iterator(Types... args) : my_it(std::make_tuple(args...)) {} |
175 | zip_iterator(const zip_iterator& input) : my_it(input.my_it) {} |
176 | zip_iterator& operator=(const zip_iterator& input) { |
177 | my_it = input.my_it; |
178 | return *this; |
179 | } |
180 | |
181 | reference operator*() const { |
182 | return tbb::internal::make_references<reference>()(my_it, tbb::internal::make_index_sequence<num_types>()); |
183 | } |
184 | reference operator[](difference_type i) const { return *(*this + i); } |
185 | |
186 | difference_type operator-(const zip_iterator& it) const { |
187 | __TBB_ASSERT(internal::tuple_util<num_types>::check_sync(my_it, it.my_it, std::get<0>(my_it) - std::get<0>(it.my_it)), |
188 | "Components of zip_iterator are not synchronous" ); |
189 | return std::get<0>(my_it) - std::get<0>(it.my_it); |
190 | } |
191 | |
192 | zip_iterator& operator+=(difference_type forward) { |
193 | internal::tuple_util<num_types>::increment(my_it, forward); |
194 | return *this; |
195 | } |
196 | zip_iterator& operator-=(difference_type backward) { return *this += -backward; } |
197 | zip_iterator& operator++() { return *this += 1; } |
198 | zip_iterator& operator--() { return *this -= 1; } |
199 | |
200 | zip_iterator operator++(int) { |
201 | zip_iterator it(*this); |
202 | ++(*this); |
203 | return it; |
204 | } |
205 | zip_iterator operator--(int) { |
206 | zip_iterator it(*this); |
207 | --(*this); |
208 | return it; |
209 | } |
210 | |
211 | zip_iterator operator-(difference_type backward) const { |
212 | zip_iterator it(*this); |
213 | return it -= backward; |
214 | } |
215 | zip_iterator operator+(difference_type forward) const { |
216 | zip_iterator it(*this); |
217 | return it += forward; |
218 | } |
219 | friend zip_iterator operator+(difference_type forward, const zip_iterator& it) { return it + forward; } |
220 | |
221 | bool operator==(const zip_iterator& it) const { |
222 | return *this - it == 0; |
223 | } |
224 | it_types base() const { return my_it; } |
225 | |
226 | bool operator!=(const zip_iterator& it) const { return !(*this == it); } |
227 | bool operator<(const zip_iterator& it) const { return *this - it < 0; } |
228 | bool operator>(const zip_iterator& it) const { return it < *this; } |
229 | bool operator<=(const zip_iterator& it) const { return !(*this > it); } |
230 | bool operator>=(const zip_iterator& it) const { return !(*this < it); } |
231 | private: |
232 | it_types my_it; |
233 | }; |
234 | |
235 | template<typename... T> |
236 | zip_iterator<T...> make_zip_iterator(T... args) { return zip_iterator<T...>(args...); } |
237 | |
238 | template <typename UnaryFunc, typename Iter> |
239 | class transform_iterator { |
240 | public: |
241 | typedef typename std::iterator_traits<Iter>::value_type value_type; |
242 | typedef typename std::iterator_traits<Iter>::difference_type difference_type; |
243 | #if __TBB_CPP17_INVOKE_RESULT_PRESENT |
244 | typedef typename std::invoke_result<UnaryFunc, typename std::iterator_traits<Iter>::reference>::type reference; |
245 | #else |
246 | typedef typename std::result_of<UnaryFunc(typename std::iterator_traits<Iter>::reference)>::type reference; |
247 | #endif |
248 | typedef typename std::iterator_traits<Iter>::pointer pointer; |
249 | typedef typename std::random_access_iterator_tag iterator_category; |
250 | |
251 | transform_iterator(Iter it, UnaryFunc unary_func) : my_it(it), my_unary_func(unary_func) { |
252 | __TBB_STATIC_ASSERT((std::is_same<typename std::iterator_traits<Iter>::iterator_category, |
253 | std::random_access_iterator_tag>::value), "Random access iterator required." ); |
254 | } |
255 | transform_iterator(const transform_iterator& input) : my_it(input.my_it), my_unary_func(input.my_unary_func) { } |
256 | transform_iterator& operator=(const transform_iterator& input) { |
257 | my_it = input.my_it; |
258 | return *this; |
259 | } |
260 | reference operator*() const { |
261 | return my_unary_func(*my_it); |
262 | } |
263 | reference operator[](difference_type i) const { |
264 | return *(*this + i); |
265 | } |
266 | transform_iterator& operator++() { |
267 | ++my_it; |
268 | return *this; |
269 | } |
270 | transform_iterator& operator--() { |
271 | --my_it; |
272 | return *this; |
273 | } |
274 | transform_iterator operator++(int) { |
275 | transform_iterator it(*this); |
276 | ++(*this); |
277 | return it; |
278 | } |
279 | transform_iterator operator--(int) { |
280 | transform_iterator it(*this); |
281 | --(*this); |
282 | return it; |
283 | } |
284 | transform_iterator operator+(difference_type forward) const { |
285 | return { my_it + forward, my_unary_func }; |
286 | } |
287 | transform_iterator operator-(difference_type backward) const { |
288 | return { my_it - backward, my_unary_func }; |
289 | } |
290 | transform_iterator& operator+=(difference_type forward) { |
291 | my_it += forward; |
292 | return *this; |
293 | } |
294 | transform_iterator& operator-=(difference_type backward) { |
295 | my_it -= backward; |
296 | return *this; |
297 | } |
298 | friend transform_iterator operator+(difference_type forward, const transform_iterator& it) { |
299 | return it + forward; |
300 | } |
301 | difference_type operator-(const transform_iterator& it) const { |
302 | return my_it - it.my_it; |
303 | } |
304 | bool operator==(const transform_iterator& it) const { return *this - it == 0; } |
305 | bool operator!=(const transform_iterator& it) const { return !(*this == it); } |
306 | bool operator<(const transform_iterator& it) const { return *this - it < 0; } |
307 | bool operator>(const transform_iterator& it) const { return it < *this; } |
308 | bool operator<=(const transform_iterator& it) const { return !(*this > it); } |
309 | bool operator>=(const transform_iterator& it) const { return !(*this < it); } |
310 | |
311 | Iter base() const { return my_it; } |
312 | private: |
313 | Iter my_it; |
314 | const UnaryFunc my_unary_func; |
315 | }; |
316 | |
317 | template<typename UnaryFunc, typename Iter> |
318 | transform_iterator<UnaryFunc, Iter> make_transform_iterator(Iter it, UnaryFunc unary_func) { |
319 | return transform_iterator<UnaryFunc, Iter>(it, unary_func); |
320 | } |
321 | |
322 | } //namespace tbb |
323 | |
324 | #endif //__TBB_CPP11_PRESENT |
325 | |
326 | #endif /* __TBB_iterators_H */ |
327 | |