LLVM 18.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#ifdef EXPERIMENTAL_DEBUGINFO_ITERATORS
206 // (Default: Off) Allow extra position-information flags to be stored
207 // in iterators, in aid of removing debug-info intrinsics from LLVM.
208
209 /// Is this position intended to contain any debug-info immediately before
210 /// the position?
211 mutable bool HeadInclusiveBit = false;
212 /// Is this position intended to contain any debug-info immediately after
213 /// the position?
214 mutable bool TailInclusiveBit = false;
215#endif
216
217public:
218 /// Create from an ilist_node.
219 explicit ilist_iterator_w_bits(node_reference N) : NodePtr(&N) {}
220
222 : NodePtr(Access::getNodePtr(NP)) {}
224 : NodePtr(Access::getNodePtr(&NR)) {}
226
227 // This is templated so that we can allow constructing a const iterator from
228 // a nonconst iterator...
229 template <bool RHSIsConst>
232 std::enable_if_t<IsConst || !RHSIsConst, void *> = nullptr)
233 : NodePtr(RHS.NodePtr) {
234#ifdef EXPERIMENTAL_DEBUGINFO_ITERATORS
235 HeadInclusiveBit = RHS.HeadInclusiveBit;
236 TailInclusiveBit = RHS.TailInclusiveBit;
237#endif
238 }
239
240 // This is templated so that we can allow assigning to a const iterator from
241 // a nonconst iterator...
242 template <bool RHSIsConst>
243 std::enable_if_t<IsConst || !RHSIsConst, ilist_iterator_w_bits &>
245 NodePtr = RHS.NodePtr;
246#ifdef EXPERIMENTAL_DEBUGINFO_ITERATORS
247 HeadInclusiveBit = RHS.HeadInclusiveBit;
248 TailInclusiveBit = RHS.TailInclusiveBit;
249#endif
250 return *this;
251 }
252
253 /// Explicit conversion between forward/reverse iterators.
254 ///
255 /// Translate between forward and reverse iterators without changing range
256 /// boundaries. The resulting iterator will dereference (and have a handle)
257 /// to the previous node, which is somewhat unexpected; but converting the
258 /// two endpoints in a range will give the same range in reverse.
259 ///
260 /// This matches std::reverse_iterator conversions.
264
265 /// Get a reverse iterator to the same node.
266 ///
267 /// Gives a reverse iterator that will dereference (and have a handle) to the
268 /// same node. Converting the endpoint iterators in a range will give a
269 /// different range; for range operations, use the explicit conversions.
271 if (NodePtr)
274 }
275
276 /// Const-cast.
278 if (NodePtr) {
280 const_cast<typename ilist_iterator_w_bits<OptionsT, IsReverse,
281 false>::node_reference>(
282 *NodePtr));
283#ifdef EXPERIMENTAL_DEBUGINFO_ITERATORS
284 New.HeadInclusiveBit = HeadInclusiveBit;
285 New.TailInclusiveBit = TailInclusiveBit;
286#endif
287 return New;
288 }
290 }
291
292 // Accessors...
294 assert(!NodePtr->isKnownSentinel());
295 return *Access::getValuePtr(NodePtr);
296 }
297 pointer operator->() const { return &operator*(); }
298
299 // Comparison operators
301 const ilist_iterator_w_bits &RHS) {
302 return LHS.NodePtr == RHS.NodePtr;
303 }
305 const ilist_iterator_w_bits &RHS) {
306 return LHS.NodePtr != RHS.NodePtr;
307 }
308
309 // Increment and decrement operators...
311 NodePtr = IsReverse ? NodePtr->getNext() : NodePtr->getPrev();
312#ifdef EXPERIMENTAL_DEBUGINFO_ITERATORS
313 HeadInclusiveBit = false;
314 TailInclusiveBit = false;
315#endif
316 return *this;
317 }
319 NodePtr = IsReverse ? NodePtr->getPrev() : NodePtr->getNext();
320#ifdef EXPERIMENTAL_DEBUGINFO_ITERATORS
321 HeadInclusiveBit = false;
322 TailInclusiveBit = false;
323#endif
324 return *this;
325 }
327 ilist_iterator_w_bits tmp = *this;
328 --*this;
329 return tmp;
330 }
332 ilist_iterator_w_bits tmp = *this;
333 ++*this;
334 return tmp;
335 }
336
337 /// Get the underlying ilist_node.
338 node_pointer getNodePtr() const { return static_cast<node_pointer>(NodePtr); }
339
340 /// Check for end. Only valid if ilist_sentinel_tracking<true>.
341 bool isEnd() const { return NodePtr ? NodePtr->isSentinel() : false; }
342
343#ifdef EXPERIMENTAL_DEBUGINFO_ITERATORS
344 bool getHeadBit() const { return HeadInclusiveBit; }
345 bool getTailBit() const { return TailInclusiveBit; }
346 void setHeadBit(bool SetBit) const { HeadInclusiveBit = SetBit; }
347 void setTailBit(bool SetBit) const { TailInclusiveBit = SetBit; }
348#else
349 // Store and return no information if we're not using this feature.
350 bool getHeadBit() const { return false; }
351 bool getTailBit() const { return false; }
352 void setHeadBit(bool SetBit) const { (void)SetBit; }
353 void setTailBit(bool SetBit) const { (void)SetBit; }
354#endif
355};
356
357template <typename From> struct simplify_type;
358
359/// Allow ilist_iterators to convert into pointers to a node automatically when
360/// used by the dyn_cast, cast, isa mechanisms...
361///
362/// FIXME: remove this, since there is no implicit conversion to NodeTy.
363template <class OptionsT, bool IsConst>
364struct simplify_type<ilist_iterator<OptionsT, false, IsConst>> {
367
368 static SimpleType getSimplifiedValue(const iterator &Node) { return &*Node; }
369};
370template <class OptionsT, bool IsConst>
371struct simplify_type<const ilist_iterator<OptionsT, false, IsConst>>
372 : simplify_type<ilist_iterator<OptionsT, false, IsConst>> {};
373
374// ilist_iterator_w_bits should also be accessible via isa/dyn_cast.
375template <class OptionsT, bool IsConst>
376struct simplify_type<ilist_iterator_w_bits<OptionsT, false, IsConst>> {
379
380 static SimpleType getSimplifiedValue(const iterator &Node) { return &*Node; }
381};
382template <class OptionsT, bool IsConst>
384 : simplify_type<ilist_iterator_w_bits<OptionsT, false, IsConst>> {};
385
386} // end namespace llvm
387
388#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