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.
24template<typename T>
25struct iterator_range
26{
27public:
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
39private:
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.
53template<typename T, typename BaseIT>
54class derived_iterator
55{
56public:
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
74protected:
75 BaseIT m_base;
76};
77
78template<typename T, typename BaseIT>
79inline derived_iterator<T, BaseIT>
80derived_iterator<T, BaseIT>::operator++ (int)
81{
82 derived_iterator ret = *this;
83 ++m_base;
84 return ret;
85}
86
87template<typename T, typename BaseIT>
88inline bool
89derived_iterator<T, BaseIT>::operator== (const derived_iterator &other) const
90{
91 return m_base == other.m_base;
92}
93
94template<typename T, typename BaseIT>
95inline bool
96derived_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.
106template<typename T, typename BaseCT>
107class const_derived_container : public BaseCT
108{
109 using base_const_iterator = typename BaseCT::const_iterator;
110
111public:
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
129template<typename T, typename BaseCT>
130inline T
131const_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--.
139template<typename T, typename StoredT = T>
140class wrapper_iterator
141{
142public:
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
154protected:
155 StoredT m_contents;
156};
157
158template<typename T, typename StoredT>
159inline bool
160wrapper_iterator<T, StoredT>::operator== (const wrapper_iterator &other) const
161{
162 return m_contents == other.m_contents;
163}
164
165template<typename T, typename StoredT>
166inline bool
167wrapper_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) ().
174template<typename T, T *(T::*Next) () const>
175class list_iterator : public wrapper_iterator<T *>
176{
177private:
178 using parent = wrapper_iterator<T *>;
179
180public:
181 using parent::parent;
182 list_iterator &operator++ ();
183 list_iterator operator++ (int);
184};
185
186template<typename T, T *(T::*Next) () const>
187inline list_iterator<T, Next> &
188list_iterator<T, Next>::operator++ ()
189{
190 this->m_contents = (this->m_contents->*Next) ();
191 return *this;
192}
193
194template<typename T, T *(T::*Next) () const>
195inline list_iterator<T, Next>
196list_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

source code of gcc/iterator-utils.h