1//===- llvm/ADT/ilist_iterator.h - Intrusive List Iterator ------*- C++ -*-===//
2//
3// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
4// See https://llvm.org/LICENSE.txt for license information.
5// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
6//
7//===----------------------------------------------------------------------===//
8
9#ifndef LLVM_ADT_ILIST_ITERATOR_H
10#define LLVM_ADT_ILIST_ITERATOR_H
11
12#include "llvm/ADT/ilist_node.h"
13#include <cassert>
14#include <cstddef>
15#include <iterator>
16#include <type_traits>
17
18namespace llvm {
19
20namespace ilist_detail {
21
22/// Find const-correct node types.
23template <class OptionsT, bool IsConst> struct IteratorTraits;
24template <class OptionsT> struct IteratorTraits<OptionsT, false> {
25  using value_type = typename OptionsT::value_type;
26  using pointer = typename OptionsT::pointer;
27  using reference = typename OptionsT::reference;
28  using node_pointer = ilist_node_impl<OptionsT> *;
29  using node_reference = ilist_node_impl<OptionsT> &;
30};
31template <class OptionsT> struct IteratorTraits<OptionsT, true> {
32  using value_type = const typename OptionsT::value_type;
33  using pointer = typename OptionsT::const_pointer;
34  using reference = typename OptionsT::const_reference;
35  using node_pointer = const ilist_node_impl<OptionsT> *;
36  using node_reference = const ilist_node_impl<OptionsT> &;
37};
38
39template <bool IsReverse> struct IteratorHelper;
40template <> struct IteratorHelper<false> : ilist_detail::NodeAccess {
41  using Access = ilist_detail::NodeAccess;
42
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  using Access = ilist_detail::NodeAccess;
48
49  template <class T> static void increment(T *&I) { I = Access::getPrev(*I); }
50  template <class T> static void decrement(T *&I) { I = Access::getNext(*I); }
51};
52
53} // end namespace ilist_detail
54
55/// Iterator for intrusive lists  based on ilist_node.
56template <class OptionsT, bool IsReverse, bool IsConst>
57class ilist_iterator : ilist_detail::SpecificNodeAccess<OptionsT> {
58  friend ilist_iterator<OptionsT, IsReverse, !IsConst>;
59  friend ilist_iterator<OptionsT, !IsReverse, IsConst>;
60  friend ilist_iterator<OptionsT, !IsReverse, !IsConst>;
61
62  using Traits = ilist_detail::IteratorTraits<OptionsT, IsConst>;
63  using Access = ilist_detail::SpecificNodeAccess<OptionsT>;
64
65public:
66  using value_type = typename Traits::value_type;
67  using pointer = typename Traits::pointer;
68  using reference = typename Traits::reference;
69  using difference_type = ptrdiff_t;
70  using iterator_category = std::bidirectional_iterator_tag;
71  using const_pointer = typename OptionsT::const_pointer;
72  using const_reference = typename OptionsT::const_reference;
73
74private:
75  using node_pointer = typename Traits::node_pointer;
76  using node_reference = typename Traits::node_reference;
77
78  node_pointer NodePtr = nullptr;
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() = default;
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  /// Explicit conversion between forward/reverse iterators.
106  ///
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.
111  ///
112  /// This matches std::reverse_iterator conversions.
113  explicit ilist_iterator(
114      const ilist_iterator<OptionsT, !IsReverse, IsConst> &RHS)
115      : ilist_iterator(++RHS.getReverse()) {}
116
117  /// Get a reverse iterator to the same node.
118  ///
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 {
123    if (NodePtr)
124      return ilist_iterator<OptionsT, !IsReverse, IsConst>(*NodePtr);
125    return ilist_iterator<OptionsT, !IsReverse, IsConst>();
126  }
127
128  /// Const-cast.
129  ilist_iterator<OptionsT, IsReverse, false> getNonConst() const {
130    if (NodePtr)
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>();
135  }
136
137  // Accessors...
138  reference operator*() const {
139    assert(!NodePtr->isKnownSentinel());
140    return *Access::getValuePtr(NodePtr);
141  }
142  pointer operator->() const { return &operator*(); }
143
144  // Comparison operators
145  friend bool operator==(const ilist_iterator &LHS, const ilist_iterator &RHS) {
146    return LHS.NodePtr == RHS.NodePtr;
147  }
148  friend bool operator!=(const ilist_iterator &LHS, const ilist_iterator &RHS) {
149    return LHS.NodePtr != RHS.NodePtr;
150  }
151
152  // Increment and decrement operators...
153  ilist_iterator &operator--() {
154    NodePtr = IsReverse ? NodePtr->getNext() : NodePtr->getPrev();
155    return *this;
156  }
157  ilist_iterator &operator++() {
158    NodePtr = IsReverse ? NodePtr->getPrev() : NodePtr->getNext();
159    return *this;
160  }
161  ilist_iterator operator--(int) {
162    ilist_iterator tmp = *this;
163    --*this;
164    return tmp;
165  }
166  ilist_iterator operator++(int) {
167    ilist_iterator tmp = *this;
168    ++*this;
169    return tmp;
170  }
171
172  /// Get the underlying ilist_node.
173  node_pointer getNodePtr() const { return static_cast<node_pointer>(NodePtr); }
174
175  /// Check for end.  Only valid if ilist_sentinel_tracking<true>.
176  bool isEnd() const { return NodePtr ? NodePtr->isSentinel() : false; }
177};
178
179template <typename From> struct simplify_type;
180
181/// Allow ilist_iterators to convert into pointers to a node automatically when
182/// used by the dyn_cast, cast, isa mechanisms...
183///
184/// FIXME: remove this, since there is no implicit conversion to NodeTy.
185template <class OptionsT, bool IsConst>
186struct simplify_type<ilist_iterator<OptionsT, false, IsConst>> {
187  using iterator = ilist_iterator<OptionsT, false, IsConst>;
188  using SimpleType = typename iterator::pointer;
189
190  static SimpleType getSimplifiedValue(const iterator &Node) { return &*Node; }
191};
192template <class OptionsT, bool IsConst>
193struct simplify_type<const ilist_iterator<OptionsT, false, IsConst>>
194    : simplify_type<ilist_iterator<OptionsT, false, IsConst>> {};
195
196} // end namespace llvm
197
198#endif // LLVM_ADT_ILIST_ITERATOR_H
199