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 74 _S_Is(const _Safe_iterator<_Iterator, _Sequence, _Category>&) 75 { return false; } 76 77 template<typename _Iterator, typename _Category> 78 static bool 79 _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 90 _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 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 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 */ 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 */ 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 */ 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> 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 354 _S_constant() 355 { return _IsConstant::__value; } 356 357 /** 358 * @brief Return the underlying iterator 359 */ 360 _Iterator& 361 base() _GLIBCXX_NOEXCEPT { return *this; } 362 363 const _Iterator& 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 */ 370 operator _Iterator() const _GLIBCXX_NOEXCEPT { return *this; } 371 372 /** Attach iterator to the given sequence. */ 373 void 374 _M_attach(_Safe_sequence_base* __seq) 375 { _Safe_base::_M_attach(__seq, _S_constant()); } 376 377 /** Likewise, but not thread-safe. */ 378 void 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 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 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 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 // Is the iterator range [*this, __rhs) valid? 409 bool 410 _M_valid_range(const _Safe_iterator& __rhs, 411 std::pair<difference_type, _Distance_precision>& __dist, 412 bool __check_dereferenceable = true) const; 413 414 // The sequence this iterator references. 415 typename __gnu_cxx::__conditional_type< 416 _IsConstant::__value, const _Sequence*, _Sequence*>::__type 417 _M_get_sequence() const 418 { return static_cast<_Sequence*>(_M_sequence); } 419 420 // Get distance to __rhs. 421 typename _Distance_traits<_Iterator>::__type 422 _M_get_distance_to(const _Safe_iterator& __rhs) const; 423 424 // Get distance from sequence begin up to *this. 425 typename _Distance_traits<_Iterator>::__type 426 _M_get_distance_from_begin() const; 427 428 // Get distance from *this to sequence end. 429 typename _Distance_traits<_Iterator>::__type 430 _M_get_distance_to_end() const; 431 432 /// Is this iterator equal to the sequence's begin() iterator? 433 bool 434 _M_is_begin() const 435 { return base() == _M_get_sequence()->_M_base().begin(); } 436 437 /// Is this iterator equal to the sequence's end() iterator? 438 bool 439 _M_is_end() const 440 { return base() == _M_get_sequence()->_M_base().end(); } 441 442 /// Is this iterator equal to the sequence's before_begin() iterator if 443 /// any? 444 bool 445 _M_is_before_begin() const 446 { return _BeforeBeginHelper<_Sequence>::_S_Is(*this); } 447 448 /// Is this iterator equal to the sequence's before_begin() iterator if 449 /// any or begin() otherwise? 450 bool 451 _M_is_beginnest() const 452 { return _BeforeBeginHelper<_Sequence>::_S_Is_Beginnest(*this); } 453 454 // ------ Operators ------ 455 456 typedef _Safe_iterator<_Iterator, _Sequence, iterator_category> _Self; 457 458 friend bool 459 operator==(const _Self& __lhs, const _Self& __rhs) _GLIBCXX_NOEXCEPT 460 { 461 _GLIBCXX_DEBUG_VERIFY_EQ_OPERANDS(__lhs, __rhs); 462 return __lhs.base() == __rhs.base(); 463 } 464 465 template<typename _IteR> 466 friend bool 467 operator==(const _Self& __lhs, 468 const _Safe_iterator<_IteR, _Sequence, iterator_category>& __rhs) 469 _GLIBCXX_NOEXCEPT 470 { 471 _GLIBCXX_DEBUG_VERIFY_EQ_OPERANDS(__lhs, __rhs); 472 return __lhs.base() == __rhs.base(); 473 } 474 475 #if ! __cpp_lib_three_way_comparison 476 friend bool 477 operator!=(const _Self& __lhs, const _Self& __rhs) _GLIBCXX_NOEXCEPT 478 { 479 _GLIBCXX_DEBUG_VERIFY_EQ_OPERANDS(__lhs, __rhs); 480 return __lhs.base() != __rhs.base(); 481 } 482 483 template<typename _IteR> 484 friend bool 485 operator!=(const _Self& __lhs, 486 const _Safe_iterator<_IteR, _Sequence, iterator_category>& __rhs) 487 _GLIBCXX_NOEXCEPT 488 { 489 _GLIBCXX_DEBUG_VERIFY_EQ_OPERANDS(__lhs, __rhs); 490 return __lhs.base() != __rhs.base(); 491 } 492 #endif // three-way comparison 493 }; 494 495 template<typename _Iterator, typename _Sequence> 496 class _Safe_iterator<_Iterator, _Sequence, std::bidirectional_iterator_tag> 497 : public _Safe_iterator<_Iterator, _Sequence, std::forward_iterator_tag> 498 { 499 typedef _Safe_iterator<_Iterator, _Sequence, 500 std::forward_iterator_tag> _Safe_base; 501 502 protected: 503 typedef typename _Safe_base::_OtherIterator _OtherIterator; 504 typedef typename _Safe_base::_Attach_single _Attach_single; 505 506 _Safe_iterator(_Iterator __i, _Safe_sequence_base* __seq, _Attach_single) 507 _GLIBCXX_NOEXCEPT 508 : _Safe_base(__i, __seq, _Attach_single()) 509 { } 510 511 public: 512 /// @post the iterator is singular and unattached 513 _Safe_iterator() _GLIBCXX_NOEXCEPT { } 514 515 /** 516 * @brief Safe iterator construction from an unsafe iterator and 517 * its sequence. 518 * 519 * @pre @p seq is not NULL 520 * @post this is not singular 521 */ 522 _Safe_iterator(_Iterator __i, const _Safe_sequence_base* __seq) 523 _GLIBCXX_NOEXCEPT 524 : _Safe_base(__i, __seq) 525 { } 526 527 /** 528 * @brief Copy construction. 529 */ 530 _Safe_iterator(const _Safe_iterator& __x) _GLIBCXX_NOEXCEPT 531 : _Safe_base(__x) 532 { } 533 534 #if __cplusplus >= 201103L 535 /** @brief Move construction. */ 536 _Safe_iterator(_Safe_iterator&&) = default; 537 #endif 538 539 /** 540 * @brief Converting constructor from a mutable iterator to a 541 * constant iterator. 542 */ 543 template<typename _MutableIterator> 544 _Safe_iterator( 545 const _Safe_iterator<_MutableIterator, _Sequence, 546 typename __gnu_cxx::__enable_if<_Safe_base::_IsConstant::__value && 547 std::__are_same<_MutableIterator, _OtherIterator>::__value, 548 std::bidirectional_iterator_tag>::__type>& __x) 549 _GLIBCXX_NOEXCEPT 550 : _Safe_base(__x) 551 { } 552 553 #if __cplusplus >= 201103L 554 /** @brief Copy assignment. */ 555 _Safe_iterator& 556 operator=(const _Safe_iterator&) = default; 557 558 /** @brief Move assignment. */ 559 _Safe_iterator& 560 operator=(_Safe_iterator&&) = default; 561 #else 562 /** @brief Copy assignment. */ 563 _Safe_iterator& 564 operator=(const _Safe_iterator& __x) 565 { 566 _Safe_base::operator=(__x); 567 return *this; 568 } 569 #endif 570 571 // ------ Input iterator requirements ------ 572 /** 573 * @brief Iterator preincrement 574 * @pre iterator is incrementable 575 */ 576 _Safe_iterator& 577 operator++() _GLIBCXX_NOEXCEPT 578 { 579 _Safe_base::operator++(); 580 return *this; 581 } 582 583 /** 584 * @brief Iterator postincrement 585 * @pre iterator is incrementable 586 */ 587 _Safe_iterator 588 operator++(int) _GLIBCXX_NOEXCEPT 589 { 590 _GLIBCXX_DEBUG_VERIFY(this->_M_incrementable(), 591 _M_message(__msg_bad_inc) 592 ._M_iterator(*this, "this")); 593 __gnu_cxx::__scoped_lock __l(this->_M_get_mutex()); 594 return _Safe_iterator(this->base()++, this->_M_sequence, 595 _Attach_single()); 596 } 597 598 // ------ Bidirectional iterator requirements ------ 599 /** 600 * @brief Iterator predecrement 601 * @pre iterator is decrementable 602 */ 603 _Safe_iterator& 604 operator--() _GLIBCXX_NOEXCEPT 605 { 606 _GLIBCXX_DEBUG_VERIFY(this->_M_decrementable(), 607 _M_message(__msg_bad_dec) 608 ._M_iterator(*this, "this")); 609 __gnu_cxx::__scoped_lock __l(this->_M_get_mutex()); 610 --this->base(); 611 return *this; 612 } 613 614 /** 615 * @brief Iterator postdecrement 616 * @pre iterator is decrementable 617 */ 618 _Safe_iterator 619 operator--(int) _GLIBCXX_NOEXCEPT 620 { 621 _GLIBCXX_DEBUG_VERIFY(this->_M_decrementable(), 622 _M_message(__msg_bad_dec) 623 ._M_iterator(*this, "this")); 624 __gnu_cxx::__scoped_lock __l(this->_M_get_mutex()); 625 return _Safe_iterator(this->base()--, this->_M_sequence, 626 _Attach_single()); 627 } 628 629 // ------ Utilities ------ 630 631 // Is the iterator decrementable? 632 bool 633 _M_decrementable() const 634 { return !this->_M_singular() && !this->_M_is_begin(); } 635 }; 636 637 template<typename _Iterator, typename _Sequence> 638 class _Safe_iterator<_Iterator, _Sequence, std::random_access_iterator_tag> 639 : public _Safe_iterator<_Iterator, _Sequence, 640 std::bidirectional_iterator_tag> 641 { 642 typedef _Safe_iterator<_Iterator, _Sequence, 643 std::bidirectional_iterator_tag> _Safe_base; 644 typedef typename _Safe_base::_OtherIterator _OtherIterator; 645 646 typedef typename _Safe_base::_Self _Self; 647 typedef _Safe_iterator<_OtherIterator, _Sequence, 648 std::random_access_iterator_tag> _OtherSelf; 649 650 typedef typename _Safe_base::_Attach_single _Attach_single; 651 652 _Safe_iterator(_Iterator __i, _Safe_sequence_base* __seq, _Attach_single) 653 _GLIBCXX_NOEXCEPT 654 : _Safe_base(__i, __seq, _Attach_single()) 655 { } 656 657 public: 658 typedef typename _Safe_base::difference_type difference_type; 659 typedef typename _Safe_base::reference reference; 660 661 /// @post the iterator is singular and unattached 662 _Safe_iterator() _GLIBCXX_NOEXCEPT { } 663 664 /** 665 * @brief Safe iterator construction from an unsafe iterator and 666 * its sequence. 667 * 668 * @pre @p seq is not NULL 669 * @post this is not singular 670 */ 671 _Safe_iterator(_Iterator __i, const _Safe_sequence_base* __seq) 672 _GLIBCXX_NOEXCEPT 673 : _Safe_base(__i, __seq) 674 { } 675 676 /** 677 * @brief Copy construction. 678 */ 679 _Safe_iterator(const _Safe_iterator& __x) _GLIBCXX_NOEXCEPT 680 : _Safe_base(__x) 681 { } 682 683 #if __cplusplus >= 201103L 684 /** @brief Move construction. */ 685 _Safe_iterator(_Safe_iterator&&) = default; 686 #endif 687 688 /** 689 * @brief Converting constructor from a mutable iterator to a 690 * constant iterator. 691 */ 692 template<typename _MutableIterator> 693 _Safe_iterator( 694 const _Safe_iterator<_MutableIterator, _Sequence, 695 typename __gnu_cxx::__enable_if<_Safe_base::_IsConstant::__value && 696 std::__are_same<_MutableIterator, _OtherIterator>::__value, 697 std::random_access_iterator_tag>::__type>& __x) 698 _GLIBCXX_NOEXCEPT 699 : _Safe_base(__x) 700 { } 701 702 #if __cplusplus >= 201103L 703 /** @brief Copy assignment. */ 704 _Safe_iterator& 705 operator=(const _Safe_iterator&) = default; 706 707 /** @brief Move assignment. */ 708 _Safe_iterator& 709 operator=(_Safe_iterator&&) = default; 710 #else 711 /** @brief Copy assignment. */ 712 _Safe_iterator& 713 operator=(const _Safe_iterator& __x) 714 { 715 _Safe_base::operator=(__x); 716 return *this; 717 } 718 #endif 719 720 // Is the iterator range [*this, __rhs) valid? 721 bool 722 _M_valid_range(const _Safe_iterator& __rhs, 723 std::pair<difference_type, 724 _Distance_precision>& __dist) const; 725 726 // ------ Input iterator requirements ------ 727 /** 728 * @brief Iterator preincrement 729 * @pre iterator is incrementable 730 */ 731 _Safe_iterator& 732 operator++() _GLIBCXX_NOEXCEPT 733 { 734 _Safe_base::operator++(); 735 return *this; 736 } 737 738 /** 739 * @brief Iterator postincrement 740 * @pre iterator is incrementable 741 */ 742 _Safe_iterator 743 operator++(int) _GLIBCXX_NOEXCEPT 744 { 745 _GLIBCXX_DEBUG_VERIFY(this->_M_incrementable(), 746 _M_message(__msg_bad_inc) 747 ._M_iterator(*this, "this")); 748 __gnu_cxx::__scoped_lock __l(this->_M_get_mutex()); 749 return _Safe_iterator(this->base()++, this->_M_sequence, 750 _Attach_single()); 751 } 752 753 // ------ Bidirectional iterator requirements ------ 754 /** 755 * @brief Iterator predecrement 756 * @pre iterator is decrementable 757 */ 758 _Safe_iterator& 759 operator--() _GLIBCXX_NOEXCEPT 760 { 761 _Safe_base::operator--(); 762 return *this; 763 } 764 765 /** 766 * @brief Iterator postdecrement 767 * @pre iterator is decrementable 768 */ 769 _Safe_iterator 770 operator--(int) _GLIBCXX_NOEXCEPT 771 { 772 _GLIBCXX_DEBUG_VERIFY(this->_M_decrementable(), 773 _M_message(__msg_bad_dec) 774 ._M_iterator(*this, "this")); 775 __gnu_cxx::__scoped_lock __l(this->_M_get_mutex()); 776 return _Safe_iterator(this->base()--, this->_M_sequence, 777 _Attach_single()); 778 } 779 780 // ------ Random access iterator requirements ------ 781 reference 782 operator[](difference_type __n) const _GLIBCXX_NOEXCEPT 783 { 784 _GLIBCXX_DEBUG_VERIFY(this->_M_can_advance(__n) 785 && this->_M_can_advance(__n + 1), 786 _M_message(__msg_iter_subscript_oob) 787 ._M_iterator(*this)._M_integer(__n)); 788 return this->base()[__n]; 789 } 790 791 _Safe_iterator& 792 operator+=(difference_type __n) _GLIBCXX_NOEXCEPT 793 { 794 _GLIBCXX_DEBUG_VERIFY(this->_M_can_advance(__n), 795 _M_message(__msg_advance_oob) 796 ._M_iterator(*this)._M_integer(__n)); 797 __gnu_cxx::__scoped_lock __l(this->_M_get_mutex()); 798 this->base() += __n; 799 return *this; 800 } 801 802 _Safe_iterator& 803 operator-=(difference_type __n) _GLIBCXX_NOEXCEPT 804 { 805 _GLIBCXX_DEBUG_VERIFY(this->_M_can_advance(-__n), 806 _M_message(__msg_retreat_oob) 807 ._M_iterator(*this)._M_integer(__n)); 808 __gnu_cxx::__scoped_lock __l(this->_M_get_mutex()); 809 this->base() -= __n; 810 return *this; 811 } 812 813 #if __cpp_lib_three_way_comparison 814 friend auto 815 operator<=>(const _Self& __lhs, const _Self& __rhs) noexcept 816 { 817 _GLIBCXX_DEBUG_VERIFY_REL_OPERANDS(__lhs, __rhs); 818 return __lhs.base() <=> __rhs.base(); 819 } 820 821 friend auto 822 operator<=>(const _Self& __lhs, const _OtherSelf& __rhs) noexcept 823 { 824 _GLIBCXX_DEBUG_VERIFY_REL_OPERANDS(__lhs, __rhs); 825 return __lhs.base() <=> __rhs.base(); 826 } 827 #else 828 friend bool 829 operator<(const _Self& __lhs, const _Self& __rhs) _GLIBCXX_NOEXCEPT 830 { 831 _GLIBCXX_DEBUG_VERIFY_REL_OPERANDS(__lhs, __rhs); 832 return __lhs.base() < __rhs.base(); 833 } 834 835 friend bool 836 operator<(const _Self& __lhs, const _OtherSelf& __rhs) _GLIBCXX_NOEXCEPT 837 { 838 _GLIBCXX_DEBUG_VERIFY_REL_OPERANDS(__lhs, __rhs); 839 return __lhs.base() < __rhs.base(); 840 } 841 842 friend bool 843 operator<=(const _Self& __lhs, const _Self& __rhs) _GLIBCXX_NOEXCEPT 844 { 845 _GLIBCXX_DEBUG_VERIFY_REL_OPERANDS(__lhs, __rhs); 846 return __lhs.base() <= __rhs.base(); 847 } 848 849 friend bool 850 operator<=(const _Self& __lhs, const _OtherSelf& __rhs) _GLIBCXX_NOEXCEPT 851 { 852 _GLIBCXX_DEBUG_VERIFY_REL_OPERANDS(__lhs, __rhs); 853 return __lhs.base() <= __rhs.base(); 854 } 855 856 friend bool 857 operator>(const _Self& __lhs, const _Self& __rhs) _GLIBCXX_NOEXCEPT 858 { 859 _GLIBCXX_DEBUG_VERIFY_REL_OPERANDS(__lhs, __rhs); 860 return __lhs.base() > __rhs.base(); 861 } 862 863 friend bool 864 operator>(const _Self& __lhs, const _OtherSelf& __rhs) _GLIBCXX_NOEXCEPT 865 { 866 _GLIBCXX_DEBUG_VERIFY_REL_OPERANDS(__lhs, __rhs); 867 return __lhs.base() > __rhs.base(); 868 } 869 870 friend bool 871 operator>=(const _Self& __lhs, const _Self& __rhs) _GLIBCXX_NOEXCEPT 872 { 873 _GLIBCXX_DEBUG_VERIFY_REL_OPERANDS(__lhs, __rhs); 874 return __lhs.base() >= __rhs.base(); 875 } 876 877 friend bool 878 operator>=(const _Self& __lhs, const _OtherSelf& __rhs) _GLIBCXX_NOEXCEPT 879 { 880 _GLIBCXX_DEBUG_VERIFY_REL_OPERANDS(__lhs, __rhs); 881 return __lhs.base() >= __rhs.base(); 882 } 883 #endif // three-way comparison 884 885 // _GLIBCXX_RESOLVE_LIB_DEFECTS 886 // According to the resolution of DR179 not only the various comparison 887 // operators but also operator- must accept mixed iterator/const_iterator 888 // parameters. 889 friend difference_type 890 operator-(const _Self& __lhs, const _OtherSelf& __rhs) _GLIBCXX_NOEXCEPT 891 { 892 _GLIBCXX_DEBUG_VERIFY_DIST_OPERANDS(__lhs, __rhs); 893 return __lhs.base() - __rhs.base(); 894 } 895 896 friend difference_type 897 operator-(const _Self& __lhs, const _Self& __rhs) _GLIBCXX_NOEXCEPT 898 { 899 _GLIBCXX_DEBUG_VERIFY_DIST_OPERANDS(__lhs, __rhs); 900 return __lhs.base() - __rhs.base(); 901 } 902 903 friend _Self 904 operator+(const _Self& __x, difference_type __n) _GLIBCXX_NOEXCEPT 905 { 906 _GLIBCXX_DEBUG_VERIFY(__x._M_can_advance(__n), 907 _M_message(__msg_advance_oob) 908 ._M_iterator(__x)._M_integer(__n)); 909 return _Safe_iterator(__x.base() + __n, __x._M_sequence); 910 } 911 912 friend _Self 913 operator+(difference_type __n, const _Self& __x) _GLIBCXX_NOEXCEPT 914 { 915 _GLIBCXX_DEBUG_VERIFY(__x._M_can_advance(__n), 916 _M_message(__msg_advance_oob) 917 ._M_iterator(__x)._M_integer(__n)); 918 return _Safe_iterator(__n + __x.base(), __x._M_sequence); 919 } 920 921 friend _Self 922 operator-(const _Self& __x, difference_type __n) _GLIBCXX_NOEXCEPT 923 { 924 _GLIBCXX_DEBUG_VERIFY(__x._M_can_advance(-__n), 925 _M_message(__msg_retreat_oob) 926 ._M_iterator(__x)._M_integer(__n)); 927 return _Safe_iterator(__x.base() - __n, __x._M_sequence); 928 } 929 }; 930 931 /** Safe iterators know how to check if they form a valid range. */ 932 template<typename _Iterator, typename _Sequence, typename _Category> 933 inline bool 934 __valid_range(const _Safe_iterator<_Iterator, _Sequence, 935 _Category>& __first, 936 const _Safe_iterator<_Iterator, _Sequence, 937 _Category>& __last, 938 typename _Distance_traits<_Iterator>::__type& __dist) 939 { return __first._M_valid_range(__last, __dist); } 940 941 template<typename _Iterator, typename _Sequence, typename _Category> 942 inline bool 943 __valid_range(const _Safe_iterator<_Iterator, _Sequence, 944 _Category>& __first, 945 const _Safe_iterator<_Iterator, _Sequence, 946 _Category>& __last) 947 { 948 typename _Distance_traits<_Iterator>::__type __dist; 949 return __first._M_valid_range(__last, __dist); 950 } 951 952 template<typename _Iterator, typename _Sequence, typename _Category, 953 typename _Size> 954 inline bool 955 __can_advance(const _Safe_iterator<_Iterator, _Sequence, _Category>& __it, 956 _Size __n) 957 { return __it._M_can_advance(__n); } 958 959 template<typename _Iterator, typename _Sequence> 960 _Iterator 961 __base(const _Safe_iterator<_Iterator, _Sequence, 962 std::random_access_iterator_tag>& __it) 963 { return __it.base(); } 964 965 #if __cplusplus < 201103L 966 template<typename _Iterator, typename _Sequence> 967 struct _Unsafe_type<_Safe_iterator<_Iterator, _Sequence> > 968 { typedef _Iterator _Type; }; 969 #endif 970 971 template<typename _Iterator, typename _Sequence> 972 inline _Iterator 973 __unsafe(const _Safe_iterator<_Iterator, _Sequence>& __it) 974 { return __it.base(); } 975 976 } // namespace __gnu_debug 977 978 #undef _GLIBCXX_DEBUG_VERIFY_DIST_OPERANDS 979 #undef _GLIBCXX_DEBUG_VERIFY_REL_OPERANDS 980 #undef _GLIBCXX_DEBUG_VERIFY_EQ_OPERANDS 981 #undef _GLIBCXX_DEBUG_VERIFY_OPERANDS 982 983 #include <debug/safe_iterator.tcc> 984 985 #endif 986