1 //===- llvm/ADT/ilist_iterator.h - Intrusive List Iterator ------*- 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 #ifndef LLVM_ADT_ILIST_ITERATOR_H 10 #define LLVM_ADT_ILIST_ITERATOR_H 11 12 #include "llvm/ADT/ilist_node.h" 13 #include <cassert> 14 #include <cstddef> 15 #include <iterator> 16 #include <type_traits> 17 18 namespace llvm { 19 20 namespace ilist_detail { 21 22 /// Find const-correct node types. 23 template <class OptionsT, bool IsConst> struct IteratorTraits; 24 template <class OptionsT> struct IteratorTraits<OptionsT, false> { 25 using value_type = typename OptionsT::value_type; 26 using pointer = typename OptionsT::pointer; 27 using reference = typename OptionsT::reference; 28 using node_pointer = ilist_node_impl<OptionsT> *; 29 using node_reference = ilist_node_impl<OptionsT> &; 30 }; 31 template <class OptionsT> struct IteratorTraits<OptionsT, true> { 32 using value_type = const typename OptionsT::value_type; 33 using pointer = typename OptionsT::const_pointer; 34 using reference = typename OptionsT::const_reference; 35 using node_pointer = const ilist_node_impl<OptionsT> *; 36 using node_reference = const ilist_node_impl<OptionsT> &; 37 }; 38 39 template <bool IsReverse> struct IteratorHelper; 40 template <> struct IteratorHelper<false> : ilist_detail::NodeAccess { 41 using Access = ilist_detail::NodeAccess; 42 43 template <class T> static void increment(T *&I) { I = Access::getNext(*I); } 44 template <class T> static void decrement(T *&I) { I = Access::getPrev(*I); } 45 }; 46 template <> struct IteratorHelper<true> : ilist_detail::NodeAccess { 47 using Access = ilist_detail::NodeAccess; 48 49 template <class T> static void increment(T *&I) { I = Access::getPrev(*I); } 50 template <class T> static void decrement(T *&I) { I = Access::getNext(*I); } 51 }; 52 53 } // end namespace ilist_detail 54 55 /// Iterator for intrusive lists based on ilist_node. 56 template <class OptionsT, bool IsReverse, bool IsConst> 57 class ilist_iterator : ilist_detail::SpecificNodeAccess<OptionsT> { 58 friend ilist_iterator<OptionsT, IsReverse, !IsConst>; 59 friend ilist_iterator<OptionsT, !IsReverse, IsConst>; 60 friend ilist_iterator<OptionsT, !IsReverse, !IsConst>; 61 62 using Traits = ilist_detail::IteratorTraits<OptionsT, IsConst>; 63 using Access = ilist_detail::SpecificNodeAccess<OptionsT>; 64 65 public: 66 using value_type = typename Traits::value_type; 67 using pointer = typename Traits::pointer; 68 using reference = typename Traits::reference; 69 using difference_type = ptrdiff_t; 70 using iterator_category = std::bidirectional_iterator_tag; 71 using const_pointer = typename OptionsT::const_pointer; 72 using const_reference = typename OptionsT::const_reference; 73 74 private: 75 using node_pointer = typename Traits::node_pointer; 76 using node_reference = typename Traits::node_reference; 77 78 node_pointer NodePtr = nullptr; 79 80 public: 81 /// Create from an ilist_node. 82 explicit ilist_iterator(node_reference N) : NodePtr(&N) {} 83 84 explicit ilist_iterator(pointer NP) : NodePtr(Access::getNodePtr(NP)) {} 85 explicit ilist_iterator(reference NR) : NodePtr(Access::getNodePtr(&NR)) {} 86 ilist_iterator() = default; 87 88 // This is templated so that we can allow constructing a const iterator from 89 // a nonconst iterator... 90 template <bool RHSIsConst> 91 ilist_iterator(const ilist_iterator<OptionsT, IsReverse, RHSIsConst> &RHS, 92 std::enable_if_t<IsConst || !RHSIsConst, void *> = nullptr) 93 : NodePtr(RHS.NodePtr) {} 94 95 // This is templated so that we can allow assigning to a const iterator from 96 // a nonconst iterator... 97 template <bool RHSIsConst> 98 std::enable_if_t<IsConst || !RHSIsConst, ilist_iterator &> 99 operator=(const ilist_iterator<OptionsT, IsReverse, RHSIsConst> &RHS) { 100 NodePtr = RHS.NodePtr; 101 return *this; 102 } 103 104 /// Explicit conversion between forward/reverse iterators. 105 /// 106 /// Translate between forward and reverse iterators without changing range 107 /// boundaries. The resulting iterator will dereference (and have a handle) 108 /// to the previous node, which is somewhat unexpected; but converting the 109 /// two endpoints in a range will give the same range in reverse. 110 /// 111 /// This matches std::reverse_iterator conversions. 112 explicit ilist_iterator( 113 const ilist_iterator<OptionsT, !IsReverse, IsConst> &RHS) 114 : ilist_iterator(++RHS.getReverse()) {} 115 116 /// Get a reverse iterator to the same node. 117 /// 118 /// Gives a reverse iterator that will dereference (and have a handle) to the 119 /// same node. Converting the endpoint iterators in a range will give a 120 /// different range; for range operations, use the explicit conversions. 121 ilist_iterator<OptionsT, !IsReverse, IsConst> getReverse() const { 122 if (NodePtr) 123 return ilist_iterator<OptionsT, !IsReverse, IsConst>(*NodePtr); 124 return ilist_iterator<OptionsT, !IsReverse, IsConst>(); 125 } 126 127 /// Const-cast. 128 ilist_iterator<OptionsT, IsReverse, false> getNonConst() const { 129 if (NodePtr) 130 return ilist_iterator<OptionsT, IsReverse, false>( 131 const_cast<typename ilist_iterator<OptionsT, IsReverse, 132 false>::node_reference>(*NodePtr)); 133 return ilist_iterator<OptionsT, IsReverse, false>(); 134 } 135 136 // Accessors... 137 reference operator*() const { 138 assert(!NodePtr->isKnownSentinel()); 139 return *Access::getValuePtr(NodePtr); 140 } 141 pointer operator->() const { return &operator*(); } 142 143 // Comparison operators 144 friend bool operator==(const ilist_iterator &LHS, const ilist_iterator &RHS) { 145 return LHS.NodePtr == RHS.NodePtr; 146 } 147 friend bool operator!=(const ilist_iterator &LHS, const ilist_iterator &RHS) { 148 return LHS.NodePtr != RHS.NodePtr; 149 } 150 151 // Increment and decrement operators... 152 ilist_iterator &operator--() { 153 NodePtr = IsReverse ? NodePtr->getNext() : NodePtr->getPrev(); 154 return *this; 155 } 156 ilist_iterator &operator++() { 157 NodePtr = IsReverse ? NodePtr->getPrev() : NodePtr->getNext(); 158 return *this; 159 } 160 ilist_iterator operator--(int) { 161 ilist_iterator tmp = *this; 162 --*this; 163 return tmp; 164 } 165 ilist_iterator operator++(int) { 166 ilist_iterator tmp = *this; 167 ++*this; 168 return tmp; 169 } 170 171 /// Get the underlying ilist_node. 172 node_pointer getNodePtr() const { return static_cast<node_pointer>(NodePtr); } 173 174 /// Check for end. Only valid if ilist_sentinel_tracking<true>. 175 bool isEnd() const { return NodePtr ? NodePtr->isSentinel() : false; } 176 }; 177 178 /// Iterator for intrusive lists based on ilist_node. Much like ilist_iterator, 179 /// but with the addition of two bits recording whether this position (when in 180 /// a range) is half or fully open. 181 template <class OptionsT, bool IsReverse, bool IsConst> 182 class ilist_iterator_w_bits : ilist_detail::SpecificNodeAccess<OptionsT> { 183 friend ilist_iterator_w_bits<OptionsT, IsReverse, !IsConst>; 184 friend ilist_iterator_w_bits<OptionsT, !IsReverse, IsConst>; 185 friend ilist_iterator<OptionsT, !IsReverse, !IsConst>; 186 187 using Traits = ilist_detail::IteratorTraits<OptionsT, IsConst>; 188 using Access = ilist_detail::SpecificNodeAccess<OptionsT>; 189 190 public: 191 using value_type = typename Traits::value_type; 192 using pointer = typename Traits::pointer; 193 using reference = typename Traits::reference; 194 using difference_type = ptrdiff_t; 195 using iterator_category = std::bidirectional_iterator_tag; 196 using const_pointer = typename OptionsT::const_pointer; 197 using const_reference = typename OptionsT::const_reference; 198 199 private: 200 using node_pointer = typename Traits::node_pointer; 201 using node_reference = typename Traits::node_reference; 202 203 node_pointer NodePtr = nullptr; 204 205 #ifdef EXPERIMENTAL_DEBUGINFO_ITERATORS 206 // (Default: Off) Allow extra position-information flags to be stored 207 // in iterators, in aid of removing debug-info intrinsics from LLVM. 208 209 /// Is this position intended to contain any debug-info immediately before 210 /// the position? 211 mutable bool HeadInclusiveBit = false; 212 /// Is this position intended to contain any debug-info immediately after 213 /// the position? 214 mutable bool TailInclusiveBit = false; 215 #endif 216 217 public: 218 /// Create from an ilist_node. 219 explicit ilist_iterator_w_bits(node_reference N) : NodePtr(&N) {} 220 221 explicit ilist_iterator_w_bits(pointer NP) 222 : NodePtr(Access::getNodePtr(NP)) {} 223 explicit ilist_iterator_w_bits(reference NR) 224 : NodePtr(Access::getNodePtr(&NR)) {} 225 ilist_iterator_w_bits() = default; 226 227 // This is templated so that we can allow constructing a const iterator from 228 // a nonconst iterator... 229 template <bool RHSIsConst> 230 ilist_iterator_w_bits( 231 const ilist_iterator_w_bits<OptionsT, IsReverse, RHSIsConst> &RHS, 232 std::enable_if_t<IsConst || !RHSIsConst, void *> = nullptr) 233 : NodePtr(RHS.NodePtr) { 234 #ifdef EXPERIMENTAL_DEBUGINFO_ITERATORS 235 HeadInclusiveBit = RHS.HeadInclusiveBit; 236 TailInclusiveBit = RHS.TailInclusiveBit; 237 #endif 238 } 239 240 // This is templated so that we can allow assigning to a const iterator from 241 // a nonconst iterator... 242 template <bool RHSIsConst> 243 std::enable_if_t<IsConst || !RHSIsConst, ilist_iterator_w_bits &> 244 operator=(const ilist_iterator_w_bits<OptionsT, IsReverse, RHSIsConst> &RHS) { 245 NodePtr = RHS.NodePtr; 246 #ifdef EXPERIMENTAL_DEBUGINFO_ITERATORS 247 HeadInclusiveBit = RHS.HeadInclusiveBit; 248 TailInclusiveBit = RHS.TailInclusiveBit; 249 #endif 250 return *this; 251 } 252 253 /// Explicit conversion between forward/reverse iterators. 254 /// 255 /// Translate between forward and reverse iterators without changing range 256 /// boundaries. The resulting iterator will dereference (and have a handle) 257 /// to the previous node, which is somewhat unexpected; but converting the 258 /// two endpoints in a range will give the same range in reverse. 259 /// 260 /// This matches std::reverse_iterator conversions. 261 explicit ilist_iterator_w_bits( 262 const ilist_iterator_w_bits<OptionsT, !IsReverse, IsConst> &RHS) 263 : ilist_iterator_w_bits(++RHS.getReverse()) {} 264 265 /// Get a reverse iterator to the same node. 266 /// 267 /// Gives a reverse iterator that will dereference (and have a handle) to the 268 /// same node. Converting the endpoint iterators in a range will give a 269 /// different range; for range operations, use the explicit conversions. 270 ilist_iterator_w_bits<OptionsT, !IsReverse, IsConst> getReverse() const { 271 if (NodePtr) 272 return ilist_iterator_w_bits<OptionsT, !IsReverse, IsConst>(*NodePtr); 273 return ilist_iterator_w_bits<OptionsT, !IsReverse, IsConst>(); 274 } 275 276 /// Const-cast. 277 ilist_iterator_w_bits<OptionsT, IsReverse, false> getNonConst() const { 278 if (NodePtr) { 279 auto New = ilist_iterator_w_bits<OptionsT, IsReverse, false>( 280 const_cast<typename ilist_iterator_w_bits<OptionsT, IsReverse, 281 false>::node_reference>( 282 *NodePtr)); 283 #ifdef EXPERIMENTAL_DEBUGINFO_ITERATORS 284 New.HeadInclusiveBit = HeadInclusiveBit; 285 New.TailInclusiveBit = TailInclusiveBit; 286 #endif 287 return New; 288 } 289 return ilist_iterator_w_bits<OptionsT, IsReverse, false>(); 290 } 291 292 // Accessors... 293 reference operator*() const { 294 assert(!NodePtr->isKnownSentinel()); 295 return *Access::getValuePtr(NodePtr); 296 } 297 pointer operator->() const { return &operator*(); } 298 299 // Comparison operators 300 friend bool operator==(const ilist_iterator_w_bits &LHS, 301 const ilist_iterator_w_bits &RHS) { 302 return LHS.NodePtr == RHS.NodePtr; 303 } 304 friend bool operator!=(const ilist_iterator_w_bits &LHS, 305 const ilist_iterator_w_bits &RHS) { 306 return LHS.NodePtr != RHS.NodePtr; 307 } 308 309 // Increment and decrement operators... 310 ilist_iterator_w_bits &operator--() { 311 NodePtr = IsReverse ? NodePtr->getNext() : NodePtr->getPrev(); 312 #ifdef EXPERIMENTAL_DEBUGINFO_ITERATORS 313 HeadInclusiveBit = false; 314 TailInclusiveBit = false; 315 #endif 316 return *this; 317 } 318 ilist_iterator_w_bits &operator++() { 319 NodePtr = IsReverse ? NodePtr->getPrev() : NodePtr->getNext(); 320 #ifdef EXPERIMENTAL_DEBUGINFO_ITERATORS 321 HeadInclusiveBit = false; 322 TailInclusiveBit = false; 323 #endif 324 return *this; 325 } 326 ilist_iterator_w_bits operator--(int) { 327 ilist_iterator_w_bits tmp = *this; 328 --*this; 329 return tmp; 330 } 331 ilist_iterator_w_bits operator++(int) { 332 ilist_iterator_w_bits tmp = *this; 333 ++*this; 334 return tmp; 335 } 336 337 /// Get the underlying ilist_node. 338 node_pointer getNodePtr() const { return static_cast<node_pointer>(NodePtr); } 339 340 /// Check for end. Only valid if ilist_sentinel_tracking<true>. 341 bool isEnd() const { return NodePtr ? NodePtr->isSentinel() : false; } 342 343 #ifdef EXPERIMENTAL_DEBUGINFO_ITERATORS 344 bool getHeadBit() const { return HeadInclusiveBit; } 345 bool getTailBit() const { return TailInclusiveBit; } 346 void setHeadBit(bool SetBit) const { HeadInclusiveBit = SetBit; } 347 void setTailBit(bool SetBit) const { TailInclusiveBit = SetBit; } 348 #else 349 // Store and return no information if we're not using this feature. 350 bool getHeadBit() const { return false; } 351 bool getTailBit() const { return false; } 352 void setHeadBit(bool SetBit) const { (void)SetBit; } 353 void setTailBit(bool SetBit) const { (void)SetBit; } 354 #endif 355 }; 356 357 template <typename From> struct simplify_type; 358 359 /// Allow ilist_iterators to convert into pointers to a node automatically when 360 /// used by the dyn_cast, cast, isa mechanisms... 361 /// 362 /// FIXME: remove this, since there is no implicit conversion to NodeTy. 363 template <class OptionsT, bool IsConst> 364 struct simplify_type<ilist_iterator<OptionsT, false, IsConst>> { 365 using iterator = ilist_iterator<OptionsT, false, IsConst>; 366 using SimpleType = typename iterator::pointer; 367 368 static SimpleType getSimplifiedValue(const iterator &Node) { return &*Node; } 369 }; 370 template <class OptionsT, bool IsConst> 371 struct simplify_type<const ilist_iterator<OptionsT, false, IsConst>> 372 : simplify_type<ilist_iterator<OptionsT, false, IsConst>> {}; 373 374 // ilist_iterator_w_bits should also be accessible via isa/dyn_cast. 375 template <class OptionsT, bool IsConst> 376 struct simplify_type<ilist_iterator_w_bits<OptionsT, false, IsConst>> { 377 using iterator = ilist_iterator_w_bits<OptionsT, false, IsConst>; 378 using SimpleType = typename iterator::pointer; 379 380 static SimpleType getSimplifiedValue(const iterator &Node) { return &*Node; } 381 }; 382 template <class OptionsT, bool IsConst> 383 struct simplify_type<const ilist_iterator_w_bits<OptionsT, false, IsConst>> 384 : simplify_type<ilist_iterator_w_bits<OptionsT, false, IsConst>> {}; 385 386 } // end namespace llvm 387 388 #endif // LLVM_ADT_ILIST_ITERATOR_H 389