LLVM 20.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/// Mixin base class that is used to add \a getParent() and
28/// \a setParent(ParentTy*) methods to \a ilist_node_impl iff \a ilist_parent
29/// has been set in the list options.
30template <class NodeTy, class ParentTy> class node_parent_access {
31public:
32 inline const ParentTy *getParent() const {
33 return static_cast<const NodeTy *>(this)->getNodeBaseParent();
34 }
35 inline ParentTy *getParent() {
36 return static_cast<NodeTy *>(this)->getNodeBaseParent();
37 }
38 void setParent(ParentTy *Parent) {
39 return static_cast<NodeTy *>(this)->setNodeBaseParent(Parent);
40 }
41};
42template <class NodeTy> class node_parent_access<NodeTy, void> {};
43
44} // end namespace ilist_detail
45
46template <class OptionsT, bool IsReverse, bool IsConst> class ilist_iterator;
47template <class OptionsT, bool IsReverse, bool IsConst>
49template <class OptionsT> class ilist_sentinel;
50
51// Selector for which iterator type to pick given the iterator-bits node option.
52template <bool use_iterator_bits, typename Opts, bool arg1, bool arg2>
54public:
56};
57template <typename Opts, bool arg1, bool arg2>
58class ilist_select_iterator_type<true, Opts, arg1, arg2> {
59public:
61};
62
63/// Implementation for an ilist node.
64///
65/// Templated on an appropriate \a ilist_detail::node_options, usually computed
66/// by \a ilist_detail::compute_node_options.
67///
68/// This is a wrapper around \a ilist_node_base whose main purpose is to
69/// provide type safety: you can't insert nodes of \a ilist_node_impl into the
70/// wrong \a simple_ilist or \a iplist.
71template <class OptionsT>
73 : OptionsT::node_base_type,
74 public ilist_detail::node_parent_access<ilist_node_impl<OptionsT>,
75 typename OptionsT::parent_ty> {
76 using value_type = typename OptionsT::value_type;
77 using node_base_type = typename OptionsT::node_base_type;
78 using list_base_type = typename OptionsT::list_base_type;
79
80 friend typename OptionsT::list_base_type;
82 friend class ilist_sentinel<OptionsT>;
83
85 typename OptionsT::parent_ty>;
86 friend class ilist_iterator<OptionsT, false, false>;
87 friend class ilist_iterator<OptionsT, false, true>;
88 friend class ilist_iterator<OptionsT, true, false>;
89 friend class ilist_iterator<OptionsT, true, true>;
90 friend class ilist_iterator_w_bits<OptionsT, false, false>;
91 friend class ilist_iterator_w_bits<OptionsT, false, true>;
92 friend class ilist_iterator_w_bits<OptionsT, true, false>;
93 friend class ilist_iterator_w_bits<OptionsT, true, true>;
94
95protected:
97 typename ilist_select_iterator_type<OptionsT::has_iterator_bits, OptionsT,
98 false, false>::type;
100 typename ilist_select_iterator_type<OptionsT::has_iterator_bits, OptionsT,
101 false, true>::type;
103 typename ilist_select_iterator_type<OptionsT::has_iterator_bits, OptionsT,
104 true, false>::type;
106 typename ilist_select_iterator_type<OptionsT::has_iterator_bits, OptionsT,
107 true, true>::type;
108
109 ilist_node_impl() = default;
110
111private:
112 ilist_node_impl *getPrev() {
113 return static_cast<ilist_node_impl *>(node_base_type::getPrev());
114 }
115
116 ilist_node_impl *getNext() {
117 return static_cast<ilist_node_impl *>(node_base_type::getNext());
118 }
119
120 const ilist_node_impl *getPrev() const {
121 return static_cast<ilist_node_impl *>(node_base_type::getPrev());
122 }
123
124 const ilist_node_impl *getNext() const {
125 return static_cast<ilist_node_impl *>(node_base_type::getNext());
126 }
127
128 void setPrev(ilist_node_impl *N) { node_base_type::setPrev(N); }
129 void setNext(ilist_node_impl *N) { node_base_type::setNext(N); }
130
131public:
134
136 return reverse_self_iterator(*this);
137 }
138
140 return const_reverse_self_iterator(*this);
141 }
142
143 // Under-approximation, but always available for assertions.
144 using node_base_type::isKnownSentinel;
145
146 /// Check whether this is the sentinel node.
147 ///
148 /// This requires sentinel tracking to be explicitly enabled. Use the
149 /// ilist_sentinel_tracking<true> option to get this API.
150 bool isSentinel() const {
151 static_assert(OptionsT::is_sentinel_tracking_explicit,
152 "Use ilist_sentinel_tracking<true> to enable isSentinel()");
153 return node_base_type::isSentinel();
154 }
155};
156
157/// An intrusive list node.
158///
159/// A base class to enable membership in intrusive lists, including \a
160/// simple_ilist, \a iplist, and \a ilist. The first template parameter is the
161/// \a value_type for the list.
162///
163/// An ilist node can be configured with compile-time options to change
164/// behaviour and/or add API.
165///
166/// By default, an \a ilist_node knows whether it is the list sentinel (an
167/// instance of \a ilist_sentinel) if and only if
168/// LLVM_ENABLE_ABI_BREAKING_CHECKS. The function \a isKnownSentinel() always
169/// returns \c false tracking is off. Sentinel tracking steals a bit from the
170/// "prev" link, which adds a mask operation when decrementing an iterator, but
171/// enables bug-finding assertions in \a ilist_iterator.
172///
173/// To turn sentinel tracking on all the time, pass in the
174/// ilist_sentinel_tracking<true> template parameter. This also enables the \a
175/// isSentinel() function. The same option must be passed to the intrusive
176/// list. (ilist_sentinel_tracking<false> turns sentinel tracking off all the
177/// time.)
178///
179/// A type can inherit from ilist_node multiple times by passing in different
180/// \a ilist_tag options. This allows a single instance to be inserted into
181/// multiple lists simultaneously, where each list is given the same tag.
182///
183/// \example
184/// struct A {};
185/// struct B {};
186/// struct N : ilist_node<N, ilist_tag<A>>, ilist_node<N, ilist_tag<B>> {};
187///
188/// void foo() {
189/// simple_ilist<N, ilist_tag<A>> ListA;
190/// simple_ilist<N, ilist_tag<B>> ListB;
191/// N N1;
192/// ListA.push_back(N1);
193/// ListB.push_back(N1);
194/// }
195/// \endexample
196///
197/// When the \a ilist_parent<ParentTy> option is passed to an ilist_node and the
198/// owning ilist, each node contains a pointer to the ilist's owner. This adds
199/// \a getParent() and \a setParent(ParentTy*) methods to the ilist_node, which
200/// will be used for node access by the ilist if the node class publicly
201/// inherits from \a ilist_node_with_parent. By default, setParent() is not
202/// automatically called by the ilist; a SymbolTableList will call setParent()
203/// on inserted nodes, but the sentinel must still be manually set after the
204/// list is created (e.g. SymTabList.end()->setParent(Parent)).
205///
206/// The primary benefit of using ilist_parent is that a parent
207/// pointer will be stored in the sentinel, meaning that you can safely use \a
208/// ilist_iterator::getNodeParent() to get the node parent from any valid (i.e.
209/// non-null) iterator, even one that points to a sentinel value.
210///
211/// See \a is_valid_option for steps on adding a new option.
212template <class T, class... Options>
214 : public ilist_node_impl<
215 typename ilist_detail::compute_node_options<T, Options...>::type> {
217 "Unrecognized node option!");
218};
219
220namespace ilist_detail {
221
222/// An access class for ilist_node private API.
223///
224/// This gives access to the private parts of ilist nodes. Nodes for an ilist
225/// should friend this class if they inherit privately from ilist_node.
226///
227/// Using this class outside of the ilist implementation is unsupported.
229protected:
230 template <class OptionsT>
231 static ilist_node_impl<OptionsT> *getNodePtr(typename OptionsT::pointer N) {
232 return N;
233 }
234
235 template <class OptionsT>
236 static const ilist_node_impl<OptionsT> *
237 getNodePtr(typename OptionsT::const_pointer N) {
238 return N;
239 }
240
241 template <class OptionsT>
242 static typename OptionsT::pointer getValuePtr(ilist_node_impl<OptionsT> *N) {
243 return static_cast<typename OptionsT::pointer>(N);
244 }
245
246 template <class OptionsT>
247 static typename OptionsT::const_pointer
249 return static_cast<typename OptionsT::const_pointer>(N);
250 }
251
252 template <class OptionsT>
254 return N.getPrev();
255 }
256
257 template <class OptionsT>
259 return N.getNext();
260 }
261
262 template <class OptionsT>
263 static const ilist_node_impl<OptionsT> *
265 return N.getPrev();
266 }
267
268 template <class OptionsT>
269 static const ilist_node_impl<OptionsT> *
271 return N.getNext();
272 }
273};
274
275template <class OptionsT> struct SpecificNodeAccess : NodeAccess {
276protected:
277 using pointer = typename OptionsT::pointer;
278 using const_pointer = typename OptionsT::const_pointer;
280
282 return NodeAccess::getNodePtr<OptionsT>(N);
283 }
284
286 return NodeAccess::getNodePtr<OptionsT>(N);
287 }
288
290 return NodeAccess::getValuePtr<OptionsT>(N);
291 }
292
294 return NodeAccess::getValuePtr<OptionsT>(N);
295 }
296};
297
298} // end namespace ilist_detail
299
300template <class OptionsT>
301class ilist_sentinel : public ilist_node_impl<OptionsT> {
302public:
304 this->initializeSentinel();
305 reset();
306 }
307
308 void reset() {
309 this->setPrev(this);
310 this->setNext(this);
311 }
312
313 bool empty() const { return this == this->getPrev(); }
314};
315
316/// An ilist node that can access its parent list.
317///
318/// Requires \c NodeTy to have \a getParent() to find the parent node, and the
319/// \c ParentTy to have \a getSublistAccess() to get a reference to the list.
320template <typename NodeTy, typename ParentTy, class... Options>
321class ilist_node_with_parent : public ilist_node<NodeTy, Options...> {
322protected:
324
325private:
326 /// Forward to NodeTy::getParent().
327 ///
328 /// Note: do not use the name "getParent()". We want a compile error
329 /// (instead of recursion) when the subclass fails to implement \a
330 /// getParent().
331 const ParentTy *getNodeParent() const {
332 return static_cast<const NodeTy *>(this)->getParent();
333 }
334
335public:
336 /// @name Adjacent Node Accessors
337 /// @{
338 /// Get the previous node, or \c nullptr for the list head.
339 NodeTy *getPrevNode() {
340 // Should be separated to a reused function, but then we couldn't use auto
341 // (and would need the type of the list).
342 const auto &List =
343 getNodeParent()->*(ParentTy::getSublistAccess((NodeTy *)nullptr));
344 return List.getPrevNode(*static_cast<NodeTy *>(this));
345 }
346
347 /// Get the previous node, or \c nullptr for the list head.
348 const NodeTy *getPrevNode() const {
349 return const_cast<ilist_node_with_parent *>(this)->getPrevNode();
350 }
351
352 /// Get the next node, or \c nullptr for the list tail.
353 NodeTy *getNextNode() {
354 // Should be separated to a reused function, but then we couldn't use auto
355 // (and would need the type of the list).
356 const auto &List =
357 getNodeParent()->*(ParentTy::getSublistAccess((NodeTy *)nullptr));
358 return List.getNextNode(*static_cast<NodeTy *>(this));
359 }
360
361 /// Get the next node, or \c nullptr for the list tail.
362 const NodeTy *getNextNode() const {
363 return const_cast<ilist_node_with_parent *>(this)->getNextNode();
364 }
365 /// @}
366};
367
368} // end namespace llvm
369
370#endif // LLVM_ADT_ILIST_NODE_H
basic Basic Alias true
Given that RA is a live value
static LVOptions Options
Definition: LVOptions.cpp:25
#define T
Mixin base class that is used to add getParent() and setParent(ParentTy*) methods to ilist_node_impl ...
Definition: ilist_node.h:30
const ParentTy * getParent() const
Definition: ilist_node.h:32
void setParent(ParentTy *Parent)
Definition: ilist_node.h:38
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:75
bool isSentinel() const
Check whether this is the sentinel node.
Definition: ilist_node.h:150
typename ilist_select_iterator_type< OptionsT::has_iterator_bits, OptionsT, true, false >::type reverse_self_iterator
Definition: ilist_node.h:104
typename ilist_select_iterator_type< OptionsT::has_iterator_bits, OptionsT, false, true >::type const_self_iterator
Definition: ilist_node.h:101
const_reverse_self_iterator getReverseIterator() const
Definition: ilist_node.h:139
typename ilist_select_iterator_type< OptionsT::has_iterator_bits, OptionsT, false, false >::type self_iterator
Definition: ilist_node.h:98
typename ilist_select_iterator_type< OptionsT::has_iterator_bits, OptionsT, true, true >::type const_reverse_self_iterator
Definition: ilist_node.h:107
const_self_iterator getIterator() const
Definition: ilist_node.h:133
reverse_self_iterator getReverseIterator()
Definition: ilist_node.h:135
self_iterator getIterator()
Definition: ilist_node.h:132
An ilist node that can access its parent list.
Definition: ilist_node.h:321
const NodeTy * getPrevNode() const
Get the previous node, or nullptr for the list head.
Definition: ilist_node.h:348
NodeTy * getNextNode()
Get the next node, or nullptr for the list tail.
Definition: ilist_node.h:353
const NodeTy * getNextNode() const
Get the next node, or nullptr for the list tail.
Definition: ilist_node.h:362
bool empty() const
Definition: ilist_node.h:313
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:228
static ilist_node_impl< OptionsT > * getPrev(ilist_node_impl< OptionsT > &N)
Definition: ilist_node.h:253
static const ilist_node_impl< OptionsT > * getNext(const ilist_node_impl< OptionsT > &N)
Definition: ilist_node.h:270
static ilist_node_impl< OptionsT > * getNext(ilist_node_impl< OptionsT > &N)
Definition: ilist_node.h:258
static const ilist_node_impl< OptionsT > * getPrev(const ilist_node_impl< OptionsT > &N)
Definition: ilist_node.h:264
static ilist_node_impl< OptionsT > * getNodePtr(typename OptionsT::pointer N)
Definition: ilist_node.h:231
static const ilist_node_impl< OptionsT > * getNodePtr(typename OptionsT::const_pointer N)
Definition: ilist_node.h:237
static OptionsT::pointer getValuePtr(ilist_node_impl< OptionsT > *N)
Definition: ilist_node.h:242
static OptionsT::const_pointer getValuePtr(const ilist_node_impl< OptionsT > *N)
Definition: ilist_node.h:248
static pointer getValuePtr(node_type *N)
Definition: ilist_node.h:289
typename OptionsT::const_pointer const_pointer
Definition: ilist_node.h:278
static const_pointer getValuePtr(const node_type *N)
Definition: ilist_node.h:293
static const node_type * getNodePtr(const_pointer N)
Definition: ilist_node.h:285
static node_type * getNodePtr(pointer N)
Definition: ilist_node.h:281
typename OptionsT::pointer pointer
Definition: ilist_node.h:277
Check whether options are valid.