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