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