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 return static_cast<ilist_node_impl *>(node_base_type::getPrev()); 64 } 65 66 ilist_node_impl *getNext() { 67 return static_cast<ilist_node_impl *>(node_base_type::getNext()); 68 } 69 70 const ilist_node_impl *getPrev() const { 71 return static_cast<ilist_node_impl *>(node_base_type::getPrev()); 72 } 73 74 const ilist_node_impl *getNext() const { 75 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 return N; 169 } 170 171 template <class OptionsT> 172 static const ilist_node_impl<OptionsT> * 173 getNodePtr(typename OptionsT::const_pointer N) { 174 return N; 175 } 176 177 template <class OptionsT> 178 static typename OptionsT::pointer getValuePtr(ilist_node_impl<OptionsT> *N) { 179 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 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 ilist_sentinel() { 240 this->initializeSentinel(); 241 reset(); 242 } 243 244 void reset() { 245 this->setPrev(this); 246 this->setNext(this); 247 } 248 249 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 return static_cast<const NodeTy *>(this)->getParent(); 269 } 270 271 public: 272 /// @name Adjacent Node Accessors 273 /// @{ 274 /// \brief 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 /// \brief 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 /// \brief 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 /// \brief 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 307