1 //===- llvm/ADT/ilist_iterator.h - Intrusive List Iterator ------*- 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 #ifndef LLVM_ADT_ILIST_ITERATOR_H 11 #define LLVM_ADT_ILIST_ITERATOR_H 12 13 #include "llvm/ADT/ilist_node.h" 14 #include <cassert> 15 #include <cstddef> 16 #include <iterator> 17 #include <type_traits> 18 19 namespace llvm { 20 21 namespace ilist_detail { 22 23 /// Find const-correct node types. 24 template <class OptionsT, bool IsConst> struct IteratorTraits; 25 template <class OptionsT> struct IteratorTraits<OptionsT, false> { 26 using value_type = typename OptionsT::value_type; 27 using pointer = typename OptionsT::pointer; 28 using reference = typename OptionsT::reference; 29 using node_pointer = ilist_node_impl<OptionsT> *; 30 using node_reference = ilist_node_impl<OptionsT> &; 31 }; 32 template <class OptionsT> struct IteratorTraits<OptionsT, true> { 33 using value_type = const typename OptionsT::value_type; 34 using pointer = typename OptionsT::const_pointer; 35 using reference = typename OptionsT::const_reference; 36 using node_pointer = const ilist_node_impl<OptionsT> *; 37 using node_reference = const ilist_node_impl<OptionsT> &; 38 }; 39 40 template <bool IsReverse> struct IteratorHelper; 41 template <> struct IteratorHelper<false> : ilist_detail::NodeAccess { 42 using Access = ilist_detail::NodeAccess; 43 44 template <class T> static void increment(T *&I) { I = Access::getNext(*I); } 45 template <class T> static void decrement(T *&I) { I = Access::getPrev(*I); } 46 }; 47 template <> struct IteratorHelper<true> : ilist_detail::NodeAccess { 48 using Access = ilist_detail::NodeAccess; 49 50 template <class T> static void increment(T *&I) { I = Access::getPrev(*I); } 51 template <class T> static void decrement(T *&I) { I = Access::getNext(*I); } 52 }; 53 54 } // end namespace ilist_detail 55 56 /// Iterator for intrusive lists based on ilist_node. 57 template <class OptionsT, bool IsReverse, bool IsConst> 58 class ilist_iterator : ilist_detail::SpecificNodeAccess<OptionsT> { 59 friend ilist_iterator<OptionsT, IsReverse, !IsConst>; 60 friend ilist_iterator<OptionsT, !IsReverse, IsConst>; 61 friend ilist_iterator<OptionsT, !IsReverse, !IsConst>; 62 63 using Traits = ilist_detail::IteratorTraits<OptionsT, IsConst>; 64 using Access = ilist_detail::SpecificNodeAccess<OptionsT>; 65 66 public: 67 using value_type = typename Traits::value_type; 68 using pointer = typename Traits::pointer; 69 using reference = typename Traits::reference; 70 using difference_type = ptrdiff_t; 71 using iterator_category = std::bidirectional_iterator_tag; 72 using const_pointer = typename OptionsT::const_pointer; 73 using const_reference = typename OptionsT::const_reference; 74 75 private: 76 using node_pointer = typename Traits::node_pointer; 77 using node_reference = typename Traits::node_reference; 78 79 node_pointer NodePtr = nullptr; 80 81 public: 82 /// Create from an ilist_node. 83 explicit ilist_iterator(node_reference N) : NodePtr(&N) {} 84 85 explicit ilist_iterator(pointer NP) : NodePtr(Access::getNodePtr(NP)) {} 86 explicit ilist_iterator(reference NR) : NodePtr(Access::getNodePtr(&NR)) {} 87 ilist_iterator() = default; 88 89 // This is templated so that we can allow constructing a const iterator from 90 // a nonconst iterator... 91 template <bool RHSIsConst> 92 ilist_iterator( 93 const ilist_iterator<OptionsT, IsReverse, RHSIsConst> &RHS, 94 typename std::enable_if<IsConst || !RHSIsConst, void *>::type = nullptr) 95 : NodePtr(RHS.NodePtr) {} 96 97 // This is templated so that we can allow assigning to a const iterator from 98 // a nonconst iterator... 99 template <bool RHSIsConst> 100 typename std::enable_if<IsConst || !RHSIsConst, ilist_iterator &>::type 101 operator=(const ilist_iterator<OptionsT, IsReverse, RHSIsConst> &RHS) { 102 NodePtr = RHS.NodePtr; 103 return *this; 104 } 105 106 /// Explicit conversion between forward/reverse iterators. 107 /// 108 /// Translate between forward and reverse iterators without changing range 109 /// boundaries. The resulting iterator will dereference (and have a handle) 110 /// to the previous node, which is somewhat unexpected; but converting the 111 /// two endpoints in a range will give the same range in reverse. 112 /// 113 /// This matches std::reverse_iterator conversions. 114 explicit ilist_iterator( 115 const ilist_iterator<OptionsT, !IsReverse, IsConst> &RHS) 116 : ilist_iterator(++RHS.getReverse()) {} 117 118 /// Get a reverse iterator to the same node. 119 /// 120 /// Gives a reverse iterator that will dereference (and have a handle) to the 121 /// same node. Converting the endpoint iterators in a range will give a 122 /// different range; for range operations, use the explicit conversions. 123 ilist_iterator<OptionsT, !IsReverse, IsConst> getReverse() const { 124 if (NodePtr) 125 return ilist_iterator<OptionsT, !IsReverse, IsConst>(*NodePtr); 126 return ilist_iterator<OptionsT, !IsReverse, IsConst>(); 127 } 128 129 /// Const-cast. 130 ilist_iterator<OptionsT, IsReverse, false> getNonConst() const { 131 if (NodePtr) 132 return ilist_iterator<OptionsT, IsReverse, false>( 133 const_cast<typename ilist_iterator<OptionsT, IsReverse, 134 false>::node_reference>(*NodePtr)); 135 return ilist_iterator<OptionsT, IsReverse, false>(); 136 } 137 138 // Accessors... 139 reference operator*() const { 140 assert(!NodePtr->isKnownSentinel()); 141 return *Access::getValuePtr(NodePtr); 142 } 143 pointer operator->() const { return &operator*(); } 144 145 // Comparison operators 146 friend bool operator==(const ilist_iterator &LHS, const ilist_iterator &RHS) { 147 return LHS.NodePtr == RHS.NodePtr; 148 } 149 friend bool operator!=(const ilist_iterator &LHS, const ilist_iterator &RHS) { 150 return LHS.NodePtr != RHS.NodePtr; 151 } 152 153 // Increment and decrement operators... 154 ilist_iterator &operator--() { 155 NodePtr = IsReverse ? NodePtr->getNext() : NodePtr->getPrev(); 156 return *this; 157 } 158 ilist_iterator &operator++() { 159 NodePtr = IsReverse ? NodePtr->getPrev() : NodePtr->getNext(); 160 return *this; 161 } 162 ilist_iterator operator--(int) { 163 ilist_iterator tmp = *this; 164 --*this; 165 return tmp; 166 } 167 ilist_iterator operator++(int) { 168 ilist_iterator tmp = *this; 169 ++*this; 170 return tmp; 171 } 172 173 /// Get the underlying ilist_node. 174 node_pointer getNodePtr() const { return static_cast<node_pointer>(NodePtr); } 175 176 /// Check for end. Only valid if ilist_sentinel_tracking<true>. 177 bool isEnd() const { return NodePtr ? NodePtr->isSentinel() : false; } 178 }; 179 180 template <typename From> struct simplify_type; 181 182 /// Allow ilist_iterators to convert into pointers to a node automatically when 183 /// used by the dyn_cast, cast, isa mechanisms... 184 /// 185 /// FIXME: remove this, since there is no implicit conversion to NodeTy. 186 template <class OptionsT, bool IsConst> 187 struct simplify_type<ilist_iterator<OptionsT, false, IsConst>> { 188 using iterator = ilist_iterator<OptionsT, false, IsConst>; 189 using SimpleType = typename iterator::pointer; 190 191 static SimpleType getSimplifiedValue(const iterator &Node) { return &*Node; } 192 }; 193 template <class OptionsT, bool IsConst> 194 struct simplify_type<const ilist_iterator<OptionsT, false, IsConst>> 195 : simplify_type<ilist_iterator<OptionsT, false, IsConst>> {}; 196 197 } // end namespace llvm 198 199 #endif // LLVM_ADT_ILIST_ITERATOR_H 200
