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