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