1 // Safe iterator implementation -*- C++ -*-
3 // Copyright (C) 2003-2015 Free Software Foundation, Inc.
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)
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.
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.
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/>.
25 /** @file debug/safe_iterator.h
26 * This file is a GNU debug extension to the Standard C++ Library.
29 #ifndef _GLIBCXX_DEBUG_SAFE_ITERATOR_H
30 #define _GLIBCXX_DEBUG_SAFE_ITERATOR_H 1
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>
41 /** Helper struct to deal with sequence offering a before_begin
44 template<typename _Sequence
>
45 struct _BeforeBeginHelper
47 template<typename _Iterator
>
49 _S_Is(const _Safe_iterator
<_Iterator
, _Sequence
>&)
52 template<typename _Iterator
>
54 _S_Is_Beginnest(const _Safe_iterator
<_Iterator
, _Sequence
>& __it
)
55 { return __it
.base() == __it
._M_get_sequence()->_M_base().begin(); }
58 /** Sequence traits giving the size of a container if possible. */
59 template<typename _Sequence
>
60 struct _Sequence_traits
62 typedef _Distance_traits
<typename
_Sequence::iterator
> _DistTraits
;
64 static typename
_DistTraits::__type
65 _S_size(const _Sequence
& __seq
)
66 { return std::make_pair(__seq
.size(), __dp_exact
); }
69 /** \brief Safe iterator wrapper.
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.
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.
85 template<typename _Iterator
, typename _Sequence
>
88 public _Safe_iterator_base
90 typedef _Iterator _Iter_base
;
91 typedef _Safe_iterator_base _Safe_base
;
92 typedef typename
_Sequence::const_iterator _Const_iterator
;
94 /// Determine if this is a constant iterator.
97 { return std::__are_same
<_Const_iterator
, _Safe_iterator
>::__value
; }
99 typedef std::iterator_traits
<_Iterator
> _Traits
;
101 struct _Attach_single
104 _Safe_iterator(const _Iterator
& __i
, _Safe_sequence_base
* __seq
,
108 { _M_attach_single(__seq
); }
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
;
118 /// @post the iterator is singular and unattached
119 _Safe_iterator() _GLIBCXX_NOEXCEPT
: _Iter_base() { }
122 * @brief Safe iterator construction from an unsafe iterator and
125 * @pre @p seq is not NULL
126 * @post this is not singular
128 _Safe_iterator(const _Iterator
& __i
, const _Safe_sequence_base
* __seq
)
130 : _Iter_base(__i
), _Safe_base(__seq
, _M_constant())
132 _GLIBCXX_DEBUG_VERIFY(!this->_M_singular(),
133 _M_message(__msg_init_singular
)
134 ._M_iterator(*this, "this"));
138 * @brief Copy construction.
140 _Safe_iterator(const _Safe_iterator
& __x
) _GLIBCXX_NOEXCEPT
141 : _Iter_base(__x
.base())
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
);
153 #if __cplusplus >= 201103L
155 * @brief Move construction.
156 * @post __x is singular and unattached
158 _Safe_iterator(_Safe_iterator
&& __x
) noexcept
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
;
168 std::swap(base(), __x
.base());
174 * @brief Converting constructor from a mutable iterator to a
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())
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
);
196 * @brief Copy assignment.
199 operator=(const _Safe_iterator
& __x
) _GLIBCXX_NOEXCEPT
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"));
209 if (this->_M_sequence
&& this->_M_sequence
== __x
._M_sequence
)
211 __gnu_cxx::__scoped_lock
__l(this->_M_get_mutex());
213 _M_version
= __x
._M_sequence
->_M_version
;
219 _M_attach(__x
._M_sequence
);
225 #if __cplusplus >= 201103L
227 * @brief Move assignment.
228 * @post __x is singular and unattached
231 operator=(_Safe_iterator
&& __x
) noexcept
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"));
242 if (this->_M_sequence
&& this->_M_sequence
== __x
._M_sequence
)
244 __gnu_cxx::__scoped_lock
__l(this->_M_get_mutex());
246 _M_version
= __x
._M_sequence
->_M_version
;
252 _M_attach(__x
._M_sequence
);
256 __x
.base() = _Iterator();
262 * @brief Iterator dereference.
263 * @pre iterator is dereferenceable
266 operator*() const _GLIBCXX_NOEXCEPT
268 _GLIBCXX_DEBUG_VERIFY(this->_M_dereferenceable(),
269 _M_message(__msg_bad_deref
)
270 ._M_iterator(*this, "this"));
275 * @brief Iterator dereference.
276 * @pre iterator is dereferenceable
277 * @todo Make this correct w.r.t. iterators that return proxies
280 operator->() const _GLIBCXX_NOEXCEPT
282 _GLIBCXX_DEBUG_VERIFY(this->_M_dereferenceable(),
283 _M_message(__msg_bad_deref
)
284 ._M_iterator(*this, "this"));
285 return std::__addressof(*base());
288 // ------ Input iterator requirements ------
290 * @brief Iterator preincrement
291 * @pre iterator is incrementable
294 operator++() _GLIBCXX_NOEXCEPT
296 _GLIBCXX_DEBUG_VERIFY(this->_M_incrementable(),
297 _M_message(__msg_bad_inc
)
298 ._M_iterator(*this, "this"));
299 __gnu_cxx::__scoped_lock(this->_M_get_mutex());
305 * @brief Iterator postincrement
306 * @pre iterator is incrementable
309 operator++(int) _GLIBCXX_NOEXCEPT
311 _GLIBCXX_DEBUG_VERIFY(this->_M_incrementable(),
312 _M_message(__msg_bad_inc
)
313 ._M_iterator(*this, "this"));
314 __gnu_cxx::__scoped_lock
__l(this->_M_get_mutex());
315 return _Safe_iterator(base()++, this->_M_sequence
, _Attach_single());
318 // ------ Bidirectional iterator requirements ------
320 * @brief Iterator predecrement
321 * @pre iterator is decrementable
324 operator--() _GLIBCXX_NOEXCEPT
326 _GLIBCXX_DEBUG_VERIFY(this->_M_decrementable(),
327 _M_message(__msg_bad_dec
)
328 ._M_iterator(*this, "this"));
329 __gnu_cxx::__scoped_lock
__l(this->_M_get_mutex());
335 * @brief Iterator postdecrement
336 * @pre iterator is decrementable
339 operator--(int) _GLIBCXX_NOEXCEPT
341 _GLIBCXX_DEBUG_VERIFY(this->_M_decrementable(),
342 _M_message(__msg_bad_dec
)
343 ._M_iterator(*this, "this"));
344 __gnu_cxx::__scoped_lock
__l(this->_M_get_mutex());
345 return _Safe_iterator(base()--, this->_M_sequence
, _Attach_single());
348 // ------ Random access iterator requirements ------
350 operator[](const difference_type
& __n
) const _GLIBCXX_NOEXCEPT
352 _GLIBCXX_DEBUG_VERIFY(this->_M_can_advance(__n
)
353 && this->_M_can_advance(__n
+1),
354 _M_message(__msg_iter_subscript_oob
)
355 ._M_iterator(*this)._M_integer(__n
));
360 operator+=(const difference_type
& __n
) _GLIBCXX_NOEXCEPT
362 _GLIBCXX_DEBUG_VERIFY(this->_M_can_advance(__n
),
363 _M_message(__msg_advance_oob
)
364 ._M_iterator(*this)._M_integer(__n
));
365 __gnu_cxx::__scoped_lock
__l(this->_M_get_mutex());
371 operator+(const difference_type
& __n
) const _GLIBCXX_NOEXCEPT
373 _GLIBCXX_DEBUG_VERIFY(this->_M_can_advance(__n
),
374 _M_message(__msg_advance_oob
)
375 ._M_iterator(*this)._M_integer(__n
));
376 return _Safe_iterator(base() + __n
, this->_M_sequence
);
380 operator-=(const difference_type
& __n
) _GLIBCXX_NOEXCEPT
382 _GLIBCXX_DEBUG_VERIFY(this->_M_can_advance(-__n
),
383 _M_message(__msg_retreat_oob
)
384 ._M_iterator(*this)._M_integer(__n
));
385 __gnu_cxx::__scoped_lock
__l(this->_M_get_mutex());
391 operator-(const difference_type
& __n
) const _GLIBCXX_NOEXCEPT
393 _GLIBCXX_DEBUG_VERIFY(this->_M_can_advance(-__n
),
394 _M_message(__msg_retreat_oob
)
395 ._M_iterator(*this)._M_integer(__n
));
396 return _Safe_iterator(base() - __n
, this->_M_sequence
);
399 // ------ Utilities ------
401 * @brief Return the underlying iterator
404 base() _GLIBCXX_NOEXCEPT
{ return *this; }
407 base() const _GLIBCXX_NOEXCEPT
{ return *this; }
410 * @brief Conversion to underlying non-debug iterator to allow
411 * better interaction with non-debug containers.
413 operator _Iterator() const _GLIBCXX_NOEXCEPT
{ return *this; }
415 /** Attach iterator to the given sequence. */
417 _M_attach(_Safe_sequence_base
* __seq
)
418 { _Safe_base::_M_attach(__seq
, _M_constant()); }
420 /** Likewise, but not thread-safe. */
422 _M_attach_single(_Safe_sequence_base
* __seq
)
423 { _Safe_base::_M_attach_single(__seq
, _M_constant()); }
425 /// Is the iterator dereferenceable?
427 _M_dereferenceable() const
428 { return !this->_M_singular() && !_M_is_end() && !_M_is_before_begin(); }
430 /// Is the iterator before a dereferenceable one?
432 _M_before_dereferenceable() const
434 if (this->_M_incrementable())
436 _Iterator __base
= base();
437 return ++__base
!= _M_get_sequence()->_M_base().end();
442 /// Is the iterator incrementable?
444 _M_incrementable() const
445 { return !this->_M_singular() && !_M_is_end(); }
447 // Is the iterator decrementable?
449 _M_decrementable() const { return !_M_singular() && !_M_is_begin(); }
451 // Can we advance the iterator @p __n steps (@p __n may be negative)
453 _M_can_advance(const difference_type
& __n
) const;
455 // Is the iterator range [*this, __rhs) valid?
457 _M_valid_range(const _Safe_iterator
& __rhs
,
458 std::pair
<difference_type
, _Distance_precision
>& __dist
,
459 bool __check_dereferenceable
= true) const;
461 // The sequence this iterator references.
463 __gnu_cxx::__conditional_type
<std::__are_same
<_Const_iterator
,
464 _Safe_iterator
>::__value
,
467 _M_get_sequence() const
468 { return static_cast<_Sequence
*>(_M_sequence
); }
470 /// Is this iterator equal to the sequence's begin() iterator?
473 { return base() == _M_get_sequence()->_M_base().begin(); }
475 /// Is this iterator equal to the sequence's end() iterator?
478 { return base() == _M_get_sequence()->_M_base().end(); }
480 /// Is this iterator equal to the sequence's before_begin() iterator if
483 _M_is_before_begin() const
484 { return _BeforeBeginHelper
<_Sequence
>::_S_Is(*this); }
486 /// Is this iterator equal to the sequence's before_begin() iterator if
487 /// any or begin() otherwise?
489 _M_is_beginnest() const
490 { return _BeforeBeginHelper
<_Sequence
>::_S_Is_Beginnest(*this); }
493 template<typename _IteratorL
, typename _IteratorR
, typename _Sequence
>
495 operator==(const _Safe_iterator
<_IteratorL
, _Sequence
>& __lhs
,
496 const _Safe_iterator
<_IteratorR
, _Sequence
>& __rhs
)
499 _GLIBCXX_DEBUG_VERIFY(! __lhs
._M_singular() && ! __rhs
._M_singular(),
500 _M_message(__msg_iter_compare_bad
)
501 ._M_iterator(__lhs
, "lhs")
502 ._M_iterator(__rhs
, "rhs"));
503 _GLIBCXX_DEBUG_VERIFY(__lhs
._M_can_compare(__rhs
),
504 _M_message(__msg_compare_different
)
505 ._M_iterator(__lhs
, "lhs")
506 ._M_iterator(__rhs
, "rhs"));
507 return __lhs
.base() == __rhs
.base();
510 template<typename _Iterator
, typename _Sequence
>
512 operator==(const _Safe_iterator
<_Iterator
, _Sequence
>& __lhs
,
513 const _Safe_iterator
<_Iterator
, _Sequence
>& __rhs
)
516 _GLIBCXX_DEBUG_VERIFY(! __lhs
._M_singular() && ! __rhs
._M_singular(),
517 _M_message(__msg_iter_compare_bad
)
518 ._M_iterator(__lhs
, "lhs")
519 ._M_iterator(__rhs
, "rhs"));
520 _GLIBCXX_DEBUG_VERIFY(__lhs
._M_can_compare(__rhs
),
521 _M_message(__msg_compare_different
)
522 ._M_iterator(__lhs
, "lhs")
523 ._M_iterator(__rhs
, "rhs"));
524 return __lhs
.base() == __rhs
.base();
527 template<typename _IteratorL
, typename _IteratorR
, typename _Sequence
>
529 operator!=(const _Safe_iterator
<_IteratorL
, _Sequence
>& __lhs
,
530 const _Safe_iterator
<_IteratorR
, _Sequence
>& __rhs
)
533 _GLIBCXX_DEBUG_VERIFY(! __lhs
._M_singular() && ! __rhs
._M_singular(),
534 _M_message(__msg_iter_compare_bad
)
535 ._M_iterator(__lhs
, "lhs")
536 ._M_iterator(__rhs
, "rhs"));
537 _GLIBCXX_DEBUG_VERIFY(__lhs
._M_can_compare(__rhs
),
538 _M_message(__msg_compare_different
)
539 ._M_iterator(__lhs
, "lhs")
540 ._M_iterator(__rhs
, "rhs"));
541 return __lhs
.base() != __rhs
.base();
544 template<typename _Iterator
, typename _Sequence
>
546 operator!=(const _Safe_iterator
<_Iterator
, _Sequence
>& __lhs
,
547 const _Safe_iterator
<_Iterator
, _Sequence
>& __rhs
)
550 _GLIBCXX_DEBUG_VERIFY(! __lhs
._M_singular() && ! __rhs
._M_singular(),
551 _M_message(__msg_iter_compare_bad
)
552 ._M_iterator(__lhs
, "lhs")
553 ._M_iterator(__rhs
, "rhs"));
554 _GLIBCXX_DEBUG_VERIFY(__lhs
._M_can_compare(__rhs
),
555 _M_message(__msg_compare_different
)
556 ._M_iterator(__lhs
, "lhs")
557 ._M_iterator(__rhs
, "rhs"));
558 return __lhs
.base() != __rhs
.base();
561 template<typename _IteratorL
, typename _IteratorR
, typename _Sequence
>
563 operator<(const _Safe_iterator
<_IteratorL
, _Sequence
>& __lhs
,
564 const _Safe_iterator
<_IteratorR
, _Sequence
>& __rhs
)
567 _GLIBCXX_DEBUG_VERIFY(! __lhs
._M_singular() && ! __rhs
._M_singular(),
568 _M_message(__msg_iter_order_bad
)
569 ._M_iterator(__lhs
, "lhs")
570 ._M_iterator(__rhs
, "rhs"));
571 _GLIBCXX_DEBUG_VERIFY(__lhs
._M_can_compare(__rhs
),
572 _M_message(__msg_order_different
)
573 ._M_iterator(__lhs
, "lhs")
574 ._M_iterator(__rhs
, "rhs"));
575 return __lhs
.base() < __rhs
.base();
578 template<typename _Iterator
, typename _Sequence
>
580 operator<(const _Safe_iterator
<_Iterator
, _Sequence
>& __lhs
,
581 const _Safe_iterator
<_Iterator
, _Sequence
>& __rhs
)
584 _GLIBCXX_DEBUG_VERIFY(! __lhs
._M_singular() && ! __rhs
._M_singular(),
585 _M_message(__msg_iter_order_bad
)
586 ._M_iterator(__lhs
, "lhs")
587 ._M_iterator(__rhs
, "rhs"));
588 _GLIBCXX_DEBUG_VERIFY(__lhs
._M_can_compare(__rhs
),
589 _M_message(__msg_order_different
)
590 ._M_iterator(__lhs
, "lhs")
591 ._M_iterator(__rhs
, "rhs"));
592 return __lhs
.base() < __rhs
.base();
595 template<typename _IteratorL
, typename _IteratorR
, typename _Sequence
>
597 operator<=(const _Safe_iterator
<_IteratorL
, _Sequence
>& __lhs
,
598 const _Safe_iterator
<_IteratorR
, _Sequence
>& __rhs
)
601 _GLIBCXX_DEBUG_VERIFY(! __lhs
._M_singular() && ! __rhs
._M_singular(),
602 _M_message(__msg_iter_order_bad
)
603 ._M_iterator(__lhs
, "lhs")
604 ._M_iterator(__rhs
, "rhs"));
605 _GLIBCXX_DEBUG_VERIFY(__lhs
._M_can_compare(__rhs
),
606 _M_message(__msg_order_different
)
607 ._M_iterator(__lhs
, "lhs")
608 ._M_iterator(__rhs
, "rhs"));
609 return __lhs
.base() <= __rhs
.base();
612 template<typename _Iterator
, typename _Sequence
>
614 operator<=(const _Safe_iterator
<_Iterator
, _Sequence
>& __lhs
,
615 const _Safe_iterator
<_Iterator
, _Sequence
>& __rhs
)
618 _GLIBCXX_DEBUG_VERIFY(! __lhs
._M_singular() && ! __rhs
._M_singular(),
619 _M_message(__msg_iter_order_bad
)
620 ._M_iterator(__lhs
, "lhs")
621 ._M_iterator(__rhs
, "rhs"));
622 _GLIBCXX_DEBUG_VERIFY(__lhs
._M_can_compare(__rhs
),
623 _M_message(__msg_order_different
)
624 ._M_iterator(__lhs
, "lhs")
625 ._M_iterator(__rhs
, "rhs"));
626 return __lhs
.base() <= __rhs
.base();
629 template<typename _IteratorL
, typename _IteratorR
, typename _Sequence
>
631 operator>(const _Safe_iterator
<_IteratorL
, _Sequence
>& __lhs
,
632 const _Safe_iterator
<_IteratorR
, _Sequence
>& __rhs
)
635 _GLIBCXX_DEBUG_VERIFY(! __lhs
._M_singular() && ! __rhs
._M_singular(),
636 _M_message(__msg_iter_order_bad
)
637 ._M_iterator(__lhs
, "lhs")
638 ._M_iterator(__rhs
, "rhs"));
639 _GLIBCXX_DEBUG_VERIFY(__lhs
._M_can_compare(__rhs
),
640 _M_message(__msg_order_different
)
641 ._M_iterator(__lhs
, "lhs")
642 ._M_iterator(__rhs
, "rhs"));
643 return __lhs
.base() > __rhs
.base();
646 template<typename _Iterator
, typename _Sequence
>
648 operator>(const _Safe_iterator
<_Iterator
, _Sequence
>& __lhs
,
649 const _Safe_iterator
<_Iterator
, _Sequence
>& __rhs
)
652 _GLIBCXX_DEBUG_VERIFY(! __lhs
._M_singular() && ! __rhs
._M_singular(),
653 _M_message(__msg_iter_order_bad
)
654 ._M_iterator(__lhs
, "lhs")
655 ._M_iterator(__rhs
, "rhs"));
656 _GLIBCXX_DEBUG_VERIFY(__lhs
._M_can_compare(__rhs
),
657 _M_message(__msg_order_different
)
658 ._M_iterator(__lhs
, "lhs")
659 ._M_iterator(__rhs
, "rhs"));
660 return __lhs
.base() > __rhs
.base();
663 template<typename _IteratorL
, typename _IteratorR
, typename _Sequence
>
665 operator>=(const _Safe_iterator
<_IteratorL
, _Sequence
>& __lhs
,
666 const _Safe_iterator
<_IteratorR
, _Sequence
>& __rhs
)
669 _GLIBCXX_DEBUG_VERIFY(! __lhs
._M_singular() && ! __rhs
._M_singular(),
670 _M_message(__msg_iter_order_bad
)
671 ._M_iterator(__lhs
, "lhs")
672 ._M_iterator(__rhs
, "rhs"));
673 _GLIBCXX_DEBUG_VERIFY(__lhs
._M_can_compare(__rhs
),
674 _M_message(__msg_order_different
)
675 ._M_iterator(__lhs
, "lhs")
676 ._M_iterator(__rhs
, "rhs"));
677 return __lhs
.base() >= __rhs
.base();
680 template<typename _Iterator
, typename _Sequence
>
682 operator>=(const _Safe_iterator
<_Iterator
, _Sequence
>& __lhs
,
683 const _Safe_iterator
<_Iterator
, _Sequence
>& __rhs
)
686 _GLIBCXX_DEBUG_VERIFY(! __lhs
._M_singular() && ! __rhs
._M_singular(),
687 _M_message(__msg_iter_order_bad
)
688 ._M_iterator(__lhs
, "lhs")
689 ._M_iterator(__rhs
, "rhs"));
690 _GLIBCXX_DEBUG_VERIFY(__lhs
._M_can_compare(__rhs
),
691 _M_message(__msg_order_different
)
692 ._M_iterator(__lhs
, "lhs")
693 ._M_iterator(__rhs
, "rhs"));
694 return __lhs
.base() >= __rhs
.base();
697 // _GLIBCXX_RESOLVE_LIB_DEFECTS
698 // According to the resolution of DR179 not only the various comparison
699 // operators but also operator- must accept mixed iterator/const_iterator
701 template<typename _IteratorL
, typename _IteratorR
, typename _Sequence
>
702 inline typename _Safe_iterator
<_IteratorL
, _Sequence
>::difference_type
703 operator-(const _Safe_iterator
<_IteratorL
, _Sequence
>& __lhs
,
704 const _Safe_iterator
<_IteratorR
, _Sequence
>& __rhs
)
707 _GLIBCXX_DEBUG_VERIFY(! __lhs
._M_singular() && ! __rhs
._M_singular(),
708 _M_message(__msg_distance_bad
)
709 ._M_iterator(__lhs
, "lhs")
710 ._M_iterator(__rhs
, "rhs"));
711 _GLIBCXX_DEBUG_VERIFY(__lhs
._M_can_compare(__rhs
),
712 _M_message(__msg_distance_different
)
713 ._M_iterator(__lhs
, "lhs")
714 ._M_iterator(__rhs
, "rhs"));
715 return __lhs
.base() - __rhs
.base();
718 template<typename _Iterator
, typename _Sequence
>
719 inline typename _Safe_iterator
<_Iterator
, _Sequence
>::difference_type
720 operator-(const _Safe_iterator
<_Iterator
, _Sequence
>& __lhs
,
721 const _Safe_iterator
<_Iterator
, _Sequence
>& __rhs
)
724 _GLIBCXX_DEBUG_VERIFY(! __lhs
._M_singular() && ! __rhs
._M_singular(),
725 _M_message(__msg_distance_bad
)
726 ._M_iterator(__lhs
, "lhs")
727 ._M_iterator(__rhs
, "rhs"));
728 _GLIBCXX_DEBUG_VERIFY(__lhs
._M_can_compare(__rhs
),
729 _M_message(__msg_distance_different
)
730 ._M_iterator(__lhs
, "lhs")
731 ._M_iterator(__rhs
, "rhs"));
732 return __lhs
.base() - __rhs
.base();
735 template<typename _Iterator
, typename _Sequence
>
736 inline _Safe_iterator
<_Iterator
, _Sequence
>
737 operator+(typename _Safe_iterator
<_Iterator
,_Sequence
>::difference_type __n
,
738 const _Safe_iterator
<_Iterator
, _Sequence
>& __i
) _GLIBCXX_NOEXCEPT
739 { return __i
+ __n
; }
741 /** Safe iterators know if they are dereferenceable. */
742 template<typename _Iterator
, typename _Sequence
>
744 __check_dereferenceable(const _Safe_iterator
<_Iterator
, _Sequence
>& __x
)
745 { return __x
._M_dereferenceable(); }
747 /** Safe iterators know how to check if they form a valid range. */
748 template<typename _Iterator
, typename _Sequence
>
750 __valid_range(const _Safe_iterator
<_Iterator
, _Sequence
>& __first
,
751 const _Safe_iterator
<_Iterator
, _Sequence
>& __last
,
752 typename _Distance_traits
<_Iterator
>::__type
& __dist
)
753 { return __first
._M_valid_range(__last
, __dist
); }
755 /** Safe iterators can help to get better distance knowledge. */
756 template<typename _Iterator
, typename _Sequence
>
757 inline typename _Distance_traits
<_Iterator
>::__type
758 __get_distance(const _Safe_iterator
<_Iterator
, _Sequence
>& __first
,
759 const _Safe_iterator
<_Iterator
, _Sequence
>& __last
,
760 std::random_access_iterator_tag
)
761 { return std::make_pair(__last
.base() - __first
.base(), __dp_exact
); }
763 template<typename _Iterator
, typename _Sequence
>
764 inline typename _Distance_traits
<_Iterator
>::__type
765 __get_distance(const _Safe_iterator
<_Iterator
, _Sequence
>& __first
,
766 const _Safe_iterator
<_Iterator
, _Sequence
>& __last
,
767 std::input_iterator_tag
)
769 typedef typename _Distance_traits
<_Iterator
>::__type _Diff
;
770 typedef _Sequence_traits
<_Sequence
> _SeqTraits
;
772 if (__first
.base() == __last
.base())
773 return std::make_pair(0, __dp_exact
);
775 if (__first
._M_is_before_begin())
777 if (__last
._M_is_begin())
778 return std::make_pair(1, __dp_exact
);
780 return std::make_pair(1, __dp_sign
);
783 if (__first
._M_is_begin())
785 if (__last
._M_is_before_begin())
786 return std::make_pair(-1, __dp_exact
);
788 if (__last
._M_is_end())
789 return _SeqTraits::_S_size(*__first
._M_get_sequence());
791 return std::make_pair(1, __dp_sign
);
794 if (__first
._M_is_end())
796 if (__last
._M_is_before_begin())
797 return std::make_pair(-1, __dp_exact
);
799 if (__last
._M_is_begin())
801 _Diff __diff
= _SeqTraits::_S_size(*__first
._M_get_sequence());
802 return std::make_pair(-__diff
.first
, __diff
.second
);
805 return std::make_pair(-1, __dp_sign
);
808 if (__last
._M_is_before_begin() || __last
._M_is_begin())
809 return std::make_pair(-1, __dp_sign
);
811 if (__last
._M_is_end())
812 return std::make_pair(1, __dp_sign
);
814 return std::make_pair(1, __dp_equality
);
817 // Get distance from sequence begin to specified iterator.
818 template<typename _Iterator
, typename _Sequence
>
819 inline typename _Distance_traits
<_Iterator
>::__type
820 __get_distance_from_begin(const _Safe_iterator
<_Iterator
, _Sequence
>& __it
)
822 typedef _Sequence_traits
<_Sequence
> _SeqTraits
;
824 // No need to consider before_begin as this function is only used in
825 // _M_can_advance which won't be used for forward_list iterators.
826 if (__it
._M_is_begin())
827 return std::make_pair(0, __dp_exact
);
829 if (__it
._M_is_end())
830 return _SeqTraits::_S_size(*__it
._M_get_sequence());
832 typename _Distance_traits
<_Iterator
>::__type __res
833 = __get_distance(__it
._M_get_sequence()->_M_base().begin(), __it
.base());
835 if (__res
.second
== __dp_equality
)
836 return std::make_pair(1, __dp_sign
);
841 // Get distance from specified iterator to sequence end.
842 template<typename _Iterator
, typename _Sequence
>
843 inline typename _Distance_traits
<_Iterator
>::__type
844 __get_distance_to_end(const _Safe_iterator
<_Iterator
, _Sequence
>& __it
)
846 typedef _Sequence_traits
<_Sequence
> _SeqTraits
;
848 // No need to consider before_begin as this function is only used in
849 // _M_can_advance which won't be used for forward_list iterators.
850 if (__it
._M_is_begin())
851 return _SeqTraits::_S_size(*__it
._M_get_sequence());
853 if (__it
._M_is_end())
854 return std::make_pair(0, __dp_exact
);
856 typename _Distance_traits
<_Iterator
>::__type __res
857 = __get_distance(__it
.base(), __it
._M_get_sequence()->_M_base().end());
859 if (__res
.second
== __dp_equality
)
860 return std::make_pair(1, __dp_sign
);
865 #if __cplusplus < 201103L
866 template<typename _Iterator
, typename _Sequence
>
867 struct __is_safe_random_iterator
<_Safe_iterator
<_Iterator
, _Sequence
> >
868 : std::__are_same
<std::random_access_iterator_tag
,
869 typename
std::iterator_traits
<_Iterator
>::
873 template<typename _Iterator
, typename _Sequence
>
875 __base(const _Safe_iterator
<_Iterator
, _Sequence
>& __it
,
876 std::random_access_iterator_tag
)
877 { return __it
.base(); }
879 template<typename _Iterator
, typename _Sequence
>
880 const _Safe_iterator
<_Iterator
, _Sequence
>&
881 __base(const _Safe_iterator
<_Iterator
, _Sequence
>& __it
,
882 std::input_iterator_tag
)
885 template<typename _Iterator
, typename _Sequence
>
887 __base(const _Safe_iterator
<_Iterator
, _Sequence
>& __it
)
888 -> decltype(__base(__it
, std::__iterator_category(__it
)))
889 { return __base(__it
, std::__iterator_category(__it
)); }
892 #if __cplusplus < 201103L
893 template<typename _Iterator
, typename _Sequence
>
894 struct _Unsafe_type
<_Safe_iterator
<_Iterator
, _Sequence
> >
895 { typedef _Iterator _Type
; };
898 template<typename _Iterator
, typename _Sequence
>
900 __unsafe(const _Safe_iterator
<_Iterator
, _Sequence
>& __it
)
901 { return __it
.base(); }
903 } // namespace __gnu_debug
905 #include <debug/safe_iterator.tcc>