libstdc++
debug/list
1 // Debugging list 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/list
26  * This file is a GNU debug extension to the Standard C++ Library.
27  */
28 
29 #ifndef _GLIBCXX_DEBUG_LIST
30 #define _GLIBCXX_DEBUG_LIST 1
31 
32 #include <list>
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::list with safety/checking/debug instrumentation.
41  template<typename _Tp, typename _Allocator = std::allocator<_Tp> >
42  class list
43  : public _GLIBCXX_STD_C::list<_Tp, _Allocator>,
44  public __gnu_debug::_Safe_sequence<list<_Tp, _Allocator> >
45  {
46  typedef _GLIBCXX_STD_C::list<_Tp, _Allocator> _Base;
47 
48  typedef typename _Base::iterator _Base_iterator;
49  typedef typename _Base::const_iterator _Base_const_iterator;
50  typedef __gnu_debug::_Equal_to<_Base_const_iterator> _Equal;
51  typedef __gnu_debug::_Not_equal_to<_Base_const_iterator> _Not_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, list>
57  iterator;
58  typedef __gnu_debug::_Safe_iterator<_Base_const_iterator, list>
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.2.1 construct/copy/destroy:
72  explicit
73  list(const _Allocator& __a = _Allocator())
74  : _Base(__a) { }
75 
76 #if __cplusplus >= 201103L
77  explicit
78  list(size_type __n)
79  : _Base(__n) { }
80 
81  list(size_type __n, const _Tp& __value,
82  const _Allocator& __a = _Allocator())
83  : _Base(__n, __value, __a) { }
84 #else
85  explicit
86  list(size_type __n, const _Tp& __value = _Tp(),
87  const _Allocator& __a = _Allocator())
88  : _Base(__n, __value, __a) { }
89 #endif
90 
91 #if __cplusplus >= 201103L
92  template<class _InputIterator,
93  typename = std::_RequireInputIter<_InputIterator>>
94 #else
95  template<class _InputIterator>
96 #endif
97  list(_InputIterator __first, _InputIterator __last,
98  const _Allocator& __a = _Allocator())
99  : _Base(__gnu_debug::__base(__gnu_debug::__check_valid_range(__first,
100  __last)),
101  __gnu_debug::__base(__last), __a)
102  { }
103 
104  list(const list& __x)
105  : _Base(__x) { }
106 
107  list(const _Base& __x)
108  : _Base(__x) { }
109 
110 #if __cplusplus >= 201103L
111  list(list&& __x) noexcept
112  : _Base(std::move(__x))
113  { this->_M_swap(__x); }
114 
115  list(initializer_list<value_type> __l,
116  const allocator_type& __a = allocator_type())
117  : _Base(__l, __a) { }
118 #endif
119 
120  ~list() _GLIBCXX_NOEXCEPT { }
121 
122  list&
123  operator=(const list& __x)
124  {
125  static_cast<_Base&>(*this) = __x;
126  this->_M_invalidate_all();
127  return *this;
128  }
129 
130 #if __cplusplus >= 201103L
131  list&
132  operator=(list&& __x)
133  {
134  // NB: DR 1204.
135  // NB: DR 675.
136  __glibcxx_check_self_move_assign(__x);
137  clear();
138  swap(__x);
139  return *this;
140  }
141 
142  list&
143  operator=(initializer_list<value_type> __l)
144  {
145  static_cast<_Base&>(*this) = __l;
146  this->_M_invalidate_all();
147  return *this;
148  }
149 
150  void
151  assign(initializer_list<value_type> __l)
152  {
153  _Base::assign(__l);
154  this->_M_invalidate_all();
155  }
156 #endif
157 
158 #if __cplusplus >= 201103L
159  template<class _InputIterator,
160  typename = std::_RequireInputIter<_InputIterator>>
161 #else
162  template<class _InputIterator>
163 #endif
164  void
165  assign(_InputIterator __first, _InputIterator __last)
166  {
167  __glibcxx_check_valid_range(__first, __last);
168  _Base::assign(__gnu_debug::__base(__first),
169  __gnu_debug::__base(__last));
170  this->_M_invalidate_all();
171  }
172 
173  void
174  assign(size_type __n, const _Tp& __t)
175  {
176  _Base::assign(__n, __t);
177  this->_M_invalidate_all();
178  }
179 
180  using _Base::get_allocator;
181 
182  // iterators:
183  iterator
184  begin() _GLIBCXX_NOEXCEPT
185  { return iterator(_Base::begin(), this); }
186 
187  const_iterator
188  begin() const _GLIBCXX_NOEXCEPT
189  { return const_iterator(_Base::begin(), this); }
190 
191  iterator
192  end() _GLIBCXX_NOEXCEPT
193  { return iterator(_Base::end(), this); }
194 
195  const_iterator
196  end() const _GLIBCXX_NOEXCEPT
197  { return const_iterator(_Base::end(), this); }
198 
199  reverse_iterator
200  rbegin() _GLIBCXX_NOEXCEPT
201  { return reverse_iterator(end()); }
202 
203  const_reverse_iterator
204  rbegin() const _GLIBCXX_NOEXCEPT
205  { return const_reverse_iterator(end()); }
206 
207  reverse_iterator
208  rend() _GLIBCXX_NOEXCEPT
209  { return reverse_iterator(begin()); }
210 
211  const_reverse_iterator
212  rend() const _GLIBCXX_NOEXCEPT
213  { return const_reverse_iterator(begin()); }
214 
215 #if __cplusplus >= 201103L
216  const_iterator
217  cbegin() const noexcept
218  { return const_iterator(_Base::begin(), this); }
219 
220  const_iterator
221  cend() const noexcept
222  { return const_iterator(_Base::end(), this); }
223 
224  const_reverse_iterator
225  crbegin() const noexcept
226  { return const_reverse_iterator(end()); }
227 
228  const_reverse_iterator
229  crend() const noexcept
230  { return const_reverse_iterator(begin()); }
231 #endif
232 
233  // 23.2.2.2 capacity:
234  using _Base::empty;
235  using _Base::size;
236  using _Base::max_size;
237 
238 #if __cplusplus >= 201103L
239  void
240  resize(size_type __sz)
241  {
242  this->_M_detach_singular();
243 
244  // if __sz < size(), invalidate all iterators in [begin+__sz, end())
245  _Base_iterator __victim = _Base::begin();
246  _Base_iterator __end = _Base::end();
247  for (size_type __i = __sz; __victim != __end && __i > 0; --__i)
248  ++__victim;
249 
250  for (; __victim != __end; ++__victim)
251  {
252  this->_M_invalidate_if(_Equal(__victim));
253  }
254 
255  __try
256  {
257  _Base::resize(__sz);
258  }
259  __catch(...)
260  {
261  this->_M_revalidate_singular();
262  __throw_exception_again;
263  }
264  }
265 
266  void
267  resize(size_type __sz, const _Tp& __c)
268  {
269  this->_M_detach_singular();
270 
271  // if __sz < size(), invalidate all iterators in [begin+__sz, end())
272  _Base_iterator __victim = _Base::begin();
273  _Base_iterator __end = _Base::end();
274  for (size_type __i = __sz; __victim != __end && __i > 0; --__i)
275  ++__victim;
276 
277  for (; __victim != __end; ++__victim)
278  {
279  this->_M_invalidate_if(_Equal(__victim));
280  }
281 
282  __try
283  {
284  _Base::resize(__sz, __c);
285  }
286  __catch(...)
287  {
288  this->_M_revalidate_singular();
289  __throw_exception_again;
290  }
291  }
292 #else
293  void
294  resize(size_type __sz, _Tp __c = _Tp())
295  {
296  this->_M_detach_singular();
297 
298  // if __sz < size(), invalidate all iterators in [begin+__sz, end())
299  _Base_iterator __victim = _Base::begin();
300  _Base_iterator __end = _Base::end();
301  for (size_type __i = __sz; __victim != __end && __i > 0; --__i)
302  ++__victim;
303 
304  for (; __victim != __end; ++__victim)
305  {
306  this->_M_invalidate_if(_Equal(__victim));
307  }
308 
309  __try
310  {
311  _Base::resize(__sz, __c);
312  }
313  __catch(...)
314  {
315  this->_M_revalidate_singular();
316  __throw_exception_again;
317  }
318  }
319 #endif
320 
321  // element access:
322  reference
323  front()
324  {
325  __glibcxx_check_nonempty();
326  return _Base::front();
327  }
328 
329  const_reference
330  front() const
331  {
332  __glibcxx_check_nonempty();
333  return _Base::front();
334  }
335 
336  reference
337  back()
338  {
339  __glibcxx_check_nonempty();
340  return _Base::back();
341  }
342 
343  const_reference
344  back() const
345  {
346  __glibcxx_check_nonempty();
347  return _Base::back();
348  }
349 
350  // 23.2.2.3 modifiers:
351  using _Base::push_front;
352 
353 #if __cplusplus >= 201103L
354  using _Base::emplace_front;
355 #endif
356 
357  void
358  pop_front()
359  {
360  __glibcxx_check_nonempty();
361  this->_M_invalidate_if(_Equal(_Base::begin()));
362  _Base::pop_front();
363  }
364 
365  using _Base::push_back;
366 
367 #if __cplusplus >= 201103L
368  using _Base::emplace_back;
369 #endif
370 
371  void
372  pop_back()
373  {
374  __glibcxx_check_nonempty();
375  this->_M_invalidate_if(_Equal(--_Base::end()));
376  _Base::pop_back();
377  }
378 
379 #if __cplusplus >= 201103L
380  template<typename... _Args>
381  iterator
382  emplace(iterator __position, _Args&&... __args)
383  {
384  __glibcxx_check_insert(__position);
385  return iterator(_Base::emplace(__position.base(),
386  std::forward<_Args>(__args)...), this);
387  }
388 #endif
389 
390  iterator
391  insert(iterator __position, const _Tp& __x)
392  {
393  __glibcxx_check_insert(__position);
394  return iterator(_Base::insert(__position.base(), __x), this);
395  }
396 
397 #if __cplusplus >= 201103L
398  iterator
399  insert(iterator __position, _Tp&& __x)
400  { return emplace(__position, std::move(__x)); }
401 
402  void
403  insert(iterator __p, initializer_list<value_type> __l)
404  {
405  __glibcxx_check_insert(__p);
406  _Base::insert(__p.base(), __l);
407  }
408 #endif
409 
410  void
411  insert(iterator __position, size_type __n, const _Tp& __x)
412  {
413  __glibcxx_check_insert(__position);
414  _Base::insert(__position.base(), __n, __x);
415  }
416 
417 #if __cplusplus >= 201103L
418  template<class _InputIterator,
419  typename = std::_RequireInputIter<_InputIterator>>
420 #else
421  template<class _InputIterator>
422 #endif
423  void
424  insert(iterator __position, _InputIterator __first,
425  _InputIterator __last)
426  {
427  __glibcxx_check_insert_range(__position, __first, __last);
428  _Base::insert(__position.base(), __gnu_debug::__base(__first),
429  __gnu_debug::__base(__last));
430  }
431 
432  private:
433  _Base_iterator
434  _M_erase(_Base_iterator __position)
435  {
436  this->_M_invalidate_if(_Equal(__position));
437  return _Base::erase(__position);
438  }
439  public:
440  iterator
441  erase(iterator __position)
442  {
443  __glibcxx_check_erase(__position);
444  return iterator(_M_erase(__position.base()), this);
445  }
446 
447  iterator
448  erase(iterator __position, iterator __last)
449  {
450  // _GLIBCXX_RESOLVE_LIB_DEFECTS
451  // 151. can't currently clear() empty container
452  __glibcxx_check_erase_range(__position, __last);
453  for (_Base_iterator __victim = __position.base();
454  __victim != __last.base(); ++__victim)
455  {
456  _GLIBCXX_DEBUG_VERIFY(__victim != _Base::end(),
457  _M_message(__gnu_debug::__msg_valid_range)
458  ._M_iterator(__position, "position")
459  ._M_iterator(__last, "last"));
460  this->_M_invalidate_if(_Equal(__victim));
461  }
462  return iterator(_Base::erase(__position.base(), __last.base()), this);
463  }
464 
465  void
466  swap(list& __x)
467  {
468  _Base::swap(__x);
469  this->_M_swap(__x);
470  }
471 
472  void
473  clear() _GLIBCXX_NOEXCEPT
474  {
475  _Base::clear();
476  this->_M_invalidate_all();
477  }
478 
479  // 23.2.2.4 list operations:
480  void
481 #if __cplusplus >= 201103L
482  splice(iterator __position, list&& __x)
483 #else
484  splice(iterator __position, list& __x)
485 #endif
486  {
487  _GLIBCXX_DEBUG_VERIFY(&__x != this,
488  _M_message(__gnu_debug::__msg_self_splice)
489  ._M_sequence(*this, "this"));
490  this->_M_transfer_from_if(__x, _Not_equal(__x._M_base().end()));
491  _Base::splice(__position.base(), _GLIBCXX_MOVE(__x._M_base()));
492  }
493 
494 #if __cplusplus >= 201103L
495  void
496  splice(iterator __position, list& __x)
497  { splice(__position, std::move(__x)); }
498 #endif
499 
500  void
501 #if __cplusplus >= 201103L
502  splice(iterator __position, list&& __x, iterator __i)
503 #else
504  splice(iterator __position, list& __x, iterator __i)
505 #endif
506  {
507  __glibcxx_check_insert(__position);
508 
509  // We used to perform the splice_alloc check: not anymore, redundant
510  // after implementing the relevant bits of N1599.
511 
512  _GLIBCXX_DEBUG_VERIFY(__i._M_dereferenceable(),
513  _M_message(__gnu_debug::__msg_splice_bad)
514  ._M_iterator(__i, "__i"));
515  _GLIBCXX_DEBUG_VERIFY(__i._M_attached_to(&__x),
516  _M_message(__gnu_debug::__msg_splice_other)
517  ._M_iterator(__i, "__i")._M_sequence(__x, "__x"));
518 
519  // _GLIBCXX_RESOLVE_LIB_DEFECTS
520  // 250. splicing invalidates iterators
521  this->_M_transfer_from_if(__x, _Equal(__i.base()));
522  _Base::splice(__position.base(), _GLIBCXX_MOVE(__x._M_base()),
523  __i.base());
524  }
525 
526 #if __cplusplus >= 201103L
527  void
528  splice(iterator __position, list& __x, iterator __i)
529  { splice(__position, std::move(__x), __i); }
530 #endif
531 
532  void
533 #if __cplusplus >= 201103L
534  splice(iterator __position, list&& __x, iterator __first,
535  iterator __last)
536 #else
537  splice(iterator __position, list& __x, iterator __first,
538  iterator __last)
539 #endif
540  {
541  __glibcxx_check_insert(__position);
542  __glibcxx_check_valid_range(__first, __last);
543  _GLIBCXX_DEBUG_VERIFY(__first._M_attached_to(&__x),
544  _M_message(__gnu_debug::__msg_splice_other)
545  ._M_sequence(__x, "x")
546  ._M_iterator(__first, "first"));
547 
548  // We used to perform the splice_alloc check: not anymore, redundant
549  // after implementing the relevant bits of N1599.
550 
551  for (_Base_iterator __tmp = __first.base();
552  __tmp != __last.base(); ++__tmp)
553  {
554  _GLIBCXX_DEBUG_VERIFY(__tmp != _Base::end(),
555  _M_message(__gnu_debug::__msg_valid_range)
556  ._M_iterator(__first, "first")
557  ._M_iterator(__last, "last"));
558  _GLIBCXX_DEBUG_VERIFY(&__x != this || __tmp != __position,
559  _M_message(__gnu_debug::__msg_splice_overlap)
560  ._M_iterator(__tmp, "position")
561  ._M_iterator(__first, "first")
562  ._M_iterator(__last, "last"));
563  // _GLIBCXX_RESOLVE_LIB_DEFECTS
564  // 250. splicing invalidates iterators
565  this->_M_transfer_from_if(__x, _Equal(__tmp));
566  }
567 
568  _Base::splice(__position.base(), _GLIBCXX_MOVE(__x._M_base()),
569  __first.base(), __last.base());
570  }
571 
572 #if __cplusplus >= 201103L
573  void
574  splice(iterator __position, list& __x, iterator __first, iterator __last)
575  { splice(__position, std::move(__x), __first, __last); }
576 #endif
577 
578  void
579  remove(const _Tp& __value)
580  {
581  for (_Base_iterator __x = _Base::begin(); __x != _Base::end(); )
582  {
583  if (*__x == __value)
584  __x = _M_erase(__x);
585  else
586  ++__x;
587  }
588  }
589 
590  template<class _Predicate>
591  void
592  remove_if(_Predicate __pred)
593  {
594  for (_Base_iterator __x = _Base::begin(); __x != _Base::end(); )
595  {
596  if (__pred(*__x))
597  __x = _M_erase(__x);
598  else
599  ++__x;
600  }
601  }
602 
603  void
604  unique()
605  {
606  _Base_iterator __first = _Base::begin();
607  _Base_iterator __last = _Base::end();
608  if (__first == __last)
609  return;
610  _Base_iterator __next = __first; ++__next;
611  while (__next != __last)
612  {
613  if (*__first == *__next)
614  __next = _M_erase(__next);
615  else
616  __first = __next++;
617  }
618  }
619 
620  template<class _BinaryPredicate>
621  void
622  unique(_BinaryPredicate __binary_pred)
623  {
624  _Base_iterator __first = _Base::begin();
625  _Base_iterator __last = _Base::end();
626  if (__first == __last)
627  return;
628  _Base_iterator __next = __first; ++__next;
629  while (__next != __last)
630  {
631  if (__binary_pred(*__first, *__next))
632  __next = _M_erase(__next);
633  else
634  __first = __next++;
635  }
636  }
637 
638  void
639 #if __cplusplus >= 201103L
640  merge(list&& __x)
641 #else
642  merge(list& __x)
643 #endif
644  {
645  // _GLIBCXX_RESOLVE_LIB_DEFECTS
646  // 300. list::merge() specification incomplete
647  if (this != &__x)
648  {
649  __glibcxx_check_sorted(_Base::begin(), _Base::end());
650  __glibcxx_check_sorted(__x.begin().base(), __x.end().base());
651  this->_M_transfer_from_if(__x, _Not_equal(__x._M_base().end()));
652  _Base::merge(_GLIBCXX_MOVE(__x._M_base()));
653  }
654  }
655 
656 #if __cplusplus >= 201103L
657  void
658  merge(list& __x)
659  { merge(std::move(__x)); }
660 #endif
661 
662  template<class _Compare>
663  void
664 #if __cplusplus >= 201103L
665  merge(list&& __x, _Compare __comp)
666 #else
667  merge(list& __x, _Compare __comp)
668 #endif
669  {
670  // _GLIBCXX_RESOLVE_LIB_DEFECTS
671  // 300. list::merge() specification incomplete
672  if (this != &__x)
673  {
674  __glibcxx_check_sorted_pred(_Base::begin(), _Base::end(),
675  __comp);
676  __glibcxx_check_sorted_pred(__x.begin().base(), __x.end().base(),
677  __comp);
678  this->_M_transfer_from_if(__x, _Not_equal(__x._M_base().end()));
679  _Base::merge(_GLIBCXX_MOVE(__x._M_base()), __comp);
680  }
681  }
682 
683 #if __cplusplus >= 201103L
684  template<typename _Compare>
685  void
686  merge(list& __x, _Compare __comp)
687  { merge(std::move(__x), __comp); }
688 #endif
689 
690  void
691  sort() { _Base::sort(); }
692 
693  template<typename _StrictWeakOrdering>
694  void
695  sort(_StrictWeakOrdering __pred) { _Base::sort(__pred); }
696 
697  using _Base::reverse;
698 
699  _Base&
700  _M_base() _GLIBCXX_NOEXCEPT { return *this; }
701 
702  const _Base&
703  _M_base() const _GLIBCXX_NOEXCEPT { return *this; }
704 
705  private:
706  void
707  _M_invalidate_all()
708  {
709  this->_M_invalidate_if(_Not_equal(_Base::end()));
710  }
711  };
712 
713  template<typename _Tp, typename _Alloc>
714  inline bool
715  operator==(const list<_Tp, _Alloc>& __lhs,
716  const list<_Tp, _Alloc>& __rhs)
717  { return __lhs._M_base() == __rhs._M_base(); }
718 
719  template<typename _Tp, typename _Alloc>
720  inline bool
721  operator!=(const list<_Tp, _Alloc>& __lhs,
722  const list<_Tp, _Alloc>& __rhs)
723  { return __lhs._M_base() != __rhs._M_base(); }
724 
725  template<typename _Tp, typename _Alloc>
726  inline bool
727  operator<(const list<_Tp, _Alloc>& __lhs,
728  const list<_Tp, _Alloc>& __rhs)
729  { return __lhs._M_base() < __rhs._M_base(); }
730 
731  template<typename _Tp, typename _Alloc>
732  inline bool
733  operator<=(const list<_Tp, _Alloc>& __lhs,
734  const list<_Tp, _Alloc>& __rhs)
735  { return __lhs._M_base() <= __rhs._M_base(); }
736 
737  template<typename _Tp, typename _Alloc>
738  inline bool
739  operator>=(const list<_Tp, _Alloc>& __lhs,
740  const list<_Tp, _Alloc>& __rhs)
741  { return __lhs._M_base() >= __rhs._M_base(); }
742 
743  template<typename _Tp, typename _Alloc>
744  inline bool
745  operator>(const list<_Tp, _Alloc>& __lhs,
746  const list<_Tp, _Alloc>& __rhs)
747  { return __lhs._M_base() > __rhs._M_base(); }
748 
749  template<typename _Tp, typename _Alloc>
750  inline void
751  swap(list<_Tp, _Alloc>& __lhs, list<_Tp, _Alloc>& __rhs)
752  { __lhs.swap(__rhs); }
753 
754 } // namespace __debug
755 } // namespace std
756 
757 #endif