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