1 | //===- llvm/ADT/ilist_iterator.h - Intrusive List Iterator ------*- C++ -*-===// |
2 | // |
3 | // The LLVM Compiler Infrastructure |
4 | // |
5 | // This file is distributed under the University of Illinois Open Source |
6 | // License. See LICENSE.TXT for details. |
7 | // |
8 | //===----------------------------------------------------------------------===// |
9 | |
10 | #ifndef LLVM_ADT_ILIST_ITERATOR_H |
11 | #define LLVM_ADT_ILIST_ITERATOR_H |
12 | |
13 | #include "llvm/ADT/ilist_node.h" |
14 | #include <cassert> |
15 | #include <cstddef> |
16 | #include <iterator> |
17 | #include <type_traits> |
18 | |
19 | namespace llvm { |
20 | |
21 | namespace ilist_detail { |
22 | |
23 | /// Find const-correct node types. |
24 | template <class OptionsT, bool IsConst> struct IteratorTraits; |
25 | template <class OptionsT> struct IteratorTraits<OptionsT, false> { |
26 | using value_type = typename OptionsT::value_type; |
27 | using pointer = typename OptionsT::pointer; |
28 | using reference = typename OptionsT::reference; |
29 | using node_pointer = ilist_node_impl<OptionsT> *; |
30 | using node_reference = ilist_node_impl<OptionsT> &; |
31 | }; |
32 | template <class OptionsT> struct IteratorTraits<OptionsT, true> { |
33 | using value_type = const typename OptionsT::value_type; |
34 | using pointer = typename OptionsT::const_pointer; |
35 | using reference = typename OptionsT::const_reference; |
36 | using node_pointer = const ilist_node_impl<OptionsT> *; |
37 | using node_reference = const ilist_node_impl<OptionsT> &; |
38 | }; |
39 | |
40 | template <bool IsReverse> struct IteratorHelper; |
41 | template <> struct IteratorHelper<false> : ilist_detail::NodeAccess { |
42 | using Access = ilist_detail::NodeAccess; |
43 | |
44 | template <class T> static void increment(T *&I) { I = Access::getNext(*I); } |
45 | template <class T> static void decrement(T *&I) { I = Access::getPrev(*I); } |
46 | }; |
47 | template <> struct IteratorHelper<true> : ilist_detail::NodeAccess { |
48 | using Access = ilist_detail::NodeAccess; |
49 | |
50 | template <class T> static void increment(T *&I) { I = Access::getPrev(*I); } |
51 | template <class T> static void decrement(T *&I) { I = Access::getNext(*I); } |
52 | }; |
53 | |
54 | } // end namespace ilist_detail |
55 | |
56 | /// Iterator for intrusive lists based on ilist_node. |
57 | template <class OptionsT, bool IsReverse, bool IsConst> |
58 | class ilist_iterator : ilist_detail::SpecificNodeAccess<OptionsT> { |
59 | friend ilist_iterator<OptionsT, IsReverse, !IsConst>; |
60 | friend ilist_iterator<OptionsT, !IsReverse, IsConst>; |
61 | friend ilist_iterator<OptionsT, !IsReverse, !IsConst>; |
62 | |
63 | using Traits = ilist_detail::IteratorTraits<OptionsT, IsConst>; |
64 | using Access = ilist_detail::SpecificNodeAccess<OptionsT>; |
65 | |
66 | public: |
67 | using value_type = typename Traits::value_type; |
68 | using pointer = typename Traits::pointer; |
69 | using reference = typename Traits::reference; |
70 | using difference_type = ptrdiff_t; |
71 | using iterator_category = std::bidirectional_iterator_tag; |
72 | using const_pointer = typename OptionsT::const_pointer; |
73 | using const_reference = typename OptionsT::const_reference; |
74 | |
75 | private: |
76 | using node_pointer = typename Traits::node_pointer; |
77 | using node_reference = typename Traits::node_reference; |
78 | |
79 | node_pointer NodePtr = nullptr; |
80 | |
81 | public: |
82 | /// Create from an ilist_node. |
83 | explicit ilist_iterator(node_reference N) : NodePtr(&N) {} |
84 | |
85 | explicit ilist_iterator(pointer NP) : NodePtr(Access::getNodePtr(NP)) {} |
86 | explicit ilist_iterator(reference NR) : NodePtr(Access::getNodePtr(&NR)) {} |
87 | ilist_iterator() = default; |
88 | |
89 | // This is templated so that we can allow constructing a const iterator from |
90 | // a nonconst iterator... |
91 | template <bool RHSIsConst> |
92 | ilist_iterator( |
93 | const ilist_iterator<OptionsT, IsReverse, RHSIsConst> &RHS, |
94 | typename std::enable_if<IsConst || !RHSIsConst, void *>::type = nullptr) |
95 | : NodePtr(RHS.NodePtr) {} |
96 | |
97 | // This is templated so that we can allow assigning to a const iterator from |
98 | // a nonconst iterator... |
99 | template <bool RHSIsConst> |
100 | typename std::enable_if<IsConst || !RHSIsConst, ilist_iterator &>::type |
101 | operator=(const ilist_iterator<OptionsT, IsReverse, RHSIsConst> &RHS) { |
102 | NodePtr = RHS.NodePtr; |
103 | return *this; |
104 | } |
105 | |
106 | /// Explicit conversion between forward/reverse iterators. |
107 | /// |
108 | /// Translate between forward and reverse iterators without changing range |
109 | /// boundaries. The resulting iterator will dereference (and have a handle) |
110 | /// to the previous node, which is somewhat unexpected; but converting the |
111 | /// two endpoints in a range will give the same range in reverse. |
112 | /// |
113 | /// This matches std::reverse_iterator conversions. |
114 | explicit ilist_iterator( |
115 | const ilist_iterator<OptionsT, !IsReverse, IsConst> &RHS) |
116 | : ilist_iterator(++RHS.getReverse()) {} |
117 | |
118 | /// Get a reverse iterator to the same node. |
119 | /// |
120 | /// Gives a reverse iterator that will dereference (and have a handle) to the |
121 | /// same node. Converting the endpoint iterators in a range will give a |
122 | /// different range; for range operations, use the explicit conversions. |
123 | ilist_iterator<OptionsT, !IsReverse, IsConst> getReverse() const { |
124 | if (NodePtr) |
125 | return ilist_iterator<OptionsT, !IsReverse, IsConst>(*NodePtr); |
126 | return ilist_iterator<OptionsT, !IsReverse, IsConst>(); |
127 | } |
128 | |
129 | /// Const-cast. |
130 | ilist_iterator<OptionsT, IsReverse, false> getNonConst() const { |
131 | if (NodePtr) |
132 | return ilist_iterator<OptionsT, IsReverse, false>( |
133 | const_cast<typename ilist_iterator<OptionsT, IsReverse, |
134 | false>::node_reference>(*NodePtr)); |
135 | return ilist_iterator<OptionsT, IsReverse, false>(); |
136 | } |
137 | |
138 | // Accessors... |
139 | reference operator*() const { |
140 | assert(!NodePtr->isKnownSentinel()); |
141 | return *Access::getValuePtr(NodePtr); |
142 | } |
143 | pointer operator->() const { return &operator*(); } |
144 | |
145 | // Comparison operators |
146 | friend bool operator==(const ilist_iterator &LHS, const ilist_iterator &RHS) { |
147 | return LHS.NodePtr == RHS.NodePtr; |
148 | } |
149 | friend bool operator!=(const ilist_iterator &LHS, const ilist_iterator &RHS) { |
150 | return LHS.NodePtr != RHS.NodePtr; |
151 | } |
152 | |
153 | // Increment and decrement operators... |
154 | ilist_iterator &operator--() { |
155 | NodePtr = IsReverse ? NodePtr->getNext() : NodePtr->getPrev(); |
156 | return *this; |
157 | } |
158 | ilist_iterator &operator++() { |
159 | NodePtr = IsReverse ? NodePtr->getPrev() : NodePtr->getNext(); |
160 | return *this; |
161 | } |
162 | ilist_iterator operator--(int) { |
163 | ilist_iterator tmp = *this; |
164 | --*this; |
165 | return tmp; |
166 | } |
167 | ilist_iterator operator++(int) { |
168 | ilist_iterator tmp = *this; |
169 | ++*this; |
170 | return tmp; |
171 | } |
172 | |
173 | /// Get the underlying ilist_node. |
174 | node_pointer getNodePtr() const { return static_cast<node_pointer>(NodePtr); } |
175 | |
176 | /// Check for end. Only valid if ilist_sentinel_tracking<true>. |
177 | bool isEnd() const { return NodePtr ? NodePtr->isSentinel() : false; } |
178 | }; |
179 | |
180 | template <typename From> struct simplify_type; |
181 | |
182 | /// Allow ilist_iterators to convert into pointers to a node automatically when |
183 | /// used by the dyn_cast, cast, isa mechanisms... |
184 | /// |
185 | /// FIXME: remove this, since there is no implicit conversion to NodeTy. |
186 | template <class OptionsT, bool IsConst> |
187 | struct simplify_type<ilist_iterator<OptionsT, false, IsConst>> { |
188 | using iterator = ilist_iterator<OptionsT, false, IsConst>; |
189 | using SimpleType = typename iterator::pointer; |
190 | |
191 | static SimpleType getSimplifiedValue(const iterator &Node) { return &*Node; } |
192 | }; |
193 | template <class OptionsT, bool IsConst> |
194 | struct simplify_type<const ilist_iterator<OptionsT, false, IsConst>> |
195 | : simplify_type<ilist_iterator<OptionsT, false, IsConst>> {}; |
196 | |
197 | } // end namespace llvm |
198 | |
199 | #endif // LLVM_ADT_ILIST_ITERATOR_H |
200 | |