LLVM  13.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 public:
99  DerivedT operator+(DifferenceTypeT n) const {
100  static_assert(std::is_base_of<iterator_facade_base, DerivedT>::value,
101  "Must pass the derived type to this template!");
102  static_assert(
104  "The '+' operator is only defined for random access iterators.");
105  DerivedT tmp = *static_cast<const DerivedT *>(this);
106  tmp += n;
107  return tmp;
108  }
109  friend DerivedT operator+(DifferenceTypeT n, const DerivedT &i) {
110  static_assert(
112  "The '+' operator is only defined for random access iterators.");
113  return i + n;
114  }
115  DerivedT operator-(DifferenceTypeT n) const {
116  static_assert(
118  "The '-' operator is only defined for random access iterators.");
119  DerivedT tmp = *static_cast<const DerivedT *>(this);
120  tmp -= n;
121  return tmp;
122  }
123 
124  DerivedT &operator++() {
125  static_assert(std::is_base_of<iterator_facade_base, DerivedT>::value,
126  "Must pass the derived type to this template!");
127  return static_cast<DerivedT *>(this)->operator+=(1);
128  }
129  DerivedT operator++(int) {
130  DerivedT tmp = *static_cast<DerivedT *>(this);
131  ++*static_cast<DerivedT *>(this);
132  return tmp;
133  }
134  DerivedT &operator--() {
135  static_assert(
137  "The decrement operator is only defined for bidirectional iterators.");
138  return static_cast<DerivedT *>(this)->operator-=(1);
139  }
140  DerivedT operator--(int) {
141  static_assert(
143  "The decrement operator is only defined for bidirectional iterators.");
144  DerivedT tmp = *static_cast<DerivedT *>(this);
145  --*static_cast<DerivedT *>(this);
146  return tmp;
147  }
148 
149 #ifndef __cpp_impl_three_way_comparison
150  bool operator!=(const DerivedT &RHS) const {
151  return !(static_cast<const DerivedT &>(*this) == RHS);
152  }
153 #endif
154 
155  bool operator>(const DerivedT &RHS) const {
156  static_assert(
158  "Relational operators are only defined for random access iterators.");
159  return !(static_cast<const DerivedT &>(*this) < RHS) &&
160  !(static_cast<const DerivedT &>(*this) == RHS);
161  }
162  bool operator<=(const DerivedT &RHS) const {
163  static_assert(
165  "Relational operators are only defined for random access iterators.");
166  return !(static_cast<const DerivedT &>(*this) > RHS);
167  }
168  bool operator>=(const DerivedT &RHS) const {
169  static_assert(
171  "Relational operators are only defined for random access iterators.");
172  return !(static_cast<const DerivedT &>(*this) < RHS);
173  }
174 
175  PointerT operator->() { return &static_cast<DerivedT *>(this)->operator*(); }
176  PointerT operator->() const {
177  return &static_cast<const DerivedT *>(this)->operator*();
178  }
179  ReferenceProxy operator[](DifferenceTypeT n) {
180  static_assert(IsRandomAccess,
181  "Subscripting is only defined for random access iterators.");
182  return ReferenceProxy(static_cast<DerivedT *>(this)->operator+(n));
183  }
184  ReferenceProxy operator[](DifferenceTypeT n) const {
185  static_assert(IsRandomAccess,
186  "Subscripting is only defined for random access iterators.");
187  return ReferenceProxy(static_cast<const DerivedT *>(this)->operator+(n));
188  }
189 };
190 
191 /// CRTP base class for adapting an iterator to a different type.
192 ///
193 /// This class can be used through CRTP to adapt one iterator into another.
194 /// Typically this is done through providing in the derived class a custom \c
195 /// operator* implementation. Other methods can be overridden as well.
196 template <
197  typename DerivedT, typename WrappedIteratorT,
198  typename IteratorCategoryT =
199  typename std::iterator_traits<WrappedIteratorT>::iterator_category,
200  typename T = typename std::iterator_traits<WrappedIteratorT>::value_type,
201  typename DifferenceTypeT =
202  typename std::iterator_traits<WrappedIteratorT>::difference_type,
203  typename PointerT = std::conditional_t<
204  std::is_same<T, typename std::iterator_traits<
205  WrappedIteratorT>::value_type>::value,
206  typename std::iterator_traits<WrappedIteratorT>::pointer, T *>,
207  typename ReferenceT = std::conditional_t<
208  std::is_same<T, typename std::iterator_traits<
209  WrappedIteratorT>::value_type>::value,
210  typename std::iterator_traits<WrappedIteratorT>::reference, T &>>
212  : public iterator_facade_base<DerivedT, IteratorCategoryT, T,
213  DifferenceTypeT, PointerT, ReferenceT> {
214  using BaseT = typename iterator_adaptor_base::iterator_facade_base;
215 
216 protected:
218 
219  iterator_adaptor_base() = default;
220 
222  static_assert(std::is_base_of<iterator_adaptor_base, DerivedT>::value,
223  "Must pass the derived type to this template!");
224  }
225 
226  const WrappedIteratorT &wrapped() const { return I; }
227 
228 public:
229  using difference_type = DifferenceTypeT;
230 
232  static_assert(
233  BaseT::IsRandomAccess,
234  "The '+=' operator is only defined for random access iterators.");
235  I += n;
236  return *static_cast<DerivedT *>(this);
237  }
239  static_assert(
240  BaseT::IsRandomAccess,
241  "The '-=' operator is only defined for random access iterators.");
242  I -= n;
243  return *static_cast<DerivedT *>(this);
244  }
245  using BaseT::operator-;
246  difference_type operator-(const DerivedT &RHS) const {
247  static_assert(
248  BaseT::IsRandomAccess,
249  "The '-' operator is only defined for random access iterators.");
250  return I - RHS.I;
251  }
252 
253  // We have to explicitly provide ++ and -- rather than letting the facade
254  // forward to += because WrappedIteratorT might not support +=.
255  using BaseT::operator++;
256  DerivedT &operator++() {
257  ++I;
258  return *static_cast<DerivedT *>(this);
259  }
260  using BaseT::operator--;
261  DerivedT &operator--() {
262  static_assert(
263  BaseT::IsBidirectional,
264  "The decrement operator is only defined for bidirectional iterators.");
265  --I;
266  return *static_cast<DerivedT *>(this);
267  }
268 
269  friend bool operator==(const iterator_adaptor_base &LHS,
270  const iterator_adaptor_base &RHS) {
271  return LHS.I == RHS.I;
272  }
273  friend bool operator<(const iterator_adaptor_base &LHS,
274  const iterator_adaptor_base &RHS) {
275  static_assert(
276  BaseT::IsRandomAccess,
277  "Relational operators are only defined for random access iterators.");
278  return LHS.I < RHS.I;
279  }
280 
281  ReferenceT operator*() const { return *I; }
282 };
283 
284 /// An iterator type that allows iterating over the pointees via some
285 /// other iterator.
286 ///
287 /// The typical usage of this is to expose a type that iterates over Ts, but
288 /// which is implemented with some iterator over T*s:
289 ///
290 /// \code
291 /// using iterator = pointee_iterator<SmallVectorImpl<T *>::iterator>;
292 /// \endcode
293 template <typename WrappedIteratorT,
294  typename T = std::remove_reference_t<decltype(
295  **std::declval<WrappedIteratorT>())>>
298  pointee_iterator<WrappedIteratorT, T>, WrappedIteratorT,
299  typename std::iterator_traits<WrappedIteratorT>::iterator_category,
300  T> {
301  pointee_iterator() = default;
302  template <typename U>
304  : pointee_iterator::iterator_adaptor_base(std::forward<U &&>(u)) {}
305 
306  T &operator*() const { return **this->I; }
307 };
308 
309 template <typename RangeT, typename WrappedIteratorT =
310  decltype(std::begin(std::declval<RangeT>()))>
311 iterator_range<pointee_iterator<WrappedIteratorT>>
312 make_pointee_range(RangeT &&Range) {
313  using PointeeIteratorT = pointee_iterator<WrappedIteratorT>;
314  return make_range(PointeeIteratorT(std::begin(std::forward<RangeT>(Range))),
315  PointeeIteratorT(std::end(std::forward<RangeT>(Range))));
316 }
317 
318 template <typename WrappedIteratorT,
319  typename T = decltype(&*std::declval<WrappedIteratorT>())>
321  : public iterator_adaptor_base<
322  pointer_iterator<WrappedIteratorT, T>, WrappedIteratorT,
323  typename std::iterator_traits<WrappedIteratorT>::iterator_category,
324  T> {
325  mutable T Ptr;
326 
327 public:
328  pointer_iterator() = default;
329 
332 
333  T &operator*() { return Ptr = &*this->I; }
334  const T &operator*() const { return Ptr = &*this->I; }
335 };
336 
337 template <typename RangeT, typename WrappedIteratorT =
338  decltype(std::begin(std::declval<RangeT>()))>
339 iterator_range<pointer_iterator<WrappedIteratorT>>
340 make_pointer_range(RangeT &&Range) {
341  using PointerIteratorT = pointer_iterator<WrappedIteratorT>;
342  return make_range(PointerIteratorT(std::begin(std::forward<RangeT>(Range))),
343  PointerIteratorT(std::end(std::forward<RangeT>(Range))));
344 }
345 
346 template <typename WrappedIteratorT,
347  typename T1 = std::remove_reference_t<decltype(
348  **std::declval<WrappedIteratorT>())>,
349  typename T2 = std::add_pointer_t<T1>>
350 using raw_pointer_iterator =
352 
353 // Wrapper iterator over iterator ItType, adding DataRef to the type of ItType,
354 // to create NodeRef = std::pair<InnerTypeOfItType, DataRef>.
355 template <typename ItType, typename NodeRef, typename DataRef>
357  : public iterator_adaptor_base<
358  WrappedPairNodeDataIterator<ItType, NodeRef, DataRef>, ItType,
359  typename std::iterator_traits<ItType>::iterator_category, NodeRef,
360  std::ptrdiff_t, NodeRef *, NodeRef &> {
363  typename std::iterator_traits<ItType>::iterator_category, NodeRef,
364  std::ptrdiff_t, NodeRef *, NodeRef &>;
365 
366  const DataRef DR;
367  mutable NodeRef NR;
368 
369 public:
370  WrappedPairNodeDataIterator(ItType Begin, const DataRef DR)
371  : BaseT(Begin), DR(DR) {
372  NR.first = DR;
373  }
374 
375  NodeRef &operator*() const {
376  NR.second = *this->I;
377  return NR;
378  }
379 };
380 
381 } // end namespace llvm
382 
383 #endif // LLVM_ADT_ITERATOR_H
i
i
Definition: README.txt:29
llvm
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
llvm::WrappedPairNodeDataIterator
Definition: iterator.h:356
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:129
llvm::pointee_iterator::pointee_iterator
pointee_iterator(U &&u)
Definition: iterator.h:303
llvm::iterator_adaptor_base::I
WrappedIteratorT I
Definition: iterator.h:217
llvm::iterator_adaptor_base::operator-=
DerivedT & operator-=(difference_type n)
Definition: iterator.h:238
llvm::iterator_facade_base::operator[]
ReferenceProxy operator[](DifferenceTypeT n) const
Definition: iterator.h:184
llvm::iterator_facade_base::operator++
DerivedT & operator++()
Definition: iterator.h:124
llvm::pointee_iterator::operator*
T & operator*() const
Definition: iterator.h:306
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:211
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:226
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:231
llvm::raw_pointer_iterator
pointer_iterator< pointee_iterator< WrappedIteratorT, T1 >, T2 > raw_pointer_iterator
Definition: iterator.h:351
llvm::pointee_iterator::pointee_iterator
pointee_iterator()=default
llvm::iterator_facade_base::IsBidirectional
@ IsBidirectional
Definition: iterator.h:78
llvm::WrappedPairNodeDataIterator::WrappedPairNodeDataIterator
WrappedPairNodeDataIterator(ItType Begin, const DataRef DR)
Definition: iterator.h:370
llvm::iterator_facade_base::operator+
DerivedT operator+(DifferenceTypeT n) const
Definition: iterator.h:99
llvm::pointer_iterator::operator*
T & operator*()
Definition: iterator.h:333
llvm::iterator_facade_base::operator+
friend DerivedT operator+(DifferenceTypeT n, const DerivedT &i)
Definition: iterator.h:109
llvm::iterator_adaptor_base::operator==
friend bool operator==(const iterator_adaptor_base &LHS, const iterator_adaptor_base &RHS)
Definition: iterator.h:269
llvm::pointer_iterator::operator*
const T & operator*() const
Definition: iterator.h:334
llvm::rdf::detail::NodeRef
std::pair< NodeId, LaneBitmask > NodeRef
Definition: RDFLiveness.h:39
llvm::iterator_facade_base::operator!=
bool operator!=(const DerivedT &RHS) const
Definition: iterator.h:150
llvm::iterator_facade_base::operator->
PointerT operator->() const
Definition: iterator.h:176
llvm::iterator_facade_base< partition_iterator, std::forward_iterator_tag, Partition >::reference
Partition & reference
Definition: iterator.h:72
llvm::pointer_iterator
Definition: iterator.h:320
llvm::iterator_facade_base::operator>
bool operator>(const DerivedT &RHS) const
Definition: iterator.h:155
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
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:115
llvm::iterator_adaptor_base::iterator_adaptor_base
iterator_adaptor_base(WrappedIteratorT u)
Definition: iterator.h:221
llvm::make_pointee_range
iterator_range< pointee_iterator< WrappedIteratorT > > make_pointee_range(RangeT &&Range)
Definition: iterator.h:312
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:1563
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:273
llvm::make_pointer_range
iterator_range< pointer_iterator< WrappedIteratorT > > make_pointer_range(RangeT &&Range)
Definition: iterator.h:340
llvm::iterator_facade_base::operator--
DerivedT operator--(int)
Definition: iterator.h:140
ItType
llvm::iterator_facade_base::operator[]
ReferenceProxy operator[](DifferenceTypeT n)
Definition: iterator.h:179
llvm::WrappedPairNodeDataIterator::operator*
NodeRef & operator*() const
Definition: iterator.h:375
std
Definition: BitVector.h:838
llvm::iterator_facade_base::operator>=
bool operator>=(const DerivedT &RHS) const
Definition: iterator.h:168
llvm::iterator_adaptor_base::operator-
difference_type operator-(const DerivedT &RHS) const
Definition: iterator.h:246
llvm::iterator_adaptor_base::operator--
DerivedT & operator--()
Definition: iterator.h:261
llvm::iterator_adaptor_base::operator++
DerivedT & operator++()
Definition: iterator.h:256
llvm::iterator_facade_base::operator<=
bool operator<=(const DerivedT &RHS) const
Definition: iterator.h:162
llvm::iterator_adaptor_base::operator*
ReferenceT operator*() const
Definition: iterator.h:281
llvm::pointee_iterator
An iterator type that allows iterating over the pointees via some other iterator.
Definition: iterator.h:296
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:134
WrappedIteratorT
llvm::pointer_iterator::pointer_iterator
pointer_iterator()=default
llvm::pointer_iterator::pointer_iterator
pointer_iterator(WrappedIteratorT u)
Definition: iterator.h:330
llvm::iterator_facade_base::operator->
PointerT operator->()
Definition: iterator.h:175
llvm::iterator_facade_base::ReferenceProxy
A proxy object for computing a reference via indirecting a copy of an iterator.
Definition: iterator.h:87