1 // Debugging list implementation -*- C++ -*- 2 3 // Copyright (C) 2003-2013 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/list 26 * This file is a GNU debug extension to the Standard C++ Library. 27 */ 28 29 #ifndef _GLIBCXX_DEBUG_LIST 30 #define _GLIBCXX_DEBUG_LIST 1 31 32 #include <list> 33 #include <debug/safe_sequence.h> 34 #include <debug/safe_iterator.h> 35 36 namespace std _GLIBCXX_VISIBILITY(default) 37 { 38 namespace __debug 39 { 40 /// Class std::list with safety/checking/debug instrumentation. 41 template<typename _Tp, typename _Allocator = std::allocator<_Tp> > 42 class list 43 : public _GLIBCXX_STD_C::list<_Tp, _Allocator>, 44 public __gnu_debug::_Safe_sequence<list<_Tp, _Allocator> > 45 { 46 typedef _GLIBCXX_STD_C::list<_Tp, _Allocator> _Base; 47 48 typedef typename _Base::iterator _Base_iterator; 49 typedef typename _Base::const_iterator _Base_const_iterator; 50 typedef __gnu_debug::_Equal_to<_Base_const_iterator> _Equal; 51 typedef __gnu_debug::_Not_equal_to<_Base_const_iterator> _Not_equal; 52 public: 53 typedef typename _Base::reference reference; 54 typedef typename _Base::const_reference const_reference; 55 56 typedef __gnu_debug::_Safe_iterator<_Base_iterator, list> 57 iterator; 58 typedef __gnu_debug::_Safe_iterator<_Base_const_iterator, list> 59 const_iterator; 60 61 typedef typename _Base::size_type size_type; 62 typedef typename _Base::difference_type difference_type; 63 64 typedef _Tp value_type; 65 typedef _Allocator allocator_type; 66 typedef typename _Base::pointer pointer; 67 typedef typename _Base::const_pointer const_pointer; 68 typedef std::reverse_iterator<iterator> reverse_iterator; 69 typedef std::reverse_iterator<const_iterator> const_reverse_iterator; 70 71 // 23.2.2.1 construct/copy/destroy: 72 explicit 73 list(const _Allocator& __a = _Allocator()) 74 : _Base(__a) { } 75 76 #if __cplusplus >= 201103L 77 explicit 78 list(size_type __n) 79 : _Base(__n) { } 80 81 list(size_type __n, const _Tp& __value, 82 const _Allocator& __a = _Allocator()) 83 : _Base(__n, __value, __a) { } 84 #else 85 explicit 86 list(size_type __n, const _Tp& __value = _Tp(), 87 const _Allocator& __a = _Allocator()) 88 : _Base(__n, __value, __a) { } 89 #endif 90 91 #if __cplusplus >= 201103L 92 template<class _InputIterator, 93 typename = std::_RequireInputIter<_InputIterator>> 94 #else 95 template<class _InputIterator> 96 #endif 97 list(_InputIterator __first, _InputIterator __last, 98 const _Allocator& __a = _Allocator()) 99 : _Base(__gnu_debug::__base(__gnu_debug::__check_valid_range(__first, 100 __last)), 101 __gnu_debug::__base(__last), __a) 102 { } 103 104 list(const list& __x) 105 : _Base(__x) { } 106 107 list(const _Base& __x) 108 : _Base(__x) { } 109 110 #if __cplusplus >= 201103L 111 list(list&& __x) noexcept 112 : _Base(std::move(__x)) 113 { this->_M_swap(__x); } 114 115 list(initializer_list<value_type> __l, 116 const allocator_type& __a = allocator_type()) 117 : _Base(__l, __a) { } 118 #endif 119 120 ~list() _GLIBCXX_NOEXCEPT { } 121 122 list& 123 operator=(const list& __x) 124 { 125 static_cast<_Base&>(*this) = __x; 126 this->_M_invalidate_all(); 127 return *this; 128 } 129 130 #if __cplusplus >= 201103L 131 list& 132 operator=(list&& __x) 133 { 134 // NB: DR 1204. 135 // NB: DR 675. 136 __glibcxx_check_self_move_assign(__x); 137 clear(); 138 swap(__x); 139 return *this; 140 } 141 142 list& 143 operator=(initializer_list<value_type> __l) 144 { 145 static_cast<_Base&>(*this) = __l; 146 this->_M_invalidate_all(); 147 return *this; 148 } 149 150 void 151 assign(initializer_list<value_type> __l) 152 { 153 _Base::assign(__l); 154 this->_M_invalidate_all(); 155 } 156 #endif 157 158 #if __cplusplus >= 201103L 159 template<class _InputIterator, 160 typename = std::_RequireInputIter<_InputIterator>> 161 #else 162 template<class _InputIterator> 163 #endif 164 void 165 assign(_InputIterator __first, _InputIterator __last) 166 { 167 __glibcxx_check_valid_range(__first, __last); 168 _Base::assign(__gnu_debug::__base(__first), 169 __gnu_debug::__base(__last)); 170 this->_M_invalidate_all(); 171 } 172 173 void 174 assign(size_type __n, const _Tp& __t) 175 { 176 _Base::assign(__n, __t); 177 this->_M_invalidate_all(); 178 } 179 180 using _Base::get_allocator; 181 182 // iterators: 183 iterator 184 begin() _GLIBCXX_NOEXCEPT 185 { return iterator(_Base::begin(), this); } 186 187 const_iterator 188 begin() const _GLIBCXX_NOEXCEPT 189 { return const_iterator(_Base::begin(), this); } 190 191 iterator 192 end() _GLIBCXX_NOEXCEPT 193 { return iterator(_Base::end(), this); } 194 195 const_iterator 196 end() const _GLIBCXX_NOEXCEPT 197 { return const_iterator(_Base::end(), this); } 198 199 reverse_iterator 200 rbegin() _GLIBCXX_NOEXCEPT 201 { return reverse_iterator(end()); } 202 203 const_reverse_iterator 204 rbegin() const _GLIBCXX_NOEXCEPT 205 { return const_reverse_iterator(end()); } 206 207 reverse_iterator 208 rend() _GLIBCXX_NOEXCEPT 209 { return reverse_iterator(begin()); } 210 211 const_reverse_iterator 212 rend() const _GLIBCXX_NOEXCEPT 213 { return const_reverse_iterator(begin()); } 214 215 #if __cplusplus >= 201103L 216 const_iterator 217 cbegin() const noexcept 218 { return const_iterator(_Base::begin(), this); } 219 220 const_iterator 221 cend() const noexcept 222 { return const_iterator(_Base::end(), this); } 223 224 const_reverse_iterator 225 crbegin() const noexcept 226 { return const_reverse_iterator(end()); } 227 228 const_reverse_iterator 229 crend() const noexcept 230 { return const_reverse_iterator(begin()); } 231 #endif 232 233 // 23.2.2.2 capacity: 234 using _Base::empty; 235 using _Base::size; 236 using _Base::max_size; 237 238 #if __cplusplus >= 201103L 239 void 240 resize(size_type __sz) 241 { 242 this->_M_detach_singular(); 243 244 // if __sz < size(), invalidate all iterators in [begin+__sz, end()) 245 _Base_iterator __victim = _Base::begin(); 246 _Base_iterator __end = _Base::end(); 247 for (size_type __i = __sz; __victim != __end && __i > 0; --__i) 248 ++__victim; 249 250 for (; __victim != __end; ++__victim) 251 { 252 this->_M_invalidate_if(_Equal(__victim)); 253 } 254 255 __try 256 { 257 _Base::resize(__sz); 258 } 259 __catch(...) 260 { 261 this->_M_revalidate_singular(); 262 __throw_exception_again; 263 } 264 } 265 266 void 267 resize(size_type __sz, const _Tp& __c) 268 { 269 this->_M_detach_singular(); 270 271 // if __sz < size(), invalidate all iterators in [begin+__sz, end()) 272 _Base_iterator __victim = _Base::begin(); 273 _Base_iterator __end = _Base::end(); 274 for (size_type __i = __sz; __victim != __end && __i > 0; --__i) 275 ++__victim; 276 277 for (; __victim != __end; ++__victim) 278 { 279 this->_M_invalidate_if(_Equal(__victim)); 280 } 281 282 __try 283 { 284 _Base::resize(__sz, __c); 285 } 286 __catch(...) 287 { 288 this->_M_revalidate_singular(); 289 __throw_exception_again; 290 } 291 } 292 #else 293 void 294 resize(size_type __sz, _Tp __c = _Tp()) 295 { 296 this->_M_detach_singular(); 297 298 // if __sz < size(), invalidate all iterators in [begin+__sz, end()) 299 _Base_iterator __victim = _Base::begin(); 300 _Base_iterator __end = _Base::end(); 301 for (size_type __i = __sz; __victim != __end && __i > 0; --__i) 302 ++__victim; 303 304 for (; __victim != __end; ++__victim) 305 { 306 this->_M_invalidate_if(_Equal(__victim)); 307 } 308 309 __try 310 { 311 _Base::resize(__sz, __c); 312 } 313 __catch(...) 314 { 315 this->_M_revalidate_singular(); 316 __throw_exception_again; 317 } 318 } 319 #endif 320 321 // element access: 322 reference 323 front() 324 { 325 __glibcxx_check_nonempty(); 326 return _Base::front(); 327 } 328 329 const_reference 330 front() const 331 { 332 __glibcxx_check_nonempty(); 333 return _Base::front(); 334 } 335 336 reference 337 back() 338 { 339 __glibcxx_check_nonempty(); 340 return _Base::back(); 341 } 342 343 const_reference 344 back() const 345 { 346 __glibcxx_check_nonempty(); 347 return _Base::back(); 348 } 349 350 // 23.2.2.3 modifiers: 351 using _Base::push_front; 352 353 #if __cplusplus >= 201103L 354 using _Base::emplace_front; 355 #endif 356 357 void 358 pop_front() 359 { 360 __glibcxx_check_nonempty(); 361 this->_M_invalidate_if(_Equal(_Base::begin())); 362 _Base::pop_front(); 363 } 364 365 using _Base::push_back; 366 367 #if __cplusplus >= 201103L 368 using _Base::emplace_back; 369 #endif 370 371 void 372 pop_back() 373 { 374 __glibcxx_check_nonempty(); 375 this->_M_invalidate_if(_Equal(--_Base::end())); 376 _Base::pop_back(); 377 } 378 379 #if __cplusplus >= 201103L 380 template<typename... _Args> 381 iterator 382 emplace(iterator __position, _Args&&... __args) 383 { 384 __glibcxx_check_insert(__position); 385 return iterator(_Base::emplace(__position.base(), 386 std::forward<_Args>(__args)...), this); 387 } 388 #endif 389 390 iterator 391 insert(iterator __position, const _Tp& __x) 392 { 393 __glibcxx_check_insert(__position); 394 return iterator(_Base::insert(__position.base(), __x), this); 395 } 396 397 #if __cplusplus >= 201103L 398 iterator 399 insert(iterator __position, _Tp&& __x) 400 { return emplace(__position, std::move(__x)); } 401 402 void 403 insert(iterator __p, initializer_list<value_type> __l) 404 { 405 __glibcxx_check_insert(__p); 406 _Base::insert(__p.base(), __l); 407 } 408 #endif 409 410 void 411 insert(iterator __position, size_type __n, const _Tp& __x) 412 { 413 __glibcxx_check_insert(__position); 414 _Base::insert(__position.base(), __n, __x); 415 } 416 417 #if __cplusplus >= 201103L 418 template<class _InputIterator, 419 typename = std::_RequireInputIter<_InputIterator>> 420 #else 421 template<class _InputIterator> 422 #endif 423 void 424 insert(iterator __position, _InputIterator __first, 425 _InputIterator __last) 426 { 427 __glibcxx_check_insert_range(__position, __first, __last); 428 _Base::insert(__position.base(), __gnu_debug::__base(__first), 429 __gnu_debug::__base(__last)); 430 } 431 432 private: 433 _Base_iterator 434 _M_erase(_Base_iterator __position) 435 { 436 this->_M_invalidate_if(_Equal(__position)); 437 return _Base::erase(__position); 438 } 439 public: 440 iterator 441 erase(iterator __position) 442 { 443 __glibcxx_check_erase(__position); 444 return iterator(_M_erase(__position.base()), this); 445 } 446 447 iterator 448 erase(iterator __position, iterator __last) 449 { 450 // _GLIBCXX_RESOLVE_LIB_DEFECTS 451 // 151. can't currently clear() empty container 452 __glibcxx_check_erase_range(__position, __last); 453 for (_Base_iterator __victim = __position.base(); 454 __victim != __last.base(); ++__victim) 455 { 456 _GLIBCXX_DEBUG_VERIFY(__victim != _Base::end(), 457 _M_message(__gnu_debug::__msg_valid_range) 458 ._M_iterator(__position, "position") 459 ._M_iterator(__last, "last")); 460 this->_M_invalidate_if(_Equal(__victim)); 461 } 462 return iterator(_Base::erase(__position.base(), __last.base()), this); 463 } 464 465 void 466 swap(list& __x) 467 { 468 _Base::swap(__x); 469 this->_M_swap(__x); 470 } 471 472 void 473 clear() _GLIBCXX_NOEXCEPT 474 { 475 _Base::clear(); 476 this->_M_invalidate_all(); 477 } 478 479 // 23.2.2.4 list operations: 480 void 481 #if __cplusplus >= 201103L 482 splice(iterator __position, list&& __x) 483 #else 484 splice(iterator __position, list& __x) 485 #endif 486 { 487 _GLIBCXX_DEBUG_VERIFY(&__x != this, 488 _M_message(__gnu_debug::__msg_self_splice) 489 ._M_sequence(*this, "this")); 490 this->_M_transfer_from_if(__x, _Not_equal(__x._M_base().end())); 491 _Base::splice(__position.base(), _GLIBCXX_MOVE(__x._M_base())); 492 } 493 494 #if __cplusplus >= 201103L 495 void 496 splice(iterator __position, list& __x) 497 { splice(__position, std::move(__x)); } 498 #endif 499 500 void 501 #if __cplusplus >= 201103L 502 splice(iterator __position, list&& __x, iterator __i) 503 #else 504 splice(iterator __position, list& __x, iterator __i) 505 #endif 506 { 507 __glibcxx_check_insert(__position); 508 509 // We used to perform the splice_alloc check: not anymore, redundant 510 // after implementing the relevant bits of N1599. 511 512 _GLIBCXX_DEBUG_VERIFY(__i._M_dereferenceable(), 513 _M_message(__gnu_debug::__msg_splice_bad) 514 ._M_iterator(__i, "__i")); 515 _GLIBCXX_DEBUG_VERIFY(__i._M_attached_to(&__x), 516 _M_message(__gnu_debug::__msg_splice_other) 517 ._M_iterator(__i, "__i")._M_sequence(__x, "__x")); 518 519 // _GLIBCXX_RESOLVE_LIB_DEFECTS 520 // 250. splicing invalidates iterators 521 this->_M_transfer_from_if(__x, _Equal(__i.base())); 522 _Base::splice(__position.base(), _GLIBCXX_MOVE(__x._M_base()), 523 __i.base()); 524 } 525 526 #if __cplusplus >= 201103L 527 void 528 splice(iterator __position, list& __x, iterator __i) 529 { splice(__position, std::move(__x), __i); } 530 #endif 531 532 void 533 #if __cplusplus >= 201103L 534 splice(iterator __position, list&& __x, iterator __first, 535 iterator __last) 536 #else 537 splice(iterator __position, list& __x, iterator __first, 538 iterator __last) 539 #endif 540 { 541 __glibcxx_check_insert(__position); 542 __glibcxx_check_valid_range(__first, __last); 543 _GLIBCXX_DEBUG_VERIFY(__first._M_attached_to(&__x), 544 _M_message(__gnu_debug::__msg_splice_other) 545 ._M_sequence(__x, "x") 546 ._M_iterator(__first, "first")); 547 548 // We used to perform the splice_alloc check: not anymore, redundant 549 // after implementing the relevant bits of N1599. 550 551 for (_Base_iterator __tmp = __first.base(); 552 __tmp != __last.base(); ++__tmp) 553 { 554 _GLIBCXX_DEBUG_VERIFY(__tmp != _Base::end(), 555 _M_message(__gnu_debug::__msg_valid_range) 556 ._M_iterator(__first, "first") 557 ._M_iterator(__last, "last")); 558 _GLIBCXX_DEBUG_VERIFY(&__x != this || __tmp != __position, 559 _M_message(__gnu_debug::__msg_splice_overlap) 560 ._M_iterator(__tmp, "position") 561 ._M_iterator(__first, "first") 562 ._M_iterator(__last, "last")); 563 // _GLIBCXX_RESOLVE_LIB_DEFECTS 564 // 250. splicing invalidates iterators 565 this->_M_transfer_from_if(__x, _Equal(__tmp)); 566 } 567 568 _Base::splice(__position.base(), _GLIBCXX_MOVE(__x._M_base()), 569 __first.base(), __last.base()); 570 } 571 572 #if __cplusplus >= 201103L 573 void 574 splice(iterator __position, list& __x, iterator __first, iterator __last) 575 { splice(__position, std::move(__x), __first, __last); } 576 #endif 577 578 void 579 remove(const _Tp& __value) 580 { 581 for (_Base_iterator __x = _Base::begin(); __x != _Base::end(); ) 582 { 583 if (*__x == __value) 584 __x = _M_erase(__x); 585 else 586 ++__x; 587 } 588 } 589 590 template<class _Predicate> 591 void 592 remove_if(_Predicate __pred) 593 { 594 for (_Base_iterator __x = _Base::begin(); __x != _Base::end(); ) 595 { 596 if (__pred(*__x)) 597 __x = _M_erase(__x); 598 else 599 ++__x; 600 } 601 } 602 603 void 604 unique() 605 { 606 _Base_iterator __first = _Base::begin(); 607 _Base_iterator __last = _Base::end(); 608 if (__first == __last) 609 return; 610 _Base_iterator __next = __first; ++__next; 611 while (__next != __last) 612 { 613 if (*__first == *__next) 614 __next = _M_erase(__next); 615 else 616 __first = __next++; 617 } 618 } 619 620 template<class _BinaryPredicate> 621 void 622 unique(_BinaryPredicate __binary_pred) 623 { 624 _Base_iterator __first = _Base::begin(); 625 _Base_iterator __last = _Base::end(); 626 if (__first == __last) 627 return; 628 _Base_iterator __next = __first; ++__next; 629 while (__next != __last) 630 { 631 if (__binary_pred(*__first, *__next)) 632 __next = _M_erase(__next); 633 else 634 __first = __next++; 635 } 636 } 637 638 void 639 #if __cplusplus >= 201103L 640 merge(list&& __x) 641 #else 642 merge(list& __x) 643 #endif 644 { 645 // _GLIBCXX_RESOLVE_LIB_DEFECTS 646 // 300. list::merge() specification incomplete 647 if (this != &__x) 648 { 649 __glibcxx_check_sorted(_Base::begin(), _Base::end()); 650 __glibcxx_check_sorted(__x.begin().base(), __x.end().base()); 651 this->_M_transfer_from_if(__x, _Not_equal(__x._M_base().end())); 652 _Base::merge(_GLIBCXX_MOVE(__x._M_base())); 653 } 654 } 655 656 #if __cplusplus >= 201103L 657 void 658 merge(list& __x) 659 { merge(std::move(__x)); } 660 #endif 661 662 template<class _Compare> 663 void 664 #if __cplusplus >= 201103L 665 merge(list&& __x, _Compare __comp) 666 #else 667 merge(list& __x, _Compare __comp) 668 #endif 669 { 670 // _GLIBCXX_RESOLVE_LIB_DEFECTS 671 // 300. list::merge() specification incomplete 672 if (this != &__x) 673 { 674 __glibcxx_check_sorted_pred(_Base::begin(), _Base::end(), 675 __comp); 676 __glibcxx_check_sorted_pred(__x.begin().base(), __x.end().base(), 677 __comp); 678 this->_M_transfer_from_if(__x, _Not_equal(__x._M_base().end())); 679 _Base::merge(_GLIBCXX_MOVE(__x._M_base()), __comp); 680 } 681 } 682 683 #if __cplusplus >= 201103L 684 template<typename _Compare> 685 void 686 merge(list& __x, _Compare __comp) 687 { merge(std::move(__x), __comp); } 688 #endif 689 690 void 691 sort() { _Base::sort(); } 692 693 template<typename _StrictWeakOrdering> 694 void 695 sort(_StrictWeakOrdering __pred) { _Base::sort(__pred); } 696 697 using _Base::reverse; 698 699 _Base& 700 _M_base() _GLIBCXX_NOEXCEPT { return *this; } 701 702 const _Base& 703 _M_base() const _GLIBCXX_NOEXCEPT { return *this; } 704 705 private: 706 void 707 _M_invalidate_all() 708 { 709 this->_M_invalidate_if(_Not_equal(_Base::end())); 710 } 711 }; 712 713 template<typename _Tp, typename _Alloc> 714 inline bool 715 operator==(const list<_Tp, _Alloc>& __lhs, 716 const list<_Tp, _Alloc>& __rhs) 717 { return __lhs._M_base() == __rhs._M_base(); } 718 719 template<typename _Tp, typename _Alloc> 720 inline bool 721 operator!=(const list<_Tp, _Alloc>& __lhs, 722 const list<_Tp, _Alloc>& __rhs) 723 { return __lhs._M_base() != __rhs._M_base(); } 724 725 template<typename _Tp, typename _Alloc> 726 inline bool 727 operator<(const list<_Tp, _Alloc>& __lhs, 728 const list<_Tp, _Alloc>& __rhs) 729 { return __lhs._M_base() < __rhs._M_base(); } 730 731 template<typename _Tp, typename _Alloc> 732 inline bool 733 operator<=(const list<_Tp, _Alloc>& __lhs, 734 const list<_Tp, _Alloc>& __rhs) 735 { return __lhs._M_base() <= __rhs._M_base(); } 736 737 template<typename _Tp, typename _Alloc> 738 inline bool 739 operator>=(const list<_Tp, _Alloc>& __lhs, 740 const list<_Tp, _Alloc>& __rhs) 741 { return __lhs._M_base() >= __rhs._M_base(); } 742 743 template<typename _Tp, typename _Alloc> 744 inline bool 745 operator>(const list<_Tp, _Alloc>& __lhs, 746 const list<_Tp, _Alloc>& __rhs) 747 { return __lhs._M_base() > __rhs._M_base(); } 748 749 template<typename _Tp, typename _Alloc> 750 inline void 751 swap(list<_Tp, _Alloc>& __lhs, list<_Tp, _Alloc>& __rhs) 752 { __lhs.swap(__rhs); } 753 754 } // namespace __debug 755 } // namespace std 756 757 #endif 758
