xref: /netbsd-src/external/gpl3/gcc.old/dist/libstdc++-v3/include/debug/list (revision b7b7574d3bf8eeb51a1fa3977b59142ec6434a55) 
1// Debugging list implementation -*- C++ -*-
2
3// Copyright (C) 2003, 2004, 2005, 2006, 2007, 2008, 2009, 2010
4// Free Software Foundation, Inc.
5//
6// This file is part of the GNU ISO C++ Library.  This library is free
7// software; you can redistribute it and/or modify it under the
8// terms of the GNU General Public License as published by the
9// Free Software Foundation; either version 3, or (at your option)
10// any later version.
11
12// This library is distributed in the hope that it will be useful,
13// but WITHOUT ANY WARRANTY; without even the implied warranty of
14// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
15// GNU General Public License for more details.
16
17// Under Section 7 of GPL version 3, you are granted additional
18// permissions described in the GCC Runtime Library Exception, version
19// 3.1, as published by the Free Software Foundation.
20
21// You should have received a copy of the GNU General Public License and
22// a copy of the GCC Runtime Library Exception along with this program;
23// see the files COPYING3 and COPYING.RUNTIME respectively.  If not, see
24// <http://www.gnu.org/licenses/>.
25
26/** @file debug/list
27 *  This file is a GNU debug extension to the Standard C++ Library.
28 */
29
30#ifndef _GLIBCXX_DEBUG_LIST
31#define _GLIBCXX_DEBUG_LIST 1
32
33#include <list>
34#include <debug/safe_sequence.h>
35#include <debug/safe_iterator.h>
36
37namespace std
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 _GLIBCXX_STD_D::list<_Tp, _Allocator>,
45      public __gnu_debug::_Safe_sequence<list<_Tp, _Allocator> >
46    {
47      typedef _GLIBCXX_STD_D::list<_Tp, _Allocator> _Base;
48      typedef __gnu_debug::_Safe_sequence<list>  _Safe_base;
49
50    public:
51      typedef typename _Base::reference             reference;
52      typedef typename _Base::const_reference       const_reference;
53
54      typedef __gnu_debug::_Safe_iterator<typename _Base::iterator, list>
55						    iterator;
56      typedef __gnu_debug::_Safe_iterator<typename _Base::const_iterator, list>
57						    const_iterator;
58
59      typedef typename _Base::size_type             size_type;
60      typedef typename _Base::difference_type       difference_type;
61
62      typedef _Tp				    value_type;
63      typedef _Allocator			    allocator_type;
64      typedef typename _Base::pointer               pointer;
65      typedef typename _Base::const_pointer         const_pointer;
66      typedef std::reverse_iterator<iterator>       reverse_iterator;
67      typedef std::reverse_iterator<const_iterator> const_reverse_iterator;
68
69      // 23.2.2.1 construct/copy/destroy:
70      explicit list(const _Allocator& __a = _Allocator())
71      : _Base(__a) { }
72
73      explicit list(size_type __n, const _Tp& __value = _Tp(),
74		    const _Allocator& __a = _Allocator())
75      : _Base(__n, __value, __a) { }
76
77      template<class _InputIterator>
78      list(_InputIterator __first, _InputIterator __last,
79	   const _Allocator& __a = _Allocator())
80      : _Base(__gnu_debug::__check_valid_range(__first, __last), __last, __a)
81      { }
82
83
84      list(const list& __x)
85      : _Base(__x), _Safe_base() { }
86
87      list(const _Base& __x)
88      : _Base(__x), _Safe_base() { }
89
90#ifdef __GXX_EXPERIMENTAL_CXX0X__
91      list(list&& __x)
92      : _Base(std::forward<list>(__x)), _Safe_base()
93      { this->_M_swap(__x); }
94
95      list(initializer_list<value_type> __l,
96           const allocator_type& __a = allocator_type())
97        : _Base(__l, __a), _Safe_base() { }
98#endif
99
100      ~list() { }
101
102      list&
103      operator=(const list& __x)
104      {
105	static_cast<_Base&>(*this) = __x;
106	this->_M_invalidate_all();
107	return *this;
108      }
109
110#ifdef __GXX_EXPERIMENTAL_CXX0X__
111      list&
112      operator=(list&& __x)
113      {
114	// NB: DR 1204.
115	// NB: DR 675.
116	clear();
117	swap(__x);
118      	return *this;
119      }
120
121      list&
122      operator=(initializer_list<value_type> __l)
123      {
124	static_cast<_Base&>(*this) = __l;
125	this->_M_invalidate_all();
126	return *this;
127      }
128
129      void
130      assign(initializer_list<value_type> __l)
131      {
132	_Base::assign(__l);
133	this->_M_invalidate_all();
134      }
135#endif
136
137      template<class _InputIterator>
138        void
139        assign(_InputIterator __first, _InputIterator __last)
140        {
141	  __glibcxx_check_valid_range(__first, __last);
142	  _Base::assign(__first, __last);
143	  this->_M_invalidate_all();
144	}
145
146      void
147      assign(size_type __n, const _Tp& __t)
148      {
149	_Base::assign(__n, __t);
150	this->_M_invalidate_all();
151      }
152
153      using _Base::get_allocator;
154
155      // iterators:
156      iterator
157      begin()
158      { return iterator(_Base::begin(), this); }
159
160      const_iterator
161      begin() const
162      { return const_iterator(_Base::begin(), this); }
163
164      iterator
165      end()
166      { return iterator(_Base::end(), this); }
167
168      const_iterator
169      end() const
170      { return const_iterator(_Base::end(), this); }
171
172      reverse_iterator
173      rbegin()
174      { return reverse_iterator(end()); }
175
176      const_reverse_iterator
177      rbegin() const
178      { return const_reverse_iterator(end()); }
179
180      reverse_iterator
181      rend()
182      { return reverse_iterator(begin()); }
183
184      const_reverse_iterator
185      rend() const
186      { return const_reverse_iterator(begin()); }
187
188#ifdef __GXX_EXPERIMENTAL_CXX0X__
189      const_iterator
190      cbegin() const
191      { return const_iterator(_Base::begin(), this); }
192
193      const_iterator
194      cend() const
195      { return const_iterator(_Base::end(), this); }
196
197      const_reverse_iterator
198      crbegin() const
199      { return const_reverse_iterator(end()); }
200
201      const_reverse_iterator
202      crend() const
203      { return const_reverse_iterator(begin()); }
204#endif
205
206      // 23.2.2.2 capacity:
207      using _Base::empty;
208      using _Base::size;
209      using _Base::max_size;
210
211      void
212      resize(size_type __sz, _Tp __c = _Tp())
213      {
214	this->_M_detach_singular();
215
216	// if __sz < size(), invalidate all iterators in [begin+__sz, end())
217	iterator __victim = begin();
218	iterator __end = end();
219	for (size_type __i = __sz; __victim != __end && __i > 0; --__i)
220	  ++__victim;
221
222	while (__victim != __end)
223	  {
224	    iterator __real_victim = __victim++;
225	    __real_victim._M_invalidate();
226	  }
227
228	__try
229	  {
230	    _Base::resize(__sz, __c);
231	  }
232	__catch(...)
233	  {
234	    this->_M_revalidate_singular();
235	    __throw_exception_again;
236	  }
237      }
238
239      // element access:
240      reference
241      front()
242      {
243	__glibcxx_check_nonempty();
244	return _Base::front();
245      }
246
247      const_reference
248      front() const
249      {
250	__glibcxx_check_nonempty();
251	return _Base::front();
252      }
253
254      reference
255      back()
256      {
257	__glibcxx_check_nonempty();
258	return _Base::back();
259      }
260
261      const_reference
262      back() const
263      {
264	__glibcxx_check_nonempty();
265	return _Base::back();
266      }
267
268      // 23.2.2.3 modifiers:
269      using _Base::push_front;
270
271#ifdef __GXX_EXPERIMENTAL_CXX0X__
272      using _Base::emplace_front;
273#endif
274
275      void
276      pop_front()
277      {
278	__glibcxx_check_nonempty();
279	iterator __victim = begin();
280	__victim._M_invalidate();
281	_Base::pop_front();
282      }
283
284      using _Base::push_back;
285
286#ifdef __GXX_EXPERIMENTAL_CXX0X__
287      using _Base::emplace_back;
288#endif
289
290      void
291      pop_back()
292      {
293	__glibcxx_check_nonempty();
294	iterator __victim = end();
295	--__victim;
296	__victim._M_invalidate();
297	_Base::pop_back();
298      }
299
300#ifdef __GXX_EXPERIMENTAL_CXX0X__
301      template<typename... _Args>
302        iterator
303        emplace(iterator __position, _Args&&... __args)
304	{
305	  __glibcxx_check_insert(__position);
306	  return iterator(_Base::emplace(__position.base(),
307					std::forward<_Args>(__args)...), this);
308	}
309#endif
310
311      iterator
312      insert(iterator __position, const _Tp& __x)
313      {
314	__glibcxx_check_insert(__position);
315	return iterator(_Base::insert(__position.base(), __x), this);
316      }
317
318#ifdef __GXX_EXPERIMENTAL_CXX0X__
319      iterator
320      insert(iterator __position, _Tp&& __x)
321      { return emplace(__position, std::move(__x)); }
322
323      void
324      insert(iterator __p, initializer_list<value_type> __l)
325      {
326	__glibcxx_check_insert(__p);
327	_Base::insert(__p, __l);
328      }
329#endif
330
331      void
332      insert(iterator __position, size_type __n, const _Tp& __x)
333      {
334	__glibcxx_check_insert(__position);
335	_Base::insert(__position.base(), __n, __x);
336      }
337
338      template<class _InputIterator>
339        void
340        insert(iterator __position, _InputIterator __first,
341	       _InputIterator __last)
342        {
343	  __glibcxx_check_insert_range(__position, __first, __last);
344	  _Base::insert(__position.base(), __first, __last);
345	}
346
347      iterator
348      erase(iterator __position)
349      {
350	__glibcxx_check_erase(__position);
351	__position._M_invalidate();
352	return iterator(_Base::erase(__position.base()), this);
353      }
354
355      iterator
356      erase(iterator __position, iterator __last)
357      {
358	// _GLIBCXX_RESOLVE_LIB_DEFECTS
359	// 151. can't currently clear() empty container
360	__glibcxx_check_erase_range(__position, __last);
361	for (iterator __victim = __position; __victim != __last; )
362	  {
363	    iterator __old = __victim;
364	    ++__victim;
365	    __old._M_invalidate();
366	  }
367	return iterator(_Base::erase(__position.base(), __last.base()), this);
368      }
369
370      void
371      swap(list& __x)
372      {
373	_Base::swap(__x);
374	this->_M_swap(__x);
375      }
376
377      void
378      clear()
379      {
380	_Base::clear();
381	this->_M_invalidate_all();
382      }
383
384      // 23.2.2.4 list operations:
385      void
386#ifdef __GXX_EXPERIMENTAL_CXX0X__
387      splice(iterator __position, list&& __x)
388#else
389      splice(iterator __position, list& __x)
390#endif
391      {
392	_GLIBCXX_DEBUG_VERIFY(&__x != this,
393			      _M_message(__gnu_debug::__msg_self_splice)
394			      ._M_sequence(*this, "this"));
395	this->splice(__position, _GLIBCXX_MOVE(__x), __x.begin(), __x.end());
396      }
397
398#ifdef __GXX_EXPERIMENTAL_CXX0X__
399      void
400      splice(iterator __position, list& __x)
401      { splice(__position, std::move(__x)); }
402#endif
403
404      void
405#ifdef __GXX_EXPERIMENTAL_CXX0X__
406      splice(iterator __position, list&& __x, iterator __i)
407#else
408      splice(iterator __position, list& __x, iterator __i)
409#endif
410      {
411	__glibcxx_check_insert(__position);
412
413	// We used to perform the splice_alloc check:  not anymore, redundant
414	// after implementing the relevant bits of N1599.
415
416	_GLIBCXX_DEBUG_VERIFY(__i._M_dereferenceable(),
417			      _M_message(__gnu_debug::__msg_splice_bad)
418			      ._M_iterator(__i, "__i"));
419	_GLIBCXX_DEBUG_VERIFY(__i._M_attached_to(&__x),
420			      _M_message(__gnu_debug::__msg_splice_other)
421			     ._M_iterator(__i, "__i")._M_sequence(__x, "__x"));
422
423	// _GLIBCXX_RESOLVE_LIB_DEFECTS
424	// 250. splicing invalidates iterators
425	this->_M_transfer_iter(__i);
426	_Base::splice(__position.base(), _GLIBCXX_MOVE(__x._M_base()),
427		      __i.base());
428      }
429
430#ifdef __GXX_EXPERIMENTAL_CXX0X__
431      void
432      splice(iterator __position, list& __x, iterator __i)
433      { splice(__position, std::move(__x), __i); }
434#endif
435
436      void
437#ifdef __GXX_EXPERIMENTAL_CXX0X__
438      splice(iterator __position, list&& __x, iterator __first,
439	     iterator __last)
440#else
441      splice(iterator __position, list& __x, iterator __first,
442	     iterator __last)
443#endif
444      {
445	__glibcxx_check_insert(__position);
446	__glibcxx_check_valid_range(__first, __last);
447	_GLIBCXX_DEBUG_VERIFY(__first._M_attached_to(&__x),
448			      _M_message(__gnu_debug::__msg_splice_other)
449			      ._M_sequence(__x, "x")
450			      ._M_iterator(__first, "first"));
451
452	// We used to perform the splice_alloc check:  not anymore, redundant
453	// after implementing the relevant bits of N1599.
454
455	for (iterator __tmp = __first; __tmp != __last; )
456	  {
457	    _GLIBCXX_DEBUG_VERIFY(&__x != this || __tmp != __position,
458				_M_message(__gnu_debug::__msg_splice_overlap)
459				  ._M_iterator(__tmp, "position")
460				  ._M_iterator(__first, "first")
461				  ._M_iterator(__last, "last"));
462	    iterator __victim = __tmp++;
463	    // _GLIBCXX_RESOLVE_LIB_DEFECTS
464	    // 250. splicing invalidates iterators
465	    this->_M_transfer_iter(__victim);
466	  }
467
468	_Base::splice(__position.base(), _GLIBCXX_MOVE(__x._M_base()),
469		      __first.base(), __last.base());
470      }
471
472#ifdef __GXX_EXPERIMENTAL_CXX0X__
473      void
474      splice(iterator __position, list& __x, iterator __first, iterator __last)
475      { splice(__position, std::move(__x), __first, __last); }
476#endif
477
478      void
479      remove(const _Tp& __value)
480      {
481	for (iterator __x = begin(); __x.base() != _Base::end(); )
482	  {
483	    if (*__x == __value)
484	      __x = erase(__x);
485	    else
486	      ++__x;
487	  }
488      }
489
490      template<class _Predicate>
491        void
492        remove_if(_Predicate __pred)
493        {
494	  for (iterator __x = begin(); __x.base() != _Base::end(); )
495	    {
496	      if (__pred(*__x))
497		__x = erase(__x);
498	      else
499		++__x;
500	    }
501	}
502
503      void
504      unique()
505      {
506	iterator __first = begin();
507	iterator __last = end();
508	if (__first == __last)
509	  return;
510	iterator __next = __first;
511	while (++__next != __last)
512	  {
513	    if (*__first == *__next)
514	      erase(__next);
515	    else
516	      __first = __next;
517	    __next = __first;
518	  }
519      }
520
521      template<class _BinaryPredicate>
522        void
523        unique(_BinaryPredicate __binary_pred)
524        {
525	  iterator __first = begin();
526	  iterator __last = end();
527	  if (__first == __last)
528	    return;
529	  iterator __next = __first;
530	  while (++__next != __last)
531	    {
532	      if (__binary_pred(*__first, *__next))
533		erase(__next);
534	      else
535		__first = __next;
536	      __next = __first;
537	    }
538	}
539
540      void
541#ifdef __GXX_EXPERIMENTAL_CXX0X__
542      merge(list&& __x)
543#else
544      merge(list& __x)
545#endif
546      {
547	// _GLIBCXX_RESOLVE_LIB_DEFECTS
548	// 300. list::merge() specification incomplete
549	if (this != &__x)
550	  {
551	    __glibcxx_check_sorted(_Base::begin(), _Base::end());
552	    __glibcxx_check_sorted(__x.begin().base(), __x.end().base());
553	    for (iterator __tmp = __x.begin(); __tmp != __x.end();)
554	      {
555		iterator __victim = __tmp++;
556		this->_M_transfer_iter(__victim);
557	      }
558	    _Base::merge(_GLIBCXX_MOVE(__x._M_base()));
559	  }
560      }
561
562#ifdef __GXX_EXPERIMENTAL_CXX0X__
563      void
564      merge(list& __x)
565      { merge(std::move(__x)); }
566#endif
567
568      template<class _Compare>
569        void
570#ifdef __GXX_EXPERIMENTAL_CXX0X__
571        merge(list&& __x, _Compare __comp)
572#else
573        merge(list& __x, _Compare __comp)
574#endif
575        {
576	  // _GLIBCXX_RESOLVE_LIB_DEFECTS
577	  // 300. list::merge() specification incomplete
578	  if (this != &__x)
579	    {
580	      __glibcxx_check_sorted_pred(_Base::begin(), _Base::end(),
581					  __comp);
582	      __glibcxx_check_sorted_pred(__x.begin().base(), __x.end().base(),
583					  __comp);
584	      for (iterator __tmp = __x.begin(); __tmp != __x.end();)
585		{
586		  iterator __victim = __tmp++;
587		  this->_M_transfer_iter(__victim);
588		}
589	      _Base::merge(_GLIBCXX_MOVE(__x._M_base()), __comp);
590	    }
591	}
592
593#ifdef __GXX_EXPERIMENTAL_CXX0X__
594      template<typename _Compare>
595        void
596        merge(list& __x, _Compare __comp)
597        { merge(std::move(__x), __comp); }
598#endif
599
600      void
601      sort() { _Base::sort(); }
602
603      template<typename _StrictWeakOrdering>
604        void
605        sort(_StrictWeakOrdering __pred) { _Base::sort(__pred); }
606
607      using _Base::reverse;
608
609      _Base&
610      _M_base()       { return *this; }
611
612      const _Base&
613      _M_base() const { return *this; }
614
615    private:
616      void
617      _M_invalidate_all()
618      {
619	typedef typename _Base::const_iterator _Base_const_iterator;
620	typedef __gnu_debug::_Not_equal_to<_Base_const_iterator> _Not_equal;
621	this->_M_invalidate_if(_Not_equal(_M_base().end()));
622      }
623    };
624
625  template<typename _Tp, typename _Alloc>
626    inline bool
627    operator==(const list<_Tp, _Alloc>& __lhs,
628	       const list<_Tp, _Alloc>& __rhs)
629    { return __lhs._M_base() == __rhs._M_base(); }
630
631  template<typename _Tp, typename _Alloc>
632    inline bool
633    operator!=(const list<_Tp, _Alloc>& __lhs,
634	       const list<_Tp, _Alloc>& __rhs)
635    { return __lhs._M_base() != __rhs._M_base(); }
636
637  template<typename _Tp, typename _Alloc>
638    inline bool
639    operator<(const list<_Tp, _Alloc>& __lhs,
640	      const list<_Tp, _Alloc>& __rhs)
641    { return __lhs._M_base() < __rhs._M_base(); }
642
643  template<typename _Tp, typename _Alloc>
644    inline bool
645    operator<=(const list<_Tp, _Alloc>& __lhs,
646	       const list<_Tp, _Alloc>& __rhs)
647    { return __lhs._M_base() <= __rhs._M_base(); }
648
649  template<typename _Tp, typename _Alloc>
650    inline bool
651    operator>=(const list<_Tp, _Alloc>& __lhs,
652	       const list<_Tp, _Alloc>& __rhs)
653    { return __lhs._M_base() >= __rhs._M_base(); }
654
655  template<typename _Tp, typename _Alloc>
656    inline bool
657    operator>(const list<_Tp, _Alloc>& __lhs,
658	      const list<_Tp, _Alloc>& __rhs)
659    { return __lhs._M_base() > __rhs._M_base(); }
660
661  template<typename _Tp, typename _Alloc>
662    inline void
663    swap(list<_Tp, _Alloc>& __lhs, list<_Tp, _Alloc>& __rhs)
664    { __lhs.swap(__rhs); }
665
666} // namespace __debug
667} // namespace std
668
669#endif
670