LLVM 20.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/// Mixin class used to add a \a getNodeParent() function to iterators iff the
54/// list uses \a ilist_parent, calling through to the node's \a getParent(). For
55/// more details see \a ilist_node.
56template <class IteratorTy, class ParentTy, bool IsConst>
58template <class IteratorTy, class ParentTy>
59class iterator_parent_access<IteratorTy, ParentTy, true> {
60public:
61 inline const ParentTy *getNodeParent() const {
62 return static_cast<IteratorTy *>(this)->NodePtr->getParent();
63 }
64};
65template <class IteratorTy, class ParentTy>
66class iterator_parent_access<IteratorTy, ParentTy, false> {
67public:
68 inline ParentTy *getNodeParent() {
69 return static_cast<IteratorTy *>(this)->NodePtr->getParent();
70 }
71};
72template <class IteratorTy>
73class iterator_parent_access<IteratorTy, void, true> {};
74template <class IteratorTy>
75class iterator_parent_access<IteratorTy, void, false> {};
76
77} // end namespace ilist_detail
78
79/// Iterator for intrusive lists based on ilist_node.
80template <class OptionsT, bool IsReverse, bool IsConst>
83 ilist_iterator<OptionsT, IsReverse, IsConst>,
84 typename OptionsT::parent_ty, IsConst> {
90 typename OptionsT::parent_ty, IsConst>;
91
94
95public:
96 using value_type = typename Traits::value_type;
97 using pointer = typename Traits::pointer;
98 using reference = typename Traits::reference;
100 using iterator_category = std::bidirectional_iterator_tag;
101 using const_pointer = typename OptionsT::const_pointer;
102 using const_reference = typename OptionsT::const_reference;
103
104private:
105 using node_pointer = typename Traits::node_pointer;
106 using node_reference = typename Traits::node_reference;
107
108 node_pointer NodePtr = nullptr;
109
110public:
111 /// Create from an ilist_node.
112 explicit ilist_iterator(node_reference N) : NodePtr(&N) {}
113
114 explicit ilist_iterator(pointer NP) : NodePtr(Access::getNodePtr(NP)) {}
115 explicit ilist_iterator(reference NR) : NodePtr(Access::getNodePtr(&NR)) {}
116 ilist_iterator() = default;
117
118 // This is templated so that we can allow constructing a const iterator from
119 // a nonconst iterator...
120 template <bool RHSIsConst>
122 std::enable_if_t<IsConst || !RHSIsConst, void *> = nullptr)
123 : NodePtr(RHS.NodePtr) {}
124
125 // This is templated so that we can allow assigning to a const iterator from
126 // a nonconst iterator...
127 template <bool RHSIsConst>
128 std::enable_if_t<IsConst || !RHSIsConst, ilist_iterator &>
130 NodePtr = RHS.NodePtr;
131 return *this;
132 }
133
134 /// Explicit conversion between forward/reverse iterators.
135 ///
136 /// Translate between forward and reverse iterators without changing range
137 /// boundaries. The resulting iterator will dereference (and have a handle)
138 /// to the previous node, which is somewhat unexpected; but converting the
139 /// two endpoints in a range will give the same range in reverse.
140 ///
141 /// This matches std::reverse_iterator conversions.
145
146 /// Get a reverse iterator to the same node.
147 ///
148 /// Gives a reverse iterator that will dereference (and have a handle) to the
149 /// same node. Converting the endpoint iterators in a range will give a
150 /// different range; for range operations, use the explicit conversions.
152 if (NodePtr)
155 }
156
157 /// Const-cast.
159 if (NodePtr)
161 const_cast<typename ilist_iterator<OptionsT, IsReverse,
162 false>::node_reference>(*NodePtr));
164 }
165
166 // Accessors...
168 assert(!NodePtr->isKnownSentinel());
169 return *Access::getValuePtr(NodePtr);
170 }
171 pointer operator->() const { return &operator*(); }
172
173 // Comparison operators
174 friend bool operator==(const ilist_iterator &LHS, const ilist_iterator &RHS) {
175 return LHS.NodePtr == RHS.NodePtr;
176 }
177 friend bool operator!=(const ilist_iterator &LHS, const ilist_iterator &RHS) {
178 return LHS.NodePtr != RHS.NodePtr;
179 }
180
181 // Increment and decrement operators...
183 NodePtr = IsReverse ? NodePtr->getNext() : NodePtr->getPrev();
184 return *this;
185 }
187 NodePtr = IsReverse ? NodePtr->getPrev() : NodePtr->getNext();
188 return *this;
189 }
191 ilist_iterator tmp = *this;
192 --*this;
193 return tmp;
194 }
196 ilist_iterator tmp = *this;
197 ++*this;
198 return tmp;
199 }
200
201 bool isValid() const { return NodePtr; }
202
203 /// Get the underlying ilist_node.
204 node_pointer getNodePtr() const { return static_cast<node_pointer>(NodePtr); }
205
206 /// Check for end. Only valid if ilist_sentinel_tracking<true>.
207 bool isEnd() const { return NodePtr ? NodePtr->isSentinel() : false; }
208};
209
210/// Iterator for intrusive lists based on ilist_node. Much like ilist_iterator,
211/// but with the addition of two bits recording whether this position (when in
212/// a range) is half or fully open.
213template <class OptionsT, bool IsReverse, bool IsConst>
217 ilist_iterator_w_bits<OptionsT, IsReverse, IsConst>,
218 typename OptionsT::parent_ty, IsConst> {
224 typename OptionsT::parent_ty, IsConst>;
225
228
229public:
230 using value_type = typename Traits::value_type;
231 using pointer = typename Traits::pointer;
232 using reference = typename Traits::reference;
234 using iterator_category = std::bidirectional_iterator_tag;
235 using const_pointer = typename OptionsT::const_pointer;
236 using const_reference = typename OptionsT::const_reference;
237
238private:
239 using node_pointer = typename Traits::node_pointer;
240 using node_reference = typename Traits::node_reference;
241
242 node_pointer NodePtr = nullptr;
243
244 /// Is this position intended to contain any debug-info immediately before
245 /// the position?
246 mutable bool HeadInclusiveBit = false;
247 /// Is this position intended to contain any debug-info immediately after
248 /// the position?
249 mutable bool TailInclusiveBit = false;
250
251public:
252 /// Create from an ilist_node.
253 explicit ilist_iterator_w_bits(node_reference N) : NodePtr(&N) {}
254
256 : NodePtr(Access::getNodePtr(NP)) {}
258 : NodePtr(Access::getNodePtr(&NR)) {}
260
261 // This is templated so that we can allow constructing a const iterator from
262 // a nonconst iterator...
263 template <bool RHSIsConst>
266 std::enable_if_t<IsConst || !RHSIsConst, void *> = nullptr)
267 : NodePtr(RHS.NodePtr) {
268 HeadInclusiveBit = RHS.HeadInclusiveBit;
269 TailInclusiveBit = RHS.TailInclusiveBit;
270 }
271
272 // This is templated so that we can allow assigning to a const iterator from
273 // a nonconst iterator...
274 template <bool RHSIsConst>
275 std::enable_if_t<IsConst || !RHSIsConst, ilist_iterator_w_bits &>
277 NodePtr = RHS.NodePtr;
278 HeadInclusiveBit = RHS.HeadInclusiveBit;
279 TailInclusiveBit = RHS.TailInclusiveBit;
280 return *this;
281 }
282
283 /// Explicit conversion between forward/reverse iterators.
284 ///
285 /// Translate between forward and reverse iterators without changing range
286 /// boundaries. The resulting iterator will dereference (and have a handle)
287 /// to the previous node, which is somewhat unexpected; but converting the
288 /// two endpoints in a range will give the same range in reverse.
289 ///
290 /// This matches std::reverse_iterator conversions.
294
295 /// Get a reverse iterator to the same node.
296 ///
297 /// Gives a reverse iterator that will dereference (and have a handle) to the
298 /// same node. Converting the endpoint iterators in a range will give a
299 /// different range; for range operations, use the explicit conversions.
301 if (NodePtr)
304 }
305
306 /// Const-cast.
308 if (NodePtr) {
310 const_cast<typename ilist_iterator_w_bits<OptionsT, IsReverse,
311 false>::node_reference>(
312 *NodePtr));
313 New.HeadInclusiveBit = HeadInclusiveBit;
314 New.TailInclusiveBit = TailInclusiveBit;
315 return New;
316 }
318 }
319
320 // Accessors...
322 assert(!NodePtr->isKnownSentinel());
323 return *Access::getValuePtr(NodePtr);
324 }
325 pointer operator->() const { return &operator*(); }
326
327 // Comparison operators
329 const ilist_iterator_w_bits &RHS) {
330 return LHS.NodePtr == RHS.NodePtr;
331 }
333 const ilist_iterator_w_bits &RHS) {
334 return LHS.NodePtr != RHS.NodePtr;
335 }
336
337 // Increment and decrement operators...
339 NodePtr = IsReverse ? NodePtr->getNext() : NodePtr->getPrev();
340 HeadInclusiveBit = false;
341 TailInclusiveBit = false;
342 return *this;
343 }
345 NodePtr = IsReverse ? NodePtr->getPrev() : NodePtr->getNext();
346 HeadInclusiveBit = false;
347 TailInclusiveBit = false;
348 return *this;
349 }
351 ilist_iterator_w_bits tmp = *this;
352 --*this;
353 return tmp;
354 }
356 ilist_iterator_w_bits tmp = *this;
357 ++*this;
358 return tmp;
359 }
360
361 bool isValid() const { return NodePtr; }
362
363 /// Get the underlying ilist_node.
364 node_pointer getNodePtr() const { return static_cast<node_pointer>(NodePtr); }
365
366 /// Check for end. Only valid if ilist_sentinel_tracking<true>.
367 bool isEnd() const { return NodePtr ? NodePtr->isSentinel() : false; }
368
369 bool getHeadBit() const { return HeadInclusiveBit; }
370 bool getTailBit() const { return TailInclusiveBit; }
371 void setHeadBit(bool SetBit) const { HeadInclusiveBit = SetBit; }
372 void setTailBit(bool SetBit) const { TailInclusiveBit = SetBit; }
373};
374
375template <typename From> struct simplify_type;
376
377/// Allow ilist_iterators to convert into pointers to a node automatically when
378/// used by the dyn_cast, cast, isa mechanisms...
379///
380/// FIXME: remove this, since there is no implicit conversion to NodeTy.
381template <class OptionsT, bool IsConst>
382struct simplify_type<ilist_iterator<OptionsT, false, IsConst>> {
385
386 static SimpleType getSimplifiedValue(const iterator &Node) { return &*Node; }
387};
388template <class OptionsT, bool IsConst>
389struct simplify_type<const ilist_iterator<OptionsT, false, IsConst>>
390 : simplify_type<ilist_iterator<OptionsT, false, IsConst>> {};
391
392// ilist_iterator_w_bits should also be accessible via isa/dyn_cast.
393template <class OptionsT, bool IsConst>
394struct simplify_type<ilist_iterator_w_bits<OptionsT, false, IsConst>> {
397
398 static SimpleType getSimplifiedValue(const iterator &Node) { return &*Node; }
399};
400template <class OptionsT, bool IsConst>
402 : simplify_type<ilist_iterator_w_bits<OptionsT, false, IsConst>> {};
403
404} // end namespace llvm
405
406#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
Mixin class used to add a getNodeParent() function to iterators iff the list uses ilist_parent,...
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:75
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:228
static pointer getValuePtr(node_type *N)
Definition: ilist_node.h:289
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