1 // Iterator-related utilities. 2 // Copyright (C) 2002-2022 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; iterator_rangeiterator_range31 iterator_range (const T &begin, const T &end) 32 : m_begin (begin), m_end (end) {} 33 beginiterator_range34 T begin () const { return m_begin; } enditerator_range35 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> derived_iterator(Ts...args)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> const_derived_container(Ts...args)118 explicit const_derived_container (Ts... args) 119 : BaseCT (std::forward<Ts> (args)...) {} 120 begin()121 const_iterator begin () const { return const_iterator (BaseCT::begin ()); } end()122 const_iterator end () const { return const_iterator (BaseCT::end ()); } 123 front()124 T front () const { return static_cast<T> (BaseCT::front ()); } back()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> wrapper_iterator(Ts...args)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 #endif 204