libstdc++-v3/include/debug/forward_list

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