LLVM  15.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 /// Iterators are expected to have const rules analogous to pointers, with a
39 /// single, const-qualified operator*() that returns ReferenceT. This matches
40 /// the second and third pointers in the following example:
41 /// \code
42 /// int Value;
43 /// { int *I = &Value; } // ReferenceT 'int&'
44 /// { int *const I = &Value; } // ReferenceT 'int&'; const
45 /// { const int *I = &Value; } // ReferenceT 'const int&'
46 /// { const int *const I = &Value; } // ReferenceT 'const int&'; const
47 /// \endcode
48 /// If an iterator facade returns a handle to its own state, then T (and
49 /// PointerT and ReferenceT) should usually be const-qualified. Otherwise, if
50 /// clients are expected to modify the handle itself, the field can be declared
51 /// mutable or use const_cast.
52 ///
53 /// Classes wishing to use `iterator_facade_base` should implement the following
54 /// methods:
55 ///
56 /// Forward Iterators:
57 /// (All of the following methods)
58 /// - DerivedT &operator=(const DerivedT &R);
59 /// - bool operator==(const DerivedT &R) const;
60 /// - T &operator*() const;
61 /// - DerivedT &operator++();
62 ///
63 /// Bidirectional Iterators:
64 /// (All methods of forward iterators, plus the following)
65 /// - DerivedT &operator--();
66 ///
67 /// Random-access Iterators:
68 /// (All methods of bidirectional iterators excluding the following)
69 /// - DerivedT &operator++();
70 /// - DerivedT &operator--();
71 /// (and plus the following)
72 /// - bool operator<(const DerivedT &RHS) const;
73 /// - DifferenceTypeT operator-(const DerivedT &R) const;
74 /// - DerivedT &operator+=(DifferenceTypeT N);
75 /// - DerivedT &operator-=(DifferenceTypeT N);
76 ///
77 template <typename DerivedT, typename IteratorCategoryT, typename T,
78  typename DifferenceTypeT = std::ptrdiff_t, typename PointerT = T *,
79  typename ReferenceT = T &>
81 public:
82  using iterator_category = IteratorCategoryT;
83  using value_type = T;
84  using difference_type = DifferenceTypeT;
85  using pointer = PointerT;
86  using reference = ReferenceT;
87 
88 protected:
89  enum {
90  IsRandomAccess = std::is_base_of<std::random_access_iterator_tag,
91  IteratorCategoryT>::value,
92  IsBidirectional = std::is_base_of<std::bidirectional_iterator_tag,
93  IteratorCategoryT>::value,
94  };
95 
96  /// A proxy object for computing a reference via indirecting a copy of an
97  /// iterator. This is used in APIs which need to produce a reference via
98  /// indirection but for which the iterator object might be a temporary. The
99  /// proxy preserves the iterator internally and exposes the indirected
100  /// reference via a conversion operator.
102  friend iterator_facade_base;
103 
104  DerivedT I;
105 
106  ReferenceProxy(DerivedT I) : I(std::move(I)) {}
107 
108  public:
109  operator ReferenceT() const { return *I; }
110  };
111 
112  /// A proxy object for computing a pointer via indirecting a copy of a
113  /// reference. This is used in APIs which need to produce a pointer but for
114  /// which the reference might be a temporary. The proxy preserves the
115  /// reference internally and exposes the pointer via a arrow operator.
116  class PointerProxy {
117  friend iterator_facade_base;
118 
119  ReferenceT R;
120 
121  template <typename RefT>
122  PointerProxy(RefT &&R) : R(std::forward<RefT>(R)) {}
123 
124  public:
125  PointerT operator->() const { return &R; }
126  };
127 
128 public:
129  DerivedT operator+(DifferenceTypeT n) const {
130  static_assert(std::is_base_of<iterator_facade_base, DerivedT>::value,
131  "Must pass the derived type to this template!");
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  friend DerivedT operator+(DifferenceTypeT n, const DerivedT &i) {
140  static_assert(
142  "The '+' operator is only defined for random access iterators.");
143  return i + n;
144  }
145  DerivedT operator-(DifferenceTypeT n) const {
146  static_assert(
148  "The '-' operator is only defined for random access iterators.");
149  DerivedT tmp = *static_cast<const DerivedT *>(this);
150  tmp -= n;
151  return tmp;
152  }
153 
154  DerivedT &operator++() {
155  static_assert(std::is_base_of<iterator_facade_base, DerivedT>::value,
156  "Must pass the derived type to this template!");
157  return static_cast<DerivedT *>(this)->operator+=(1);
158  }
159  DerivedT operator++(int) {
160  DerivedT tmp = *static_cast<DerivedT *>(this);
161  ++*static_cast<DerivedT *>(this);
162  return tmp;
163  }
164  DerivedT &operator--() {
165  static_assert(
167  "The decrement operator is only defined for bidirectional iterators.");
168  return static_cast<DerivedT *>(this)->operator-=(1);
169  }
170  DerivedT operator--(int) {
171  static_assert(
173  "The decrement operator is only defined for bidirectional iterators.");
174  DerivedT tmp = *static_cast<DerivedT *>(this);
175  --*static_cast<DerivedT *>(this);
176  return tmp;
177  }
178 
179 #ifndef __cpp_impl_three_way_comparison
180  bool operator!=(const DerivedT &RHS) const {
181  return !(static_cast<const DerivedT &>(*this) == RHS);
182  }
183 #endif
184 
185  bool operator>(const DerivedT &RHS) const {
186  static_assert(
188  "Relational operators are only defined for random access iterators.");
189  return !(static_cast<const DerivedT &>(*this) < RHS) &&
190  !(static_cast<const DerivedT &>(*this) == RHS);
191  }
192  bool operator<=(const DerivedT &RHS) const {
193  static_assert(
195  "Relational operators are only defined for random access iterators.");
196  return !(static_cast<const DerivedT &>(*this) > RHS);
197  }
198  bool operator>=(const DerivedT &RHS) const {
199  static_assert(
201  "Relational operators are only defined for random access iterators.");
202  return !(static_cast<const DerivedT &>(*this) < RHS);
203  }
204 
205  PointerProxy operator->() const {
206  return static_cast<const DerivedT *>(this)->operator*();
207  }
208  ReferenceProxy operator[](DifferenceTypeT n) const {
209  static_assert(IsRandomAccess,
210  "Subscripting is only defined for random access iterators.");
211  return static_cast<const DerivedT *>(this)->operator+(n);
212  }
213 };
214 
215 /// CRTP base class for adapting an iterator to a different type.
216 ///
217 /// This class can be used through CRTP to adapt one iterator into another.
218 /// Typically this is done through providing in the derived class a custom \c
219 /// operator* implementation. Other methods can be overridden as well.
220 template <
221  typename DerivedT, typename WrappedIteratorT,
222  typename IteratorCategoryT =
223  typename std::iterator_traits<WrappedIteratorT>::iterator_category,
224  typename T = typename std::iterator_traits<WrappedIteratorT>::value_type,
225  typename DifferenceTypeT =
226  typename std::iterator_traits<WrappedIteratorT>::difference_type,
227  typename PointerT = std::conditional_t<
228  std::is_same<T, typename std::iterator_traits<
229  WrappedIteratorT>::value_type>::value,
231  typename ReferenceT = std::conditional_t<
232  std::is_same<T, typename std::iterator_traits<
233  WrappedIteratorT>::value_type>::value,
234  typename std::iterator_traits<WrappedIteratorT>::reference, T &>>
236  : public iterator_facade_base<DerivedT, IteratorCategoryT, T,
237  DifferenceTypeT, PointerT, ReferenceT> {
238  using BaseT = typename iterator_adaptor_base::iterator_facade_base;
239 
240 protected:
242 
243  iterator_adaptor_base() = default;
244 
246  static_assert(std::is_base_of<iterator_adaptor_base, DerivedT>::value,
247  "Must pass the derived type to this template!");
248  }
249 
250  const WrappedIteratorT &wrapped() const { return I; }
251 
252 public:
253  using difference_type = DifferenceTypeT;
254 
256  static_assert(
257  BaseT::IsRandomAccess,
258  "The '+=' operator is only defined for random access iterators.");
259  I += n;
260  return *static_cast<DerivedT *>(this);
261  }
263  static_assert(
264  BaseT::IsRandomAccess,
265  "The '-=' operator is only defined for random access iterators.");
266  I -= n;
267  return *static_cast<DerivedT *>(this);
268  }
269  using BaseT::operator-;
270  difference_type operator-(const DerivedT &RHS) const {
271  static_assert(
272  BaseT::IsRandomAccess,
273  "The '-' operator is only defined for random access iterators.");
274  return I - RHS.I;
275  }
276 
277  // We have to explicitly provide ++ and -- rather than letting the facade
278  // forward to += because WrappedIteratorT might not support +=.
279  using BaseT::operator++;
280  DerivedT &operator++() {
281  ++I;
282  return *static_cast<DerivedT *>(this);
283  }
284  using BaseT::operator--;
285  DerivedT &operator--() {
286  static_assert(
287  BaseT::IsBidirectional,
288  "The decrement operator is only defined for bidirectional iterators.");
289  --I;
290  return *static_cast<DerivedT *>(this);
291  }
292 
294  const iterator_adaptor_base &RHS) {
295  return LHS.I == RHS.I;
296  }
297  friend bool operator<(const iterator_adaptor_base &LHS,
298  const iterator_adaptor_base &RHS) {
299  static_assert(
300  BaseT::IsRandomAccess,
301  "Relational operators are only defined for random access iterators.");
302  return LHS.I < RHS.I;
303  }
304 
305  ReferenceT operator*() const { return *I; }
306 };
307 
308 /// An iterator type that allows iterating over the pointees via some
309 /// other iterator.
310 ///
311 /// The typical usage of this is to expose a type that iterates over Ts, but
312 /// which is implemented with some iterator over T*s:
313 ///
314 /// \code
315 /// using iterator = pointee_iterator<SmallVectorImpl<T *>::iterator>;
316 /// \endcode
317 template <typename WrappedIteratorT,
318  typename T = std::remove_reference_t<decltype(
319  **std::declval<WrappedIteratorT>())>>
322  pointee_iterator<WrappedIteratorT, T>, WrappedIteratorT,
323  typename std::iterator_traits<WrappedIteratorT>::iterator_category,
324  T> {
325  pointee_iterator() = default;
326  template <typename U>
328  : pointee_iterator::iterator_adaptor_base(std::forward<U &&>(u)) {}
329 
330  T &operator*() const { return **this->I; }
331 };
332 
333 template <typename RangeT, typename WrappedIteratorT =
334  decltype(std::begin(std::declval<RangeT>()))>
335 iterator_range<pointee_iterator<WrappedIteratorT>>
336 make_pointee_range(RangeT &&Range) {
337  using PointeeIteratorT = pointee_iterator<WrappedIteratorT>;
338  return make_range(PointeeIteratorT(std::begin(std::forward<RangeT>(Range))),
339  PointeeIteratorT(std::end(std::forward<RangeT>(Range))));
340 }
341 
342 template <typename WrappedIteratorT,
343  typename T = decltype(&*std::declval<WrappedIteratorT>())>
345  : public iterator_adaptor_base<
346  pointer_iterator<WrappedIteratorT, T>, WrappedIteratorT,
347  typename std::iterator_traits<WrappedIteratorT>::iterator_category,
348  T> {
349  mutable T Ptr;
350 
351 public:
352  pointer_iterator() = default;
353 
356 
357  T &operator*() const { return Ptr = &*this->I; }
358 };
359 
360 template <typename RangeT, typename WrappedIteratorT =
361  decltype(std::begin(std::declval<RangeT>()))>
362 iterator_range<pointer_iterator<WrappedIteratorT>>
363 make_pointer_range(RangeT &&Range) {
364  using PointerIteratorT = pointer_iterator<WrappedIteratorT>;
365  return make_range(PointerIteratorT(std::begin(std::forward<RangeT>(Range))),
366  PointerIteratorT(std::end(std::forward<RangeT>(Range))));
367 }
368 
369 template <typename WrappedIteratorT,
370  typename T1 = std::remove_reference_t<decltype(
371  **std::declval<WrappedIteratorT>())>,
372  typename T2 = std::add_pointer_t<T1>>
373 using raw_pointer_iterator =
375 
376 } // end namespace llvm
377 
378 #endif // LLVM_ADT_ITERATOR_H
i
i
Definition: README.txt:29
llvm::pointer_iterator::operator*
T & operator*() const
Definition: iterator.h:357
llvm
This is an optimization pass for GlobalISel generic memory operations.
Definition: AddressRanges.h:17
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:631
llvm::iterator_facade_base< iterator, std::forward_iterator_tag, const entry >::pointer
const entry * pointer
Definition: iterator.h:85
llvm::iterator_facade_base::operator++
DerivedT operator++(int)
Definition: iterator.h:159
llvm::iterator_facade_base::IsBidirectional
@ IsBidirectional
Definition: iterator.h:92
llvm::pointee_iterator::pointee_iterator
pointee_iterator(U &&u)
Definition: iterator.h:327
llvm::iterator_adaptor_base::I
WrappedIteratorT I
Definition: iterator.h:241
llvm::iterator_facade_base::operator->
PointerProxy operator->() const
Definition: iterator.h:205
llvm::iterator_adaptor_base::operator-=
DerivedT & operator-=(difference_type n)
Definition: iterator.h:262
llvm::iterator_facade_base::operator[]
ReferenceProxy operator[](DifferenceTypeT n) const
Definition: iterator.h:208
llvm::iterator_facade_base::operator++
DerivedT & operator++()
Definition: iterator.h:154
llvm::pointee_iterator::operator*
T & operator*() const
Definition: iterator.h:330
llvm::sys::path::end
const_iterator end(StringRef path)
Get end iterator over path.
Definition: Path.cpp:235
llvm::sys::path::begin
const_iterator begin(StringRef path, Style style=Style::native)
Get begin iterator over path.
Definition: Path.cpp:226
llvm::iterator_adaptor_base
CRTP base class for adapting an iterator to a different type.
Definition: iterator.h:235
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< iterator, std::forward_iterator_tag, const entry >::value_type
const entry value_type
Definition: iterator.h:83
RHS
Value * RHS
Definition: X86PartialReduction.cpp:76
llvm::iterator_adaptor_base::wrapped
const WrappedIteratorT & wrapped() const
Definition: iterator.h:250
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:255
llvm::raw_pointer_iterator
pointer_iterator< pointee_iterator< WrappedIteratorT, T1 >, T2 > raw_pointer_iterator
Definition: iterator.h:374
llvm::pointee_iterator::pointee_iterator
pointee_iterator()=default
llvm::iterator_facade_base::operator+
DerivedT operator+(DifferenceTypeT n) const
Definition: iterator.h:129
LHS
Value * LHS
Definition: X86PartialReduction.cpp:75
llvm::iterator_facade_base::operator+
friend DerivedT operator+(DifferenceTypeT n, const DerivedT &i)
Definition: iterator.h:139
llvm::iterator_adaptor_base::operator==
friend bool operator==(const iterator_adaptor_base &LHS, const iterator_adaptor_base &RHS)
Definition: iterator.h:293
llvm::iterator_facade_base::PointerProxy::operator->
PointerT operator->() const
Definition: iterator.h:125
llvm::iterator_facade_base::operator!=
bool operator!=(const DerivedT &RHS) const
Definition: iterator.h:180
llvm::iterator_facade_base< iterator, std::forward_iterator_tag, const entry >::reference
const entry & reference
Definition: iterator.h:86
llvm::pointer_iterator
Definition: iterator.h:344
llvm::iterator_facade_base::IsRandomAccess
@ IsRandomAccess
Definition: iterator.h:90
llvm::iterator_facade_base::operator>
bool operator>(const DerivedT &RHS) const
Definition: iterator.h:185
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:116
I
#define I(x, y, z)
Definition: MD5.cpp:58
llvm::iterator_facade_base
CRTP base class which implements the entire standard iterator facade in terms of a minimal subset of ...
Definition: iterator.h:80
llvm::iterator_facade_base::operator-
DerivedT operator-(DifferenceTypeT n) const
Definition: iterator.h:145
llvm::iterator_adaptor_base::iterator_adaptor_base
iterator_adaptor_base(WrappedIteratorT u)
Definition: iterator.h:245
llvm::make_pointee_range
iterator_range< pointee_iterator< WrappedIteratorT > > make_pointee_range(RangeT &&Range)
Definition: iterator.h:336
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:1675
llvm::iterator_facade_base< iterator, std::forward_iterator_tag, const entry >::difference_type
std::ptrdiff_t difference_type
Definition: iterator.h:84
iterator_range.h
llvm::iterator_adaptor_base::operator<
friend bool operator<(const iterator_adaptor_base &LHS, const iterator_adaptor_base &RHS)
Definition: iterator.h:297
llvm::make_pointer_range
iterator_range< pointer_iterator< WrappedIteratorT > > make_pointer_range(RangeT &&Range)
Definition: iterator.h:363
llvm::iterator_facade_base::operator--
DerivedT operator--(int)
Definition: iterator.h:170
std
Definition: BitVector.h:851
llvm::iterator_facade_base::operator>=
bool operator>=(const DerivedT &RHS) const
Definition: iterator.h:198
llvm::iterator_adaptor_base::operator-
difference_type operator-(const DerivedT &RHS) const
Definition: iterator.h:270
llvm::iterator_adaptor_base::operator--
DerivedT & operator--()
Definition: iterator.h:285
llvm::iterator_adaptor_base::operator++
DerivedT & operator++()
Definition: iterator.h:280
llvm::iterator_facade_base::operator<=
bool operator<=(const DerivedT &RHS) const
Definition: iterator.h:192
llvm::iterator_adaptor_base::operator*
ReferenceT operator*() const
Definition: iterator.h:305
llvm::pointee_iterator
An iterator type that allows iterating over the pointees via some other iterator.
Definition: iterator.h:320
llvm::iterator_facade_base< iterator, std::forward_iterator_tag, const entry >::iterator_category
std::forward_iterator_tag iterator_category
Definition: iterator.h:82
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:164
WrappedIteratorT
llvm::pointer_iterator::pointer_iterator
pointer_iterator()=default
llvm::pointer_iterator::pointer_iterator
pointer_iterator(WrappedIteratorT u)
Definition: iterator.h:354
llvm::iterator_facade_base::ReferenceProxy
A proxy object for computing a reference via indirecting a copy of an iterator.
Definition: iterator.h:101