1//===- llvm/ADT/ilist_node.h - Intrusive Linked List Helper -----*- 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// This file defines the ilist_node class template, which is a convenient
11// base class for creating classes that can be used with ilists.
12//
13//===----------------------------------------------------------------------===//
14
15#ifndef LLVM_ADT_ILIST_NODE_H
16#define LLVM_ADT_ILIST_NODE_H
17
18#include "llvm/ADT/ilist_node_base.h"
19#include "llvm/ADT/ilist_node_options.h"
20
21namespace llvm {
22
23namespace ilist_detail {
24
25struct NodeAccess;
26
27} // end namespace ilist_detail
28
29template <class OptionsT, bool IsReverse, bool IsConst> class ilist_iterator;
30template <class OptionsT> class ilist_sentinel;
31
32/// Implementation for an ilist node.
33///
34/// Templated on an appropriate \a ilist_detail::node_options, usually computed
35/// by \a ilist_detail::compute_node_options.
36///
37/// This is a wrapper around \a ilist_node_base whose main purpose is to
38/// provide type safety: you can't insert nodes of \a ilist_node_impl into the
39/// wrong \a simple_ilist or \a iplist.
40template <class OptionsT> class ilist_node_impl : OptionsT::node_base_type {
41 using value_type = typename OptionsT::value_type;
42 using node_base_type = typename OptionsT::node_base_type;
43 using list_base_type = typename OptionsT::list_base_type;
44
45 friend typename OptionsT::list_base_type;
46 friend struct ilist_detail::NodeAccess;
47 friend class ilist_sentinel<OptionsT>;
48 friend class ilist_iterator<OptionsT, false, false>;
49 friend class ilist_iterator<OptionsT, false, true>;
50 friend class ilist_iterator<OptionsT, true, false>;
51 friend class ilist_iterator<OptionsT, true, true>;
52
53protected:
54 using self_iterator = ilist_iterator<OptionsT, false, false>;
55 using const_self_iterator = ilist_iterator<OptionsT, false, true>;
56 using reverse_self_iterator = ilist_iterator<OptionsT, true, false>;
57 using const_reverse_self_iterator = ilist_iterator<OptionsT, true, true>;
58
59 ilist_node_impl() = default;
60
61private:
62 ilist_node_impl *getPrev() {
63 return static_cast<ilist_node_impl *>(node_base_type::getPrev());
64 }
65
66 ilist_node_impl *getNext() {
67 return static_cast<ilist_node_impl *>(node_base_type::getNext());
68 }
69
70 const ilist_node_impl *getPrev() const {
71 return static_cast<ilist_node_impl *>(node_base_type::getPrev());
72 }
73
74 const ilist_node_impl *getNext() const {
75 return static_cast<ilist_node_impl *>(node_base_type::getNext());
76 }
77
78 void setPrev(ilist_node_impl *N) { node_base_type::setPrev(N); }
79 void setNext(ilist_node_impl *N) { node_base_type::setNext(N); }
80
81public:
82 self_iterator getIterator() { return self_iterator(*this); }
83 const_self_iterator getIterator() const { return const_self_iterator(*this); }
84
85 reverse_self_iterator getReverseIterator() {
86 return reverse_self_iterator(*this);
87 }
88
89 const_reverse_self_iterator getReverseIterator() const {
90 return const_reverse_self_iterator(*this);
91 }
92
93 // Under-approximation, but always available for assertions.
94 using node_base_type::isKnownSentinel;
95
96 /// Check whether this is the sentinel node.
97 ///
98 /// This requires sentinel tracking to be explicitly enabled. Use the
99 /// ilist_sentinel_tracking<true> option to get this API.
100 bool isSentinel() const {
101 static_assert(OptionsT::is_sentinel_tracking_explicit,
102 "Use ilist_sentinel_tracking<true> to enable isSentinel()");
103 return node_base_type::isSentinel();
104 }
105};
106
107/// An intrusive list node.
108///
109/// A base class to enable membership in intrusive lists, including \a
110/// simple_ilist, \a iplist, and \a ilist. The first template parameter is the
111/// \a value_type for the list.
112///
113/// An ilist node can be configured with compile-time options to change
114/// behaviour and/or add API.
115///
116/// By default, an \a ilist_node knows whether it is the list sentinel (an
117/// instance of \a ilist_sentinel) if and only if
118/// LLVM_ENABLE_ABI_BREAKING_CHECKS. The function \a isKnownSentinel() always
119/// returns \c false tracking is off. Sentinel tracking steals a bit from the
120/// "prev" link, which adds a mask operation when decrementing an iterator, but
121/// enables bug-finding assertions in \a ilist_iterator.
122///
123/// To turn sentinel tracking on all the time, pass in the
124/// ilist_sentinel_tracking<true> template parameter. This also enables the \a
125/// isSentinel() function. The same option must be passed to the intrusive
126/// list. (ilist_sentinel_tracking<false> turns sentinel tracking off all the
127/// time.)
128///
129/// A type can inherit from ilist_node multiple times by passing in different
130/// \a ilist_tag options. This allows a single instance to be inserted into
131/// multiple lists simultaneously, where each list is given the same tag.
132///
133/// \example
134/// struct A {};
135/// struct B {};
136/// struct N : ilist_node<N, ilist_tag<A>>, ilist_node<N, ilist_tag<B>> {};
137///
138/// void foo() {
139/// simple_ilist<N, ilist_tag<A>> ListA;
140/// simple_ilist<N, ilist_tag<B>> ListB;
141/// N N1;
142/// ListA.push_back(N1);
143/// ListB.push_back(N1);
144/// }
145/// \endexample
146///
147/// See \a is_valid_option for steps on adding a new option.
148template <class T, class... Options>
149class ilist_node
150 : public ilist_node_impl<
151 typename ilist_detail::compute_node_options<T, Options...>::type> {
152 static_assert(ilist_detail::check_options<Options...>::value,
153 "Unrecognized node option!");
154};
155
156namespace ilist_detail {
157
158/// An access class for ilist_node private API.
159///
160/// This gives access to the private parts of ilist nodes. Nodes for an ilist
161/// should friend this class if they inherit privately from ilist_node.
162///
163/// Using this class outside of the ilist implementation is unsupported.
164struct NodeAccess {
165protected:
166 template <class OptionsT>
167 static ilist_node_impl<OptionsT> *getNodePtr(typename OptionsT::pointer N) {
168 return N;
169 }
170
171 template <class OptionsT>
172 static const ilist_node_impl<OptionsT> *
173 getNodePtr(typename OptionsT::const_pointer N) {
174 return N;
175 }
176
177 template <class OptionsT>
178 static typename OptionsT::pointer getValuePtr(ilist_node_impl<OptionsT> *N) {
179 return static_cast<typename OptionsT::pointer>(N);
180 }
181
182 template <class OptionsT>
183 static typename OptionsT::const_pointer
184 getValuePtr(const ilist_node_impl<OptionsT> *N) {
185 return static_cast<typename OptionsT::const_pointer>(N);
186 }
187
188 template <class OptionsT>
189 static ilist_node_impl<OptionsT> *getPrev(ilist_node_impl<OptionsT> &N) {
190 return N.getPrev();
191 }
192
193 template <class OptionsT>
194 static ilist_node_impl<OptionsT> *getNext(ilist_node_impl<OptionsT> &N) {
195 return N.getNext();
196 }
197
198 template <class OptionsT>
199 static const ilist_node_impl<OptionsT> *
200 getPrev(const ilist_node_impl<OptionsT> &N) {
201 return N.getPrev();
202 }
203
204 template <class OptionsT>
205 static const ilist_node_impl<OptionsT> *
206 getNext(const ilist_node_impl<OptionsT> &N) {
207 return N.getNext();
208 }
209};
210
211template <class OptionsT> struct SpecificNodeAccess : NodeAccess {
212protected:
213 using pointer = typename OptionsT::pointer;
214 using const_pointer = typename OptionsT::const_pointer;
215 using node_type = ilist_node_impl<OptionsT>;
216
217 static node_type *getNodePtr(pointer N) {
218 return NodeAccess::getNodePtr<OptionsT>(N);
219 }
220
221 static const node_type *getNodePtr(const_pointer N) {
222 return NodeAccess::getNodePtr<OptionsT>(N);
223 }
224
225 static pointer getValuePtr(node_type *N) {
226 return NodeAccess::getValuePtr<OptionsT>(N);
227 }
228
229 static const_pointer getValuePtr(const node_type *N) {
230 return NodeAccess::getValuePtr<OptionsT>(N);
231 }
232};
233
234} // end namespace ilist_detail
235
236template <class OptionsT>
237class ilist_sentinel : public ilist_node_impl<OptionsT> {
238public:
239 ilist_sentinel() {
240 this->initializeSentinel();
241 reset();
242 }
243
244 void reset() {
245 this->setPrev(this);
246 this->setNext(this);
247 }
248
249 bool empty() const { return this == this->getPrev(); }
250};
251
252/// An ilist node that can access its parent list.
253///
254/// Requires \c NodeTy to have \a getParent() to find the parent node, and the
255/// \c ParentTy to have \a getSublistAccess() to get a reference to the list.
256template <typename NodeTy, typename ParentTy, class... Options>
257class ilist_node_with_parent : public ilist_node<NodeTy, Options...> {
258protected:
259 ilist_node_with_parent() = default;
260
261private:
262 /// Forward to NodeTy::getParent().
263 ///
264 /// Note: do not use the name "getParent()". We want a compile error
265 /// (instead of recursion) when the subclass fails to implement \a
266 /// getParent().
267 const ParentTy *getNodeParent() const {
268 return static_cast<const NodeTy *>(this)->getParent();
269 }
270
271public:
272 /// @name Adjacent Node Accessors
273 /// @{
274 /// Get the previous node, or \c nullptr for the list head.
275 NodeTy *getPrevNode() {
276 // Should be separated to a reused function, but then we couldn't use auto
277 // (and would need the type of the list).
278 const auto &List =
279 getNodeParent()->*(ParentTy::getSublistAccess((NodeTy *)nullptr));
280 return List.getPrevNode(*static_cast<NodeTy *>(this));
281 }
282
283 /// Get the previous node, or \c nullptr for the list head.
284 const NodeTy *getPrevNode() const {
285 return const_cast<ilist_node_with_parent *>(this)->getPrevNode();
286 }
287
288 /// Get the next node, or \c nullptr for the list tail.
289 NodeTy *getNextNode() {
290 // Should be separated to a reused function, but then we couldn't use auto
291 // (and would need the type of the list).
292 const auto &List =
293 getNodeParent()->*(ParentTy::getSublistAccess((NodeTy *)nullptr));
294 return List.getNextNode(*static_cast<NodeTy *>(this));
295 }
296
297 /// Get the next node, or \c nullptr for the list tail.
298 const NodeTy *getNextNode() const {
299 return const_cast<ilist_node_with_parent *>(this)->getNextNode();
300 }
301 /// @}
302};
303
304} // end namespace llvm
305
306#endif // LLVM_ADT_ILIST_NODE_H
307