1 // Safe iterator implementation -*- C++ -*- 2 3 // Copyright (C) 2011-2020 Free Software Foundation, Inc. 4 // 5 // This file is part of the GNU ISO C++ Library. This library is free 6 // software; you can redistribute it and/or modify it under the 7 // terms of the GNU General Public License as published by the 8 // Free Software Foundation; either version 3, or (at your option) 9 // any later version. 10 11 // This library is distributed in the hope that it will be useful, 12 // but WITHOUT ANY WARRANTY; without even the implied warranty of 13 // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the 14 // GNU General Public License for more details. 15 16 // Under Section 7 of GPL version 3, you are granted additional 17 // permissions described in the GCC Runtime Library Exception, version 18 // 3.1, as published by the Free Software Foundation. 19 20 // You should have received a copy of the GNU General Public License and 21 // a copy of the GCC Runtime Library Exception along with this program; 22 // see the files COPYING3 and COPYING.RUNTIME respectively. If not, see 23 // <http://www.gnu.org/licenses/>. 24 25 /** @file debug/safe_local_iterator.h 26 * This file is a GNU debug extension to the Standard C++ Library. 27 */ 28 29 #ifndef _GLIBCXX_DEBUG_SAFE_LOCAL_ITERATOR_H 30 #define _GLIBCXX_DEBUG_SAFE_LOCAL_ITERATOR_H 1 31 32 #include <debug/safe_unordered_base.h> 33 34 #define _GLIBCXX_DEBUG_VERIFY_OPERANDS(_Lhs, _Rhs) \ 35 _GLIBCXX_DEBUG_VERIFY(!_Lhs._M_singular() && !_Rhs._M_singular(), \ 36 _M_message(__msg_iter_compare_bad) \ 37 ._M_iterator(_Lhs, "lhs") \ 38 ._M_iterator(_Rhs, "rhs")); \ 39 _GLIBCXX_DEBUG_VERIFY(_Lhs._M_can_compare(_Rhs), \ 40 _M_message(__msg_compare_different) \ 41 ._M_iterator(_Lhs, "lhs") \ 42 ._M_iterator(_Rhs, "rhs")); \ 43 _GLIBCXX_DEBUG_VERIFY(_Lhs._M_in_same_bucket(_Rhs), \ 44 _M_message(__msg_local_iter_compare_bad) \ 45 ._M_iterator(_Lhs, "lhs") \ 46 ._M_iterator(_Rhs, "rhs")) 47 48 namespace __gnu_debug 49 { 50 /** \brief Safe iterator wrapper. 51 * 52 * The class template %_Safe_local_iterator is a wrapper around an 53 * iterator that tracks the iterator's movement among sequences and 54 * checks that operations performed on the "safe" iterator are 55 * legal. In additional to the basic iterator operations (which are 56 * validated, and then passed to the underlying iterator), 57 * %_Safe_local_iterator has member functions for iterator invalidation, 58 * attaching/detaching the iterator from sequences, and querying 59 * the iterator's state. 60 */ 61 template<typename _Iterator, typename _Sequence> 62 class _Safe_local_iterator 63 : private _Iterator 64 , public _Safe_local_iterator_base 65 { 66 typedef _Iterator _Iter_base; 67 typedef _Safe_local_iterator_base _Safe_base; 68 69 typedef typename _Sequence::size_type size_type; 70 71 typedef std::iterator_traits<_Iterator> _Traits; 72 73 typedef std::__are_same< 74 typename _Sequence::_Base::const_local_iterator, 75 _Iterator> _IsConstant; 76 77 typedef typename __gnu_cxx::__conditional_type<_IsConstant::__value, 78 typename _Sequence::_Base::local_iterator, 79 typename _Sequence::_Base::const_local_iterator>::__type 80 _OtherIterator; 81 82 typedef _Safe_local_iterator _Self; 83 typedef _Safe_local_iterator<_OtherIterator, _Sequence> _OtherSelf; 84 85 struct _Attach_single 86 { }; 87 _Safe_local_iterator(_Iterator __i,_Safe_sequence_base * __cont,_Attach_single)88 _Safe_local_iterator(_Iterator __i, _Safe_sequence_base* __cont, 89 _Attach_single) noexcept 90 : _Iter_base(__i) 91 { _M_attach_single(__cont); } 92 93 public: 94 typedef _Iterator iterator_type; 95 typedef typename _Traits::iterator_category iterator_category; 96 typedef typename _Traits::value_type value_type; 97 typedef typename _Traits::difference_type difference_type; 98 typedef typename _Traits::reference reference; 99 typedef typename _Traits::pointer pointer; 100 101 /// @post the iterator is singular and unattached _Safe_local_iterator()102 _Safe_local_iterator() noexcept : _Iter_base() { } 103 104 /** 105 * @brief Safe iterator construction from an unsafe iterator and 106 * its sequence. 107 * 108 * @pre @p seq is not NULL 109 * @post this is not singular 110 */ _Safe_local_iterator(_Iterator __i,const _Safe_sequence_base * __cont)111 _Safe_local_iterator(_Iterator __i, const _Safe_sequence_base* __cont) 112 : _Iter_base(__i), _Safe_base(__cont, _S_constant()) 113 { 114 _GLIBCXX_DEBUG_VERIFY(!this->_M_singular(), 115 _M_message(__msg_init_singular) 116 ._M_iterator(*this, "this")); 117 } 118 119 /** 120 * @brief Copy construction. 121 */ _Safe_local_iterator(const _Safe_local_iterator & __x)122 _Safe_local_iterator(const _Safe_local_iterator& __x) noexcept 123 : _Iter_base(__x.base()) 124 { 125 // _GLIBCXX_RESOLVE_LIB_DEFECTS 126 // DR 408. Is vector<reverse_iterator<char*> > forbidden? 127 _GLIBCXX_DEBUG_VERIFY(!__x._M_singular() 128 || __x.base() == _Iterator(), 129 _M_message(__msg_init_copy_singular) 130 ._M_iterator(*this, "this") 131 ._M_iterator(__x, "other")); 132 _M_attach(__x._M_sequence); 133 } 134 135 /** 136 * @brief Move construction. 137 * @post __x is singular and unattached 138 */ _Safe_local_iterator(_Safe_local_iterator && __x)139 _Safe_local_iterator(_Safe_local_iterator&& __x) noexcept 140 : _Iter_base() 141 { 142 _GLIBCXX_DEBUG_VERIFY(!__x._M_singular() 143 || __x.base() == _Iterator(), 144 _M_message(__msg_init_copy_singular) 145 ._M_iterator(*this, "this") 146 ._M_iterator(__x, "other")); 147 auto __cont = __x._M_sequence; 148 __x._M_detach(); 149 std::swap(base(), __x.base()); 150 _M_attach(__cont); 151 } 152 153 /** 154 * @brief Converting constructor from a mutable iterator to a 155 * constant iterator. 156 */ 157 template<typename _MutableIterator> _Safe_local_iterator(const _Safe_local_iterator<_MutableIterator,typename __gnu_cxx::__enable_if<_IsConstant::__value && std::__are_same<_MutableIterator,_OtherIterator>::__value,_Sequence>::__type> & __x)158 _Safe_local_iterator( 159 const _Safe_local_iterator<_MutableIterator, 160 typename __gnu_cxx::__enable_if<_IsConstant::__value && 161 std::__are_same<_MutableIterator, _OtherIterator>::__value, 162 _Sequence>::__type>& __x) noexcept 163 : _Iter_base(__x.base()) 164 { 165 // _GLIBCXX_RESOLVE_LIB_DEFECTS 166 // DR 408. Is vector<reverse_iterator<char*> > forbidden? 167 _GLIBCXX_DEBUG_VERIFY(!__x._M_singular() 168 || __x.base() == _MutableIterator(), 169 _M_message(__msg_init_const_singular) 170 ._M_iterator(*this, "this") 171 ._M_iterator(__x, "other")); 172 _M_attach(__x._M_sequence); 173 } 174 175 /** 176 * @brief Copy assignment. 177 */ 178 _Safe_local_iterator& 179 operator=(const _Safe_local_iterator& __x) 180 { 181 // _GLIBCXX_RESOLVE_LIB_DEFECTS 182 // DR 408. Is vector<reverse_iterator<char*> > forbidden? 183 _GLIBCXX_DEBUG_VERIFY(!__x._M_singular() 184 || __x.base() == _Iterator(), 185 _M_message(__msg_copy_singular) 186 ._M_iterator(*this, "this") 187 ._M_iterator(__x, "other")); 188 189 if (this->_M_sequence && this->_M_sequence == __x._M_sequence) 190 { 191 __gnu_cxx::__scoped_lock __l(this->_M_get_mutex()); 192 base() = __x.base(); 193 _M_version = __x._M_sequence->_M_version; 194 } 195 else 196 { 197 _M_detach(); 198 base() = __x.base(); 199 _M_attach(__x._M_sequence); 200 } 201 202 return *this; 203 } 204 205 /** 206 * @brief Move assignment. 207 * @post __x is singular and unattached 208 */ 209 _Safe_local_iterator& 210 operator=(_Safe_local_iterator&& __x) noexcept 211 { 212 _GLIBCXX_DEBUG_VERIFY(this != &__x, 213 _M_message(__msg_self_move_assign) 214 ._M_iterator(*this, "this")); 215 _GLIBCXX_DEBUG_VERIFY(!__x._M_singular() 216 || __x.base() == _Iterator(), 217 _M_message(__msg_copy_singular) 218 ._M_iterator(*this, "this") 219 ._M_iterator(__x, "other")); 220 221 if (this->_M_sequence && this->_M_sequence == __x._M_sequence) 222 { 223 __gnu_cxx::__scoped_lock __l(this->_M_get_mutex()); 224 base() = __x.base(); 225 _M_version = __x._M_sequence->_M_version; 226 } 227 else 228 { 229 _M_detach(); 230 base() = __x.base(); 231 _M_attach(__x._M_sequence); 232 } 233 234 __x._M_detach(); 235 __x.base() = _Iterator(); 236 return *this; 237 } 238 239 /** 240 * @brief Iterator dereference. 241 * @pre iterator is dereferenceable 242 */ 243 reference 244 operator*() const 245 { 246 _GLIBCXX_DEBUG_VERIFY(this->_M_dereferenceable(), 247 _M_message(__msg_bad_deref) 248 ._M_iterator(*this, "this")); 249 return *base(); 250 } 251 252 /** 253 * @brief Iterator dereference. 254 * @pre iterator is dereferenceable 255 */ 256 pointer 257 operator->() const 258 { 259 _GLIBCXX_DEBUG_VERIFY(this->_M_dereferenceable(), 260 _M_message(__msg_bad_deref) 261 ._M_iterator(*this, "this")); 262 return base().operator->(); 263 } 264 265 // ------ Input iterator requirements ------ 266 /** 267 * @brief Iterator preincrement 268 * @pre iterator is incrementable 269 */ 270 _Safe_local_iterator& 271 operator++() 272 { 273 _GLIBCXX_DEBUG_VERIFY(this->_M_incrementable(), 274 _M_message(__msg_bad_inc) 275 ._M_iterator(*this, "this")); 276 __gnu_cxx::__scoped_lock __l(this->_M_get_mutex()); 277 ++base(); 278 return *this; 279 } 280 281 /** 282 * @brief Iterator postincrement 283 * @pre iterator is incrementable 284 */ 285 _Safe_local_iterator 286 operator++(int) 287 { 288 _GLIBCXX_DEBUG_VERIFY(this->_M_incrementable(), 289 _M_message(__msg_bad_inc) 290 ._M_iterator(*this, "this")); 291 __gnu_cxx::__scoped_lock __l(this->_M_get_mutex()); 292 return _Safe_local_iterator(base()++, this->_M_sequence, 293 _Attach_single()); 294 } 295 296 // ------ Utilities ------ 297 298 /// Determine if this is a constant iterator. 299 static constexpr bool _S_constant()300 _S_constant() 301 { return _IsConstant::__value; } 302 303 /** 304 * @brief Return the underlying iterator 305 */ 306 _Iterator& base()307 base() noexcept { return *this; } 308 309 const _Iterator& base()310 base() const noexcept { return *this; } 311 312 /** 313 * @brief Return the bucket 314 */ 315 size_type bucket()316 bucket() const { return base()._M_get_bucket(); } 317 318 /** 319 * @brief Conversion to underlying non-debug iterator to allow 320 * better interaction with non-debug containers. 321 */ _Iterator()322 operator _Iterator() const { return *this; } 323 324 /** Attach iterator to the given sequence. */ 325 void _M_attach(_Safe_sequence_base * __seq)326 _M_attach(_Safe_sequence_base* __seq) 327 { _Safe_base::_M_attach(__seq, _S_constant()); } 328 329 /** Likewise, but not thread-safe. */ 330 void _M_attach_single(_Safe_sequence_base * __seq)331 _M_attach_single(_Safe_sequence_base* __seq) 332 { _Safe_base::_M_attach_single(__seq, _S_constant()); } 333 334 /// Is the iterator dereferenceable? 335 bool _M_dereferenceable()336 _M_dereferenceable() const 337 { return !this->_M_singular() && !_M_is_end(); } 338 339 /// Is the iterator incrementable? 340 bool _M_incrementable()341 _M_incrementable() const 342 { return !this->_M_singular() && !_M_is_end(); } 343 344 // Is the iterator range [*this, __rhs) valid? 345 bool 346 _M_valid_range(const _Safe_local_iterator& __rhs, 347 std::pair<difference_type, 348 _Distance_precision>& __dist_info) const; 349 350 // Get distance to __rhs. 351 typename _Distance_traits<_Iterator>::__type 352 _M_get_distance_to(const _Safe_local_iterator& __rhs) const; 353 354 // The sequence this iterator references. 355 typename __gnu_cxx::__conditional_type< 356 _IsConstant::__value, const _Sequence*, _Sequence*>::__type _M_get_sequence()357 _M_get_sequence() const 358 { return static_cast<_Sequence*>(_M_sequence); } 359 360 /// Is this iterator equal to the sequence's begin(bucket) iterator? _M_is_begin()361 bool _M_is_begin() const 362 { return base() == _M_get_sequence()->_M_base().begin(bucket()); } 363 364 /// Is this iterator equal to the sequence's end(bucket) iterator? _M_is_end()365 bool _M_is_end() const 366 { return base() == _M_get_sequence()->_M_base().end(bucket()); } 367 368 /// Is this iterator part of the same bucket as the other one? 369 template<typename _Other> 370 bool _M_in_same_bucket(const _Safe_local_iterator<_Other,_Sequence> & __other)371 _M_in_same_bucket(const _Safe_local_iterator<_Other, 372 _Sequence>& __other) const 373 { return bucket() == __other.bucket(); } 374 375 friend inline bool 376 operator==(const _Self& __lhs, const _OtherSelf& __rhs) noexcept 377 { 378 _GLIBCXX_DEBUG_VERIFY_OPERANDS(__lhs, __rhs); 379 return __lhs.base() == __rhs.base(); 380 } 381 382 friend inline bool 383 operator==(const _Self& __lhs, const _Self& __rhs) noexcept 384 { 385 _GLIBCXX_DEBUG_VERIFY_OPERANDS(__lhs, __rhs); 386 return __lhs.base() == __rhs.base(); 387 } 388 389 friend inline bool 390 operator!=(const _Self& __lhs, const _OtherSelf& __rhs) noexcept 391 { 392 _GLIBCXX_DEBUG_VERIFY_OPERANDS(__lhs, __rhs); 393 return __lhs.base() != __rhs.base(); 394 } 395 396 friend inline bool 397 operator!=(const _Self& __lhs, const _Self& __rhs) noexcept 398 { 399 _GLIBCXX_DEBUG_VERIFY_OPERANDS(__lhs, __rhs); 400 return __lhs.base() != __rhs.base(); 401 } 402 }; 403 404 /** Safe local iterators know how to check if they form a valid range. */ 405 template<typename _Iterator, typename _Sequence> 406 inline bool __valid_range(const _Safe_local_iterator<_Iterator,_Sequence> & __first,const _Safe_local_iterator<_Iterator,_Sequence> & __last,typename _Distance_traits<_Iterator>::__type & __dist_info)407 __valid_range(const _Safe_local_iterator<_Iterator, _Sequence>& __first, 408 const _Safe_local_iterator<_Iterator, _Sequence>& __last, 409 typename _Distance_traits<_Iterator>::__type& __dist_info) 410 { return __first._M_valid_range(__last, __dist_info); } 411 412 template<typename _Iterator, typename _Sequence> 413 inline bool __valid_range(const _Safe_local_iterator<_Iterator,_Sequence> & __first,const _Safe_local_iterator<_Iterator,_Sequence> & __last)414 __valid_range(const _Safe_local_iterator<_Iterator, _Sequence>& __first, 415 const _Safe_local_iterator<_Iterator, _Sequence>& __last) 416 { 417 typename _Distance_traits<_Iterator>::__type __dist_info; 418 return __first._M_valid_range(__last, __dist_info); 419 } 420 421 #if __cplusplus < 201103L 422 template<typename _Iterator, typename _Sequence> 423 struct _Unsafe_type<_Safe_local_iterator<_Iterator, _Sequence> > 424 { typedef _Iterator _Type; }; 425 #endif 426 427 template<typename _Iterator, typename _Sequence> 428 inline _Iterator 429 __unsafe(const _Safe_local_iterator<_Iterator, _Sequence>& __it) 430 { return __it.base(); } 431 432 } // namespace __gnu_debug 433 434 #undef _GLIBCXX_DEBUG_VERIFY_OPERANDS 435 436 #include <debug/safe_local_iterator.tcc> 437 438 #endif 439