libstdc++
safe_local_iterator.h
Go to the documentation of this file.
1// Safe iterator implementation -*- C++ -*-
2
3// Copyright (C) 2011-2017 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
34namespace __gnu_debug
35{
36 /** \brief Safe iterator wrapper.
37 *
38 * The class template %_Safe_local_iterator is a wrapper around an
39 * iterator that tracks the iterator's movement among sequences and
40 * checks that operations performed on the "safe" iterator are
41 * legal. In additional to the basic iterator operations (which are
42 * validated, and then passed to the underlying iterator),
43 * %_Safe_local_iterator has member functions for iterator invalidation,
44 * attaching/detaching the iterator from sequences, and querying
45 * the iterator's state.
46 */
47 template<typename _Iterator, typename _Sequence>
49 : private _Iterator
51 {
52 typedef _Iterator _Iter_base;
54 typedef typename _Sequence::const_local_iterator _Const_local_iterator;
55 typedef typename _Sequence::size_type size_type;
56
57 /// Determine if this is a constant iterator.
58 bool
59 _M_constant() const
60 {
61 return std::__are_same<_Const_local_iterator,
62 _Safe_local_iterator>::__value;
63 }
64
65 typedef std::iterator_traits<_Iterator> _Traits;
66
67 struct _Attach_single
68 { };
69
70 _Safe_local_iterator(const _Iterator& __i, _Safe_sequence_base* __cont,
71 _Attach_single) noexcept
72 : _Iter_base(__i)
73 { _M_attach_single(__cont); }
74
75 public:
76 typedef _Iterator iterator_type;
77 typedef typename _Traits::iterator_category iterator_category;
78 typedef typename _Traits::value_type value_type;
79 typedef typename _Traits::difference_type difference_type;
80 typedef typename _Traits::reference reference;
81 typedef typename _Traits::pointer pointer;
82
83 /// @post the iterator is singular and unattached
84 _Safe_local_iterator() noexcept : _Iter_base() { }
85
86 /**
87 * @brief Safe iterator construction from an unsafe iterator and
88 * its sequence.
89 *
90 * @pre @p seq is not NULL
91 * @post this is not singular
92 */
93 _Safe_local_iterator(const _Iterator& __i,
94 const _Safe_sequence_base* __cont)
95 : _Iter_base(__i), _Safe_base(__cont, _M_constant())
96 {
97 _GLIBCXX_DEBUG_VERIFY(!this->_M_singular(),
98 _M_message(__msg_init_singular)
99 ._M_iterator(*this, "this"));
100 }
101
102 /**
103 * @brief Copy construction.
104 */
106 : _Iter_base(__x.base())
107 {
108 // _GLIBCXX_RESOLVE_LIB_DEFECTS
109 // DR 408. Is vector<reverse_iterator<char*> > forbidden?
110 _GLIBCXX_DEBUG_VERIFY(!__x._M_singular()
111 || __x.base() == _Iterator(),
112 _M_message(__msg_init_copy_singular)
113 ._M_iterator(*this, "this")
114 ._M_iterator(__x, "other"));
115 _M_attach(__x._M_sequence);
116 }
117
118 /**
119 * @brief Move construction.
120 * @post __x is singular and unattached
121 */
123 : _Iter_base()
124 {
125 _GLIBCXX_DEBUG_VERIFY(!__x._M_singular()
126 || __x.base() == _Iterator(),
127 _M_message(__msg_init_copy_singular)
128 ._M_iterator(*this, "this")
129 ._M_iterator(__x, "other"));
130 auto __cont = __x._M_sequence;
131 __x._M_detach();
132 std::swap(base(), __x.base());
133 _M_attach(__cont);
134 }
135
136 /**
137 * @brief Converting constructor from a mutable iterator to a
138 * constant iterator.
139 */
140 template<typename _MutableIterator>
142 const _Safe_local_iterator<_MutableIterator,
143 typename __gnu_cxx::__enable_if<std::__are_same<
144 _MutableIterator,
145 typename _Sequence::local_iterator::iterator_type>::__value,
146 _Sequence>::__type>& __x)
147 : _Iter_base(__x.base())
148 {
149 // _GLIBCXX_RESOLVE_LIB_DEFECTS
150 // DR 408. Is vector<reverse_iterator<char*> > forbidden?
151 _GLIBCXX_DEBUG_VERIFY(!__x._M_singular()
152 || __x.base() == _Iterator(),
153 _M_message(__msg_init_const_singular)
154 ._M_iterator(*this, "this")
155 ._M_iterator(__x, "other"));
156 _M_attach(__x._M_sequence);
157 }
158
159 /**
160 * @brief Copy assignment.
161 */
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() == _Iterator(),
169 _M_message(__msg_copy_singular)
170 ._M_iterator(*this, "this")
171 ._M_iterator(__x, "other"));
172
173 if (this->_M_sequence && this->_M_sequence == __x._M_sequence)
174 {
176 base() = __x.base();
178 }
179 else
180 {
181 _M_detach();
182 base() = __x.base();
184 }
185
186 return *this;
187 }
188
189 /**
190 * @brief Move assignment.
191 * @post __x is singular and unattached
192 */
195 {
196 _GLIBCXX_DEBUG_VERIFY(this != &__x,
197 _M_message(__msg_self_move_assign)
198 ._M_iterator(*this, "this"));
199 _GLIBCXX_DEBUG_VERIFY(!__x._M_singular()
200 || __x.base() == _Iterator(),
201 _M_message(__msg_copy_singular)
202 ._M_iterator(*this, "this")
203 ._M_iterator(__x, "other"));
204
205 if (this->_M_sequence && this->_M_sequence == __x._M_sequence)
206 {
208 base() = __x.base();
209 _M_version = __x._M_sequence->_M_version;
210 }
211 else
212 {
213 _M_detach();
214 base() = __x.base();
215 _M_attach(__x._M_sequence);
216 }
217
218 __x._M_detach();
219 __x.base() = _Iterator();
220 return *this;
221 }
222
223 /**
224 * @brief Iterator dereference.
225 * @pre iterator is dereferenceable
226 */
227 reference
228 operator*() const
229 {
230 _GLIBCXX_DEBUG_VERIFY(this->_M_dereferenceable(),
231 _M_message(__msg_bad_deref)
232 ._M_iterator(*this, "this"));
233 return *base();
234 }
235
236 /**
237 * @brief Iterator dereference.
238 * @pre iterator is dereferenceable
239 */
240 pointer
242 {
243 _GLIBCXX_DEBUG_VERIFY(this->_M_dereferenceable(),
244 _M_message(__msg_bad_deref)
245 ._M_iterator(*this, "this"));
246 return base().operator->();
247 }
248
249 // ------ Input iterator requirements ------
250 /**
251 * @brief Iterator preincrement
252 * @pre iterator is incrementable
253 */
256 {
257 _GLIBCXX_DEBUG_VERIFY(this->_M_incrementable(),
258 _M_message(__msg_bad_inc)
259 ._M_iterator(*this, "this"));
261 ++base();
262 return *this;
263 }
264
265 /**
266 * @brief Iterator postincrement
267 * @pre iterator is incrementable
268 */
271 {
272 _GLIBCXX_DEBUG_VERIFY(this->_M_incrementable(),
273 _M_message(__msg_bad_inc)
274 ._M_iterator(*this, "this"));
276 return _Safe_local_iterator(base()++, this->_M_sequence,
277 _Attach_single());
278 }
279
280 // ------ Utilities ------
281 /**
282 * @brief Return the underlying iterator
283 */
284 _Iterator&
285 base() noexcept { return *this; }
286
287 const _Iterator&
288 base() const noexcept { return *this; }
289
290 /**
291 * @brief Return the bucket
292 */
293 size_type
294 bucket() const { return base()._M_get_bucket(); }
295
296 /**
297 * @brief Conversion to underlying non-debug iterator to allow
298 * better interaction with non-debug containers.
299 */
300 operator _Iterator() const { return *this; }
301
302 /** Attach iterator to the given sequence. */
303 void
305 { _Safe_base::_M_attach(__seq, _M_constant()); }
306
307 /** Likewise, but not thread-safe. */
308 void
310 { _Safe_base::_M_attach_single(__seq, _M_constant()); }
311
312 /// Is the iterator dereferenceable?
313 bool
315 { return !this->_M_singular() && !_M_is_end(); }
316
317 /// Is the iterator incrementable?
318 bool
320 { return !this->_M_singular() && !_M_is_end(); }
321
322 // Is the iterator range [*this, __rhs) valid?
323 bool
324 _M_valid_range(const _Safe_local_iterator& __rhs,
325 std::pair<difference_type,
326 _Distance_precision>& __dist_info) const;
327
328 // The sequence this iterator references.
329 typename
330 __gnu_cxx::__conditional_type<std::__are_same<_Const_local_iterator,
331 _Safe_local_iterator>::__value,
332 const _Sequence*,
333 _Sequence*>::__type
334 _M_get_sequence() const
335 { return static_cast<_Sequence*>(_M_sequence); }
336
337 /// Is this iterator equal to the sequence's begin(bucket) iterator?
338 bool _M_is_begin() const
339 { return base() == _M_get_sequence()->_M_base().begin(bucket()); }
340
341 /// Is this iterator equal to the sequence's end(bucket) iterator?
342 bool _M_is_end() const
343 { return base() == _M_get_sequence()->_M_base().end(bucket()); }
344
345 /// Is this iterator part of the same bucket as the other one?
346 template<typename _Other>
347 bool
349 _Sequence>& __other) const
350 { return bucket() == __other.bucket(); }
351 };
352
353 template<typename _IteratorL, typename _IteratorR, typename _Sequence>
354 inline bool
355 operator==(const _Safe_local_iterator<_IteratorL, _Sequence>& __lhs,
356 const _Safe_local_iterator<_IteratorR, _Sequence>& __rhs)
357 {
358 _GLIBCXX_DEBUG_VERIFY(!__lhs._M_singular() && !__rhs._M_singular(),
359 _M_message(__msg_iter_compare_bad)
360 ._M_iterator(__lhs, "lhs")
361 ._M_iterator(__rhs, "rhs"));
362 _GLIBCXX_DEBUG_VERIFY(__lhs._M_can_compare(__rhs),
363 _M_message(__msg_compare_different)
364 ._M_iterator(__lhs, "lhs")
365 ._M_iterator(__rhs, "rhs"));
366 _GLIBCXX_DEBUG_VERIFY(__lhs._M_in_same_bucket(__rhs),
367 _M_message(__msg_local_iter_compare_bad)
368 ._M_iterator(__lhs, "lhs")
369 ._M_iterator(__rhs, "rhs"));
370 return __lhs.base() == __rhs.base();
371 }
372
373 template<typename _Iterator, typename _Sequence>
374 inline bool
375 operator==(const _Safe_local_iterator<_Iterator, _Sequence>& __lhs,
376 const _Safe_local_iterator<_Iterator, _Sequence>& __rhs)
377 {
378 _GLIBCXX_DEBUG_VERIFY(!__lhs._M_singular() && !__rhs._M_singular(),
379 _M_message(__msg_iter_compare_bad)
380 ._M_iterator(__lhs, "lhs")
381 ._M_iterator(__rhs, "rhs"));
382 _GLIBCXX_DEBUG_VERIFY(__lhs._M_can_compare(__rhs),
383 _M_message(__msg_compare_different)
384 ._M_iterator(__lhs, "lhs")
385 ._M_iterator(__rhs, "rhs"));
386 _GLIBCXX_DEBUG_VERIFY(__lhs._M_in_same_bucket(__rhs),
387 _M_message(__msg_local_iter_compare_bad)
388 ._M_iterator(__lhs, "lhs")
389 ._M_iterator(__rhs, "rhs"));
390 return __lhs.base() == __rhs.base();
391 }
392
393 template<typename _IteratorL, typename _IteratorR, typename _Sequence>
394 inline bool
395 operator!=(const _Safe_local_iterator<_IteratorL, _Sequence>& __lhs,
396 const _Safe_local_iterator<_IteratorR, _Sequence>& __rhs)
397 {
398 _GLIBCXX_DEBUG_VERIFY(! __lhs._M_singular() && ! __rhs._M_singular(),
399 _M_message(__msg_iter_compare_bad)
400 ._M_iterator(__lhs, "lhs")
401 ._M_iterator(__rhs, "rhs"));
402 _GLIBCXX_DEBUG_VERIFY(__lhs._M_can_compare(__rhs),
403 _M_message(__msg_compare_different)
404 ._M_iterator(__lhs, "lhs")
405 ._M_iterator(__rhs, "rhs"));
406 _GLIBCXX_DEBUG_VERIFY(__lhs._M_in_same_bucket(__rhs),
407 _M_message(__msg_local_iter_compare_bad)
408 ._M_iterator(__lhs, "lhs")
409 ._M_iterator(__rhs, "rhs"));
410 return __lhs.base() != __rhs.base();
411 }
412
413 template<typename _Iterator, typename _Sequence>
414 inline bool
415 operator!=(const _Safe_local_iterator<_Iterator, _Sequence>& __lhs,
416 const _Safe_local_iterator<_Iterator, _Sequence>& __rhs)
417 {
418 _GLIBCXX_DEBUG_VERIFY(!__lhs._M_singular() && !__rhs._M_singular(),
419 _M_message(__msg_iter_compare_bad)
420 ._M_iterator(__lhs, "lhs")
421 ._M_iterator(__rhs, "rhs"));
422 _GLIBCXX_DEBUG_VERIFY(__lhs._M_can_compare(__rhs),
423 _M_message(__msg_compare_different)
424 ._M_iterator(__lhs, "lhs")
425 ._M_iterator(__rhs, "rhs"));
426 _GLIBCXX_DEBUG_VERIFY(__lhs._M_in_same_bucket(__rhs),
427 _M_message(__msg_local_iter_compare_bad)
428 ._M_iterator(__lhs, "lhs")
429 ._M_iterator(__rhs, "rhs"));
430 return __lhs.base() != __rhs.base();
431 }
432
433 /** Safe local iterators know if they are dereferenceable. */
434 template<typename _Iterator, typename _Sequence>
435 inline bool
437 _Sequence>& __x)
438 { return __x._M_dereferenceable(); }
439
440 /** Safe local iterators know how to check if they form a valid range. */
441 template<typename _Iterator, typename _Sequence>
442 inline bool
445 typename _Distance_traits<_Iterator>::__type& __dist_info)
446 { return __first._M_valid_range(__last, __dist_info); }
447
448 /** Safe local iterators need a special method to get distance between each
449 other. */
450 template<typename _Iterator, typename _Sequence>
456 {
457 if (__first.base() == __last.base())
458 return { 0, __dp_exact };
459
460 if (__first._M_is_begin())
461 {
462 if (__last._M_is_end())
463 return
464 {
465 __first._M_get_sequence()->bucket_size(__first.bucket()),
466 __dp_exact
467 };
468
469 return { 1, __dp_sign };
470 }
471
472 if (__first._M_is_end())
473 {
474 if (__last._M_is_begin())
475 return
476 {
477 -__first._M_get_sequence()->bucket_size(__first.bucket()),
478 __dp_exact
479 };
480
481 return { -1, __dp_sign };
482 }
483
484 if (__last._M_is_begin())
485 return { -1, __dp_sign };
486
487 if (__last._M_is_end())
488 return { 1, __dp_sign };
489
490 return { 1, __dp_equality };
491 }
492
493#if __cplusplus < 201103L
494 template<typename _Iterator, typename _Sequence>
495 struct _Unsafe_type<_Safe_local_iterator<_Iterator, _Sequence> >
496 { typedef _Iterator _Type; };
497#endif
498
499 template<typename _Iterator, typename _Sequence>
500 inline _Iterator
501 __unsafe(const _Safe_local_iterator<_Iterator, _Sequence>& __it)
502 { return __it.base(); }
503
504} // namespace __gnu_debug
505
507
508#endif
GNU debug classes for public use.
bool __valid_range(const _InputIterator &__first, const _InputIterator &__last, typename _Distance_traits< _InputIterator >::__type &__dist)
bool __check_dereferenceable(const _Iterator &)
Definition: functions.h:74
_Distance_traits< _Iterator >::__type __get_distance(const _Iterator &__lhs, const _Iterator &__rhs, std::random_access_iterator_tag)
Marking input iterators.
Struct holding two objects of arbitrary type.
Definition: stl_pair.h:199
_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_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.
_Safe_local_iterator(const _Iterator &__i, const _Safe_sequence_base *__cont)
Safe iterator construction from an unsafe iterator and its sequence.
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< std::__are_same< _MutableIterator, typename _Sequence::local_iterator::iterator_type >::__value, _Sequence >::__type > &__x)
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:232