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
39namespace __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
171namespace std _GLIBCXX_VISIBILITY(default)
172{
173namespace __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
798namespace __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
828