Branch data Line data Source code
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 : 969884750 : iterator_range (const T &begin, const T &end)
32 : 775341524 : : m_begin (begin), m_end (end) {}
33 : :
34 : : T begin () const { return m_begin; }
35 : : T end () const { return m_end; }
36 : :
37 : 2320054 : 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 : 599326132 : explicit derived_iterator (Ts... args)
63 : : : m_base (std::forward<Ts> (args)...) {}
64 : :
65 : 777682487 : derived_iterator &operator++ () { ++m_base; return *this; }
66 : : derived_iterator operator++ (int);
67 : :
68 : 791676604 : 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 : 20321310 : const_derived_container () = default;
116 : :
117 : : template<typename... Ts>
118 : 818954447 : explicit const_derived_container (Ts... args)
119 : 722313242 : : BaseCT (std::forward<Ts> (args)...) {}
120 : :
121 : 509046187 : const_iterator begin () const { return const_iterator (BaseCT::begin ()); }
122 : 599326132 : const_iterator end () const { return const_iterator (BaseCT::end ()); }
123 : :
124 : : T front () const { return static_cast<T> (BaseCT::front ()); }
125 : 98075820 : 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 : 61253310 : const_derived_container<T, BaseCT>::operator[] (unsigned int i) const
132 : : {
133 : 97204284 : 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 : 231195758 : 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 : 115416748 : wrapper_iterator<T, StoredT>::operator!= (const wrapper_iterator &other) const
168 : : {
169 : 115416748 : 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 : 231195758 : 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 : 324458671 : list_iterator<T, Next>::operator++ ()
189 : : {
190 : 530655941 : this->m_contents = (this->m_contents->*Next) ();
191 : 184419870 : 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
|
