libstdc++-v3/include/debug/safe_iterator.h

   1 // Safe iterator implementation  -*- C++ -*-
   2
   3 // Copyright (C) 2003, 2004, 2005, 2006, 2009, 2010, 2011, 2012
   4 // Free Software Foundation, Inc.
   5 //
   6 // This file is part of the GNU ISO C++ Library.  This library is free
   7 // software; you can redistribute it and/or modify it under the
   8 // terms of the GNU General Public License as published by the
   9 // Free Software Foundation; either version 3, or (at your option)
  10 // any later version.
  11
  12 // This library is distributed in the hope that it will be useful,
  13 // but WITHOUT ANY WARRANTY; without even the implied warranty of
  14 // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  15 // GNU General Public License for more details.
  16
  17 // Under Section 7 of GPL version 3, you are granted additional
  18 // permissions described in the GCC Runtime Library Exception, version
  19 // 3.1, as published by the Free Software Foundation.
  20
  21 // You should have received a copy of the GNU General Public License and
  22 // a copy of the GCC Runtime Library Exception along with this program;
  23 // see the files COPYING3 and COPYING.RUNTIME respectively.  If not, see
  24 // <http://www.gnu.org/licenses/>.
  25
  26 /** @file debug/safe_iterator.h
  27  *  This file is a GNU debug extension to the Standard C++ Library.
  28  */
  29
  30 #ifndef _GLIBCXX_DEBUG_SAFE_ITERATOR_H
  31 #define _GLIBCXX_DEBUG_SAFE_ITERATOR_H 1
  32
  33 #include <debug/debug.h>
  34 #include <debug/macros.h>
  35 #include <debug/functions.h>
  36 #include <debug/safe_base.h>
  37 #include <bits/stl_pair.h>
  38 #include <bits/stl_iterator_base_types.h> // for _Iter_base
  39 #include <ext/type_traits.h>
  40
  41 namespace __gnu_debug
  42 {
  43   /** Helper struct to deal with sequence offering a before_begin
  44    *  iterator.
  45    **/
  46   template <typename _Sequence>
  47     struct _BeforeBeginHelper
  48     {
  49       typedef typename _Sequence::const_iterator _It;
  50       typedef typename _It::iterator_type _BaseIt;
  51
  52       static bool
  53       _M_Is(_BaseIt __it, const _Sequence* __seq)
  54       { return false; }
  55     };
  56
  57   /** Iterators that derive from _Safe_iterator_base but that aren't
  58    *  _Safe_iterators can be determined singular or non-singular via
  59    *  _Safe_iterator_base.
  60    */
  61   inline bool
  62   __check_singular_aux(const _Safe_iterator_base* __x)
  63   { return __x->_M_singular(); }
  64
  65   /** The precision to which we can calculate the distance between
  66    *  two iterators.
  67    */
  68   enum _Distance_precision
  69     {
  70       __dp_equality, //< Can compare iterator equality, only
  71       __dp_sign,     //< Can determine equality and ordering
  72       __dp_exact     //< Can determine distance precisely
  73     };
  74
  75   /** Determine the distance between two iterators with some known
  76    *    precision.
  77   */
  78   template<typename _Iterator1, typename _Iterator2>
  79     inline std::pair<typename std::iterator_traits<_Iterator1>::difference_type,
  80                      _Distance_precision>
  81     __get_distance(const _Iterator1& __lhs, const _Iterator2& __rhs,
  82                    std::random_access_iterator_tag)
  83     { return std::make_pair(__rhs - __lhs, __dp_exact); }
  84
  85   template<typename _Iterator1, typename _Iterator2>
  86     inline std::pair<typename std::iterator_traits<_Iterator1>::difference_type,
  87                      _Distance_precision>
  88     __get_distance(const _Iterator1& __lhs, const _Iterator2& __rhs,
  89                    std::forward_iterator_tag)
  90     { return std::make_pair(__lhs == __rhs? 0 : 1, __dp_equality); }
  91
  92   template<typename _Iterator1, typename _Iterator2>
  93     inline std::pair<typename std::iterator_traits<_Iterator1>::difference_type,
  94                      _Distance_precision>
  95     __get_distance(const _Iterator1& __lhs, const _Iterator2& __rhs)
  96     {
  97       typedef typename std::iterator_traits<_Iterator1>::iterator_category
  98           _Category;
  99       return __get_distance(__lhs, __rhs, _Category());
 100     }
 101
 102   /** \brief Safe iterator wrapper.
 103    *
 104    *  The class template %_Safe_iterator is a wrapper around an
 105    *  iterator that tracks the iterator's movement among sequences and
 106    *  checks that operations performed on the "safe" iterator are
 107    *  legal. In additional to the basic iterator operations (which are
 108    *  validated, and then passed to the underlying iterator),
 109    *  %_Safe_iterator has member functions for iterator invalidation,
 110    *  attaching/detaching the iterator from sequences, and querying
 111    *  the iterator's state.
 112    */
 113   template<typename _Iterator, typename _Sequence>
 114     class _Safe_iterator : public _Safe_iterator_base
 115     {
 116       typedef _Safe_iterator _Self;
 117
 118       /// The underlying iterator
 119       _Iterator _M_current;
 120
 121       /// Determine if this is a constant iterator.
 122       bool
 123       _M_constant() const
 124       {
 125         typedef typename _Sequence::const_iterator const_iterator;
 126         return std::__are_same<const_iterator, _Safe_iterator>::__value;
 127       }
 128
 129       typedef std::iterator_traits<_Iterator> _Traits;
 130
 131     public:
 132       typedef _Iterator                           iterator_type;
 133       typedef typename _Traits::iterator_category iterator_category;
 134       typedef typename _Traits::value_type        value_type;
 135       typedef typename _Traits::difference_type   difference_type;
 136       typedef typename _Traits::reference         reference;
 137       typedef typename _Traits::pointer           pointer;
 138
 139       /// @post the iterator is singular and unattached
 140       _Safe_iterator() : _M_current() { }
 141
 142       /**
 143        * @brief Safe iterator construction from an unsafe iterator and
 144        * its sequence.
 145        *
 146        * @pre @p seq is not NULL
 147        * @post this is not singular
 148        */
 149       _Safe_iterator(const _Iterator& __i, const _Sequence* __seq)
 150       : _Safe_iterator_base(__seq, _M_constant()), _M_current(__i)
 151       {
 152         _GLIBCXX_DEBUG_VERIFY(! this->_M_singular(),
 153                               _M_message(__msg_init_singular)
 154                               ._M_iterator(*this, "this"));
 155       }
 156
 157       /**
 158        * @brief Copy construction.
 159        */
 160       _Safe_iterator(const _Safe_iterator& __x)
 161       : _Safe_iterator_base(__x, _M_constant()), _M_current(__x._M_current)
 162       {
 163         // _GLIBCXX_RESOLVE_LIB_DEFECTS
 164         // DR 408. Is vector<reverse_iterator<char*> > forbidden?
 165         _GLIBCXX_DEBUG_VERIFY(!__x._M_singular()
 166                               || __x._M_current == _Iterator(),
 167                               _M_message(__msg_init_copy_singular)
 168                               ._M_iterator(*this, "this")
 169                               ._M_iterator(__x, "other"));
 170       }
 171
 172 #ifdef __GXX_EXPERIMENTAL_CXX0X__
 173       /**
 174        * @brief Move construction.
 175        * @post __x is singular and unattached
 176        */
 177       _Safe_iterator(_Safe_iterator&& __x) : _M_current()
 178       {
 179         _GLIBCXX_DEBUG_VERIFY(!__x._M_singular()
 180                               || __x._M_current == _Iterator(),
 181                               _M_message(__msg_init_copy_singular)
 182                               ._M_iterator(*this, "this")
 183                               ._M_iterator(__x, "other"));
 184         std::swap(_M_current, __x._M_current);
 185         this->_M_attach(__x._M_sequence);
 186         __x._M_detach();
 187       }
 188 #endif
 189
 190       /**
 191        *  @brief Converting constructor from a mutable iterator to a
 192        *  constant iterator.
 193       */
 194       template<typename _MutableIterator>
 195         _Safe_iterator(
 196           const _Safe_iterator<_MutableIterator,
 197           typename __gnu_cxx::__enable_if<(std::__are_same<_MutableIterator,
 198                       typename _Sequence::iterator::iterator_type>::__value),
 199                    _Sequence>::__type>& __x)
 200         : _Safe_iterator_base(__x, _M_constant()), _M_current(__x.base())
 201         {
 202           // _GLIBCXX_RESOLVE_LIB_DEFECTS
 203           // DR 408. Is vector<reverse_iterator<char*> > forbidden?
 204           _GLIBCXX_DEBUG_VERIFY(!__x._M_singular()
 205                                 || __x.base() == _Iterator(),
 206                                 _M_message(__msg_init_const_singular)
 207                                 ._M_iterator(*this, "this")
 208                                 ._M_iterator(__x, "other"));
 209         }
 210
 211       /**
 212        * @brief Copy assignment.
 213        */
 214       _Safe_iterator&
 215       operator=(const _Safe_iterator& __x)
 216       {
 217         // _GLIBCXX_RESOLVE_LIB_DEFECTS
 218         // DR 408. Is vector<reverse_iterator<char*> > forbidden?
 219         _GLIBCXX_DEBUG_VERIFY(!__x._M_singular()
 220                               || __x._M_current == _Iterator(),
 221                               _M_message(__msg_copy_singular)
 222                               ._M_iterator(*this, "this")
 223                               ._M_iterator(__x, "other"));
 224         _M_current = __x._M_current;
 225         this->_M_attach(__x._M_sequence);
 226         return *this;
 227       }
 228
 229 #ifdef __GXX_EXPERIMENTAL_CXX0X__
 230       /**
 231        * @brief Move assignment.
 232        * @post __x is singular and unattached
 233        */
 234       _Safe_iterator&
 235       operator=(_Safe_iterator&& __x)
 236       {
 237         _GLIBCXX_DEBUG_VERIFY(!__x._M_singular()
 238                               || __x._M_current == _Iterator(),
 239                               _M_message(__msg_copy_singular)
 240                               ._M_iterator(*this, "this")
 241                               ._M_iterator(__x, "other"));
 242         _M_current = __x._M_current;
 243         _M_attach(__x._M_sequence);
 244         __x._M_detach();
 245         __x._M_current = _Iterator();
 246         return *this;
 247       }
 248 #endif
 249
 250       /**
 251        *  @brief Iterator dereference.
 252        *  @pre iterator is dereferenceable
 253        */
 254       reference
 255       operator*() const
 256       {
 257         _GLIBCXX_DEBUG_VERIFY(this->_M_dereferenceable(),
 258                               _M_message(__msg_bad_deref)
 259                               ._M_iterator(*this, "this"));
 260         return *_M_current;
 261       }
 262
 263       /**
 264        *  @brief Iterator dereference.
 265        *  @pre iterator is dereferenceable
 266        *  @todo Make this correct w.r.t. iterators that return proxies
 267        *  @todo Use addressof() instead of & operator
 268        */
 269       pointer
 270       operator->() const
 271       {
 272         _GLIBCXX_DEBUG_VERIFY(this->_M_dereferenceable(),
 273                               _M_message(__msg_bad_deref)
 274                               ._M_iterator(*this, "this"));
 275         return &*_M_current;
 276       }
 277
 278       // ------ Input iterator requirements ------
 279       /**
 280        *  @brief Iterator preincrement
 281        *  @pre iterator is incrementable
 282        */
 283       _Safe_iterator&
 284       operator++()
 285       {
 286         _GLIBCXX_DEBUG_VERIFY(this->_M_incrementable(),
 287                               _M_message(__msg_bad_inc)
 288                               ._M_iterator(*this, "this"));
 289         ++_M_current;
 290         return *this;
 291       }
 292
 293       /**
 294        *  @brief Iterator postincrement
 295        *  @pre iterator is incrementable
 296        */
 297       _Safe_iterator
 298       operator++(int)
 299       {
 300         _GLIBCXX_DEBUG_VERIFY(this->_M_incrementable(),
 301                               _M_message(__msg_bad_inc)
 302                               ._M_iterator(*this, "this"));
 303         _Safe_iterator __tmp(*this);
 304         ++_M_current;
 305         return __tmp;
 306       }
 307
 308       // ------ Bidirectional iterator requirements ------
 309       /**
 310        *  @brief Iterator predecrement
 311        *  @pre iterator is decrementable
 312        */
 313       _Safe_iterator&
 314       operator--()
 315       {
 316         _GLIBCXX_DEBUG_VERIFY(this->_M_decrementable(),
 317                               _M_message(__msg_bad_dec)
 318                               ._M_iterator(*this, "this"));
 319         --_M_current;
 320         return *this;
 321       }
 322
 323       /**
 324        *  @brief Iterator postdecrement
 325        *  @pre iterator is decrementable
 326        */
 327       _Safe_iterator
 328       operator--(int)
 329       {
 330         _GLIBCXX_DEBUG_VERIFY(this->_M_decrementable(),
 331                               _M_message(__msg_bad_dec)
 332                               ._M_iterator(*this, "this"));
 333         _Safe_iterator __tmp(*this);
 334         --_M_current;
 335         return __tmp;
 336       }
 337
 338       // ------ Random access iterator requirements ------
 339       reference
 340       operator[](const difference_type& __n) const
 341       {
 342         _GLIBCXX_DEBUG_VERIFY(this->_M_can_advance(__n)
 343                               && this->_M_can_advance(__n+1),
 344                               _M_message(__msg_iter_subscript_oob)
 345                               ._M_iterator(*this)._M_integer(__n));
 346
 347         return _M_current[__n];
 348       }
 349
 350       _Safe_iterator&
 351       operator+=(const difference_type& __n)
 352       {
 353         _GLIBCXX_DEBUG_VERIFY(this->_M_can_advance(__n),
 354                               _M_message(__msg_advance_oob)
 355                               ._M_iterator(*this)._M_integer(__n));
 356         _M_current += __n;
 357         return *this;
 358       }
 359
 360       _Safe_iterator
 361       operator+(const difference_type& __n) const
 362       {
 363         _Safe_iterator __tmp(*this);
 364         __tmp += __n;
 365         return __tmp;
 366       }
 367
 368       _Safe_iterator&
 369       operator-=(const difference_type& __n)
 370       {
 371         _GLIBCXX_DEBUG_VERIFY(this->_M_can_advance(-__n),
 372                               _M_message(__msg_retreat_oob)
 373                               ._M_iterator(*this)._M_integer(__n));
 374         _M_current += -__n;
 375         return *this;
 376       }
 377
 378       _Safe_iterator
 379       operator-(const difference_type& __n) const
 380       {
 381         _Safe_iterator __tmp(*this);
 382         __tmp -= __n;
 383         return __tmp;
 384       }
 385
 386       // ------ Utilities ------
 387       /**
 388        * @brief Return the underlying iterator
 389        */
 390       _Iterator
 391       base() const { return _M_current; }
 392
 393       /**
 394        * @brief Conversion to underlying non-debug iterator to allow
 395        * better interaction with non-debug containers.
 396        */
 397       operator _Iterator() const { return _M_current; }
 398
 399       /** Attach iterator to the given sequence. */
 400       void
 401       _M_attach(_Safe_sequence_base* __seq)
 402       {
 403         _Safe_iterator_base::_M_attach(__seq, _M_constant());
 404       }
 405
 406       /** Likewise, but not thread-safe. */
 407       void
 408       _M_attach_single(_Safe_sequence_base* __seq)
 409       {
 410         _Safe_iterator_base::_M_attach_single(__seq, _M_constant());
 411       }
 412
 413       /// Is the iterator dereferenceable?
 414       bool
 415       _M_dereferenceable() const
 416       { return !this->_M_singular() && !_M_is_end() && !_M_is_before_begin(); }
 417
 418       /// Is the iterator before a dereferenceable one?
 419       bool
 420       _M_before_dereferenceable() const
 421       {
 422         if (this->_M_incrementable())
 423         {
 424           _Iterator __base = base();
 425           return ++__base != _M_get_sequence()->_M_base().end();
 426         }
 427         return false;
 428       }
 429
 430       /// Is the iterator incrementable?
 431       bool
 432       _M_incrementable() const
 433       { return !this->_M_singular() && !_M_is_end(); }
 434
 435       // Is the iterator decrementable?
 436       bool
 437       _M_decrementable() const { return !_M_singular() && !_M_is_begin(); }
 438
 439       // Can we advance the iterator @p __n steps (@p __n may be negative)
 440       bool
 441       _M_can_advance(const difference_type& __n) const;
 442
 443       // Is the iterator range [*this, __rhs) valid?
 444       template<typename _Other>
 445         bool
 446         _M_valid_range(const _Safe_iterator<_Other, _Sequence>& __rhs) const;
 447
 448       // The sequence this iterator references.
 449       const _Sequence*
 450       _M_get_sequence() const
 451       { return static_cast<const _Sequence*>(_M_sequence); }
 452
 453       /// Is this iterator equal to the sequence's begin() iterator?
 454       bool _M_is_begin() const
 455       { return base() == _M_get_sequence()->_M_base().begin(); }
 456
 457       /// Is this iterator equal to the sequence's end() iterator?
 458       bool _M_is_end() const
 459       { return base() == _M_get_sequence()->_M_base().end(); }
 460
 461       /// Is this iterator equal to the sequence's before_begin() iterator if
 462       /// any?
 463       bool _M_is_before_begin() const
 464       {
 465         return _BeforeBeginHelper<_Sequence>::_M_Is(base(), _M_get_sequence());
 466       }
 467     };
 468
 469   template<typename _IteratorL, typename _IteratorR, typename _Sequence>
 470     inline bool
 471     operator==(const _Safe_iterator<_IteratorL, _Sequence>& __lhs,
 472                const _Safe_iterator<_IteratorR, _Sequence>& __rhs)
 473     {
 474       _GLIBCXX_DEBUG_VERIFY(! __lhs._M_singular() && ! __rhs._M_singular(),
 475                             _M_message(__msg_iter_compare_bad)
 476                             ._M_iterator(__lhs, "lhs")
 477                             ._M_iterator(__rhs, "rhs"));
 478       _GLIBCXX_DEBUG_VERIFY(__lhs._M_can_compare(__rhs),
 479                             _M_message(__msg_compare_different)
 480                             ._M_iterator(__lhs, "lhs")
 481                             ._M_iterator(__rhs, "rhs"));
 482       return __lhs.base() == __rhs.base();
 483     }
 484
 485   template<typename _Iterator, typename _Sequence>
 486     inline bool
 487     operator==(const _Safe_iterator<_Iterator, _Sequence>& __lhs,
 488                const _Safe_iterator<_Iterator, _Sequence>& __rhs)
 489     {
 490       _GLIBCXX_DEBUG_VERIFY(! __lhs._M_singular() && ! __rhs._M_singular(),
 491                             _M_message(__msg_iter_compare_bad)
 492                             ._M_iterator(__lhs, "lhs")
 493                             ._M_iterator(__rhs, "rhs"));
 494       _GLIBCXX_DEBUG_VERIFY(__lhs._M_can_compare(__rhs),
 495                             _M_message(__msg_compare_different)
 496                             ._M_iterator(__lhs, "lhs")
 497                             ._M_iterator(__rhs, "rhs"));
 498       return __lhs.base() == __rhs.base();
 499     }
 500
 501   template<typename _IteratorL, typename _IteratorR, typename _Sequence>
 502     inline bool
 503     operator!=(const _Safe_iterator<_IteratorL, _Sequence>& __lhs,
 504                const _Safe_iterator<_IteratorR, _Sequence>& __rhs)
 505     {
 506       _GLIBCXX_DEBUG_VERIFY(! __lhs._M_singular() && ! __rhs._M_singular(),
 507                             _M_message(__msg_iter_compare_bad)
 508                             ._M_iterator(__lhs, "lhs")
 509                             ._M_iterator(__rhs, "rhs"));
 510       _GLIBCXX_DEBUG_VERIFY(__lhs._M_can_compare(__rhs),
 511                             _M_message(__msg_compare_different)
 512                             ._M_iterator(__lhs, "lhs")
 513                             ._M_iterator(__rhs, "rhs"));
 514       return __lhs.base() != __rhs.base();
 515     }
 516
 517   template<typename _Iterator, typename _Sequence>
 518     inline bool
 519     operator!=(const _Safe_iterator<_Iterator, _Sequence>& __lhs,
 520                const _Safe_iterator<_Iterator, _Sequence>& __rhs)
 521     {
 522       _GLIBCXX_DEBUG_VERIFY(! __lhs._M_singular() && ! __rhs._M_singular(),
 523                             _M_message(__msg_iter_compare_bad)
 524                             ._M_iterator(__lhs, "lhs")
 525                             ._M_iterator(__rhs, "rhs"));
 526       _GLIBCXX_DEBUG_VERIFY(__lhs._M_can_compare(__rhs),
 527                             _M_message(__msg_compare_different)
 528                             ._M_iterator(__lhs, "lhs")
 529                             ._M_iterator(__rhs, "rhs"));
 530       return __lhs.base() != __rhs.base();
 531     }
 532
 533   template<typename _IteratorL, typename _IteratorR, typename _Sequence>
 534     inline bool
 535     operator<(const _Safe_iterator<_IteratorL, _Sequence>& __lhs,
 536               const _Safe_iterator<_IteratorR, _Sequence>& __rhs)
 537     {
 538       _GLIBCXX_DEBUG_VERIFY(! __lhs._M_singular() && ! __rhs._M_singular(),
 539                             _M_message(__msg_iter_order_bad)
 540                             ._M_iterator(__lhs, "lhs")
 541                             ._M_iterator(__rhs, "rhs"));
 542       _GLIBCXX_DEBUG_VERIFY(__lhs._M_can_compare(__rhs),
 543                             _M_message(__msg_order_different)
 544                             ._M_iterator(__lhs, "lhs")
 545                             ._M_iterator(__rhs, "rhs"));
 546       return __lhs.base() < __rhs.base();
 547     }
 548
 549   template<typename _Iterator, typename _Sequence>
 550     inline bool
 551     operator<(const _Safe_iterator<_Iterator, _Sequence>& __lhs,
 552               const _Safe_iterator<_Iterator, _Sequence>& __rhs)
 553     {
 554       _GLIBCXX_DEBUG_VERIFY(! __lhs._M_singular() && ! __rhs._M_singular(),
 555                             _M_message(__msg_iter_order_bad)
 556                             ._M_iterator(__lhs, "lhs")
 557                             ._M_iterator(__rhs, "rhs"));
 558       _GLIBCXX_DEBUG_VERIFY(__lhs._M_can_compare(__rhs),
 559                             _M_message(__msg_order_different)
 560                             ._M_iterator(__lhs, "lhs")
 561                             ._M_iterator(__rhs, "rhs"));
 562       return __lhs.base() < __rhs.base();
 563     }
 564
 565   template<typename _IteratorL, typename _IteratorR, typename _Sequence>
 566     inline bool
 567     operator<=(const _Safe_iterator<_IteratorL, _Sequence>& __lhs,
 568                const _Safe_iterator<_IteratorR, _Sequence>& __rhs)
 569     {
 570       _GLIBCXX_DEBUG_VERIFY(! __lhs._M_singular() && ! __rhs._M_singular(),
 571                             _M_message(__msg_iter_order_bad)
 572                             ._M_iterator(__lhs, "lhs")
 573                             ._M_iterator(__rhs, "rhs"));
 574       _GLIBCXX_DEBUG_VERIFY(__lhs._M_can_compare(__rhs),
 575                             _M_message(__msg_order_different)
 576                             ._M_iterator(__lhs, "lhs")
 577                             ._M_iterator(__rhs, "rhs"));
 578       return __lhs.base() <= __rhs.base();
 579     }
 580
 581   template<typename _Iterator, typename _Sequence>
 582     inline bool
 583     operator<=(const _Safe_iterator<_Iterator, _Sequence>& __lhs,
 584                const _Safe_iterator<_Iterator, _Sequence>& __rhs)
 585     {
 586       _GLIBCXX_DEBUG_VERIFY(! __lhs._M_singular() && ! __rhs._M_singular(),
 587                             _M_message(__msg_iter_order_bad)
 588                             ._M_iterator(__lhs, "lhs")
 589                             ._M_iterator(__rhs, "rhs"));
 590       _GLIBCXX_DEBUG_VERIFY(__lhs._M_can_compare(__rhs),
 591                             _M_message(__msg_order_different)
 592                             ._M_iterator(__lhs, "lhs")
 593                             ._M_iterator(__rhs, "rhs"));
 594       return __lhs.base() <= __rhs.base();
 595     }
 596
 597   template<typename _IteratorL, typename _IteratorR, typename _Sequence>
 598     inline bool
 599     operator>(const _Safe_iterator<_IteratorL, _Sequence>& __lhs,
 600               const _Safe_iterator<_IteratorR, _Sequence>& __rhs)
 601     {
 602       _GLIBCXX_DEBUG_VERIFY(! __lhs._M_singular() && ! __rhs._M_singular(),
 603                             _M_message(__msg_iter_order_bad)
 604                             ._M_iterator(__lhs, "lhs")
 605                             ._M_iterator(__rhs, "rhs"));
 606       _GLIBCXX_DEBUG_VERIFY(__lhs._M_can_compare(__rhs),
 607                             _M_message(__msg_order_different)
 608                             ._M_iterator(__lhs, "lhs")
 609                             ._M_iterator(__rhs, "rhs"));
 610       return __lhs.base() > __rhs.base();
 611     }
 612
 613   template<typename _Iterator, typename _Sequence>
 614     inline bool
 615     operator>(const _Safe_iterator<_Iterator, _Sequence>& __lhs,
 616               const _Safe_iterator<_Iterator, _Sequence>& __rhs)
 617     {
 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();
 627     }
 628
 629   template<typename _IteratorL, typename _IteratorR, typename _Sequence>
 630     inline bool
 631     operator>=(const _Safe_iterator<_IteratorL, _Sequence>& __lhs,
 632                const _Safe_iterator<_IteratorR, _Sequence>& __rhs)
 633     {
 634       _GLIBCXX_DEBUG_VERIFY(! __lhs._M_singular() && ! __rhs._M_singular(),
 635                             _M_message(__msg_iter_order_bad)
 636                             ._M_iterator(__lhs, "lhs")
 637                             ._M_iterator(__rhs, "rhs"));
 638       _GLIBCXX_DEBUG_VERIFY(__lhs._M_can_compare(__rhs),
 639                             _M_message(__msg_order_different)
 640                             ._M_iterator(__lhs, "lhs")
 641                             ._M_iterator(__rhs, "rhs"));
 642       return __lhs.base() >= __rhs.base();
 643     }
 644
 645   template<typename _Iterator, typename _Sequence>
 646     inline bool
 647     operator>=(const _Safe_iterator<_Iterator, _Sequence>& __lhs,
 648                const _Safe_iterator<_Iterator, _Sequence>& __rhs)
 649     {
 650       _GLIBCXX_DEBUG_VERIFY(! __lhs._M_singular() && ! __rhs._M_singular(),
 651                             _M_message(__msg_iter_order_bad)
 652                             ._M_iterator(__lhs, "lhs")
 653                             ._M_iterator(__rhs, "rhs"));
 654       _GLIBCXX_DEBUG_VERIFY(__lhs._M_can_compare(__rhs),
 655                             _M_message(__msg_order_different)
 656                             ._M_iterator(__lhs, "lhs")
 657                             ._M_iterator(__rhs, "rhs"));
 658       return __lhs.base() >= __rhs.base();
 659     }
 660
 661   // _GLIBCXX_RESOLVE_LIB_DEFECTS
 662   // According to the resolution of DR179 not only the various comparison
 663   // operators but also operator- must accept mixed iterator/const_iterator
 664   // parameters.
 665   template<typename _IteratorL, typename _IteratorR, typename _Sequence>
 666     inline typename _Safe_iterator<_IteratorL, _Sequence>::difference_type
 667     operator-(const _Safe_iterator<_IteratorL, _Sequence>& __lhs,
 668               const _Safe_iterator<_IteratorR, _Sequence>& __rhs)
 669     {
 670       _GLIBCXX_DEBUG_VERIFY(! __lhs._M_singular() && ! __rhs._M_singular(),
 671                             _M_message(__msg_distance_bad)
 672                             ._M_iterator(__lhs, "lhs")
 673                             ._M_iterator(__rhs, "rhs"));
 674       _GLIBCXX_DEBUG_VERIFY(__lhs._M_can_compare(__rhs),
 675                             _M_message(__msg_distance_different)
 676                             ._M_iterator(__lhs, "lhs")
 677                             ._M_iterator(__rhs, "rhs"));
 678       return __lhs.base() - __rhs.base();
 679     }
 680
 681    template<typename _Iterator, typename _Sequence>
 682      inline typename _Safe_iterator<_Iterator, _Sequence>::difference_type
 683      operator-(const _Safe_iterator<_Iterator, _Sequence>& __lhs,
 684                const _Safe_iterator<_Iterator, _Sequence>& __rhs)
 685      {
 686        _GLIBCXX_DEBUG_VERIFY(! __lhs._M_singular() && ! __rhs._M_singular(),
 687                              _M_message(__msg_distance_bad)
 688                              ._M_iterator(__lhs, "lhs")
 689                              ._M_iterator(__rhs, "rhs"));
 690        _GLIBCXX_DEBUG_VERIFY(__lhs._M_can_compare(__rhs),
 691                              _M_message(__msg_distance_different)
 692                              ._M_iterator(__lhs, "lhs")
 693                              ._M_iterator(__rhs, "rhs"));
 694        return __lhs.base() - __rhs.base();
 695      }
 696
 697   template<typename _Iterator, typename _Sequence>
 698     inline _Safe_iterator<_Iterator, _Sequence>
 699     operator+(typename _Safe_iterator<_Iterator,_Sequence>::difference_type __n,
 700               const _Safe_iterator<_Iterator, _Sequence>& __i)
 701     { return __i + __n; }
 702
 703   // Helper struct to detect random access safe iterators.
 704   template<typename _Iterator>
 705     struct __is_safe_random_iterator
 706     {
 707       enum { __value = 0 };
 708       typedef std::__false_type __type;
 709     };
 710
 711   template<typename _Iterator, typename _Sequence>
 712     struct __is_safe_random_iterator<_Safe_iterator<_Iterator, _Sequence> >
 713     : std::__are_same<std::random_access_iterator_tag,
 714                       typename std::iterator_traits<_Iterator>::
 715                       iterator_category>
 716     { };
 717
 718   template<typename _Iterator>
 719     struct _Siter_base
 720     : std::_Iter_base<_Iterator, __is_safe_random_iterator<_Iterator>::__value>
 721     { };
 722
 723   /** Helper function to extract base iterator of random access safe iterator
 724       in order to reduce performance impact of debug mode.  Limited to random
 725       access iterator because it is the only category for which it is possible
 726       to check for correct iterators order in the __valid_range function
 727       thanks to the < operator.
 728   */
 729   template<typename _Iterator>
 730     inline typename _Siter_base<_Iterator>::iterator_type
 731     __base(_Iterator __it)
 732     { return _Siter_base<_Iterator>::_S_base(__it); }
 733 } // namespace __gnu_debug
 734
 735 #include <debug/safe_iterator.tcc>
 736
 737 #endif