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