libstdc++
safe_local_iterator.h
Go to the documentation of this file.
1 // Safe iterator implementation -*- C++ -*-
2 
3 // Copyright (C) 2011-2023 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._M_value_initialized() \
37  && _Rhs._M_value_initialized()), \
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 
50 namespace __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>
64  class _Safe_local_iterator
65  : private _Iterator
66  , public _Safe_local_iterator_base
67  {
68  typedef _Iterator _Iter_base;
69  typedef _Safe_local_iterator_base _Safe_base;
70 
71  typedef typename _Sequence::size_type size_type;
72 
73  typedef std::iterator_traits<_Iterator> _Traits;
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 
84  typedef _Safe_local_iterator _Self;
85  typedef _Safe_local_iterator<_OtherIterator, _Sequence> _OtherSelf;
86 
87  struct _Unchecked { };
88 
90  _Unchecked) noexcept
91  : _Iter_base(__x.base())
92  { _M_attach(__x._M_sequence); }
93 
94  public:
95  typedef _Iterator iterator_type;
96  typedef typename _Traits::iterator_category iterator_category;
97  typedef typename _Traits::value_type value_type;
98  typedef typename _Traits::difference_type difference_type;
99  typedef typename _Traits::reference reference;
100  typedef typename _Traits::pointer pointer;
101 
102  /// @post the iterator is singular and unattached
103  _Safe_local_iterator() noexcept : _Iter_base() { }
104 
105  /**
106  * @brief Safe iterator construction from an unsafe iterator and
107  * its sequence.
108  *
109  * @pre @p seq is not NULL
110  * @post this is not singular
111  */
113  : _Iter_base(__i), _Safe_base(__cont, _S_constant())
114  { }
115 
116  /**
117  * @brief Copy construction.
118  */
120  : _Iter_base(__x.base())
121  {
122  // _GLIBCXX_RESOLVE_LIB_DEFECTS
123  // DR 408. Is vector<reverse_iterator<char*> > forbidden?
124  _GLIBCXX_DEBUG_VERIFY(!__x._M_singular()
125  || __x._M_value_initialized(),
126  _M_message(__msg_init_copy_singular)
127  ._M_iterator(*this, "this")
128  ._M_iterator(__x, "other"));
129  _M_attach(__x._M_sequence);
130  }
131 
132  /**
133  * @brief Move construction.
134  * @post __x is singular and unattached
135  */
137  : _Iter_base()
138  {
139  _GLIBCXX_DEBUG_VERIFY(!__x._M_singular()
140  || __x._M_value_initialized(),
141  _M_message(__msg_init_copy_singular)
142  ._M_iterator(*this, "this")
143  ._M_iterator(__x, "other"));
144  auto __cont = __x._M_sequence;
145  __x._M_detach();
146  std::swap(base(), __x.base());
147  _M_attach(__cont);
148  }
149 
150  /**
151  * @brief Converting constructor from a mutable iterator to a
152  * constant iterator.
153  */
154  template<typename _MutableIterator>
156  const _Safe_local_iterator<_MutableIterator,
157  typename __gnu_cxx::__enable_if<_IsConstant::__value &&
158  std::__are_same<_MutableIterator, _OtherIterator>::__value,
159  _Sequence>::__type>& __x) noexcept
160  : _Iter_base(__x.base())
161  {
162  // _GLIBCXX_RESOLVE_LIB_DEFECTS
163  // DR 408. Is vector<reverse_iterator<char*> > forbidden?
164  _GLIBCXX_DEBUG_VERIFY(!__x._M_singular()
165  || __x._M_value_initialized(),
166  _M_message(__msg_init_const_singular)
167  ._M_iterator(*this, "this")
168  ._M_iterator(__x, "other"));
169  _M_attach(__x._M_sequence);
170  }
171 
172  /**
173  * @brief Copy assignment.
174  */
177  {
178  // _GLIBCXX_RESOLVE_LIB_DEFECTS
179  // DR 408. Is vector<reverse_iterator<char*> > forbidden?
180  _GLIBCXX_DEBUG_VERIFY(!__x._M_singular()
181  || __x._M_value_initialized(),
182  _M_message(__msg_copy_singular)
183  ._M_iterator(*this, "this")
184  ._M_iterator(__x, "other"));
185 
186  if (this->_M_sequence && this->_M_sequence == __x._M_sequence)
187  {
189  base() = __x.base();
190  _M_version = __x._M_sequence->_M_version;
191  }
192  else
193  {
194  _M_detach();
195  base() = __x.base();
196  _M_attach(__x._M_sequence);
197  }
198 
199  return *this;
200  }
201 
202  /**
203  * @brief Move assignment.
204  * @post __x is singular and unattached
205  */
208  {
209  _GLIBCXX_DEBUG_VERIFY(!__x._M_singular()
210  || __x._M_value_initialized(),
211  _M_message(__msg_copy_singular)
212  ._M_iterator(*this, "this")
213  ._M_iterator(__x, "other"));
214 
215  if (std::__addressof(__x) == this)
216  return *this;
217 
218  if (this->_M_sequence && this->_M_sequence == __x._M_sequence)
219  {
221  base() = __x.base();
222  _M_version = __x._M_sequence->_M_version;
223  }
224  else
225  {
226  _M_detach();
227  base() = __x.base();
228  _M_attach(__x._M_sequence);
229  }
230 
231  __x._M_detach();
232  __x.base() = _Iterator();
233  return *this;
234  }
235 
236  /**
237  * @brief Iterator dereference.
238  * @pre iterator is dereferenceable
239  */
240  reference
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();
247  }
248 
249  /**
250  * @brief Iterator dereference.
251  * @pre iterator is dereferenceable
252  */
253  pointer
254  operator->() const
255  {
256  _GLIBCXX_DEBUG_VERIFY(this->_M_dereferenceable(),
257  _M_message(__msg_bad_deref)
258  ._M_iterator(*this, "this"));
259  return base().operator->();
260  }
261 
262  // ------ Input iterator requirements ------
263  /**
264  * @brief Iterator preincrement
265  * @pre iterator is incrementable
266  */
269  {
270  _GLIBCXX_DEBUG_VERIFY(this->_M_incrementable(),
271  _M_message(__msg_bad_inc)
272  ._M_iterator(*this, "this"));
274  ++base();
275  return *this;
276  }
277 
278  /**
279  * @brief Iterator postincrement
280  * @pre iterator is incrementable
281  */
284  {
285  _GLIBCXX_DEBUG_VERIFY(this->_M_incrementable(),
286  _M_message(__msg_bad_inc)
287  ._M_iterator(*this, "this"));
288  _Safe_local_iterator __ret(*this, _Unchecked{});
289  ++*this;
290  return __ret;
291  }
292 
293  // ------ Utilities ------
294 
295  /// Determine if this is a constant iterator.
296  static constexpr bool
298  { return _IsConstant::__value; }
299 
300  /**
301  * @brief Return the underlying iterator
302  */
303  _Iterator&
304  base() noexcept { return *this; }
305 
306  const _Iterator&
307  base() const noexcept { return *this; }
308 
309  /**
310  * @brief Return the bucket
311  */
312  size_type
313  bucket() const { return base()._M_get_bucket(); }
314 
315  /**
316  * @brief Conversion to underlying non-debug iterator to allow
317  * better interaction with non-debug containers.
318  */
319  operator _Iterator() const { return *this; }
320 
321  /** Attach iterator to the given sequence. */
322  void
324  { _Safe_base::_M_attach(__seq, _S_constant()); }
325 
326  /** Likewise, but not thread-safe. */
327  void
330 
331  /// Is the iterator dereferenceable?
332  bool
334  { return !this->_M_singular() && !_M_is_end(); }
335 
336  /// Is the iterator incrementable?
337  bool
339  { return !this->_M_singular() && !_M_is_end(); }
340 
341  /// Is the iterator value-initialized?
342  bool
344  { return _M_version == 0 && base() == _Iter_base{}; }
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
_Safe_local_iterator & operator=(const _Safe_local_iterator &__x)
Copy assignment.
pointer operator->() const
Iterator dereference.
Basic functionality for a safe iterator.
bool _M_value_initialized() const
Is the iterator value-initialized?
constexpr _Tp * __addressof(_Tp &__r) noexcept
Same as C++11 std::addressof.
Definition: move.h:51
bool _M_incrementable() const
Is the iterator incrementable?
_Safe_sequence_base * _M_sequence
Definition: safe_base.h:57
Scoped lock idiom.
Definition: concurrence.h:228
void _M_attach_single(_Safe_sequence_base *__seq, bool __constant)
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?
_Iterator & base() noexcept
Return the underlying iterator.
Struct holding two objects of arbitrary type.
bool _M_is_end() const
Is this iterator equal to the sequence&#39;s end(bucket) iterator?
void _M_attach(_Safe_sequence_base *__seq)
size_type bucket() const
Return the bucket.
reference operator*() const
Iterator dereference.
void _M_attach_single(_Safe_sequence_base *__seq)
_Safe_local_iterator & operator++()
Iterator preincrement.
Safe iterator wrapper.
Definition: formatter.h:100
Traits class for iterators.
ISO C++ entities toplevel namespace is std.
__gnu_cxx::__mutex & _M_get_mutex()
constexpr bool __valid_range(_InputIterator __first, _InputIterator __last, typename _Distance_traits< _InputIterator >::__type &__dist)
bool _M_dereferenceable() const
Is the iterator dereferenceable?
static constexpr bool _S_constant()
Determine if this is a constant iterator.
_Safe_local_iterator operator++(int)
Iterator postincrement.
void _M_attach(_Safe_sequence_base *__seq, bool __constant)
Base class that supports tracking of iterators that reference a sequence.
Definition: safe_base.h:188
_Safe_local_iterator(const _Safe_local_iterator &__x) noexcept
Copy construction.
_Safe_local_iterator(_Safe_local_iterator &&__x) noexcept
Move construction.
_Safe_local_iterator & operator=(_Safe_local_iterator &&__x) noexcept
Move assignment.
GNU debug classes for public use.
bool _M_is_begin() const
Is this iterator equal to the sequence&#39;s begin(bucket) iterator?
_Safe_local_iterator(_Iterator __i, const _Safe_sequence_base *__cont)
Safe iterator construction from an unsafe iterator and its sequence.
_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.