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