libstdc++
safe_local_iterator.h
Go to the documentation of this file.
1// Safe iterator implementation -*- C++ -*-
2
3// Copyright (C) 2011-2022 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.base() == _Iterator{} \
37 && _Rhs.base() == _Iterator{}), \
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 struct _Attach_single
88 { };
89
91 _Attach_single) noexcept
92 : _Iter_base(__i)
94
95 public:
96 typedef _Iterator iterator_type;
97 typedef typename _Traits::iterator_category iterator_category;
98 typedef typename _Traits::value_type value_type;
99 typedef typename _Traits::difference_type difference_type;
100 typedef typename _Traits::reference reference;
101 typedef typename _Traits::pointer pointer;
102
103 /// @post the iterator is singular and unattached
104 _Safe_local_iterator() noexcept : _Iter_base() { }
105
106 /**
107 * @brief Safe iterator construction from an unsafe iterator and
108 * its sequence.
109 *
110 * @pre @p seq is not NULL
111 * @post this is not singular
112 */
114 : _Iter_base(__i), _Safe_base(__cont, _S_constant())
115 {
116 _GLIBCXX_DEBUG_VERIFY(!this->_M_singular(),
117 _M_message(__msg_init_singular)
118 ._M_iterator(*this, "this"));
119 }
120
121 /**
122 * @brief Copy construction.
123 */
125 : _Iter_base(__x.base())
126 {
127 // _GLIBCXX_RESOLVE_LIB_DEFECTS
128 // DR 408. Is vector<reverse_iterator<char*> > forbidden?
129 _GLIBCXX_DEBUG_VERIFY(!__x._M_singular()
130 || __x.base() == _Iterator(),
131 _M_message(__msg_init_copy_singular)
132 ._M_iterator(*this, "this")
133 ._M_iterator(__x, "other"));
134 _M_attach(__x._M_sequence);
135 }
136
137 /**
138 * @brief Move construction.
139 * @post __x is singular and unattached
140 */
142 : _Iter_base()
143 {
144 _GLIBCXX_DEBUG_VERIFY(!__x._M_singular()
145 || __x.base() == _Iterator(),
146 _M_message(__msg_init_copy_singular)
147 ._M_iterator(*this, "this")
148 ._M_iterator(__x, "other"));
149 auto __cont = __x._M_sequence;
150 __x._M_detach();
151 std::swap(base(), __x.base());
153 }
154
155 /**
156 * @brief Converting constructor from a mutable iterator to a
157 * constant iterator.
158 */
159 template<typename _MutableIterator>
161 const _Safe_local_iterator<_MutableIterator,
162 typename __gnu_cxx::__enable_if<_IsConstant::__value &&
163 std::__are_same<_MutableIterator, _OtherIterator>::__value,
164 _Sequence>::__type>& __x) noexcept
165 : _Iter_base(__x.base())
166 {
167 // _GLIBCXX_RESOLVE_LIB_DEFECTS
168 // DR 408. Is vector<reverse_iterator<char*> > forbidden?
169 _GLIBCXX_DEBUG_VERIFY(!__x._M_singular()
170 || __x.base() == _MutableIterator(),
171 _M_message(__msg_init_const_singular)
172 ._M_iterator(*this, "this")
173 ._M_iterator(__x, "other"));
174 _M_attach(__x._M_sequence);
175 }
176
177 /**
178 * @brief Copy assignment.
179 */
182 {
183 // _GLIBCXX_RESOLVE_LIB_DEFECTS
184 // DR 408. Is vector<reverse_iterator<char*> > forbidden?
185 _GLIBCXX_DEBUG_VERIFY(!__x._M_singular()
186 || __x.base() == _Iterator(),
187 _M_message(__msg_copy_singular)
188 ._M_iterator(*this, "this")
189 ._M_iterator(__x, "other"));
190
191 if (this->_M_sequence && this->_M_sequence == __x._M_sequence)
192 {
194 base() = __x.base();
196 }
197 else
198 {
199 _M_detach();
200 base() = __x.base();
202 }
203
204 return *this;
205 }
206
207 /**
208 * @brief Move assignment.
209 * @post __x is singular and unattached
210 */
213 {
214 _GLIBCXX_DEBUG_VERIFY(!__x._M_singular()
215 || __x.base() == _Iterator(),
216 _M_message(__msg_copy_singular)
217 ._M_iterator(*this, "this")
218 ._M_iterator(__x, "other"));
219
220 if (std::__addressof(__x) == this)
221 return *this;
222
223 if (this->_M_sequence && this->_M_sequence == __x._M_sequence)
224 {
226 base() = __x.base();
227 _M_version = __x._M_sequence->_M_version;
228 }
229 else
230 {
231 _M_detach();
232 base() = __x.base();
233 _M_attach(__x._M_sequence);
234 }
235
236 __x._M_detach();
237 __x.base() = _Iterator();
238 return *this;
239 }
240
241 /**
242 * @brief Iterator dereference.
243 * @pre iterator is dereferenceable
244 */
245 reference
246 operator*() const
247 {
248 _GLIBCXX_DEBUG_VERIFY(this->_M_dereferenceable(),
249 _M_message(__msg_bad_deref)
250 ._M_iterator(*this, "this"));
251 return *base();
252 }
253
254 /**
255 * @brief Iterator dereference.
256 * @pre iterator is dereferenceable
257 */
258 pointer
260 {
261 _GLIBCXX_DEBUG_VERIFY(this->_M_dereferenceable(),
262 _M_message(__msg_bad_deref)
263 ._M_iterator(*this, "this"));
264 return base().operator->();
265 }
266
267 // ------ Input iterator requirements ------
268 /**
269 * @brief Iterator preincrement
270 * @pre iterator is incrementable
271 */
274 {
275 _GLIBCXX_DEBUG_VERIFY(this->_M_incrementable(),
276 _M_message(__msg_bad_inc)
277 ._M_iterator(*this, "this"));
279 ++base();
280 return *this;
281 }
282
283 /**
284 * @brief Iterator postincrement
285 * @pre iterator is incrementable
286 */
289 {
290 _GLIBCXX_DEBUG_VERIFY(this->_M_incrementable(),
291 _M_message(__msg_bad_inc)
292 ._M_iterator(*this, "this"));
294 return _Safe_local_iterator(base()++, this->_M_sequence,
295 _Attach_single());
296 }
297
298 // ------ Utilities ------
299
300 /// Determine if this is a constant iterator.
301 static constexpr bool
303 { return _IsConstant::__value; }
304
305 /**
306 * @brief Return the underlying iterator
307 */
308 _Iterator&
309 base() noexcept { return *this; }
310
311 const _Iterator&
312 base() const noexcept { return *this; }
313
314 /**
315 * @brief Return the bucket
316 */
317 size_type
318 bucket() const { return base()._M_get_bucket(); }
319
320 /**
321 * @brief Conversion to underlying non-debug iterator to allow
322 * better interaction with non-debug containers.
323 */
324 operator _Iterator() const { return *this; }
325
326 /** Attach iterator to the given sequence. */
327 void
330
331 /** Likewise, but not thread-safe. */
332 void
335
336 /// Is the iterator dereferenceable?
337 bool
339 { return !this->_M_singular() && !_M_is_end(); }
340
341 /// Is the iterator incrementable?
342 bool
344 { return !this->_M_singular() && !_M_is_end(); }
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.
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
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
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
439
440#endif
void swap(any &__x, any &__y) noexcept
Exchange the states of two any objects.
Definition: any:429
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:187
_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.
_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