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