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