libstdc++
safe_local_iterator.h
Go to the documentation of this file.
1 // Safe iterator implementation -*- C++ -*-
2 
3 // Copyright (C) 2011-2018 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 namespace __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>
48  class _Safe_local_iterator
49  : private _Iterator
50  , public _Safe_local_iterator_base
51  {
52  typedef _Iterator _Iter_base;
53  typedef _Safe_local_iterator_base _Safe_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();
177  _M_version = __x._M_sequence->_M_version;
178  }
179  else
180  {
181  _M_detach();
182  base() = __x.base();
183  _M_attach(__x._M_sequence);
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
241  operator->() const
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
bool _M_dereferenceable() const
Is the iterator dereferenceable?
_Safe_local_iterator & operator=(_Safe_local_iterator &&__x) noexcept
Move assignment.
Struct holding two objects of arbitrary type.
Definition: stl_pair.h:208
_Iterator & base() noexcept
Return the underlying iterator.
Marking input iterators.
pointer operator->() const
Iterator dereference.
_Safe_local_iterator(_Safe_local_iterator &&__x) noexcept
Move construction.
_Safe_local_iterator operator++(int)
Iterator postincrement.
Scoped lock idiom.
Definition: concurrence.h:231
GNU debug classes for public use.
Base class that supports tracking of iterators that reference a sequence.
Definition: safe_base.h:188
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?
void _M_attach(_Safe_sequence_base *__seq)
bool _M_incrementable() const
Is the iterator incrementable?
_Safe_local_iterator & operator=(const _Safe_local_iterator &__x)
Copy assignment.
bool _M_is_begin() const
Is this iterator equal to the sequence's begin(bucket) iterator?
reference operator*() const
Iterator dereference.
_Distance_traits< _Iterator >::__type __get_distance(const _Iterator &__lhs, const _Iterator &__rhs, std::random_access_iterator_tag)
void _M_attach_single(_Safe_sequence_base *__seq)
_Safe_local_iterator(const _Safe_local_iterator &__x) noexcept
Copy construction.
_Safe_sequence_base * _M_sequence
Definition: safe_base.h:57
bool __valid_range(const _InputIterator &__first, const _InputIterator &__last, typename _Distance_traits< _InputIterator >::__type &__dist)
_Safe_local_iterator(const _Iterator &__i, const _Safe_sequence_base *__cont)
Safe iterator construction from an unsafe iterator and its sequence.
bool __check_dereferenceable(const _Iterator &)
Definition: functions.h:74
void _M_attach(_Safe_sequence_base *__seq, bool __constant)
_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.
size_type bucket() const
Return the bucket.
_Safe_local_iterator & operator++()
Iterator preincrement.
Safe iterator wrapper.
Definition: formatter.h:59
Basic functionality for a safe iterator.
void _M_attach_single(_Safe_sequence_base *__seq, bool __constant)
__gnu_cxx::__mutex & _M_get_mutex()
bool _M_is_end() const
Is this iterator equal to the sequence's end(bucket) iterator?