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 typedef typename OptionsT::value_type value_type; 27 typedef typename OptionsT::pointer pointer; 28 typedef typename OptionsT::reference reference; 29 typedef ilist_node_impl<OptionsT> *node_pointer; 30 typedef ilist_node_impl<OptionsT> &node_reference; 31 }; 32 template <class OptionsT> struct IteratorTraits<OptionsT, true> { 33 typedef const typename OptionsT::value_type value_type; 34 typedef typename OptionsT::const_pointer pointer; 35 typedef typename OptionsT::const_reference reference; 36 typedef const ilist_node_impl<OptionsT> *node_pointer; 37 typedef const ilist_node_impl<OptionsT> &node_reference; 38 }; 39 40 template <bool IsReverse> struct IteratorHelper; 41 template <> struct IteratorHelper<false> : ilist_detail::NodeAccess { 42 typedef ilist_detail::NodeAccess Access; 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 typedef ilist_detail::NodeAccess Access; 48 template <class T> static void increment(T *&I) { I = Access::getPrev(*I); } 49 template <class T> static void decrement(T *&I) { I = Access::getNext(*I); } 50 }; 51 52 } // end namespace ilist_detail 53 54 /// Iterator for intrusive lists based on ilist_node. 55 template <class OptionsT, bool IsReverse, bool IsConst> 56 class ilist_iterator : ilist_detail::SpecificNodeAccess<OptionsT> { 57 friend ilist_iterator<OptionsT, IsReverse, !IsConst>; 58 friend ilist_iterator<OptionsT, !IsReverse, IsConst>; 59 friend ilist_iterator<OptionsT, !IsReverse, !IsConst>; 60 61 typedef ilist_detail::IteratorTraits<OptionsT, IsConst> Traits; 62 typedef ilist_detail::SpecificNodeAccess<OptionsT> Access; 63 64 public: 65 typedef typename Traits::value_type value_type; 66 typedef typename Traits::pointer pointer; 67 typedef typename Traits::reference reference; 68 typedef ptrdiff_t difference_type; 69 typedef std::bidirectional_iterator_tag iterator_category; 70 71 typedef typename OptionsT::const_pointer const_pointer; 72 typedef typename OptionsT::const_reference const_reference; 73 74 private: 75 typedef typename Traits::node_pointer node_pointer; 76 typedef typename Traits::node_reference node_reference; 77 78 node_pointer NodePtr; 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() : NodePtr(nullptr) {} 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 /// Convert from an iterator to its reverse. 106 /// 107 /// TODO: Roll this into the implicit constructor once we're sure that no one 108 /// is relying on the std::reverse_iterator off-by-one semantics. 109 ilist_iterator<OptionsT, !IsReverse, IsConst> getReverse() const { 110 if (NodePtr) 111 return ilist_iterator<OptionsT, !IsReverse, IsConst>(*NodePtr); 112 return ilist_iterator<OptionsT, !IsReverse, IsConst>(); 113 } 114 115 /// Const-cast. 116 ilist_iterator<OptionsT, IsReverse, false> getNonConst() const { 117 if (NodePtr) 118 return ilist_iterator<OptionsT, IsReverse, false>( 119 const_cast<typename ilist_iterator<OptionsT, IsReverse, 120 false>::node_reference>(*NodePtr)); 121 return ilist_iterator<OptionsT, IsReverse, false>(); 122 } 123 124 // Accessors... 125 reference operator*() const { 126 assert(!NodePtr->isKnownSentinel()); 127 return *Access::getValuePtr(NodePtr); 128 } 129 pointer operator->() const { return &operator*(); } 130 131 // Comparison operators 132 friend bool operator==(const ilist_iterator &LHS, const ilist_iterator &RHS) { 133 return LHS.NodePtr == RHS.NodePtr; 134 } 135 friend bool operator!=(const ilist_iterator &LHS, const ilist_iterator &RHS) { 136 return LHS.NodePtr != RHS.NodePtr; 137 } 138 139 // Increment and decrement operators... 140 ilist_iterator &operator--() { 141 NodePtr = IsReverse ? NodePtr->getNext() : NodePtr->getPrev(); 142 return *this; 143 } 144 ilist_iterator &operator++() { 145 NodePtr = IsReverse ? NodePtr->getPrev() : NodePtr->getNext(); 146 return *this; 147 } 148 ilist_iterator operator--(int) { 149 ilist_iterator tmp = *this; 150 --*this; 151 return tmp; 152 } 153 ilist_iterator operator++(int) { 154 ilist_iterator tmp = *this; 155 ++*this; 156 return tmp; 157 } 158 159 /// Get the underlying ilist_node. 160 node_pointer getNodePtr() const { return static_cast<node_pointer>(NodePtr); } 161 162 /// Check for end. Only valid if ilist_sentinel_tracking<true>. 163 bool isEnd() const { return NodePtr ? NodePtr->isSentinel() : false; } 164 }; 165 166 template <typename From> struct simplify_type; 167 168 /// Allow ilist_iterators to convert into pointers to a node automatically when 169 /// used by the dyn_cast, cast, isa mechanisms... 170 /// 171 /// FIXME: remove this, since there is no implicit conversion to NodeTy. 172 template <class OptionsT, bool IsConst> 173 struct simplify_type<ilist_iterator<OptionsT, false, IsConst>> { 174 typedef ilist_iterator<OptionsT, false, IsConst> iterator; 175 typedef typename iterator::pointer SimpleType; 176 177 static SimpleType getSimplifiedValue(const iterator &Node) { return &*Node; } 178 }; 179 template <class OptionsT, bool IsConst> 180 struct simplify_type<const ilist_iterator<OptionsT, false, IsConst>> 181 : simplify_type<ilist_iterator<OptionsT, false, IsConst>> {}; 182 183 } // end namespace llvm 184 185 #endif // LLVM_ADT_ILIST_ITERATOR_H 186
