1// Debugging deque implementation -*- C++ -*-
2
3// Copyright (C) 2003-2015 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	  __glibcxx_check_valid_range(__first, __last);
173	  _Base::assign(__gnu_debug::__base(__first),
174			__gnu_debug::__base(__last));
175	  this->_M_invalidate_all();
176	}
177
178      void
179      assign(size_type __n, const _Tp& __t)
180      {
181	_Base::assign(__n, __t);
182	this->_M_invalidate_all();
183      }
184
185#if __cplusplus >= 201103L
186      void
187      assign(initializer_list<value_type> __l)
188      {
189	_Base::assign(__l);
190	this->_M_invalidate_all();
191      }
192#endif
193
194      using _Base::get_allocator;
195
196      // iterators:
197      iterator
198      begin() _GLIBCXX_NOEXCEPT
199      { return iterator(_Base::begin(), this); }
200
201      const_iterator
202      begin() const _GLIBCXX_NOEXCEPT
203      { return const_iterator(_Base::begin(), this); }
204
205      iterator
206      end() _GLIBCXX_NOEXCEPT
207      { return iterator(_Base::end(), this); }
208
209      const_iterator
210      end() const _GLIBCXX_NOEXCEPT
211      { return const_iterator(_Base::end(), this); }
212
213      reverse_iterator
214      rbegin() _GLIBCXX_NOEXCEPT
215      { return reverse_iterator(end()); }
216
217      const_reverse_iterator
218      rbegin() const _GLIBCXX_NOEXCEPT
219      { return const_reverse_iterator(end()); }
220
221      reverse_iterator
222      rend() _GLIBCXX_NOEXCEPT
223      { return reverse_iterator(begin()); }
224
225      const_reverse_iterator
226      rend() const _GLIBCXX_NOEXCEPT
227      { return const_reverse_iterator(begin()); }
228
229#if __cplusplus >= 201103L
230      const_iterator
231      cbegin() const noexcept
232      { return const_iterator(_Base::begin(), this); }
233
234      const_iterator
235      cend() const noexcept
236      { return const_iterator(_Base::end(), this); }
237
238      const_reverse_iterator
239      crbegin() const noexcept
240      { return const_reverse_iterator(end()); }
241
242      const_reverse_iterator
243      crend() const noexcept
244      { return const_reverse_iterator(begin()); }
245#endif
246
247    private:
248      void
249      _M_invalidate_after_nth(difference_type __n)
250      {
251	typedef __gnu_debug::_After_nth_from<_Base_const_iterator> _After_nth;
252	this->_M_invalidate_if(_After_nth(__n, _Base::begin()));
253      }
254
255    public:
256      // 23.2.1.2 capacity:
257      using _Base::size;
258      using _Base::max_size;
259
260#if __cplusplus >= 201103L
261      void
262      resize(size_type __sz)
263      {
264	bool __invalidate_all = __sz > this->size();
265	if (__sz < this->size())
266	  this->_M_invalidate_after_nth(__sz);
267
268	_Base::resize(__sz);
269
270	if (__invalidate_all)
271	  this->_M_invalidate_all();
272      }
273
274      void
275      resize(size_type __sz, const _Tp& __c)
276      {
277	bool __invalidate_all = __sz > this->size();
278	if (__sz < this->size())
279	  this->_M_invalidate_after_nth(__sz);
280
281	_Base::resize(__sz, __c);
282
283	if (__invalidate_all)
284	  this->_M_invalidate_all();
285      }
286#else
287      void
288      resize(size_type __sz, _Tp __c = _Tp())
289      {
290	bool __invalidate_all = __sz > this->size();
291	if (__sz < this->size())
292	  this->_M_invalidate_after_nth(__sz);
293
294	_Base::resize(__sz, __c);
295
296	if (__invalidate_all)
297	  this->_M_invalidate_all();
298      }
299#endif
300
301#if __cplusplus >= 201103L
302      void
303      shrink_to_fit() noexcept
304      {
305	if (_Base::_M_shrink_to_fit())
306	  this->_M_invalidate_all();
307      }
308#endif
309
310      using _Base::empty;
311
312      // element access:
313      reference
314      operator[](size_type __n) _GLIBCXX_NOEXCEPT
315      {
316	__glibcxx_check_subscript(__n);
317	return _M_base()[__n];
318      }
319
320      const_reference
321      operator[](size_type __n) const _GLIBCXX_NOEXCEPT
322      {
323	__glibcxx_check_subscript(__n);
324	return _M_base()[__n];
325      }
326
327      using _Base::at;
328
329      reference
330      front() _GLIBCXX_NOEXCEPT
331      {
332	__glibcxx_check_nonempty();
333	return _Base::front();
334      }
335
336      const_reference
337      front() const _GLIBCXX_NOEXCEPT
338      {
339	__glibcxx_check_nonempty();
340	return _Base::front();
341      }
342
343      reference
344      back() _GLIBCXX_NOEXCEPT
345      {
346	__glibcxx_check_nonempty();
347	return _Base::back();
348      }
349
350      const_reference
351      back() const _GLIBCXX_NOEXCEPT
352      {
353	__glibcxx_check_nonempty();
354	return _Base::back();
355      }
356
357      // 23.2.1.3 modifiers:
358      void
359      push_front(const _Tp& __x)
360      {
361	_Base::push_front(__x);
362	this->_M_invalidate_all();
363      }
364
365      void
366      push_back(const _Tp& __x)
367      {
368	_Base::push_back(__x);
369	this->_M_invalidate_all();
370      }
371
372#if __cplusplus >= 201103L
373      void
374      push_front(_Tp&& __x)
375      { emplace_front(std::move(__x)); }
376
377      void
378      push_back(_Tp&& __x)
379      { emplace_back(std::move(__x)); }
380
381      template<typename... _Args>
382	void
383	emplace_front(_Args&&... __args)
384	{
385	  _Base::emplace_front(std::forward<_Args>(__args)...);
386	  this->_M_invalidate_all();
387	}
388
389      template<typename... _Args>
390	void
391	emplace_back(_Args&&... __args)
392	{
393	  _Base::emplace_back(std::forward<_Args>(__args)...);
394	  this->_M_invalidate_all();
395	}
396
397      template<typename... _Args>
398	iterator
399	emplace(const_iterator __position, _Args&&... __args)
400	{
401	  __glibcxx_check_insert(__position);
402	  _Base_iterator __res = _Base::emplace(__position.base(),
403						std::forward<_Args>(__args)...);
404	  this->_M_invalidate_all();
405	  return iterator(__res, this);
406	}
407#endif
408
409      iterator
410#if __cplusplus >= 201103L
411      insert(const_iterator __position, const _Tp& __x)
412#else
413      insert(iterator __position, const _Tp& __x)
414#endif
415      {
416	__glibcxx_check_insert(__position);
417	_Base_iterator __res = _Base::insert(__position.base(), __x);
418	this->_M_invalidate_all();
419	return iterator(__res, this);
420      }
421
422#if __cplusplus >= 201103L
423      iterator
424      insert(const_iterator __position, _Tp&& __x)
425      { return emplace(__position, std::move(__x)); }
426
427      iterator
428      insert(const_iterator __position, initializer_list<value_type> __l)
429      {
430	__glibcxx_check_insert(__position);
431	_Base_iterator __res = _Base::insert(__position.base(), __l);
432	this->_M_invalidate_all();
433	return iterator(__res, this);
434      }
435#endif
436
437#if __cplusplus >= 201103L
438      iterator
439      insert(const_iterator __position, size_type __n, const _Tp& __x)
440      {
441	__glibcxx_check_insert(__position);
442	_Base_iterator __res = _Base::insert(__position.base(), __n, __x);
443	this->_M_invalidate_all();
444	return iterator(__res, this);
445      }
446#else
447      void
448      insert(iterator __position, size_type __n, const _Tp& __x)
449      {
450	__glibcxx_check_insert(__position);
451	_Base::insert(__position.base(), __n, __x);
452	this->_M_invalidate_all();
453      }
454#endif
455
456#if __cplusplus >= 201103L
457      template<class _InputIterator,
458	       typename = std::_RequireInputIter<_InputIterator>>
459	iterator
460	insert(const_iterator __position,
461	       _InputIterator __first, _InputIterator __last)
462	{
463	  __glibcxx_check_insert_range(__position, __first, __last);
464	  _Base_iterator __res = _Base::insert(__position.base(),
465					       __gnu_debug::__base(__first),
466					       __gnu_debug::__base(__last));
467	  this->_M_invalidate_all();
468	  return iterator(__res, this);
469	}
470#else
471      template<class _InputIterator>
472	void
473	insert(iterator __position,
474	       _InputIterator __first, _InputIterator __last)
475	{
476	  __glibcxx_check_insert_range(__position, __first, __last);
477	  _Base::insert(__position.base(), __gnu_debug::__base(__first),
478					   __gnu_debug::__base(__last));
479	  this->_M_invalidate_all();
480	}
481#endif
482
483      void
484      pop_front() _GLIBCXX_NOEXCEPT
485      {
486	__glibcxx_check_nonempty();
487	this->_M_invalidate_if(_Equal(_Base::begin()));
488	_Base::pop_front();
489      }
490
491      void
492      pop_back() _GLIBCXX_NOEXCEPT
493      {
494	__glibcxx_check_nonempty();
495	this->_M_invalidate_if(_Equal(--_Base::end()));
496	_Base::pop_back();
497      }
498
499      iterator
500#if __cplusplus >= 201103L
501      erase(const_iterator __position)
502#else
503      erase(iterator __position)
504#endif
505      {
506	__glibcxx_check_erase(__position);
507#if __cplusplus >= 201103L
508	_Base_const_iterator __victim = __position.base();
509#else
510	_Base_iterator __victim = __position.base();
511#endif
512	if (__victim == _Base::begin() || __victim == _Base::end() - 1)
513	  {
514	    this->_M_invalidate_if(_Equal(__victim));
515	    return iterator(_Base::erase(__victim), this);
516	  }
517	else
518	  {
519	    _Base_iterator __res = _Base::erase(__victim);
520	    this->_M_invalidate_all();
521	    return iterator(__res, this);
522	  }
523      }
524
525      iterator
526#if __cplusplus >= 201103L
527      erase(const_iterator __first, const_iterator __last)
528#else
529      erase(iterator __first, iterator __last)
530#endif
531      {
532	// _GLIBCXX_RESOLVE_LIB_DEFECTS
533	// 151. can't currently clear() empty container
534	__glibcxx_check_erase_range(__first, __last);
535
536	if (__first.base() == __last.base())
537#if __cplusplus >= 201103L
538	  return iterator(__first.base()._M_const_cast(), this);
539#else
540	  return __first;
541#endif
542	else if (__first.base() == _Base::begin()
543		 || __last.base() == _Base::end())
544	  {
545	    this->_M_detach_singular();
546	    for (_Base_const_iterator __position = __first.base();
547		 __position != __last.base(); ++__position)
548	      {
549		this->_M_invalidate_if(_Equal(__position));
550	      }
551	    __try
552	      {
553		return iterator(_Base::erase(__first.base(), __last.base()),
554				this);
555	      }
556	    __catch(...)
557	      {
558		this->_M_revalidate_singular();
559		__throw_exception_again;
560	      }
561	  }
562	else
563	  {
564	    _Base_iterator __res = _Base::erase(__first.base(),
565						__last.base());
566	    this->_M_invalidate_all();
567	    return iterator(__res, this);
568	  }
569      }
570
571      void
572      swap(deque& __x)
573#if __cplusplus >= 201103L
574	noexcept( noexcept(declval<_Base>().swap(__x)) )
575#endif
576      {
577	_Safe::_M_swap(__x);
578	_Base::swap(__x);
579      }
580
581      void
582      clear() _GLIBCXX_NOEXCEPT
583      {
584	_Base::clear();
585	this->_M_invalidate_all();
586      }
587
588      _Base&
589      _M_base() _GLIBCXX_NOEXCEPT	{ return *this; }
590
591      const _Base&
592      _M_base() const _GLIBCXX_NOEXCEPT	{ return *this; }
593    };
594
595  template<typename _Tp, typename _Alloc>
596    inline bool
597    operator==(const deque<_Tp, _Alloc>& __lhs,
598	       const deque<_Tp, _Alloc>& __rhs)
599    { return __lhs._M_base() == __rhs._M_base(); }
600
601  template<typename _Tp, typename _Alloc>
602    inline bool
603    operator!=(const deque<_Tp, _Alloc>& __lhs,
604	       const deque<_Tp, _Alloc>& __rhs)
605    { return __lhs._M_base() != __rhs._M_base(); }
606
607  template<typename _Tp, typename _Alloc>
608    inline bool
609    operator<(const deque<_Tp, _Alloc>& __lhs,
610	      const deque<_Tp, _Alloc>& __rhs)
611    { return __lhs._M_base() < __rhs._M_base(); }
612
613  template<typename _Tp, typename _Alloc>
614    inline bool
615    operator<=(const deque<_Tp, _Alloc>& __lhs,
616	       const deque<_Tp, _Alloc>& __rhs)
617    { return __lhs._M_base() <= __rhs._M_base(); }
618
619  template<typename _Tp, typename _Alloc>
620    inline bool
621    operator>=(const deque<_Tp, _Alloc>& __lhs,
622	       const deque<_Tp, _Alloc>& __rhs)
623    { return __lhs._M_base() >= __rhs._M_base(); }
624
625  template<typename _Tp, typename _Alloc>
626    inline bool
627    operator>(const deque<_Tp, _Alloc>& __lhs,
628	      const deque<_Tp, _Alloc>& __rhs)
629    { return __lhs._M_base() > __rhs._M_base(); }
630
631  template<typename _Tp, typename _Alloc>
632    inline void
633    swap(deque<_Tp, _Alloc>& __lhs, deque<_Tp, _Alloc>& __rhs)
634    { __lhs.swap(__rhs); }
635
636} // namespace __debug
637} // namespace std
638
639#endif
640