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