1// Debugging deque 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/deque
26 *  This file is a GNU debug extension to the Standard C++ Library.
27 */
28
29#ifndef _GLIBCXX_DEBUG_DEQUE
30#define _GLIBCXX_DEBUG_DEQUE 1
31
32#include <deque>
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::deque with safety/checking/debug instrumentation.
42  template<typename _Tp, typename _Allocator = std::allocator<_Tp> >
43    class deque
44    : public __gnu_debug::_Safe_container<
45	deque<_Tp, _Allocator>, _Allocator,
46	__gnu_debug::_Safe_sequence>,
47      public _GLIBCXX_STD_C::deque<_Tp, _Allocator>
48    {
49      typedef  _GLIBCXX_STD_C::deque<_Tp, _Allocator>		_Base;
50      typedef __gnu_debug::_Safe_container<
51	deque, _Allocator, __gnu_debug::_Safe_sequence>	_Safe;
52
53      typedef typename _Base::const_iterator	_Base_const_iterator;
54      typedef typename _Base::iterator		_Base_iterator;
55      typedef __gnu_debug::_Equal_to<_Base_const_iterator> _Equal;
56
57    public:
58      typedef typename _Base::reference			reference;
59      typedef typename _Base::const_reference		const_reference;
60
61      typedef __gnu_debug::_Safe_iterator<_Base_iterator, deque>
62							iterator;
63      typedef __gnu_debug::_Safe_iterator<_Base_const_iterator, deque>
64							const_iterator;
65
66      typedef typename _Base::size_type			size_type;
67      typedef typename _Base::difference_type		difference_type;
68
69      typedef _Tp					value_type;
70      typedef _Allocator				allocator_type;
71      typedef typename _Base::pointer			pointer;
72      typedef typename _Base::const_pointer		const_pointer;
73      typedef std::reverse_iterator<iterator>		reverse_iterator;
74      typedef std::reverse_iterator<const_iterator>	const_reverse_iterator;
75
76      // 23.2.1.1 construct/copy/destroy:
77
78#if __cplusplus < 201103L
79      deque()
80      : _Base() { }
81
82      deque(const deque& __x)
83      : _Base(__x) { }
84
85      ~deque() { }
86#else
87      deque() = default;
88      deque(const deque&) = default;
89      deque(deque&&) = default;
90
91      deque(const deque& __d, const _Allocator& __a)
92      : _Base(__d, __a) { }
93
94      deque(deque&& __d, const _Allocator& __a)
95      : _Safe(std::move(__d)), _Base(std::move(__d), __a) { }
96
97      deque(initializer_list<value_type> __l,
98	    const allocator_type& __a = allocator_type())
99      : _Base(__l, __a) { }
100
101      ~deque() = default;
102#endif
103
104      explicit
105      deque(const _Allocator& __a)
106      : _Base(__a) { }
107
108#if __cplusplus >= 201103L
109      explicit
110      deque(size_type __n, const _Allocator& __a = _Allocator())
111      : _Base(__n, __a) { }
112
113      deque(size_type __n, const _Tp& __value,
114	    const _Allocator& __a = _Allocator())
115      : _Base(__n, __value, __a) { }
116#else
117      explicit
118      deque(size_type __n, const _Tp& __value = _Tp(),
119	    const _Allocator& __a = _Allocator())
120      : _Base(__n, __value, __a) { }
121#endif
122
123#if __cplusplus >= 201103L
124      template<class _InputIterator,
125	       typename = std::_RequireInputIter<_InputIterator>>
126#else
127      template<class _InputIterator>
128#endif
129	deque(_InputIterator __first, _InputIterator __last,
130	      const _Allocator& __a = _Allocator())
131	: _Base(__gnu_debug::__base(__gnu_debug::__check_valid_range(__first,
132								     __last)),
133		__gnu_debug::__base(__last), __a)
134	{ }
135
136      deque(const _Base& __x)
137      : _Base(__x) { }
138
139#if __cplusplus < 201103L
140      deque&
141      operator=(const deque& __x)
142      {
143	this->_M_safe() = __x;
144	_M_base() = __x;
145	return *this;
146      }
147#else
148      deque&
149      operator=(const deque&) = default;
150
151      deque&
152      operator=(deque&&) = default;
153
154      deque&
155      operator=(initializer_list<value_type> __l)
156      {
157	_M_base() = __l;
158	this->_M_invalidate_all();
159	return *this;
160      }
161#endif
162
163#if __cplusplus >= 201103L
164      template<class _InputIterator,
165	       typename = std::_RequireInputIter<_InputIterator>>
166#else
167      template<class _InputIterator>
168#endif
169	void
170	assign(_InputIterator __first, _InputIterator __last)
171	{
172	  typename __gnu_debug::_Distance_traits<_InputIterator>::__type __dist;
173	  __glibcxx_check_valid_range2(__first, __last, __dist);
174	  if (__dist.second >= __gnu_debug::__dp_sign)
175	    _Base::assign(__gnu_debug::__unsafe(__first),
176			  __gnu_debug::__unsafe(__last));
177	  else
178	    _Base::assign(__first, __last);
179
180	  this->_M_invalidate_all();
181	}
182
183      void
184      assign(size_type __n, const _Tp& __t)
185      {
186	_Base::assign(__n, __t);
187	this->_M_invalidate_all();
188      }
189
190#if __cplusplus >= 201103L
191      void
192      assign(initializer_list<value_type> __l)
193      {
194	_Base::assign(__l);
195	this->_M_invalidate_all();
196      }
197#endif
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    private:
253      void
254      _M_invalidate_after_nth(difference_type __n)
255      {
256	typedef __gnu_debug::_After_nth_from<_Base_const_iterator> _After_nth;
257	this->_M_invalidate_if(_After_nth(__n, _Base::begin()));
258      }
259
260    public:
261      // 23.2.1.2 capacity:
262      using _Base::size;
263      using _Base::max_size;
264
265#if __cplusplus >= 201103L
266      void
267      resize(size_type __sz)
268      {
269	bool __invalidate_all = __sz > this->size();
270	if (__sz < this->size())
271	  this->_M_invalidate_after_nth(__sz);
272
273	_Base::resize(__sz);
274
275	if (__invalidate_all)
276	  this->_M_invalidate_all();
277      }
278
279      void
280      resize(size_type __sz, const _Tp& __c)
281      {
282	bool __invalidate_all = __sz > this->size();
283	if (__sz < this->size())
284	  this->_M_invalidate_after_nth(__sz);
285
286	_Base::resize(__sz, __c);
287
288	if (__invalidate_all)
289	  this->_M_invalidate_all();
290      }
291#else
292      void
293      resize(size_type __sz, _Tp __c = _Tp())
294      {
295	bool __invalidate_all = __sz > this->size();
296	if (__sz < this->size())
297	  this->_M_invalidate_after_nth(__sz);
298
299	_Base::resize(__sz, __c);
300
301	if (__invalidate_all)
302	  this->_M_invalidate_all();
303      }
304#endif
305
306#if __cplusplus >= 201103L
307      void
308      shrink_to_fit() noexcept
309      {
310	if (_Base::_M_shrink_to_fit())
311	  this->_M_invalidate_all();
312      }
313#endif
314
315      using _Base::empty;
316
317      // element access:
318      reference
319      operator[](size_type __n) _GLIBCXX_NOEXCEPT
320      {
321	__glibcxx_check_subscript(__n);
322	return _M_base()[__n];
323      }
324
325      const_reference
326      operator[](size_type __n) const _GLIBCXX_NOEXCEPT
327      {
328	__glibcxx_check_subscript(__n);
329	return _M_base()[__n];
330      }
331
332      using _Base::at;
333
334      reference
335      front() _GLIBCXX_NOEXCEPT
336      {
337	__glibcxx_check_nonempty();
338	return _Base::front();
339      }
340
341      const_reference
342      front() const _GLIBCXX_NOEXCEPT
343      {
344	__glibcxx_check_nonempty();
345	return _Base::front();
346      }
347
348      reference
349      back() _GLIBCXX_NOEXCEPT
350      {
351	__glibcxx_check_nonempty();
352	return _Base::back();
353      }
354
355      const_reference
356      back() const _GLIBCXX_NOEXCEPT
357      {
358	__glibcxx_check_nonempty();
359	return _Base::back();
360      }
361
362      // 23.2.1.3 modifiers:
363      void
364      push_front(const _Tp& __x)
365      {
366	_Base::push_front(__x);
367	this->_M_invalidate_all();
368      }
369
370      void
371      push_back(const _Tp& __x)
372      {
373	_Base::push_back(__x);
374	this->_M_invalidate_all();
375      }
376
377#if __cplusplus >= 201103L
378      void
379      push_front(_Tp&& __x)
380      { emplace_front(std::move(__x)); }
381
382      void
383      push_back(_Tp&& __x)
384      { emplace_back(std::move(__x)); }
385
386      template<typename... _Args>
387	void
388	emplace_front(_Args&&... __args)
389	{
390	  _Base::emplace_front(std::forward<_Args>(__args)...);
391	  this->_M_invalidate_all();
392	}
393
394      template<typename... _Args>
395	void
396	emplace_back(_Args&&... __args)
397	{
398	  _Base::emplace_back(std::forward<_Args>(__args)...);
399	  this->_M_invalidate_all();
400	}
401
402      template<typename... _Args>
403	iterator
404	emplace(const_iterator __position, _Args&&... __args)
405	{
406	  __glibcxx_check_insert(__position);
407	  _Base_iterator __res = _Base::emplace(__position.base(),
408						std::forward<_Args>(__args)...);
409	  this->_M_invalidate_all();
410	  return iterator(__res, this);
411	}
412#endif
413
414      iterator
415#if __cplusplus >= 201103L
416      insert(const_iterator __position, const _Tp& __x)
417#else
418      insert(iterator __position, const _Tp& __x)
419#endif
420      {
421	__glibcxx_check_insert(__position);
422	_Base_iterator __res = _Base::insert(__position.base(), __x);
423	this->_M_invalidate_all();
424	return iterator(__res, this);
425      }
426
427#if __cplusplus >= 201103L
428      iterator
429      insert(const_iterator __position, _Tp&& __x)
430      { return emplace(__position, std::move(__x)); }
431
432      iterator
433      insert(const_iterator __position, initializer_list<value_type> __l)
434      {
435	__glibcxx_check_insert(__position);
436	_Base_iterator __res = _Base::insert(__position.base(), __l);
437	this->_M_invalidate_all();
438	return iterator(__res, this);
439      }
440#endif
441
442#if __cplusplus >= 201103L
443      iterator
444      insert(const_iterator __position, size_type __n, const _Tp& __x)
445      {
446	__glibcxx_check_insert(__position);
447	_Base_iterator __res = _Base::insert(__position.base(), __n, __x);
448	this->_M_invalidate_all();
449	return iterator(__res, this);
450      }
451#else
452      void
453      insert(iterator __position, size_type __n, const _Tp& __x)
454      {
455	__glibcxx_check_insert(__position);
456	_Base::insert(__position.base(), __n, __x);
457	this->_M_invalidate_all();
458      }
459#endif
460
461#if __cplusplus >= 201103L
462      template<class _InputIterator,
463	       typename = std::_RequireInputIter<_InputIterator>>
464	iterator
465	insert(const_iterator __position,
466	       _InputIterator __first, _InputIterator __last)
467	{
468	  typename __gnu_debug::_Distance_traits<_InputIterator>::__type __dist;
469	  __glibcxx_check_insert_range(__position, __first, __last, __dist);
470	  _Base_iterator __res;
471	  if (__dist.second >= __gnu_debug::__dp_sign)
472	    __res = _Base::insert(__position.base(),
473				  __gnu_debug::__unsafe(__first),
474				  __gnu_debug::__unsafe(__last));
475	  else
476	    __res = _Base::insert(__position.base(), __first, __last);
477
478	  this->_M_invalidate_all();
479	  return iterator(__res, this);
480	}
481#else
482      template<class _InputIterator>
483	void
484	insert(iterator __position,
485	       _InputIterator __first, _InputIterator __last)
486	{
487	  typename __gnu_debug::_Distance_traits<_InputIterator>::__type __dist;
488	  __glibcxx_check_insert_range(__position, __first, __last, __dist);
489
490	  if (__dist.second >= __gnu_debug::__dp_sign)
491	    _Base::insert(__position.base(),
492			  __gnu_debug::__unsafe(__first),
493			  __gnu_debug::__unsafe(__last));
494	  else
495	    _Base::insert(__position.base(), __first, __last);
496
497	  this->_M_invalidate_all();
498	}
499#endif
500
501      void
502      pop_front() _GLIBCXX_NOEXCEPT
503      {
504	__glibcxx_check_nonempty();
505	this->_M_invalidate_if(_Equal(_Base::begin()));
506	_Base::pop_front();
507      }
508
509      void
510      pop_back() _GLIBCXX_NOEXCEPT
511      {
512	__glibcxx_check_nonempty();
513	this->_M_invalidate_if(_Equal(--_Base::end()));
514	_Base::pop_back();
515      }
516
517      iterator
518#if __cplusplus >= 201103L
519      erase(const_iterator __position)
520#else
521      erase(iterator __position)
522#endif
523      {
524	__glibcxx_check_erase(__position);
525#if __cplusplus >= 201103L
526	_Base_const_iterator __victim = __position.base();
527#else
528	_Base_iterator __victim = __position.base();
529#endif
530	if (__victim == _Base::begin() || __victim == _Base::end() - 1)
531	  {
532	    this->_M_invalidate_if(_Equal(__victim));
533	    return iterator(_Base::erase(__victim), this);
534	  }
535	else
536	  {
537	    _Base_iterator __res = _Base::erase(__victim);
538	    this->_M_invalidate_all();
539	    return iterator(__res, this);
540	  }
541      }
542
543      iterator
544#if __cplusplus >= 201103L
545      erase(const_iterator __first, const_iterator __last)
546#else
547      erase(iterator __first, iterator __last)
548#endif
549      {
550	// _GLIBCXX_RESOLVE_LIB_DEFECTS
551	// 151. can't currently clear() empty container
552	__glibcxx_check_erase_range(__first, __last);
553
554	if (__first.base() == __last.base())
555#if __cplusplus >= 201103L
556	  return iterator(__first.base()._M_const_cast(), this);
557#else
558	  return __first;
559#endif
560	else if (__first.base() == _Base::begin()
561		 || __last.base() == _Base::end())
562	  {
563	    this->_M_detach_singular();
564	    for (_Base_const_iterator __position = __first.base();
565		 __position != __last.base(); ++__position)
566	      {
567		this->_M_invalidate_if(_Equal(__position));
568	      }
569	    __try
570	      {
571		return iterator(_Base::erase(__first.base(), __last.base()),
572				this);
573	      }
574	    __catch(...)
575	      {
576		this->_M_revalidate_singular();
577		__throw_exception_again;
578	      }
579	  }
580	else
581	  {
582	    _Base_iterator __res = _Base::erase(__first.base(),
583						__last.base());
584	    this->_M_invalidate_all();
585	    return iterator(__res, this);
586	  }
587      }
588
589      void
590      swap(deque& __x)
591      _GLIBCXX_NOEXCEPT_IF( noexcept(declval<_Base&>().swap(__x)) )
592      {
593	_Safe::_M_swap(__x);
594	_Base::swap(__x);
595      }
596
597      void
598      clear() _GLIBCXX_NOEXCEPT
599      {
600	_Base::clear();
601	this->_M_invalidate_all();
602      }
603
604      _Base&
605      _M_base() _GLIBCXX_NOEXCEPT	{ return *this; }
606
607      const _Base&
608      _M_base() const _GLIBCXX_NOEXCEPT	{ return *this; }
609    };
610
611  template<typename _Tp, typename _Alloc>
612    inline bool
613    operator==(const deque<_Tp, _Alloc>& __lhs,
614	       const deque<_Tp, _Alloc>& __rhs)
615    { return __lhs._M_base() == __rhs._M_base(); }
616
617  template<typename _Tp, typename _Alloc>
618    inline bool
619    operator!=(const deque<_Tp, _Alloc>& __lhs,
620	       const deque<_Tp, _Alloc>& __rhs)
621    { return __lhs._M_base() != __rhs._M_base(); }
622
623  template<typename _Tp, typename _Alloc>
624    inline bool
625    operator<(const deque<_Tp, _Alloc>& __lhs,
626	      const deque<_Tp, _Alloc>& __rhs)
627    { return __lhs._M_base() < __rhs._M_base(); }
628
629  template<typename _Tp, typename _Alloc>
630    inline bool
631    operator<=(const deque<_Tp, _Alloc>& __lhs,
632	       const deque<_Tp, _Alloc>& __rhs)
633    { return __lhs._M_base() <= __rhs._M_base(); }
634
635  template<typename _Tp, typename _Alloc>
636    inline bool
637    operator>=(const deque<_Tp, _Alloc>& __lhs,
638	       const deque<_Tp, _Alloc>& __rhs)
639    { return __lhs._M_base() >= __rhs._M_base(); }
640
641  template<typename _Tp, typename _Alloc>
642    inline bool
643    operator>(const deque<_Tp, _Alloc>& __lhs,
644	      const deque<_Tp, _Alloc>& __rhs)
645    { return __lhs._M_base() > __rhs._M_base(); }
646
647  template<typename _Tp, typename _Alloc>
648    inline void
649    swap(deque<_Tp, _Alloc>& __lhs, deque<_Tp, _Alloc>& __rhs)
650    _GLIBCXX_NOEXCEPT_IF(noexcept(__lhs.swap(__rhs)))
651    { __lhs.swap(__rhs); }
652
653} // namespace __debug
654} // namespace std
655
656#endif
657