1 // Safe iterator implementation -*- C++ -*- 2 3 // Copyright (C) 2003-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_iterator.h 26 * This file is a GNU debug extension to the Standard C++ Library. 27 */ 28 29 #ifndef _GLIBCXX_DEBUG_SAFE_ITERATOR_H 30 #define _GLIBCXX_DEBUG_SAFE_ITERATOR_H 1 31 32 #include <debug/assertions.h> 33 #include <debug/macros.h> 34 #include <debug/functions.h> 35 #include <debug/safe_base.h> 36 #include <bits/stl_pair.h> 37 #include <ext/type_traits.h> 38 #if __cplusplus > 201703L 39 # include <compare> 40 #endif 41 42 #define _GLIBCXX_DEBUG_VERIFY_OPERANDS(_Lhs, _Rhs, _BadMsgId, _DiffMsgId) \ 43 _GLIBCXX_DEBUG_VERIFY(!_Lhs._M_singular() && !_Rhs._M_singular(), \ 44 _M_message(_BadMsgId) \ 45 ._M_iterator(_Lhs, #_Lhs) \ 46 ._M_iterator(_Rhs, #_Rhs)); \ 47 _GLIBCXX_DEBUG_VERIFY(_Lhs._M_can_compare(_Rhs), \ 48 _M_message(_DiffMsgId) \ 49 ._M_iterator(_Lhs, #_Lhs) \ 50 ._M_iterator(_Rhs, #_Rhs)) 51 52 #define _GLIBCXX_DEBUG_VERIFY_EQ_OPERANDS(_Lhs, _Rhs) \ 53 _GLIBCXX_DEBUG_VERIFY_OPERANDS(_Lhs, _Rhs, __msg_iter_compare_bad, \ 54 __msg_compare_different) 55 56 #define _GLIBCXX_DEBUG_VERIFY_REL_OPERANDS(_Lhs, _Rhs) \ 57 _GLIBCXX_DEBUG_VERIFY_OPERANDS(_Lhs, _Rhs, __msg_iter_order_bad, \ 58 __msg_order_different) 59 60 #define _GLIBCXX_DEBUG_VERIFY_DIST_OPERANDS(_Lhs, _Rhs) \ 61 _GLIBCXX_DEBUG_VERIFY_OPERANDS(_Lhs, _Rhs, __msg_distance_bad, \ 62 __msg_distance_different) 63 64 namespace __gnu_debug 65 { 66 /** Helper struct to deal with sequence offering a before_begin 67 * iterator. 68 **/ 69 template<typename _Sequence> 70 struct _BeforeBeginHelper 71 { 72 template<typename _Iterator, typename _Category> 73 static bool _S_Is_BeforeBeginHelper74 _S_Is(const _Safe_iterator<_Iterator, _Sequence, _Category>&) 75 { return false; } 76 77 template<typename _Iterator, typename _Category> 78 static bool _S_Is_Beginnest_BeforeBeginHelper79 _S_Is_Beginnest(const _Safe_iterator<_Iterator, _Sequence, _Category>& __it) 80 { return __it.base() == __it._M_get_sequence()->_M_base().begin(); } 81 }; 82 83 /** Sequence traits giving the size of a container if possible. */ 84 template<typename _Sequence> 85 struct _Sequence_traits 86 { 87 typedef _Distance_traits<typename _Sequence::iterator> _DistTraits; 88 89 static typename _DistTraits::__type _S_size_Sequence_traits90 _S_size(const _Sequence& __seq) 91 { return std::make_pair(__seq.size(), __dp_exact); } 92 }; 93 94 /** \brief Safe iterator wrapper. 95 * 96 * The class template %_Safe_iterator is a wrapper around an 97 * iterator that tracks the iterator's movement among sequences and 98 * checks that operations performed on the "safe" iterator are 99 * legal. In additional to the basic iterator operations (which are 100 * validated, and then passed to the underlying iterator), 101 * %_Safe_iterator has member functions for iterator invalidation, 102 * attaching/detaching the iterator from sequences, and querying 103 * the iterator's state. 104 * 105 * Note that _Iterator must be the first base class so that it gets 106 * initialized before the iterator is being attached to the container's list 107 * of iterators and it is being detached before _Iterator get 108 * destroyed. Otherwise it would result in a data race. 109 */ 110 template<typename _Iterator, typename _Sequence, typename _Category 111 = typename std::iterator_traits<_Iterator>::iterator_category> 112 class _Safe_iterator 113 : private _Iterator, 114 public _Safe_iterator_base 115 { 116 typedef _Iterator _Iter_base; 117 typedef _Safe_iterator_base _Safe_base; 118 119 typedef std::iterator_traits<_Iterator> _Traits; 120 121 protected: 122 typedef std::__are_same<typename _Sequence::_Base::const_iterator, 123 _Iterator> _IsConstant; 124 125 typedef typename __gnu_cxx::__conditional_type< 126 _IsConstant::__value, 127 typename _Sequence::_Base::iterator, 128 typename _Sequence::_Base::const_iterator>::__type _OtherIterator; 129 130 struct _Attach_single 131 { }; 132 _Safe_iterator(_Iterator __i,_Safe_sequence_base * __seq,_Attach_single)133 _Safe_iterator(_Iterator __i, _Safe_sequence_base* __seq, _Attach_single) 134 _GLIBCXX_NOEXCEPT 135 : _Iter_base(__i) 136 { _M_attach_single(__seq); } 137 138 public: 139 typedef _Iterator iterator_type; 140 typedef typename _Traits::iterator_category iterator_category; 141 typedef typename _Traits::value_type value_type; 142 typedef typename _Traits::difference_type difference_type; 143 typedef typename _Traits::reference reference; 144 typedef typename _Traits::pointer pointer; 145 146 #if __cplusplus > 201703L && __cpp_lib_concepts 147 using iterator_concept = std::__detail::__iter_concept<_Iterator>; 148 #endif 149 150 /// @post the iterator is singular and unattached _Safe_iterator()151 _Safe_iterator() _GLIBCXX_NOEXCEPT : _Iter_base() { } 152 153 /** 154 * @brief Safe iterator construction from an unsafe iterator and 155 * its sequence. 156 * 157 * @pre @p seq is not NULL 158 * @post this is not singular 159 */ _Safe_iterator(_Iterator __i,const _Safe_sequence_base * __seq)160 _Safe_iterator(_Iterator __i, const _Safe_sequence_base* __seq) 161 _GLIBCXX_NOEXCEPT 162 : _Iter_base(__i), _Safe_base(__seq, _S_constant()) 163 { 164 _GLIBCXX_DEBUG_VERIFY(!this->_M_singular(), 165 _M_message(__msg_init_singular) 166 ._M_iterator(*this, "this")); 167 } 168 169 /** 170 * @brief Copy construction. 171 */ _Safe_iterator(const _Safe_iterator & __x)172 _Safe_iterator(const _Safe_iterator& __x) _GLIBCXX_NOEXCEPT 173 : _Iter_base(__x.base()) 174 { 175 // _GLIBCXX_RESOLVE_LIB_DEFECTS 176 // DR 408. Is vector<reverse_iterator<char*> > forbidden? 177 _GLIBCXX_DEBUG_VERIFY(!__x._M_singular() 178 || __x.base() == _Iterator(), 179 _M_message(__msg_init_copy_singular) 180 ._M_iterator(*this, "this") 181 ._M_iterator(__x, "other")); 182 _M_attach(__x._M_sequence); 183 } 184 185 #if __cplusplus >= 201103L 186 /** 187 * @brief Move construction. 188 * @post __x is singular and unattached 189 */ _Safe_iterator(_Safe_iterator && __x)190 _Safe_iterator(_Safe_iterator&& __x) noexcept 191 : _Iter_base() 192 { 193 _GLIBCXX_DEBUG_VERIFY(!__x._M_singular() 194 || __x.base() == _Iterator(), 195 _M_message(__msg_init_copy_singular) 196 ._M_iterator(*this, "this") 197 ._M_iterator(__x, "other")); 198 _Safe_sequence_base* __seq = __x._M_sequence; 199 __x._M_detach(); 200 std::swap(base(), __x.base()); 201 _M_attach(__seq); 202 } 203 #endif 204 205 /** 206 * @brief Converting constructor from a mutable iterator to a 207 * constant iterator. 208 */ 209 template<typename _MutableIterator> _Safe_iterator(const _Safe_iterator<_MutableIterator,_Sequence,typename __gnu_cxx::__enable_if<_IsConstant::__value && std::__are_same<_MutableIterator,_OtherIterator>::__value,_Category>::__type> & __x)210 _Safe_iterator( 211 const _Safe_iterator<_MutableIterator, _Sequence, 212 typename __gnu_cxx::__enable_if<_IsConstant::__value && 213 std::__are_same<_MutableIterator, _OtherIterator>::__value, 214 _Category>::__type>& __x) 215 _GLIBCXX_NOEXCEPT 216 : _Iter_base(__x.base()) 217 { 218 // _GLIBCXX_RESOLVE_LIB_DEFECTS 219 // DR 408. Is vector<reverse_iterator<char*> > forbidden? 220 _GLIBCXX_DEBUG_VERIFY(!__x._M_singular() 221 || __x.base() == _MutableIterator(), 222 _M_message(__msg_init_const_singular) 223 ._M_iterator(*this, "this") 224 ._M_iterator(__x, "other")); 225 _M_attach(__x._M_sequence); 226 } 227 228 /** 229 * @brief Copy assignment. 230 */ 231 _Safe_iterator& 232 operator=(const _Safe_iterator& __x) _GLIBCXX_NOEXCEPT 233 { 234 // _GLIBCXX_RESOLVE_LIB_DEFECTS 235 // DR 408. Is vector<reverse_iterator<char*> > forbidden? 236 _GLIBCXX_DEBUG_VERIFY(!__x._M_singular() 237 || __x.base() == _Iterator(), 238 _M_message(__msg_copy_singular) 239 ._M_iterator(*this, "this") 240 ._M_iterator(__x, "other")); 241 242 if (this->_M_sequence && this->_M_sequence == __x._M_sequence) 243 { 244 __gnu_cxx::__scoped_lock __l(this->_M_get_mutex()); 245 base() = __x.base(); 246 _M_version = __x._M_sequence->_M_version; 247 } 248 else 249 { 250 _M_detach(); 251 base() = __x.base(); 252 _M_attach(__x._M_sequence); 253 } 254 255 return *this; 256 } 257 258 #if __cplusplus >= 201103L 259 /** 260 * @brief Move assignment. 261 * @post __x is singular and unattached 262 */ 263 _Safe_iterator& 264 operator=(_Safe_iterator&& __x) noexcept 265 { 266 _GLIBCXX_DEBUG_VERIFY(this != &__x, 267 _M_message(__msg_self_move_assign) 268 ._M_iterator(*this, "this")); 269 _GLIBCXX_DEBUG_VERIFY(!__x._M_singular() 270 || __x.base() == _Iterator(), 271 _M_message(__msg_copy_singular) 272 ._M_iterator(*this, "this") 273 ._M_iterator(__x, "other")); 274 275 if (this->_M_sequence && this->_M_sequence == __x._M_sequence) 276 { 277 __gnu_cxx::__scoped_lock __l(this->_M_get_mutex()); 278 base() = __x.base(); 279 _M_version = __x._M_sequence->_M_version; 280 } 281 else 282 { 283 _M_detach(); 284 base() = __x.base(); 285 _M_attach(__x._M_sequence); 286 } 287 288 __x._M_detach(); 289 __x.base() = _Iterator(); 290 return *this; 291 } 292 #endif 293 294 /** 295 * @brief Iterator dereference. 296 * @pre iterator is dereferenceable 297 */ 298 reference 299 operator*() const _GLIBCXX_NOEXCEPT 300 { 301 _GLIBCXX_DEBUG_VERIFY(this->_M_dereferenceable(), 302 _M_message(__msg_bad_deref) 303 ._M_iterator(*this, "this")); 304 return *base(); 305 } 306 307 /** 308 * @brief Iterator dereference. 309 * @pre iterator is dereferenceable 310 */ 311 pointer 312 operator->() const _GLIBCXX_NOEXCEPT 313 { 314 _GLIBCXX_DEBUG_VERIFY(this->_M_dereferenceable(), 315 _M_message(__msg_bad_deref) 316 ._M_iterator(*this, "this")); 317 return base().operator->(); 318 } 319 320 // ------ Input iterator requirements ------ 321 /** 322 * @brief Iterator preincrement 323 * @pre iterator is incrementable 324 */ 325 _Safe_iterator& 326 operator++() _GLIBCXX_NOEXCEPT 327 { 328 _GLIBCXX_DEBUG_VERIFY(this->_M_incrementable(), 329 _M_message(__msg_bad_inc) 330 ._M_iterator(*this, "this")); 331 __gnu_cxx::__scoped_lock __l(this->_M_get_mutex()); 332 ++base(); 333 return *this; 334 } 335 336 /** 337 * @brief Iterator postincrement 338 * @pre iterator is incrementable 339 */ 340 _Safe_iterator 341 operator++(int) _GLIBCXX_NOEXCEPT 342 { 343 _GLIBCXX_DEBUG_VERIFY(this->_M_incrementable(), 344 _M_message(__msg_bad_inc) 345 ._M_iterator(*this, "this")); 346 __gnu_cxx::__scoped_lock __l(this->_M_get_mutex()); 347 return _Safe_iterator(base()++, this->_M_sequence, _Attach_single()); 348 } 349 350 // ------ Utilities ------ 351 352 /// Determine if this is a constant iterator. 353 static _GLIBCXX_CONSTEXPR bool _S_constant()354 _S_constant() 355 { return _IsConstant::__value; } 356 357 /** 358 * @brief Return the underlying iterator 359 */ 360 _Iterator& base()361 base() _GLIBCXX_NOEXCEPT { return *this; } 362 363 const _Iterator& base()364 base() const _GLIBCXX_NOEXCEPT { return *this; } 365 366 /** 367 * @brief Conversion to underlying non-debug iterator to allow 368 * better interaction with non-debug containers. 369 */ _Iterator()370 operator _Iterator() const _GLIBCXX_NOEXCEPT { return *this; } 371 372 /** Attach iterator to the given sequence. */ 373 void _M_attach(_Safe_sequence_base * __seq)374 _M_attach(_Safe_sequence_base* __seq) 375 { _Safe_base::_M_attach(__seq, _S_constant()); } 376 377 /** Likewise, but not thread-safe. */ 378 void _M_attach_single(_Safe_sequence_base * __seq)379 _M_attach_single(_Safe_sequence_base* __seq) 380 { _Safe_base::_M_attach_single(__seq, _S_constant()); } 381 382 /// Is the iterator dereferenceable? 383 bool _M_dereferenceable()384 _M_dereferenceable() const 385 { return !this->_M_singular() && !_M_is_end() && !_M_is_before_begin(); } 386 387 /// Is the iterator before a dereferenceable one? 388 bool _M_before_dereferenceable()389 _M_before_dereferenceable() const 390 { 391 if (this->_M_incrementable()) 392 { 393 _Iterator __base = base(); 394 return ++__base != _M_get_sequence()->_M_base().end(); 395 } 396 return false; 397 } 398 399 /// Is the iterator incrementable? 400 bool _M_incrementable()401 _M_incrementable() const 402 { return !this->_M_singular() && !_M_is_end(); } 403 404 // Can we advance the iterator @p __n steps (@p __n may be negative) 405 bool 406 _M_can_advance(difference_type __n, bool __strict = false) const; 407 408 // Can we advance the iterator using @p __dist in @p __way direction. 409 template<typename _Diff> 410 bool 411 _M_can_advance(const std::pair<_Diff, _Distance_precision>& __dist, 412 int __way) const; 413 414 // Is the iterator range [*this, __rhs) valid? 415 bool 416 _M_valid_range(const _Safe_iterator& __rhs, 417 std::pair<difference_type, _Distance_precision>& __dist, 418 bool __check_dereferenceable = true) const; 419 420 // The sequence this iterator references. 421 typename __gnu_cxx::__conditional_type< 422 _IsConstant::__value, const _Sequence*, _Sequence*>::__type _M_get_sequence()423 _M_get_sequence() const 424 { return static_cast<_Sequence*>(_M_sequence); } 425 426 // Get distance to __rhs. 427 typename _Distance_traits<_Iterator>::__type 428 _M_get_distance_to(const _Safe_iterator& __rhs) const; 429 430 // Get distance from sequence begin up to *this. 431 typename _Distance_traits<_Iterator>::__type 432 _M_get_distance_from_begin() const; 433 434 // Get distance from *this to sequence end. 435 typename _Distance_traits<_Iterator>::__type 436 _M_get_distance_to_end() const; 437 438 /// Is this iterator equal to the sequence's begin() iterator? 439 bool _M_is_begin()440 _M_is_begin() const 441 { return base() == _M_get_sequence()->_M_base().begin(); } 442 443 /// Is this iterator equal to the sequence's end() iterator? 444 bool _M_is_end()445 _M_is_end() const 446 { return base() == _M_get_sequence()->_M_base().end(); } 447 448 /// Is this iterator equal to the sequence's before_begin() iterator if 449 /// any? 450 bool _M_is_before_begin()451 _M_is_before_begin() const 452 { return _BeforeBeginHelper<_Sequence>::_S_Is(*this); } 453 454 /// Is this iterator equal to the sequence's before_begin() iterator if 455 /// any or begin() otherwise? 456 bool _M_is_beginnest()457 _M_is_beginnest() const 458 { return _BeforeBeginHelper<_Sequence>::_S_Is_Beginnest(*this); } 459 460 // ------ Operators ------ 461 462 typedef _Safe_iterator<_Iterator, _Sequence, iterator_category> _Self; 463 464 friend bool 465 operator==(const _Self& __lhs, const _Self& __rhs) _GLIBCXX_NOEXCEPT 466 { 467 _GLIBCXX_DEBUG_VERIFY_EQ_OPERANDS(__lhs, __rhs); 468 return __lhs.base() == __rhs.base(); 469 } 470 471 template<typename _IteR> 472 friend bool 473 operator==(const _Self& __lhs, 474 const _Safe_iterator<_IteR, _Sequence, iterator_category>& __rhs) 475 _GLIBCXX_NOEXCEPT 476 { 477 _GLIBCXX_DEBUG_VERIFY_EQ_OPERANDS(__lhs, __rhs); 478 return __lhs.base() == __rhs.base(); 479 } 480 481 #if ! __cpp_lib_three_way_comparison 482 friend bool 483 operator!=(const _Self& __lhs, const _Self& __rhs) _GLIBCXX_NOEXCEPT 484 { 485 _GLIBCXX_DEBUG_VERIFY_EQ_OPERANDS(__lhs, __rhs); 486 return __lhs.base() != __rhs.base(); 487 } 488 489 template<typename _IteR> 490 friend bool 491 operator!=(const _Self& __lhs, 492 const _Safe_iterator<_IteR, _Sequence, iterator_category>& __rhs) 493 _GLIBCXX_NOEXCEPT 494 { 495 _GLIBCXX_DEBUG_VERIFY_EQ_OPERANDS(__lhs, __rhs); 496 return __lhs.base() != __rhs.base(); 497 } 498 #endif // three-way comparison 499 }; 500 501 template<typename _Iterator, typename _Sequence> 502 class _Safe_iterator<_Iterator, _Sequence, std::bidirectional_iterator_tag> 503 : public _Safe_iterator<_Iterator, _Sequence, std::forward_iterator_tag> 504 { 505 typedef _Safe_iterator<_Iterator, _Sequence, 506 std::forward_iterator_tag> _Safe_base; 507 508 protected: 509 typedef typename _Safe_base::_OtherIterator _OtherIterator; 510 typedef typename _Safe_base::_Attach_single _Attach_single; 511 _Safe_iterator(_Iterator __i,_Safe_sequence_base * __seq,_Attach_single)512 _Safe_iterator(_Iterator __i, _Safe_sequence_base* __seq, _Attach_single) 513 _GLIBCXX_NOEXCEPT 514 : _Safe_base(__i, __seq, _Attach_single()) 515 { } 516 517 public: 518 /// @post the iterator is singular and unattached _Safe_iterator()519 _Safe_iterator() _GLIBCXX_NOEXCEPT { } 520 521 /** 522 * @brief Safe iterator construction from an unsafe iterator and 523 * its sequence. 524 * 525 * @pre @p seq is not NULL 526 * @post this is not singular 527 */ _Safe_iterator(_Iterator __i,const _Safe_sequence_base * __seq)528 _Safe_iterator(_Iterator __i, const _Safe_sequence_base* __seq) 529 _GLIBCXX_NOEXCEPT 530 : _Safe_base(__i, __seq) 531 { } 532 533 /** 534 * @brief Copy construction. 535 */ _Safe_iterator(const _Safe_iterator & __x)536 _Safe_iterator(const _Safe_iterator& __x) _GLIBCXX_NOEXCEPT 537 : _Safe_base(__x) 538 { } 539 540 #if __cplusplus >= 201103L 541 /** @brief Move construction. */ 542 _Safe_iterator(_Safe_iterator&&) = default; 543 #endif 544 545 /** 546 * @brief Converting constructor from a mutable iterator to a 547 * constant iterator. 548 */ 549 template<typename _MutableIterator> _Safe_iterator(const _Safe_iterator<_MutableIterator,_Sequence,typename __gnu_cxx::__enable_if<_Safe_base::_IsConstant::__value && std::__are_same<_MutableIterator,_OtherIterator>::__value,std::bidirectional_iterator_tag>::__type> & __x)550 _Safe_iterator( 551 const _Safe_iterator<_MutableIterator, _Sequence, 552 typename __gnu_cxx::__enable_if<_Safe_base::_IsConstant::__value && 553 std::__are_same<_MutableIterator, _OtherIterator>::__value, 554 std::bidirectional_iterator_tag>::__type>& __x) 555 _GLIBCXX_NOEXCEPT 556 : _Safe_base(__x) 557 { } 558 559 #if __cplusplus >= 201103L 560 /** @brief Copy assignment. */ 561 _Safe_iterator& 562 operator=(const _Safe_iterator&) = default; 563 564 /** @brief Move assignment. */ 565 _Safe_iterator& 566 operator=(_Safe_iterator&&) = default; 567 #else 568 /** @brief Copy assignment. */ 569 _Safe_iterator& 570 operator=(const _Safe_iterator& __x) 571 { 572 _Safe_base::operator=(__x); 573 return *this; 574 } 575 #endif 576 577 // ------ Input iterator requirements ------ 578 /** 579 * @brief Iterator preincrement 580 * @pre iterator is incrementable 581 */ 582 _Safe_iterator& 583 operator++() _GLIBCXX_NOEXCEPT 584 { 585 _Safe_base::operator++(); 586 return *this; 587 } 588 589 /** 590 * @brief Iterator postincrement 591 * @pre iterator is incrementable 592 */ 593 _Safe_iterator 594 operator++(int) _GLIBCXX_NOEXCEPT 595 { 596 _GLIBCXX_DEBUG_VERIFY(this->_M_incrementable(), 597 _M_message(__msg_bad_inc) 598 ._M_iterator(*this, "this")); 599 __gnu_cxx::__scoped_lock __l(this->_M_get_mutex()); 600 return _Safe_iterator(this->base()++, this->_M_sequence, 601 _Attach_single()); 602 } 603 604 // ------ Bidirectional iterator requirements ------ 605 /** 606 * @brief Iterator predecrement 607 * @pre iterator is decrementable 608 */ 609 _Safe_iterator& 610 operator--() _GLIBCXX_NOEXCEPT 611 { 612 _GLIBCXX_DEBUG_VERIFY(this->_M_decrementable(), 613 _M_message(__msg_bad_dec) 614 ._M_iterator(*this, "this")); 615 __gnu_cxx::__scoped_lock __l(this->_M_get_mutex()); 616 --this->base(); 617 return *this; 618 } 619 620 /** 621 * @brief Iterator postdecrement 622 * @pre iterator is decrementable 623 */ 624 _Safe_iterator 625 operator--(int) _GLIBCXX_NOEXCEPT 626 { 627 _GLIBCXX_DEBUG_VERIFY(this->_M_decrementable(), 628 _M_message(__msg_bad_dec) 629 ._M_iterator(*this, "this")); 630 __gnu_cxx::__scoped_lock __l(this->_M_get_mutex()); 631 return _Safe_iterator(this->base()--, this->_M_sequence, 632 _Attach_single()); 633 } 634 635 // ------ Utilities ------ 636 637 // Is the iterator decrementable? 638 bool _M_decrementable()639 _M_decrementable() const 640 { return !this->_M_singular() && !this->_M_is_begin(); } 641 }; 642 643 template<typename _Iterator, typename _Sequence> 644 class _Safe_iterator<_Iterator, _Sequence, std::random_access_iterator_tag> 645 : public _Safe_iterator<_Iterator, _Sequence, 646 std::bidirectional_iterator_tag> 647 { 648 typedef _Safe_iterator<_Iterator, _Sequence, 649 std::bidirectional_iterator_tag> _Safe_base; 650 typedef typename _Safe_base::_OtherIterator _OtherIterator; 651 652 typedef typename _Safe_base::_Self _Self; 653 typedef _Safe_iterator<_OtherIterator, _Sequence, 654 std::random_access_iterator_tag> _OtherSelf; 655 656 typedef typename _Safe_base::_Attach_single _Attach_single; 657 _Safe_iterator(_Iterator __i,_Safe_sequence_base * __seq,_Attach_single)658 _Safe_iterator(_Iterator __i, _Safe_sequence_base* __seq, _Attach_single) 659 _GLIBCXX_NOEXCEPT 660 : _Safe_base(__i, __seq, _Attach_single()) 661 { } 662 663 public: 664 typedef typename _Safe_base::difference_type difference_type; 665 typedef typename _Safe_base::reference reference; 666 667 /// @post the iterator is singular and unattached _Safe_iterator()668 _Safe_iterator() _GLIBCXX_NOEXCEPT { } 669 670 /** 671 * @brief Safe iterator construction from an unsafe iterator and 672 * its sequence. 673 * 674 * @pre @p seq is not NULL 675 * @post this is not singular 676 */ _Safe_iterator(_Iterator __i,const _Safe_sequence_base * __seq)677 _Safe_iterator(_Iterator __i, const _Safe_sequence_base* __seq) 678 _GLIBCXX_NOEXCEPT 679 : _Safe_base(__i, __seq) 680 { } 681 682 /** 683 * @brief Copy construction. 684 */ _Safe_iterator(const _Safe_iterator & __x)685 _Safe_iterator(const _Safe_iterator& __x) _GLIBCXX_NOEXCEPT 686 : _Safe_base(__x) 687 { } 688 689 #if __cplusplus >= 201103L 690 /** @brief Move construction. */ 691 _Safe_iterator(_Safe_iterator&&) = default; 692 #endif 693 694 /** 695 * @brief Converting constructor from a mutable iterator to a 696 * constant iterator. 697 */ 698 template<typename _MutableIterator> _Safe_iterator(const _Safe_iterator<_MutableIterator,_Sequence,typename __gnu_cxx::__enable_if<_Safe_base::_IsConstant::__value && std::__are_same<_MutableIterator,_OtherIterator>::__value,std::random_access_iterator_tag>::__type> & __x)699 _Safe_iterator( 700 const _Safe_iterator<_MutableIterator, _Sequence, 701 typename __gnu_cxx::__enable_if<_Safe_base::_IsConstant::__value && 702 std::__are_same<_MutableIterator, _OtherIterator>::__value, 703 std::random_access_iterator_tag>::__type>& __x) 704 _GLIBCXX_NOEXCEPT 705 : _Safe_base(__x) 706 { } 707 708 #if __cplusplus >= 201103L 709 /** @brief Copy assignment. */ 710 _Safe_iterator& 711 operator=(const _Safe_iterator&) = default; 712 713 /** @brief Move assignment. */ 714 _Safe_iterator& 715 operator=(_Safe_iterator&&) = default; 716 #else 717 /** @brief Copy assignment. */ 718 _Safe_iterator& 719 operator=(const _Safe_iterator& __x) 720 { 721 _Safe_base::operator=(__x); 722 return *this; 723 } 724 #endif 725 726 // Is the iterator range [*this, __rhs) valid? 727 bool 728 _M_valid_range(const _Safe_iterator& __rhs, 729 std::pair<difference_type, 730 _Distance_precision>& __dist) const; 731 732 // ------ Input iterator requirements ------ 733 /** 734 * @brief Iterator preincrement 735 * @pre iterator is incrementable 736 */ 737 _Safe_iterator& 738 operator++() _GLIBCXX_NOEXCEPT 739 { 740 _Safe_base::operator++(); 741 return *this; 742 } 743 744 /** 745 * @brief Iterator postincrement 746 * @pre iterator is incrementable 747 */ 748 _Safe_iterator 749 operator++(int) _GLIBCXX_NOEXCEPT 750 { 751 _GLIBCXX_DEBUG_VERIFY(this->_M_incrementable(), 752 _M_message(__msg_bad_inc) 753 ._M_iterator(*this, "this")); 754 __gnu_cxx::__scoped_lock __l(this->_M_get_mutex()); 755 return _Safe_iterator(this->base()++, this->_M_sequence, 756 _Attach_single()); 757 } 758 759 // ------ Bidirectional iterator requirements ------ 760 /** 761 * @brief Iterator predecrement 762 * @pre iterator is decrementable 763 */ 764 _Safe_iterator& 765 operator--() _GLIBCXX_NOEXCEPT 766 { 767 _Safe_base::operator--(); 768 return *this; 769 } 770 771 /** 772 * @brief Iterator postdecrement 773 * @pre iterator is decrementable 774 */ 775 _Safe_iterator 776 operator--(int) _GLIBCXX_NOEXCEPT 777 { 778 _GLIBCXX_DEBUG_VERIFY(this->_M_decrementable(), 779 _M_message(__msg_bad_dec) 780 ._M_iterator(*this, "this")); 781 __gnu_cxx::__scoped_lock __l(this->_M_get_mutex()); 782 return _Safe_iterator(this->base()--, this->_M_sequence, 783 _Attach_single()); 784 } 785 786 // ------ Random access iterator requirements ------ 787 reference 788 operator[](difference_type __n) const _GLIBCXX_NOEXCEPT 789 { 790 _GLIBCXX_DEBUG_VERIFY(this->_M_can_advance(__n) 791 && this->_M_can_advance(__n + 1), 792 _M_message(__msg_iter_subscript_oob) 793 ._M_iterator(*this)._M_integer(__n)); 794 return this->base()[__n]; 795 } 796 797 _Safe_iterator& 798 operator+=(difference_type __n) _GLIBCXX_NOEXCEPT 799 { 800 _GLIBCXX_DEBUG_VERIFY(this->_M_can_advance(__n), 801 _M_message(__msg_advance_oob) 802 ._M_iterator(*this)._M_integer(__n)); 803 __gnu_cxx::__scoped_lock __l(this->_M_get_mutex()); 804 this->base() += __n; 805 return *this; 806 } 807 808 _Safe_iterator& 809 operator-=(difference_type __n) _GLIBCXX_NOEXCEPT 810 { 811 _GLIBCXX_DEBUG_VERIFY(this->_M_can_advance(-__n), 812 _M_message(__msg_retreat_oob) 813 ._M_iterator(*this)._M_integer(__n)); 814 __gnu_cxx::__scoped_lock __l(this->_M_get_mutex()); 815 this->base() -= __n; 816 return *this; 817 } 818 819 #if __cpp_lib_three_way_comparison 820 friend auto 821 operator<=>(const _Self& __lhs, const _Self& __rhs) noexcept 822 { 823 _GLIBCXX_DEBUG_VERIFY_REL_OPERANDS(__lhs, __rhs); 824 return __lhs.base() <=> __rhs.base(); 825 } 826 827 friend auto 828 operator<=>(const _Self& __lhs, const _OtherSelf& __rhs) noexcept 829 { 830 _GLIBCXX_DEBUG_VERIFY_REL_OPERANDS(__lhs, __rhs); 831 return __lhs.base() <=> __rhs.base(); 832 } 833 #else 834 friend bool 835 operator<(const _Self& __lhs, const _Self& __rhs) _GLIBCXX_NOEXCEPT 836 { 837 _GLIBCXX_DEBUG_VERIFY_REL_OPERANDS(__lhs, __rhs); 838 return __lhs.base() < __rhs.base(); 839 } 840 841 friend bool 842 operator<(const _Self& __lhs, const _OtherSelf& __rhs) _GLIBCXX_NOEXCEPT 843 { 844 _GLIBCXX_DEBUG_VERIFY_REL_OPERANDS(__lhs, __rhs); 845 return __lhs.base() < __rhs.base(); 846 } 847 848 friend bool 849 operator<=(const _Self& __lhs, const _Self& __rhs) _GLIBCXX_NOEXCEPT 850 { 851 _GLIBCXX_DEBUG_VERIFY_REL_OPERANDS(__lhs, __rhs); 852 return __lhs.base() <= __rhs.base(); 853 } 854 855 friend bool 856 operator<=(const _Self& __lhs, const _OtherSelf& __rhs) _GLIBCXX_NOEXCEPT 857 { 858 _GLIBCXX_DEBUG_VERIFY_REL_OPERANDS(__lhs, __rhs); 859 return __lhs.base() <= __rhs.base(); 860 } 861 862 friend bool 863 operator>(const _Self& __lhs, const _Self& __rhs) _GLIBCXX_NOEXCEPT 864 { 865 _GLIBCXX_DEBUG_VERIFY_REL_OPERANDS(__lhs, __rhs); 866 return __lhs.base() > __rhs.base(); 867 } 868 869 friend bool 870 operator>(const _Self& __lhs, const _OtherSelf& __rhs) _GLIBCXX_NOEXCEPT 871 { 872 _GLIBCXX_DEBUG_VERIFY_REL_OPERANDS(__lhs, __rhs); 873 return __lhs.base() > __rhs.base(); 874 } 875 876 friend bool 877 operator>=(const _Self& __lhs, const _Self& __rhs) _GLIBCXX_NOEXCEPT 878 { 879 _GLIBCXX_DEBUG_VERIFY_REL_OPERANDS(__lhs, __rhs); 880 return __lhs.base() >= __rhs.base(); 881 } 882 883 friend bool 884 operator>=(const _Self& __lhs, const _OtherSelf& __rhs) _GLIBCXX_NOEXCEPT 885 { 886 _GLIBCXX_DEBUG_VERIFY_REL_OPERANDS(__lhs, __rhs); 887 return __lhs.base() >= __rhs.base(); 888 } 889 #endif // three-way comparison 890 891 // _GLIBCXX_RESOLVE_LIB_DEFECTS 892 // According to the resolution of DR179 not only the various comparison 893 // operators but also operator- must accept mixed iterator/const_iterator 894 // parameters. 895 friend difference_type 896 operator-(const _Self& __lhs, const _OtherSelf& __rhs) _GLIBCXX_NOEXCEPT 897 { 898 _GLIBCXX_DEBUG_VERIFY_DIST_OPERANDS(__lhs, __rhs); 899 return __lhs.base() - __rhs.base(); 900 } 901 902 friend difference_type 903 operator-(const _Self& __lhs, const _Self& __rhs) _GLIBCXX_NOEXCEPT 904 { 905 _GLIBCXX_DEBUG_VERIFY_DIST_OPERANDS(__lhs, __rhs); 906 return __lhs.base() - __rhs.base(); 907 } 908 909 friend _Self 910 operator+(const _Self& __x, difference_type __n) _GLIBCXX_NOEXCEPT 911 { 912 _GLIBCXX_DEBUG_VERIFY(__x._M_can_advance(__n), 913 _M_message(__msg_advance_oob) 914 ._M_iterator(__x)._M_integer(__n)); 915 return _Safe_iterator(__x.base() + __n, __x._M_sequence); 916 } 917 918 friend _Self 919 operator+(difference_type __n, const _Self& __x) _GLIBCXX_NOEXCEPT 920 { 921 _GLIBCXX_DEBUG_VERIFY(__x._M_can_advance(__n), 922 _M_message(__msg_advance_oob) 923 ._M_iterator(__x)._M_integer(__n)); 924 return _Safe_iterator(__n + __x.base(), __x._M_sequence); 925 } 926 927 friend _Self 928 operator-(const _Self& __x, difference_type __n) _GLIBCXX_NOEXCEPT 929 { 930 _GLIBCXX_DEBUG_VERIFY(__x._M_can_advance(-__n), 931 _M_message(__msg_retreat_oob) 932 ._M_iterator(__x)._M_integer(__n)); 933 return _Safe_iterator(__x.base() - __n, __x._M_sequence); 934 } 935 }; 936 937 /** Safe iterators know how to check if they form a valid range. */ 938 template<typename _Iterator, typename _Sequence, typename _Category> 939 inline bool __valid_range(const _Safe_iterator<_Iterator,_Sequence,_Category> & __first,const _Safe_iterator<_Iterator,_Sequence,_Category> & __last,typename _Distance_traits<_Iterator>::__type & __dist)940 __valid_range(const _Safe_iterator<_Iterator, _Sequence, 941 _Category>& __first, 942 const _Safe_iterator<_Iterator, _Sequence, 943 _Category>& __last, 944 typename _Distance_traits<_Iterator>::__type& __dist) 945 { return __first._M_valid_range(__last, __dist); } 946 947 template<typename _Iterator, typename _Sequence, typename _Category> 948 inline bool __valid_range(const _Safe_iterator<_Iterator,_Sequence,_Category> & __first,const _Safe_iterator<_Iterator,_Sequence,_Category> & __last)949 __valid_range(const _Safe_iterator<_Iterator, _Sequence, 950 _Category>& __first, 951 const _Safe_iterator<_Iterator, _Sequence, 952 _Category>& __last) 953 { 954 typename _Distance_traits<_Iterator>::__type __dist; 955 return __first._M_valid_range(__last, __dist); 956 } 957 958 template<typename _Iterator, typename _Sequence, typename _Category, 959 typename _Size> 960 inline bool __can_advance(const _Safe_iterator<_Iterator,_Sequence,_Category> & __it,_Size __n)961 __can_advance(const _Safe_iterator<_Iterator, _Sequence, _Category>& __it, 962 _Size __n) 963 { return __it._M_can_advance(__n); } 964 965 template<typename _Iterator, typename _Sequence, typename _Category, 966 typename _Diff> 967 inline bool __can_advance(const _Safe_iterator<_Iterator,_Sequence,_Category> & __it,const std::pair<_Diff,_Distance_precision> & __dist,int __way)968 __can_advance(const _Safe_iterator<_Iterator, _Sequence, _Category>& __it, 969 const std::pair<_Diff, _Distance_precision>& __dist, 970 int __way) 971 { return __it._M_can_advance(__dist, __way); } 972 973 template<typename _Iterator, typename _Sequence> 974 _Iterator __base(const _Safe_iterator<_Iterator,_Sequence,std::random_access_iterator_tag> & __it)975 __base(const _Safe_iterator<_Iterator, _Sequence, 976 std::random_access_iterator_tag>& __it) 977 { return __it.base(); } 978 979 #if __cplusplus < 201103L 980 template<typename _Iterator, typename _Sequence> 981 struct _Unsafe_type<_Safe_iterator<_Iterator, _Sequence> > 982 { typedef _Iterator _Type; }; 983 #endif 984 985 template<typename _Iterator, typename _Sequence> 986 inline _Iterator 987 __unsafe(const _Safe_iterator<_Iterator, _Sequence>& __it) 988 { return __it.base(); } 989 990 } // namespace __gnu_debug 991 992 #undef _GLIBCXX_DEBUG_VERIFY_DIST_OPERANDS 993 #undef _GLIBCXX_DEBUG_VERIFY_REL_OPERANDS 994 #undef _GLIBCXX_DEBUG_VERIFY_EQ_OPERANDS 995 #undef _GLIBCXX_DEBUG_VERIFY_OPERANDS 996 997 #include <debug/safe_iterator.tcc> 998 999 #endif 1000