1 // Safe iterator implementation -*- C++ -*-
2
3 // Copyright (C) 2011-2023 Free Software Foundation, Inc.
4 //
5 // This file is part of the GNU ISO C++ Library. This library is free
6 // software; you can redistribute it and/or modify it under the
7 // terms of the GNU General Public License as published by the
8 // Free Software Foundation; either version 3, or (at your option)
9 // any later version.
10
11 // This library is distributed in the hope that it will be useful,
12 // but WITHOUT ANY WARRANTY; without even the implied warranty of
13 // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
14 // GNU General Public License for more details.
15
16 // Under Section 7 of GPL version 3, you are granted additional
17 // permissions described in the GCC Runtime Library Exception, version
18 // 3.1, as published by the Free Software Foundation.
19
20 // You should have received a copy of the GNU General Public License and
21 // a copy of the GCC Runtime Library Exception along with this program;
22 // see the files COPYING3 and COPYING.RUNTIME respectively. If not, see
23 // <http://www.gnu.org/licenses/>.
24
25 /** @file debug/safe_local_iterator.h
26 * This file is a GNU debug extension to the Standard C++ Library.
27 */
28
29 #ifndef _GLIBCXX_DEBUG_SAFE_LOCAL_ITERATOR_H
30 #define _GLIBCXX_DEBUG_SAFE_LOCAL_ITERATOR_H 1
31
32 #include <debug/safe_unordered_base.h>
33
34 #define _GLIBCXX_DEBUG_VERIFY_OPERANDS(_Lhs, _Rhs) \
35 _GLIBCXX_DEBUG_VERIFY(!_Lhs._M_singular() && !_Rhs._M_singular() \
36 || (_Lhs._M_value_initialized() \
37 && _Rhs._M_value_initialized()), \
38 _M_message(__msg_iter_compare_bad) \
39 ._M_iterator(_Lhs, "lhs") \
40 ._M_iterator(_Rhs, "rhs")); \
41 _GLIBCXX_DEBUG_VERIFY(_Lhs._M_can_compare(_Rhs), \
42 _M_message(__msg_compare_different) \
43 ._M_iterator(_Lhs, "lhs") \
44 ._M_iterator(_Rhs, "rhs")); \
45 _GLIBCXX_DEBUG_VERIFY(_Lhs._M_in_same_bucket(_Rhs), \
46 _M_message(__msg_local_iter_compare_bad) \
47 ._M_iterator(_Lhs, "lhs") \
48 ._M_iterator(_Rhs, "rhs"))
49
50 namespace __gnu_debug
51 {
52 /** \brief Safe iterator wrapper.
53 *
54 * The class template %_Safe_local_iterator is a wrapper around an
55 * iterator that tracks the iterator's movement among sequences and
56 * checks that operations performed on the "safe" iterator are
57 * legal. In additional to the basic iterator operations (which are
58 * validated, and then passed to the underlying iterator),
59 * %_Safe_local_iterator has member functions for iterator invalidation,
60 * attaching/detaching the iterator from sequences, and querying
61 * the iterator's state.
62 */
63 template<typename _Iterator, typename _Sequence>
64 class _Safe_local_iterator
65 : private _Iterator
66 , public _Safe_local_iterator_base
67 {
68 typedef _Iterator _Iter_base;
69 typedef _Safe_local_iterator_base _Safe_base;
70
71 typedef typename _Sequence::size_type size_type;
72
73 typedef std::iterator_traits<_Iterator> _Traits;
74
75 typedef std::__are_same<
76 typename _Sequence::_Base::const_local_iterator,
77 _Iterator> _IsConstant;
78
79 typedef typename __gnu_cxx::__conditional_type<_IsConstant::__value,
80 typename _Sequence::_Base::local_iterator,
81 typename _Sequence::_Base::const_local_iterator>::__type
82 _OtherIterator;
83
84 typedef _Safe_local_iterator _Self;
85 typedef _Safe_local_iterator<_OtherIterator, _Sequence> _OtherSelf;
86
87 struct _Unchecked { };
88
89 _Safe_local_iterator(const _Safe_local_iterator& __x,
90 _Unchecked) noexcept
91 : _Iter_base(__x.base())
92 { _M_attach(__x._M_sequence); }
93
94 public:
95 typedef _Iterator iterator_type;
96 typedef typename _Traits::iterator_category iterator_category;
97 typedef typename _Traits::value_type value_type;
98 typedef typename _Traits::difference_type difference_type;
99 typedef typename _Traits::reference reference;
100 typedef typename _Traits::pointer pointer;
101
102 /// @post the iterator is singular and unattached
103 _Safe_local_iterator() noexcept : _Iter_base() { }
104
105 /**
106 * @brief Safe iterator construction from an unsafe iterator and
107 * its sequence.
108 *
109 * @pre @p seq is not NULL
110 * @post this is not singular
111 */
112 _Safe_local_iterator(_Iterator __i, const _Safe_sequence_base* __cont)
113 : _Iter_base(__i), _Safe_base(__cont, _S_constant())
114 { }
115
116 /**
117 * @brief Copy construction.
118 */
119 _Safe_local_iterator(const _Safe_local_iterator& __x) noexcept
120 : _Iter_base(__x.base())
121 {
122 // _GLIBCXX_RESOLVE_LIB_DEFECTS
123 // DR 408. Is vector<reverse_iterator<char*> > forbidden?
124 _GLIBCXX_DEBUG_VERIFY(!__x._M_singular()
125 || __x._M_value_initialized(),
126 _M_message(__msg_init_copy_singular)
127 ._M_iterator(*this, "this")
128 ._M_iterator(__x, "other"));
129 _M_attach(__x._M_sequence);
130 }
131
132 /**
133 * @brief Move construction.
134 * @post __x is singular and unattached
135 */
136 _Safe_local_iterator(_Safe_local_iterator&& __x) noexcept
137 : _Iter_base()
138 {
139 _GLIBCXX_DEBUG_VERIFY(!__x._M_singular()
140 || __x._M_value_initialized(),
141 _M_message(__msg_init_copy_singular)
142 ._M_iterator(*this, "this")
143 ._M_iterator(__x, "other"));
144 auto __cont = __x._M_sequence;
145 __x._M_detach();
146 std::swap(base(), __x.base());
147 _M_attach(__cont);
148 }
149
150 /**
151 * @brief Converting constructor from a mutable iterator to a
152 * constant iterator.
153 */
154 template<typename _MutableIterator>
155 _Safe_local_iterator(
156 const _Safe_local_iterator<_MutableIterator,
157 typename __gnu_cxx::__enable_if<_IsConstant::__value &&
158 std::__are_same<_MutableIterator, _OtherIterator>::__value,
159 _Sequence>::__type>& __x) noexcept
160 : _Iter_base(__x.base())
161 {
162 // _GLIBCXX_RESOLVE_LIB_DEFECTS
163 // DR 408. Is vector<reverse_iterator<char*> > forbidden?
164 _GLIBCXX_DEBUG_VERIFY(!__x._M_singular()
165 || __x._M_value_initialized(),
166 _M_message(__msg_init_const_singular)
167 ._M_iterator(*this, "this")
168 ._M_iterator(__x, "other"));
169 _M_attach(__x._M_sequence);
170 }
171
172 /**
173 * @brief Copy assignment.
174 */
175 _Safe_local_iterator&
176 operator=(const _Safe_local_iterator& __x)
177 {
178 // _GLIBCXX_RESOLVE_LIB_DEFECTS
179 // DR 408. Is vector<reverse_iterator<char*> > forbidden?
180 _GLIBCXX_DEBUG_VERIFY(!__x._M_singular()
181 || __x._M_value_initialized(),
182 _M_message(__msg_copy_singular)
183 ._M_iterator(*this, "this")
184 ._M_iterator(__x, "other"));
185
186 if (this->_M_sequence && this->_M_sequence == __x._M_sequence)
187 {
188 __gnu_cxx::__scoped_lock __l(this->_M_get_mutex());
189 base() = __x.base();
190 _M_version = __x._M_sequence->_M_version;
191 }
192 else
193 {
194 _M_detach();
195 base() = __x.base();
196 _M_attach(__x._M_sequence);
197 }
198
199 return *this;
200 }
201
202 /**
203 * @brief Move assignment.
204 * @post __x is singular and unattached
205 */
206 _Safe_local_iterator&
207 operator=(_Safe_local_iterator&& __x) noexcept
208 {
209 _GLIBCXX_DEBUG_VERIFY(!__x._M_singular()
210 || __x._M_value_initialized(),
211 _M_message(__msg_copy_singular)
212 ._M_iterator(*this, "this")
213 ._M_iterator(__x, "other"));
214
215 if (std::__addressof(__x) == this)
216 return *this;
217
218 if (this->_M_sequence && this->_M_sequence == __x._M_sequence)
219 {
220 __gnu_cxx::__scoped_lock __l(this->_M_get_mutex());
221 base() = __x.base();
222 _M_version = __x._M_sequence->_M_version;
223 }
224 else
225 {
226 _M_detach();
227 base() = __x.base();
228 _M_attach(__x._M_sequence);
229 }
230
231 __x._M_detach();
232 __x.base() = _Iterator();
233 return *this;
234 }
235
236 /**
237 * @brief Iterator dereference.
238 * @pre iterator is dereferenceable
239 */
240 reference
241 operator*() const
242 {
243 _GLIBCXX_DEBUG_VERIFY(this->_M_dereferenceable(),
244 _M_message(__msg_bad_deref)
245 ._M_iterator(*this, "this"));
246 return *base();
247 }
248
249 /**
250 * @brief Iterator dereference.
251 * @pre iterator is dereferenceable
252 */
253 pointer
254 operator->() const
255 {
256 _GLIBCXX_DEBUG_VERIFY(this->_M_dereferenceable(),
257 _M_message(__msg_bad_deref)
258 ._M_iterator(*this, "this"));
259 return base().operator->();
260 }
261
262 // ------ Input iterator requirements ------
263 /**
264 * @brief Iterator preincrement
265 * @pre iterator is incrementable
266 */
267 _Safe_local_iterator&
268 operator++()
269 {
270 _GLIBCXX_DEBUG_VERIFY(this->_M_incrementable(),
271 _M_message(__msg_bad_inc)
272 ._M_iterator(*this, "this"));
273 __gnu_cxx::__scoped_lock __l(this->_M_get_mutex());
274 ++base();
275 return *this;
276 }
277
278 /**
279 * @brief Iterator postincrement
280 * @pre iterator is incrementable
281 */
282 _Safe_local_iterator
283 operator++(int)
284 {
285 _GLIBCXX_DEBUG_VERIFY(this->_M_incrementable(),
286 _M_message(__msg_bad_inc)
287 ._M_iterator(*this, "this"));
288 _Safe_local_iterator __ret(*this, _Unchecked{});
289 ++*this;
290 return __ret;
291 }
292
293 // ------ Utilities ------
294
295 /// Determine if this is a constant iterator.
296 static constexpr bool
297 _S_constant()
298 { return _IsConstant::__value; }
299
300 /**
301 * @brief Return the underlying iterator
302 */
303 _Iterator&
304 base() noexcept { return *this; }
305
306 const _Iterator&
307 base() const noexcept { return *this; }
308
309 /**
310 * @brief Return the bucket
311 */
312 size_type
313 bucket() const { return base()._M_get_bucket(); }
314
315 /**
316 * @brief Conversion to underlying non-debug iterator to allow
317 * better interaction with non-debug containers.
318 */
319 operator _Iterator() const { return *this; }
320
321 /** Attach iterator to the given sequence. */
322 void
323 _M_attach(_Safe_sequence_base* __seq)
324 { _Safe_base::_M_attach(__seq, _S_constant()); }
325
326 /** Likewise, but not thread-safe. */
327 void
328 _M_attach_single(_Safe_sequence_base* __seq)
329 { _Safe_base::_M_attach_single(__seq, _S_constant()); }
330
331 /// Is the iterator dereferenceable?
332 bool
333 _M_dereferenceable() const
334 { return !this->_M_singular() && !_M_is_end(); }
335
336 /// Is the iterator incrementable?
337 bool
338 _M_incrementable() const
339 { return !this->_M_singular() && !_M_is_end(); }
340
341 /// Is the iterator value-initialized?
342 bool
343 _M_value_initialized() const
344 { return _M_version == 0 && base() == _Iter_base{}; }
345
346 // Is the iterator range [*this, __rhs) valid?
347 bool
348 _M_valid_range(const _Safe_local_iterator& __rhs,
349 std::pair<difference_type,
350 _Distance_precision>& __dist_info) const;
351
352 // Get distance to __rhs.
353 typename _Distance_traits<_Iterator>::__type
354 _M_get_distance_to(const _Safe_local_iterator& __rhs) const;
355
356 // The sequence this iterator references.
357 typename __gnu_cxx::__conditional_type<
358 _IsConstant::__value, const _Sequence*, _Sequence*>::__type
359 _M_get_sequence() const
360 { return static_cast<_Sequence*>(_M_sequence); }
361
362 /// Is this iterator equal to the sequence's begin(bucket) iterator?
363 bool _M_is_begin() const
364 { return base() == _M_get_sequence()->_M_base().begin(bucket()); }
365
366 /// Is this iterator equal to the sequence's end(bucket) iterator?
367 bool _M_is_end() const
368 { return base() == _M_get_sequence()->_M_base().end(bucket()); }
369
370 /// Is this iterator part of the same bucket as the other one?
371 template<typename _Other>
372 bool
373 _M_in_same_bucket(const _Safe_local_iterator<_Other,
374 _Sequence>& __other) const
375 { return bucket() == __other.bucket(); }
376
377 friend inline bool
378 operator==(const _Self& __lhs, const _OtherSelf& __rhs) noexcept
379 {
380 _GLIBCXX_DEBUG_VERIFY_OPERANDS(__lhs, __rhs);
381 return __lhs.base() == __rhs.base();
382 }
383
384 friend inline bool
385 operator==(const _Self& __lhs, const _Self& __rhs) noexcept
386 {
387 _GLIBCXX_DEBUG_VERIFY_OPERANDS(__lhs, __rhs);
388 return __lhs.base() == __rhs.base();
389 }
390
391 friend inline bool
392 operator!=(const _Self& __lhs, const _OtherSelf& __rhs) noexcept
393 {
394 _GLIBCXX_DEBUG_VERIFY_OPERANDS(__lhs, __rhs);
395 return __lhs.base() != __rhs.base();
396 }
397
398 friend inline bool
399 operator!=(const _Self& __lhs, const _Self& __rhs) noexcept
400 {
401 _GLIBCXX_DEBUG_VERIFY_OPERANDS(__lhs, __rhs);
402 return __lhs.base() != __rhs.base();
403 }
404 };
405
406 /** Safe local iterators know how to check if they form a valid range. */
407 template<typename _Iterator, typename _Sequence>
408 inline bool
409 __valid_range(const _Safe_local_iterator<_Iterator, _Sequence>& __first,
410 const _Safe_local_iterator<_Iterator, _Sequence>& __last,
411 typename _Distance_traits<_Iterator>::__type& __dist_info)
412 { return __first._M_valid_range(__last, __dist_info); }
413
414 template<typename _Iterator, typename _Sequence>
415 inline bool
416 __valid_range(const _Safe_local_iterator<_Iterator, _Sequence>& __first,
417 const _Safe_local_iterator<_Iterator, _Sequence>& __last)
418 {
419 typename _Distance_traits<_Iterator>::__type __dist_info;
420 return __first._M_valid_range(__last, __dist_info);
421 }
422
423 #if __cplusplus < 201103L
424 template<typename _Iterator, typename _Sequence>
425 struct _Unsafe_type<_Safe_local_iterator<_Iterator, _Sequence> >
426 { typedef _Iterator _Type; };
427 #endif
428
429 template<typename _Iterator, typename _Sequence>
430 inline _Iterator
431 __unsafe(const _Safe_local_iterator<_Iterator, _Sequence>& __it)
432 { return __it.base(); }
433
434 } // namespace __gnu_debug
435
436 #undef _GLIBCXX_DEBUG_VERIFY_OPERANDS
437
438 #include <debug/safe_local_iterator.tcc>
439
440 #endif