Line data Source code
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 25431188 : explicit ilist_iterator(pointer NP) : NodePtr(Access::getNodePtr(NP)) {}
86 35568599 : explicit ilist_iterator(reference NR) : NodePtr(Access::getNodePtr(&NR)) {}
87 28992854 : 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 5218650 : ilist_iterator(
93 : const ilist_iterator<OptionsT, IsReverse, RHSIsConst> &RHS,
94 : typename std::enable_if<IsConst || !RHSIsConst, void *>::type = nullptr)
95 5072766 : : NodePtr(RHS.NodePtr) {}
96 0 :
97 : // This is templated so that we can allow assigning to a const iterator from
98 : // a nonconst iterator...
99 0 : template <bool RHSIsConst>
100 0 : typename std::enable_if<IsConst || !RHSIsConst, ilist_iterator &>::type
101 : operator=(const ilist_iterator<OptionsT, IsReverse, RHSIsConst> &RHS) {
102 : NodePtr = RHS.NodePtr;
103 0 : return *this;
104 0 : }
105 :
106 : /// Explicit conversion between forward/reverse iterators.
107 0 : ///
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 5 : /// different range; for range operations, use the explicit conversions.
123 0 : ilist_iterator<OptionsT, !IsReverse, IsConst> getReverse() const {
124 41937782 : if (NodePtr)
125 0 : return ilist_iterator<OptionsT, !IsReverse, IsConst>(*NodePtr);
126 0 : return ilist_iterator<OptionsT, !IsReverse, IsConst>();
127 : }
128 0 :
129 0 : /// Const-cast.
130 0 : ilist_iterator<OptionsT, IsReverse, false> getNonConst() const {
131 4238747 : if (NodePtr)
132 12 : return ilist_iterator<OptionsT, IsReverse, false>(
133 0 : const_cast<typename ilist_iterator<OptionsT, IsReverse,
134 0 : false>::node_reference>(*NodePtr));
135 0 : return ilist_iterator<OptionsT, IsReverse, false>();
136 7 : }
137 0 :
138 0 : // Accessors...
139 0 : reference operator*() const {
140 0 : assert(!NodePtr->isKnownSentinel());
141 0 : return *Access::getValuePtr(NodePtr);
142 0 : }
143 28 : pointer operator->() const { return &operator*(); }
144 0 :
145 0 : // Comparison operators
146 0 : friend bool operator==(const ilist_iterator &LHS, const ilist_iterator &RHS) {
147 48 : return LHS.NodePtr == RHS.NodePtr;
148 0 : }
149 0 : friend bool operator!=(const ilist_iterator &LHS, const ilist_iterator &RHS) {
150 0 : return LHS.NodePtr != RHS.NodePtr;
151 111472060 : }
152 0 :
153 0 : // Increment and decrement operators...
154 0 : ilist_iterator &operator--() {
155 43117309 : NodePtr = IsReverse ? NodePtr->getNext() : NodePtr->getPrev();
156 0 : return *this;
157 0 : }
158 0 : ilist_iterator &operator++() {
159 75482464 : NodePtr = IsReverse ? NodePtr->getPrev() : NodePtr->getNext();
160 0 : return *this;
161 0 : }
162 0 : ilist_iterator operator--(int) {
163 12405571 : ilist_iterator tmp = *this;
164 0 : --*this;
165 10235266 : return tmp;
166 0 : }
167 18064346 : ilist_iterator operator++(int) {
168 23137 : ilist_iterator tmp = *this;
169 665140 : ++*this;
170 0 : return tmp;
171 155412 : }
172 0 :
173 169382747 : /// Get the underlying ilist_node.
174 8322023 : node_pointer getNodePtr() const { return static_cast<node_pointer>(NodePtr); }
175 3449964 :
176 4618172 : /// Check for end. Only valid if ilist_sentinel_tracking<true>.
177 7481947 : bool isEnd() const { return NodePtr ? NodePtr->isSentinel() : false; }
178 33424 : };
179 92052709 :
180 688997 : template <typename From> struct simplify_type;
181 1 :
182 11487749 : /// Allow ilist_iterators to convert into pointers to a node automatically when
183 163548 : /// used by the dyn_cast, cast, isa mechanisms...
184 3514 : ///
185 96260305 : /// FIXME: remove this, since there is no implicit conversion to NodeTy.
186 2698716 : template <class OptionsT, bool IsConst>
187 152467 : struct simplify_type<ilist_iterator<OptionsT, false, IsConst>> {
188 62 : using iterator = ilist_iterator<OptionsT, false, IsConst>;
189 19607868 : using SimpleType = typename iterator::pointer;
190 106278095 :
191 147840564 : static SimpleType getSimplifiedValue(const iterator &Node) { return &*Node; }
192 467 : };
193 77695517 : template <class OptionsT, bool IsConst>
194 2649192 : struct simplify_type<const ilist_iterator<OptionsT, false, IsConst>>
195 10600862 : : simplify_type<ilist_iterator<OptionsT, false, IsConst>> {};
196 33841048 :
197 7282032 : } // end namespace llvm
198 55068 :
199 28664641 : #endif // LLVM_ADT_ILIST_ITERATOR_H
|
