LLVM  6.0.0svn
ilist_iterator.h
Go to the documentation of this file.
1 //===- llvm/ADT/ilist_iterator.h - Intrusive List Iterator ------*- C++ -*-===//
2 //
3 // The LLVM Compiler Infrastructure
4 //
5 // This file is distributed under the University of Illinois Open Source
6 // License. See LICENSE.TXT for details.
7 //
8 //===----------------------------------------------------------------------===//
9 
10 #ifndef LLVM_ADT_ILIST_ITERATOR_H
11 #define LLVM_ADT_ILIST_ITERATOR_H
12 
13 #include "llvm/ADT/ilist_node.h"
14 #include <cassert>
15 #include <cstddef>
16 #include <iterator>
17 #include <type_traits>
18 
19 namespace llvm {
20 
21 namespace ilist_detail {
22 
23 /// Find const-correct node types.
24 template <class OptionsT, bool IsConst> struct IteratorTraits;
25 template <class OptionsT> struct IteratorTraits<OptionsT, false> {
26  using value_type = typename OptionsT::value_type;
27  using pointer = typename OptionsT::pointer;
28  using reference = typename OptionsT::reference;
31 };
32 template <class OptionsT> struct IteratorTraits<OptionsT, true> {
33  using value_type = const typename OptionsT::value_type;
34  using pointer = typename OptionsT::const_pointer;
35  using reference = typename OptionsT::const_reference;
38 };
39 
40 template <bool IsReverse> struct IteratorHelper;
43 
44  template <class T> static void increment(T *&I) { I = Access::getNext(*I); }
45  template <class T> static void decrement(T *&I) { I = Access::getPrev(*I); }
46 };
49 
50  template <class T> static void increment(T *&I) { I = Access::getPrev(*I); }
51  template <class T> static void decrement(T *&I) { I = Access::getNext(*I); }
52 };
53 
54 } // end namespace ilist_detail
55 
56 /// Iterator for intrusive lists based on ilist_node.
57 template <class OptionsT, bool IsReverse, bool IsConst>
62 
65 
66 public:
67  using value_type = typename Traits::value_type;
68  using pointer = typename Traits::pointer;
69  using reference = typename Traits::reference;
71  using iterator_category = std::bidirectional_iterator_tag;
72  using const_pointer = typename OptionsT::const_pointer;
73  using const_reference = typename OptionsT::const_reference;
74 
75 private:
76  using node_pointer = typename Traits::node_pointer;
77  using node_reference = typename Traits::node_reference;
78 
79  node_pointer NodePtr = nullptr;
80 
81 public:
82  /// Create from an ilist_node.
83  explicit ilist_iterator(node_reference N) : NodePtr(&N) {}
84 
85  explicit ilist_iterator(pointer NP) : NodePtr(Access::getNodePtr(NP)) {}
86  explicit ilist_iterator(reference NR) : NodePtr(Access::getNodePtr(&NR)) {}
87  ilist_iterator() = default;
88 
89  // This is templated so that we can allow constructing a const iterator from
90  // a nonconst iterator...
91  template <bool RHSIsConst>
94  typename std::enable_if<IsConst || !RHSIsConst, void *>::type = nullptr)
95  : NodePtr(RHS.NodePtr) {}
96 
97  // This is templated so that we can allow assigning to a const iterator from
98  // a nonconst iterator...
99  template <bool RHSIsConst>
100  typename std::enable_if<IsConst || !RHSIsConst, ilist_iterator &>::type
102  NodePtr = RHS.NodePtr;
103  return *this;
104  }
105 
106  /// Explicit conversion between forward/reverse iterators.
107  ///
108  /// Translate between forward and reverse iterators without changing range
109  /// boundaries. The resulting iterator will dereference (and have a handle)
110  /// to the previous node, which is somewhat unexpected; but converting the
111  /// two endpoints in a range will give the same range in reverse.
112  ///
113  /// This matches std::reverse_iterator conversions.
114  explicit ilist_iterator(
116  : ilist_iterator(++RHS.getReverse()) {}
117 
118  /// Get a reverse iterator to the same node.
119  ///
120  /// Gives a reverse iterator that will dereference (and have a handle) to the
121  /// same node. Converting the endpoint iterators in a range will give a
122  /// different range; for range operations, use the explicit conversions.
124  if (NodePtr)
127  }
128 
129  /// Const-cast.
131  if (NodePtr)
133  const_cast<typename ilist_iterator<OptionsT, IsReverse,
134  false>::node_reference>(*NodePtr));
136  }
137 
138  // Accessors...
140  assert(!NodePtr->isKnownSentinel());
141  return *Access::getValuePtr(NodePtr);
142  }
143  pointer operator->() const { return &operator*(); }
144 
145  // Comparison operators
146  friend bool operator==(const ilist_iterator &LHS, const ilist_iterator &RHS) {
147  return LHS.NodePtr == RHS.NodePtr;
148  }
149  friend bool operator!=(const ilist_iterator &LHS, const ilist_iterator &RHS) {
150  return LHS.NodePtr != RHS.NodePtr;
151  }
152 
153  // Increment and decrement operators...
155  NodePtr = IsReverse ? NodePtr->getNext() : NodePtr->getPrev();
156  return *this;
157  }
159  NodePtr = IsReverse ? NodePtr->getPrev() : NodePtr->getNext();
160  return *this;
161  }
163  ilist_iterator tmp = *this;
164  --*this;
165  return tmp;
166  }
168  ilist_iterator tmp = *this;
169  ++*this;
170  return tmp;
171  }
172 
173  /// Get the underlying ilist_node.
174  node_pointer getNodePtr() const { return static_cast<node_pointer>(NodePtr); }
175 
176  /// Check for end. Only valid if ilist_sentinel_tracking<true>.
177  bool isEnd() const { return NodePtr ? NodePtr->isSentinel() : false; }
178 };
179 
180 template <typename From> struct simplify_type;
181 
182 /// Allow ilist_iterators to convert into pointers to a node automatically when
183 /// used by the dyn_cast, cast, isa mechanisms...
184 ///
185 /// FIXME: remove this, since there is no implicit conversion to NodeTy.
186 template <class OptionsT, bool IsConst>
189  using SimpleType = typename iterator::pointer;
190 
191  static SimpleType getSimplifiedValue(const iterator &Node) { return &*Node; }
192 };
193 template <class OptionsT, bool IsConst>
195  : simplify_type<ilist_iterator<OptionsT, false, IsConst>> {};
196 
197 } // end namespace llvm
198 
199 #endif // LLVM_ADT_ILIST_ITERATOR_H
typename OptionsT::const_reference reference
typename Traits::reference reference
const typename OptionsT::value_type value_type
Compute iterated dominance frontiers using a linear time algorithm.
Definition: AllocatorList.h:24
ilist_iterator(node_reference N)
Create from an ilist_node.
bool isEnd() const
Check for end. Only valid if ilist_sentinel_tracking<true>.
std::bidirectional_iterator_tag iterator_category
typename Traits::pointer pointer
Implementation for an ilist node.
Definition: ilist_node.h:40
typename Traits::value_type value_type
APInt operator*(APInt a, uint64_t RHS)
Definition: APInt.h:2070
ilist_iterator(reference NR)
ilist_iterator< OptionsT, IsReverse, false > getNonConst() const
Const-cast.
pointer operator->() const
node_pointer getNodePtr() const
Get the underlying ilist_node.
friend bool operator==(const ilist_iterator &LHS, const ilist_iterator &RHS)
static ilist_node_impl< OptionsT > * getPrev(ilist_node_impl< OptionsT > &N)
Definition: ilist_node.h:189
std::enable_if< IsConst||!RHSIsConst, ilist_iterator & >::type operator=(const ilist_iterator< OptionsT, IsReverse, RHSIsConst > &RHS)
static SimpleType getSimplifiedValue(const iterator &Node)
ilist_iterator operator++(int)
ilist_iterator(pointer NP)
Find const-correct node types.
reference operator*() const
An access class for ilist_node private API.
Definition: ilist_node.h:164
Iterator for intrusive lists based on ilist_node.
friend bool operator!=(const ilist_iterator &LHS, const ilist_iterator &RHS)
ilist_iterator & operator++()
typename OptionsT::const_reference const_reference
ilist_iterator(const ilist_iterator< OptionsT, IsReverse, RHSIsConst > &RHS, typename std::enable_if< IsConst||!RHSIsConst, void *>::type=nullptr)
Basic Alias true
ilist_iterator(const ilist_iterator< OptionsT, !IsReverse, IsConst > &RHS)
Explicit conversion between forward/reverse iterators.
ilist_iterator operator--(int)
ilist_iterator & operator--()
#define I(x, y, z)
Definition: MD5.cpp:58
#define N
ilist_iterator< OptionsT, !IsReverse, IsConst > getReverse() const
Get a reverse iterator to the same node.
constexpr char IsConst[]
Key for Kernel::Arg::Metadata::mIsConst.
typename OptionsT::const_pointer const_pointer
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
aarch64 promote const
static ilist_node_impl< OptionsT > * getNext(ilist_node_impl< OptionsT > &N)
Definition: ilist_node.h:194