1 // Debugging list implementation -*- C++ -*-
3 // Copyright (C) 2003, 2004, 2005, 2006, 2007, 2008, 2009, 2010
4 // Free Software Foundation, Inc.
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)
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.
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.
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/>.
27 * This file is a GNU debug extension to the Standard C++ Library.
30 #ifndef _GLIBCXX_DEBUG_LIST
31 #define _GLIBCXX_DEBUG_LIST 1
34 #include <debug/safe_sequence.h>
35 #include <debug/safe_iterator.h>
41 /// Class std::list with safety/checking/debug instrumentation.
42 template<typename _Tp, typename _Allocator = std::allocator<_Tp> >
44 : public _GLIBCXX_STD_D::list<_Tp, _Allocator>,
45 public __gnu_debug::_Safe_sequence<list<_Tp, _Allocator> >
47 typedef _GLIBCXX_STD_D::list<_Tp, _Allocator> _Base;
48 typedef __gnu_debug::_Safe_sequence<list> _Safe_base;
51 typedef typename _Base::reference reference;
52 typedef typename _Base::const_reference const_reference;
54 typedef __gnu_debug::_Safe_iterator<typename _Base::iterator, list>
56 typedef __gnu_debug::_Safe_iterator<typename _Base::const_iterator, list>
59 typedef typename _Base::size_type size_type;
60 typedef typename _Base::difference_type difference_type;
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;
69 // 23.2.2.1 construct/copy/destroy:
70 explicit list(const _Allocator& __a = _Allocator())
73 explicit list(size_type __n, const _Tp& __value = _Tp(),
74 const _Allocator& __a = _Allocator())
75 : _Base(__n, __value, __a) { }
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)
85 : _Base(__x), _Safe_base() { }
87 list(const _Base& __x)
88 : _Base(__x), _Safe_base() { }
90 #ifdef __GXX_EXPERIMENTAL_CXX0X__
92 : _Base(std::forward<list>(__x)), _Safe_base()
93 { this->_M_swap(__x); }
95 list(initializer_list<value_type> __l,
96 const allocator_type& __a = allocator_type())
97 : _Base(__l, __a), _Safe_base() { }
103 operator=(const list& __x)
105 static_cast<_Base&>(*this) = __x;
106 this->_M_invalidate_all();
110 #ifdef __GXX_EXPERIMENTAL_CXX0X__
112 operator=(list&& __x)
122 operator=(initializer_list<value_type> __l)
124 static_cast<_Base&>(*this) = __l;
125 this->_M_invalidate_all();
130 assign(initializer_list<value_type> __l)
133 this->_M_invalidate_all();
137 template<class _InputIterator>
139 assign(_InputIterator __first, _InputIterator __last)
141 __glibcxx_check_valid_range(__first, __last);
142 _Base::assign(__first, __last);
143 this->_M_invalidate_all();
147 assign(size_type __n, const _Tp& __t)
149 _Base::assign(__n, __t);
150 this->_M_invalidate_all();
153 using _Base::get_allocator;
158 { return iterator(_Base::begin(), this); }
162 { return const_iterator(_Base::begin(), this); }
166 { return iterator(_Base::end(), this); }
170 { return const_iterator(_Base::end(), this); }
174 { return reverse_iterator(end()); }
176 const_reverse_iterator
178 { return const_reverse_iterator(end()); }
182 { return reverse_iterator(begin()); }
184 const_reverse_iterator
186 { return const_reverse_iterator(begin()); }
188 #ifdef __GXX_EXPERIMENTAL_CXX0X__
191 { return const_iterator(_Base::begin(), this); }
195 { return const_iterator(_Base::end(), this); }
197 const_reverse_iterator
199 { return const_reverse_iterator(end()); }
201 const_reverse_iterator
203 { return const_reverse_iterator(begin()); }
206 // 23.2.2.2 capacity:
209 using _Base::max_size;
212 resize(size_type __sz, _Tp __c = _Tp())
214 this->_M_detach_singular();
216 // if __sz < size(), invalidate all iterators in [begin+__sz, end())
217 iterator __victim = begin();
218 iterator __end = end();
219 for (size_type __i = __sz; __victim != __end && __i > 0; --__i)
222 while (__victim != __end)
224 iterator __real_victim = __victim++;
225 __real_victim._M_invalidate();
230 _Base::resize(__sz, __c);
234 this->_M_revalidate_singular();
235 __throw_exception_again;
243 __glibcxx_check_nonempty();
244 return _Base::front();
250 __glibcxx_check_nonempty();
251 return _Base::front();
257 __glibcxx_check_nonempty();
258 return _Base::back();
264 __glibcxx_check_nonempty();
265 return _Base::back();
268 // 23.2.2.3 modifiers:
269 using _Base::push_front;
271 #ifdef __GXX_EXPERIMENTAL_CXX0X__
272 using _Base::emplace_front;
278 __glibcxx_check_nonempty();
279 iterator __victim = begin();
280 __victim._M_invalidate();
284 using _Base::push_back;
286 #ifdef __GXX_EXPERIMENTAL_CXX0X__
287 using _Base::emplace_back;
293 __glibcxx_check_nonempty();
294 iterator __victim = end();
296 __victim._M_invalidate();
300 #ifdef __GXX_EXPERIMENTAL_CXX0X__
301 template<typename... _Args>
303 emplace(iterator __position, _Args&&... __args)
305 __glibcxx_check_insert(__position);
306 return iterator(_Base::emplace(__position.base(),
307 std::forward<_Args>(__args)...), this);
312 insert(iterator __position, const _Tp& __x)
314 __glibcxx_check_insert(__position);
315 return iterator(_Base::insert(__position.base(), __x), this);
318 #ifdef __GXX_EXPERIMENTAL_CXX0X__
320 insert(iterator __position, _Tp&& __x)
321 { return emplace(__position, std::move(__x)); }
324 insert(iterator __p, initializer_list<value_type> __l)
326 __glibcxx_check_insert(__p);
327 _Base::insert(__p, __l);
332 insert(iterator __position, size_type __n, const _Tp& __x)
334 __glibcxx_check_insert(__position);
335 _Base::insert(__position.base(), __n, __x);
338 template<class _InputIterator>
340 insert(iterator __position, _InputIterator __first,
341 _InputIterator __last)
343 __glibcxx_check_insert_range(__position, __first, __last);
344 _Base::insert(__position.base(), __first, __last);
348 erase(iterator __position)
350 __glibcxx_check_erase(__position);
351 __position._M_invalidate();
352 return iterator(_Base::erase(__position.base()), this);
356 erase(iterator __position, iterator __last)
358 // _GLIBCXX_RESOLVE_LIB_DEFECTS
359 // 151. can't currently clear() empty container
360 __glibcxx_check_erase_range(__position, __last);
361 for (iterator __victim = __position; __victim != __last; )
363 iterator __old = __victim;
365 __old._M_invalidate();
367 return iterator(_Base::erase(__position.base(), __last.base()), this);
381 this->_M_invalidate_all();
384 // 23.2.2.4 list operations:
386 #ifdef __GXX_EXPERIMENTAL_CXX0X__
387 splice(iterator __position, list&& __x)
389 splice(iterator __position, list& __x)
392 _GLIBCXX_DEBUG_VERIFY(&__x != this,
393 _M_message(__gnu_debug::__msg_self_splice)
394 ._M_sequence(*this, "this"));
395 this->splice(__position, _GLIBCXX_MOVE(__x), __x.begin(), __x.end());
398 #ifdef __GXX_EXPERIMENTAL_CXX0X__
400 splice(iterator __position, list& __x)
401 { splice(__position, std::move(__x)); }
405 #ifdef __GXX_EXPERIMENTAL_CXX0X__
406 splice(iterator __position, list&& __x, iterator __i)
408 splice(iterator __position, list& __x, iterator __i)
411 __glibcxx_check_insert(__position);
413 // We used to perform the splice_alloc check: not anymore, redundant
414 // after implementing the relevant bits of N1599.
416 _GLIBCXX_DEBUG_VERIFY(__i._M_dereferenceable(),
417 _M_message(__gnu_debug::__msg_splice_bad)
418 ._M_iterator(__i, "__i"));
419 _GLIBCXX_DEBUG_VERIFY(__i._M_attached_to(&__x),
420 _M_message(__gnu_debug::__msg_splice_other)
421 ._M_iterator(__i, "__i")._M_sequence(__x, "__x"));
423 // _GLIBCXX_RESOLVE_LIB_DEFECTS
424 // 250. splicing invalidates iterators
425 this->_M_transfer_iter(__i);
426 _Base::splice(__position.base(), _GLIBCXX_MOVE(__x._M_base()),
430 #ifdef __GXX_EXPERIMENTAL_CXX0X__
432 splice(iterator __position, list& __x, iterator __i)
433 { splice(__position, std::move(__x), __i); }
437 #ifdef __GXX_EXPERIMENTAL_CXX0X__
438 splice(iterator __position, list&& __x, iterator __first,
441 splice(iterator __position, list& __x, iterator __first,
445 __glibcxx_check_insert(__position);
446 __glibcxx_check_valid_range(__first, __last);
447 _GLIBCXX_DEBUG_VERIFY(__first._M_attached_to(&__x),
448 _M_message(__gnu_debug::__msg_splice_other)
449 ._M_sequence(__x, "x")
450 ._M_iterator(__first, "first"));
452 // We used to perform the splice_alloc check: not anymore, redundant
453 // after implementing the relevant bits of N1599.
455 for (iterator __tmp = __first; __tmp != __last; )
457 _GLIBCXX_DEBUG_VERIFY(&__x != this || __tmp != __position,
458 _M_message(__gnu_debug::__msg_splice_overlap)
459 ._M_iterator(__tmp, "position")
460 ._M_iterator(__first, "first")
461 ._M_iterator(__last, "last"));
462 iterator __victim = __tmp++;
463 // _GLIBCXX_RESOLVE_LIB_DEFECTS
464 // 250. splicing invalidates iterators
465 this->_M_transfer_iter(__victim);
468 _Base::splice(__position.base(), _GLIBCXX_MOVE(__x._M_base()),
469 __first.base(), __last.base());
472 #ifdef __GXX_EXPERIMENTAL_CXX0X__
474 splice(iterator __position, list& __x, iterator __first, iterator __last)
475 { splice(__position, std::move(__x), __first, __last); }
479 remove(const _Tp& __value)
481 for (iterator __x = begin(); __x.base() != _Base::end(); )
490 template<class _Predicate>
492 remove_if(_Predicate __pred)
494 for (iterator __x = begin(); __x.base() != _Base::end(); )
506 iterator __first = begin();
507 iterator __last = end();
508 if (__first == __last)
510 iterator __next = __first;
511 while (++__next != __last)
513 if (*__first == *__next)
521 template<class _BinaryPredicate>
523 unique(_BinaryPredicate __binary_pred)
525 iterator __first = begin();
526 iterator __last = end();
527 if (__first == __last)
529 iterator __next = __first;
530 while (++__next != __last)
532 if (__binary_pred(*__first, *__next))
541 #ifdef __GXX_EXPERIMENTAL_CXX0X__
547 // _GLIBCXX_RESOLVE_LIB_DEFECTS
548 // 300. list::merge() specification incomplete
551 __glibcxx_check_sorted(_Base::begin(), _Base::end());
552 __glibcxx_check_sorted(__x.begin().base(), __x.end().base());
553 for (iterator __tmp = __x.begin(); __tmp != __x.end();)
555 iterator __victim = __tmp++;
556 this->_M_transfer_iter(__victim);
558 _Base::merge(_GLIBCXX_MOVE(__x._M_base()));
562 #ifdef __GXX_EXPERIMENTAL_CXX0X__
565 { merge(std::move(__x)); }
568 template<class _Compare>
570 #ifdef __GXX_EXPERIMENTAL_CXX0X__
571 merge(list&& __x, _Compare __comp)
573 merge(list& __x, _Compare __comp)
576 // _GLIBCXX_RESOLVE_LIB_DEFECTS
577 // 300. list::merge() specification incomplete
580 __glibcxx_check_sorted_pred(_Base::begin(), _Base::end(),
582 __glibcxx_check_sorted_pred(__x.begin().base(), __x.end().base(),
584 for (iterator __tmp = __x.begin(); __tmp != __x.end();)
586 iterator __victim = __tmp++;
587 this->_M_transfer_iter(__victim);
589 _Base::merge(_GLIBCXX_MOVE(__x._M_base()), __comp);
593 #ifdef __GXX_EXPERIMENTAL_CXX0X__
594 template<typename _Compare>
596 merge(list& __x, _Compare __comp)
597 { merge(std::move(__x), __comp); }
601 sort() { _Base::sort(); }
603 template<typename _StrictWeakOrdering>
605 sort(_StrictWeakOrdering __pred) { _Base::sort(__pred); }
607 using _Base::reverse;
610 _M_base() { return *this; }
613 _M_base() const { return *this; }
619 typedef typename _Base::const_iterator _Base_const_iterator;
620 typedef __gnu_debug::_Not_equal_to<_Base_const_iterator> _Not_equal;
621 this->_M_invalidate_if(_Not_equal(_M_base().end()));
625 template<typename _Tp, typename _Alloc>
627 operator==(const list<_Tp, _Alloc>& __lhs,
628 const list<_Tp, _Alloc>& __rhs)
629 { return __lhs._M_base() == __rhs._M_base(); }
631 template<typename _Tp, typename _Alloc>
633 operator!=(const list<_Tp, _Alloc>& __lhs,
634 const list<_Tp, _Alloc>& __rhs)
635 { return __lhs._M_base() != __rhs._M_base(); }
637 template<typename _Tp, typename _Alloc>
639 operator<(const list<_Tp, _Alloc>& __lhs,
640 const list<_Tp, _Alloc>& __rhs)
641 { return __lhs._M_base() < __rhs._M_base(); }
643 template<typename _Tp, typename _Alloc>
645 operator<=(const list<_Tp, _Alloc>& __lhs,
646 const list<_Tp, _Alloc>& __rhs)
647 { return __lhs._M_base() <= __rhs._M_base(); }
649 template<typename _Tp, typename _Alloc>
651 operator>=(const list<_Tp, _Alloc>& __lhs,
652 const list<_Tp, _Alloc>& __rhs)
653 { return __lhs._M_base() >= __rhs._M_base(); }
655 template<typename _Tp, typename _Alloc>
657 operator>(const list<_Tp, _Alloc>& __lhs,
658 const list<_Tp, _Alloc>& __rhs)
659 { return __lhs._M_base() > __rhs._M_base(); }
661 template<typename _Tp, typename _Alloc>
663 swap(list<_Tp, _Alloc>& __lhs, list<_Tp, _Alloc>& __rhs)
664 { __lhs.swap(__rhs); }
666 } // namespace __debug