contrib/gcc-5.0/libstdc++-v3/include/debug/forward_list

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