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( 92 const ilist_iterator<OptionsT, IsReverse, RHSIsConst> &RHS, 93 typename std::enable_if<IsConst || !RHSIsConst, void *>::type = nullptr) 94 : NodePtr(RHS.NodePtr) {} 95 96 // This is templated so that we can allow assigning to a const iterator from 97 // a nonconst iterator... 98 template <bool RHSIsConst> 99 typename std::enable_if<IsConst || !RHSIsConst, ilist_iterator &>::type 100 operator=(const ilist_iterator<OptionsT, IsReverse, RHSIsConst> &RHS) { 101 NodePtr = RHS.NodePtr; 102 return *this; 103 } 104 105 /// Explicit conversion between forward/reverse iterators. 106 /// 107 /// Translate between forward and reverse iterators without changing range 108 /// boundaries. The resulting iterator will dereference (and have a handle) 109 /// to the previous node, which is somewhat unexpected; but converting the 110 /// two endpoints in a range will give the same range in reverse. 111 /// 112 /// This matches std::reverse_iterator conversions. 113 explicit ilist_iterator( 114 const ilist_iterator<OptionsT, !IsReverse, IsConst> &RHS) 115 : ilist_iterator(++RHS.getReverse()) {} 116 117 /// Get a reverse iterator to the same node. 118 /// 119 /// Gives a reverse iterator that will dereference (and have a handle) to the 120 /// same node. Converting the endpoint iterators in a range will give a 121 /// different range; for range operations, use the explicit conversions. 122 ilist_iterator<OptionsT, !IsReverse, IsConst> getReverse() const { 123 if (NodePtr) 124 return ilist_iterator<OptionsT, !IsReverse, IsConst>(*NodePtr); 125 return ilist_iterator<OptionsT, !IsReverse, IsConst>(); 126 } 127 128 /// Const-cast. 129 ilist_iterator<OptionsT, IsReverse, false> getNonConst() const { 130 if (NodePtr) 131 return ilist_iterator<OptionsT, IsReverse, false>( 132 const_cast<typename ilist_iterator<OptionsT, IsReverse, 133 false>::node_reference>(*NodePtr)); 134 return ilist_iterator<OptionsT, IsReverse, false>(); 135 } 136 137 // Accessors... 138 reference operator*() const { 139 assert(!NodePtr->isKnownSentinel()); 140 return *Access::getValuePtr(NodePtr); 141 } 142 pointer operator->() const { return &operator*(); } 143 144 // Comparison operators 145 friend bool operator==(const ilist_iterator &LHS, const ilist_iterator &RHS) { 146 return LHS.NodePtr == RHS.NodePtr; 147 } 148 friend bool operator!=(const ilist_iterator &LHS, const ilist_iterator &RHS) { 149 return LHS.NodePtr != RHS.NodePtr; 150 } 151 152 // Increment and decrement operators... 153 ilist_iterator &operator--() { 154 NodePtr = IsReverse ? NodePtr->getNext() : NodePtr->getPrev(); 155 return *this; 156 } 157 ilist_iterator &operator++() { 158 NodePtr = IsReverse ? NodePtr->getPrev() : NodePtr->getNext(); 159 return *this; 160 } 161 ilist_iterator operator--(int) { 162 ilist_iterator tmp = *this; 163 --*this; 164 return tmp; 165 } 166 ilist_iterator operator++(int) { 167 ilist_iterator tmp = *this; 168 ++*this; 169 return tmp; 170 } 171 172 /// Get the underlying ilist_node. 173 node_pointer getNodePtr() const { return static_cast<node_pointer>(NodePtr); } 174 175 /// Check for end. Only valid if ilist_sentinel_tracking<true>. 176 bool isEnd() const { return NodePtr ? NodePtr->isSentinel() : false; } 177 }; 178 179 template <typename From> struct simplify_type; 180 181 /// Allow ilist_iterators to convert into pointers to a node automatically when 182 /// used by the dyn_cast, cast, isa mechanisms... 183 /// 184 /// FIXME: remove this, since there is no implicit conversion to NodeTy. 185 template <class OptionsT, bool IsConst> 186 struct simplify_type<ilist_iterator<OptionsT, false, IsConst>> { 187 using iterator = ilist_iterator<OptionsT, false, IsConst>; 188 using SimpleType = typename iterator::pointer; 189 190 static SimpleType getSimplifiedValue(const iterator &Node) { return &*Node; } 191 }; 192 template <class OptionsT, bool IsConst> 193 struct simplify_type<const ilist_iterator<OptionsT, false, IsConst>> 194 : simplify_type<ilist_iterator<OptionsT, false, IsConst>> {}; 195 196 } // end namespace llvm 197 198 #endif // LLVM_ADT_ILIST_ITERATOR_H 199