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