libstdc++
safe_local_iterator.h
Go to the documentation of this file.
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
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
50namespace __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>
65 : private _Iterator
67 {
68 typedef _Iterator _Iter_base;
70
71 typedef typename _Sequence::size_type size_type;
72
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
86
87 public:
88 typedef _Iterator iterator_type;
89 typedef typename _Traits::iterator_category iterator_category;
90 typedef typename _Traits::value_type value_type;
91 typedef typename _Traits::difference_type difference_type;
92 typedef typename _Traits::reference reference;
93 typedef typename _Traits::pointer pointer;
94
95 /// @post the iterator is singular and unattached
96 _Safe_local_iterator() noexcept : _Iter_base() { }
97
98 /**
99 * @brief Safe iterator construction from an unsafe iterator and
100 * its sequence.
101 *
102 * @pre @p seq is not NULL
103 * @post this is not singular
104 */
106 : _Iter_base(__i), _Safe_base(__cont, _S_constant())
107 {
108 _GLIBCXX_DEBUG_VERIFY(!this->_M_singular(),
109 _M_message(__msg_init_singular)
110 ._M_iterator(*this, "this"));
111 }
112
113 /**
114 * @brief Copy construction.
115 */
117 : _Iter_base(__x.base())
118 {
119 // _GLIBCXX_RESOLVE_LIB_DEFECTS
120 // DR 408. Is vector<reverse_iterator<char*> > forbidden?
121 _GLIBCXX_DEBUG_VERIFY(!__x._M_singular()
122 || __x._M_value_initialized(),
123 _M_message(__msg_init_copy_singular)
124 ._M_iterator(*this, "this")
125 ._M_iterator(__x, "other"));
126 _M_attach(__x._M_sequence);
127 }
128
129 /**
130 * @brief Move construction.
131 * @post __x is singular and unattached
132 */
134 : _Iter_base()
135 {
136 _GLIBCXX_DEBUG_VERIFY(!__x._M_singular()
137 || __x._M_value_initialized(),
138 _M_message(__msg_init_copy_singular)
139 ._M_iterator(*this, "this")
140 ._M_iterator(__x, "other"));
141 auto __cont = __x._M_sequence;
142 __x._M_detach();
143 std::swap(base(), __x.base());
145 }
146
147 /**
148 * @brief Converting constructor from a mutable iterator to a
149 * constant iterator.
150 */
151 template<typename _MutableIterator>
153 const _Safe_local_iterator<_MutableIterator,
154 typename __gnu_cxx::__enable_if<_IsConstant::__value &&
155 std::__are_same<_MutableIterator, _OtherIterator>::__value,
156 _Sequence>::__type>& __x) noexcept
157 : _Iter_base(__x.base())
158 {
159 // _GLIBCXX_RESOLVE_LIB_DEFECTS
160 // DR 408. Is vector<reverse_iterator<char*> > forbidden?
161 _GLIBCXX_DEBUG_VERIFY(!__x._M_singular()
162 || __x._M_value_initialized(),
163 _M_message(__msg_init_const_singular)
164 ._M_iterator(*this, "this")
165 ._M_iterator(__x, "other"));
166 _M_attach(__x._M_sequence);
167 }
168
169 /**
170 * @brief Copy assignment.
171 */
174 {
175 // _GLIBCXX_RESOLVE_LIB_DEFECTS
176 // DR 408. Is vector<reverse_iterator<char*> > forbidden?
177 _GLIBCXX_DEBUG_VERIFY(!__x._M_singular()
178 || __x._M_value_initialized(),
179 _M_message(__msg_copy_singular)
180 ._M_iterator(*this, "this")
181 ._M_iterator(__x, "other"));
182
183 if (this->_M_sequence && this->_M_sequence == __x._M_sequence)
184 {
186 base() = __x.base();
188 }
189 else
190 {
191 _M_detach();
192 base() = __x.base();
194 }
195
196 return *this;
197 }
198
199 /**
200 * @brief Move assignment.
201 * @post __x is singular and unattached
202 */
205 {
206 _GLIBCXX_DEBUG_VERIFY(!__x._M_singular()
207 || __x._M_value_initialized(),
208 _M_message(__msg_copy_singular)
209 ._M_iterator(*this, "this")
210 ._M_iterator(__x, "other"));
211
212 if (std::__addressof(__x) == this)
213 return *this;
214
215 if (this->_M_sequence && this->_M_sequence == __x._M_sequence)
216 {
218 base() = __x.base();
219 _M_version = __x._M_sequence->_M_version;
220 }
221 else
222 {
223 _M_detach();
224 base() = __x.base();
225 _M_attach(__x._M_sequence);
226 }
227
228 __x._M_detach();
229 __x.base() = _Iterator();
230 return *this;
231 }
232
233 /**
234 * @brief Iterator dereference.
235 * @pre iterator is dereferenceable
236 */
237 reference
238 operator*() const
239 {
240 _GLIBCXX_DEBUG_VERIFY(this->_M_dereferenceable(),
241 _M_message(__msg_bad_deref)
242 ._M_iterator(*this, "this"));
243 return *base();
244 }
245
246 /**
247 * @brief Iterator dereference.
248 * @pre iterator is dereferenceable
249 */
250 pointer
252 {
253 _GLIBCXX_DEBUG_VERIFY(this->_M_dereferenceable(),
254 _M_message(__msg_bad_deref)
255 ._M_iterator(*this, "this"));
256 return base().operator->();
257 }
258
259 // ------ Input iterator requirements ------
260 /**
261 * @brief Iterator preincrement
262 * @pre iterator is incrementable
263 */
266 {
267 _GLIBCXX_DEBUG_VERIFY(this->_M_incrementable(),
268 _M_message(__msg_bad_inc)
269 ._M_iterator(*this, "this"));
271 ++base();
272 return *this;
273 }
274
275 /**
276 * @brief Iterator postincrement
277 * @pre iterator is incrementable
278 */
281 {
282 _GLIBCXX_DEBUG_VERIFY(this->_M_incrementable(),
283 _M_message(__msg_bad_inc)
284 ._M_iterator(*this, "this"));
285 _Safe_local_iterator __ret = *this;
286 ++*this;
287 return __ret;
288 }
289
290 // ------ Utilities ------
291
292 /// Determine if this is a constant iterator.
293 static constexpr bool
295 { return _IsConstant::__value; }
296
297 /**
298 * @brief Return the underlying iterator
299 */
300 _Iterator&
301 base() noexcept { return *this; }
302
303 const _Iterator&
304 base() const noexcept { return *this; }
305
306 /**
307 * @brief Return the bucket
308 */
309 size_type
310 bucket() const { return base()._M_get_bucket(); }
311
312 /**
313 * @brief Conversion to underlying non-debug iterator to allow
314 * better interaction with non-debug containers.
315 */
316 operator _Iterator() const { return *this; }
317
318 /** Attach iterator to the given sequence. */
319 void
322
323 /** Likewise, but not thread-safe. */
324 void
327
328 /// Is the iterator dereferenceable?
329 bool
331 { return !this->_M_singular() && !_M_is_end(); }
332
333 /// Is the iterator incrementable?
334 bool
336 { return !this->_M_singular() && !_M_is_end(); }
337
338 /// Is the iterator value-initialized?
339 bool
341 { return _M_version == 0 && base() == _Iter_base{}; }
342
343 // Is the iterator range [*this, __rhs) valid?
344 bool
345 _M_valid_range(const _Safe_local_iterator& __rhs,
346 std::pair<difference_type,
347 _Distance_precision>& __dist_info) const;
348
349 // Get distance to __rhs.
351 _M_get_distance_to(const _Safe_local_iterator& __rhs) const;
352
353 // The sequence this iterator references.
354 typename __gnu_cxx::__conditional_type<
355 _IsConstant::__value, const _Sequence*, _Sequence*>::__type
356 _M_get_sequence() const
357 { return static_cast<_Sequence*>(_M_sequence); }
358
359 /// Is this iterator equal to the sequence's begin(bucket) iterator?
360 bool _M_is_begin() const
361 { return base() == _M_get_sequence()->_M_base().begin(bucket()); }
362
363 /// Is this iterator equal to the sequence's end(bucket) iterator?
364 bool _M_is_end() const
365 { return base() == _M_get_sequence()->_M_base().end(bucket()); }
366
367 /// Is this iterator part of the same bucket as the other one?
368 template<typename _Other>
369 bool
371 _Sequence>& __other) const
372 { return bucket() == __other.bucket(); }
373
374 friend inline bool
375 operator==(const _Self& __lhs, const _OtherSelf& __rhs) noexcept
376 {
377 _GLIBCXX_DEBUG_VERIFY_OPERANDS(__lhs, __rhs);
378 return __lhs.base() == __rhs.base();
379 }
380
381 friend inline bool
382 operator==(const _Self& __lhs, const _Self& __rhs) noexcept
383 {
384 _GLIBCXX_DEBUG_VERIFY_OPERANDS(__lhs, __rhs);
385 return __lhs.base() == __rhs.base();
386 }
387
388 friend inline bool
389 operator!=(const _Self& __lhs, const _OtherSelf& __rhs) noexcept
390 {
391 _GLIBCXX_DEBUG_VERIFY_OPERANDS(__lhs, __rhs);
392 return __lhs.base() != __rhs.base();
393 }
394
395 friend inline bool
396 operator!=(const _Self& __lhs, const _Self& __rhs) noexcept
397 {
398 _GLIBCXX_DEBUG_VERIFY_OPERANDS(__lhs, __rhs);
399 return __lhs.base() != __rhs.base();
400 }
401 };
402
403 /** Safe local iterators know how to check if they form a valid range. */
404 template<typename _Iterator, typename _Sequence>
405 inline bool
408 typename _Distance_traits<_Iterator>::__type& __dist_info)
409 { return __first._M_valid_range(__last, __dist_info); }
410
411 template<typename _Iterator, typename _Sequence>
412 inline bool
413 __valid_range(const _Safe_local_iterator<_Iterator, _Sequence>& __first,
414 const _Safe_local_iterator<_Iterator, _Sequence>& __last)
415 {
416 typename _Distance_traits<_Iterator>::__type __dist_info;
417 return __first._M_valid_range(__last, __dist_info);
418 }
419
420#if __cplusplus < 201103L
421 template<typename _Iterator, typename _Sequence>
422 struct _Unsafe_type<_Safe_local_iterator<_Iterator, _Sequence> >
423 { typedef _Iterator _Type; };
424#endif
425
426 template<typename _Iterator, typename _Sequence>
427 inline _Iterator
428 __unsafe(const _Safe_local_iterator<_Iterator, _Sequence>& __it)
429 { return __it.base(); }
430
431} // namespace __gnu_debug
432
433#undef _GLIBCXX_DEBUG_VERIFY_OPERANDS
434
436
437#endif
constexpr _Tp * __addressof(_Tp &__r) noexcept
Same as C++11 std::addressof.
Definition: move.h:49
ISO C++ entities toplevel namespace is std.
GNU debug classes for public use.
constexpr bool __valid_range(_InputIterator __first, _InputIterator __last, typename _Distance_traits< _InputIterator >::__type &__dist)
Traits class for iterators.
Struct holding two objects of arbitrary type.
Definition: stl_pair.h:189
_Safe_local_iterator(const _Safe_local_iterator &__x) noexcept
Copy construction.
bool _M_is_end() const
Is this iterator equal to the sequence's end(bucket) iterator?
size_type bucket() const
Return the bucket.
_Safe_local_iterator & operator=(_Safe_local_iterator &&__x) noexcept
Move assignment.
bool _M_incrementable() const
Is the iterator incrementable?
_Safe_local_iterator(_Safe_local_iterator &&__x) noexcept
Move construction.
bool _M_value_initialized() const
Is the iterator value-initialized?
_Safe_local_iterator(_Iterator __i, const _Safe_sequence_base *__cont)
Safe iterator construction from an unsafe iterator and its sequence.
bool _M_in_same_bucket(const _Safe_local_iterator< _Other, _Sequence > &__other) const
Is this iterator part of the same bucket as the other one?
_Safe_local_iterator & operator++()
Iterator preincrement.
_Safe_local_iterator & operator=(const _Safe_local_iterator &__x)
Copy assignment.
pointer operator->() const
Iterator dereference.
static constexpr bool _S_constant()
Determine if this is a constant iterator.
bool _M_dereferenceable() const
Is the iterator dereferenceable?
void _M_attach_single(_Safe_sequence_base *__seq)
reference operator*() const
Iterator dereference.
_Safe_local_iterator operator++(int)
Iterator postincrement.
_Iterator & base() noexcept
Return the underlying iterator.
_Safe_local_iterator(const _Safe_local_iterator< _MutableIterator, typename __gnu_cxx::__enable_if< _IsConstant::__value &&std::__are_same< _MutableIterator, _OtherIterator >::__value, _Sequence >::__type > &__x) noexcept
Converting constructor from a mutable iterator to a constant iterator.
void _M_attach(_Safe_sequence_base *__seq)
bool _M_is_begin() const
Is this iterator equal to the sequence's begin(bucket) iterator?
_Safe_sequence_base * _M_sequence
Definition: safe_base.h:57
__gnu_cxx::__mutex & _M_get_mutex()
Base class that supports tracking of iterators that reference a sequence.
Definition: safe_base.h:189
unsigned int _M_version
The container version number. This number may never be 0.
Definition: safe_base.h:200
Basic functionality for a safe iterator.
void _M_attach_single(_Safe_sequence_base *__seq, bool __constant)
void _M_attach(_Safe_sequence_base *__seq, bool __constant)
Scoped lock idiom.
Definition: concurrence.h:229