libstdc++
safe_iterator.h
Go to the documentation of this file.
00001 // Safe iterator implementation  -*- C++ -*-
00002 
00003 // Copyright (C) 2003-2018 Free Software Foundation, Inc.
00004 //
00005 // This file is part of the GNU ISO C++ Library.  This library is free
00006 // software; you can redistribute it and/or modify it under the
00007 // terms of the GNU General Public License as published by the
00008 // Free Software Foundation; either version 3, or (at your option)
00009 // any later version.
00010 
00011 // This library is distributed in the hope that it will be useful,
00012 // but WITHOUT ANY WARRANTY; without even the implied warranty of
00013 // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
00014 // GNU General Public License for more details.
00015 
00016 // Under Section 7 of GPL version 3, you are granted additional
00017 // permissions described in the GCC Runtime Library Exception, version
00018 // 3.1, as published by the Free Software Foundation.
00019 
00020 // You should have received a copy of the GNU General Public License and
00021 // a copy of the GCC Runtime Library Exception along with this program;
00022 // see the files COPYING3 and COPYING.RUNTIME respectively.  If not, see
00023 // <http://www.gnu.org/licenses/>.
00024 
00025 /** @file debug/safe_iterator.h
00026  *  This file is a GNU debug extension to the Standard C++ Library.
00027  */
00028 
00029 #ifndef _GLIBCXX_DEBUG_SAFE_ITERATOR_H
00030 #define _GLIBCXX_DEBUG_SAFE_ITERATOR_H 1
00031 
00032 #include <debug/assertions.h>
00033 #include <debug/macros.h>
00034 #include <debug/functions.h>
00035 #include <debug/safe_base.h>
00036 #include <bits/stl_pair.h>
00037 #include <ext/type_traits.h>
00038 
00039 namespace __gnu_debug
00040 {
00041   /** Helper struct to deal with sequence offering a before_begin
00042    *  iterator.
00043    **/
00044   template<typename _Sequence>
00045     struct _BeforeBeginHelper
00046     {
00047       template<typename _Iterator>
00048         static bool
00049         _S_Is(const _Safe_iterator<_Iterator, _Sequence>&)
00050         { return false; }
00051 
00052       template<typename _Iterator>
00053         static bool
00054         _S_Is_Beginnest(const _Safe_iterator<_Iterator, _Sequence>& __it)
00055         { return __it.base() == __it._M_get_sequence()->_M_base().begin(); }
00056     };
00057 
00058   /** Sequence traits giving the size of a container if possible. */
00059   template<typename _Sequence>
00060     struct _Sequence_traits
00061     {
00062       typedef _Distance_traits<typename _Sequence::iterator> _DistTraits;
00063 
00064       static typename _DistTraits::__type
00065       _S_size(const _Sequence& __seq)
00066       { return std::make_pair(__seq.size(), __dp_exact); }
00067     };
00068 
00069   /** \brief Safe iterator wrapper.
00070    *
00071    *  The class template %_Safe_iterator is a wrapper around an
00072    *  iterator that tracks the iterator's movement among sequences and
00073    *  checks that operations performed on the "safe" iterator are
00074    *  legal. In additional to the basic iterator operations (which are
00075    *  validated, and then passed to the underlying iterator),
00076    *  %_Safe_iterator has member functions for iterator invalidation,
00077    *  attaching/detaching the iterator from sequences, and querying
00078    *  the iterator's state.
00079    *
00080    *  Note that _Iterator must be the first base class so that it gets
00081    *  initialized before the iterator is being attached to the container's list
00082    *  of iterators and it is being detached before _Iterator get
00083    *  destroyed. Otherwise it would result in a data race.
00084    */
00085   template<typename _Iterator, typename _Sequence>
00086     class _Safe_iterator
00087     : private _Iterator,
00088       public _Safe_iterator_base
00089     {
00090       typedef _Iterator _Iter_base;
00091       typedef _Safe_iterator_base _Safe_base;
00092       typedef typename _Sequence::const_iterator _Const_iterator;
00093 
00094       /// Determine if this is a constant iterator.
00095       bool
00096       _M_constant() const
00097       { return std::__are_same<_Const_iterator, _Safe_iterator>::__value; }
00098 
00099       typedef std::iterator_traits<_Iterator> _Traits;
00100 
00101       struct _Attach_single
00102       { };
00103 
00104       _Safe_iterator(const _Iterator& __i, _Safe_sequence_base* __seq,
00105                      _Attach_single)
00106       _GLIBCXX_NOEXCEPT
00107       : _Iter_base(__i)
00108       { _M_attach_single(__seq); }
00109 
00110     public:
00111       typedef _Iterator                                 iterator_type;
00112       typedef typename _Traits::iterator_category       iterator_category;
00113       typedef typename _Traits::value_type              value_type;
00114       typedef typename _Traits::difference_type         difference_type;
00115       typedef typename _Traits::reference               reference;
00116       typedef typename _Traits::pointer                 pointer;
00117 
00118       /// @post the iterator is singular and unattached
00119       _Safe_iterator() _GLIBCXX_NOEXCEPT : _Iter_base() { }
00120 
00121       /**
00122        * @brief Safe iterator construction from an unsafe iterator and
00123        * its sequence.
00124        *
00125        * @pre @p seq is not NULL
00126        * @post this is not singular
00127        */
00128       _Safe_iterator(const _Iterator& __i, const _Safe_sequence_base* __seq)
00129       _GLIBCXX_NOEXCEPT
00130       : _Iter_base(__i), _Safe_base(__seq, _M_constant())
00131       {
00132         _GLIBCXX_DEBUG_VERIFY(!this->_M_singular(),
00133                               _M_message(__msg_init_singular)
00134                               ._M_iterator(*this, "this"));
00135       }
00136 
00137       /**
00138        * @brief Copy construction.
00139        */
00140       _Safe_iterator(const _Safe_iterator& __x) _GLIBCXX_NOEXCEPT
00141       : _Iter_base(__x.base())
00142       {
00143         // _GLIBCXX_RESOLVE_LIB_DEFECTS
00144         // DR 408. Is vector<reverse_iterator<char*> > forbidden?
00145         _GLIBCXX_DEBUG_VERIFY(!__x._M_singular()
00146                               || __x.base() == _Iterator(),
00147                               _M_message(__msg_init_copy_singular)
00148                               ._M_iterator(*this, "this")
00149                               ._M_iterator(__x, "other"));
00150         _M_attach(__x._M_sequence);
00151       }
00152 
00153 #if __cplusplus >= 201103L
00154       /**
00155        * @brief Move construction.
00156        * @post __x is singular and unattached
00157        */
00158       _Safe_iterator(_Safe_iterator&& __x) noexcept
00159       : _Iter_base()
00160       {
00161         _GLIBCXX_DEBUG_VERIFY(!__x._M_singular()
00162                               || __x.base() == _Iterator(),
00163                               _M_message(__msg_init_copy_singular)
00164                               ._M_iterator(*this, "this")
00165                               ._M_iterator(__x, "other"));
00166         _Safe_sequence_base* __seq = __x._M_sequence;
00167         __x._M_detach();
00168         std::swap(base(), __x.base());
00169         _M_attach(__seq);
00170       }
00171 #endif
00172 
00173       /**
00174        *  @brief Converting constructor from a mutable iterator to a
00175        *  constant iterator.
00176       */
00177       template<typename _MutableIterator>
00178         _Safe_iterator(
00179           const _Safe_iterator<_MutableIterator,
00180           typename __gnu_cxx::__enable_if<(std::__are_same<_MutableIterator,
00181                       typename _Sequence::iterator::iterator_type>::__value),
00182                    _Sequence>::__type>& __x) _GLIBCXX_NOEXCEPT
00183         : _Iter_base(__x.base())
00184         {
00185           // _GLIBCXX_RESOLVE_LIB_DEFECTS
00186           // DR 408. Is vector<reverse_iterator<char*> > forbidden?
00187           _GLIBCXX_DEBUG_VERIFY(!__x._M_singular()
00188                                 || __x.base() == _Iterator(),
00189                                 _M_message(__msg_init_const_singular)
00190                                 ._M_iterator(*this, "this")
00191                                 ._M_iterator(__x, "other"));
00192           _M_attach(__x._M_sequence);
00193         }
00194 
00195       /**
00196        * @brief Copy assignment.
00197        */
00198       _Safe_iterator&
00199       operator=(const _Safe_iterator& __x) _GLIBCXX_NOEXCEPT
00200       {
00201         // _GLIBCXX_RESOLVE_LIB_DEFECTS
00202         // DR 408. Is vector<reverse_iterator<char*> > forbidden?
00203         _GLIBCXX_DEBUG_VERIFY(!__x._M_singular()
00204                               || __x.base() == _Iterator(),
00205                               _M_message(__msg_copy_singular)
00206                               ._M_iterator(*this, "this")
00207                               ._M_iterator(__x, "other"));
00208 
00209         if (this->_M_sequence && this->_M_sequence == __x._M_sequence)
00210           {
00211             __gnu_cxx::__scoped_lock __l(this->_M_get_mutex());
00212             base() = __x.base();
00213             _M_version = __x._M_sequence->_M_version;
00214           }
00215         else
00216           {
00217             _M_detach();
00218             base() = __x.base();
00219             _M_attach(__x._M_sequence);
00220           }
00221 
00222         return *this;
00223       }
00224 
00225 #if __cplusplus >= 201103L
00226       /**
00227        * @brief Move assignment.
00228        * @post __x is singular and unattached
00229        */
00230       _Safe_iterator&
00231       operator=(_Safe_iterator&& __x) noexcept
00232       {
00233         _GLIBCXX_DEBUG_VERIFY(this != &__x,
00234                               _M_message(__msg_self_move_assign)
00235                               ._M_iterator(*this, "this"));
00236         _GLIBCXX_DEBUG_VERIFY(!__x._M_singular()
00237                               || __x.base() == _Iterator(),
00238                               _M_message(__msg_copy_singular)
00239                               ._M_iterator(*this, "this")
00240                               ._M_iterator(__x, "other"));
00241 
00242         if (this->_M_sequence && this->_M_sequence == __x._M_sequence)
00243           {
00244             __gnu_cxx::__scoped_lock __l(this->_M_get_mutex());
00245             base() = __x.base();
00246             _M_version = __x._M_sequence->_M_version;
00247           }
00248         else
00249           {
00250             _M_detach();
00251             base() = __x.base();
00252             _M_attach(__x._M_sequence);
00253           }
00254 
00255         __x._M_detach();
00256         __x.base() = _Iterator();
00257         return *this;
00258       }
00259 #endif
00260 
00261       /**
00262        *  @brief Iterator dereference.
00263        *  @pre iterator is dereferenceable
00264        */
00265       reference
00266       operator*() const _GLIBCXX_NOEXCEPT
00267       {
00268         _GLIBCXX_DEBUG_VERIFY(this->_M_dereferenceable(),
00269                               _M_message(__msg_bad_deref)
00270                               ._M_iterator(*this, "this"));
00271         return *base();
00272       }
00273 
00274       /**
00275        *  @brief Iterator dereference.
00276        *  @pre iterator is dereferenceable
00277        */
00278       pointer
00279       operator->() const _GLIBCXX_NOEXCEPT
00280       {
00281         _GLIBCXX_DEBUG_VERIFY(this->_M_dereferenceable(),
00282                               _M_message(__msg_bad_deref)
00283                               ._M_iterator(*this, "this"));
00284         return base().operator->();
00285       }
00286 
00287       // ------ Input iterator requirements ------
00288       /**
00289        *  @brief Iterator preincrement
00290        *  @pre iterator is incrementable
00291        */
00292       _Safe_iterator&
00293       operator++() _GLIBCXX_NOEXCEPT
00294       {
00295         _GLIBCXX_DEBUG_VERIFY(this->_M_incrementable(),
00296                               _M_message(__msg_bad_inc)
00297                               ._M_iterator(*this, "this"));
00298         __gnu_cxx::__scoped_lock __l(this->_M_get_mutex());
00299         ++base();
00300         return *this;
00301       }
00302 
00303       /**
00304        *  @brief Iterator postincrement
00305        *  @pre iterator is incrementable
00306        */
00307       _Safe_iterator
00308       operator++(int) _GLIBCXX_NOEXCEPT
00309       {
00310         _GLIBCXX_DEBUG_VERIFY(this->_M_incrementable(),
00311                               _M_message(__msg_bad_inc)
00312                               ._M_iterator(*this, "this"));
00313         __gnu_cxx::__scoped_lock __l(this->_M_get_mutex());
00314         return _Safe_iterator(base()++, this->_M_sequence, _Attach_single());
00315       }
00316 
00317       // ------ Bidirectional iterator requirements ------
00318       /**
00319        *  @brief Iterator predecrement
00320        *  @pre iterator is decrementable
00321        */
00322       _Safe_iterator&
00323       operator--() _GLIBCXX_NOEXCEPT
00324       {
00325         _GLIBCXX_DEBUG_VERIFY(this->_M_decrementable(),
00326                               _M_message(__msg_bad_dec)
00327                               ._M_iterator(*this, "this"));
00328         __gnu_cxx::__scoped_lock __l(this->_M_get_mutex());
00329         --base();
00330         return *this;
00331       }
00332 
00333       /**
00334        *  @brief Iterator postdecrement
00335        *  @pre iterator is decrementable
00336        */
00337       _Safe_iterator
00338       operator--(int) _GLIBCXX_NOEXCEPT
00339       {
00340         _GLIBCXX_DEBUG_VERIFY(this->_M_decrementable(),
00341                               _M_message(__msg_bad_dec)
00342                               ._M_iterator(*this, "this"));
00343         __gnu_cxx::__scoped_lock __l(this->_M_get_mutex());
00344         return _Safe_iterator(base()--, this->_M_sequence, _Attach_single());
00345       }
00346 
00347       // ------ Random access iterator requirements ------
00348       reference
00349       operator[](const difference_type& __n) const _GLIBCXX_NOEXCEPT
00350       {
00351         _GLIBCXX_DEBUG_VERIFY(this->_M_can_advance(__n)
00352                               && this->_M_can_advance(__n+1),
00353                               _M_message(__msg_iter_subscript_oob)
00354                               ._M_iterator(*this)._M_integer(__n));
00355         return base()[__n];
00356       }
00357 
00358       _Safe_iterator&
00359       operator+=(const difference_type& __n) _GLIBCXX_NOEXCEPT
00360       {
00361         _GLIBCXX_DEBUG_VERIFY(this->_M_can_advance(__n),
00362                               _M_message(__msg_advance_oob)
00363                               ._M_iterator(*this)._M_integer(__n));
00364         __gnu_cxx::__scoped_lock __l(this->_M_get_mutex());
00365         base() += __n;
00366         return *this;
00367       }
00368 
00369       _Safe_iterator
00370       operator+(const difference_type& __n) const _GLIBCXX_NOEXCEPT
00371       {
00372         _GLIBCXX_DEBUG_VERIFY(this->_M_can_advance(__n),
00373                               _M_message(__msg_advance_oob)
00374                               ._M_iterator(*this)._M_integer(__n));
00375         return _Safe_iterator(base() + __n, this->_M_sequence);
00376       }
00377 
00378       _Safe_iterator&
00379       operator-=(const difference_type& __n) _GLIBCXX_NOEXCEPT
00380       {
00381         _GLIBCXX_DEBUG_VERIFY(this->_M_can_advance(-__n),
00382                               _M_message(__msg_retreat_oob)
00383                               ._M_iterator(*this)._M_integer(__n));
00384         __gnu_cxx::__scoped_lock __l(this->_M_get_mutex());
00385         base() -= __n;
00386         return *this;
00387       }
00388 
00389       _Safe_iterator
00390       operator-(const difference_type& __n) const _GLIBCXX_NOEXCEPT
00391       {
00392         _GLIBCXX_DEBUG_VERIFY(this->_M_can_advance(-__n),
00393                               _M_message(__msg_retreat_oob)
00394                               ._M_iterator(*this)._M_integer(__n));
00395         return _Safe_iterator(base() - __n, this->_M_sequence);
00396       }
00397 
00398       // ------ Utilities ------
00399       /**
00400        * @brief Return the underlying iterator
00401        */
00402       _Iterator&
00403       base() _GLIBCXX_NOEXCEPT { return *this; }
00404 
00405       const _Iterator&
00406       base() const _GLIBCXX_NOEXCEPT { return *this; }
00407 
00408       /**
00409        * @brief Conversion to underlying non-debug iterator to allow
00410        * better interaction with non-debug containers.
00411        */
00412       operator _Iterator() const _GLIBCXX_NOEXCEPT { return *this; }
00413 
00414       /** Attach iterator to the given sequence. */
00415       void
00416       _M_attach(_Safe_sequence_base* __seq)
00417       { _Safe_base::_M_attach(__seq, _M_constant()); }
00418 
00419       /** Likewise, but not thread-safe. */
00420       void
00421       _M_attach_single(_Safe_sequence_base* __seq)
00422       { _Safe_base::_M_attach_single(__seq, _M_constant()); }
00423 
00424       /// Is the iterator dereferenceable?
00425       bool
00426       _M_dereferenceable() const
00427       { return !this->_M_singular() && !_M_is_end() && !_M_is_before_begin(); }
00428 
00429       /// Is the iterator before a dereferenceable one?
00430       bool
00431       _M_before_dereferenceable() const
00432       {
00433         if (this->_M_incrementable())
00434         {
00435           _Iterator __base = base();
00436           return ++__base != _M_get_sequence()->_M_base().end();
00437         }
00438         return false;
00439       }
00440 
00441       /// Is the iterator incrementable?
00442       bool
00443       _M_incrementable() const
00444       { return !this->_M_singular() && !_M_is_end(); }
00445 
00446       // Is the iterator decrementable?
00447       bool
00448       _M_decrementable() const { return !_M_singular() && !_M_is_begin(); }
00449 
00450       // Can we advance the iterator @p __n steps (@p __n may be negative)
00451       bool
00452       _M_can_advance(const difference_type& __n) const;
00453 
00454       // Is the iterator range [*this, __rhs) valid?
00455       bool
00456       _M_valid_range(const _Safe_iterator& __rhs,
00457                      std::pair<difference_type, _Distance_precision>& __dist,
00458                      bool __check_dereferenceable = true) const;
00459 
00460       // The sequence this iterator references.
00461       typename
00462       __gnu_cxx::__conditional_type<std::__are_same<_Const_iterator,
00463                                                     _Safe_iterator>::__value,
00464                                     const _Sequence*,
00465                                     _Sequence*>::__type
00466       _M_get_sequence() const
00467       { return static_cast<_Sequence*>(_M_sequence); }
00468 
00469       /// Is this iterator equal to the sequence's begin() iterator?
00470       bool
00471       _M_is_begin() const
00472       { return base() == _M_get_sequence()->_M_base().begin(); }
00473 
00474       /// Is this iterator equal to the sequence's end() iterator?
00475       bool
00476       _M_is_end() const
00477       { return base() == _M_get_sequence()->_M_base().end(); }
00478 
00479       /// Is this iterator equal to the sequence's before_begin() iterator if
00480       /// any?
00481       bool
00482       _M_is_before_begin() const
00483       { return _BeforeBeginHelper<_Sequence>::_S_Is(*this); }
00484 
00485       /// Is this iterator equal to the sequence's before_begin() iterator if
00486       /// any or begin() otherwise?
00487       bool
00488       _M_is_beginnest() const
00489       { return _BeforeBeginHelper<_Sequence>::_S_Is_Beginnest(*this); }
00490     };
00491 
00492   template<typename _IteratorL, typename _IteratorR, typename _Sequence>
00493     inline bool
00494     operator==(const _Safe_iterator<_IteratorL, _Sequence>& __lhs,
00495                const _Safe_iterator<_IteratorR, _Sequence>& __rhs)
00496     _GLIBCXX_NOEXCEPT
00497     {
00498       _GLIBCXX_DEBUG_VERIFY(! __lhs._M_singular() && ! __rhs._M_singular(),
00499                             _M_message(__msg_iter_compare_bad)
00500                             ._M_iterator(__lhs, "lhs")
00501                             ._M_iterator(__rhs, "rhs"));
00502       _GLIBCXX_DEBUG_VERIFY(__lhs._M_can_compare(__rhs),
00503                             _M_message(__msg_compare_different)
00504                             ._M_iterator(__lhs, "lhs")
00505                             ._M_iterator(__rhs, "rhs"));
00506       return __lhs.base() == __rhs.base();
00507     }
00508 
00509   template<typename _Iterator, typename _Sequence>
00510     inline bool
00511     operator==(const _Safe_iterator<_Iterator, _Sequence>& __lhs,
00512                const _Safe_iterator<_Iterator, _Sequence>& __rhs)
00513     _GLIBCXX_NOEXCEPT
00514     {
00515       _GLIBCXX_DEBUG_VERIFY(! __lhs._M_singular() && ! __rhs._M_singular(),
00516                             _M_message(__msg_iter_compare_bad)
00517                             ._M_iterator(__lhs, "lhs")
00518                             ._M_iterator(__rhs, "rhs"));
00519       _GLIBCXX_DEBUG_VERIFY(__lhs._M_can_compare(__rhs),
00520                             _M_message(__msg_compare_different)
00521                             ._M_iterator(__lhs, "lhs")
00522                             ._M_iterator(__rhs, "rhs"));
00523       return __lhs.base() == __rhs.base();
00524     }
00525 
00526   template<typename _IteratorL, typename _IteratorR, typename _Sequence>
00527     inline bool
00528     operator!=(const _Safe_iterator<_IteratorL, _Sequence>& __lhs,
00529                const _Safe_iterator<_IteratorR, _Sequence>& __rhs)
00530     _GLIBCXX_NOEXCEPT
00531     {
00532       _GLIBCXX_DEBUG_VERIFY(! __lhs._M_singular() && ! __rhs._M_singular(),
00533                             _M_message(__msg_iter_compare_bad)
00534                             ._M_iterator(__lhs, "lhs")
00535                             ._M_iterator(__rhs, "rhs"));
00536       _GLIBCXX_DEBUG_VERIFY(__lhs._M_can_compare(__rhs),
00537                             _M_message(__msg_compare_different)
00538                             ._M_iterator(__lhs, "lhs")
00539                             ._M_iterator(__rhs, "rhs"));
00540       return __lhs.base() != __rhs.base();
00541     }
00542 
00543   template<typename _Iterator, typename _Sequence>
00544     inline bool
00545     operator!=(const _Safe_iterator<_Iterator, _Sequence>& __lhs,
00546                const _Safe_iterator<_Iterator, _Sequence>& __rhs)
00547     _GLIBCXX_NOEXCEPT
00548     {
00549       _GLIBCXX_DEBUG_VERIFY(! __lhs._M_singular() && ! __rhs._M_singular(),
00550                             _M_message(__msg_iter_compare_bad)
00551                             ._M_iterator(__lhs, "lhs")
00552                             ._M_iterator(__rhs, "rhs"));
00553       _GLIBCXX_DEBUG_VERIFY(__lhs._M_can_compare(__rhs),
00554                             _M_message(__msg_compare_different)
00555                             ._M_iterator(__lhs, "lhs")
00556                             ._M_iterator(__rhs, "rhs"));
00557       return __lhs.base() != __rhs.base();
00558     }
00559 
00560   template<typename _IteratorL, typename _IteratorR, typename _Sequence>
00561     inline bool
00562     operator<(const _Safe_iterator<_IteratorL, _Sequence>& __lhs,
00563               const _Safe_iterator<_IteratorR, _Sequence>& __rhs)
00564     _GLIBCXX_NOEXCEPT
00565     {
00566       _GLIBCXX_DEBUG_VERIFY(! __lhs._M_singular() && ! __rhs._M_singular(),
00567                             _M_message(__msg_iter_order_bad)
00568                             ._M_iterator(__lhs, "lhs")
00569                             ._M_iterator(__rhs, "rhs"));
00570       _GLIBCXX_DEBUG_VERIFY(__lhs._M_can_compare(__rhs),
00571                             _M_message(__msg_order_different)
00572                             ._M_iterator(__lhs, "lhs")
00573                             ._M_iterator(__rhs, "rhs"));
00574       return __lhs.base() < __rhs.base();
00575     }
00576 
00577   template<typename _Iterator, typename _Sequence>
00578     inline bool
00579     operator<(const _Safe_iterator<_Iterator, _Sequence>& __lhs,
00580               const _Safe_iterator<_Iterator, _Sequence>& __rhs)
00581     _GLIBCXX_NOEXCEPT
00582     {
00583       _GLIBCXX_DEBUG_VERIFY(! __lhs._M_singular() && ! __rhs._M_singular(),
00584                             _M_message(__msg_iter_order_bad)
00585                             ._M_iterator(__lhs, "lhs")
00586                             ._M_iterator(__rhs, "rhs"));
00587       _GLIBCXX_DEBUG_VERIFY(__lhs._M_can_compare(__rhs),
00588                             _M_message(__msg_order_different)
00589                             ._M_iterator(__lhs, "lhs")
00590                             ._M_iterator(__rhs, "rhs"));
00591       return __lhs.base() < __rhs.base();
00592     }
00593 
00594   template<typename _IteratorL, typename _IteratorR, typename _Sequence>
00595     inline bool
00596     operator<=(const _Safe_iterator<_IteratorL, _Sequence>& __lhs,
00597                const _Safe_iterator<_IteratorR, _Sequence>& __rhs)
00598     _GLIBCXX_NOEXCEPT
00599     {
00600       _GLIBCXX_DEBUG_VERIFY(! __lhs._M_singular() && ! __rhs._M_singular(),
00601                             _M_message(__msg_iter_order_bad)
00602                             ._M_iterator(__lhs, "lhs")
00603                             ._M_iterator(__rhs, "rhs"));
00604       _GLIBCXX_DEBUG_VERIFY(__lhs._M_can_compare(__rhs),
00605                             _M_message(__msg_order_different)
00606                             ._M_iterator(__lhs, "lhs")
00607                             ._M_iterator(__rhs, "rhs"));
00608       return __lhs.base() <= __rhs.base();
00609     }
00610 
00611   template<typename _Iterator, typename _Sequence>
00612     inline bool
00613     operator<=(const _Safe_iterator<_Iterator, _Sequence>& __lhs,
00614                const _Safe_iterator<_Iterator, _Sequence>& __rhs)
00615     _GLIBCXX_NOEXCEPT
00616     {
00617       _GLIBCXX_DEBUG_VERIFY(! __lhs._M_singular() && ! __rhs._M_singular(),
00618                             _M_message(__msg_iter_order_bad)
00619                             ._M_iterator(__lhs, "lhs")
00620                             ._M_iterator(__rhs, "rhs"));
00621       _GLIBCXX_DEBUG_VERIFY(__lhs._M_can_compare(__rhs),
00622                             _M_message(__msg_order_different)
00623                             ._M_iterator(__lhs, "lhs")
00624                             ._M_iterator(__rhs, "rhs"));
00625       return __lhs.base() <= __rhs.base();
00626     }
00627 
00628   template<typename _IteratorL, typename _IteratorR, typename _Sequence>
00629     inline bool
00630     operator>(const _Safe_iterator<_IteratorL, _Sequence>& __lhs,
00631               const _Safe_iterator<_IteratorR, _Sequence>& __rhs)
00632     _GLIBCXX_NOEXCEPT
00633     {
00634       _GLIBCXX_DEBUG_VERIFY(! __lhs._M_singular() && ! __rhs._M_singular(),
00635                             _M_message(__msg_iter_order_bad)
00636                             ._M_iterator(__lhs, "lhs")
00637                             ._M_iterator(__rhs, "rhs"));
00638       _GLIBCXX_DEBUG_VERIFY(__lhs._M_can_compare(__rhs),
00639                             _M_message(__msg_order_different)
00640                             ._M_iterator(__lhs, "lhs")
00641                             ._M_iterator(__rhs, "rhs"));
00642       return __lhs.base() > __rhs.base();
00643     }
00644 
00645   template<typename _Iterator, typename _Sequence>
00646     inline bool
00647     operator>(const _Safe_iterator<_Iterator, _Sequence>& __lhs,
00648               const _Safe_iterator<_Iterator, _Sequence>& __rhs)
00649     _GLIBCXX_NOEXCEPT
00650     {
00651       _GLIBCXX_DEBUG_VERIFY(! __lhs._M_singular() && ! __rhs._M_singular(),
00652                             _M_message(__msg_iter_order_bad)
00653                             ._M_iterator(__lhs, "lhs")
00654                             ._M_iterator(__rhs, "rhs"));
00655       _GLIBCXX_DEBUG_VERIFY(__lhs._M_can_compare(__rhs),
00656                             _M_message(__msg_order_different)
00657                             ._M_iterator(__lhs, "lhs")
00658                             ._M_iterator(__rhs, "rhs"));
00659       return __lhs.base() > __rhs.base();
00660     }
00661 
00662   template<typename _IteratorL, typename _IteratorR, typename _Sequence>
00663     inline bool
00664     operator>=(const _Safe_iterator<_IteratorL, _Sequence>& __lhs,
00665                const _Safe_iterator<_IteratorR, _Sequence>& __rhs)
00666     _GLIBCXX_NOEXCEPT
00667     {
00668       _GLIBCXX_DEBUG_VERIFY(! __lhs._M_singular() && ! __rhs._M_singular(),
00669                             _M_message(__msg_iter_order_bad)
00670                             ._M_iterator(__lhs, "lhs")
00671                             ._M_iterator(__rhs, "rhs"));
00672       _GLIBCXX_DEBUG_VERIFY(__lhs._M_can_compare(__rhs),
00673                             _M_message(__msg_order_different)
00674                             ._M_iterator(__lhs, "lhs")
00675                             ._M_iterator(__rhs, "rhs"));
00676       return __lhs.base() >= __rhs.base();
00677     }
00678 
00679   template<typename _Iterator, typename _Sequence>
00680     inline bool
00681     operator>=(const _Safe_iterator<_Iterator, _Sequence>& __lhs,
00682                const _Safe_iterator<_Iterator, _Sequence>& __rhs)
00683     _GLIBCXX_NOEXCEPT
00684     {
00685       _GLIBCXX_DEBUG_VERIFY(! __lhs._M_singular() && ! __rhs._M_singular(),
00686                             _M_message(__msg_iter_order_bad)
00687                             ._M_iterator(__lhs, "lhs")
00688                             ._M_iterator(__rhs, "rhs"));
00689       _GLIBCXX_DEBUG_VERIFY(__lhs._M_can_compare(__rhs),
00690                             _M_message(__msg_order_different)
00691                             ._M_iterator(__lhs, "lhs")
00692                             ._M_iterator(__rhs, "rhs"));
00693       return __lhs.base() >= __rhs.base();
00694     }
00695 
00696   // _GLIBCXX_RESOLVE_LIB_DEFECTS
00697   // According to the resolution of DR179 not only the various comparison
00698   // operators but also operator- must accept mixed iterator/const_iterator
00699   // parameters.
00700   template<typename _IteratorL, typename _IteratorR, typename _Sequence>
00701     inline typename _Safe_iterator<_IteratorL, _Sequence>::difference_type
00702     operator-(const _Safe_iterator<_IteratorL, _Sequence>& __lhs,
00703               const _Safe_iterator<_IteratorR, _Sequence>& __rhs)
00704     _GLIBCXX_NOEXCEPT
00705     {
00706       _GLIBCXX_DEBUG_VERIFY(! __lhs._M_singular() && ! __rhs._M_singular(),
00707                             _M_message(__msg_distance_bad)
00708                             ._M_iterator(__lhs, "lhs")
00709                             ._M_iterator(__rhs, "rhs"));
00710       _GLIBCXX_DEBUG_VERIFY(__lhs._M_can_compare(__rhs),
00711                             _M_message(__msg_distance_different)
00712                             ._M_iterator(__lhs, "lhs")
00713                             ._M_iterator(__rhs, "rhs"));
00714       return __lhs.base() - __rhs.base();
00715     }
00716 
00717    template<typename _Iterator, typename _Sequence>
00718      inline typename _Safe_iterator<_Iterator, _Sequence>::difference_type
00719      operator-(const _Safe_iterator<_Iterator, _Sequence>& __lhs,
00720                const _Safe_iterator<_Iterator, _Sequence>& __rhs)
00721     _GLIBCXX_NOEXCEPT
00722      {
00723        _GLIBCXX_DEBUG_VERIFY(! __lhs._M_singular() && ! __rhs._M_singular(),
00724                              _M_message(__msg_distance_bad)
00725                              ._M_iterator(__lhs, "lhs")
00726                              ._M_iterator(__rhs, "rhs"));
00727        _GLIBCXX_DEBUG_VERIFY(__lhs._M_can_compare(__rhs),
00728                              _M_message(__msg_distance_different)
00729                              ._M_iterator(__lhs, "lhs")
00730                              ._M_iterator(__rhs, "rhs"));
00731        return __lhs.base() - __rhs.base();
00732      }
00733 
00734   template<typename _Iterator, typename _Sequence>
00735     inline _Safe_iterator<_Iterator, _Sequence>
00736     operator+(typename _Safe_iterator<_Iterator,_Sequence>::difference_type __n,
00737               const _Safe_iterator<_Iterator, _Sequence>& __i) _GLIBCXX_NOEXCEPT
00738     { return __i + __n; }
00739 
00740   /** Safe iterators know if they are dereferenceable. */
00741   template<typename _Iterator, typename _Sequence>
00742     inline bool
00743     __check_dereferenceable(const _Safe_iterator<_Iterator, _Sequence>& __x)
00744     { return __x._M_dereferenceable(); }
00745 
00746   /** Safe iterators know how to check if they form a valid range. */
00747   template<typename _Iterator, typename _Sequence>
00748     inline bool
00749     __valid_range(const _Safe_iterator<_Iterator, _Sequence>& __first,
00750                   const _Safe_iterator<_Iterator, _Sequence>& __last,
00751                   typename _Distance_traits<_Iterator>::__type& __dist)
00752     { return __first._M_valid_range(__last, __dist); }
00753 
00754   /** Safe iterators can help to get better distance knowledge. */
00755   template<typename _Iterator, typename _Sequence>
00756     inline typename _Distance_traits<_Iterator>::__type
00757     __get_distance(const _Safe_iterator<_Iterator, _Sequence>& __first,
00758                    const _Safe_iterator<_Iterator, _Sequence>& __last,
00759                    std::random_access_iterator_tag)
00760     { return std::make_pair(__last.base() - __first.base(), __dp_exact); }
00761 
00762   template<typename _Iterator, typename _Sequence>
00763     inline typename _Distance_traits<_Iterator>::__type
00764     __get_distance(const _Safe_iterator<_Iterator, _Sequence>& __first,
00765                    const _Safe_iterator<_Iterator, _Sequence>& __last,
00766                    std::input_iterator_tag)
00767     {
00768       typedef typename _Distance_traits<_Iterator>::__type _Diff;
00769       typedef _Sequence_traits<_Sequence> _SeqTraits;
00770 
00771       if (__first.base() == __last.base())
00772         return std::make_pair(0, __dp_exact);
00773 
00774       if (__first._M_is_before_begin())
00775         {
00776           if (__last._M_is_begin())
00777             return std::make_pair(1, __dp_exact);
00778 
00779           return std::make_pair(1, __dp_sign);
00780         }
00781 
00782       if (__first._M_is_begin())
00783         {
00784           if (__last._M_is_before_begin())
00785             return std::make_pair(-1, __dp_exact);
00786 
00787           if (__last._M_is_end())
00788             return _SeqTraits::_S_size(*__first._M_get_sequence());
00789 
00790           return std::make_pair(1, __dp_sign);
00791         }
00792 
00793       if (__first._M_is_end())
00794         {
00795           if (__last._M_is_before_begin())
00796             return std::make_pair(-1, __dp_exact);
00797 
00798           if (__last._M_is_begin())
00799             {
00800               _Diff __diff = _SeqTraits::_S_size(*__first._M_get_sequence());
00801               return std::make_pair(-__diff.first, __diff.second);
00802             }
00803 
00804           return std::make_pair(-1, __dp_sign);
00805         }
00806 
00807       if (__last._M_is_before_begin() || __last._M_is_begin())
00808         return std::make_pair(-1, __dp_sign);
00809 
00810       if (__last._M_is_end())
00811         return std::make_pair(1, __dp_sign);
00812 
00813       return std::make_pair(1, __dp_equality);
00814     }
00815 
00816   // Get distance from sequence begin to specified iterator.
00817   template<typename _Iterator, typename _Sequence>
00818     inline typename _Distance_traits<_Iterator>::__type
00819     __get_distance_from_begin(const _Safe_iterator<_Iterator, _Sequence>& __it)
00820     {
00821       typedef _Sequence_traits<_Sequence> _SeqTraits;
00822 
00823       // No need to consider before_begin as this function is only used in
00824       // _M_can_advance which won't be used for forward_list iterators.
00825       if (__it._M_is_begin())
00826         return std::make_pair(0, __dp_exact);
00827 
00828       if (__it._M_is_end())
00829         return _SeqTraits::_S_size(*__it._M_get_sequence());
00830 
00831       typename _Distance_traits<_Iterator>::__type __res
00832         = __get_distance(__it._M_get_sequence()->_M_base().begin(), __it.base());
00833 
00834       if (__res.second == __dp_equality)
00835         return std::make_pair(1, __dp_sign);
00836 
00837       return __res;
00838     }
00839 
00840   // Get distance from specified iterator to sequence end.
00841   template<typename _Iterator, typename _Sequence>
00842     inline typename _Distance_traits<_Iterator>::__type
00843     __get_distance_to_end(const _Safe_iterator<_Iterator, _Sequence>& __it)
00844     {
00845       typedef _Sequence_traits<_Sequence> _SeqTraits;
00846 
00847       // No need to consider before_begin as this function is only used in
00848       // _M_can_advance which won't be used for forward_list iterators.
00849       if (__it._M_is_begin())
00850         return _SeqTraits::_S_size(*__it._M_get_sequence());
00851 
00852       if (__it._M_is_end())
00853         return std::make_pair(0, __dp_exact);
00854 
00855       typename _Distance_traits<_Iterator>::__type __res
00856         = __get_distance(__it.base(), __it._M_get_sequence()->_M_base().end());
00857 
00858       if (__res.second == __dp_equality)
00859         return std::make_pair(1, __dp_sign);
00860 
00861       return __res;
00862     }
00863 
00864 #if __cplusplus < 201103L
00865   template<typename _Iterator, typename _Sequence>
00866     struct __is_safe_random_iterator<_Safe_iterator<_Iterator, _Sequence> >
00867     : std::__are_same<std::random_access_iterator_tag,
00868                       typename std::iterator_traits<_Iterator>::
00869                       iterator_category>
00870     { };
00871 #else
00872   template<typename _Iterator, typename _Sequence>
00873     _Iterator
00874     __base(const _Safe_iterator<_Iterator, _Sequence>& __it,
00875            std::random_access_iterator_tag)
00876     { return __it.base(); }
00877 
00878   template<typename _Iterator, typename _Sequence>
00879     const _Safe_iterator<_Iterator, _Sequence>&
00880     __base(const _Safe_iterator<_Iterator, _Sequence>& __it,
00881            std::input_iterator_tag)
00882     { return __it; }
00883 
00884   template<typename _Iterator, typename _Sequence>
00885     auto
00886     __base(const _Safe_iterator<_Iterator, _Sequence>& __it)
00887     -> decltype(__base(__it, std::__iterator_category(__it)))
00888     { return __base(__it, std::__iterator_category(__it)); }
00889 #endif
00890 
00891 #if __cplusplus < 201103L
00892   template<typename _Iterator, typename _Sequence>
00893     struct _Unsafe_type<_Safe_iterator<_Iterator, _Sequence> >
00894     { typedef _Iterator _Type; };
00895 #endif
00896 
00897   template<typename _Iterator, typename _Sequence>
00898     inline _Iterator
00899     __unsafe(const _Safe_iterator<_Iterator, _Sequence>& __it)
00900     { return __it.base(); }
00901 
00902 } // namespace __gnu_debug
00903 
00904 #include <debug/safe_iterator.tcc>
00905 
00906 #endif