libstdc++
safe_iterator.h
Go to the documentation of this file.
1 // Safe iterator implementation -*- C++ -*-
2 
3 // Copyright (C) 2003-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_iterator.h
26  * This file is a GNU debug extension to the Standard C++ Library.
27  */
28 
29 #ifndef _GLIBCXX_DEBUG_SAFE_ITERATOR_H
30 #define _GLIBCXX_DEBUG_SAFE_ITERATOR_H 1
31 
32 #include <debug/assertions.h>
33 #include <debug/macros.h>
34 #include <debug/functions.h>
35 #include <debug/safe_base.h>
36 #include <bits/stl_pair.h>
37 #include <ext/type_traits.h>
38 
39 namespace __gnu_debug
40 {
41  /** Helper struct to deal with sequence offering a before_begin
42  * iterator.
43  **/
44  template<typename _Sequence>
46  {
47  template<typename _Iterator>
48  static bool
50  { return false; }
51 
52  template<typename _Iterator>
53  static bool
54  _S_Is_Beginnest(const _Safe_iterator<_Iterator, _Sequence>& __it)
55  { return __it.base() == __it._M_get_sequence()->_M_base().begin(); }
56  };
57 
58  /** Sequence traits giving the size of a container if possible. */
59  template<typename _Sequence>
61  {
62  typedef _Distance_traits<typename _Sequence::iterator> _DistTraits;
63 
64  static typename _DistTraits::__type
65  _S_size(const _Sequence& __seq)
66  { return std::make_pair(__seq.size(), __dp_exact); }
67  };
68 
69  /** \brief Safe iterator wrapper.
70  *
71  * The class template %_Safe_iterator is a wrapper around an
72  * iterator that tracks the iterator's movement among sequences and
73  * checks that operations performed on the "safe" iterator are
74  * legal. In additional to the basic iterator operations (which are
75  * validated, and then passed to the underlying iterator),
76  * %_Safe_iterator has member functions for iterator invalidation,
77  * attaching/detaching the iterator from sequences, and querying
78  * the iterator's state.
79  *
80  * Note that _Iterator must be the first base class so that it gets
81  * initialized before the iterator is being attached to the container's list
82  * of iterators and it is being detached before _Iterator get
83  * destroyed. Otherwise it would result in a data race.
84  */
85  template<typename _Iterator, typename _Sequence>
86  class _Safe_iterator
87  : private _Iterator,
88  public _Safe_iterator_base
89  {
90  typedef _Iterator _Iter_base;
91  typedef _Safe_iterator_base _Safe_base;
92  typedef typename _Sequence::const_iterator _Const_iterator;
93 
94  /// Determine if this is a constant iterator.
95  bool
96  _M_constant() const
97  { return std::__are_same<_Const_iterator, _Safe_iterator>::__value; }
98 
99  typedef std::iterator_traits<_Iterator> _Traits;
100 
101  struct _Attach_single
102  { };
103 
104  _Safe_iterator(const _Iterator& __i, _Safe_sequence_base* __seq,
105  _Attach_single)
106  _GLIBCXX_NOEXCEPT
107  : _Iter_base(__i)
108  { _M_attach_single(__seq); }
109 
110  public:
111  typedef _Iterator iterator_type;
112  typedef typename _Traits::iterator_category iterator_category;
113  typedef typename _Traits::value_type value_type;
114  typedef typename _Traits::difference_type difference_type;
115  typedef typename _Traits::reference reference;
116  typedef typename _Traits::pointer pointer;
117 
118  /// @post the iterator is singular and unattached
119  _Safe_iterator() _GLIBCXX_NOEXCEPT : _Iter_base() { }
120 
121  /**
122  * @brief Safe iterator construction from an unsafe iterator and
123  * its sequence.
124  *
125  * @pre @p seq is not NULL
126  * @post this is not singular
127  */
128  _Safe_iterator(const _Iterator& __i, const _Safe_sequence_base* __seq)
129  _GLIBCXX_NOEXCEPT
130  : _Iter_base(__i), _Safe_base(__seq, _M_constant())
131  {
132  _GLIBCXX_DEBUG_VERIFY(!this->_M_singular(),
133  _M_message(__msg_init_singular)
134  ._M_iterator(*this, "this"));
135  }
136 
137  /**
138  * @brief Copy construction.
139  */
140  _Safe_iterator(const _Safe_iterator& __x) _GLIBCXX_NOEXCEPT
141  : _Iter_base(__x.base())
142  {
143  // _GLIBCXX_RESOLVE_LIB_DEFECTS
144  // DR 408. Is vector<reverse_iterator<char*> > forbidden?
145  _GLIBCXX_DEBUG_VERIFY(!__x._M_singular()
146  || __x.base() == _Iterator(),
147  _M_message(__msg_init_copy_singular)
148  ._M_iterator(*this, "this")
149  ._M_iterator(__x, "other"));
150  _M_attach(__x._M_sequence);
151  }
152 
153 #if __cplusplus >= 201103L
154  /**
155  * @brief Move construction.
156  * @post __x is singular and unattached
157  */
159  : _Iter_base()
160  {
161  _GLIBCXX_DEBUG_VERIFY(!__x._M_singular()
162  || __x.base() == _Iterator(),
163  _M_message(__msg_init_copy_singular)
164  ._M_iterator(*this, "this")
165  ._M_iterator(__x, "other"));
166  _Safe_sequence_base* __seq = __x._M_sequence;
167  __x._M_detach();
168  std::swap(base(), __x.base());
169  _M_attach(__seq);
170  }
171 #endif
172 
173  /**
174  * @brief Converting constructor from a mutable iterator to a
175  * constant iterator.
176  */
177  template<typename _MutableIterator>
179  const _Safe_iterator<_MutableIterator,
180  typename __gnu_cxx::__enable_if<(std::__are_same<_MutableIterator,
181  typename _Sequence::iterator::iterator_type>::__value),
182  _Sequence>::__type>& __x) _GLIBCXX_NOEXCEPT
183  : _Iter_base(__x.base())
184  {
185  // _GLIBCXX_RESOLVE_LIB_DEFECTS
186  // DR 408. Is vector<reverse_iterator<char*> > forbidden?
187  _GLIBCXX_DEBUG_VERIFY(!__x._M_singular()
188  || __x.base() == _Iterator(),
189  _M_message(__msg_init_const_singular)
190  ._M_iterator(*this, "this")
191  ._M_iterator(__x, "other"));
192  _M_attach(__x._M_sequence);
193  }
194 
195  /**
196  * @brief Copy assignment.
197  */
199  operator=(const _Safe_iterator& __x) _GLIBCXX_NOEXCEPT
200  {
201  // _GLIBCXX_RESOLVE_LIB_DEFECTS
202  // DR 408. Is vector<reverse_iterator<char*> > forbidden?
203  _GLIBCXX_DEBUG_VERIFY(!__x._M_singular()
204  || __x.base() == _Iterator(),
205  _M_message(__msg_copy_singular)
206  ._M_iterator(*this, "this")
207  ._M_iterator(__x, "other"));
208 
209  if (this->_M_sequence && this->_M_sequence == __x._M_sequence)
210  {
212  base() = __x.base();
213  _M_version = __x._M_sequence->_M_version;
214  }
215  else
216  {
217  _M_detach();
218  base() = __x.base();
219  _M_attach(__x._M_sequence);
220  }
221 
222  return *this;
223  }
224 
225 #if __cplusplus >= 201103L
226  /**
227  * @brief Move assignment.
228  * @post __x is singular and unattached
229  */
231  operator=(_Safe_iterator&& __x) noexcept
232  {
233  _GLIBCXX_DEBUG_VERIFY(this != &__x,
234  _M_message(__msg_self_move_assign)
235  ._M_iterator(*this, "this"));
236  _GLIBCXX_DEBUG_VERIFY(!__x._M_singular()
237  || __x.base() == _Iterator(),
238  _M_message(__msg_copy_singular)
239  ._M_iterator(*this, "this")
240  ._M_iterator(__x, "other"));
241 
242  if (this->_M_sequence && this->_M_sequence == __x._M_sequence)
243  {
245  base() = __x.base();
246  _M_version = __x._M_sequence->_M_version;
247  }
248  else
249  {
250  _M_detach();
251  base() = __x.base();
252  _M_attach(__x._M_sequence);
253  }
254 
255  __x._M_detach();
256  __x.base() = _Iterator();
257  return *this;
258  }
259 #endif
260 
261  /**
262  * @brief Iterator dereference.
263  * @pre iterator is dereferenceable
264  */
265  reference
266  operator*() const _GLIBCXX_NOEXCEPT
267  {
268  _GLIBCXX_DEBUG_VERIFY(this->_M_dereferenceable(),
269  _M_message(__msg_bad_deref)
270  ._M_iterator(*this, "this"));
271  return *base();
272  }
273 
274  /**
275  * @brief Iterator dereference.
276  * @pre iterator is dereferenceable
277  */
278  pointer
279  operator->() const _GLIBCXX_NOEXCEPT
280  {
281  _GLIBCXX_DEBUG_VERIFY(this->_M_dereferenceable(),
282  _M_message(__msg_bad_deref)
283  ._M_iterator(*this, "this"));
284  return base().operator->();
285  }
286 
287  // ------ Input iterator requirements ------
288  /**
289  * @brief Iterator preincrement
290  * @pre iterator is incrementable
291  */
293  operator++() _GLIBCXX_NOEXCEPT
294  {
295  _GLIBCXX_DEBUG_VERIFY(this->_M_incrementable(),
296  _M_message(__msg_bad_inc)
297  ._M_iterator(*this, "this"));
299  ++base();
300  return *this;
301  }
302 
303  /**
304  * @brief Iterator postincrement
305  * @pre iterator is incrementable
306  */
308  operator++(int) _GLIBCXX_NOEXCEPT
309  {
310  _GLIBCXX_DEBUG_VERIFY(this->_M_incrementable(),
311  _M_message(__msg_bad_inc)
312  ._M_iterator(*this, "this"));
314  return _Safe_iterator(base()++, this->_M_sequence, _Attach_single());
315  }
316 
317  // ------ Bidirectional iterator requirements ------
318  /**
319  * @brief Iterator predecrement
320  * @pre iterator is decrementable
321  */
323  operator--() _GLIBCXX_NOEXCEPT
324  {
325  _GLIBCXX_DEBUG_VERIFY(this->_M_decrementable(),
326  _M_message(__msg_bad_dec)
327  ._M_iterator(*this, "this"));
329  --base();
330  return *this;
331  }
332 
333  /**
334  * @brief Iterator postdecrement
335  * @pre iterator is decrementable
336  */
338  operator--(int) _GLIBCXX_NOEXCEPT
339  {
340  _GLIBCXX_DEBUG_VERIFY(this->_M_decrementable(),
341  _M_message(__msg_bad_dec)
342  ._M_iterator(*this, "this"));
344  return _Safe_iterator(base()--, this->_M_sequence, _Attach_single());
345  }
346 
347  // ------ Random access iterator requirements ------
348  reference
349  operator[](const difference_type& __n) const _GLIBCXX_NOEXCEPT
350  {
351  _GLIBCXX_DEBUG_VERIFY(this->_M_can_advance(__n)
352  && this->_M_can_advance(__n+1),
353  _M_message(__msg_iter_subscript_oob)
354  ._M_iterator(*this)._M_integer(__n));
355  return base()[__n];
356  }
357 
359  operator+=(const difference_type& __n) _GLIBCXX_NOEXCEPT
360  {
361  _GLIBCXX_DEBUG_VERIFY(this->_M_can_advance(__n),
362  _M_message(__msg_advance_oob)
363  ._M_iterator(*this)._M_integer(__n));
365  base() += __n;
366  return *this;
367  }
368 
370  operator+(const difference_type& __n) const _GLIBCXX_NOEXCEPT
371  {
372  _GLIBCXX_DEBUG_VERIFY(this->_M_can_advance(__n),
373  _M_message(__msg_advance_oob)
374  ._M_iterator(*this)._M_integer(__n));
375  return _Safe_iterator(base() + __n, this->_M_sequence);
376  }
377 
379  operator-=(const difference_type& __n) _GLIBCXX_NOEXCEPT
380  {
381  _GLIBCXX_DEBUG_VERIFY(this->_M_can_advance(-__n),
382  _M_message(__msg_retreat_oob)
383  ._M_iterator(*this)._M_integer(__n));
385  base() -= __n;
386  return *this;
387  }
388 
390  operator-(const difference_type& __n) const _GLIBCXX_NOEXCEPT
391  {
392  _GLIBCXX_DEBUG_VERIFY(this->_M_can_advance(-__n),
393  _M_message(__msg_retreat_oob)
394  ._M_iterator(*this)._M_integer(__n));
395  return _Safe_iterator(base() - __n, this->_M_sequence);
396  }
397 
398  // ------ Utilities ------
399  /**
400  * @brief Return the underlying iterator
401  */
402  _Iterator&
403  base() _GLIBCXX_NOEXCEPT { return *this; }
404 
405  const _Iterator&
406  base() const _GLIBCXX_NOEXCEPT { return *this; }
407 
408  /**
409  * @brief Conversion to underlying non-debug iterator to allow
410  * better interaction with non-debug containers.
411  */
412  operator _Iterator() const _GLIBCXX_NOEXCEPT { return *this; }
413 
414  /** Attach iterator to the given sequence. */
415  void
417  { _Safe_base::_M_attach(__seq, _M_constant()); }
418 
419  /** Likewise, but not thread-safe. */
420  void
422  { _Safe_base::_M_attach_single(__seq, _M_constant()); }
423 
424  /// Is the iterator dereferenceable?
425  bool
427  { return !this->_M_singular() && !_M_is_end() && !_M_is_before_begin(); }
428 
429  /// Is the iterator before a dereferenceable one?
430  bool
432  {
433  if (this->_M_incrementable())
434  {
435  _Iterator __base = base();
436  return ++__base != _M_get_sequence()->_M_base().end();
437  }
438  return false;
439  }
440 
441  /// Is the iterator incrementable?
442  bool
444  { return !this->_M_singular() && !_M_is_end(); }
445 
446  // Is the iterator decrementable?
447  bool
448  _M_decrementable() const { return !_M_singular() && !_M_is_begin(); }
449 
450  // Can we advance the iterator @p __n steps (@p __n may be negative)
451  bool
452  _M_can_advance(const difference_type& __n) const;
453 
454  // Is the iterator range [*this, __rhs) valid?
455  bool
456  _M_valid_range(const _Safe_iterator& __rhs,
458  bool __check_dereferenceable = true) const;
459 
460  // The sequence this iterator references.
461  typename
462  __gnu_cxx::__conditional_type<std::__are_same<_Const_iterator,
463  _Safe_iterator>::__value,
464  const _Sequence*,
465  _Sequence*>::__type
466  _M_get_sequence() const
467  { return static_cast<_Sequence*>(_M_sequence); }
468 
469  /// Is this iterator equal to the sequence's begin() iterator?
470  bool
471  _M_is_begin() const
472  { return base() == _M_get_sequence()->_M_base().begin(); }
473 
474  /// Is this iterator equal to the sequence's end() iterator?
475  bool
476  _M_is_end() const
477  { return base() == _M_get_sequence()->_M_base().end(); }
478 
479  /// Is this iterator equal to the sequence's before_begin() iterator if
480  /// any?
481  bool
483  { return _BeforeBeginHelper<_Sequence>::_S_Is(*this); }
484 
485  /// Is this iterator equal to the sequence's before_begin() iterator if
486  /// any or begin() otherwise?
487  bool
490  };
491 
492  template<typename _IteratorL, typename _IteratorR, typename _Sequence>
493  inline bool
494  operator==(const _Safe_iterator<_IteratorL, _Sequence>& __lhs,
495  const _Safe_iterator<_IteratorR, _Sequence>& __rhs)
496  _GLIBCXX_NOEXCEPT
497  {
498  _GLIBCXX_DEBUG_VERIFY(! __lhs._M_singular() && ! __rhs._M_singular(),
499  _M_message(__msg_iter_compare_bad)
500  ._M_iterator(__lhs, "lhs")
501  ._M_iterator(__rhs, "rhs"));
502  _GLIBCXX_DEBUG_VERIFY(__lhs._M_can_compare(__rhs),
503  _M_message(__msg_compare_different)
504  ._M_iterator(__lhs, "lhs")
505  ._M_iterator(__rhs, "rhs"));
506  return __lhs.base() == __rhs.base();
507  }
508 
509  template<typename _Iterator, typename _Sequence>
510  inline bool
511  operator==(const _Safe_iterator<_Iterator, _Sequence>& __lhs,
512  const _Safe_iterator<_Iterator, _Sequence>& __rhs)
513  _GLIBCXX_NOEXCEPT
514  {
515  _GLIBCXX_DEBUG_VERIFY(! __lhs._M_singular() && ! __rhs._M_singular(),
516  _M_message(__msg_iter_compare_bad)
517  ._M_iterator(__lhs, "lhs")
518  ._M_iterator(__rhs, "rhs"));
519  _GLIBCXX_DEBUG_VERIFY(__lhs._M_can_compare(__rhs),
520  _M_message(__msg_compare_different)
521  ._M_iterator(__lhs, "lhs")
522  ._M_iterator(__rhs, "rhs"));
523  return __lhs.base() == __rhs.base();
524  }
525 
526  template<typename _IteratorL, typename _IteratorR, typename _Sequence>
527  inline bool
528  operator!=(const _Safe_iterator<_IteratorL, _Sequence>& __lhs,
529  const _Safe_iterator<_IteratorR, _Sequence>& __rhs)
530  _GLIBCXX_NOEXCEPT
531  {
532  _GLIBCXX_DEBUG_VERIFY(! __lhs._M_singular() && ! __rhs._M_singular(),
533  _M_message(__msg_iter_compare_bad)
534  ._M_iterator(__lhs, "lhs")
535  ._M_iterator(__rhs, "rhs"));
536  _GLIBCXX_DEBUG_VERIFY(__lhs._M_can_compare(__rhs),
537  _M_message(__msg_compare_different)
538  ._M_iterator(__lhs, "lhs")
539  ._M_iterator(__rhs, "rhs"));
540  return __lhs.base() != __rhs.base();
541  }
542 
543  template<typename _Iterator, typename _Sequence>
544  inline bool
545  operator!=(const _Safe_iterator<_Iterator, _Sequence>& __lhs,
546  const _Safe_iterator<_Iterator, _Sequence>& __rhs)
547  _GLIBCXX_NOEXCEPT
548  {
549  _GLIBCXX_DEBUG_VERIFY(! __lhs._M_singular() && ! __rhs._M_singular(),
550  _M_message(__msg_iter_compare_bad)
551  ._M_iterator(__lhs, "lhs")
552  ._M_iterator(__rhs, "rhs"));
553  _GLIBCXX_DEBUG_VERIFY(__lhs._M_can_compare(__rhs),
554  _M_message(__msg_compare_different)
555  ._M_iterator(__lhs, "lhs")
556  ._M_iterator(__rhs, "rhs"));
557  return __lhs.base() != __rhs.base();
558  }
559 
560  template<typename _IteratorL, typename _IteratorR, typename _Sequence>
561  inline bool
562  operator<(const _Safe_iterator<_IteratorL, _Sequence>& __lhs,
563  const _Safe_iterator<_IteratorR, _Sequence>& __rhs)
564  _GLIBCXX_NOEXCEPT
565  {
566  _GLIBCXX_DEBUG_VERIFY(! __lhs._M_singular() && ! __rhs._M_singular(),
567  _M_message(__msg_iter_order_bad)
568  ._M_iterator(__lhs, "lhs")
569  ._M_iterator(__rhs, "rhs"));
570  _GLIBCXX_DEBUG_VERIFY(__lhs._M_can_compare(__rhs),
571  _M_message(__msg_order_different)
572  ._M_iterator(__lhs, "lhs")
573  ._M_iterator(__rhs, "rhs"));
574  return __lhs.base() < __rhs.base();
575  }
576 
577  template<typename _Iterator, typename _Sequence>
578  inline bool
579  operator<(const _Safe_iterator<_Iterator, _Sequence>& __lhs,
580  const _Safe_iterator<_Iterator, _Sequence>& __rhs)
581  _GLIBCXX_NOEXCEPT
582  {
583  _GLIBCXX_DEBUG_VERIFY(! __lhs._M_singular() && ! __rhs._M_singular(),
584  _M_message(__msg_iter_order_bad)
585  ._M_iterator(__lhs, "lhs")
586  ._M_iterator(__rhs, "rhs"));
587  _GLIBCXX_DEBUG_VERIFY(__lhs._M_can_compare(__rhs),
588  _M_message(__msg_order_different)
589  ._M_iterator(__lhs, "lhs")
590  ._M_iterator(__rhs, "rhs"));
591  return __lhs.base() < __rhs.base();
592  }
593 
594  template<typename _IteratorL, typename _IteratorR, typename _Sequence>
595  inline bool
596  operator<=(const _Safe_iterator<_IteratorL, _Sequence>& __lhs,
597  const _Safe_iterator<_IteratorR, _Sequence>& __rhs)
598  _GLIBCXX_NOEXCEPT
599  {
600  _GLIBCXX_DEBUG_VERIFY(! __lhs._M_singular() && ! __rhs._M_singular(),
601  _M_message(__msg_iter_order_bad)
602  ._M_iterator(__lhs, "lhs")
603  ._M_iterator(__rhs, "rhs"));
604  _GLIBCXX_DEBUG_VERIFY(__lhs._M_can_compare(__rhs),
605  _M_message(__msg_order_different)
606  ._M_iterator(__lhs, "lhs")
607  ._M_iterator(__rhs, "rhs"));
608  return __lhs.base() <= __rhs.base();
609  }
610 
611  template<typename _Iterator, typename _Sequence>
612  inline bool
613  operator<=(const _Safe_iterator<_Iterator, _Sequence>& __lhs,
614  const _Safe_iterator<_Iterator, _Sequence>& __rhs)
615  _GLIBCXX_NOEXCEPT
616  {
617  _GLIBCXX_DEBUG_VERIFY(! __lhs._M_singular() && ! __rhs._M_singular(),
618  _M_message(__msg_iter_order_bad)
619  ._M_iterator(__lhs, "lhs")
620  ._M_iterator(__rhs, "rhs"));
621  _GLIBCXX_DEBUG_VERIFY(__lhs._M_can_compare(__rhs),
622  _M_message(__msg_order_different)
623  ._M_iterator(__lhs, "lhs")
624  ._M_iterator(__rhs, "rhs"));
625  return __lhs.base() <= __rhs.base();
626  }
627 
628  template<typename _IteratorL, typename _IteratorR, typename _Sequence>
629  inline bool
630  operator>(const _Safe_iterator<_IteratorL, _Sequence>& __lhs,
631  const _Safe_iterator<_IteratorR, _Sequence>& __rhs)
632  _GLIBCXX_NOEXCEPT
633  {
634  _GLIBCXX_DEBUG_VERIFY(! __lhs._M_singular() && ! __rhs._M_singular(),
635  _M_message(__msg_iter_order_bad)
636  ._M_iterator(__lhs, "lhs")
637  ._M_iterator(__rhs, "rhs"));
638  _GLIBCXX_DEBUG_VERIFY(__lhs._M_can_compare(__rhs),
639  _M_message(__msg_order_different)
640  ._M_iterator(__lhs, "lhs")
641  ._M_iterator(__rhs, "rhs"));
642  return __lhs.base() > __rhs.base();
643  }
644 
645  template<typename _Iterator, typename _Sequence>
646  inline bool
647  operator>(const _Safe_iterator<_Iterator, _Sequence>& __lhs,
648  const _Safe_iterator<_Iterator, _Sequence>& __rhs)
649  _GLIBCXX_NOEXCEPT
650  {
651  _GLIBCXX_DEBUG_VERIFY(! __lhs._M_singular() && ! __rhs._M_singular(),
652  _M_message(__msg_iter_order_bad)
653  ._M_iterator(__lhs, "lhs")
654  ._M_iterator(__rhs, "rhs"));
655  _GLIBCXX_DEBUG_VERIFY(__lhs._M_can_compare(__rhs),
656  _M_message(__msg_order_different)
657  ._M_iterator(__lhs, "lhs")
658  ._M_iterator(__rhs, "rhs"));
659  return __lhs.base() > __rhs.base();
660  }
661 
662  template<typename _IteratorL, typename _IteratorR, typename _Sequence>
663  inline bool
664  operator>=(const _Safe_iterator<_IteratorL, _Sequence>& __lhs,
665  const _Safe_iterator<_IteratorR, _Sequence>& __rhs)
666  _GLIBCXX_NOEXCEPT
667  {
668  _GLIBCXX_DEBUG_VERIFY(! __lhs._M_singular() && ! __rhs._M_singular(),
669  _M_message(__msg_iter_order_bad)
670  ._M_iterator(__lhs, "lhs")
671  ._M_iterator(__rhs, "rhs"));
672  _GLIBCXX_DEBUG_VERIFY(__lhs._M_can_compare(__rhs),
673  _M_message(__msg_order_different)
674  ._M_iterator(__lhs, "lhs")
675  ._M_iterator(__rhs, "rhs"));
676  return __lhs.base() >= __rhs.base();
677  }
678 
679  template<typename _Iterator, typename _Sequence>
680  inline bool
681  operator>=(const _Safe_iterator<_Iterator, _Sequence>& __lhs,
682  const _Safe_iterator<_Iterator, _Sequence>& __rhs)
683  _GLIBCXX_NOEXCEPT
684  {
685  _GLIBCXX_DEBUG_VERIFY(! __lhs._M_singular() && ! __rhs._M_singular(),
686  _M_message(__msg_iter_order_bad)
687  ._M_iterator(__lhs, "lhs")
688  ._M_iterator(__rhs, "rhs"));
689  _GLIBCXX_DEBUG_VERIFY(__lhs._M_can_compare(__rhs),
690  _M_message(__msg_order_different)
691  ._M_iterator(__lhs, "lhs")
692  ._M_iterator(__rhs, "rhs"));
693  return __lhs.base() >= __rhs.base();
694  }
695 
696  // _GLIBCXX_RESOLVE_LIB_DEFECTS
697  // According to the resolution of DR179 not only the various comparison
698  // operators but also operator- must accept mixed iterator/const_iterator
699  // parameters.
700  template<typename _IteratorL, typename _IteratorR, typename _Sequence>
701  inline typename _Safe_iterator<_IteratorL, _Sequence>::difference_type
702  operator-(const _Safe_iterator<_IteratorL, _Sequence>& __lhs,
703  const _Safe_iterator<_IteratorR, _Sequence>& __rhs)
704  _GLIBCXX_NOEXCEPT
705  {
706  _GLIBCXX_DEBUG_VERIFY(! __lhs._M_singular() && ! __rhs._M_singular(),
707  _M_message(__msg_distance_bad)
708  ._M_iterator(__lhs, "lhs")
709  ._M_iterator(__rhs, "rhs"));
710  _GLIBCXX_DEBUG_VERIFY(__lhs._M_can_compare(__rhs),
711  _M_message(__msg_distance_different)
712  ._M_iterator(__lhs, "lhs")
713  ._M_iterator(__rhs, "rhs"));
714  return __lhs.base() - __rhs.base();
715  }
716 
717  template<typename _Iterator, typename _Sequence>
718  inline typename _Safe_iterator<_Iterator, _Sequence>::difference_type
719  operator-(const _Safe_iterator<_Iterator, _Sequence>& __lhs,
720  const _Safe_iterator<_Iterator, _Sequence>& __rhs)
721  _GLIBCXX_NOEXCEPT
722  {
723  _GLIBCXX_DEBUG_VERIFY(! __lhs._M_singular() && ! __rhs._M_singular(),
724  _M_message(__msg_distance_bad)
725  ._M_iterator(__lhs, "lhs")
726  ._M_iterator(__rhs, "rhs"));
727  _GLIBCXX_DEBUG_VERIFY(__lhs._M_can_compare(__rhs),
728  _M_message(__msg_distance_different)
729  ._M_iterator(__lhs, "lhs")
730  ._M_iterator(__rhs, "rhs"));
731  return __lhs.base() - __rhs.base();
732  }
733 
734  template<typename _Iterator, typename _Sequence>
735  inline _Safe_iterator<_Iterator, _Sequence>
736  operator+(typename _Safe_iterator<_Iterator,_Sequence>::difference_type __n,
737  const _Safe_iterator<_Iterator, _Sequence>& __i) _GLIBCXX_NOEXCEPT
738  { return __i + __n; }
739 
740  /** Safe iterators know if they are dereferenceable. */
741  template<typename _Iterator, typename _Sequence>
742  inline bool
744  { return __x._M_dereferenceable(); }
745 
746  /** Safe iterators know how to check if they form a valid range. */
747  template<typename _Iterator, typename _Sequence>
748  inline bool
751  typename _Distance_traits<_Iterator>::__type& __dist)
752  { return __first._M_valid_range(__last, __dist); }
753 
754  /** Safe iterators can help to get better distance knowledge. */
755  template<typename _Iterator, typename _Sequence>
756  inline typename _Distance_traits<_Iterator>::__type
760  { return std::make_pair(__last.base() - __first.base(), __dp_exact); }
761 
762  template<typename _Iterator, typename _Sequence>
763  inline typename _Distance_traits<_Iterator>::__type
764  __get_distance(const _Safe_iterator<_Iterator, _Sequence>& __first,
765  const _Safe_iterator<_Iterator, _Sequence>& __last,
767  {
768  typedef typename _Distance_traits<_Iterator>::__type _Diff;
769  typedef _Sequence_traits<_Sequence> _SeqTraits;
770 
771  if (__first.base() == __last.base())
772  return std::make_pair(0, __dp_exact);
773 
774  if (__first._M_is_before_begin())
775  {
776  if (__last._M_is_begin())
777  return std::make_pair(1, __dp_exact);
778 
779  return std::make_pair(1, __dp_sign);
780  }
781 
782  if (__first._M_is_begin())
783  {
784  if (__last._M_is_before_begin())
785  return std::make_pair(-1, __dp_exact);
786 
787  if (__last._M_is_end())
788  return _SeqTraits::_S_size(*__first._M_get_sequence());
789 
790  return std::make_pair(1, __dp_sign);
791  }
792 
793  if (__first._M_is_end())
794  {
795  if (__last._M_is_before_begin())
796  return std::make_pair(-1, __dp_exact);
797 
798  if (__last._M_is_begin())
799  {
800  _Diff __diff = _SeqTraits::_S_size(*__first._M_get_sequence());
801  return std::make_pair(-__diff.first, __diff.second);
802  }
803 
804  return std::make_pair(-1, __dp_sign);
805  }
806 
807  if (__last._M_is_before_begin() || __last._M_is_begin())
808  return std::make_pair(-1, __dp_sign);
809 
810  if (__last._M_is_end())
811  return std::make_pair(1, __dp_sign);
812 
813  return std::make_pair(1, __dp_equality);
814  }
815 
816  // Get distance from sequence begin to specified iterator.
817  template<typename _Iterator, typename _Sequence>
818  inline typename _Distance_traits<_Iterator>::__type
819  __get_distance_from_begin(const _Safe_iterator<_Iterator, _Sequence>& __it)
820  {
821  typedef _Sequence_traits<_Sequence> _SeqTraits;
822 
823  // No need to consider before_begin as this function is only used in
824  // _M_can_advance which won't be used for forward_list iterators.
825  if (__it._M_is_begin())
826  return std::make_pair(0, __dp_exact);
827 
828  if (__it._M_is_end())
829  return _SeqTraits::_S_size(*__it._M_get_sequence());
830 
831  typename _Distance_traits<_Iterator>::__type __res
832  = __get_distance(__it._M_get_sequence()->_M_base().begin(), __it.base());
833 
834  if (__res.second == __dp_equality)
835  return std::make_pair(1, __dp_sign);
836 
837  return __res;
838  }
839 
840  // Get distance from specified iterator to sequence end.
841  template<typename _Iterator, typename _Sequence>
842  inline typename _Distance_traits<_Iterator>::__type
843  __get_distance_to_end(const _Safe_iterator<_Iterator, _Sequence>& __it)
844  {
845  typedef _Sequence_traits<_Sequence> _SeqTraits;
846 
847  // No need to consider before_begin as this function is only used in
848  // _M_can_advance which won't be used for forward_list iterators.
849  if (__it._M_is_begin())
850  return _SeqTraits::_S_size(*__it._M_get_sequence());
851 
852  if (__it._M_is_end())
853  return std::make_pair(0, __dp_exact);
854 
855  typename _Distance_traits<_Iterator>::__type __res
856  = __get_distance(__it.base(), __it._M_get_sequence()->_M_base().end());
857 
858  if (__res.second == __dp_equality)
859  return std::make_pair(1, __dp_sign);
860 
861  return __res;
862  }
863 
864 #if __cplusplus < 201103L
865  template<typename _Iterator, typename _Sequence>
866  struct __is_safe_random_iterator<_Safe_iterator<_Iterator, _Sequence> >
867  : std::__are_same<std::random_access_iterator_tag,
868  typename std::iterator_traits<_Iterator>::
869  iterator_category>
870  { };
871 #else
872  template<typename _Iterator, typename _Sequence>
873  _Iterator
874  __base(const _Safe_iterator<_Iterator, _Sequence>& __it,
876  { return __it.base(); }
877 
878  template<typename _Iterator, typename _Sequence>
879  const _Safe_iterator<_Iterator, _Sequence>&
880  __base(const _Safe_iterator<_Iterator, _Sequence>& __it,
882  { return __it; }
883 
884  template<typename _Iterator, typename _Sequence>
885  auto
886  __base(const _Safe_iterator<_Iterator, _Sequence>& __it)
887  -> decltype(__base(__it, std::__iterator_category(__it)))
888  { return __base(__it, std::__iterator_category(__it)); }
889 #endif
890 
891 #if __cplusplus < 201103L
892  template<typename _Iterator, typename _Sequence>
893  struct _Unsafe_type<_Safe_iterator<_Iterator, _Sequence> >
894  { typedef _Iterator _Type; };
895 #endif
896 
897  template<typename _Iterator, typename _Sequence>
898  inline _Iterator
899  __unsafe(const _Safe_iterator<_Iterator, _Sequence>& __it)
900  { return __it.base(); }
901 
902 } // namespace __gnu_debug
903 
904 #include <debug/safe_iterator.tcc>
905 
906 #endif
_Safe_iterator & operator=(_Safe_iterator &&__x) noexcept
Move assignment.
Struct holding two objects of arbitrary type.
Definition: stl_pair.h:208
Marking input iterators.
Scoped lock idiom.
Definition: concurrence.h:231
GNU debug classes for public use.
bool _M_before_dereferenceable() const
Is the iterator before a dereferenceable one?
_Safe_iterator(const _Safe_iterator< _MutableIterator, typename __gnu_cxx::__enable_if<(std::__are_same< _MutableIterator, typename _Sequence::iterator::iterator_type >::__value), _Sequence >::__type > &__x) noexcept
Converting constructor from a mutable iterator to a constant iterator.
Base class that supports tracking of iterators that reference a sequence.
Definition: safe_base.h:188
Safe iterator wrapper.
Definition: formatter.h:56
bool _M_incrementable() const
Is the iterator incrementable?
_Safe_iterator & operator=(const _Safe_iterator &__x) noexcept
Copy assignment.
reference operator*() const noexcept
Iterator dereference.
_Safe_iterator & operator++() noexcept
Iterator preincrement.
pointer operator->() const noexcept
Iterator dereference.
constexpr pair< typename __decay_and_strip< _T1 >::__type, typename __decay_and_strip< _T2 >::__type > make_pair(_T1 &&__x, _T2 &&__y)
A convenience wrapper for creating a pair from two objects.
Definition: stl_pair.h:524
Basic functionality for a safe iterator.
Definition: safe_base.h:50
void _M_attach_single(_Safe_sequence_base *__seq)
bool _M_is_before_begin() const
Is this iterator equal to the sequence's before_begin() iterator if any?
_Safe_iterator operator--(int) noexcept
Iterator postdecrement.
_Safe_iterator & operator--() noexcept
Iterator predecrement.
_Safe_iterator(const _Safe_iterator &__x) noexcept
Copy construction.
_Distance_traits< _Iterator >::__type __get_distance(const _Iterator &__lhs, const _Iterator &__rhs, std::random_access_iterator_tag)
_Safe_iterator(const _Iterator &__i, const _Safe_sequence_base *__seq) noexcept
Safe iterator construction from an unsafe iterator and its sequence.
constexpr iterator_traits< _Iter >::iterator_category __iterator_category(const _Iter &)
_Safe_sequence_base * _M_sequence
Definition: safe_base.h:57
void _M_attach_single(_Safe_sequence_base *__seq, bool __constant)
bool _M_dereferenceable() const
Is the iterator dereferenceable?
bool __valid_range(const _InputIterator &__first, const _InputIterator &__last, typename _Distance_traits< _InputIterator >::__type &__dist)
_Iterator & base() noexcept
Return the underlying iterator.
bool _M_is_end() const
Is this iterator equal to the sequence's end() iterator?
bool _M_is_begin() const
Is this iterator equal to the sequence's begin() iterator?
void _M_attach(_Safe_sequence_base *__seq)
_Safe_iterator operator++(int) noexcept
Iterator postincrement.
bool __check_dereferenceable(const _Iterator &)
Definition: functions.h:74
void _M_attach(_Safe_sequence_base *__seq, bool __constant)
Random-access iterators support a superset of bidirectional iterator operations.
_Safe_iterator(_Safe_iterator &&__x) noexcept
Move construction.
bool _M_is_beginnest() const
Is this iterator equal to the sequence's before_begin() iterator if any or begin() otherwise?
__gnu_cxx::__mutex & _M_get_mutex()