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  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};
32template <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
40template <bool IsReverse> struct IteratorHelper;
41template <> 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};
46template <> 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.
55template <class OptionsT, bool IsReverse, bool IsConst>
56class 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
64public:
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
74private:
75  typedef typename Traits::node_pointer node_pointer;
76  typedef typename Traits::node_reference node_reference;
77
78  node_pointer NodePtr;
79
80public:
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
166template <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.
172template <class OptionsT, bool IsConst>
173struct 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};
179template <class OptionsT, bool IsConst>
180struct 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