gcc/iterator-utils.h

   1 // Iterator-related utilities.
   2 // Copyright (C) 2002-2024 Free Software Foundation, Inc.
   3 //
   4 // This file is part of GCC.
   5 //
   6 // GCC is free software; you can redistribute it and/or modify it under
   7 // the terms of the GNU General Public License as published by the Free
   8 // Software Foundation; either version 3, or (at your option) any later
   9 // version.
  10 //
  11 // GCC is distributed in the hope that it will be useful, but WITHOUT ANY
  12 // WARRANTY; without even the implied warranty of MERCHANTABILITY or
  13 // FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
  14 // for more details.
  15 //
  16 // You should have received a copy of the GNU General Public License
  17 // along with GCC; see the file COPYING3.  If not see
  18 // <http://www.gnu.org/licenses/>.
  19
  20 #ifndef GCC_ITERATOR_UTILS_H
  21 #define GCC_ITERATOR_UTILS_H 1
  22
  23 // A half-open [begin, end) range of iterators.
  24 template<typename T>
  25 struct iterator_range
  26 {
  27 public:
  28   using const_iterator = T;
  29
  30   iterator_range () = default;
  31   iterator_range (const T &begin, const T &end)
  32     : m_begin (begin), m_end (end) {}
  33
  34   T begin () const { return m_begin; }
  35   T end () const { return m_end; }
  36
  37   explicit operator bool () const { return m_begin != m_end; }
  38
  39 private:
  40   T m_begin;
  41   T m_end;
  42 };
  43
  44 // Provide an iterator like BaseIT, except that it yields values of type T,
  45 // which is derived from the type that BaseIT normally yields.
  46 //
  47 // The class doesn't inherit from BaseIT for two reasons:
  48 // - using inheritance would stop the class working with plain pointers
  49 // - not using inheritance increases type-safety for writable iterators
  50 //
  51 // Constructing this class from a BaseIT involves an assertion that all
  52 // contents really do have type T.  The constructor is therefore explicit.
  53 template<typename T, typename BaseIT>
  54 class derived_iterator
  55 {
  56 public:
  57   using value_type = T;
  58
  59   derived_iterator () = default;
  60
  61   template<typename... Ts>
  62   explicit derived_iterator (Ts... args)
  63     : m_base (std::forward<Ts> (args)...) {}
  64
  65   derived_iterator &operator++ () { ++m_base; return *this; }
  66   derived_iterator operator++ (int);
  67
  68   T operator* () const { return static_cast<T> (*m_base); }
  69   T *operator-> () const { return static_cast<T *> (m_base.operator-> ()); }
  70
  71   bool operator== (const derived_iterator &other) const;
  72   bool operator!= (const derived_iterator &other) const;
  73
  74 protected:
  75   BaseIT m_base;
  76 };
  77
  78 template<typename T, typename BaseIT>
  79 inline derived_iterator<T, BaseIT>
  80 derived_iterator<T, BaseIT>::operator++ (int)
  81 {
  82   derived_iterator ret = *this;
  83   ++m_base;
  84   return ret;
  85 }
  86
  87 template<typename T, typename BaseIT>
  88 inline bool
  89 derived_iterator<T, BaseIT>::operator== (const derived_iterator &other) const
  90 {
  91   return m_base == other.m_base;
  92 }
  93
  94 template<typename T, typename BaseIT>
  95 inline bool
  96 derived_iterator<T, BaseIT>::operator!= (const derived_iterator &other) const
  97 {
  98   return m_base != other.m_base;
  99 }
 100
 101 // Provide a constant view of a BaseCT in which every value is known to
 102 // have type T, which is derived from the type that BaseCT normally presents.
 103 //
 104 // Constructing this class from a BaseCT involves an assertion that all
 105 // contents really do have type T.  The constructor is therefore explicit.
 106 template<typename T, typename BaseCT>
 107 class const_derived_container : public BaseCT
 108 {
 109   using base_const_iterator = typename BaseCT::const_iterator;
 110
 111 public:
 112   using value_type = T;
 113   using const_iterator = derived_iterator<T, base_const_iterator>;
 114
 115   const_derived_container () = default;
 116
 117   template<typename... Ts>
 118   explicit const_derived_container (Ts... args)
 119     : BaseCT (std::forward<Ts> (args)...) {}
 120
 121   const_iterator begin () const { return const_iterator (BaseCT::begin ()); }
 122   const_iterator end () const { return const_iterator (BaseCT::end ()); }
 123
 124   T front () const { return static_cast<T> (BaseCT::front ()); }
 125   T back () const { return static_cast<T> (BaseCT::back ()); }
 126   T operator[] (unsigned int i) const;
 127 };
 128
 129 template<typename T, typename BaseCT>
 130 inline T
 131 const_derived_container<T, BaseCT>::operator[] (unsigned int i) const
 132 {
 133   return static_cast<T> (BaseCT::operator[] (i));
 134 }
 135
 136 // A base class for iterators whose contents consist of a StoredT and that
 137 // when dereferenced yield those StoredT contents as a T.  Derived classes
 138 // should implement at least operator++ or operator--.
 139 template<typename T, typename StoredT = T>
 140 class wrapper_iterator
 141 {
 142 public:
 143   using value_type = T;
 144
 145   wrapper_iterator () = default;
 146
 147   template<typename... Ts>
 148   wrapper_iterator (Ts... args) : m_contents (std::forward<Ts> (args)...) {}
 149
 150   T operator* () const { return static_cast<T> (m_contents); }
 151   bool operator== (const wrapper_iterator &) const;
 152   bool operator!= (const wrapper_iterator &) const;
 153
 154 protected:
 155   StoredT m_contents;
 156 };
 157
 158 template<typename T, typename StoredT>
 159 inline bool
 160 wrapper_iterator<T, StoredT>::operator== (const wrapper_iterator &other) const
 161 {
 162   return m_contents == other.m_contents;
 163 }
 164
 165 template<typename T, typename StoredT>
 166 inline bool
 167 wrapper_iterator<T, StoredT>::operator!= (const wrapper_iterator &other) const
 168 {
 169   return m_contents != other.m_contents;
 170 }
 171
 172 // A forward iterator for a linked list whose nodes are referenced using
 173 // type T.  Given a node "T N", the next element is given by (N->*Next) ().
 174 template<typename T, T *(T::*Next) () const>
 175 class list_iterator : public wrapper_iterator<T *>
 176 {
 177 private:
 178   using parent = wrapper_iterator<T *>;
 179
 180 public:
 181   using parent::parent;
 182   list_iterator &operator++ ();
 183   list_iterator operator++ (int);
 184 };
 185
 186 template<typename T, T *(T::*Next) () const>
 187 inline list_iterator<T, Next> &
 188 list_iterator<T, Next>::operator++ ()
 189 {
 190   this->m_contents = (this->m_contents->*Next) ();
 191   return *this;
 192 }
 193
 194 template<typename T, T *(T::*Next) () const>
 195 inline list_iterator<T, Next>
 196 list_iterator<T, Next>::operator++ (int)
 197 {
 198   list_iterator ret = *this;
 199   this->m_contents = (this->m_contents->*Next) ();
 200   return ret;
 201 }
 202
 203 // An iterator that pre-computes the next value if we haven't already got to the
 204 // end.  This is useful in cases where a standard iterator would get invalidated
 205 // (e.g. elements getting removed from a container) during the body of a loop.
 206 template<typename T>
 207 class safe_iterator
 208 {
 209   T m_current;
 210   const T m_end;
 211   T m_next;
 212
 213   T get_next ()
 214   {
 215     if (m_current != m_end)
 216       {
 217         // FIXME: we should use std::next here but that would mean having
 218         // #include <iterator> everywhere that iterator-utils.h is included.
 219         //
 220         // For now we just implement it directly.
 221         T iter = m_current;
 222         return ++iter;
 223       }
 224     return m_end;
 225   }
 226
 227   void advance ()
 228   {
 229     m_current = m_next;
 230     if (m_next != m_end)
 231       ++m_next;
 232   }
 233
 234 public:
 235   bool operator== (const safe_iterator &other) const
 236   {
 237     return m_current == other.m_current;
 238   }
 239
 240   bool operator!= (const safe_iterator &other) const
 241   {
 242     return m_current != other.m_current;
 243   }
 244
 245   typename T::value_type operator*() const { return *m_current; }
 246
 247   safe_iterator &operator++ ()
 248   {
 249     advance ();
 250     return *this;
 251   }
 252
 253   safe_iterator operator++ (int)
 254   {
 255     auto ret = *this;
 256     advance ();
 257     return ret;
 258   }
 259
 260   safe_iterator (T iter, T end)
 261     : m_current (iter), m_end (end), m_next (get_next ()) {}
 262 };
 263
 264 // Convert a container RANGE into a container of safe_iterators.
 265 template<typename Container>
 266 inline
 267 iterator_range<safe_iterator<typename Container::const_iterator>>
 268 iterate_safely (Container range)
 269 {
 270   return {
 271     { range.begin (), range.end () },
 272     { range.end (), range.end () }
 273   };
 274 }
 275
 276 #endif