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