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