libstdc++
safe_local_iterator.h
Go to the documentation of this file.
1// Safe iterator implementation -*- C++ -*-
2
3// Copyright (C) 2011-2016 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 * @todo Make this correct w.r.t. iterators that return proxies
240 */
241 pointer
243 {
244 _GLIBCXX_DEBUG_VERIFY(this->_M_dereferenceable(),
245 _M_message(__msg_bad_deref)
246 ._M_iterator(*this, "this"));
247 return std::__addressof(*base());
248 }
249
250 // ------ Input iterator requirements ------
251 /**
252 * @brief Iterator preincrement
253 * @pre iterator is incrementable
254 */
257 {
258 _GLIBCXX_DEBUG_VERIFY(this->_M_incrementable(),
259 _M_message(__msg_bad_inc)
260 ._M_iterator(*this, "this"));
262 ++base();
263 return *this;
264 }
265
266 /**
267 * @brief Iterator postincrement
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 return _Safe_local_iterator(base()++, this->_M_sequence,
278 _Attach_single());
279 }
280
281 // ------ Utilities ------
282 /**
283 * @brief Return the underlying iterator
284 */
285 _Iterator&
286 base() noexcept { return *this; }
287
288 const _Iterator&
289 base() const noexcept { return *this; }
290
291 /**
292 * @brief Return the bucket
293 */
294 size_type
295 bucket() const { return base()._M_get_bucket(); }
296
297 /**
298 * @brief Conversion to underlying non-debug iterator to allow
299 * better interaction with non-debug containers.
300 */
301 operator _Iterator() const { return *this; }
302
303 /** Attach iterator to the given sequence. */
304 void
306 { _Safe_base::_M_attach(__seq, _M_constant()); }
307
308 /** Likewise, but not thread-safe. */
309 void
312
313 /// Is the iterator dereferenceable?
314 bool
316 { return !this->_M_singular() && !_M_is_end(); }
317
318 /// Is the iterator incrementable?
319 bool
321 { return !this->_M_singular() && !_M_is_end(); }
322
323 // Is the iterator range [*this, __rhs) valid?
324 bool
325 _M_valid_range(const _Safe_local_iterator& __rhs,
326 std::pair<difference_type,
327 _Distance_precision>& __dist_info) const;
328
329 // The sequence this iterator references.
330 typename
331 __gnu_cxx::__conditional_type<std::__are_same<_Const_local_iterator,
332 _Safe_local_iterator>::__value,
333 const _Sequence*,
334 _Sequence*>::__type
335 _M_get_sequence() const
336 { return static_cast<_Sequence*>(_M_sequence); }
337
338 /// Is this iterator equal to the sequence's begin(bucket) iterator?
339 bool _M_is_begin() const
340 { return base() == _M_get_sequence()->_M_base().begin(bucket()); }
341
342 /// Is this iterator equal to the sequence's end(bucket) iterator?
343 bool _M_is_end() const
344 { return base() == _M_get_sequence()->_M_base().end(bucket()); }
345
346 /// Is this iterator part of the same bucket as the other one?
347 template<typename _Other>
348 bool
350 _Sequence>& __other) const
351 { return bucket() == __other.bucket(); }
352 };
353
354 template<typename _IteratorL, typename _IteratorR, typename _Sequence>
355 inline bool
356 operator==(const _Safe_local_iterator<_IteratorL, _Sequence>& __lhs,
357 const _Safe_local_iterator<_IteratorR, _Sequence>& __rhs)
358 {
359 _GLIBCXX_DEBUG_VERIFY(!__lhs._M_singular() && !__rhs._M_singular(),
360 _M_message(__msg_iter_compare_bad)
361 ._M_iterator(__lhs, "lhs")
362 ._M_iterator(__rhs, "rhs"));
363 _GLIBCXX_DEBUG_VERIFY(__lhs._M_can_compare(__rhs),
364 _M_message(__msg_compare_different)
365 ._M_iterator(__lhs, "lhs")
366 ._M_iterator(__rhs, "rhs"));
367 _GLIBCXX_DEBUG_VERIFY(__lhs._M_in_same_bucket(__rhs),
368 _M_message(__msg_local_iter_compare_bad)
369 ._M_iterator(__lhs, "lhs")
370 ._M_iterator(__rhs, "rhs"));
371 return __lhs.base() == __rhs.base();
372 }
373
374 template<typename _Iterator, typename _Sequence>
375 inline bool
376 operator==(const _Safe_local_iterator<_Iterator, _Sequence>& __lhs,
377 const _Safe_local_iterator<_Iterator, _Sequence>& __rhs)
378 {
379 _GLIBCXX_DEBUG_VERIFY(!__lhs._M_singular() && !__rhs._M_singular(),
380 _M_message(__msg_iter_compare_bad)
381 ._M_iterator(__lhs, "lhs")
382 ._M_iterator(__rhs, "rhs"));
383 _GLIBCXX_DEBUG_VERIFY(__lhs._M_can_compare(__rhs),
384 _M_message(__msg_compare_different)
385 ._M_iterator(__lhs, "lhs")
386 ._M_iterator(__rhs, "rhs"));
387 _GLIBCXX_DEBUG_VERIFY(__lhs._M_in_same_bucket(__rhs),
388 _M_message(__msg_local_iter_compare_bad)
389 ._M_iterator(__lhs, "lhs")
390 ._M_iterator(__rhs, "rhs"));
391 return __lhs.base() == __rhs.base();
392 }
393
394 template<typename _IteratorL, typename _IteratorR, typename _Sequence>
395 inline bool
396 operator!=(const _Safe_local_iterator<_IteratorL, _Sequence>& __lhs,
397 const _Safe_local_iterator<_IteratorR, _Sequence>& __rhs)
398 {
399 _GLIBCXX_DEBUG_VERIFY(! __lhs._M_singular() && ! __rhs._M_singular(),
400 _M_message(__msg_iter_compare_bad)
401 ._M_iterator(__lhs, "lhs")
402 ._M_iterator(__rhs, "rhs"));
403 _GLIBCXX_DEBUG_VERIFY(__lhs._M_can_compare(__rhs),
404 _M_message(__msg_compare_different)
405 ._M_iterator(__lhs, "lhs")
406 ._M_iterator(__rhs, "rhs"));
407 _GLIBCXX_DEBUG_VERIFY(__lhs._M_in_same_bucket(__rhs),
408 _M_message(__msg_local_iter_compare_bad)
409 ._M_iterator(__lhs, "lhs")
410 ._M_iterator(__rhs, "rhs"));
411 return __lhs.base() != __rhs.base();
412 }
413
414 template<typename _Iterator, typename _Sequence>
415 inline bool
416 operator!=(const _Safe_local_iterator<_Iterator, _Sequence>& __lhs,
417 const _Safe_local_iterator<_Iterator, _Sequence>& __rhs)
418 {
419 _GLIBCXX_DEBUG_VERIFY(!__lhs._M_singular() && !__rhs._M_singular(),
420 _M_message(__msg_iter_compare_bad)
421 ._M_iterator(__lhs, "lhs")
422 ._M_iterator(__rhs, "rhs"));
423 _GLIBCXX_DEBUG_VERIFY(__lhs._M_can_compare(__rhs),
424 _M_message(__msg_compare_different)
425 ._M_iterator(__lhs, "lhs")
426 ._M_iterator(__rhs, "rhs"));
427 _GLIBCXX_DEBUG_VERIFY(__lhs._M_in_same_bucket(__rhs),
428 _M_message(__msg_local_iter_compare_bad)
429 ._M_iterator(__lhs, "lhs")
430 ._M_iterator(__rhs, "rhs"));
431 return __lhs.base() != __rhs.base();
432 }
433
434 /** Safe local iterators know if they are dereferenceable. */
435 template<typename _Iterator, typename _Sequence>
436 inline bool
438 _Sequence>& __x)
439 { return __x._M_dereferenceable(); }
440
441 /** Safe local iterators know how to check if they form a valid range. */
442 template<typename _Iterator, typename _Sequence>
443 inline bool
446 typename _Distance_traits<_Iterator>::__type& __dist_info)
447 { return __first._M_valid_range(__last, __dist_info); }
448
449 /** Safe local iterators need a special method to get distance between each
450 other. */
451 template<typename _Iterator, typename _Sequence>
457 {
458 if (__first.base() == __last.base())
459 return { 0, __dp_exact };
460
461 if (__first._M_is_begin())
462 {
463 if (__last._M_is_end())
464 return
465 {
466 __first._M_get_sequence()->bucket_size(__first.bucket()),
467 __dp_exact
468 };
469
470 return { 1, __dp_sign };
471 }
472
473 if (__first._M_is_end())
474 {
475 if (__last._M_is_begin())
476 return
477 {
478 -__first._M_get_sequence()->bucket_size(__first.bucket()),
479 __dp_exact
480 };
481
482 return { -1, __dp_sign };
483 }
484
485 if (__last._M_is_begin())
486 return { -1, __dp_sign };
487
488 if (__last._M_is_end())
489 return { 1, __dp_sign };
490
491 return { 1, __dp_equality };
492 }
493
494#if __cplusplus < 201103L
495 template<typename _Iterator, typename _Sequence>
496 struct _Unsafe_type<_Safe_local_iterator<_Iterator, _Sequence> >
497 { typedef _Iterator _Type; };
498#endif
499
500 template<typename _Iterator, typename _Sequence>
501 inline _Iterator
502 __unsafe(const _Safe_local_iterator<_Iterator, _Sequence>& __it)
503 { return __it.base(); }
504
505} // namespace __gnu_debug
506
508
509#endif
_Tp * __addressof(_Tp &__r) noexcept
Same as C++11 std::addressof.
Definition move.h:47
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:75
_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:206
_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:55
__gnu_cxx::__mutex & _M_get_mutex()
Base class that supports tracking of iterators that reference a sequence.
Definition safe_base.h:187
void _M_detach(_Safe_iterator_base *__it)
unsigned int _M_version
The container version number. This number may never be 0.
Definition safe_base.h:196
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.