libstdc++
debug/deque
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 
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 
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