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