1 //==-- llvm/ADT/ilist_node.h - Intrusive Linked List Helper ------*- C++ -*-==//
3 // The LLVM Compiler Infrastructure
5 // This file is distributed under the University of Illinois Open Source
6 // License. See LICENSE.TXT for details.
8 //===----------------------------------------------------------------------===//
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.
13 //===----------------------------------------------------------------------===//
15 #ifndef LLVM_ADT_ILIST_NODE_H
16 #define LLVM_ADT_ILIST_NODE_H
18 #include "llvm/ADT/ilist_node_base.h"
19 #include "llvm/ADT/ilist_node_options.h"
23 namespace ilist_detail {
25 } // end namespace ilist_detail
27 template<typename NodeTy>
30 template <class OptionsT, bool IsReverse, bool IsConst> class ilist_iterator;
31 template <class OptionsT> class ilist_sentinel;
33 /// Implementation for an ilist node.
35 /// Templated on an appropriate \a ilist_detail::node_options, usually computed
36 /// by \a ilist_detail::compute_node_options.
38 /// This is a wrapper around \a ilist_node_base whose main purpose is to
39 /// provide type safety: you can't insert nodes of \a ilist_node_impl into the
40 /// wrong \a simple_ilist or \a iplist.
41 template <class OptionsT> class ilist_node_impl : OptionsT::node_base_type {
42 typedef typename OptionsT::value_type value_type;
43 typedef typename OptionsT::node_base_type node_base_type;
44 typedef typename OptionsT::list_base_type list_base_type;
46 friend typename OptionsT::list_base_type;
47 friend struct ilist_detail::NodeAccess;
48 friend class ilist_sentinel<OptionsT>;
49 friend class ilist_iterator<OptionsT, false, false>;
50 friend class ilist_iterator<OptionsT, false, true>;
51 friend class ilist_iterator<OptionsT, true, false>;
52 friend class ilist_iterator<OptionsT, true, true>;
55 ilist_node_impl() = default;
57 typedef ilist_iterator<OptionsT, false, false> self_iterator;
58 typedef ilist_iterator<OptionsT, false, true> const_self_iterator;
59 typedef ilist_iterator<OptionsT, true, false> reverse_self_iterator;
60 typedef ilist_iterator<OptionsT, true, true> const_reverse_self_iterator;
63 ilist_node_impl *getPrev() {
64 return static_cast<ilist_node_impl *>(node_base_type::getPrev());
66 ilist_node_impl *getNext() {
67 return static_cast<ilist_node_impl *>(node_base_type::getNext());
70 const ilist_node_impl *getPrev() const {
71 return static_cast<ilist_node_impl *>(node_base_type::getPrev());
73 const ilist_node_impl *getNext() const {
74 return static_cast<ilist_node_impl *>(node_base_type::getNext());
77 void setPrev(ilist_node_impl *N) { node_base_type::setPrev(N); }
78 void setNext(ilist_node_impl *N) { node_base_type::setNext(N); }
81 self_iterator getIterator() { return self_iterator(*this); }
82 const_self_iterator getIterator() const { return const_self_iterator(*this); }
83 reverse_self_iterator getReverseIterator() {
84 return reverse_self_iterator(*this);
86 const_reverse_self_iterator getReverseIterator() const {
87 return const_reverse_self_iterator(*this);
90 // Under-approximation, but always available for assertions.
91 using node_base_type::isKnownSentinel;
93 /// Check whether this is the sentinel node.
95 /// This requires sentinel tracking to be explicitly enabled. Use the
96 /// ilist_sentinel_tracking<true> option to get this API.
97 bool isSentinel() const {
98 static_assert(OptionsT::is_sentinel_tracking_explicit,
99 "Use ilist_sentinel_tracking<true> to enable isSentinel()");
100 return node_base_type::isSentinel();
104 /// An intrusive list node.
106 /// A base class to enable membership in intrusive lists, including \a
107 /// simple_ilist, \a iplist, and \a ilist. The first template parameter is the
108 /// \a value_type for the list.
110 /// An ilist node can be configured with compile-time options to change
111 /// behaviour and/or add API.
113 /// By default, an \a ilist_node knows whether it is the list sentinel (an
114 /// instance of \a ilist_sentinel) if and only if
115 /// LLVM_ENABLE_ABI_BREAKING_CHECKS. The function \a isKnownSentinel() always
116 /// returns \c false tracking is off. Sentinel tracking steals a bit from the
117 /// "prev" link, which adds a mask operation when decrementing an iterator, but
118 /// enables bug-finding assertions in \a ilist_iterator.
120 /// To turn sentinel tracking on all the time, pass in the
121 /// ilist_sentinel_tracking<true> template parameter. This also enables the \a
122 /// isSentinel() function. The same option must be passed to the intrusive
123 /// list. (ilist_sentinel_tracking<false> turns sentinel tracking off all the
126 /// A type can inherit from ilist_node multiple times by passing in different
127 /// \a ilist_tag options. This allows a single instance to be inserted into
128 /// multiple lists simultaneously, where each list is given the same tag.
133 /// struct N : ilist_node<N, ilist_tag<A>>, ilist_node<N, ilist_tag<B>> {};
136 /// simple_ilist<N, ilist_tag<A>> ListA;
137 /// simple_ilist<N, ilist_tag<B>> ListB;
139 /// ListA.push_back(N1);
140 /// ListB.push_back(N1);
144 /// See \a is_valid_option for steps on adding a new option.
145 template <class T, class... Options>
147 : public ilist_node_impl<
148 typename ilist_detail::compute_node_options<T, Options...>::type> {
149 static_assert(ilist_detail::check_options<Options...>::value,
150 "Unrecognized node option!");
153 namespace ilist_detail {
154 /// An access class for ilist_node private API.
156 /// This gives access to the private parts of ilist nodes. Nodes for an ilist
157 /// should friend this class if they inherit privately from ilist_node.
159 /// Using this class outside of the ilist implementation is unsupported.
162 template <class OptionsT>
163 static ilist_node_impl<OptionsT> *getNodePtr(typename OptionsT::pointer N) {
166 template <class OptionsT>
167 static const ilist_node_impl<OptionsT> *
168 getNodePtr(typename OptionsT::const_pointer N) {
171 template <class OptionsT>
172 static typename OptionsT::pointer getValuePtr(ilist_node_impl<OptionsT> *N) {
173 return static_cast<typename OptionsT::pointer>(N);
175 template <class OptionsT>
176 static typename OptionsT::const_pointer
177 getValuePtr(const ilist_node_impl<OptionsT> *N) {
178 return static_cast<typename OptionsT::const_pointer>(N);
181 template <class OptionsT>
182 static ilist_node_impl<OptionsT> *getPrev(ilist_node_impl<OptionsT> &N) {
185 template <class OptionsT>
186 static ilist_node_impl<OptionsT> *getNext(ilist_node_impl<OptionsT> &N) {
189 template <class OptionsT>
190 static const ilist_node_impl<OptionsT> *
191 getPrev(const ilist_node_impl<OptionsT> &N) {
194 template <class OptionsT>
195 static const ilist_node_impl<OptionsT> *
196 getNext(const ilist_node_impl<OptionsT> &N) {
201 template <class OptionsT> struct SpecificNodeAccess : NodeAccess {
203 typedef typename OptionsT::pointer pointer;
204 typedef typename OptionsT::const_pointer const_pointer;
205 typedef ilist_node_impl<OptionsT> node_type;
207 static node_type *getNodePtr(pointer N) {
208 return NodeAccess::getNodePtr<OptionsT>(N);
210 static const node_type *getNodePtr(const_pointer N) {
211 return NodeAccess::getNodePtr<OptionsT>(N);
213 static pointer getValuePtr(node_type *N) {
214 return NodeAccess::getValuePtr<OptionsT>(N);
216 static const_pointer getValuePtr(const node_type *N) {
217 return NodeAccess::getValuePtr<OptionsT>(N);
220 } // end namespace ilist_detail
222 template <class OptionsT>
223 class ilist_sentinel : public ilist_node_impl<OptionsT> {
226 this->initializeSentinel();
235 bool empty() const { return this == this->getPrev(); }
238 /// An ilist node that can access its parent list.
240 /// Requires \c NodeTy to have \a getParent() to find the parent node, and the
241 /// \c ParentTy to have \a getSublistAccess() to get a reference to the list.
242 template <typename NodeTy, typename ParentTy, class... Options>
243 class ilist_node_with_parent : public ilist_node<NodeTy, Options...> {
245 ilist_node_with_parent() = default;
248 /// Forward to NodeTy::getParent().
250 /// Note: do not use the name "getParent()". We want a compile error
251 /// (instead of recursion) when the subclass fails to implement \a
253 const ParentTy *getNodeParent() const {
254 return static_cast<const NodeTy *>(this)->getParent();
258 /// @name Adjacent Node Accessors
260 /// \brief Get the previous node, or \c nullptr for the list head.
261 NodeTy *getPrevNode() {
262 // Should be separated to a reused function, but then we couldn't use auto
263 // (and would need the type of the list).
265 getNodeParent()->*(ParentTy::getSublistAccess((NodeTy *)nullptr));
266 return List.getPrevNode(*static_cast<NodeTy *>(this));
268 /// \brief Get the previous node, or \c nullptr for the list head.
269 const NodeTy *getPrevNode() const {
270 return const_cast<ilist_node_with_parent *>(this)->getPrevNode();
273 /// \brief Get the next node, or \c nullptr for the list tail.
274 NodeTy *getNextNode() {
275 // Should be separated to a reused function, but then we couldn't use auto
276 // (and would need the type of the list).
278 getNodeParent()->*(ParentTy::getSublistAccess((NodeTy *)nullptr));
279 return List.getNextNode(*static_cast<NodeTy *>(this));
281 /// \brief Get the next node, or \c nullptr for the list tail.
282 const NodeTy *getNextNode() const {
283 return const_cast<ilist_node_with_parent *>(this)->getNextNode();
288 } // End llvm namespace