libstdc++-v3/include/debug/forward_list

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