libstdc++
|
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