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