Branch data 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 : 0 : 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 : 0 : reference operator*() const {
168 [ # # ]: 0 : assert(!NodePtr->isKnownSentinel());
169 : 0 : 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 : 0 : friend bool operator!=(const ilist_iterator &LHS, const ilist_iterator &RHS) {
178 : 0 : 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 : 0 : ilist_iterator &operator++() {
187 : 0 : NodePtr = IsReverse ? NodePtr->getPrev() : NodePtr->getNext();
188 : 0 : 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 : 0 : 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 : 0 : reference operator*() const {
322 [ # # ]: 0 : assert(!NodePtr->isKnownSentinel());
323 : 0 : 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 : 0 : friend bool operator!=(const ilist_iterator_w_bits &LHS,
333 : : const ilist_iterator_w_bits &RHS) {
334 : 0 : 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 : 0 : ilist_iterator_w_bits &operator++() {
345 : 0 : NodePtr = IsReverse ? NodePtr->getPrev() : NodePtr->getNext();
346 : 0 : HeadInclusiveBit = false;
347 : 0 : TailInclusiveBit = false;
348 : 0 : 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 : 0 : 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
|
