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++ -*-===//
//
// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
// See https://llvm.org/LICENSE.txt for license information.
// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
//
//===----------------------------------------------------------------------===//
#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> {
using value_type = typename OptionsT::value_type;
using pointer = typename OptionsT::pointer;
using reference = typename OptionsT::reference;
using node_pointer = ilist_node_impl<OptionsT> *;
using node_reference = ilist_node_impl<OptionsT> &;
};
template <class OptionsT> struct IteratorTraits<OptionsT, true> {
using value_type = const typename OptionsT::value_type;
using pointer = typename OptionsT::const_pointer;
using reference = typename OptionsT::const_reference;
using node_pointer = const ilist_node_impl<OptionsT> *;
using node_reference = const ilist_node_impl<OptionsT> &;
};
template <bool IsReverse> struct IteratorHelper;
template <> struct IteratorHelper<false> : ilist_detail::NodeAccess {
using Access = ilist_detail::NodeAccess;
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 {
using Access = ilist_detail::NodeAccess;
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>;
using Traits = ilist_detail::IteratorTraits<OptionsT, IsConst>;
using Access = ilist_detail::SpecificNodeAccess<OptionsT>;
public:
using value_type = typename Traits::value_type;
using pointer = typename Traits::pointer;
using reference = typename Traits::reference;
using difference_type = ptrdiff_t;
using iterator_category = std::bidirectional_iterator_tag;
using const_pointer = typename OptionsT::const_pointer;
using const_reference = typename OptionsT::const_reference;
private:
using node_pointer = typename Traits::node_pointer;
using node_reference = typename Traits::node_reference;
node_pointer NodePtr = nullptr;
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() = default;
// 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>> {
using iterator = ilist_iterator<OptionsT, false, IsConst>;
using SimpleType = typename iterator::pointer;
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
|