1 // Iterator-related utilities.
2 // Copyright (C) 2002-2023 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 #endif