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 | |
18 | #include "llvm/ADT/ilist_node_base.h" |
19 | #include "llvm/ADT/ilist_node_options.h" |
20 | |
21 | namespace llvm { |
22 | |
23 | namespace ilist_detail { |
24 | |
25 | struct NodeAccess; |
26 | |
27 | } // end namespace ilist_detail |
28 | |
29 | template <class OptionsT, bool IsReverse, bool IsConst> class ilist_iterator; |
30 | template <class OptionsT, bool IsReverse, bool IsConst> |
31 | class ilist_iterator_w_bits; |
32 | template <class OptionsT> class ilist_sentinel; |
33 | |
34 | // Selector for which iterator type to pick given the iterator-bits node option. |
35 | template <bool use_iterator_bits, typename Opts, bool arg1, bool arg2> |
36 | class ilist_select_iterator_type { |
37 | public: |
38 | using type = ilist_iterator<Opts, arg1, arg2>; |
39 | }; |
40 | template <typename Opts, bool arg1, bool arg2> |
41 | class ilist_select_iterator_type<true, Opts, arg1, arg2> { |
42 | public: |
43 | using type = ilist_iterator_w_bits<Opts, arg1, arg2>; |
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. |
54 | template <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; |
60 | friend struct ilist_detail::NodeAccess; |
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 | |
72 | protected: |
73 | using self_iterator = |
74 | typename ilist_select_iterator_type<OptionsT::has_iterator_bits, OptionsT, |
75 | false, false>::type; |
76 | using const_self_iterator = |
77 | typename ilist_select_iterator_type<OptionsT::has_iterator_bits, OptionsT, |
78 | false, true>::type; |
79 | using reverse_self_iterator = |
80 | typename ilist_select_iterator_type<OptionsT::has_iterator_bits, OptionsT, |
81 | true, false>::type; |
82 | using const_reverse_self_iterator = |
83 | typename ilist_select_iterator_type<OptionsT::has_iterator_bits, OptionsT, |
84 | true, true>::type; |
85 | |
86 | ilist_node_impl() = default; |
87 | |
88 | private: |
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 | |
108 | public: |
109 | self_iterator getIterator() { return self_iterator(*this); } |
110 | const_self_iterator getIterator() const { return const_self_iterator(*this); } |
111 | |
112 | reverse_self_iterator getReverseIterator() { |
113 | return reverse_self_iterator(*this); |
114 | } |
115 | |
116 | const_reverse_self_iterator getReverseIterator() const { |
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. |
175 | template <class T, class... Options> |
176 | class ilist_node |
177 | : public ilist_node_impl< |
178 | typename ilist_detail::compute_node_options<T, Options...>::type> { |
179 | static_assert(ilist_detail::check_options<Options...>::value, |
180 | "Unrecognized node option!" ); |
181 | }; |
182 | |
183 | namespace 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. |
191 | struct NodeAccess { |
192 | protected: |
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 |
211 | getValuePtr(const ilist_node_impl<OptionsT> *N) { |
212 | return static_cast<typename OptionsT::const_pointer>(N); |
213 | } |
214 | |
215 | template <class OptionsT> |
216 | static ilist_node_impl<OptionsT> *getPrev(ilist_node_impl<OptionsT> &N) { |
217 | return N.getPrev(); |
218 | } |
219 | |
220 | template <class OptionsT> |
221 | static ilist_node_impl<OptionsT> *getNext(ilist_node_impl<OptionsT> &N) { |
222 | return N.getNext(); |
223 | } |
224 | |
225 | template <class OptionsT> |
226 | static const ilist_node_impl<OptionsT> * |
227 | getPrev(const ilist_node_impl<OptionsT> &N) { |
228 | return N.getPrev(); |
229 | } |
230 | |
231 | template <class OptionsT> |
232 | static const ilist_node_impl<OptionsT> * |
233 | getNext(const ilist_node_impl<OptionsT> &N) { |
234 | return N.getNext(); |
235 | } |
236 | }; |
237 | |
238 | template <class OptionsT> struct SpecificNodeAccess : NodeAccess { |
239 | protected: |
240 | using pointer = typename OptionsT::pointer; |
241 | using const_pointer = typename OptionsT::const_pointer; |
242 | using node_type = ilist_node_impl<OptionsT>; |
243 | |
244 | static node_type *getNodePtr(pointer N) { |
245 | return NodeAccess::getNodePtr<OptionsT>(N); |
246 | } |
247 | |
248 | static const node_type *getNodePtr(const_pointer N) { |
249 | return NodeAccess::getNodePtr<OptionsT>(N); |
250 | } |
251 | |
252 | static pointer getValuePtr(node_type *N) { |
253 | return NodeAccess::getValuePtr<OptionsT>(N); |
254 | } |
255 | |
256 | static const_pointer getValuePtr(const node_type *N) { |
257 | return NodeAccess::getValuePtr<OptionsT>(N); |
258 | } |
259 | }; |
260 | |
261 | } // end namespace ilist_detail |
262 | |
263 | template <class OptionsT> |
264 | class ilist_sentinel : public ilist_node_impl<OptionsT> { |
265 | public: |
266 | ilist_sentinel() { |
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. |
283 | template <typename NodeTy, typename ParentTy, class... Options> |
284 | class ilist_node_with_parent : public ilist_node<NodeTy, Options...> { |
285 | protected: |
286 | ilist_node_with_parent() = default; |
287 | |
288 | private: |
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 | |
298 | public: |
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 |
334 | |