libstdc++
|
00001 // Safe iterator implementation -*- C++ -*- 00002 00003 // Copyright (C) 2011-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_local_iterator.h 00026 * This file is a GNU debug extension to the Standard C++ Library. 00027 */ 00028 00029 #ifndef _GLIBCXX_DEBUG_SAFE_LOCAL_ITERATOR_H 00030 #define _GLIBCXX_DEBUG_SAFE_LOCAL_ITERATOR_H 1 00031 00032 #include <debug/safe_unordered_base.h> 00033 00034 #define _GLIBCXX_DEBUG_VERIFY_OPERANDS(_Lhs, _Rhs) \ 00035 _GLIBCXX_DEBUG_VERIFY(!_Lhs._M_singular() && !_Rhs._M_singular(), \ 00036 _M_message(__msg_iter_compare_bad) \ 00037 ._M_iterator(_Lhs, "lhs") \ 00038 ._M_iterator(_Rhs, "rhs")); \ 00039 _GLIBCXX_DEBUG_VERIFY(_Lhs._M_can_compare(_Rhs), \ 00040 _M_message(__msg_compare_different) \ 00041 ._M_iterator(_Lhs, "lhs") \ 00042 ._M_iterator(_Rhs, "rhs")); \ 00043 _GLIBCXX_DEBUG_VERIFY(_Lhs._M_in_same_bucket(_Rhs), \ 00044 _M_message(__msg_local_iter_compare_bad) \ 00045 ._M_iterator(_Lhs, "lhs") \ 00046 ._M_iterator(_Rhs, "rhs")) 00047 00048 namespace __gnu_debug 00049 { 00050 /** \brief Safe iterator wrapper. 00051 * 00052 * The class template %_Safe_local_iterator is a wrapper around an 00053 * iterator that tracks the iterator's movement among sequences and 00054 * checks that operations performed on the "safe" iterator are 00055 * legal. In additional to the basic iterator operations (which are 00056 * validated, and then passed to the underlying iterator), 00057 * %_Safe_local_iterator has member functions for iterator invalidation, 00058 * attaching/detaching the iterator from sequences, and querying 00059 * the iterator's state. 00060 */ 00061 template<typename _Iterator, typename _Sequence> 00062 class _Safe_local_iterator 00063 : private _Iterator 00064 , public _Safe_local_iterator_base 00065 { 00066 typedef _Iterator _Iter_base; 00067 typedef _Safe_local_iterator_base _Safe_base; 00068 00069 typedef typename _Sequence::size_type size_type; 00070 00071 typedef std::iterator_traits<_Iterator> _Traits; 00072 00073 typedef std::__are_same< 00074 typename _Sequence::_Base::const_local_iterator, 00075 _Iterator> _IsConstant; 00076 00077 typedef typename __gnu_cxx::__conditional_type<_IsConstant::__value, 00078 typename _Sequence::_Base::local_iterator, 00079 typename _Sequence::_Base::const_local_iterator>::__type 00080 _OtherIterator; 00081 00082 typedef _Safe_local_iterator _Self; 00083 typedef _Safe_local_iterator<_OtherIterator, _Sequence> _OtherSelf; 00084 00085 struct _Attach_single 00086 { }; 00087 00088 _Safe_local_iterator(_Iterator __i, _Safe_sequence_base* __cont, 00089 _Attach_single) noexcept 00090 : _Iter_base(__i) 00091 { _M_attach_single(__cont); } 00092 00093 public: 00094 typedef _Iterator iterator_type; 00095 typedef typename _Traits::iterator_category iterator_category; 00096 typedef typename _Traits::value_type value_type; 00097 typedef typename _Traits::difference_type difference_type; 00098 typedef typename _Traits::reference reference; 00099 typedef typename _Traits::pointer pointer; 00100 00101 /// @post the iterator is singular and unattached 00102 _Safe_local_iterator() noexcept : _Iter_base() { } 00103 00104 /** 00105 * @brief Safe iterator construction from an unsafe iterator and 00106 * its sequence. 00107 * 00108 * @pre @p seq is not NULL 00109 * @post this is not singular 00110 */ 00111 _Safe_local_iterator(_Iterator __i, const _Safe_sequence_base* __cont) 00112 : _Iter_base(__i), _Safe_base(__cont, _S_constant()) 00113 { 00114 _GLIBCXX_DEBUG_VERIFY(!this->_M_singular(), 00115 _M_message(__msg_init_singular) 00116 ._M_iterator(*this, "this")); 00117 } 00118 00119 /** 00120 * @brief Copy construction. 00121 */ 00122 _Safe_local_iterator(const _Safe_local_iterator& __x) noexcept 00123 : _Iter_base(__x.base()) 00124 { 00125 // _GLIBCXX_RESOLVE_LIB_DEFECTS 00126 // DR 408. Is vector<reverse_iterator<char*> > forbidden? 00127 _GLIBCXX_DEBUG_VERIFY(!__x._M_singular() 00128 || __x.base() == _Iterator(), 00129 _M_message(__msg_init_copy_singular) 00130 ._M_iterator(*this, "this") 00131 ._M_iterator(__x, "other")); 00132 _M_attach(__x._M_sequence); 00133 } 00134 00135 /** 00136 * @brief Move construction. 00137 * @post __x is singular and unattached 00138 */ 00139 _Safe_local_iterator(_Safe_local_iterator&& __x) noexcept 00140 : _Iter_base() 00141 { 00142 _GLIBCXX_DEBUG_VERIFY(!__x._M_singular() 00143 || __x.base() == _Iterator(), 00144 _M_message(__msg_init_copy_singular) 00145 ._M_iterator(*this, "this") 00146 ._M_iterator(__x, "other")); 00147 auto __cont = __x._M_sequence; 00148 __x._M_detach(); 00149 std::swap(base(), __x.base()); 00150 _M_attach(__cont); 00151 } 00152 00153 /** 00154 * @brief Converting constructor from a mutable iterator to a 00155 * constant iterator. 00156 */ 00157 template<typename _MutableIterator> 00158 _Safe_local_iterator( 00159 const _Safe_local_iterator<_MutableIterator, 00160 typename __gnu_cxx::__enable_if<_IsConstant::__value && 00161 std::__are_same<_MutableIterator, _OtherIterator>::__value, 00162 _Sequence>::__type>& __x) noexcept 00163 : _Iter_base(__x.base()) 00164 { 00165 // _GLIBCXX_RESOLVE_LIB_DEFECTS 00166 // DR 408. Is vector<reverse_iterator<char*> > forbidden? 00167 _GLIBCXX_DEBUG_VERIFY(!__x._M_singular() 00168 || __x.base() == _MutableIterator(), 00169 _M_message(__msg_init_const_singular) 00170 ._M_iterator(*this, "this") 00171 ._M_iterator(__x, "other")); 00172 _M_attach(__x._M_sequence); 00173 } 00174 00175 /** 00176 * @brief Copy assignment. 00177 */ 00178 _Safe_local_iterator& 00179 operator=(const _Safe_local_iterator& __x) 00180 { 00181 // _GLIBCXX_RESOLVE_LIB_DEFECTS 00182 // DR 408. Is vector<reverse_iterator<char*> > forbidden? 00183 _GLIBCXX_DEBUG_VERIFY(!__x._M_singular() 00184 || __x.base() == _Iterator(), 00185 _M_message(__msg_copy_singular) 00186 ._M_iterator(*this, "this") 00187 ._M_iterator(__x, "other")); 00188 00189 if (this->_M_sequence && this->_M_sequence == __x._M_sequence) 00190 { 00191 __gnu_cxx::__scoped_lock __l(this->_M_get_mutex()); 00192 base() = __x.base(); 00193 _M_version = __x._M_sequence->_M_version; 00194 } 00195 else 00196 { 00197 _M_detach(); 00198 base() = __x.base(); 00199 _M_attach(__x._M_sequence); 00200 } 00201 00202 return *this; 00203 } 00204 00205 /** 00206 * @brief Move assignment. 00207 * @post __x is singular and unattached 00208 */ 00209 _Safe_local_iterator& 00210 operator=(_Safe_local_iterator&& __x) noexcept 00211 { 00212 _GLIBCXX_DEBUG_VERIFY(this != &__x, 00213 _M_message(__msg_self_move_assign) 00214 ._M_iterator(*this, "this")); 00215 _GLIBCXX_DEBUG_VERIFY(!__x._M_singular() 00216 || __x.base() == _Iterator(), 00217 _M_message(__msg_copy_singular) 00218 ._M_iterator(*this, "this") 00219 ._M_iterator(__x, "other")); 00220 00221 if (this->_M_sequence && this->_M_sequence == __x._M_sequence) 00222 { 00223 __gnu_cxx::__scoped_lock __l(this->_M_get_mutex()); 00224 base() = __x.base(); 00225 _M_version = __x._M_sequence->_M_version; 00226 } 00227 else 00228 { 00229 _M_detach(); 00230 base() = __x.base(); 00231 _M_attach(__x._M_sequence); 00232 } 00233 00234 __x._M_detach(); 00235 __x.base() = _Iterator(); 00236 return *this; 00237 } 00238 00239 /** 00240 * @brief Iterator dereference. 00241 * @pre iterator is dereferenceable 00242 */ 00243 reference 00244 operator*() const 00245 { 00246 _GLIBCXX_DEBUG_VERIFY(this->_M_dereferenceable(), 00247 _M_message(__msg_bad_deref) 00248 ._M_iterator(*this, "this")); 00249 return *base(); 00250 } 00251 00252 /** 00253 * @brief Iterator dereference. 00254 * @pre iterator is dereferenceable 00255 */ 00256 pointer 00257 operator->() const 00258 { 00259 _GLIBCXX_DEBUG_VERIFY(this->_M_dereferenceable(), 00260 _M_message(__msg_bad_deref) 00261 ._M_iterator(*this, "this")); 00262 return base().operator->(); 00263 } 00264 00265 // ------ Input iterator requirements ------ 00266 /** 00267 * @brief Iterator preincrement 00268 * @pre iterator is incrementable 00269 */ 00270 _Safe_local_iterator& 00271 operator++() 00272 { 00273 _GLIBCXX_DEBUG_VERIFY(this->_M_incrementable(), 00274 _M_message(__msg_bad_inc) 00275 ._M_iterator(*this, "this")); 00276 __gnu_cxx::__scoped_lock __l(this->_M_get_mutex()); 00277 ++base(); 00278 return *this; 00279 } 00280 00281 /** 00282 * @brief Iterator postincrement 00283 * @pre iterator is incrementable 00284 */ 00285 _Safe_local_iterator 00286 operator++(int) 00287 { 00288 _GLIBCXX_DEBUG_VERIFY(this->_M_incrementable(), 00289 _M_message(__msg_bad_inc) 00290 ._M_iterator(*this, "this")); 00291 __gnu_cxx::__scoped_lock __l(this->_M_get_mutex()); 00292 return _Safe_local_iterator(base()++, this->_M_sequence, 00293 _Attach_single()); 00294 } 00295 00296 // ------ Utilities ------ 00297 00298 /// Determine if this is a constant iterator. 00299 static constexpr bool 00300 _S_constant() 00301 { return _IsConstant::__value; } 00302 00303 /** 00304 * @brief Return the underlying iterator 00305 */ 00306 _Iterator& 00307 base() noexcept { return *this; } 00308 00309 const _Iterator& 00310 base() const noexcept { return *this; } 00311 00312 /** 00313 * @brief Return the bucket 00314 */ 00315 size_type 00316 bucket() const { return base()._M_get_bucket(); } 00317 00318 /** 00319 * @brief Conversion to underlying non-debug iterator to allow 00320 * better interaction with non-debug containers. 00321 */ 00322 operator _Iterator() const { return *this; } 00323 00324 /** Attach iterator to the given sequence. */ 00325 void 00326 _M_attach(_Safe_sequence_base* __seq) 00327 { _Safe_base::_M_attach(__seq, _S_constant()); } 00328 00329 /** Likewise, but not thread-safe. */ 00330 void 00331 _M_attach_single(_Safe_sequence_base* __seq) 00332 { _Safe_base::_M_attach_single(__seq, _S_constant()); } 00333 00334 /// Is the iterator dereferenceable? 00335 bool 00336 _M_dereferenceable() const 00337 { return !this->_M_singular() && !_M_is_end(); } 00338 00339 /// Is the iterator incrementable? 00340 bool 00341 _M_incrementable() const 00342 { return !this->_M_singular() && !_M_is_end(); } 00343 00344 // Is the iterator range [*this, __rhs) valid? 00345 bool 00346 _M_valid_range(const _Safe_local_iterator& __rhs, 00347 std::pair<difference_type, 00348 _Distance_precision>& __dist_info) const; 00349 00350 // Get distance to __rhs. 00351 typename _Distance_traits<_Iterator>::__type 00352 _M_get_distance_to(const _Safe_local_iterator& __rhs) const; 00353 00354 // The sequence this iterator references. 00355 typename __gnu_cxx::__conditional_type< 00356 _IsConstant::__value, const _Sequence*, _Sequence*>::__type 00357 _M_get_sequence() const 00358 { return static_cast<_Sequence*>(_M_sequence); } 00359 00360 /// Is this iterator equal to the sequence's begin(bucket) iterator? 00361 bool _M_is_begin() const 00362 { return base() == _M_get_sequence()->_M_base().begin(bucket()); } 00363 00364 /// Is this iterator equal to the sequence's end(bucket) iterator? 00365 bool _M_is_end() const 00366 { return base() == _M_get_sequence()->_M_base().end(bucket()); } 00367 00368 /// Is this iterator part of the same bucket as the other one? 00369 template<typename _Other> 00370 bool 00371 _M_in_same_bucket(const _Safe_local_iterator<_Other, 00372 _Sequence>& __other) const 00373 { return bucket() == __other.bucket(); } 00374 00375 friend inline bool 00376 operator==(const _Self& __lhs, const _OtherSelf& __rhs) noexcept 00377 { 00378 _GLIBCXX_DEBUG_VERIFY_OPERANDS(__lhs, __rhs); 00379 return __lhs.base() == __rhs.base(); 00380 } 00381 00382 friend inline bool 00383 operator==(const _Self& __lhs, const _Self& __rhs) noexcept 00384 { 00385 _GLIBCXX_DEBUG_VERIFY_OPERANDS(__lhs, __rhs); 00386 return __lhs.base() == __rhs.base(); 00387 } 00388 00389 friend inline bool 00390 operator!=(const _Self& __lhs, const _OtherSelf& __rhs) noexcept 00391 { 00392 _GLIBCXX_DEBUG_VERIFY_OPERANDS(__lhs, __rhs); 00393 return __lhs.base() != __rhs.base(); 00394 } 00395 00396 friend inline bool 00397 operator!=(const _Self& __lhs, const _Self& __rhs) noexcept 00398 { 00399 _GLIBCXX_DEBUG_VERIFY_OPERANDS(__lhs, __rhs); 00400 return __lhs.base() != __rhs.base(); 00401 } 00402 }; 00403 00404 /** Safe local iterators know how to check if they form a valid range. */ 00405 template<typename _Iterator, typename _Sequence> 00406 inline bool 00407 __valid_range(const _Safe_local_iterator<_Iterator, _Sequence>& __first, 00408 const _Safe_local_iterator<_Iterator, _Sequence>& __last, 00409 typename _Distance_traits<_Iterator>::__type& __dist_info) 00410 { return __first._M_valid_range(__last, __dist_info); } 00411 00412 template<typename _Iterator, typename _Sequence> 00413 inline bool 00414 __valid_range(const _Safe_local_iterator<_Iterator, _Sequence>& __first, 00415 const _Safe_local_iterator<_Iterator, _Sequence>& __last) 00416 { 00417 typename _Distance_traits<_Iterator>::__type __dist_info; 00418 return __first._M_valid_range(__last, __dist_info); 00419 } 00420 00421 #if __cplusplus < 201103L 00422 template<typename _Iterator, typename _Sequence> 00423 struct _Unsafe_type<_Safe_local_iterator<_Iterator, _Sequence> > 00424 { typedef _Iterator _Type; }; 00425 #endif 00426 00427 template<typename _Iterator, typename _Sequence> 00428 inline _Iterator 00429 __unsafe(const _Safe_local_iterator<_Iterator, _Sequence>& __it) 00430 { return __it.base(); } 00431 00432 } // namespace __gnu_debug 00433 00434 #undef _GLIBCXX_DEBUG_VERIFY_OPERANDS 00435 00436 #include <debug/safe_local_iterator.tcc> 00437 00438 #endif