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