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