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