1 //===- llvm/ADT/ilist_iterator.h - Intrusive List Iterator -------*- C++ -*-==//
3 // The LLVM Compiler Infrastructure
5 // This file is distributed under the University of Illinois Open Source
6 // License. See LICENSE.TXT for details.
8 //===----------------------------------------------------------------------===//
10 #ifndef LLVM_ADT_ILIST_ITERATOR_H
11 #define LLVM_ADT_ILIST_ITERATOR_H
13 #include "llvm/ADT/ilist_node.h"
17 #include <type_traits>
21 namespace ilist_detail {
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;
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;
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); }
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); }
52 } // end namespace ilist_detail
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>;
61 typedef ilist_detail::IteratorTraits<OptionsT, IsConst> Traits;
62 typedef ilist_detail::SpecificNodeAccess<OptionsT> Access;
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;
71 typedef typename OptionsT::const_pointer const_pointer;
72 typedef typename OptionsT::const_reference const_reference;
75 typedef typename Traits::node_pointer node_pointer;
76 typedef typename Traits::node_reference node_reference;
81 /// Create from an ilist_node.
82 explicit ilist_iterator(node_reference N) : NodePtr(&N) {}
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) {}
88 // This is templated so that we can allow constructing a const iterator from
89 // a nonconst iterator...
90 template <bool RHSIsConst>
92 const ilist_iterator<OptionsT, IsReverse, RHSIsConst> &RHS,
93 typename std::enable_if<IsConst || !RHSIsConst, void *>::type = nullptr)
94 : NodePtr(RHS.NodePtr) {}
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;
105 /// Explicit conversion between forward/reverse iterators.
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.
112 /// This matches std::reverse_iterator conversions.
113 explicit ilist_iterator(
114 const ilist_iterator<OptionsT, !IsReverse, IsConst> &RHS)
115 : ilist_iterator(++RHS.getReverse()) {}
117 /// Get a reverse iterator to the same node.
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 {
124 return ilist_iterator<OptionsT, !IsReverse, IsConst>(*NodePtr);
125 return ilist_iterator<OptionsT, !IsReverse, IsConst>();
129 ilist_iterator<OptionsT, IsReverse, false> getNonConst() const {
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>();
138 reference operator*() const {
139 assert(!NodePtr->isKnownSentinel());
140 return *Access::getValuePtr(NodePtr);
142 pointer operator->() const { return &operator*(); }
144 // Comparison operators
145 friend bool operator==(const ilist_iterator &LHS, const ilist_iterator &RHS) {
146 return LHS.NodePtr == RHS.NodePtr;
148 friend bool operator!=(const ilist_iterator &LHS, const ilist_iterator &RHS) {
149 return LHS.NodePtr != RHS.NodePtr;
152 // Increment and decrement operators...
153 ilist_iterator &operator--() {
154 NodePtr = IsReverse ? NodePtr->getNext() : NodePtr->getPrev();
157 ilist_iterator &operator++() {
158 NodePtr = IsReverse ? NodePtr->getPrev() : NodePtr->getNext();
161 ilist_iterator operator--(int) {
162 ilist_iterator tmp = *this;
166 ilist_iterator operator++(int) {
167 ilist_iterator tmp = *this;
172 /// Get the underlying ilist_node.
173 node_pointer getNodePtr() const { return static_cast<node_pointer>(NodePtr); }
175 /// Check for end. Only valid if ilist_sentinel_tracking<true>.
176 bool isEnd() const { return NodePtr ? NodePtr->isSentinel() : false; }
179 template <typename From> struct simplify_type;
181 /// Allow ilist_iterators to convert into pointers to a node automatically when
182 /// used by the dyn_cast, cast, isa mechanisms...
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 typedef ilist_iterator<OptionsT, false, IsConst> iterator;
188 typedef typename iterator::pointer SimpleType;
190 static SimpleType getSimplifiedValue(const iterator &Node) { return &*Node; }
192 template <class OptionsT, bool IsConst>
193 struct simplify_type<const ilist_iterator<OptionsT, false, IsConst>>
194 : simplify_type<ilist_iterator<OptionsT, false, IsConst>> {};
196 } // end namespace llvm
198 #endif // LLVM_ADT_ILIST_ITERATOR_H