include/llvm/ADT/ilist_iterator.h

   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
  18 namespace llvm {
  19
  20 namespace ilist_detail {
  21
  22 /// Find const-correct node types.
  23 template <class OptionsT, bool IsConst> struct IteratorTraits;
  24 template <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 };
  31 template <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
  39 template <bool IsReverse> struct IteratorHelper;
  40 template <> 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 };
  46 template <> 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.
  56 template <class OptionsT, bool IsReverse, bool IsConst>
  57 class 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
  65 public:
  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
  74 private:
  75   using node_pointer = typename Traits::node_pointer;
  76   using node_reference = typename Traits::node_reference;
  77
  78   node_pointer NodePtr = nullptr;
  79
  80 public:
  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
 179 template <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.
 185 template <class OptionsT, bool IsConst>
 186 struct 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 };
 192 template <class OptionsT, bool IsConst>
 193 struct 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