1// Debugging deque implementation -*- C++ -*-
2
3// Copyright (C) 2003, 2004, 2005, 2006, 2007, 2008, 2009, 2010, 2011
4// Free Software Foundation, Inc.
5//
6// This file is part of the GNU ISO C++ Library.  This library is free
7// software; you can redistribute it and/or modify it under the
8// terms of the GNU General Public License as published by the
9// Free Software Foundation; either version 3, or (at your option)
10// any later version.
11
12// This library is distributed in the hope that it will be useful,
13// but WITHOUT ANY WARRANTY; without even the implied warranty of
14// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
15// GNU General Public License for more details.
16
17// Under Section 7 of GPL version 3, you are granted additional
18// permissions described in the GCC Runtime Library Exception, version
19// 3.1, as published by the Free Software Foundation.
20
21// You should have received a copy of the GNU General Public License and
22// a copy of the GCC Runtime Library Exception along with this program;
23// see the files COPYING3 and COPYING.RUNTIME respectively.  If not, see
24// <http://www.gnu.org/licenses/>.
25
26/** @file debug/deque
27 *  This file is a GNU debug extension to the Standard C++ Library.
28 */
29
30#ifndef _GLIBCXX_DEBUG_DEQUE
31#define _GLIBCXX_DEBUG_DEQUE 1
32
33#include <deque>
34#include <debug/safe_sequence.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 _GLIBCXX_STD_C::deque<_Tp, _Allocator>,
45      public __gnu_debug::_Safe_sequence<deque<_Tp, _Allocator> >
46    {
47      typedef  _GLIBCXX_STD_C::deque<_Tp, _Allocator> _Base;
48
49      typedef typename _Base::const_iterator _Base_const_iterator;
50      typedef typename _Base::iterator _Base_iterator;
51      typedef __gnu_debug::_Equal_to<_Base_const_iterator> _Equal;
52    public:
53      typedef typename _Base::reference             reference;
54      typedef typename _Base::const_reference       const_reference;
55
56      typedef __gnu_debug::_Safe_iterator<_Base_iterator,deque>
57						    iterator;
58      typedef __gnu_debug::_Safe_iterator<_Base_const_iterator,deque>
59						    const_iterator;
60
61      typedef typename _Base::size_type             size_type;
62      typedef typename _Base::difference_type       difference_type;
63
64      typedef _Tp				    value_type;
65      typedef _Allocator			    allocator_type;
66      typedef typename _Base::pointer               pointer;
67      typedef typename _Base::const_pointer         const_pointer;
68      typedef std::reverse_iterator<iterator>       reverse_iterator;
69      typedef std::reverse_iterator<const_iterator> const_reverse_iterator;
70
71      // 23.2.1.1 construct/copy/destroy:
72      explicit
73      deque(const _Allocator& __a = _Allocator())
74      : _Base(__a) { }
75
76#ifdef __GXX_EXPERIMENTAL_CXX0X__
77      explicit
78      deque(size_type __n)
79      : _Base(__n) { }
80
81      deque(size_type __n, const _Tp& __value,
82	    const _Allocator& __a = _Allocator())
83      : _Base(__n, __value, __a) { }
84#else
85      explicit
86      deque(size_type __n, const _Tp& __value = _Tp(),
87	    const _Allocator& __a = _Allocator())
88      : _Base(__n, __value, __a) { }
89#endif
90
91      template<class _InputIterator>
92        deque(_InputIterator __first, _InputIterator __last,
93	      const _Allocator& __a = _Allocator())
94	: _Base(__gnu_debug::__base(__gnu_debug::__check_valid_range(__first,
95								     __last)),
96		__gnu_debug::__base(__last), __a)
97        { }
98
99      deque(const deque& __x)
100      : _Base(__x) { }
101
102      deque(const _Base& __x)
103      : _Base(__x) { }
104
105#ifdef __GXX_EXPERIMENTAL_CXX0X__
106      deque(deque&& __x)
107      : _Base(std::move(__x))
108      { this->_M_swap(__x); }
109
110      deque(initializer_list<value_type> __l,
111	    const allocator_type& __a = allocator_type())
112      : _Base(__l, __a) { }
113#endif
114
115      ~deque() _GLIBCXX_NOEXCEPT { }
116
117      deque&
118      operator=(const deque& __x)
119      {
120	*static_cast<_Base*>(this) = __x;
121	this->_M_invalidate_all();
122	return *this;
123      }
124
125#ifdef __GXX_EXPERIMENTAL_CXX0X__
126      deque&
127      operator=(deque&& __x)
128      {
129	// NB: DR 1204.
130	// NB: DR 675.
131	clear();
132	swap(__x);
133	return *this;
134      }
135
136      deque&
137      operator=(initializer_list<value_type> __l)
138      {
139	*static_cast<_Base*>(this) = __l;
140	this->_M_invalidate_all();
141	return *this;
142      }
143#endif
144
145      template<class _InputIterator>
146        void
147        assign(_InputIterator __first, _InputIterator __last)
148        {
149	  __glibcxx_check_valid_range(__first, __last);
150	  _Base::assign(__gnu_debug::__base(__first),
151			__gnu_debug::__base(__last));
152	  this->_M_invalidate_all();
153	}
154
155      void
156      assign(size_type __n, const _Tp& __t)
157      {
158	_Base::assign(__n, __t);
159	this->_M_invalidate_all();
160      }
161
162#ifdef __GXX_EXPERIMENTAL_CXX0X__
163      void
164      assign(initializer_list<value_type> __l)
165      {
166	_Base::assign(__l);
167	this->_M_invalidate_all();
168      }
169#endif
170
171      using _Base::get_allocator;
172
173      // iterators:
174      iterator
175      begin() _GLIBCXX_NOEXCEPT
176      { return iterator(_Base::begin(), this); }
177
178      const_iterator
179      begin() const _GLIBCXX_NOEXCEPT
180      { return const_iterator(_Base::begin(), this); }
181
182      iterator
183      end() _GLIBCXX_NOEXCEPT
184      { return iterator(_Base::end(), this); }
185
186      const_iterator
187      end() const _GLIBCXX_NOEXCEPT
188      { return const_iterator(_Base::end(), this); }
189
190      reverse_iterator
191      rbegin() _GLIBCXX_NOEXCEPT
192      { return reverse_iterator(end()); }
193
194      const_reverse_iterator
195      rbegin() const _GLIBCXX_NOEXCEPT
196      { return const_reverse_iterator(end()); }
197
198      reverse_iterator
199      rend() _GLIBCXX_NOEXCEPT
200      { return reverse_iterator(begin()); }
201
202      const_reverse_iterator
203      rend() const _GLIBCXX_NOEXCEPT
204      { return const_reverse_iterator(begin()); }
205
206#ifdef __GXX_EXPERIMENTAL_CXX0X__
207      const_iterator
208      cbegin() const noexcept
209      { return const_iterator(_Base::begin(), this); }
210
211      const_iterator
212      cend() const noexcept
213      { return const_iterator(_Base::end(), this); }
214
215      const_reverse_iterator
216      crbegin() const noexcept
217      { return const_reverse_iterator(end()); }
218
219      const_reverse_iterator
220      crend() const noexcept
221      { return const_reverse_iterator(begin()); }
222#endif
223
224    private:
225      void
226      _M_invalidate_after_nth(difference_type __n)
227      {
228	typedef __gnu_debug::_After_nth_from<_Base_const_iterator> _After_nth;
229	this->_M_invalidate_if(_After_nth(__n, _Base::begin()));
230      }
231
232    public:
233      // 23.2.1.2 capacity:
234      using _Base::size;
235      using _Base::max_size;
236
237#ifdef __GXX_EXPERIMENTAL_CXX0X__
238      void
239      resize(size_type __sz)
240      {
241	bool __invalidate_all = __sz > this->size();
242	if (__sz < this->size())
243	  this->_M_invalidate_after_nth(__sz);
244
245	_Base::resize(__sz);
246
247	if (__invalidate_all)
248	  this->_M_invalidate_all();
249      }
250
251      void
252      resize(size_type __sz, const _Tp& __c)
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, __c);
259
260	if (__invalidate_all)
261	  this->_M_invalidate_all();
262      }
263#else
264      void
265      resize(size_type __sz, _Tp __c = _Tp())
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#endif
277
278#ifdef __GXX_EXPERIMENTAL_CXX0X__
279      void
280      shrink_to_fit()
281      {
282	if (_Base::_M_shrink_to_fit())
283	  this->_M_invalidate_all();
284      }
285#endif
286
287      using _Base::empty;
288
289      // element access:
290      reference
291      operator[](size_type __n)
292      {
293	__glibcxx_check_subscript(__n);
294	return _M_base()[__n];
295      }
296
297      const_reference
298      operator[](size_type __n) const
299      {
300	__glibcxx_check_subscript(__n);
301	return _M_base()[__n];
302      }
303
304      using _Base::at;
305
306      reference
307      front()
308      {
309	__glibcxx_check_nonempty();
310	return _Base::front();
311      }
312
313      const_reference
314      front() const
315      {
316	__glibcxx_check_nonempty();
317	return _Base::front();
318      }
319
320      reference
321      back()
322      {
323	__glibcxx_check_nonempty();
324	return _Base::back();
325      }
326
327      const_reference
328      back() const
329      {
330	__glibcxx_check_nonempty();
331	return _Base::back();
332      }
333
334      // 23.2.1.3 modifiers:
335      void
336      push_front(const _Tp& __x)
337      {
338	_Base::push_front(__x);
339	this->_M_invalidate_all();
340      }
341
342      void
343      push_back(const _Tp& __x)
344      {
345	_Base::push_back(__x);
346	this->_M_invalidate_all();
347      }
348
349#ifdef __GXX_EXPERIMENTAL_CXX0X__
350      void
351      push_front(_Tp&& __x)
352      { emplace_front(std::move(__x)); }
353
354      void
355      push_back(_Tp&& __x)
356      { emplace_back(std::move(__x)); }
357
358      template<typename... _Args>
359        void
360        emplace_front(_Args&&... __args)
361	{
362	  _Base::emplace_front(std::forward<_Args>(__args)...);
363	  this->_M_invalidate_all();
364	}
365
366      template<typename... _Args>
367        void
368        emplace_back(_Args&&... __args)
369	{
370	  _Base::emplace_back(std::forward<_Args>(__args)...);
371	  this->_M_invalidate_all();
372	}
373
374      template<typename... _Args>
375        iterator
376        emplace(iterator __position, _Args&&... __args)
377	{
378	  __glibcxx_check_insert(__position);
379	  _Base_iterator __res = _Base::emplace(__position.base(),
380						std::forward<_Args>(__args)...);
381	  this->_M_invalidate_all();
382	  return iterator(__res, this);
383	}
384#endif
385
386      iterator
387      insert(iterator __position, const _Tp& __x)
388      {
389	__glibcxx_check_insert(__position);
390	_Base_iterator __res = _Base::insert(__position.base(), __x);
391	this->_M_invalidate_all();
392	return iterator(__res, this);
393      }
394
395#ifdef __GXX_EXPERIMENTAL_CXX0X__
396      iterator
397      insert(iterator __position, _Tp&& __x)
398      { return emplace(__position, std::move(__x)); }
399
400      void
401      insert(iterator __p, initializer_list<value_type> __l)
402      {
403	_Base::insert(__p, __l);
404	this->_M_invalidate_all();
405      }
406#endif
407
408      void
409      insert(iterator __position, size_type __n, const _Tp& __x)
410      {
411	__glibcxx_check_insert(__position);
412	_Base::insert(__position.base(), __n, __x);
413	this->_M_invalidate_all();
414      }
415
416      template<class _InputIterator>
417        void
418        insert(iterator __position,
419	       _InputIterator __first, _InputIterator __last)
420        {
421	  __glibcxx_check_insert_range(__position, __first, __last);
422	  _Base::insert(__position.base(), __gnu_debug::__base(__first),
423					   __gnu_debug::__base(__last));
424	  this->_M_invalidate_all();
425	}
426
427      void
428      pop_front()
429      {
430	__glibcxx_check_nonempty();
431	this->_M_invalidate_if(_Equal(_Base::begin()));
432	_Base::pop_front();
433      }
434
435      void
436      pop_back()
437      {
438	__glibcxx_check_nonempty();
439	this->_M_invalidate_if(_Equal(--_Base::end()));
440	_Base::pop_back();
441      }
442
443      iterator
444      erase(iterator __position)
445      {
446	__glibcxx_check_erase(__position);
447	_Base_iterator __victim = __position.base();
448	if (__victim == _Base::begin() || __victim == _Base::end()-1)
449	  {
450	    this->_M_invalidate_if(_Equal(__victim));
451	    return iterator(_Base::erase(__victim), this);
452	  }
453	else
454	  {
455	    _Base_iterator __res = _Base::erase(__victim);
456	    this->_M_invalidate_all();
457	    return iterator(__res, this);
458	  }
459      }
460
461      iterator
462      erase(iterator __first, iterator __last)
463      {
464	// _GLIBCXX_RESOLVE_LIB_DEFECTS
465	// 151. can't currently clear() empty container
466	__glibcxx_check_erase_range(__first, __last);
467
468	if (__first.base() == __last.base())
469	  return __first;
470        else if (__first.base() == _Base::begin()
471		 || __last.base() == _Base::end())
472	  {
473	    this->_M_detach_singular();
474	    for (_Base_iterator __position = __first.base();
475		 __position != __last.base(); ++__position)
476	      {
477		this->_M_invalidate_if(_Equal(__position));
478	      }
479	    __try
480	      {
481		return iterator(_Base::erase(__first.base(), __last.base()),
482				this);
483	      }
484	    __catch(...)
485	      {
486		this->_M_revalidate_singular();
487		__throw_exception_again;
488	      }
489	  }
490	else
491	  {
492	    _Base_iterator __res = _Base::erase(__first.base(),
493						__last.base());
494	    this->_M_invalidate_all();
495	    return iterator(__res, this);
496	  }
497      }
498
499      void
500      swap(deque& __x)
501      {
502	_Base::swap(__x);
503	this->_M_swap(__x);
504      }
505
506      void
507      clear() _GLIBCXX_NOEXCEPT
508      {
509	_Base::clear();
510	this->_M_invalidate_all();
511      }
512
513      _Base&
514      _M_base() _GLIBCXX_NOEXCEPT       { return *this; }
515
516      const _Base&
517      _M_base() const _GLIBCXX_NOEXCEPT { return *this; }
518    };
519
520  template<typename _Tp, typename _Alloc>
521    inline bool
522    operator==(const deque<_Tp, _Alloc>& __lhs,
523	       const deque<_Tp, _Alloc>& __rhs)
524    { return __lhs._M_base() == __rhs._M_base(); }
525
526  template<typename _Tp, typename _Alloc>
527    inline bool
528    operator!=(const deque<_Tp, _Alloc>& __lhs,
529	       const deque<_Tp, _Alloc>& __rhs)
530    { return __lhs._M_base() != __rhs._M_base(); }
531
532  template<typename _Tp, typename _Alloc>
533    inline bool
534    operator<(const deque<_Tp, _Alloc>& __lhs,
535	      const deque<_Tp, _Alloc>& __rhs)
536    { return __lhs._M_base() < __rhs._M_base(); }
537
538  template<typename _Tp, typename _Alloc>
539    inline bool
540    operator<=(const deque<_Tp, _Alloc>& __lhs,
541	       const deque<_Tp, _Alloc>& __rhs)
542    { return __lhs._M_base() <= __rhs._M_base(); }
543
544  template<typename _Tp, typename _Alloc>
545    inline bool
546    operator>=(const deque<_Tp, _Alloc>& __lhs,
547	       const deque<_Tp, _Alloc>& __rhs)
548    { return __lhs._M_base() >= __rhs._M_base(); }
549
550  template<typename _Tp, typename _Alloc>
551    inline bool
552    operator>(const deque<_Tp, _Alloc>& __lhs,
553	      const deque<_Tp, _Alloc>& __rhs)
554    { return __lhs._M_base() > __rhs._M_base(); }
555
556  template<typename _Tp, typename _Alloc>
557    inline void
558    swap(deque<_Tp, _Alloc>& __lhs, deque<_Tp, _Alloc>& __rhs)
559    { __lhs.swap(__rhs); }
560
561} // namespace __debug
562} // namespace std
563
564#endif
565