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