libstdc++
safe_iterator.h
Go to the documentation of this file.
00001 // Safe iterator implementation  -*- C++ -*-
00002 
00003 // Copyright (C) 2003-2016 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        *  @todo Make this correct w.r.t. iterators that return proxies
00278        */
00279       pointer
00280       operator->() const _GLIBCXX_NOEXCEPT
00281       {
00282         _GLIBCXX_DEBUG_VERIFY(this->_M_dereferenceable(),
00283                               _M_message(__msg_bad_deref)
00284                               ._M_iterator(*this, "this"));
00285         return std::__addressof(*base());
00286       }
00287 
00288       // ------ Input iterator requirements ------
00289       /**
00290        *  @brief Iterator preincrement
00291        *  @pre iterator is incrementable
00292        */
00293       _Safe_iterator&
00294       operator++() _GLIBCXX_NOEXCEPT
00295       {
00296         _GLIBCXX_DEBUG_VERIFY(this->_M_incrementable(),
00297                               _M_message(__msg_bad_inc)
00298                               ._M_iterator(*this, "this"));
00299         __gnu_cxx::__scoped_lock(this->_M_get_mutex());
00300         ++base();
00301         return *this;
00302       }
00303 
00304       /**
00305        *  @brief Iterator postincrement
00306        *  @pre iterator is incrementable
00307        */
00308       _Safe_iterator
00309       operator++(int) _GLIBCXX_NOEXCEPT
00310       {
00311         _GLIBCXX_DEBUG_VERIFY(this->_M_incrementable(),
00312                               _M_message(__msg_bad_inc)
00313                               ._M_iterator(*this, "this"));
00314         __gnu_cxx::__scoped_lock __l(this->_M_get_mutex());
00315         return _Safe_iterator(base()++, this->_M_sequence, _Attach_single());
00316       }
00317 
00318       // ------ Bidirectional iterator requirements ------
00319       /**
00320        *  @brief Iterator predecrement
00321        *  @pre iterator is decrementable
00322        */
00323       _Safe_iterator&
00324       operator--() _GLIBCXX_NOEXCEPT
00325       {
00326         _GLIBCXX_DEBUG_VERIFY(this->_M_decrementable(),
00327                               _M_message(__msg_bad_dec)
00328                               ._M_iterator(*this, "this"));
00329         __gnu_cxx::__scoped_lock __l(this->_M_get_mutex());
00330         --base();
00331         return *this;
00332       }
00333 
00334       /**
00335        *  @brief Iterator postdecrement
00336        *  @pre iterator is decrementable
00337        */
00338       _Safe_iterator
00339       operator--(int) _GLIBCXX_NOEXCEPT
00340       {
00341         _GLIBCXX_DEBUG_VERIFY(this->_M_decrementable(),
00342                               _M_message(__msg_bad_dec)
00343                               ._M_iterator(*this, "this"));
00344         __gnu_cxx::__scoped_lock __l(this->_M_get_mutex());
00345         return _Safe_iterator(base()--, this->_M_sequence, _Attach_single());
00346       }
00347 
00348       // ------ Random access iterator requirements ------
00349       reference
00350       operator[](const difference_type& __n) const _GLIBCXX_NOEXCEPT
00351       {
00352         _GLIBCXX_DEBUG_VERIFY(this->_M_can_advance(__n)
00353                               && this->_M_can_advance(__n+1),
00354                               _M_message(__msg_iter_subscript_oob)
00355                               ._M_iterator(*this)._M_integer(__n));
00356         return base()[__n];
00357       }
00358 
00359       _Safe_iterator&
00360       operator+=(const difference_type& __n) _GLIBCXX_NOEXCEPT
00361       {
00362         _GLIBCXX_DEBUG_VERIFY(this->_M_can_advance(__n),
00363                               _M_message(__msg_advance_oob)
00364                               ._M_iterator(*this)._M_integer(__n));
00365         __gnu_cxx::__scoped_lock __l(this->_M_get_mutex());
00366         base() += __n;
00367         return *this;
00368       }
00369 
00370       _Safe_iterator
00371       operator+(const difference_type& __n) const _GLIBCXX_NOEXCEPT
00372       {
00373         _GLIBCXX_DEBUG_VERIFY(this->_M_can_advance(__n),
00374                               _M_message(__msg_advance_oob)
00375                               ._M_iterator(*this)._M_integer(__n));
00376         return _Safe_iterator(base() + __n, this->_M_sequence);
00377       }
00378 
00379       _Safe_iterator&
00380       operator-=(const difference_type& __n) _GLIBCXX_NOEXCEPT
00381       {
00382         _GLIBCXX_DEBUG_VERIFY(this->_M_can_advance(-__n),
00383                               _M_message(__msg_retreat_oob)
00384                               ._M_iterator(*this)._M_integer(__n));
00385         __gnu_cxx::__scoped_lock __l(this->_M_get_mutex());
00386         base() -= __n;
00387         return *this;
00388       }
00389 
00390       _Safe_iterator
00391       operator-(const difference_type& __n) const _GLIBCXX_NOEXCEPT
00392       {
00393         _GLIBCXX_DEBUG_VERIFY(this->_M_can_advance(-__n),
00394                               _M_message(__msg_retreat_oob)
00395                               ._M_iterator(*this)._M_integer(__n));
00396         return _Safe_iterator(base() - __n, this->_M_sequence);
00397       }
00398 
00399       // ------ Utilities ------
00400       /**
00401        * @brief Return the underlying iterator
00402        */
00403       _Iterator&
00404       base() _GLIBCXX_NOEXCEPT { return *this; }
00405 
00406       const _Iterator&
00407       base() const _GLIBCXX_NOEXCEPT { return *this; }
00408 
00409       /**
00410        * @brief Conversion to underlying non-debug iterator to allow
00411        * better interaction with non-debug containers.
00412        */
00413       operator _Iterator() const _GLIBCXX_NOEXCEPT { return *this; }
00414 
00415       /** Attach iterator to the given sequence. */
00416       void
00417       _M_attach(_Safe_sequence_base* __seq)
00418       { _Safe_base::_M_attach(__seq, _M_constant()); }
00419 
00420       /** Likewise, but not thread-safe. */
00421       void
00422       _M_attach_single(_Safe_sequence_base* __seq)
00423       { _Safe_base::_M_attach_single(__seq, _M_constant()); }
00424 
00425       /// Is the iterator dereferenceable?
00426       bool
00427       _M_dereferenceable() const
00428       { return !this->_M_singular() && !_M_is_end() && !_M_is_before_begin(); }
00429 
00430       /// Is the iterator before a dereferenceable one?
00431       bool
00432       _M_before_dereferenceable() const
00433       {
00434         if (this->_M_incrementable())
00435         {
00436           _Iterator __base = base();
00437           return ++__base != _M_get_sequence()->_M_base().end();
00438         }
00439         return false;
00440       }
00441 
00442       /// Is the iterator incrementable?
00443       bool
00444       _M_incrementable() const
00445       { return !this->_M_singular() && !_M_is_end(); }
00446 
00447       // Is the iterator decrementable?
00448       bool
00449       _M_decrementable() const { return !_M_singular() && !_M_is_begin(); }
00450 
00451       // Can we advance the iterator @p __n steps (@p __n may be negative)
00452       bool
00453       _M_can_advance(const difference_type& __n) const;
00454 
00455       // Is the iterator range [*this, __rhs) valid?
00456       bool
00457       _M_valid_range(const _Safe_iterator& __rhs,
00458                      std::pair<difference_type, _Distance_precision>& __dist,
00459                      bool __check_dereferenceable = true) const;
00460 
00461       // The sequence this iterator references.
00462       typename
00463       __gnu_cxx::__conditional_type<std::__are_same<_Const_iterator,
00464                                                     _Safe_iterator>::__value,
00465                                     const _Sequence*,
00466                                     _Sequence*>::__type
00467       _M_get_sequence() const
00468       { return static_cast<_Sequence*>(_M_sequence); }
00469 
00470       /// Is this iterator equal to the sequence's begin() iterator?
00471       bool
00472       _M_is_begin() const
00473       { return base() == _M_get_sequence()->_M_base().begin(); }
00474 
00475       /// Is this iterator equal to the sequence's end() iterator?
00476       bool
00477       _M_is_end() const
00478       { return base() == _M_get_sequence()->_M_base().end(); }
00479 
00480       /// Is this iterator equal to the sequence's before_begin() iterator if
00481       /// any?
00482       bool
00483       _M_is_before_begin() const
00484       { return _BeforeBeginHelper<_Sequence>::_S_Is(*this); }
00485 
00486       /// Is this iterator equal to the sequence's before_begin() iterator if
00487       /// any or begin() otherwise?
00488       bool
00489       _M_is_beginnest() const
00490       { return _BeforeBeginHelper<_Sequence>::_S_Is_Beginnest(*this); }
00491     };
00492 
00493   template<typename _IteratorL, typename _IteratorR, typename _Sequence>
00494     inline bool
00495     operator==(const _Safe_iterator<_IteratorL, _Sequence>& __lhs,
00496                const _Safe_iterator<_IteratorR, _Sequence>& __rhs)
00497     _GLIBCXX_NOEXCEPT
00498     {
00499       _GLIBCXX_DEBUG_VERIFY(! __lhs._M_singular() && ! __rhs._M_singular(),
00500                             _M_message(__msg_iter_compare_bad)
00501                             ._M_iterator(__lhs, "lhs")
00502                             ._M_iterator(__rhs, "rhs"));
00503       _GLIBCXX_DEBUG_VERIFY(__lhs._M_can_compare(__rhs),
00504                             _M_message(__msg_compare_different)
00505                             ._M_iterator(__lhs, "lhs")
00506                             ._M_iterator(__rhs, "rhs"));
00507       return __lhs.base() == __rhs.base();
00508     }
00509 
00510   template<typename _Iterator, typename _Sequence>
00511     inline bool
00512     operator==(const _Safe_iterator<_Iterator, _Sequence>& __lhs,
00513                const _Safe_iterator<_Iterator, _Sequence>& __rhs)
00514     _GLIBCXX_NOEXCEPT
00515     {
00516       _GLIBCXX_DEBUG_VERIFY(! __lhs._M_singular() && ! __rhs._M_singular(),
00517                             _M_message(__msg_iter_compare_bad)
00518                             ._M_iterator(__lhs, "lhs")
00519                             ._M_iterator(__rhs, "rhs"));
00520       _GLIBCXX_DEBUG_VERIFY(__lhs._M_can_compare(__rhs),
00521                             _M_message(__msg_compare_different)
00522                             ._M_iterator(__lhs, "lhs")
00523                             ._M_iterator(__rhs, "rhs"));
00524       return __lhs.base() == __rhs.base();
00525     }
00526 
00527   template<typename _IteratorL, typename _IteratorR, typename _Sequence>
00528     inline bool
00529     operator!=(const _Safe_iterator<_IteratorL, _Sequence>& __lhs,
00530                const _Safe_iterator<_IteratorR, _Sequence>& __rhs)
00531     _GLIBCXX_NOEXCEPT
00532     {
00533       _GLIBCXX_DEBUG_VERIFY(! __lhs._M_singular() && ! __rhs._M_singular(),
00534                             _M_message(__msg_iter_compare_bad)
00535                             ._M_iterator(__lhs, "lhs")
00536                             ._M_iterator(__rhs, "rhs"));
00537       _GLIBCXX_DEBUG_VERIFY(__lhs._M_can_compare(__rhs),
00538                             _M_message(__msg_compare_different)
00539                             ._M_iterator(__lhs, "lhs")
00540                             ._M_iterator(__rhs, "rhs"));
00541       return __lhs.base() != __rhs.base();
00542     }
00543 
00544   template<typename _Iterator, typename _Sequence>
00545     inline bool
00546     operator!=(const _Safe_iterator<_Iterator, _Sequence>& __lhs,
00547                const _Safe_iterator<_Iterator, _Sequence>& __rhs)
00548     _GLIBCXX_NOEXCEPT
00549     {
00550       _GLIBCXX_DEBUG_VERIFY(! __lhs._M_singular() && ! __rhs._M_singular(),
00551                             _M_message(__msg_iter_compare_bad)
00552                             ._M_iterator(__lhs, "lhs")
00553                             ._M_iterator(__rhs, "rhs"));
00554       _GLIBCXX_DEBUG_VERIFY(__lhs._M_can_compare(__rhs),
00555                             _M_message(__msg_compare_different)
00556                             ._M_iterator(__lhs, "lhs")
00557                             ._M_iterator(__rhs, "rhs"));
00558       return __lhs.base() != __rhs.base();
00559     }
00560 
00561   template<typename _IteratorL, typename _IteratorR, typename _Sequence>
00562     inline bool
00563     operator<(const _Safe_iterator<_IteratorL, _Sequence>& __lhs,
00564               const _Safe_iterator<_IteratorR, _Sequence>& __rhs)
00565     _GLIBCXX_NOEXCEPT
00566     {
00567       _GLIBCXX_DEBUG_VERIFY(! __lhs._M_singular() && ! __rhs._M_singular(),
00568                             _M_message(__msg_iter_order_bad)
00569                             ._M_iterator(__lhs, "lhs")
00570                             ._M_iterator(__rhs, "rhs"));
00571       _GLIBCXX_DEBUG_VERIFY(__lhs._M_can_compare(__rhs),
00572                             _M_message(__msg_order_different)
00573                             ._M_iterator(__lhs, "lhs")
00574                             ._M_iterator(__rhs, "rhs"));
00575       return __lhs.base() < __rhs.base();
00576     }
00577 
00578   template<typename _Iterator, typename _Sequence>
00579     inline bool
00580     operator<(const _Safe_iterator<_Iterator, _Sequence>& __lhs,
00581               const _Safe_iterator<_Iterator, _Sequence>& __rhs)
00582     _GLIBCXX_NOEXCEPT
00583     {
00584       _GLIBCXX_DEBUG_VERIFY(! __lhs._M_singular() && ! __rhs._M_singular(),
00585                             _M_message(__msg_iter_order_bad)
00586                             ._M_iterator(__lhs, "lhs")
00587                             ._M_iterator(__rhs, "rhs"));
00588       _GLIBCXX_DEBUG_VERIFY(__lhs._M_can_compare(__rhs),
00589                             _M_message(__msg_order_different)
00590                             ._M_iterator(__lhs, "lhs")
00591                             ._M_iterator(__rhs, "rhs"));
00592       return __lhs.base() < __rhs.base();
00593     }
00594 
00595   template<typename _IteratorL, typename _IteratorR, typename _Sequence>
00596     inline bool
00597     operator<=(const _Safe_iterator<_IteratorL, _Sequence>& __lhs,
00598                const _Safe_iterator<_IteratorR, _Sequence>& __rhs)
00599     _GLIBCXX_NOEXCEPT
00600     {
00601       _GLIBCXX_DEBUG_VERIFY(! __lhs._M_singular() && ! __rhs._M_singular(),
00602                             _M_message(__msg_iter_order_bad)
00603                             ._M_iterator(__lhs, "lhs")
00604                             ._M_iterator(__rhs, "rhs"));
00605       _GLIBCXX_DEBUG_VERIFY(__lhs._M_can_compare(__rhs),
00606                             _M_message(__msg_order_different)
00607                             ._M_iterator(__lhs, "lhs")
00608                             ._M_iterator(__rhs, "rhs"));
00609       return __lhs.base() <= __rhs.base();
00610     }
00611 
00612   template<typename _Iterator, typename _Sequence>
00613     inline bool
00614     operator<=(const _Safe_iterator<_Iterator, _Sequence>& __lhs,
00615                const _Safe_iterator<_Iterator, _Sequence>& __rhs)
00616     _GLIBCXX_NOEXCEPT
00617     {
00618       _GLIBCXX_DEBUG_VERIFY(! __lhs._M_singular() && ! __rhs._M_singular(),
00619                             _M_message(__msg_iter_order_bad)
00620                             ._M_iterator(__lhs, "lhs")
00621                             ._M_iterator(__rhs, "rhs"));
00622       _GLIBCXX_DEBUG_VERIFY(__lhs._M_can_compare(__rhs),
00623                             _M_message(__msg_order_different)
00624                             ._M_iterator(__lhs, "lhs")
00625                             ._M_iterator(__rhs, "rhs"));
00626       return __lhs.base() <= __rhs.base();
00627     }
00628 
00629   template<typename _IteratorL, typename _IteratorR, typename _Sequence>
00630     inline bool
00631     operator>(const _Safe_iterator<_IteratorL, _Sequence>& __lhs,
00632               const _Safe_iterator<_IteratorR, _Sequence>& __rhs)
00633     _GLIBCXX_NOEXCEPT
00634     {
00635       _GLIBCXX_DEBUG_VERIFY(! __lhs._M_singular() && ! __rhs._M_singular(),
00636                             _M_message(__msg_iter_order_bad)
00637                             ._M_iterator(__lhs, "lhs")
00638                             ._M_iterator(__rhs, "rhs"));
00639       _GLIBCXX_DEBUG_VERIFY(__lhs._M_can_compare(__rhs),
00640                             _M_message(__msg_order_different)
00641                             ._M_iterator(__lhs, "lhs")
00642                             ._M_iterator(__rhs, "rhs"));
00643       return __lhs.base() > __rhs.base();
00644     }
00645 
00646   template<typename _Iterator, typename _Sequence>
00647     inline bool
00648     operator>(const _Safe_iterator<_Iterator, _Sequence>& __lhs,
00649               const _Safe_iterator<_Iterator, _Sequence>& __rhs)
00650     _GLIBCXX_NOEXCEPT
00651     {
00652       _GLIBCXX_DEBUG_VERIFY(! __lhs._M_singular() && ! __rhs._M_singular(),
00653                             _M_message(__msg_iter_order_bad)
00654                             ._M_iterator(__lhs, "lhs")
00655                             ._M_iterator(__rhs, "rhs"));
00656       _GLIBCXX_DEBUG_VERIFY(__lhs._M_can_compare(__rhs),
00657                             _M_message(__msg_order_different)
00658                             ._M_iterator(__lhs, "lhs")
00659                             ._M_iterator(__rhs, "rhs"));
00660       return __lhs.base() > __rhs.base();
00661     }
00662 
00663   template<typename _IteratorL, typename _IteratorR, typename _Sequence>
00664     inline bool
00665     operator>=(const _Safe_iterator<_IteratorL, _Sequence>& __lhs,
00666                const _Safe_iterator<_IteratorR, _Sequence>& __rhs)
00667     _GLIBCXX_NOEXCEPT
00668     {
00669       _GLIBCXX_DEBUG_VERIFY(! __lhs._M_singular() && ! __rhs._M_singular(),
00670                             _M_message(__msg_iter_order_bad)
00671                             ._M_iterator(__lhs, "lhs")
00672                             ._M_iterator(__rhs, "rhs"));
00673       _GLIBCXX_DEBUG_VERIFY(__lhs._M_can_compare(__rhs),
00674                             _M_message(__msg_order_different)
00675                             ._M_iterator(__lhs, "lhs")
00676                             ._M_iterator(__rhs, "rhs"));
00677       return __lhs.base() >= __rhs.base();
00678     }
00679 
00680   template<typename _Iterator, typename _Sequence>
00681     inline bool
00682     operator>=(const _Safe_iterator<_Iterator, _Sequence>& __lhs,
00683                const _Safe_iterator<_Iterator, _Sequence>& __rhs)
00684     _GLIBCXX_NOEXCEPT
00685     {
00686       _GLIBCXX_DEBUG_VERIFY(! __lhs._M_singular() && ! __rhs._M_singular(),
00687                             _M_message(__msg_iter_order_bad)
00688                             ._M_iterator(__lhs, "lhs")
00689                             ._M_iterator(__rhs, "rhs"));
00690       _GLIBCXX_DEBUG_VERIFY(__lhs._M_can_compare(__rhs),
00691                             _M_message(__msg_order_different)
00692                             ._M_iterator(__lhs, "lhs")
00693                             ._M_iterator(__rhs, "rhs"));
00694       return __lhs.base() >= __rhs.base();
00695     }
00696 
00697   // _GLIBCXX_RESOLVE_LIB_DEFECTS
00698   // According to the resolution of DR179 not only the various comparison
00699   // operators but also operator- must accept mixed iterator/const_iterator
00700   // parameters.
00701   template<typename _IteratorL, typename _IteratorR, typename _Sequence>
00702     inline typename _Safe_iterator<_IteratorL, _Sequence>::difference_type
00703     operator-(const _Safe_iterator<_IteratorL, _Sequence>& __lhs,
00704               const _Safe_iterator<_IteratorR, _Sequence>& __rhs)
00705     _GLIBCXX_NOEXCEPT
00706     {
00707       _GLIBCXX_DEBUG_VERIFY(! __lhs._M_singular() && ! __rhs._M_singular(),
00708                             _M_message(__msg_distance_bad)
00709                             ._M_iterator(__lhs, "lhs")
00710                             ._M_iterator(__rhs, "rhs"));
00711       _GLIBCXX_DEBUG_VERIFY(__lhs._M_can_compare(__rhs),
00712                             _M_message(__msg_distance_different)
00713                             ._M_iterator(__lhs, "lhs")
00714                             ._M_iterator(__rhs, "rhs"));
00715       return __lhs.base() - __rhs.base();
00716     }
00717 
00718    template<typename _Iterator, typename _Sequence>
00719      inline typename _Safe_iterator<_Iterator, _Sequence>::difference_type
00720      operator-(const _Safe_iterator<_Iterator, _Sequence>& __lhs,
00721                const _Safe_iterator<_Iterator, _Sequence>& __rhs)
00722     _GLIBCXX_NOEXCEPT
00723      {
00724        _GLIBCXX_DEBUG_VERIFY(! __lhs._M_singular() && ! __rhs._M_singular(),
00725                              _M_message(__msg_distance_bad)
00726                              ._M_iterator(__lhs, "lhs")
00727                              ._M_iterator(__rhs, "rhs"));
00728        _GLIBCXX_DEBUG_VERIFY(__lhs._M_can_compare(__rhs),
00729                              _M_message(__msg_distance_different)
00730                              ._M_iterator(__lhs, "lhs")
00731                              ._M_iterator(__rhs, "rhs"));
00732        return __lhs.base() - __rhs.base();
00733      }
00734 
00735   template<typename _Iterator, typename _Sequence>
00736     inline _Safe_iterator<_Iterator, _Sequence>
00737     operator+(typename _Safe_iterator<_Iterator,_Sequence>::difference_type __n,
00738               const _Safe_iterator<_Iterator, _Sequence>& __i) _GLIBCXX_NOEXCEPT
00739     { return __i + __n; }
00740 
00741   /** Safe iterators know if they are dereferenceable. */
00742   template<typename _Iterator, typename _Sequence>
00743     inline bool
00744     __check_dereferenceable(const _Safe_iterator<_Iterator, _Sequence>& __x)
00745     { return __x._M_dereferenceable(); }
00746 
00747   /** Safe iterators know how to check if they form a valid range. */
00748   template<typename _Iterator, typename _Sequence>
00749     inline bool
00750     __valid_range(const _Safe_iterator<_Iterator, _Sequence>& __first,
00751                   const _Safe_iterator<_Iterator, _Sequence>& __last,
00752                   typename _Distance_traits<_Iterator>::__type& __dist)
00753     { return __first._M_valid_range(__last, __dist); }
00754 
00755   /** Safe iterators can help to get better distance knowledge. */
00756   template<typename _Iterator, typename _Sequence>
00757     inline typename _Distance_traits<_Iterator>::__type
00758     __get_distance(const _Safe_iterator<_Iterator, _Sequence>& __first,
00759                    const _Safe_iterator<_Iterator, _Sequence>& __last,
00760                    std::random_access_iterator_tag)
00761     { return std::make_pair(__last.base() - __first.base(), __dp_exact); }
00762 
00763   template<typename _Iterator, typename _Sequence>
00764     inline typename _Distance_traits<_Iterator>::__type
00765     __get_distance(const _Safe_iterator<_Iterator, _Sequence>& __first,
00766                    const _Safe_iterator<_Iterator, _Sequence>& __last,
00767                    std::input_iterator_tag)
00768     {
00769       typedef typename _Distance_traits<_Iterator>::__type _Diff;
00770       typedef _Sequence_traits<_Sequence> _SeqTraits;
00771 
00772       if (__first.base() == __last.base())
00773         return std::make_pair(0, __dp_exact);
00774 
00775       if (__first._M_is_before_begin())
00776         {
00777           if (__last._M_is_begin())
00778             return std::make_pair(1, __dp_exact);
00779 
00780           return std::make_pair(1, __dp_sign);
00781         }
00782 
00783       if (__first._M_is_begin())
00784         {
00785           if (__last._M_is_before_begin())
00786             return std::make_pair(-1, __dp_exact);
00787 
00788           if (__last._M_is_end())
00789             return _SeqTraits::_S_size(*__first._M_get_sequence());
00790 
00791           return std::make_pair(1, __dp_sign);
00792         }
00793 
00794       if (__first._M_is_end())
00795         {
00796           if (__last._M_is_before_begin())
00797             return std::make_pair(-1, __dp_exact);
00798 
00799           if (__last._M_is_begin())
00800             {
00801               _Diff __diff = _SeqTraits::_S_size(*__first._M_get_sequence());
00802               return std::make_pair(-__diff.first, __diff.second);
00803             }
00804 
00805           return std::make_pair(-1, __dp_sign);
00806         }
00807 
00808       if (__last._M_is_before_begin() || __last._M_is_begin())
00809         return std::make_pair(-1, __dp_sign);
00810 
00811       if (__last._M_is_end())
00812         return std::make_pair(1, __dp_sign);
00813 
00814       return std::make_pair(1, __dp_equality);
00815     }
00816 
00817   // Get distance from sequence begin to specified iterator.
00818   template<typename _Iterator, typename _Sequence>
00819     inline typename _Distance_traits<_Iterator>::__type
00820     __get_distance_from_begin(const _Safe_iterator<_Iterator, _Sequence>& __it)
00821     {
00822       typedef _Sequence_traits<_Sequence> _SeqTraits;
00823 
00824       // No need to consider before_begin as this function is only used in
00825       // _M_can_advance which won't be used for forward_list iterators.
00826       if (__it._M_is_begin())
00827         return std::make_pair(0, __dp_exact);
00828 
00829       if (__it._M_is_end())
00830         return _SeqTraits::_S_size(*__it._M_get_sequence());
00831 
00832       typename _Distance_traits<_Iterator>::__type __res
00833         = __get_distance(__it._M_get_sequence()->_M_base().begin(), __it.base());
00834 
00835       if (__res.second == __dp_equality)
00836         return std::make_pair(1, __dp_sign);
00837 
00838       return __res;
00839     }
00840 
00841   // Get distance from specified iterator to sequence end.
00842   template<typename _Iterator, typename _Sequence>
00843     inline typename _Distance_traits<_Iterator>::__type
00844     __get_distance_to_end(const _Safe_iterator<_Iterator, _Sequence>& __it)
00845     {
00846       typedef _Sequence_traits<_Sequence> _SeqTraits;
00847 
00848       // No need to consider before_begin as this function is only used in
00849       // _M_can_advance which won't be used for forward_list iterators.
00850       if (__it._M_is_begin())
00851         return _SeqTraits::_S_size(*__it._M_get_sequence());
00852 
00853       if (__it._M_is_end())
00854         return std::make_pair(0, __dp_exact);
00855 
00856       typename _Distance_traits<_Iterator>::__type __res
00857         = __get_distance(__it.base(), __it._M_get_sequence()->_M_base().end());
00858 
00859       if (__res.second == __dp_equality)
00860         return std::make_pair(1, __dp_sign);
00861 
00862       return __res;
00863     }
00864 
00865 #if __cplusplus < 201103L
00866   template<typename _Iterator, typename _Sequence>
00867     struct __is_safe_random_iterator<_Safe_iterator<_Iterator, _Sequence> >
00868     : std::__are_same<std::random_access_iterator_tag,
00869                       typename std::iterator_traits<_Iterator>::
00870                       iterator_category>
00871     { };
00872 #else
00873   template<typename _Iterator, typename _Sequence>
00874     _Iterator
00875     __base(const _Safe_iterator<_Iterator, _Sequence>& __it,
00876            std::random_access_iterator_tag)
00877     { return __it.base(); }
00878 
00879   template<typename _Iterator, typename _Sequence>
00880     const _Safe_iterator<_Iterator, _Sequence>&
00881     __base(const _Safe_iterator<_Iterator, _Sequence>& __it,
00882            std::input_iterator_tag)
00883     { return __it; }
00884 
00885   template<typename _Iterator, typename _Sequence>
00886     auto
00887     __base(const _Safe_iterator<_Iterator, _Sequence>& __it)
00888     -> decltype(__base(__it, std::__iterator_category(__it)))
00889     { return __base(__it, std::__iterator_category(__it)); }
00890 #endif
00891 
00892 #if __cplusplus < 201103L
00893   template<typename _Iterator, typename _Sequence>
00894     struct _Unsafe_type<_Safe_iterator<_Iterator, _Sequence> >
00895     { typedef _Iterator _Type; };
00896 #endif
00897 
00898   template<typename _Iterator, typename _Sequence>
00899     inline _Iterator
00900     __unsafe(const _Safe_iterator<_Iterator, _Sequence>& __it)
00901     { return __it.base(); }
00902 
00903 } // namespace __gnu_debug
00904 
00905 #include <debug/safe_iterator.tcc>
00906 
00907 #endif