Branch data Line data Source code
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 : : /// 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.
30 : : template <class NodeTy, class ParentTy> class node_parent_access {
31 : : public:
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 : : };
42 : : template <class NodeTy> class node_parent_access<NodeTy, void> {};
43 : :
44 : : } // end namespace ilist_detail
45 : :
46 : : template <class OptionsT, bool IsReverse, bool IsConst> class ilist_iterator;
47 : : template <class OptionsT, bool IsReverse, bool IsConst>
48 : : class ilist_iterator_w_bits;
49 : : template <class OptionsT> class ilist_sentinel;
50 : :
51 : : // Selector for which iterator type to pick given the iterator-bits node option.
52 : : template <bool use_iterator_bits, typename Opts, bool arg1, bool arg2>
53 : : class ilist_select_iterator_type {
54 : : public:
55 : : using type = ilist_iterator<Opts, arg1, arg2>;
56 : : };
57 : : template <typename Opts, bool arg1, bool arg2>
58 : : class ilist_select_iterator_type<true, Opts, arg1, arg2> {
59 : : public:
60 : : using type = ilist_iterator_w_bits<Opts, arg1, arg2>;
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.
71 : : template <class OptionsT>
72 : : class ilist_node_impl
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;
81 : : friend struct ilist_detail::NodeAccess;
82 : : friend class ilist_sentinel<OptionsT>;
83 : :
84 : : friend class ilist_detail::node_parent_access<ilist_node_impl<OptionsT>,
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 : :
95 : : protected:
96 : : using self_iterator =
97 : : typename ilist_select_iterator_type<OptionsT::has_iterator_bits, OptionsT,
98 : : false, false>::type;
99 : : using const_self_iterator =
100 : : typename ilist_select_iterator_type<OptionsT::has_iterator_bits, OptionsT,
101 : : false, true>::type;
102 : : using reverse_self_iterator =
103 : : typename ilist_select_iterator_type<OptionsT::has_iterator_bits, OptionsT,
104 : : true, false>::type;
105 : : using const_reverse_self_iterator =
106 : : typename ilist_select_iterator_type<OptionsT::has_iterator_bits, OptionsT,
107 : : true, true>::type;
108 : :
109 : : ilist_node_impl() = default;
110 : :
111 : : private:
112 : : ilist_node_impl *getPrev() {
113 : : return static_cast<ilist_node_impl *>(node_base_type::getPrev());
114 : : }
115 : :
116 : 0 : ilist_node_impl *getNext() {
117 : 0 : 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 : :
131 : : public:
132 : : self_iterator getIterator() { return self_iterator(*this); }
133 : : const_self_iterator getIterator() const { return const_self_iterator(*this); }
134 : :
135 : : reverse_self_iterator getReverseIterator() {
136 : : return reverse_self_iterator(*this);
137 : : }
138 : :
139 : : const_reverse_self_iterator getReverseIterator() const {
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.
212 : : template <class T, class... Options>
213 : : class ilist_node
214 : : : public ilist_node_impl<
215 : : typename ilist_detail::compute_node_options<T, Options...>::type> {
216 : : static_assert(ilist_detail::check_options<Options...>::value,
217 : : "Unrecognized node option!");
218 : : };
219 : :
220 : : namespace 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.
228 : : struct NodeAccess {
229 : : protected:
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 : 0 : static typename OptionsT::pointer getValuePtr(ilist_node_impl<OptionsT> *N) {
243 [ # # ]: 0 : return static_cast<typename OptionsT::pointer>(N);
244 : : }
245 : :
246 : : template <class OptionsT>
247 : : static typename OptionsT::const_pointer
248 : : getValuePtr(const ilist_node_impl<OptionsT> *N) {
249 : : return static_cast<typename OptionsT::const_pointer>(N);
250 : : }
251 : :
252 : : template <class OptionsT>
253 : : static ilist_node_impl<OptionsT> *getPrev(ilist_node_impl<OptionsT> &N) {
254 : : return N.getPrev();
255 : : }
256 : :
257 : : template <class OptionsT>
258 : : static ilist_node_impl<OptionsT> *getNext(ilist_node_impl<OptionsT> &N) {
259 : : return N.getNext();
260 : : }
261 : :
262 : : template <class OptionsT>
263 : : static const ilist_node_impl<OptionsT> *
264 : : getPrev(const ilist_node_impl<OptionsT> &N) {
265 : : return N.getPrev();
266 : : }
267 : :
268 : : template <class OptionsT>
269 : : static const ilist_node_impl<OptionsT> *
270 : : getNext(const ilist_node_impl<OptionsT> &N) {
271 : : return N.getNext();
272 : : }
273 : : };
274 : :
275 : : template <class OptionsT> struct SpecificNodeAccess : NodeAccess {
276 : : protected:
277 : : using pointer = typename OptionsT::pointer;
278 : : using const_pointer = typename OptionsT::const_pointer;
279 : : using node_type = ilist_node_impl<OptionsT>;
280 : :
281 : : static node_type *getNodePtr(pointer N) {
282 : : return NodeAccess::getNodePtr<OptionsT>(N);
283 : : }
284 : :
285 : : static const node_type *getNodePtr(const_pointer N) {
286 : : return NodeAccess::getNodePtr<OptionsT>(N);
287 : : }
288 : :
289 : 0 : static pointer getValuePtr(node_type *N) {
290 : 0 : return NodeAccess::getValuePtr<OptionsT>(N);
291 : : }
292 : :
293 : : static const_pointer getValuePtr(const node_type *N) {
294 : : return NodeAccess::getValuePtr<OptionsT>(N);
295 : : }
296 : : };
297 : :
298 : : } // end namespace ilist_detail
299 : :
300 : : template <class OptionsT>
301 : : class ilist_sentinel : public ilist_node_impl<OptionsT> {
302 : : public:
303 : : ilist_sentinel() {
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.
320 : : template <typename NodeTy, typename ParentTy, class... Options>
321 : : class ilist_node_with_parent : public ilist_node<NodeTy, Options...> {
322 : : protected:
323 : : ilist_node_with_parent() = default;
324 : :
325 : : private:
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 : :
335 : : public:
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
|
