Line data Source code
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 :
18 : namespace llvm {
19 :
20 : namespace ilist_detail {
21 :
22 : /// Find const-correct node types.
23 : template <class OptionsT, bool IsConst> struct IteratorTraits;
24 : template <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;
28 : using node_pointer = ilist_node_impl<OptionsT> *;
29 : using node_reference = ilist_node_impl<OptionsT> &;
30 : };
31 : template <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;
35 : using node_pointer = const ilist_node_impl<OptionsT> *;
36 : using node_reference = const ilist_node_impl<OptionsT> &;
37 : };
38 :
39 : template <bool IsReverse> struct IteratorHelper;
40 : template <> struct IteratorHelper<false> : ilist_detail::NodeAccess {
41 : using Access = ilist_detail::NodeAccess;
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 : };
46 : template <> struct IteratorHelper<true> : ilist_detail::NodeAccess {
47 : using Access = ilist_detail::NodeAccess;
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.
56 : template <class IteratorTy, class ParentTy, bool IsConst>
57 : class iterator_parent_access;
58 : template <class IteratorTy, class ParentTy>
59 : class iterator_parent_access<IteratorTy, ParentTy, true> {
60 : public:
61 : inline const ParentTy *getNodeParent() const {
62 : return static_cast<IteratorTy *>(this)->NodePtr->getParent();
63 : }
64 : };
65 : template <class IteratorTy, class ParentTy>
66 : class iterator_parent_access<IteratorTy, ParentTy, false> {
67 : public:
68 : inline ParentTy *getNodeParent() {
69 : return static_cast<IteratorTy *>(this)->NodePtr->getParent();
70 : }
71 : };
72 : template <class IteratorTy>
73 : class iterator_parent_access<IteratorTy, void, true> {};
74 : template <class IteratorTy>
75 : class iterator_parent_access<IteratorTy, void, false> {};
76 :
77 : } // end namespace ilist_detail
78 :
79 : /// Iterator for intrusive lists based on ilist_node.
80 : template <class OptionsT, bool IsReverse, bool IsConst>
81 : class ilist_iterator : ilist_detail::SpecificNodeAccess<OptionsT>,
82 : public ilist_detail::iterator_parent_access<
83 : ilist_iterator<OptionsT, IsReverse, IsConst>,
84 : typename OptionsT::parent_ty, IsConst> {
85 : friend ilist_iterator<OptionsT, IsReverse, !IsConst>;
86 : friend ilist_iterator<OptionsT, !IsReverse, IsConst>;
87 : friend ilist_iterator<OptionsT, !IsReverse, !IsConst>;
88 : friend ilist_detail::iterator_parent_access<
89 : ilist_iterator<OptionsT, IsReverse, IsConst>,
90 : typename OptionsT::parent_ty, IsConst>;
91 :
92 : using Traits = ilist_detail::IteratorTraits<OptionsT, IsConst>;
93 : using Access = ilist_detail::SpecificNodeAccess<OptionsT>;
94 :
95 : public:
96 : using value_type = typename Traits::value_type;
97 : using pointer = typename Traits::pointer;
98 : using reference = typename Traits::reference;
99 : using difference_type = ptrdiff_t;
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 :
104 : private:
105 : using node_pointer = typename Traits::node_pointer;
106 : using node_reference = typename Traits::node_reference;
107 :
108 : node_pointer NodePtr = nullptr;
109 :
110 : public:
111 : /// Create from an ilist_node.
112 8666 : 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>
121 : ilist_iterator(const ilist_iterator<OptionsT, IsReverse, RHSIsConst> &RHS,
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 &>
129 : operator=(const ilist_iterator<OptionsT, IsReverse, RHSIsConst> &RHS) {
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.
142 : explicit ilist_iterator(
143 : const ilist_iterator<OptionsT, !IsReverse, IsConst> &RHS)
144 : : ilist_iterator(++RHS.getReverse()) {}
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.
151 : ilist_iterator<OptionsT, !IsReverse, IsConst> getReverse() const {
152 : if (NodePtr)
153 : return ilist_iterator<OptionsT, !IsReverse, IsConst>(*NodePtr);
154 : return ilist_iterator<OptionsT, !IsReverse, IsConst>();
155 : }
156 :
157 : /// Const-cast.
158 : ilist_iterator<OptionsT, IsReverse, false> getNonConst() const {
159 : if (NodePtr)
160 : return ilist_iterator<OptionsT, IsReverse, false>(
161 : const_cast<typename ilist_iterator<OptionsT, IsReverse,
162 : false>::node_reference>(*NodePtr));
163 : return ilist_iterator<OptionsT, IsReverse, false>();
164 : }
165 :
166 : // Accessors...
167 60983 : reference operator*() const {
168 60983 : assert(!NodePtr->isKnownSentinel());
169 60983 : 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 65316 : friend bool operator!=(const ilist_iterator &LHS, const ilist_iterator &RHS) {
178 65316 : return LHS.NodePtr != RHS.NodePtr;
179 : }
180 :
181 : // Increment and decrement operators...
182 : ilist_iterator &operator--() {
183 : NodePtr = IsReverse ? NodePtr->getNext() : NodePtr->getPrev();
184 : return *this;
185 : }
186 65316 : ilist_iterator &operator++() {
187 65316 : NodePtr = IsReverse ? NodePtr->getPrev() : NodePtr->getNext();
188 65316 : return *this;
189 : }
190 : ilist_iterator operator--(int) {
191 : ilist_iterator tmp = *this;
192 : --*this;
193 : return tmp;
194 : }
195 : ilist_iterator operator++(int) {
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.
213 : template <class OptionsT, bool IsReverse, bool IsConst>
214 : class ilist_iterator_w_bits
215 : : ilist_detail::SpecificNodeAccess<OptionsT>,
216 : public ilist_detail::iterator_parent_access<
217 : ilist_iterator_w_bits<OptionsT, IsReverse, IsConst>,
218 : typename OptionsT::parent_ty, IsConst> {
219 : friend ilist_iterator_w_bits<OptionsT, IsReverse, !IsConst>;
220 : friend ilist_iterator_w_bits<OptionsT, !IsReverse, IsConst>;
221 : friend ilist_iterator<OptionsT, !IsReverse, !IsConst>;
222 : friend ilist_detail::iterator_parent_access<
223 : ilist_iterator_w_bits<OptionsT, IsReverse, IsConst>,
224 : typename OptionsT::parent_ty, IsConst>;
225 :
226 : using Traits = ilist_detail::IteratorTraits<OptionsT, IsConst>;
227 : using Access = ilist_detail::SpecificNodeAccess<OptionsT>;
228 :
229 : public:
230 : using value_type = typename Traits::value_type;
231 : using pointer = typename Traits::pointer;
232 : using reference = typename Traits::reference;
233 : using difference_type = ptrdiff_t;
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 :
238 : private:
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 :
251 : public:
252 : /// Create from an ilist_node.
253 117082 : explicit ilist_iterator_w_bits(node_reference N) : NodePtr(&N) {}
254 :
255 : explicit ilist_iterator_w_bits(pointer NP)
256 : : NodePtr(Access::getNodePtr(NP)) {}
257 : explicit ilist_iterator_w_bits(reference NR)
258 : : NodePtr(Access::getNodePtr(&NR)) {}
259 0 : ilist_iterator_w_bits() = default;
260 :
261 : // This is templated so that we can allow constructing a const iterator from
262 : // a nonconst iterator...
263 : template <bool RHSIsConst>
264 : ilist_iterator_w_bits(
265 : const ilist_iterator_w_bits<OptionsT, IsReverse, RHSIsConst> &RHS,
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 &>
276 : operator=(const ilist_iterator_w_bits<OptionsT, IsReverse, RHSIsConst> &RHS) {
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.
291 : explicit ilist_iterator_w_bits(
292 : const ilist_iterator_w_bits<OptionsT, !IsReverse, IsConst> &RHS)
293 : : ilist_iterator_w_bits(++RHS.getReverse()) {}
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.
300 : ilist_iterator_w_bits<OptionsT, !IsReverse, IsConst> getReverse() const {
301 : if (NodePtr)
302 : return ilist_iterator_w_bits<OptionsT, !IsReverse, IsConst>(*NodePtr);
303 : return ilist_iterator_w_bits<OptionsT, !IsReverse, IsConst>();
304 : }
305 :
306 : /// Const-cast.
307 : ilist_iterator_w_bits<OptionsT, IsReverse, false> getNonConst() const {
308 : if (NodePtr) {
309 : auto New = ilist_iterator_w_bits<OptionsT, IsReverse, false>(
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 : }
317 : return ilist_iterator_w_bits<OptionsT, IsReverse, false>();
318 : }
319 :
320 : // Accessors...
321 284157 : reference operator*() const {
322 284157 : assert(!NodePtr->isKnownSentinel());
323 284157 : return *Access::getValuePtr(NodePtr);
324 : }
325 : pointer operator->() const { return &operator*(); }
326 :
327 : // Comparison operators
328 : friend bool operator==(const ilist_iterator_w_bits &LHS,
329 : const ilist_iterator_w_bits &RHS) {
330 : return LHS.NodePtr == RHS.NodePtr;
331 : }
332 342698 : friend bool operator!=(const ilist_iterator_w_bits &LHS,
333 : const ilist_iterator_w_bits &RHS) {
334 342698 : return LHS.NodePtr != RHS.NodePtr;
335 : }
336 :
337 : // Increment and decrement operators...
338 : ilist_iterator_w_bits &operator--() {
339 : NodePtr = IsReverse ? NodePtr->getNext() : NodePtr->getPrev();
340 : HeadInclusiveBit = false;
341 : TailInclusiveBit = false;
342 : return *this;
343 : }
344 342698 : ilist_iterator_w_bits &operator++() {
345 342698 : NodePtr = IsReverse ? NodePtr->getPrev() : NodePtr->getNext();
346 342698 : HeadInclusiveBit = false;
347 342698 : TailInclusiveBit = false;
348 342698 : return *this;
349 : }
350 : ilist_iterator_w_bits operator--(int) {
351 : ilist_iterator_w_bits tmp = *this;
352 : --*this;
353 : return tmp;
354 : }
355 : ilist_iterator_w_bits operator++(int) {
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 58541 : void setHeadBit(bool SetBit) const { HeadInclusiveBit = SetBit; }
372 : void setTailBit(bool SetBit) const { TailInclusiveBit = SetBit; }
373 : };
374 :
375 : template <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.
381 : template <class OptionsT, bool IsConst>
382 : struct simplify_type<ilist_iterator<OptionsT, false, IsConst>> {
383 : using iterator = ilist_iterator<OptionsT, false, IsConst>;
384 : using SimpleType = typename iterator::pointer;
385 :
386 : static SimpleType getSimplifiedValue(const iterator &Node) { return &*Node; }
387 : };
388 : template <class OptionsT, bool IsConst>
389 : struct 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.
393 : template <class OptionsT, bool IsConst>
394 : struct simplify_type<ilist_iterator_w_bits<OptionsT, false, IsConst>> {
395 : using iterator = ilist_iterator_w_bits<OptionsT, false, IsConst>;
396 : using SimpleType = typename iterator::pointer;
397 :
398 : static SimpleType getSimplifiedValue(const iterator &Node) { return &*Node; }
399 : };
400 : template <class OptionsT, bool IsConst>
401 : struct simplify_type<const ilist_iterator_w_bits<OptionsT, false, IsConst>>
402 : : simplify_type<ilist_iterator_w_bits<OptionsT, false, IsConst>> {};
403 :
404 : } // end namespace llvm
405 :
406 : #endif // LLVM_ADT_ILIST_ITERATOR_H
|
