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