libstdc++
safe_local_iterator.h
Go to the documentation of this file.
1// Safe iterator implementation -*- C++ -*-
2
3// Copyright (C) 2011-2019 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 _M_message(__msg_iter_compare_bad) \
37 ._M_iterator(_Lhs, "lhs") \
38 ._M_iterator(_Rhs, "rhs")); \
39 _GLIBCXX_DEBUG_VERIFY(_Lhs._M_can_compare(_Rhs), \
40 _M_message(__msg_compare_different) \
41 ._M_iterator(_Lhs, "lhs") \
42 ._M_iterator(_Rhs, "rhs")); \
43 _GLIBCXX_DEBUG_VERIFY(_Lhs._M_in_same_bucket(_Rhs), \
44 _M_message(__msg_local_iter_compare_bad) \
45 ._M_iterator(_Lhs, "lhs") \
46 ._M_iterator(_Rhs, "rhs"))
47
48namespace __gnu_debug
49{
50 /** \brief Safe iterator wrapper.
51 *
52 * The class template %_Safe_local_iterator is a wrapper around an
53 * iterator that tracks the iterator's movement among sequences and
54 * checks that operations performed on the "safe" iterator are
55 * legal. In additional to the basic iterator operations (which are
56 * validated, and then passed to the underlying iterator),
57 * %_Safe_local_iterator has member functions for iterator invalidation,
58 * attaching/detaching the iterator from sequences, and querying
59 * the iterator's state.
60 */
61 template<typename _Iterator, typename _Sequence>
63 : private _Iterator
65 {
66 typedef _Iterator _Iter_base;
68
69 typedef typename _Sequence::size_type size_type;
70
71 typedef std::iterator_traits<_Iterator> _Traits;
72
73 typedef std::__are_same<
74 typename _Sequence::_Base::const_local_iterator,
75 _Iterator> _IsConstant;
76
77 typedef typename __gnu_cxx::__conditional_type<_IsConstant::__value,
78 typename _Sequence::_Base::local_iterator,
79 typename _Sequence::_Base::const_local_iterator>::__type
80 _OtherIterator;
81
84
85 struct _Attach_single
86 { };
87
88 _Safe_local_iterator(_Iterator __i, _Safe_sequence_base* __cont,
89 _Attach_single) noexcept
90 : _Iter_base(__i)
91 { _M_attach_single(__cont); }
92
93 public:
94 typedef _Iterator iterator_type;
95 typedef typename _Traits::iterator_category iterator_category;
96 typedef typename _Traits::value_type value_type;
97 typedef typename _Traits::difference_type difference_type;
98 typedef typename _Traits::reference reference;
99 typedef typename _Traits::pointer pointer;
100
101 /// @post the iterator is singular and unattached
102 _Safe_local_iterator() noexcept : _Iter_base() { }
103
104 /**
105 * @brief Safe iterator construction from an unsafe iterator and
106 * its sequence.
107 *
108 * @pre @p seq is not NULL
109 * @post this is not singular
110 */
111 _Safe_local_iterator(_Iterator __i, const _Safe_sequence_base* __cont)
112 : _Iter_base(__i), _Safe_base(__cont, _S_constant())
113 {
114 _GLIBCXX_DEBUG_VERIFY(!this->_M_singular(),
115 _M_message(__msg_init_singular)
116 ._M_iterator(*this, "this"));
117 }
118
119 /**
120 * @brief Copy construction.
121 */
123 : _Iter_base(__x.base())
124 {
125 // _GLIBCXX_RESOLVE_LIB_DEFECTS
126 // DR 408. Is vector<reverse_iterator<char*> > forbidden?
127 _GLIBCXX_DEBUG_VERIFY(!__x._M_singular()
128 || __x.base() == _Iterator(),
129 _M_message(__msg_init_copy_singular)
130 ._M_iterator(*this, "this")
131 ._M_iterator(__x, "other"));
132 _M_attach(__x._M_sequence);
133 }
134
135 /**
136 * @brief Move construction.
137 * @post __x is singular and unattached
138 */
140 : _Iter_base()
141 {
142 _GLIBCXX_DEBUG_VERIFY(!__x._M_singular()
143 || __x.base() == _Iterator(),
144 _M_message(__msg_init_copy_singular)
145 ._M_iterator(*this, "this")
146 ._M_iterator(__x, "other"));
147 auto __cont = __x._M_sequence;
148 __x._M_detach();
149 std::swap(base(), __x.base());
150 _M_attach(__cont);
151 }
152
153 /**
154 * @brief Converting constructor from a mutable iterator to a
155 * constant iterator.
156 */
157 template<typename _MutableIterator>
159 const _Safe_local_iterator<_MutableIterator,
160 typename __gnu_cxx::__enable_if<_IsConstant::__value &&
161 std::__are_same<_MutableIterator, _OtherIterator>::__value,
162 _Sequence>::__type>& __x) noexcept
163 : _Iter_base(__x.base())
164 {
165 // _GLIBCXX_RESOLVE_LIB_DEFECTS
166 // DR 408. Is vector<reverse_iterator<char*> > forbidden?
167 _GLIBCXX_DEBUG_VERIFY(!__x._M_singular()
168 || __x.base() == _MutableIterator(),
169 _M_message(__msg_init_const_singular)
170 ._M_iterator(*this, "this")
171 ._M_iterator(__x, "other"));
172 _M_attach(__x._M_sequence);
173 }
174
175 /**
176 * @brief Copy assignment.
177 */
180 {
181 // _GLIBCXX_RESOLVE_LIB_DEFECTS
182 // DR 408. Is vector<reverse_iterator<char*> > forbidden?
183 _GLIBCXX_DEBUG_VERIFY(!__x._M_singular()
184 || __x.base() == _Iterator(),
185 _M_message(__msg_copy_singular)
186 ._M_iterator(*this, "this")
187 ._M_iterator(__x, "other"));
188
189 if (this->_M_sequence && this->_M_sequence == __x._M_sequence)
190 {
192 base() = __x.base();
194 }
195 else
196 {
197 _M_detach();
198 base() = __x.base();
200 }
201
202 return *this;
203 }
204
205 /**
206 * @brief Move assignment.
207 * @post __x is singular and unattached
208 */
211 {
212 _GLIBCXX_DEBUG_VERIFY(this != &__x,
213 _M_message(__msg_self_move_assign)
214 ._M_iterator(*this, "this"));
215 _GLIBCXX_DEBUG_VERIFY(!__x._M_singular()
216 || __x.base() == _Iterator(),
217 _M_message(__msg_copy_singular)
218 ._M_iterator(*this, "this")
219 ._M_iterator(__x, "other"));
220
221 if (this->_M_sequence && this->_M_sequence == __x._M_sequence)
222 {
224 base() = __x.base();
225 _M_version = __x._M_sequence->_M_version;
226 }
227 else
228 {
229 _M_detach();
230 base() = __x.base();
231 _M_attach(__x._M_sequence);
232 }
233
234 __x._M_detach();
235 __x.base() = _Iterator();
236 return *this;
237 }
238
239 /**
240 * @brief Iterator dereference.
241 * @pre iterator is dereferenceable
242 */
243 reference
244 operator*() const
245 {
246 _GLIBCXX_DEBUG_VERIFY(this->_M_dereferenceable(),
247 _M_message(__msg_bad_deref)
248 ._M_iterator(*this, "this"));
249 return *base();
250 }
251
252 /**
253 * @brief Iterator dereference.
254 * @pre iterator is dereferenceable
255 */
256 pointer
258 {
259 _GLIBCXX_DEBUG_VERIFY(this->_M_dereferenceable(),
260 _M_message(__msg_bad_deref)
261 ._M_iterator(*this, "this"));
262 return base().operator->();
263 }
264
265 // ------ Input iterator requirements ------
266 /**
267 * @brief Iterator preincrement
268 * @pre iterator is incrementable
269 */
272 {
273 _GLIBCXX_DEBUG_VERIFY(this->_M_incrementable(),
274 _M_message(__msg_bad_inc)
275 ._M_iterator(*this, "this"));
277 ++base();
278 return *this;
279 }
280
281 /**
282 * @brief Iterator postincrement
283 * @pre iterator is incrementable
284 */
287 {
288 _GLIBCXX_DEBUG_VERIFY(this->_M_incrementable(),
289 _M_message(__msg_bad_inc)
290 ._M_iterator(*this, "this"));
292 return _Safe_local_iterator(base()++, this->_M_sequence,
293 _Attach_single());
294 }
295
296 // ------ Utilities ------
297
298 /// Determine if this is a constant iterator.
299 static constexpr bool
301 { return _IsConstant::__value; }
302
303 /**
304 * @brief Return the underlying iterator
305 */
306 _Iterator&
307 base() noexcept { return *this; }
308
309 const _Iterator&
310 base() const noexcept { return *this; }
311
312 /**
313 * @brief Return the bucket
314 */
315 size_type
316 bucket() const { return base()._M_get_bucket(); }
317
318 /**
319 * @brief Conversion to underlying non-debug iterator to allow
320 * better interaction with non-debug containers.
321 */
322 operator _Iterator() const { return *this; }
323
324 /** Attach iterator to the given sequence. */
325 void
328
329 /** Likewise, but not thread-safe. */
330 void
333
334 /// Is the iterator dereferenceable?
335 bool
337 { return !this->_M_singular() && !_M_is_end(); }
338
339 /// Is the iterator incrementable?
340 bool
342 { return !this->_M_singular() && !_M_is_end(); }
343
344 // Is the iterator range [*this, __rhs) valid?
345 bool
346 _M_valid_range(const _Safe_local_iterator& __rhs,
347 std::pair<difference_type,
348 _Distance_precision>& __dist_info) const;
349
350 // Get distance to __rhs.
352 _M_get_distance_to(const _Safe_local_iterator& __rhs) const;
353
354 // The sequence this iterator references.
355 typename __gnu_cxx::__conditional_type<
356 _IsConstant::__value, const _Sequence*, _Sequence*>::__type
357 _M_get_sequence() const
358 { return static_cast<_Sequence*>(_M_sequence); }
359
360 /// Is this iterator equal to the sequence's begin(bucket) iterator?
361 bool _M_is_begin() const
362 { return base() == _M_get_sequence()->_M_base().begin(bucket()); }
363
364 /// Is this iterator equal to the sequence's end(bucket) iterator?
365 bool _M_is_end() const
366 { return base() == _M_get_sequence()->_M_base().end(bucket()); }
367
368 /// Is this iterator part of the same bucket as the other one?
369 template<typename _Other>
370 bool
372 _Sequence>& __other) const
373 { return bucket() == __other.bucket(); }
374
375 friend inline bool
376 operator==(const _Self& __lhs, const _OtherSelf& __rhs) noexcept
377 {
378 _GLIBCXX_DEBUG_VERIFY_OPERANDS(__lhs, __rhs);
379 return __lhs.base() == __rhs.base();
380 }
381
382 friend inline bool
383 operator==(const _Self& __lhs, const _Self& __rhs) noexcept
384 {
385 _GLIBCXX_DEBUG_VERIFY_OPERANDS(__lhs, __rhs);
386 return __lhs.base() == __rhs.base();
387 }
388
389 friend inline bool
390 operator!=(const _Self& __lhs, const _OtherSelf& __rhs) noexcept
391 {
392 _GLIBCXX_DEBUG_VERIFY_OPERANDS(__lhs, __rhs);
393 return __lhs.base() != __rhs.base();
394 }
395
396 friend inline bool
397 operator!=(const _Self& __lhs, const _Self& __rhs) noexcept
398 {
399 _GLIBCXX_DEBUG_VERIFY_OPERANDS(__lhs, __rhs);
400 return __lhs.base() != __rhs.base();
401 }
402 };
403
404 /** Safe local iterators know how to check if they form a valid range. */
405 template<typename _Iterator, typename _Sequence>
406 inline bool
409 typename _Distance_traits<_Iterator>::__type& __dist_info)
410 { return __first._M_valid_range(__last, __dist_info); }
411
412 template<typename _Iterator, typename _Sequence>
413 inline bool
414 __valid_range(const _Safe_local_iterator<_Iterator, _Sequence>& __first,
415 const _Safe_local_iterator<_Iterator, _Sequence>& __last)
416 {
417 typename _Distance_traits<_Iterator>::__type __dist_info;
418 return __first._M_valid_range(__last, __dist_info);
419 }
420
421#if __cplusplus < 201103L
422 template<typename _Iterator, typename _Sequence>
423 struct _Unsafe_type<_Safe_local_iterator<_Iterator, _Sequence> >
424 { typedef _Iterator _Type; };
425#endif
426
427 template<typename _Iterator, typename _Sequence>
428 inline _Iterator
429 __unsafe(const _Safe_local_iterator<_Iterator, _Sequence>& __it)
430 { return __it.base(); }
431
432} // namespace __gnu_debug
433
434#undef _GLIBCXX_DEBUG_VERIFY_OPERANDS
435
437
438#endif
GNU debug classes for public use.
bool __valid_range(_InputIterator __first, _InputIterator __last, typename _Distance_traits< _InputIterator >::__type &__dist)
Struct holding two objects of arbitrary type.
Definition: stl_pair.h:210
_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