Line data Source code
1 : //===- iterator.h - Utilities for using and defining iterators --*- C++ -*-===//
2 : //
3 : // The LLVM Compiler Infrastructure
4 : //
5 : // This file is distributed under the University of Illinois Open Source
6 : // License. See LICENSE.TXT for details.
7 : //
8 : //===----------------------------------------------------------------------===//
9 :
10 : #ifndef LLVM_ADT_ITERATOR_H
11 : #define LLVM_ADT_ITERATOR_H
12 :
13 : #include <cstddef>
14 : #include <iterator>
15 :
16 : namespace llvm {
17 :
18 : /// \brief CRTP base class which implements the entire standard iterator facade
19 : /// in terms of a minimal subset of the interface.
20 : ///
21 : /// Use this when it is reasonable to implement most of the iterator
22 : /// functionality in terms of a core subset. If you need special behavior or
23 : /// there are performance implications for this, you may want to override the
24 : /// relevant members instead.
25 : ///
26 : /// Note, one abstraction that this does *not* provide is implementing
27 : /// subtraction in terms of addition by negating the difference. Negation isn't
28 : /// always information preserving, and I can see very reasonable iterator
29 : /// designs where this doesn't work well. It doesn't really force much added
30 : /// boilerplate anyways.
31 : ///
32 : /// Another abstraction that this doesn't provide is implementing increment in
33 : /// terms of addition of one. These aren't equivalent for all iterator
34 : /// categories, and respecting that adds a lot of complexity for little gain.
35 : template <typename DerivedT, typename IteratorCategoryT, typename T,
36 : typename DifferenceTypeT = std::ptrdiff_t, typename PointerT = T *,
37 : typename ReferenceT = T &>
38 : class iterator_facade_base
39 : : public std::iterator<IteratorCategoryT, T, DifferenceTypeT, PointerT,
40 : ReferenceT> {
41 : protected:
42 : enum {
43 : IsRandomAccess =
44 : std::is_base_of<std::random_access_iterator_tag, IteratorCategoryT>::value,
45 : IsBidirectional =
46 : std::is_base_of<std::bidirectional_iterator_tag, IteratorCategoryT>::value,
47 : };
48 :
49 : public:
50 : DerivedT operator+(DifferenceTypeT n) const {
51 : static_assert(
52 : IsRandomAccess,
53 : "The '+' operator is only defined for random access iterators.");
54 : DerivedT tmp = *static_cast<const DerivedT *>(this);
55 : tmp += n;
56 : return tmp;
57 : }
58 : friend DerivedT operator+(DifferenceTypeT n, const DerivedT &i) {
59 : static_assert(
60 : IsRandomAccess,
61 : "The '+' operator is only defined for random access iterators.");
62 : return i + n;
63 : }
64 : DerivedT operator-(DifferenceTypeT n) const {
65 : static_assert(
66 : IsRandomAccess,
67 : "The '-' operator is only defined for random access iterators.");
68 : DerivedT tmp = *static_cast<const DerivedT *>(this);
69 : tmp -= n;
70 : return tmp;
71 : }
72 :
73 : DerivedT &operator++() {
74 : return static_cast<DerivedT *>(this)->operator+=(1);
75 : }
76 : DerivedT operator++(int) {
77 : DerivedT tmp = *static_cast<DerivedT *>(this);
78 : ++*static_cast<DerivedT *>(this);
79 : return tmp;
80 : }
81 : DerivedT &operator--() {
82 : static_assert(
83 : IsBidirectional,
84 : "The decrement operator is only defined for bidirectional iterators.");
85 : return static_cast<DerivedT *>(this)->operator-=(1);
86 : }
87 : DerivedT operator--(int) {
88 : static_assert(
89 : IsBidirectional,
90 : "The decrement operator is only defined for bidirectional iterators.");
91 : DerivedT tmp = *static_cast<DerivedT *>(this);
92 : --*static_cast<DerivedT *>(this);
93 : return tmp;
94 : }
95 :
96 : bool operator!=(const DerivedT &RHS) const {
97 0 : return !static_cast<const DerivedT *>(this)->operator==(RHS);
98 : }
99 :
100 : bool operator>(const DerivedT &RHS) const {
101 : static_assert(
102 : IsRandomAccess,
103 : "Relational operators are only defined for random access iterators.");
104 : return !static_cast<const DerivedT *>(this)->operator<(RHS) &&
105 : !static_cast<const DerivedT *>(this)->operator==(RHS);
106 : }
107 : bool operator<=(const DerivedT &RHS) const {
108 : static_assert(
109 : IsRandomAccess,
110 : "Relational operators are only defined for random access iterators.");
111 : return !static_cast<const DerivedT *>(this)->operator>(RHS);
112 : }
113 : bool operator>=(const DerivedT &RHS) const {
114 : static_assert(
115 : IsRandomAccess,
116 : "Relational operators are only defined for random access iterators.");
117 : return !static_cast<const DerivedT *>(this)->operator<(RHS);
118 : }
119 :
120 : PointerT operator->() const {
121 : return &static_cast<const DerivedT *>(this)->operator*();
122 : }
123 : ReferenceT operator[](DifferenceTypeT n) const {
124 : static_assert(IsRandomAccess,
125 : "Subscripting is only defined for random access iterators.");
126 : return *static_cast<const DerivedT *>(this)->operator+(n);
127 : }
128 : };
129 :
130 : /// \brief CRTP base class for adapting an iterator to a different type.
131 : ///
132 : /// This class can be used through CRTP to adapt one iterator into another.
133 : /// Typically this is done through providing in the derived class a custom \c
134 : /// operator* implementation. Other methods can be overridden as well.
135 : template <
136 : typename DerivedT, typename WrappedIteratorT,
137 : typename IteratorCategoryT =
138 : typename std::iterator_traits<WrappedIteratorT>::iterator_category,
139 : typename T = typename std::iterator_traits<WrappedIteratorT>::value_type,
140 : typename DifferenceTypeT =
141 : typename std::iterator_traits<WrappedIteratorT>::difference_type,
142 : typename PointerT = T *, typename ReferenceT = T &,
143 : // Don't provide these, they are mostly to act as aliases below.
144 : typename WrappedTraitsT = std::iterator_traits<WrappedIteratorT>>
145 : class iterator_adaptor_base
146 : : public iterator_facade_base<DerivedT, IteratorCategoryT, T,
147 : DifferenceTypeT, PointerT, ReferenceT> {
148 : typedef typename iterator_adaptor_base::iterator_facade_base BaseT;
149 :
150 : protected:
151 : WrappedIteratorT I;
152 :
153 : iterator_adaptor_base() = default;
154 :
155 : template <typename U>
156 : explicit iterator_adaptor_base(
157 : U &&u,
158 : typename std::enable_if<
159 : !std::is_base_of<typename std::remove_cv<
160 : typename std::remove_reference<U>::type>::type,
161 : DerivedT>::value,
162 : int>::type = 0)
163 0 : : I(std::forward<U &&>(u)) {}
164 :
165 : const WrappedIteratorT &wrapped() const { return I; }
166 :
167 : public:
168 : typedef DifferenceTypeT difference_type;
169 :
170 : DerivedT &operator+=(difference_type n) {
171 : static_assert(
172 : BaseT::IsRandomAccess,
173 : "The '+=' operator is only defined for random access iterators.");
174 : I += n;
175 : return *static_cast<DerivedT *>(this);
176 : }
177 : DerivedT &operator-=(difference_type n) {
178 : static_assert(
179 : BaseT::IsRandomAccess,
180 : "The '-=' operator is only defined for random access iterators.");
181 : I -= n;
182 : return *static_cast<DerivedT *>(this);
183 : }
184 : using BaseT::operator-;
185 : difference_type operator-(const DerivedT &RHS) const {
186 : static_assert(
187 : BaseT::IsRandomAccess,
188 : "The '-' operator is only defined for random access iterators.");
189 : return I - RHS.I;
190 : }
191 :
192 : // We have to explicitly provide ++ and -- rather than letting the facade
193 : // forward to += because WrappedIteratorT might not support +=.
194 : using BaseT::operator++;
195 : DerivedT &operator++() {
196 0 : ++I;
197 0 : return *static_cast<DerivedT *>(this);
198 : }
199 : using BaseT::operator--;
200 : DerivedT &operator--() {
201 : static_assert(
202 : BaseT::IsBidirectional,
203 : "The decrement operator is only defined for bidirectional iterators.");
204 : --I;
205 : return *static_cast<DerivedT *>(this);
206 : }
207 :
208 0 : bool operator==(const DerivedT &RHS) const { return I == RHS.I; }
209 : bool operator<(const DerivedT &RHS) const {
210 : static_assert(
211 : BaseT::IsRandomAccess,
212 : "Relational operators are only defined for random access iterators.");
213 : return I < RHS.I;
214 : }
215 :
216 : ReferenceT operator*() const { return *I; }
217 : };
218 :
219 : /// \brief An iterator type that allows iterating over the pointees via some
220 : /// other iterator.
221 : ///
222 : /// The typical usage of this is to expose a type that iterates over Ts, but
223 : /// which is implemented with some iterator over T*s:
224 : ///
225 : /// \code
226 : /// typedef pointee_iterator<SmallVectorImpl<T *>::iterator> iterator;
227 : /// \endcode
228 : template <typename WrappedIteratorT,
229 : typename T = typename std::remove_reference<
230 : decltype(**std::declval<WrappedIteratorT>())>::type>
231 : struct pointee_iterator
232 : : iterator_adaptor_base<
233 : pointee_iterator<WrappedIteratorT>, WrappedIteratorT,
234 : typename std::iterator_traits<WrappedIteratorT>::iterator_category,
235 : T> {
236 : pointee_iterator() = default;
237 : template <typename U>
238 : pointee_iterator(U &&u)
239 0 : : pointee_iterator::iterator_adaptor_base(std::forward<U &&>(u)) {}
240 :
241 0 : T &operator*() const { return **this->I; }
242 : };
243 :
244 : }
245 :
246 : #endif
|
