1// <forward_list> -*- C++ -*- 2 3// Copyright (C) 2010-2022 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 <bits/c++config.h> 35namespace std _GLIBCXX_VISIBILITY(default) { namespace __debug { 36 template<typename _Tp, typename _Allocator> class forward_list; 37} } // namespace std::__debug 38 39#include <forward_list> 40#include <debug/safe_sequence.h> 41#include <debug/safe_container.h> 42#include <debug/safe_iterator.h> 43 44// Special validity check for forward_list ranges. 45#define __glibcxx_check_valid_fl_range(_First,_Last,_Dist) \ 46_GLIBCXX_DEBUG_VERIFY(_First._M_valid_range(_Last, _Dist, false), \ 47 _M_message(__gnu_debug::__msg_valid_range) \ 48 ._M_iterator(_First, #_First) \ 49 ._M_iterator(_Last, #_Last)) 50 51namespace __gnu_debug 52{ 53 /// Special iterators swap and invalidation for forward_list because of the 54 /// before_begin iterator. 55 template<typename _SafeSequence> 56 class _Safe_forward_list 57 : public _Safe_sequence<_SafeSequence> 58 { 59 _SafeSequence& 60 _M_this() noexcept 61 { return *static_cast<_SafeSequence*>(this); } 62 63 static void 64 _M_swap_aux(_Safe_sequence_base& __lhs, 65 _Safe_iterator_base*& __lhs_iterators, 66 _Safe_sequence_base& __rhs, 67 _Safe_iterator_base*& __rhs_iterators); 68 69 void _M_swap_single(_Safe_sequence_base&) noexcept; 70 71 protected: 72 void 73 _M_invalidate_all() 74 { 75 using _Base_const_iterator = __decltype(_M_this()._M_base().cend()); 76 this->_M_invalidate_if([this](_Base_const_iterator __it) 77 { 78 return __it != _M_this()._M_base().cbefore_begin() 79 && __it != _M_this()._M_base().cend(); }); 80 } 81 82 void _M_swap(_Safe_sequence_base&) noexcept; 83 }; 84 85 template<typename _SafeSequence> 86 void 87 _Safe_forward_list<_SafeSequence>:: 88 _M_swap_aux(_Safe_sequence_base& __lhs, 89 _Safe_iterator_base*& __lhs_iterators, 90 _Safe_sequence_base& __rhs, 91 _Safe_iterator_base*& __rhs_iterators) 92 { 93 using const_iterator = typename _SafeSequence::const_iterator; 94 _Safe_iterator_base* __bbegin_its = 0; 95 _Safe_iterator_base* __last_bbegin = 0; 96 _SafeSequence& __rseq = static_cast<_SafeSequence&>(__rhs); 97 98 for (_Safe_iterator_base* __iter = __lhs_iterators; __iter;) 99 { 100 // Even iterator is cast to const_iterator, not a problem. 101 _Safe_iterator_base* __victim_base = __iter; 102 const_iterator* __victim = 103 static_cast<const_iterator*>(__victim_base); 104 __iter = __iter->_M_next; 105 if (__victim->base() == __rseq._M_base().cbefore_begin()) 106 { 107 __victim->_M_unlink(); 108 if (__lhs_iterators == __victim_base) 109 __lhs_iterators = __victim_base->_M_next; 110 if (__bbegin_its) 111 { 112 __victim_base->_M_next = __bbegin_its; 113 __bbegin_its->_M_prior = __victim_base; 114 } 115 else 116 __last_bbegin = __victim_base; 117 __bbegin_its = __victim_base; 118 } 119 else 120 __victim_base->_M_sequence = std::__addressof(__lhs); 121 } 122 123 if (__bbegin_its) 124 { 125 if (__rhs_iterators) 126 { 127 __rhs_iterators->_M_prior = __last_bbegin; 128 __last_bbegin->_M_next = __rhs_iterators; 129 } 130 __rhs_iterators = __bbegin_its; 131 } 132 } 133 134 template<typename _SafeSequence> 135 void 136 _Safe_forward_list<_SafeSequence>:: 137 _M_swap_single(_Safe_sequence_base& __other) noexcept 138 { 139 std::swap(_M_this()._M_iterators, __other._M_iterators); 140 std::swap(_M_this()._M_const_iterators, __other._M_const_iterators); 141 // Useless, always 1 on forward_list 142 //std::swap(_M_this()_M_version, __other._M_version); 143 _Safe_iterator_base* __this_its = _M_this()._M_iterators; 144 _M_swap_aux(__other, __other._M_iterators, 145 _M_this(), _M_this()._M_iterators); 146 _Safe_iterator_base* __this_const_its = _M_this()._M_const_iterators; 147 _M_swap_aux(__other, __other._M_const_iterators, 148 _M_this(), _M_this()._M_const_iterators); 149 _M_swap_aux(_M_this(), __this_its, 150 __other, __other._M_iterators); 151 _M_swap_aux(_M_this(), __this_const_its, 152 __other, __other._M_const_iterators); 153 } 154 155 /* Special forward_list _M_swap version that does not swap the 156 * before-begin ownership.*/ 157 template<typename _SafeSequence> 158 void 159 _Safe_forward_list<_SafeSequence>:: 160 _M_swap(_Safe_sequence_base& __other) noexcept 161 { 162 // We need to lock both sequences to swap 163 using namespace __gnu_cxx; 164 __mutex *__this_mutex = &_M_this()._M_get_mutex(); 165 __mutex *__other_mutex = 166 &static_cast<_SafeSequence&>(__other)._M_get_mutex(); 167 if (__this_mutex == __other_mutex) 168 { 169 __scoped_lock __lock(*__this_mutex); 170 _M_swap_single(__other); 171 } 172 else 173 { 174 __scoped_lock __l1(__this_mutex < __other_mutex 175 ? *__this_mutex : *__other_mutex); 176 __scoped_lock __l2(__this_mutex < __other_mutex 177 ? *__other_mutex : *__this_mutex); 178 _M_swap_single(__other); 179 } 180 } 181} 182 183namespace std _GLIBCXX_VISIBILITY(default) 184{ 185namespace __debug 186{ 187 /// Class std::forward_list with safety/checking/debug instrumentation. 188 template<typename _Tp, typename _Alloc = std::allocator<_Tp> > 189 class forward_list 190 : public __gnu_debug::_Safe_container< 191 forward_list<_Tp, _Alloc>, _Alloc, __gnu_debug::_Safe_forward_list>, 192 public _GLIBCXX_STD_C::forward_list<_Tp, _Alloc> 193 { 194 typedef _GLIBCXX_STD_C::forward_list<_Tp, _Alloc> _Base; 195 typedef __gnu_debug::_Safe_container< 196 forward_list, _Alloc, __gnu_debug::_Safe_forward_list> _Safe; 197 198 typedef typename _Base::iterator _Base_iterator; 199 typedef typename _Base::const_iterator _Base_const_iterator; 200 201 template<typename _ItT, typename _SeqT, typename _CatT> 202 friend class ::__gnu_debug::_Safe_iterator; 203 204 // Reference wrapper for base class. See PR libstdc++/90102. 205 struct _Base_ref 206 { 207 _Base_ref(const _Base& __r) : _M_ref(__r) { } 208 209 const _Base& _M_ref; 210 }; 211 212 public: 213 typedef typename _Base::reference reference; 214 typedef typename _Base::const_reference const_reference; 215 216 typedef __gnu_debug::_Safe_iterator< 217 _Base_iterator, forward_list> iterator; 218 typedef __gnu_debug::_Safe_iterator< 219 _Base_const_iterator, forward_list> const_iterator; 220 221 typedef typename _Base::size_type size_type; 222 typedef typename _Base::difference_type difference_type; 223 224 typedef _Tp value_type; 225 typedef typename _Base::allocator_type allocator_type; 226 typedef typename _Base::pointer pointer; 227 typedef typename _Base::const_pointer const_pointer; 228 229 // 23.2.3.1 construct/copy/destroy: 230 231 forward_list() = default; 232 233 explicit 234 forward_list(const allocator_type& __al) noexcept 235 : _Base(__al) { } 236 237 forward_list(const forward_list& __list, const allocator_type& __al) 238 : _Base(__list, __al) 239 { } 240 241 forward_list(forward_list&& __list, const allocator_type& __al) 242 noexcept( 243 std::is_nothrow_constructible<_Base, 244 _Base, const allocator_type&>::value ) 245 : _Safe(std::move(__list), __al), 246 _Base(std::move(__list), __al) 247 { } 248 249 explicit 250 forward_list(size_type __n, const allocator_type& __al = allocator_type()) 251 : _Base(__n, __al) 252 { } 253 254 forward_list(size_type __n, const __type_identity_t<_Tp>& __value, 255 const allocator_type& __al = allocator_type()) 256 : _Base(__n, __value, __al) 257 { } 258 259 template<typename _InputIterator, 260 typename = std::_RequireInputIter<_InputIterator>> 261 forward_list(_InputIterator __first, _InputIterator __last, 262 const allocator_type& __al = allocator_type()) 263 : _Base(__gnu_debug::__base( 264 __glibcxx_check_valid_constructor_range(__first, __last)), 265 __gnu_debug::__base(__last), __al) 266 { } 267 268 forward_list(const forward_list&) = default; 269 270 forward_list(forward_list&&) = default; 271 272 forward_list(std::initializer_list<_Tp> __il, 273 const allocator_type& __al = allocator_type()) 274 : _Base(__il, __al) 275 { } 276 277 ~forward_list() = default; 278 279 forward_list(_Base_ref __x) : _Base(__x._M_ref) { } 280 281 forward_list& 282 operator=(const forward_list&) = default; 283 284 forward_list& 285 operator=(forward_list&&) = default; 286 287 forward_list& 288 operator=(std::initializer_list<_Tp> __il) 289 { 290 _Base::operator=(__il); 291 this->_M_invalidate_all(); 292 return *this; 293 } 294 295 template<typename _InputIterator, 296 typename = std::_RequireInputIter<_InputIterator>> 297 void 298 assign(_InputIterator __first, _InputIterator __last) 299 { 300 typename __gnu_debug::_Distance_traits<_InputIterator>::__type __dist; 301 __glibcxx_check_valid_range2(__first, __last, __dist); 302 303 if (__dist.second >= __gnu_debug::__dp_sign) 304 _Base::assign(__gnu_debug::__unsafe(__first), 305 __gnu_debug::__unsafe(__last)); 306 else 307 _Base::assign(__first, __last); 308 309 this->_M_invalidate_all(); 310 } 311 312 void 313 assign(size_type __n, const _Tp& __val) 314 { 315 _Base::assign(__n, __val); 316 this->_M_invalidate_all(); 317 } 318 319 void 320 assign(std::initializer_list<_Tp> __il) 321 { 322 _Base::assign(__il); 323 this->_M_invalidate_all(); 324 } 325 326 using _Base::get_allocator; 327 328 // iterators: 329 330 [[__nodiscard__]] 331 iterator 332 before_begin() noexcept 333 { return { _Base::before_begin(), this }; } 334 335 [[__nodiscard__]] 336 const_iterator 337 before_begin() const noexcept 338 { return { _Base::before_begin(), this }; } 339 340 [[__nodiscard__]] 341 iterator 342 begin() noexcept 343 { return { _Base::begin(), this }; } 344 345 [[__nodiscard__]] 346 const_iterator 347 begin() const noexcept 348 { return { _Base::begin(), this }; } 349 350 [[__nodiscard__]] 351 iterator 352 end() noexcept 353 { return { _Base::end(), this }; } 354 355 [[__nodiscard__]] 356 const_iterator 357 end() const noexcept 358 { return { _Base::end(), this }; } 359 360 [[__nodiscard__]] 361 const_iterator 362 cbegin() const noexcept 363 { return { _Base::cbegin(), this }; } 364 365 [[__nodiscard__]] 366 const_iterator 367 cbefore_begin() const noexcept 368 { return { _Base::cbefore_begin(), this }; } 369 370 [[__nodiscard__]] 371 const_iterator 372 cend() const noexcept 373 { return { _Base::cend(), this }; } 374 375 using _Base::empty; 376 using _Base::max_size; 377 378 // element access: 379 380 [[__nodiscard__]] 381 reference 382 front() 383 { 384 __glibcxx_check_nonempty(); 385 return _Base::front(); 386 } 387 388 [[__nodiscard__]] 389 const_reference 390 front() const 391 { 392 __glibcxx_check_nonempty(); 393 return _Base::front(); 394 } 395 396 // modifiers: 397 398 using _Base::emplace_front; 399 using _Base::push_front; 400 401 void 402 pop_front() 403 { 404 __glibcxx_check_nonempty(); 405 this->_M_invalidate_if([this](_Base_const_iterator __it) 406 { return __it == this->_M_base().cbegin(); }); 407 _Base::pop_front(); 408 } 409 410 template<typename... _Args> 411 iterator 412 emplace_after(const_iterator __pos, _Args&&... __args) 413 { 414 __glibcxx_check_insert_after(__pos); 415 return { _Base::emplace_after(__pos.base(), 416 std::forward<_Args>(__args)...), 417 this }; 418 } 419 420 iterator 421 insert_after(const_iterator __pos, const _Tp& __val) 422 { 423 __glibcxx_check_insert_after(__pos); 424 return { _Base::insert_after(__pos.base(), __val), this }; 425 } 426 427 iterator 428 insert_after(const_iterator __pos, _Tp&& __val) 429 { 430 __glibcxx_check_insert_after(__pos); 431 return { _Base::insert_after(__pos.base(), std::move(__val)), this }; 432 } 433 434 iterator 435 insert_after(const_iterator __pos, size_type __n, const _Tp& __val) 436 { 437 __glibcxx_check_insert_after(__pos); 438 return { _Base::insert_after(__pos.base(), __n, __val), this }; 439 } 440 441 template<typename _InputIterator, 442 typename = std::_RequireInputIter<_InputIterator>> 443 iterator 444 insert_after(const_iterator __pos, 445 _InputIterator __first, _InputIterator __last) 446 { 447 typename __gnu_debug::_Distance_traits<_InputIterator>::__type __dist; 448 __glibcxx_check_insert_range_after(__pos, __first, __last, __dist); 449 450 if (__dist.second >= __gnu_debug::__dp_sign) 451 return 452 { 453 _Base::insert_after(__pos.base(), 454 __gnu_debug::__unsafe(__first), 455 __gnu_debug::__unsafe(__last)), 456 this 457 }; 458 else 459 return { _Base::insert_after(__pos.base(), __first, __last), this }; 460 } 461 462 iterator 463 insert_after(const_iterator __pos, std::initializer_list<_Tp> __il) 464 { 465 __glibcxx_check_insert_after(__pos); 466 return { _Base::insert_after(__pos.base(), __il), this }; 467 } 468 469 iterator 470 erase_after(const_iterator __pos) 471 { 472 __glibcxx_check_erase_after(__pos); 473 474 _Base_const_iterator __next = std::next(__pos.base()); 475 this->_M_invalidate_if([__next](_Base_const_iterator __it) 476 { return __it == __next; }); 477 return { _Base::erase_after(__pos.base()), this }; 478 } 479 480 iterator 481 erase_after(const_iterator __pos, const_iterator __last) 482 { 483 __glibcxx_check_erase_range_after(__pos, __last); 484 for (_Base_const_iterator __victim = std::next(__pos.base()); 485 __victim != __last.base(); ++__victim) 486 { 487 _GLIBCXX_DEBUG_VERIFY(__victim != _Base::cend(), 488 _M_message(__gnu_debug::__msg_valid_range2) 489 ._M_sequence(*this, "this") 490 ._M_iterator(__pos, "pos") 491 ._M_iterator(__last, "last")); 492 this->_M_invalidate_if([__victim](_Base_const_iterator __it) 493 { return __it == __victim; }); 494 } 495 496 return { _Base::erase_after(__pos.base(), __last.base()), this }; 497 } 498 499 void 500 swap(forward_list& __list) 501 noexcept( noexcept(declval<_Base&>().swap(__list)) ) 502 { 503 _Safe::_M_swap(__list); 504 _Base::swap(__list); 505 } 506 507 void 508 resize(size_type __sz) 509 { 510 this->_M_detach_singular(); 511 512 // if __sz < size(), invalidate all iterators in [begin+__sz, end() 513 _Base_iterator __victim = _Base::begin(); 514 _Base_iterator __end = _Base::end(); 515 for (size_type __i = __sz; __victim != __end && __i > 0; --__i) 516 ++__victim; 517 518 for (; __victim != __end; ++__victim) 519 { 520 this->_M_invalidate_if([__victim](_Base_const_iterator __it) 521 { return __it == __victim; }); 522 } 523 524 __try 525 { 526 _Base::resize(__sz); 527 } 528 __catch(...) 529 { 530 this->_M_revalidate_singular(); 531 __throw_exception_again; 532 } 533 } 534 535 void 536 resize(size_type __sz, const value_type& __val) 537 { 538 this->_M_detach_singular(); 539 540 // if __sz < size(), invalidate all iterators in [begin+__sz, end()) 541 _Base_iterator __victim = _Base::begin(); 542 _Base_iterator __end = _Base::end(); 543 for (size_type __i = __sz; __victim != __end && __i > 0; --__i) 544 ++__victim; 545 546 for (; __victim != __end; ++__victim) 547 { 548 this->_M_invalidate_if([__victim](_Base_const_iterator __it) 549 { return __it == __victim; }); 550 } 551 552 __try 553 { 554 _Base::resize(__sz, __val); 555 } 556 __catch(...) 557 { 558 this->_M_revalidate_singular(); 559 __throw_exception_again; 560 } 561 } 562 563 void 564 clear() noexcept 565 { 566 _Base::clear(); 567 this->_M_invalidate_all(); 568 } 569 570 // 23.2.3.5 forward_list operations: 571 void 572 splice_after(const_iterator __pos, forward_list&& __list) 573 { 574 __glibcxx_check_insert_after(__pos); 575 _GLIBCXX_DEBUG_VERIFY(std::__addressof(__list) != this, 576 _M_message(__gnu_debug::__msg_self_splice) 577 ._M_sequence(*this, "this")); 578 _GLIBCXX_DEBUG_VERIFY(__list.get_allocator() == this->get_allocator(), 579 _M_message(__gnu_debug::__msg_splice_alloc) 580 ._M_sequence(*this) 581 ._M_sequence(__list, "__list")); 582 this->_M_transfer_from_if(__list, [&__list](_Base_const_iterator __it) 583 { 584 return __it != __list._M_base().cbefore_begin() 585 && __it != __list._M_base().end(); 586 }); 587 _Base::splice_after(__pos.base(), std::move(__list)); 588 } 589 590 void 591 splice_after(const_iterator __pos, forward_list& __list) 592 { splice_after(__pos, std::move(__list)); } 593 594 void 595 splice_after(const_iterator __pos, forward_list&& __list, 596 const_iterator __i) 597 { 598 __glibcxx_check_insert_after(__pos); 599 _GLIBCXX_DEBUG_VERIFY(__i._M_before_dereferenceable(), 600 _M_message(__gnu_debug::__msg_splice_bad) 601 ._M_iterator(__i, "__i")); 602 _GLIBCXX_DEBUG_VERIFY(__i._M_attached_to(std::__addressof(__list)), 603 _M_message(__gnu_debug::__msg_splice_other) 604 ._M_iterator(__i, "__i") 605 ._M_sequence(__list, "__list")); 606 _GLIBCXX_DEBUG_VERIFY(__list.get_allocator() == this->get_allocator(), 607 _M_message(__gnu_debug::__msg_splice_alloc) 608 ._M_sequence(*this) 609 ._M_sequence(__list, "__list")); 610 611 // _GLIBCXX_RESOLVE_LIB_DEFECTS 612 // 250. splicing invalidates iterators 613 _Base_const_iterator __next = std::next(__i.base()); 614 this->_M_transfer_from_if(__list, [__next](_Base_const_iterator __it) 615 { return __it == __next; }); 616 _Base::splice_after(__pos.base(), std::move(__list), __i.base()); 617 } 618 619 void 620 splice_after(const_iterator __pos, forward_list& __list, 621 const_iterator __i) 622 { splice_after(__pos, std::move(__list), __i); } 623 624 void 625 splice_after(const_iterator __pos, forward_list&& __list, 626 const_iterator __before, const_iterator __last) 627 { 628 typename __gnu_debug::_Distance_traits<const_iterator>::__type __dist; 629 auto __listptr = std::__addressof(__list); 630 __glibcxx_check_insert_after(__pos); 631 __glibcxx_check_valid_fl_range(__before, __last, __dist); 632 _GLIBCXX_DEBUG_VERIFY(__before._M_attached_to(__listptr), 633 _M_message(__gnu_debug::__msg_splice_other) 634 ._M_sequence(__list, "list") 635 ._M_iterator(__before, "before")); 636 _GLIBCXX_DEBUG_VERIFY(__before._M_dereferenceable() 637 || __before._M_is_before_begin(), 638 _M_message(__gnu_debug::__msg_valid_range2) 639 ._M_sequence(__list, "list") 640 ._M_iterator(__before, "before") 641 ._M_iterator(__last, "last")); 642 _GLIBCXX_DEBUG_VERIFY(__before != __last, 643 _M_message(__gnu_debug::__msg_valid_range2) 644 ._M_sequence(__list, "list") 645 ._M_iterator(__before, "before") 646 ._M_iterator(__last, "last")); 647 _GLIBCXX_DEBUG_VERIFY(__list.get_allocator() == this->get_allocator(), 648 _M_message(__gnu_debug::__msg_splice_alloc) 649 ._M_sequence(*this) 650 ._M_sequence(__list, "__list")); 651 652 for (_Base_const_iterator __tmp = std::next(__before.base()); 653 __tmp != __last.base(); ++__tmp) 654 { 655 _GLIBCXX_DEBUG_VERIFY(__tmp != __list._M_base().end(), 656 _M_message(__gnu_debug::__msg_valid_range2) 657 ._M_sequence(__list, "list") 658 ._M_iterator(__before, "before") 659 ._M_iterator(__last, "last")); 660 _GLIBCXX_DEBUG_VERIFY(__listptr != this || __tmp != __pos.base(), 661 _M_message(__gnu_debug::__msg_splice_overlap) 662 ._M_iterator(__tmp, "position") 663 ._M_iterator(__before, "before") 664 ._M_iterator(__last, "last")); 665 // _GLIBCXX_RESOLVE_LIB_DEFECTS 666 // 250. splicing invalidates iterators 667 this->_M_transfer_from_if(__list, [__tmp](_Base_const_iterator __it) 668 { return __it == __tmp; }); 669 } 670 671 _Base::splice_after(__pos.base(), std::move(__list), 672 __before.base(), __last.base()); 673 } 674 675 void 676 splice_after(const_iterator __pos, forward_list& __list, 677 const_iterator __before, const_iterator __last) 678 { splice_after(__pos, std::move(__list), __before, __last); } 679 680 private: 681#if __cplusplus > 201703L 682 using __remove_return_type = size_type; 683# define _GLIBCXX_FWDLIST_REMOVE_RETURN_TYPE_TAG \ 684 __attribute__((__abi_tag__("__cxx20"))) 685# define _GLIBCXX20_ONLY(__expr) __expr 686#else 687 using __remove_return_type = void; 688# define _GLIBCXX_FWDLIST_REMOVE_RETURN_TYPE_TAG 689# define _GLIBCXX20_ONLY(__expr) 690#endif 691 692 public: 693 _GLIBCXX_FWDLIST_REMOVE_RETURN_TYPE_TAG 694 __remove_return_type 695 remove(const _Tp& __val) 696 { 697 if (!this->_M_iterators && !this->_M_const_iterators) 698 return _Base::remove(__val); 699 700 size_type __removed __attribute__((__unused__)) = 0; 701 _Base __to_destroy(get_allocator()); 702 _Base_const_iterator __x = _Base::cbefore_begin(); 703 _Base_const_iterator __old = __x++; 704 while (__x != _Base::cend()) 705 { 706 if (*__x == __val) 707 { 708 _Base_const_iterator __next = std::next(__old); 709 this->_M_invalidate_if([__next](_Base_const_iterator __it) 710 { return __it == __next; }); 711 __to_destroy.splice_after(__to_destroy.cbefore_begin(), 712 *this, __old); 713 __x = __old; 714 _GLIBCXX20_ONLY( __removed++ ); 715 } 716 717 __old = __x++; 718 } 719 720 return _GLIBCXX20_ONLY( __removed ); 721 } 722 723 template<typename _Pred> 724 __remove_return_type 725 remove_if(_Pred __pred) 726 { 727 if (!this->_M_iterators && !this->_M_const_iterators) 728 return _Base::remove_if(__pred); 729 730 size_type __removed __attribute__((__unused__)) = 0; 731 _Base __to_destroy(get_allocator()); 732 _Base_iterator __x = _Base::before_begin(); 733 _Base_iterator __old = __x++; 734 while (__x != _Base::end()) 735 { 736 if (__pred(*__x)) 737 { 738 this->_M_invalidate_if([__x](_Base_const_iterator __it) 739 { return __it == __x; }); 740 __to_destroy.splice_after(__to_destroy.cbefore_begin(), 741 *this, __old); 742 __x = __old; 743 _GLIBCXX20_ONLY( __removed++ ); 744 } 745 746 __old = __x++; 747 } 748 749 return _GLIBCXX20_ONLY( __removed ); 750 } 751 752 _GLIBCXX_FWDLIST_REMOVE_RETURN_TYPE_TAG 753 __remove_return_type 754 unique() 755 { return unique(std::equal_to<_Tp>()); } 756 757 template<typename _BinPred> 758 __remove_return_type 759 unique(_BinPred __binary_pred) 760 { 761 if (!this->_M_iterators && !this->_M_const_iterators) 762 return _Base::unique(__binary_pred); 763 764 _Base_const_iterator __first = _Base::cbegin(); 765 _Base_const_iterator __last = _Base::cend(); 766 if (__first == __last) 767 return _GLIBCXX20_ONLY(0); 768 769 size_type __removed __attribute__((__unused__)) = 0; 770 _Base __to_destroy(get_allocator()); 771 _Base_const_iterator __next = std::next(__first); 772 while (__next != __last) 773 { 774 if (__binary_pred(*__first, *__next)) 775 { 776 this->_M_invalidate_if([__next](_Base_const_iterator __it) 777 { return __it == __next; }); 778 __to_destroy.splice_after(__to_destroy.cbefore_begin(), 779 *this, __first); 780 __next = __first; 781 _GLIBCXX20_ONLY( __removed++ ); 782 } 783 784 __first = __next++; 785 } 786 787 return _GLIBCXX20_ONLY( __removed ); 788 } 789 790#undef _GLIBCXX_FWDLIST_REMOVE_RETURN_TYPE_TAG 791#undef _GLIBCXX20_ONLY 792 793 void 794 merge(forward_list&& __list) 795 { 796 if (this != std::__addressof(__list)) 797 { 798 __glibcxx_check_sorted(_Base::begin(), _Base::end()); 799 __glibcxx_check_sorted(__list._M_base().begin(), 800 __list._M_base().end()); 801 this->_M_transfer_from_if(__list, [&__list](_Base_const_iterator __it) 802 { 803 return __it != __list._M_base().cbefore_begin() 804 && __it != __list._M_base().cend(); 805 }); 806 _Base::merge(std::move(__list)); 807 } 808 } 809 810 void 811 merge(forward_list& __list) 812 { merge(std::move(__list)); } 813 814 template<typename _Comp> 815 void 816 merge(forward_list&& __list, _Comp __comp) 817 { 818 if (this != std::__addressof(__list)) 819 { 820 __glibcxx_check_sorted_pred(_Base::begin(), _Base::end(), __comp); 821 __glibcxx_check_sorted_pred(__list._M_base().begin(), 822 __list._M_base().end(), __comp); 823 this->_M_transfer_from_if(__list, 824 [&__list](_Base_const_iterator __it) 825 { 826 return __it != __list._M_base().cbefore_begin() 827 && __it != __list._M_base().cend(); 828 }); 829 _Base::merge(std::move(__list), __comp); 830 } 831 } 832 833 template<typename _Comp> 834 void 835 merge(forward_list& __list, _Comp __comp) 836 { merge(std::move(__list), __comp); } 837 838 using _Base::sort; 839 using _Base::reverse; 840 841 _Base& 842 _M_base() noexcept { return *this; } 843 844 const _Base& 845 _M_base() const noexcept { return *this; } 846 }; 847 848#if __cpp_deduction_guides >= 201606 849 template<typename _InputIterator, typename _ValT 850 = typename iterator_traits<_InputIterator>::value_type, 851 typename _Allocator = allocator<_ValT>, 852 typename = _RequireInputIter<_InputIterator>, 853 typename = _RequireAllocator<_Allocator>> 854 forward_list(_InputIterator, _InputIterator, _Allocator = _Allocator()) 855 -> forward_list<_ValT, _Allocator>; 856 857 template<typename _Tp, typename _Allocator = allocator<_Tp>, 858 typename = _RequireAllocator<_Allocator>> 859 forward_list(size_t, _Tp, _Allocator = _Allocator()) 860 -> forward_list<_Tp, _Allocator>; 861#endif 862 863 template<typename _Tp, typename _Alloc> 864 bool 865 operator==(const forward_list<_Tp, _Alloc>& __lx, 866 const forward_list<_Tp, _Alloc>& __ly) 867 { return __lx._M_base() == __ly._M_base(); } 868 869#if __cpp_lib_three_way_comparison 870 template<typename _Tp, typename _Alloc> 871 constexpr __detail::__synth3way_t<_Tp> 872 operator<=>(const forward_list<_Tp, _Alloc>& __x, 873 const forward_list<_Tp, _Alloc>& __y) 874 { return __x._M_base() <=> __y._M_base(); } 875#else 876 template<typename _Tp, typename _Alloc> 877 inline bool 878 operator<(const forward_list<_Tp, _Alloc>& __lx, 879 const forward_list<_Tp, _Alloc>& __ly) 880 { return __lx._M_base() < __ly._M_base(); } 881 882 template<typename _Tp, typename _Alloc> 883 inline bool 884 operator!=(const forward_list<_Tp, _Alloc>& __lx, 885 const forward_list<_Tp, _Alloc>& __ly) 886 { return !(__lx == __ly); } 887 888 /// Based on operator< 889 template<typename _Tp, typename _Alloc> 890 inline bool 891 operator>(const forward_list<_Tp, _Alloc>& __lx, 892 const forward_list<_Tp, _Alloc>& __ly) 893 { return (__ly < __lx); } 894 895 /// Based on operator< 896 template<typename _Tp, typename _Alloc> 897 inline bool 898 operator>=(const forward_list<_Tp, _Alloc>& __lx, 899 const forward_list<_Tp, _Alloc>& __ly) 900 { return !(__lx < __ly); } 901 902 /// Based on operator< 903 template<typename _Tp, typename _Alloc> 904 inline bool 905 operator<=(const forward_list<_Tp, _Alloc>& __lx, 906 const forward_list<_Tp, _Alloc>& __ly) 907 { return !(__ly < __lx); } 908#endif // three-way comparison 909 910 /// See std::forward_list::swap(). 911 template<typename _Tp, typename _Alloc> 912 inline void 913 swap(forward_list<_Tp, _Alloc>& __lx, forward_list<_Tp, _Alloc>& __ly) 914 noexcept(noexcept(__lx.swap(__ly))) 915 { __lx.swap(__ly); } 916 917} // namespace __debug 918} // namespace std 919 920namespace __gnu_debug 921{ 922 template<typename _Tp, typename _Alloc> 923 struct _BeforeBeginHelper<std::__debug::forward_list<_Tp, _Alloc> > 924 { 925 typedef std::__debug::forward_list<_Tp, _Alloc> _Sequence; 926 927 template<typename _Iterator> 928 static bool 929 _S_Is(const _Safe_iterator<_Iterator, _Sequence>& __it) 930 { 931 return 932 __it.base() == __it._M_get_sequence()->_M_base().before_begin(); 933 } 934 935 template<typename _Iterator> 936 static bool 937 _S_Is_Beginnest(const _Safe_iterator<_Iterator, _Sequence>& __it) 938 { return _S_Is(__it); } 939 }; 940 941 template<typename _Tp, typename _Alloc> 942 struct _Sequence_traits<std::__debug::forward_list<_Tp, _Alloc> > 943 { 944 typedef typename std::__debug::forward_list<_Tp, _Alloc>::iterator _It; 945 946 static typename _Distance_traits<_It>::__type 947 _S_size(const std::__debug::forward_list<_Tp, _Alloc>& __seq) 948 { 949 return __seq.empty() 950 ? std::make_pair(0, __dp_exact) : std::make_pair(1, __dp_sign); 951 } 952 }; 953 954#ifndef _GLIBCXX_DEBUG_PEDANTIC 955 template<class _Tp, class _Alloc> 956 struct _Insert_range_from_self_is_safe< 957 std::__debug::forward_list<_Tp, _Alloc> > 958 { enum { __value = 1 }; }; 959#endif 960} 961 962#endif 963