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