LLVM 19.0.0git
ilist_iterator.h
Go to the documentation of this file.
1//===- llvm/ADT/ilist_iterator.h - Intrusive List Iterator ------*- 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_ILIST_ITERATOR_H
10#define LLVM_ADT_ILIST_ITERATOR_H
11
12#include "llvm/ADT/ilist_node.h"
13#include <cassert>
14#include <cstddef>
15#include <iterator>
16#include <type_traits>
17
18namespace llvm {
19
20namespace ilist_detail {
21
22/// Find const-correct node types.
23template <class OptionsT, bool IsConst> struct IteratorTraits;
24template <class OptionsT> struct IteratorTraits<OptionsT, false> {
25 using value_type = typename OptionsT::value_type;
26 using pointer = typename OptionsT::pointer;
27 using reference = typename OptionsT::reference;
30};
31template <class OptionsT> struct IteratorTraits<OptionsT, true> {
32 using value_type = const typename OptionsT::value_type;
33 using pointer = typename OptionsT::const_pointer;
34 using reference = typename OptionsT::const_reference;
37};
38
39template <bool IsReverse> struct IteratorHelper;
42
43 template <class T> static void increment(T *&I) { I = Access::getNext(*I); }
44 template <class T> static void decrement(T *&I) { I = Access::getPrev(*I); }
45};
48
49 template <class T> static void increment(T *&I) { I = Access::getPrev(*I); }
50 template <class T> static void decrement(T *&I) { I = Access::getNext(*I); }
51};
52
53} // end namespace ilist_detail
54
55/// Iterator for intrusive lists based on ilist_node.
56template <class OptionsT, bool IsReverse, bool IsConst>
61
64
65public:
66 using value_type = typename Traits::value_type;
67 using pointer = typename Traits::pointer;
68 using reference = typename Traits::reference;
70 using iterator_category = std::bidirectional_iterator_tag;
71 using const_pointer = typename OptionsT::const_pointer;
72 using const_reference = typename OptionsT::const_reference;
73
74private:
75 using node_pointer = typename Traits::node_pointer;
76 using node_reference = typename Traits::node_reference;
77
78 node_pointer NodePtr = nullptr;
79
80public:
81 /// Create from an ilist_node.
82 explicit ilist_iterator(node_reference N) : NodePtr(&N) {}
83
84 explicit ilist_iterator(pointer NP) : NodePtr(Access::getNodePtr(NP)) {}
85 explicit ilist_iterator(reference NR) : NodePtr(Access::getNodePtr(&NR)) {}
86 ilist_iterator() = default;
87
88 // This is templated so that we can allow constructing a const iterator from
89 // a nonconst iterator...
90 template <bool RHSIsConst>
92 std::enable_if_t<IsConst || !RHSIsConst, void *> = nullptr)
93 : NodePtr(RHS.NodePtr) {}
94
95 // This is templated so that we can allow assigning to a const iterator from
96 // a nonconst iterator...
97 template <bool RHSIsConst>
98 std::enable_if_t<IsConst || !RHSIsConst, ilist_iterator &>
100 NodePtr = RHS.NodePtr;
101 return *this;
102 }
103
104 /// Explicit conversion between forward/reverse iterators.
105 ///
106 /// Translate between forward and reverse iterators without changing range
107 /// boundaries. The resulting iterator will dereference (and have a handle)
108 /// to the previous node, which is somewhat unexpected; but converting the
109 /// two endpoints in a range will give the same range in reverse.
110 ///
111 /// This matches std::reverse_iterator conversions.
115
116 /// Get a reverse iterator to the same node.
117 ///
118 /// Gives a reverse iterator that will dereference (and have a handle) to the
119 /// same node. Converting the endpoint iterators in a range will give a
120 /// different range; for range operations, use the explicit conversions.
122 if (NodePtr)
125 }
126
127 /// Const-cast.
129 if (NodePtr)
131 const_cast<typename ilist_iterator<OptionsT, IsReverse,
132 false>::node_reference>(*NodePtr));
134 }
135
136 // Accessors...
138 assert(!NodePtr->isKnownSentinel());
139 return *Access::getValuePtr(NodePtr);
140 }
141 pointer operator->() const { return &operator*(); }
142
143 // Comparison operators
144 friend bool operator==(const ilist_iterator &LHS, const ilist_iterator &RHS) {
145 return LHS.NodePtr == RHS.NodePtr;
146 }
147 friend bool operator!=(const ilist_iterator &LHS, const ilist_iterator &RHS) {
148 return LHS.NodePtr != RHS.NodePtr;
149 }
150
151 // Increment and decrement operators...
153 NodePtr = IsReverse ? NodePtr->getNext() : NodePtr->getPrev();
154 return *this;
155 }
157 NodePtr = IsReverse ? NodePtr->getPrev() : NodePtr->getNext();
158 return *this;
159 }
161 ilist_iterator tmp = *this;
162 --*this;
163 return tmp;
164 }
166 ilist_iterator tmp = *this;
167 ++*this;
168 return tmp;
169 }
170
171 /// Get the underlying ilist_node.
172 node_pointer getNodePtr() const { return static_cast<node_pointer>(NodePtr); }
173
174 /// Check for end. Only valid if ilist_sentinel_tracking<true>.
175 bool isEnd() const { return NodePtr ? NodePtr->isSentinel() : false; }
176};
177
178/// Iterator for intrusive lists based on ilist_node. Much like ilist_iterator,
179/// but with the addition of two bits recording whether this position (when in
180/// a range) is half or fully open.
181template <class OptionsT, bool IsReverse, bool IsConst>
186
189
190public:
191 using value_type = typename Traits::value_type;
192 using pointer = typename Traits::pointer;
193 using reference = typename Traits::reference;
195 using iterator_category = std::bidirectional_iterator_tag;
196 using const_pointer = typename OptionsT::const_pointer;
197 using const_reference = typename OptionsT::const_reference;
198
199private:
200 using node_pointer = typename Traits::node_pointer;
201 using node_reference = typename Traits::node_reference;
202
203 node_pointer NodePtr = nullptr;
204
205 /// Is this position intended to contain any debug-info immediately before
206 /// the position?
207 mutable bool HeadInclusiveBit = false;
208 /// Is this position intended to contain any debug-info immediately after
209 /// the position?
210 mutable bool TailInclusiveBit = false;
211
212public:
213 /// Create from an ilist_node.
214 explicit ilist_iterator_w_bits(node_reference N) : NodePtr(&N) {}
215
217 : NodePtr(Access::getNodePtr(NP)) {}
219 : NodePtr(Access::getNodePtr(&NR)) {}
221
222 // This is templated so that we can allow constructing a const iterator from
223 // a nonconst iterator...
224 template <bool RHSIsConst>
227 std::enable_if_t<IsConst || !RHSIsConst, void *> = nullptr)
228 : NodePtr(RHS.NodePtr) {
229 HeadInclusiveBit = RHS.HeadInclusiveBit;
230 TailInclusiveBit = RHS.TailInclusiveBit;
231 }
232
233 // This is templated so that we can allow assigning to a const iterator from
234 // a nonconst iterator...
235 template <bool RHSIsConst>
236 std::enable_if_t<IsConst || !RHSIsConst, ilist_iterator_w_bits &>
238 NodePtr = RHS.NodePtr;
239 HeadInclusiveBit = RHS.HeadInclusiveBit;
240 TailInclusiveBit = RHS.TailInclusiveBit;
241 return *this;
242 }
243
244 /// Explicit conversion between forward/reverse iterators.
245 ///
246 /// Translate between forward and reverse iterators without changing range
247 /// boundaries. The resulting iterator will dereference (and have a handle)
248 /// to the previous node, which is somewhat unexpected; but converting the
249 /// two endpoints in a range will give the same range in reverse.
250 ///
251 /// This matches std::reverse_iterator conversions.
255
256 /// Get a reverse iterator to the same node.
257 ///
258 /// Gives a reverse iterator that will dereference (and have a handle) to the
259 /// same node. Converting the endpoint iterators in a range will give a
260 /// different range; for range operations, use the explicit conversions.
262 if (NodePtr)
265 }
266
267 /// Const-cast.
269 if (NodePtr) {
271 const_cast<typename ilist_iterator_w_bits<OptionsT, IsReverse,
272 false>::node_reference>(
273 *NodePtr));
274 New.HeadInclusiveBit = HeadInclusiveBit;
275 New.TailInclusiveBit = TailInclusiveBit;
276 return New;
277 }
279 }
280
281 // Accessors...
283 assert(!NodePtr->isKnownSentinel());
284 return *Access::getValuePtr(NodePtr);
285 }
286 pointer operator->() const { return &operator*(); }
287
288 // Comparison operators
290 const ilist_iterator_w_bits &RHS) {
291 return LHS.NodePtr == RHS.NodePtr;
292 }
294 const ilist_iterator_w_bits &RHS) {
295 return LHS.NodePtr != RHS.NodePtr;
296 }
297
298 // Increment and decrement operators...
300 NodePtr = IsReverse ? NodePtr->getNext() : NodePtr->getPrev();
301 HeadInclusiveBit = false;
302 TailInclusiveBit = false;
303 return *this;
304 }
306 NodePtr = IsReverse ? NodePtr->getPrev() : NodePtr->getNext();
307 HeadInclusiveBit = false;
308 TailInclusiveBit = false;
309 return *this;
310 }
312 ilist_iterator_w_bits tmp = *this;
313 --*this;
314 return tmp;
315 }
317 ilist_iterator_w_bits tmp = *this;
318 ++*this;
319 return tmp;
320 }
321
322 /// Get the underlying ilist_node.
323 node_pointer getNodePtr() const { return static_cast<node_pointer>(NodePtr); }
324
325 /// Check for end. Only valid if ilist_sentinel_tracking<true>.
326 bool isEnd() const { return NodePtr ? NodePtr->isSentinel() : false; }
327
328 bool getHeadBit() const { return HeadInclusiveBit; }
329 bool getTailBit() const { return TailInclusiveBit; }
330 void setHeadBit(bool SetBit) const { HeadInclusiveBit = SetBit; }
331 void setTailBit(bool SetBit) const { TailInclusiveBit = SetBit; }
332};
333
334template <typename From> struct simplify_type;
335
336/// Allow ilist_iterators to convert into pointers to a node automatically when
337/// used by the dyn_cast, cast, isa mechanisms...
338///
339/// FIXME: remove this, since there is no implicit conversion to NodeTy.
340template <class OptionsT, bool IsConst>
341struct simplify_type<ilist_iterator<OptionsT, false, IsConst>> {
344
345 static SimpleType getSimplifiedValue(const iterator &Node) { return &*Node; }
346};
347template <class OptionsT, bool IsConst>
348struct simplify_type<const ilist_iterator<OptionsT, false, IsConst>>
349 : simplify_type<ilist_iterator<OptionsT, false, IsConst>> {};
350
351// ilist_iterator_w_bits should also be accessible via isa/dyn_cast.
352template <class OptionsT, bool IsConst>
353struct simplify_type<ilist_iterator_w_bits<OptionsT, false, IsConst>> {
356
357 static SimpleType getSimplifiedValue(const iterator &Node) { return &*Node; }
358};
359template <class OptionsT, bool IsConst>
361 : simplify_type<ilist_iterator_w_bits<OptionsT, false, IsConst>> {};
362
363} // end namespace llvm
364
365#endif // LLVM_ADT_ILIST_ITERATOR_H
aarch64 promote const
basic Basic Alias true
#define I(x, y, z)
Definition: MD5.cpp:58
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
Value * RHS
Value * LHS
Iterator for intrusive lists based on ilist_node.
ilist_iterator_w_bits< OptionsT, !IsReverse, IsConst > getReverse() const
Get a reverse iterator to the same node.
ilist_iterator_w_bits(reference NR)
ilist_iterator_w_bits & operator--()
typename OptionsT::const_pointer const_pointer
ilist_iterator_w_bits(const ilist_iterator_w_bits< OptionsT, IsReverse, RHSIsConst > &RHS, std::enable_if_t< IsConst||!RHSIsConst, void * >=nullptr)
ilist_iterator_w_bits operator--(int)
typename OptionsT::const_reference const_reference
ilist_iterator_w_bits(node_reference N)
Create from an ilist_node.
std::bidirectional_iterator_tag iterator_category
ilist_iterator_w_bits< OptionsT, IsReverse, false > getNonConst() const
Const-cast.
node_pointer getNodePtr() const
Get the underlying ilist_node.
ilist_iterator_w_bits(const ilist_iterator_w_bits< OptionsT, !IsReverse, IsConst > &RHS)
Explicit conversion between forward/reverse iterators.
reference operator*() const
typename Traits::pointer pointer
ilist_iterator_w_bits & operator++()
friend bool operator==(const ilist_iterator_w_bits &LHS, const ilist_iterator_w_bits &RHS)
bool isEnd() const
Check for end. Only valid if ilist_sentinel_tracking<true>.
typename Traits::value_type value_type
ilist_iterator_w_bits operator++(int)
std::enable_if_t< IsConst||!RHSIsConst, ilist_iterator_w_bits & > operator=(const ilist_iterator_w_bits< OptionsT, IsReverse, RHSIsConst > &RHS)
void setTailBit(bool SetBit) const
void setHeadBit(bool SetBit) const
friend bool operator!=(const ilist_iterator_w_bits &LHS, const ilist_iterator_w_bits &RHS)
typename Traits::reference reference
Iterator for intrusive lists based on ilist_node.
typename Traits::reference reference
ilist_iterator()=default
std::bidirectional_iterator_tag iterator_category
ilist_iterator(reference NR)
bool isEnd() const
Check for end. Only valid if ilist_sentinel_tracking<true>.
node_pointer getNodePtr() const
Get the underlying ilist_node.
friend bool operator!=(const ilist_iterator &LHS, const ilist_iterator &RHS)
ilist_iterator operator--(int)
typename OptionsT::const_pointer const_pointer
ilist_iterator< OptionsT, !IsReverse, IsConst > getReverse() const
Get a reverse iterator to the same node.
reference operator*() const
ilist_iterator< OptionsT, IsReverse, false > getNonConst() const
Const-cast.
ilist_iterator & operator++()
typename Traits::value_type value_type
ilist_iterator(const ilist_iterator< OptionsT, !IsReverse, IsConst > &RHS)
Explicit conversion between forward/reverse iterators.
ilist_iterator(const ilist_iterator< OptionsT, IsReverse, RHSIsConst > &RHS, std::enable_if_t< IsConst||!RHSIsConst, void * >=nullptr)
friend bool operator==(const ilist_iterator &LHS, const ilist_iterator &RHS)
pointer operator->() const
ilist_iterator operator++(int)
ilist_iterator(node_reference N)
Create from an ilist_node.
ilist_iterator(pointer NP)
std::enable_if_t< IsConst||!RHSIsConst, ilist_iterator & > operator=(const ilist_iterator< OptionsT, IsReverse, RHSIsConst > &RHS)
typename OptionsT::const_reference const_reference
ilist_iterator & operator--()
typename Traits::pointer pointer
Implementation for an ilist node.
Definition: ilist_node.h:54
This file defines the ilist_node class template, which is a convenient base class for creating classe...
This is an optimization pass for GlobalISel generic memory operations.
Definition: AddressRanges.h:18
#define N
const typename OptionsT::value_type value_type
typename OptionsT::const_reference reference
Find const-correct node types.
An access class for ilist_node private API.
Definition: ilist_node.h:191
static pointer getValuePtr(node_type *N)
Definition: ilist_node.h:252
static SimpleType getSimplifiedValue(const iterator &Node)
Define a template that can be specialized by smart pointers to reflect the fact that they are automat...
Definition: Casting.h:34