contrib/llvm/include/llvm/ADT/ilist_iterator.h

   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