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