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