deque revision 132720 
1// Debugging deque implementation -*- C++ -*-
2
3// Copyright (C) 2003, 2004
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 2, 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// You should have received a copy of the GNU General Public License along
18// with this library; see the file COPYING.  If not, write to the Free
19// Software Foundation, 59 Temple Place - Suite 330, Boston, MA 02111-1307,
20// USA.
21
22// As a special exception, you may use this file as part of a free software
23// library without restriction.  Specifically, if other files instantiate
24// templates or use macros or inline functions from this file, or you compile
25// this file and link it with other files to produce an executable, this
26// file does not by itself cause the resulting executable to be covered by
27// the GNU General Public License.  This exception does not however
28// invalidate any other reasons why the executable file might be covered by
29// the GNU General Public License.
30
31#ifndef _GLIBCXX_DEBUG_DEQUE
32#define _GLIBCXX_DEBUG_DEQUE 1
33
34#include <deque>
35#include <debug/safe_sequence.h>
36#include <debug/safe_iterator.h>
37
38namespace __gnu_debug_def
39{
40  template<typename _Tp, typename _Allocator = std::allocator<_Tp> >
41    class deque
42    : public _GLIBCXX_STD::deque<_Tp, _Allocator>,
43      public __gnu_debug::_Safe_sequence<deque<_Tp, _Allocator> >
44    {
45      typedef  _GLIBCXX_STD::deque<_Tp, _Allocator> _Base;
46      typedef __gnu_debug::_Safe_sequence<deque> _Safe_base;
47
48    public:
49      typedef typename _Allocator::reference        reference;
50      typedef typename _Allocator::const_reference  const_reference;
51
52      typedef __gnu_debug::_Safe_iterator<typename _Base::iterator,deque>
53						    iterator;
54      typedef __gnu_debug::_Safe_iterator<typename _Base::const_iterator,deque>
55						     const_iterator;
56
57      typedef typename _Base::size_type             size_type;
58      typedef typename _Base::difference_type       difference_type;
59
60      typedef _Tp				    value_type;
61      typedef _Allocator			    allocator_type;
62      typedef typename _Allocator::pointer          pointer;
63      typedef typename _Allocator::const_pointer    const_pointer;
64      typedef std::reverse_iterator<iterator>       reverse_iterator;
65      typedef std::reverse_iterator<const_iterator> const_reverse_iterator;
66
67      // 23.2.1.1 construct/copy/destroy:
68      explicit deque(const _Allocator& __a = _Allocator())
69      : _Base(__a) { }
70
71      explicit deque(size_type __n, const _Tp& __value = _Tp(),
72		     const _Allocator& __a = _Allocator())
73      : _Base(__n, __value, __a) { }
74
75      template<class _InputIterator>
76        deque(_InputIterator __first, _InputIterator __last,
77	      const _Allocator& __a = _Allocator())
78	: _Base(__gnu_debug::__check_valid_range(__first, __last), __last, __a)
79        { }
80
81      deque(const deque<_Tp,_Allocator>& __x) : _Base(__x), _Safe_base() { }
82
83      deque(const _Base& __x) : _Base(__x), _Safe_base() { }
84
85      ~deque() { }
86
87      deque<_Tp,_Allocator>&
88      operator=(const deque<_Tp,_Allocator>& __x)
89      {
90	*static_cast<_Base*>(this) = __x;
91	this->_M_invalidate_all();
92	return *this;
93      }
94
95      template<class _InputIterator>
96        void
97        assign(_InputIterator __first, _InputIterator __last)
98        {
99	  __glibcxx_check_valid_range(__first, __last);
100	  _Base::assign(__first, __last);
101	  this->_M_invalidate_all();
102	}
103
104      void
105      assign(size_type __n, const _Tp& __t)
106      {
107	_Base::assign(__n, __t);
108	this->_M_invalidate_all();
109      }
110
111      using _Base::get_allocator;
112
113      // iterators:
114      iterator
115      begin()
116      { return iterator(_Base::begin(), this); }
117
118      const_iterator
119      begin() const
120      { return const_iterator(_Base::begin(), this); }
121
122      iterator
123      end()
124      { return iterator(_Base::end(), this); }
125
126      const_iterator
127      end() const
128      { return const_iterator(_Base::end(), this); }
129
130      reverse_iterator
131      rbegin()
132      { return reverse_iterator(end()); }
133
134      const_reverse_iterator
135      rbegin() const
136      { return const_reverse_iterator(end()); }
137
138      reverse_iterator
139      rend()
140      { return reverse_iterator(begin()); }
141
142      const_reverse_iterator
143      rend() const
144      { return const_reverse_iterator(begin()); }
145
146      // 23.2.1.2 capacity:
147      using _Base::size;
148      using _Base::max_size;
149
150      void
151      resize(size_type __sz, _Tp __c = _Tp())
152      {
153	typedef typename _Base::const_iterator _Base_const_iterator;
154	typedef __gnu_debug::_After_nth_from<_Base_const_iterator> _After_nth;
155
156	bool __invalidate_all = __sz > this->size();
157	if (__sz < this->size())
158	  this->_M_invalidate_if(_After_nth(__sz, _M_base().begin()));
159
160	_Base::resize(__sz, __c);
161
162	if (__invalidate_all)
163	  this->_M_invalidate_all();
164      }
165
166      using _Base::empty;
167
168      // element access:
169      reference
170      operator[](size_type __n)
171      {
172	__glibcxx_check_subscript(__n);
173	return _M_base()[__n];
174      }
175
176      const_reference
177      operator[](size_type __n) const
178      {
179	__glibcxx_check_subscript(__n);
180	return _M_base()[__n];
181      }
182
183      using _Base::at;
184
185      reference
186      front()
187      {
188	__glibcxx_check_nonempty();
189	return _Base::front();
190      }
191
192      const_reference
193      front() const
194      {
195	__glibcxx_check_nonempty();
196	return _Base::front();
197      }
198
199      reference
200      back()
201      {
202	__glibcxx_check_nonempty();
203	return _Base::back();
204      }
205
206      const_reference
207      back() const
208      {
209	__glibcxx_check_nonempty();
210	return _Base::back();
211      }
212
213      // 23.2.1.3 modifiers:
214      void
215      push_front(const _Tp& __x)
216      {
217	_Base::push_front(__x);
218	this->_M_invalidate_all();
219      }
220
221      void
222      push_back(const _Tp& __x)
223      {
224	_Base::push_back(__x);
225	this->_M_invalidate_all();
226      }
227
228      iterator
229      insert(iterator __position, const _Tp& __x)
230      {
231	__glibcxx_check_insert(__position);
232	typename _Base::iterator __res = _Base::insert(__position.base(), __x);
233	this->_M_invalidate_all();
234	return iterator(__res, this);
235      }
236
237      void
238      insert(iterator __position, size_type __n, const _Tp& __x)
239      {
240	__glibcxx_check_insert(__position);
241	_Base::insert(__position.base(), __n, __x);
242	this->_M_invalidate_all();
243      }
244
245      template<class _InputIterator>
246        void
247        insert(iterator __position,
248	       _InputIterator __first, _InputIterator __last)
249        {
250	  __glibcxx_check_insert_range(__position, __first, __last);
251	  _Base::insert(__position.base(), __first, __last);
252	  this->_M_invalidate_all();
253	}
254
255      void
256      pop_front()
257      {
258	__glibcxx_check_nonempty();
259	iterator __victim = begin();
260	__victim._M_invalidate();
261	_Base::pop_front();
262      }
263
264      void
265      pop_back()
266      {
267	__glibcxx_check_nonempty();
268	iterator __victim = end();
269	--__victim;
270	__victim._M_invalidate();
271	_Base::pop_back();
272      }
273
274      iterator
275      erase(iterator __position)
276      {
277	__glibcxx_check_erase(__position);
278	if (__position == begin() || __position == end()-1)
279	  {
280	    __position._M_invalidate();
281	    return iterator(_Base::erase(__position.base()), this);
282	  }
283	else
284	  {
285	    typename _Base::iterator __res = _Base::erase(__position.base());
286	    this->_M_invalidate_all();
287	    return iterator(__res, this);
288	  }
289      }
290
291      iterator
292      erase(iterator __first, iterator __last)
293      {
294	// _GLIBCXX_RESOLVE_LIB_DEFECTS
295	// 151. can't currently clear() empty container
296	__glibcxx_check_erase_range(__first, __last);
297        if (__first == begin() || __last == end())
298	  {
299	    this->_M_detach_singular();
300	    for (iterator __position = __first; __position != __last; )
301	      {
302		iterator __victim = __position++;
303		__victim._M_invalidate();
304	      }
305	    try
306	      {
307		return iterator(_Base::erase(__first.base(), __last.base()),
308				this);
309	      }
310	    catch (...)
311	      {
312		this->_M_revalidate_singular();
313		__throw_exception_again;
314	      }
315	  }
316	else
317	  {
318	    typename _Base::iterator __res = _Base::erase(__first.base(),
319							  __last.base());
320	    this->_M_invalidate_all();
321	    return iterator(__res, this);
322	  }
323      }
324
325      void
326      swap(deque<_Tp,_Allocator>& __x)
327      {
328	_Base::swap(__x);
329	this->_M_swap(__x);
330      }
331
332      void
333      clear()
334      {
335	_Base::clear();
336	this->_M_invalidate_all();
337      }
338
339      _Base&
340      _M_base()       { return *this; }
341
342      const _Base&
343      _M_base() const { return *this; }
344    };
345
346  template<typename _Tp, typename _Alloc>
347    inline bool
348    operator==(const deque<_Tp, _Alloc>& __lhs,
349	       const deque<_Tp, _Alloc>& __rhs)
350    { return __lhs._M_base() == __rhs._M_base(); }
351
352  template<typename _Tp, typename _Alloc>
353    inline bool
354    operator!=(const deque<_Tp, _Alloc>& __lhs,
355	       const deque<_Tp, _Alloc>& __rhs)
356    { return __lhs._M_base() != __rhs._M_base(); }
357
358  template<typename _Tp, typename _Alloc>
359    inline bool
360    operator<(const deque<_Tp, _Alloc>& __lhs, const deque<_Tp, _Alloc>& __rhs)
361    { return __lhs._M_base() < __rhs._M_base(); }
362
363  template<typename _Tp, typename _Alloc>
364    inline bool
365    operator<=(const deque<_Tp, _Alloc>& __lhs,
366	       const deque<_Tp, _Alloc>& __rhs)
367    { return __lhs._M_base() <= __rhs._M_base(); }
368
369  template<typename _Tp, typename _Alloc>
370    inline bool
371    operator>=(const deque<_Tp, _Alloc>& __lhs,
372	       const deque<_Tp, _Alloc>& __rhs)
373    { return __lhs._M_base() >= __rhs._M_base(); }
374
375  template<typename _Tp, typename _Alloc>
376    inline bool
377    operator>(const deque<_Tp, _Alloc>& __lhs, const deque<_Tp, _Alloc>& __rhs)
378    { return __lhs._M_base() > __rhs._M_base(); }
379
380  template<typename _Tp, typename _Alloc>
381    inline void
382    swap(deque<_Tp, _Alloc>& __lhs, deque<_Tp, _Alloc>& __rhs)
383    { __lhs.swap(__rhs); }
384} // namespace __gnu_debug_def
385
386#endif
387