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