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
19namespace llvm {
20
21namespace ilist_detail {
22
23/// Find const-correct node types.
24template <class OptionsT, bool IsConst> struct IteratorTraits;
25template <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};
32template <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
40template <bool IsReverse> struct IteratorHelper;
41template <> 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};
47template <> 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.
57template <class OptionsT, bool IsReverse, bool IsConst>
58class 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
66public:
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
75private:
76  using node_pointer = typename Traits::node_pointer;
77  using node_reference = typename Traits::node_reference;
78
79  node_pointer NodePtr = nullptr;
80
81public:
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
180template <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.
186template <class OptionsT, bool IsConst>
187struct 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};
193template <class OptionsT, bool IsConst>
194struct 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