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 | } // end namespace ilist_detail |
54 | |
55 | /// Iterator for intrusive lists based on ilist_node. |
56 | template <class OptionsT, bool IsReverse, bool IsConst> |
57 | class ilist_iterator : ilist_detail::SpecificNodeAccess<OptionsT> { |
58 | friend ilist_iterator<OptionsT, IsReverse, !IsConst>; |
59 | friend ilist_iterator<OptionsT, !IsReverse, IsConst>; |
60 | friend ilist_iterator<OptionsT, !IsReverse, !IsConst>; |
61 | |
62 | using Traits = ilist_detail::IteratorTraits<OptionsT, IsConst>; |
63 | using Access = ilist_detail::SpecificNodeAccess<OptionsT>; |
64 | |
65 | public: |
66 | using value_type = typename Traits::value_type; |
67 | using pointer = typename Traits::pointer; |
68 | using reference = typename Traits::reference; |
69 | using difference_type = ptrdiff_t; |
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 | |
74 | private: |
75 | using node_pointer = typename Traits::node_pointer; |
76 | using node_reference = typename Traits::node_reference; |
77 | |
78 | node_pointer NodePtr = nullptr; |
79 | |
80 | public: |
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> |
91 | ilist_iterator(const ilist_iterator<OptionsT, IsReverse, RHSIsConst> &RHS, |
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 &> |
99 | operator=(const ilist_iterator<OptionsT, IsReverse, RHSIsConst> &RHS) { |
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. |
112 | explicit ilist_iterator( |
113 | const ilist_iterator<OptionsT, !IsReverse, IsConst> &RHS) |
114 | : ilist_iterator(++RHS.getReverse()) {} |
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. |
121 | ilist_iterator<OptionsT, !IsReverse, IsConst> getReverse() const { |
122 | if (NodePtr) |
123 | return ilist_iterator<OptionsT, !IsReverse, IsConst>(*NodePtr); |
124 | return ilist_iterator<OptionsT, !IsReverse, IsConst>(); |
125 | } |
126 | |
127 | /// Const-cast. |
128 | ilist_iterator<OptionsT, IsReverse, false> getNonConst() const { |
129 | if (NodePtr) |
130 | return ilist_iterator<OptionsT, IsReverse, false>( |
131 | const_cast<typename ilist_iterator<OptionsT, IsReverse, |
132 | false>::node_reference>(*NodePtr)); |
133 | return ilist_iterator<OptionsT, IsReverse, false>(); |
134 | } |
135 | |
136 | // Accessors... |
137 | reference operator*() const { |
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... |
152 | ilist_iterator &operator--() { |
153 | NodePtr = IsReverse ? NodePtr->getNext() : NodePtr->getPrev(); |
154 | return *this; |
155 | } |
156 | ilist_iterator &operator++() { |
157 | NodePtr = IsReverse ? NodePtr->getPrev() : NodePtr->getNext(); |
158 | return *this; |
159 | } |
160 | ilist_iterator operator--(int) { |
161 | ilist_iterator tmp = *this; |
162 | --*this; |
163 | return tmp; |
164 | } |
165 | ilist_iterator operator++(int) { |
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. |
181 | template <class OptionsT, bool IsReverse, bool IsConst> |
182 | class ilist_iterator_w_bits : ilist_detail::SpecificNodeAccess<OptionsT> { |
183 | friend ilist_iterator_w_bits<OptionsT, IsReverse, !IsConst>; |
184 | friend ilist_iterator_w_bits<OptionsT, !IsReverse, IsConst>; |
185 | friend ilist_iterator<OptionsT, !IsReverse, !IsConst>; |
186 | |
187 | using Traits = ilist_detail::IteratorTraits<OptionsT, IsConst>; |
188 | using Access = ilist_detail::SpecificNodeAccess<OptionsT>; |
189 | |
190 | public: |
191 | using value_type = typename Traits::value_type; |
192 | using pointer = typename Traits::pointer; |
193 | using reference = typename Traits::reference; |
194 | using difference_type = ptrdiff_t; |
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 | |
199 | private: |
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 | |
212 | public: |
213 | /// Create from an ilist_node. |
214 | explicit ilist_iterator_w_bits(node_reference N) : NodePtr(&N) {} |
215 | |
216 | explicit ilist_iterator_w_bits(pointer NP) |
217 | : NodePtr(Access::getNodePtr(NP)) {} |
218 | explicit ilist_iterator_w_bits(reference NR) |
219 | : NodePtr(Access::getNodePtr(&NR)) {} |
220 | ilist_iterator_w_bits() = default; |
221 | |
222 | // This is templated so that we can allow constructing a const iterator from |
223 | // a nonconst iterator... |
224 | template <bool RHSIsConst> |
225 | ilist_iterator_w_bits( |
226 | const ilist_iterator_w_bits<OptionsT, IsReverse, RHSIsConst> &RHS, |
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 &> |
237 | operator=(const ilist_iterator_w_bits<OptionsT, IsReverse, RHSIsConst> &RHS) { |
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. |
252 | explicit ilist_iterator_w_bits( |
253 | const ilist_iterator_w_bits<OptionsT, !IsReverse, IsConst> &RHS) |
254 | : ilist_iterator_w_bits(++RHS.getReverse()) {} |
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. |
261 | ilist_iterator_w_bits<OptionsT, !IsReverse, IsConst> getReverse() const { |
262 | if (NodePtr) |
263 | return ilist_iterator_w_bits<OptionsT, !IsReverse, IsConst>(*NodePtr); |
264 | return ilist_iterator_w_bits<OptionsT, !IsReverse, IsConst>(); |
265 | } |
266 | |
267 | /// Const-cast. |
268 | ilist_iterator_w_bits<OptionsT, IsReverse, false> getNonConst() const { |
269 | if (NodePtr) { |
270 | auto New = ilist_iterator_w_bits<OptionsT, IsReverse, false>( |
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 | } |
278 | return ilist_iterator_w_bits<OptionsT, IsReverse, false>(); |
279 | } |
280 | |
281 | // Accessors... |
282 | reference operator*() const { |
283 | assert(!NodePtr->isKnownSentinel()); |
284 | return *Access::getValuePtr(NodePtr); |
285 | } |
286 | pointer operator->() const { return &operator*(); } |
287 | |
288 | // Comparison operators |
289 | friend bool operator==(const ilist_iterator_w_bits &LHS, |
290 | const ilist_iterator_w_bits &RHS) { |
291 | return LHS.NodePtr == RHS.NodePtr; |
292 | } |
293 | friend bool operator!=(const ilist_iterator_w_bits &LHS, |
294 | const ilist_iterator_w_bits &RHS) { |
295 | return LHS.NodePtr != RHS.NodePtr; |
296 | } |
297 | |
298 | // Increment and decrement operators... |
299 | ilist_iterator_w_bits &operator--() { |
300 | NodePtr = IsReverse ? NodePtr->getNext() : NodePtr->getPrev(); |
301 | HeadInclusiveBit = false; |
302 | TailInclusiveBit = false; |
303 | return *this; |
304 | } |
305 | ilist_iterator_w_bits &operator++() { |
306 | NodePtr = IsReverse ? NodePtr->getPrev() : NodePtr->getNext(); |
307 | HeadInclusiveBit = false; |
308 | TailInclusiveBit = false; |
309 | return *this; |
310 | } |
311 | ilist_iterator_w_bits operator--(int) { |
312 | ilist_iterator_w_bits tmp = *this; |
313 | --*this; |
314 | return tmp; |
315 | } |
316 | ilist_iterator_w_bits operator++(int) { |
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 | |
334 | template <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. |
340 | template <class OptionsT, bool IsConst> |
341 | struct simplify_type<ilist_iterator<OptionsT, false, IsConst>> { |
342 | using iterator = ilist_iterator<OptionsT, false, IsConst>; |
343 | using SimpleType = typename iterator::pointer; |
344 | |
345 | static SimpleType getSimplifiedValue(const iterator &Node) { return &*Node; } |
346 | }; |
347 | template <class OptionsT, bool IsConst> |
348 | struct 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. |
352 | template <class OptionsT, bool IsConst> |
353 | struct simplify_type<ilist_iterator_w_bits<OptionsT, false, IsConst>> { |
354 | using iterator = ilist_iterator_w_bits<OptionsT, false, IsConst>; |
355 | using SimpleType = typename iterator::pointer; |
356 | |
357 | static SimpleType getSimplifiedValue(const iterator &Node) { return &*Node; } |
358 | }; |
359 | template <class OptionsT, bool IsConst> |
360 | struct simplify_type<const ilist_iterator_w_bits<OptionsT, false, IsConst>> |
361 | : simplify_type<ilist_iterator_w_bits<OptionsT, false, IsConst>> {}; |
362 | |
363 | } // end namespace llvm |
364 | |
365 | #endif // LLVM_ADT_ILIST_ITERATOR_H |
366 | |