Line data Source code
1 : // Iterator-related utilities.
2 : // Copyright (C) 2002-2026 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 1601873216 : iterator_range (const T &begin, const T &end)
32 1330741077 : : m_begin (begin), m_end (end) {}
33 :
34 : T begin () const { return m_begin; }
35 : T end () const { return m_end; }
36 :
37 2181179 : 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 906502394 : explicit derived_iterator (Ts... args)
63 : : m_base (std::forward<Ts> (args)...) {}
64 :
65 1094535802 : derived_iterator &operator++ () { ++m_base; return *this; }
66 : derived_iterator operator++ (int);
67 :
68 1113540645 : 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 25125558 : const_derived_container () = default;
116 :
117 : template<typename... Ts>
118 1202799177 : explicit const_derived_container (Ts... args)
119 1096903916 : : BaseCT (std::forward<Ts> (args)...) {}
120 :
121 906502394 : const_iterator begin () const { return const_iterator (BaseCT::begin ()); }
122 906502394 : const_iterator end () const { return const_iterator (BaseCT::end ()); }
123 :
124 : T front () const { return static_cast<T> (BaseCT::front ()); }
125 112268371 : 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 95338145 : const_derived_container<T, BaseCT>::operator[] (unsigned int i) const
132 : {
133 140469984 : 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 330160848 : 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 171182855 : wrapper_iterator<T, StoredT>::operator!= (const wrapper_iterator &other) const
168 : {
169 171182855 : 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 330160848 : 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 470788634 : list_iterator<T, Next>::operator++ ()
189 : {
190 751976674 : this->m_contents = (this->m_contents->*Next) ();
191 279787868 : 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
|
