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