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