LLVM  14.0.0git
iterator.h
Go to the documentation of this file.
1 //===- iterator.h - Utilities for using and defining iterators --*- C++ -*-===//
2 //
3 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
4 // See https://llvm.org/LICENSE.txt for license information.
5 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
6 //
7 //===----------------------------------------------------------------------===//
8 
9 #ifndef LLVM_ADT_ITERATOR_H
10 #define LLVM_ADT_ITERATOR_H
11 
13 #include <cstddef>
14 #include <iterator>
15 #include <type_traits>
16 #include <utility>
17 
18 namespace llvm {
19 
20 /// CRTP base class which implements the entire standard iterator facade
21 /// in terms of a minimal subset of the interface.
22 ///
23 /// Use this when it is reasonable to implement most of the iterator
24 /// functionality in terms of a core subset. If you need special behavior or
25 /// there are performance implications for this, you may want to override the
26 /// relevant members instead.
27 ///
28 /// Note, one abstraction that this does *not* provide is implementing
29 /// subtraction in terms of addition by negating the difference. Negation isn't
30 /// always information preserving, and I can see very reasonable iterator
31 /// designs where this doesn't work well. It doesn't really force much added
32 /// boilerplate anyways.
33 ///
34 /// Another abstraction that this doesn't provide is implementing increment in
35 /// terms of addition of one. These aren't equivalent for all iterator
36 /// categories, and respecting that adds a lot of complexity for little gain.
37 ///
38 /// Classes wishing to use `iterator_facade_base` should implement the following
39 /// methods:
40 ///
41 /// Forward Iterators:
42 /// (All of the following methods)
43 /// - DerivedT &operator=(const DerivedT &R);
44 /// - bool operator==(const DerivedT &R) const;
45 /// - const T &operator*() const;
46 /// - T &operator*();
47 /// - DerivedT &operator++();
48 ///
49 /// Bidirectional Iterators:
50 /// (All methods of forward iterators, plus the following)
51 /// - DerivedT &operator--();
52 ///
53 /// Random-access Iterators:
54 /// (All methods of bidirectional iterators excluding the following)
55 /// - DerivedT &operator++();
56 /// - DerivedT &operator--();
57 /// (and plus the following)
58 /// - bool operator<(const DerivedT &RHS) const;
59 /// - DifferenceTypeT operator-(const DerivedT &R) const;
60 /// - DerivedT &operator+=(DifferenceTypeT N);
61 /// - DerivedT &operator-=(DifferenceTypeT N);
62 ///
63 template <typename DerivedT, typename IteratorCategoryT, typename T,
64  typename DifferenceTypeT = std::ptrdiff_t, typename PointerT = T *,
65  typename ReferenceT = T &>
67 public:
68  using iterator_category = IteratorCategoryT;
69  using value_type = T;
70  using difference_type = DifferenceTypeT;
71  using pointer = PointerT;
72  using reference = ReferenceT;
73 
74 protected:
75  enum {
76  IsRandomAccess = std::is_base_of<std::random_access_iterator_tag,
77  IteratorCategoryT>::value,
78  IsBidirectional = std::is_base_of<std::bidirectional_iterator_tag,
79  IteratorCategoryT>::value,
80  };
81 
82  /// A proxy object for computing a reference via indirecting a copy of an
83  /// iterator. This is used in APIs which need to produce a reference via
84  /// indirection but for which the iterator object might be a temporary. The
85  /// proxy preserves the iterator internally and exposes the indirected
86  /// reference via a conversion operator.
88  friend iterator_facade_base;
89 
90  DerivedT I;
91 
92  ReferenceProxy(DerivedT I) : I(std::move(I)) {}
93 
94  public:
95  operator ReferenceT() const { return *I; }
96  };
97 
98  /// A proxy object for computing a pointer via indirecting a copy of a
99  /// reference. This is used in APIs which need to produce a pointer but for
100  /// which the reference might be a temporary. The proxy preserves the
101  /// reference internally and exposes the pointer via a arrow operator.
102  class PointerProxy {
103  friend iterator_facade_base;
104 
105  ReferenceT R;
106 
107  template <typename RefT>
108  PointerProxy(RefT &&R) : R(std::forward<RefT>(R)) {}
109 
110  public:
111  PointerT operator->() const { return &R; }
112  };
113 
114 public:
115  DerivedT operator+(DifferenceTypeT n) const {
116  static_assert(std::is_base_of<iterator_facade_base, DerivedT>::value,
117  "Must pass the derived type to this template!");
118  static_assert(
120  "The '+' operator is only defined for random access iterators.");
121  DerivedT tmp = *static_cast<const DerivedT *>(this);
122  tmp += n;
123  return tmp;
124  }
125  friend DerivedT operator+(DifferenceTypeT n, const DerivedT &i) {
126  static_assert(
128  "The '+' operator is only defined for random access iterators.");
129  return i + n;
130  }
131  DerivedT operator-(DifferenceTypeT n) const {
132  static_assert(
134  "The '-' operator is only defined for random access iterators.");
135  DerivedT tmp = *static_cast<const DerivedT *>(this);
136  tmp -= n;
137  return tmp;
138  }
139 
140  DerivedT &operator++() {
141  static_assert(std::is_base_of<iterator_facade_base, DerivedT>::value,
142  "Must pass the derived type to this template!");
143  return static_cast<DerivedT *>(this)->operator+=(1);
144  }
145  DerivedT operator++(int) {
146  DerivedT tmp = *static_cast<DerivedT *>(this);
147  ++*static_cast<DerivedT *>(this);
148  return tmp;
149  }
150  DerivedT &operator--() {
151  static_assert(
153  "The decrement operator is only defined for bidirectional iterators.");
154  return static_cast<DerivedT *>(this)->operator-=(1);
155  }
156  DerivedT operator--(int) {
157  static_assert(
159  "The decrement operator is only defined for bidirectional iterators.");
160  DerivedT tmp = *static_cast<DerivedT *>(this);
161  --*static_cast<DerivedT *>(this);
162  return tmp;
163  }
164 
165 #ifndef __cpp_impl_three_way_comparison
166  bool operator!=(const DerivedT &RHS) const {
167  return !(static_cast<const DerivedT &>(*this) == RHS);
168  }
169 #endif
170 
171  bool operator>(const DerivedT &RHS) const {
172  static_assert(
174  "Relational operators are only defined for random access iterators.");
175  return !(static_cast<const DerivedT &>(*this) < RHS) &&
176  !(static_cast<const DerivedT &>(*this) == RHS);
177  }
178  bool operator<=(const DerivedT &RHS) const {
179  static_assert(
181  "Relational operators are only defined for random access iterators.");
182  return !(static_cast<const DerivedT &>(*this) > RHS);
183  }
184  bool operator>=(const DerivedT &RHS) const {
185  static_assert(
187  "Relational operators are only defined for random access iterators.");
188  return !(static_cast<const DerivedT &>(*this) < RHS);
189  }
190 
191  PointerProxy operator->() {
192  return static_cast<DerivedT *>(this)->operator*();
193  }
194  PointerProxy operator->() const {
195  return static_cast<const DerivedT *>(this)->operator*();
196  }
197  ReferenceProxy operator[](DifferenceTypeT n) {
198  static_assert(IsRandomAccess,
199  "Subscripting is only defined for random access iterators.");
200  return static_cast<DerivedT *>(this)->operator+(n);
201  }
202  ReferenceProxy operator[](DifferenceTypeT n) const {
203  static_assert(IsRandomAccess,
204  "Subscripting is only defined for random access iterators.");
205  return static_cast<const DerivedT *>(this)->operator+(n);
206  }
207 };
208 
209 /// CRTP base class for adapting an iterator to a different type.
210 ///
211 /// This class can be used through CRTP to adapt one iterator into another.
212 /// Typically this is done through providing in the derived class a custom \c
213 /// operator* implementation. Other methods can be overridden as well.
214 template <
215  typename DerivedT, typename WrappedIteratorT,
216  typename IteratorCategoryT =
217  typename std::iterator_traits<WrappedIteratorT>::iterator_category,
218  typename T = typename std::iterator_traits<WrappedIteratorT>::value_type,
219  typename DifferenceTypeT =
220  typename std::iterator_traits<WrappedIteratorT>::difference_type,
221  typename PointerT = std::conditional_t<
222  std::is_same<T, typename std::iterator_traits<
223  WrappedIteratorT>::value_type>::value,
225  typename ReferenceT = std::conditional_t<
226  std::is_same<T, typename std::iterator_traits<
227  WrappedIteratorT>::value_type>::value,
228  typename std::iterator_traits<WrappedIteratorT>::reference, T &>>
230  : public iterator_facade_base<DerivedT, IteratorCategoryT, T,
231  DifferenceTypeT, PointerT, ReferenceT> {
232  using BaseT = typename iterator_adaptor_base::iterator_facade_base;
233 
234 protected:
236 
237  iterator_adaptor_base() = default;
238 
240  static_assert(std::is_base_of<iterator_adaptor_base, DerivedT>::value,
241  "Must pass the derived type to this template!");
242  }
243 
244  const WrappedIteratorT &wrapped() const { return I; }
245 
246 public:
247  using difference_type = DifferenceTypeT;
248 
250  static_assert(
251  BaseT::IsRandomAccess,
252  "The '+=' operator is only defined for random access iterators.");
253  I += n;
254  return *static_cast<DerivedT *>(this);
255  }
257  static_assert(
258  BaseT::IsRandomAccess,
259  "The '-=' operator is only defined for random access iterators.");
260  I -= n;
261  return *static_cast<DerivedT *>(this);
262  }
263  using BaseT::operator-;
264  difference_type operator-(const DerivedT &RHS) const {
265  static_assert(
266  BaseT::IsRandomAccess,
267  "The '-' operator is only defined for random access iterators.");
268  return I - RHS.I;
269  }
270 
271  // We have to explicitly provide ++ and -- rather than letting the facade
272  // forward to += because WrappedIteratorT might not support +=.
273  using BaseT::operator++;
274  DerivedT &operator++() {
275  ++I;
276  return *static_cast<DerivedT *>(this);
277  }
278  using BaseT::operator--;
279  DerivedT &operator--() {
280  static_assert(
281  BaseT::IsBidirectional,
282  "The decrement operator is only defined for bidirectional iterators.");
283  --I;
284  return *static_cast<DerivedT *>(this);
285  }
286 
287  friend bool operator==(const iterator_adaptor_base &LHS,
288  const iterator_adaptor_base &RHS) {
289  return LHS.I == RHS.I;
290  }
291  friend bool operator<(const iterator_adaptor_base &LHS,
292  const iterator_adaptor_base &RHS) {
293  static_assert(
294  BaseT::IsRandomAccess,
295  "Relational operators are only defined for random access iterators.");
296  return LHS.I < RHS.I;
297  }
298 
299  ReferenceT operator*() const { return *I; }
300 };
301 
302 /// An iterator type that allows iterating over the pointees via some
303 /// other iterator.
304 ///
305 /// The typical usage of this is to expose a type that iterates over Ts, but
306 /// which is implemented with some iterator over T*s:
307 ///
308 /// \code
309 /// using iterator = pointee_iterator<SmallVectorImpl<T *>::iterator>;
310 /// \endcode
311 template <typename WrappedIteratorT,
312  typename T = std::remove_reference_t<decltype(
313  **std::declval<WrappedIteratorT>())>>
316  pointee_iterator<WrappedIteratorT, T>, WrappedIteratorT,
317  typename std::iterator_traits<WrappedIteratorT>::iterator_category,
318  T> {
319  pointee_iterator() = default;
320  template <typename U>
322  : pointee_iterator::iterator_adaptor_base(std::forward<U &&>(u)) {}
323 
324  T &operator*() const { return **this->I; }
325 };
326 
327 template <typename RangeT, typename WrappedIteratorT =
328  decltype(std::begin(std::declval<RangeT>()))>
329 iterator_range<pointee_iterator<WrappedIteratorT>>
330 make_pointee_range(RangeT &&Range) {
331  using PointeeIteratorT = pointee_iterator<WrappedIteratorT>;
332  return make_range(PointeeIteratorT(std::begin(std::forward<RangeT>(Range))),
333  PointeeIteratorT(std::end(std::forward<RangeT>(Range))));
334 }
335 
336 template <typename WrappedIteratorT,
337  typename T = decltype(&*std::declval<WrappedIteratorT>())>
339  : public iterator_adaptor_base<
340  pointer_iterator<WrappedIteratorT, T>, WrappedIteratorT,
341  typename std::iterator_traits<WrappedIteratorT>::iterator_category,
342  T> {
343  mutable T Ptr;
344 
345 public:
346  pointer_iterator() = default;
347 
350 
351  T &operator*() { return Ptr = &*this->I; }
352  const T &operator*() const { return Ptr = &*this->I; }
353 };
354 
355 template <typename RangeT, typename WrappedIteratorT =
356  decltype(std::begin(std::declval<RangeT>()))>
357 iterator_range<pointer_iterator<WrappedIteratorT>>
358 make_pointer_range(RangeT &&Range) {
359  using PointerIteratorT = pointer_iterator<WrappedIteratorT>;
360  return make_range(PointerIteratorT(std::begin(std::forward<RangeT>(Range))),
361  PointerIteratorT(std::end(std::forward<RangeT>(Range))));
362 }
363 
364 template <typename WrappedIteratorT,
365  typename T1 = std::remove_reference_t<decltype(
366  **std::declval<WrappedIteratorT>())>,
367  typename T2 = std::add_pointer_t<T1>>
368 using raw_pointer_iterator =
370 
371 } // end namespace llvm
372 
373 #endif // LLVM_ADT_ITERATOR_H
i
i
Definition: README.txt:29
llvm
This file implements support for optimizing divisions by a constant.
Definition: AllocatorList.h:23
llvm::make_range
iterator_range< T > make_range(T x, T y)
Convenience function for iterating over sub-ranges.
Definition: iterator_range.h:53
pointer
Replace within non kernel function use of LDS with pointer
Definition: AMDGPUReplaceLDSUseWithPointer.cpp:443
llvm::iterator_facade_base< partition_iterator, std::forward_iterator_tag, Partition >::pointer
Partition * pointer
Definition: iterator.h:71
llvm::iterator_facade_base::operator++
DerivedT operator++(int)
Definition: iterator.h:145
llvm::pointee_iterator::pointee_iterator
pointee_iterator(U &&u)
Definition: iterator.h:321
llvm::iterator_adaptor_base::I
WrappedIteratorT I
Definition: iterator.h:235
llvm::iterator_facade_base::operator->
PointerProxy operator->() const
Definition: iterator.h:194
llvm::iterator_adaptor_base::operator-=
DerivedT & operator-=(difference_type n)
Definition: iterator.h:256
llvm::iterator_facade_base::operator[]
ReferenceProxy operator[](DifferenceTypeT n) const
Definition: iterator.h:202
llvm::iterator_facade_base::operator++
DerivedT & operator++()
Definition: iterator.h:140
llvm::pointee_iterator::operator*
T & operator*() const
Definition: iterator.h:324
llvm::sys::path::end
const_iterator end(StringRef path)
Get end iterator over path.
Definition: Path.cpp:233
llvm::sys::path::begin
const_iterator begin(StringRef path, Style style=Style::native)
Get begin iterator over path.
Definition: Path.cpp:224
llvm::iterator_adaptor_base
CRTP base class for adapting an iterator to a different type.
Definition: iterator.h:229
llvm::iterator_adaptor_base::iterator_adaptor_base
iterator_adaptor_base()=default
T1
#define T1
Definition: Mips16ISelLowering.cpp:340
T
#define T
Definition: Mips16ISelLowering.cpp:341
llvm::iterator_facade_base< partition_iterator, std::forward_iterator_tag, Partition >::value_type
Partition value_type
Definition: iterator.h:69
llvm::iterator_adaptor_base::wrapped
const WrappedIteratorT & wrapped() const
Definition: iterator.h:244
tmp
alloca< 16 x float >, align 16 %tmp2=alloca< 16 x float >, align 16 store< 16 x float > %A,< 16 x float > *%tmp %s=bitcast< 16 x float > *%tmp to i8 *%s2=bitcast< 16 x float > *%tmp2 to i8 *call void @llvm.memcpy.i64(i8 *%s, i8 *%s2, i64 64, i32 16) %R=load< 16 x float > *%tmp2 ret< 16 x float > %R } declare void @llvm.memcpy.i64(i8 *nocapture, i8 *nocapture, i64, i32) nounwind which compiles to:_foo:subl $140, %esp movaps %xmm3, 112(%esp) movaps %xmm2, 96(%esp) movaps %xmm1, 80(%esp) movaps %xmm0, 64(%esp) movl 60(%esp), %eax movl %eax, 124(%esp) movl 56(%esp), %eax movl %eax, 120(%esp) movl 52(%esp), %eax< many many more 32-bit copies > movaps(%esp), %xmm0 movaps 16(%esp), %xmm1 movaps 32(%esp), %xmm2 movaps 48(%esp), %xmm3 addl $140, %esp ret On Nehalem, it may even be cheaper to just use movups when unaligned than to fall back to lower-granularity chunks. Implement processor-specific optimizations for parity with GCC on these processors. GCC does two optimizations:1. ix86_pad_returns inserts a noop before ret instructions if immediately preceded by a conditional branch or is the target of a jump. 2. ix86_avoid_jump_misspredicts inserts noops in cases where a 16-byte block of code contains more than 3 branches. The first one is done for all AMDs, Core2, and "Generic" The second one is done for:Atom, Pentium Pro, all AMDs, Pentium 4, Nocona, Core 2, and "Generic" Testcase:int x(int a) { return(a &0xf0)> >4 tmp
Definition: README.txt:1347
llvm::iterator_adaptor_base::operator+=
DerivedT & operator+=(difference_type n)
Definition: iterator.h:249
llvm::raw_pointer_iterator
pointer_iterator< pointee_iterator< WrappedIteratorT, T1 >, T2 > raw_pointer_iterator
Definition: iterator.h:369
llvm::pointee_iterator::pointee_iterator
pointee_iterator()=default
llvm::iterator_facade_base::IsBidirectional
@ IsBidirectional
Definition: iterator.h:78
llvm::iterator_facade_base::operator+
DerivedT operator+(DifferenceTypeT n) const
Definition: iterator.h:115
llvm::pointer_iterator::operator*
T & operator*()
Definition: iterator.h:351
llvm::iterator_facade_base::operator+
friend DerivedT operator+(DifferenceTypeT n, const DerivedT &i)
Definition: iterator.h:125
llvm::iterator_adaptor_base::operator==
friend bool operator==(const iterator_adaptor_base &LHS, const iterator_adaptor_base &RHS)
Definition: iterator.h:287
llvm::pointer_iterator::operator*
const T & operator*() const
Definition: iterator.h:352
llvm::iterator_facade_base::PointerProxy::operator->
PointerT operator->() const
Definition: iterator.h:111
llvm::iterator_facade_base::operator!=
bool operator!=(const DerivedT &RHS) const
Definition: iterator.h:166
llvm::iterator_facade_base< partition_iterator, std::forward_iterator_tag, Partition >::reference
Partition & reference
Definition: iterator.h:72
llvm::pointer_iterator
Definition: iterator.h:338
llvm::iterator_facade_base::operator>
bool operator>(const DerivedT &RHS) const
Definition: iterator.h:171
move
compiles ldr LCPI1_0 ldr ldr mov lsr tst moveq r1 ldr LCPI1_1 and r0 bx lr It would be better to do something like to fold the shift into the conditional move
Definition: README.txt:546
llvm::iterator_facade_base::PointerProxy
A proxy object for computing a pointer via indirecting a copy of a reference.
Definition: iterator.h:102
I
#define I(x, y, z)
Definition: MD5.cpp:59
llvm::iterator_facade_base
CRTP base class which implements the entire standard iterator facade in terms of a minimal subset of ...
Definition: iterator.h:66
llvm::iterator_facade_base::IsRandomAccess
@ IsRandomAccess
Definition: iterator.h:76
llvm::iterator_facade_base::operator-
DerivedT operator-(DifferenceTypeT n) const
Definition: iterator.h:131
llvm::iterator_adaptor_base::iterator_adaptor_base
iterator_adaptor_base(WrappedIteratorT u)
Definition: iterator.h:239
llvm::make_pointee_range
iterator_range< pointee_iterator< WrappedIteratorT > > make_pointee_range(RangeT &&Range)
Definition: iterator.h:330
llvm::move
OutputIt move(R &&Range, OutputIt Out)
Provide wrappers to std::move which take ranges instead of having to pass begin/end explicitly.
Definition: STLExtras.h:1609
llvm::iterator_facade_base< partition_iterator, std::forward_iterator_tag, Partition >::difference_type
std::ptrdiff_t difference_type
Definition: iterator.h:70
iterator_range.h
llvm::iterator_adaptor_base::operator<
friend bool operator<(const iterator_adaptor_base &LHS, const iterator_adaptor_base &RHS)
Definition: iterator.h:291
llvm::iterator_facade_base::operator->
PointerProxy operator->()
Definition: iterator.h:191
llvm::make_pointer_range
iterator_range< pointer_iterator< WrappedIteratorT > > make_pointer_range(RangeT &&Range)
Definition: iterator.h:358
llvm::iterator_facade_base::operator--
DerivedT operator--(int)
Definition: iterator.h:156
llvm::iterator_facade_base::operator[]
ReferenceProxy operator[](DifferenceTypeT n)
Definition: iterator.h:197
std
Definition: BitVector.h:838
llvm::iterator_facade_base::operator>=
bool operator>=(const DerivedT &RHS) const
Definition: iterator.h:184
llvm::iterator_adaptor_base::operator-
difference_type operator-(const DerivedT &RHS) const
Definition: iterator.h:264
llvm::iterator_adaptor_base::operator--
DerivedT & operator--()
Definition: iterator.h:279
llvm::iterator_adaptor_base::operator++
DerivedT & operator++()
Definition: iterator.h:274
llvm::iterator_facade_base::operator<=
bool operator<=(const DerivedT &RHS) const
Definition: iterator.h:178
llvm::iterator_adaptor_base::operator*
ReferenceT operator*() const
Definition: iterator.h:299
llvm::pointee_iterator
An iterator type that allows iterating over the pointees via some other iterator.
Definition: iterator.h:314
llvm::iterator_facade_base< partition_iterator, std::forward_iterator_tag, Partition >::iterator_category
std::forward_iterator_tag iterator_category
Definition: iterator.h:68
n
The same transformation can work with an even modulo with the addition of a and shrink the compare RHS by the same amount Unless the target supports that transformation probably isn t worthwhile The transformation can also easily be made to work with non zero equality for n
Definition: README.txt:685
llvm::iterator_facade_base::operator--
DerivedT & operator--()
Definition: iterator.h:150
WrappedIteratorT
llvm::pointer_iterator::pointer_iterator
pointer_iterator()=default
llvm::pointer_iterator::pointer_iterator
pointer_iterator(WrappedIteratorT u)
Definition: iterator.h:348
llvm::iterator_facade_base::ReferenceProxy
A proxy object for computing a reference via indirecting a copy of an iterator.
Definition: iterator.h:87