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