// Debugging list implementation -*- C++ -*-
-// Copyright (C) 2003, 2004, 2005
+// Copyright (C) 2003, 2004, 2005, 2006, 2007, 2008, 2009, 2010
// Free Software Foundation, Inc.
//
// This file is part of the GNU ISO C++ Library. This library is free
// software; you can redistribute it and/or modify it under the
// terms of the GNU General Public License as published by the
-// Free Software Foundation; either version 2, or (at your option)
+// Free Software Foundation; either version 3, or (at your option)
// any later version.
// This library is distributed in the hope that it will be useful,
// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
// GNU General Public License for more details.
-// You should have received a copy of the GNU General Public License along
-// with this library; see the file COPYING. If not, write to the Free
-// Software Foundation, 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301,
-// USA.
+// Under Section 7 of GPL version 3, you are granted additional
+// permissions described in the GCC Runtime Library Exception, version
+// 3.1, as published by the Free Software Foundation.
-// As a special exception, you may use this file as part of a free software
-// library without restriction. Specifically, if other files instantiate
-// templates or use macros or inline functions from this file, or you compile
-// this file and link it with other files to produce an executable, this
-// file does not by itself cause the resulting executable to be covered by
-// the GNU General Public License. This exception does not however
-// invalidate any other reasons why the executable file might be covered by
-// the GNU General Public License.
+// You should have received a copy of the GNU General Public License and
+// a copy of the GCC Runtime Library Exception along with this program;
+// see the files COPYING3 and COPYING.RUNTIME respectively. If not, see
+// <http://www.gnu.org/licenses/>.
+
+/** @file debug/list
+ * This file is a GNU debug extension to the Standard C++ Library.
+ */
#ifndef _GLIBCXX_DEBUG_LIST
#define _GLIBCXX_DEBUG_LIST 1
#include <list>
-#include <bits/stl_algo.h>
#include <debug/safe_sequence.h>
#include <debug/safe_iterator.h>
-namespace std
+namespace std _GLIBCXX_VISIBILITY(default)
{
-namespace __gnu_debug_def
+namespace __debug
{
+ /// Class std::list with safety/checking/debug instrumentation.
template<typename _Tp, typename _Allocator = std::allocator<_Tp> >
class list
- : public _GLIBCXX_STD::list<_Tp, _Allocator>,
+ : public _GLIBCXX_STD_C::list<_Tp, _Allocator>,
public __gnu_debug::_Safe_sequence<list<_Tp, _Allocator> >
{
- typedef _GLIBCXX_STD::list<_Tp, _Allocator> _Base;
+ typedef _GLIBCXX_STD_C::list<_Tp, _Allocator> _Base;
typedef __gnu_debug::_Safe_sequence<list> _Safe_base;
+ typedef typename _Base::iterator _Base_iterator;
+ typedef typename _Base::const_iterator _Base_const_iterator;
+ typedef __gnu_debug::_Equal_to<_Base_const_iterator> _Equal;
+ typedef __gnu_debug::_Not_equal_to<_Base_const_iterator> _Not_equal;
public:
typedef typename _Base::reference reference;
typedef typename _Base::const_reference const_reference;
- typedef __gnu_debug::_Safe_iterator<typename _Base::iterator, list>
+ typedef __gnu_debug::_Safe_iterator<_Base_iterator, list>
iterator;
- typedef __gnu_debug::_Safe_iterator<typename _Base::const_iterator, list>
+ typedef __gnu_debug::_Safe_iterator<_Base_const_iterator, list>
const_iterator;
typedef typename _Base::size_type size_type;
typedef std::reverse_iterator<const_iterator> const_reverse_iterator;
// 23.2.2.1 construct/copy/destroy:
- explicit list(const _Allocator& __a = _Allocator())
+ explicit
+ list(const _Allocator& __a = _Allocator())
: _Base(__a) { }
- explicit list(size_type __n, const _Tp& __value = _Tp(),
- const _Allocator& __a = _Allocator())
+#ifdef __GXX_EXPERIMENTAL_CXX0X__
+ explicit
+ list(size_type __n)
+ : _Base(__n) { }
+
+ list(size_type __n, const _Tp& __value,
+ const _Allocator& __a = _Allocator())
+ : _Base(__n, __value, __a) { }
+#else
+ explicit
+ list(size_type __n, const _Tp& __value = _Tp(),
+ const _Allocator& __a = _Allocator())
: _Base(__n, __value, __a) { }
+#endif
template<class _InputIterator>
list(_InputIterator __first, _InputIterator __last,
const _Allocator& __a = _Allocator())
- : _Base(__gnu_debug::__check_valid_range(__first, __last), __last, __a)
+ : _Base(__gnu_debug::__base(__gnu_debug::__check_valid_range(__first,
+ __last)),
+ __gnu_debug::__base(__last), __a)
{ }
- list(const list& __x) : _Base(__x), _Safe_base() { }
+ list(const list& __x)
+ : _Base(__x), _Safe_base() { }
+
+ list(const _Base& __x)
+ : _Base(__x), _Safe_base() { }
- list(const _Base& __x) : _Base(__x), _Safe_base() { }
+#ifdef __GXX_EXPERIMENTAL_CXX0X__
+ list(list&& __x)
+ : _Base(std::move(__x)), _Safe_base()
+ { this->_M_swap(__x); }
+
+ list(initializer_list<value_type> __l,
+ const allocator_type& __a = allocator_type())
+ : _Base(__l, __a), _Safe_base() { }
+#endif
~list() { }
return *this;
}
+#ifdef __GXX_EXPERIMENTAL_CXX0X__
+ list&
+ operator=(list&& __x)
+ {
+ // NB: DR 1204.
+ // NB: DR 675.
+ clear();
+ swap(__x);
+ return *this;
+ }
+
+ list&
+ operator=(initializer_list<value_type> __l)
+ {
+ static_cast<_Base&>(*this) = __l;
+ this->_M_invalidate_all();
+ return *this;
+ }
+
+ void
+ assign(initializer_list<value_type> __l)
+ {
+ _Base::assign(__l);
+ this->_M_invalidate_all();
+ }
+#endif
+
template<class _InputIterator>
void
assign(_InputIterator __first, _InputIterator __last)
{
__glibcxx_check_valid_range(__first, __last);
- _Base::assign(__first, __last);
+ _Base::assign(__gnu_debug::__base(__first),
+ __gnu_debug::__base(__last));
this->_M_invalidate_all();
}
rend() const
{ return const_reverse_iterator(begin()); }
+#ifdef __GXX_EXPERIMENTAL_CXX0X__
+ const_iterator
+ cbegin() const
+ { return const_iterator(_Base::begin(), this); }
+
+ const_iterator
+ cend() const
+ { return const_iterator(_Base::end(), this); }
+
+ const_reverse_iterator
+ crbegin() const
+ { return const_reverse_iterator(end()); }
+
+ const_reverse_iterator
+ crend() const
+ { return const_reverse_iterator(begin()); }
+#endif
+
// 23.2.2.2 capacity:
using _Base::empty;
using _Base::size;
using _Base::max_size;
+#ifdef __GXX_EXPERIMENTAL_CXX0X__
+ void
+ resize(size_type __sz)
+ {
+ this->_M_detach_singular();
+
+ // if __sz < size(), invalidate all iterators in [begin+__sz, end())
+ _Base_iterator __victim = _Base::begin();
+ _Base_iterator __end = _Base::end();
+ for (size_type __i = __sz; __victim != __end && __i > 0; --__i)
+ ++__victim;
+
+ for (; __victim != __end; ++__victim)
+ {
+ this->_M_invalidate_if(_Equal(__victim));
+ }
+
+ __try
+ {
+ _Base::resize(__sz);
+ }
+ __catch(...)
+ {
+ this->_M_revalidate_singular();
+ __throw_exception_again;
+ }
+ }
+
+ void
+ resize(size_type __sz, const _Tp& __c)
+ {
+ this->_M_detach_singular();
+
+ // if __sz < size(), invalidate all iterators in [begin+__sz, end())
+ _Base_iterator __victim = _Base::begin();
+ _Base_iterator __end = _Base::end();
+ for (size_type __i = __sz; __victim != __end && __i > 0; --__i)
+ ++__victim;
+
+ for (; __victim != __end; ++__victim)
+ {
+ this->_M_invalidate_if(_Equal(__victim));
+ }
+
+ __try
+ {
+ _Base::resize(__sz, __c);
+ }
+ __catch(...)
+ {
+ this->_M_revalidate_singular();
+ __throw_exception_again;
+ }
+ }
+#else
void
resize(size_type __sz, _Tp __c = _Tp())
{
this->_M_detach_singular();
// if __sz < size(), invalidate all iterators in [begin+__sz, end())
- iterator __victim = begin();
- iterator __end = end();
+ _Base_iterator __victim = _Base::begin();
+ _Base_iterator __end = _Base::end();
for (size_type __i = __sz; __victim != __end && __i > 0; --__i)
++__victim;
- while (__victim != __end)
+ for (; __victim != __end; ++__victim)
{
- iterator __real_victim = __victim++;
- __real_victim._M_invalidate();
+ this->_M_invalidate_if(_Equal(__victim));
}
- try
+ __try
{
_Base::resize(__sz, __c);
}
- catch(...)
+ __catch(...)
{
this->_M_revalidate_singular();
__throw_exception_again;
}
}
+#endif
// element access:
reference
// 23.2.2.3 modifiers:
using _Base::push_front;
+#ifdef __GXX_EXPERIMENTAL_CXX0X__
+ using _Base::emplace_front;
+#endif
+
void
pop_front()
{
__glibcxx_check_nonempty();
- iterator __victim = begin();
- __victim._M_invalidate();
+ this->_M_invalidate_if(_Equal(_Base::begin()));
_Base::pop_front();
}
using _Base::push_back;
+#ifdef __GXX_EXPERIMENTAL_CXX0X__
+ using _Base::emplace_back;
+#endif
+
void
pop_back()
{
__glibcxx_check_nonempty();
- iterator __victim = end();
- --__victim;
- __victim._M_invalidate();
+ this->_M_invalidate_if(_Equal(--_Base::end()));
_Base::pop_back();
}
+#ifdef __GXX_EXPERIMENTAL_CXX0X__
+ template<typename... _Args>
+ iterator
+ emplace(iterator __position, _Args&&... __args)
+ {
+ __glibcxx_check_insert(__position);
+ return iterator(_Base::emplace(__position.base(),
+ std::forward<_Args>(__args)...), this);
+ }
+#endif
+
iterator
insert(iterator __position, const _Tp& __x)
{
return iterator(_Base::insert(__position.base(), __x), this);
}
+#ifdef __GXX_EXPERIMENTAL_CXX0X__
+ iterator
+ insert(iterator __position, _Tp&& __x)
+ { return emplace(__position, std::move(__x)); }
+
+ void
+ insert(iterator __p, initializer_list<value_type> __l)
+ {
+ __glibcxx_check_insert(__p);
+ _Base::insert(__p, __l);
+ }
+#endif
+
void
insert(iterator __position, size_type __n, const _Tp& __x)
{
_InputIterator __last)
{
__glibcxx_check_insert_range(__position, __first, __last);
- _Base::insert(__position.base(), __first, __last);
+ _Base::insert(__position.base(), __gnu_debug::__base(__first),
+ __gnu_debug::__base(__last));
}
+ private:
+ _Base_iterator
+ _M_erase(_Base_iterator __position)
+ {
+ this->_M_invalidate_if(_Equal(__position));
+ return _Base::erase(__position);
+ }
+ public:
iterator
erase(iterator __position)
{
__glibcxx_check_erase(__position);
- __position._M_invalidate();
- return iterator(_Base::erase(__position.base()), this);
+ return iterator(_M_erase(__position.base()), this);
}
iterator
// _GLIBCXX_RESOLVE_LIB_DEFECTS
// 151. can't currently clear() empty container
__glibcxx_check_erase_range(__position, __last);
- for (iterator __victim = __position; __victim != __last; )
+ for (_Base_iterator __victim = __position.base();
+ __victim != __last.base(); ++__victim)
{
- iterator __old = __victim;
- ++__victim;
- __old._M_invalidate();
+ _GLIBCXX_DEBUG_VERIFY(__victim != _Base::end(),
+ _M_message(__gnu_debug::__msg_valid_range)
+ ._M_iterator(__position, "position")
+ ._M_iterator(__last, "last"));
+ this->_M_invalidate_if(_Equal(__victim));
}
return iterator(_Base::erase(__position.base(), __last.base()), this);
}
// 23.2.2.4 list operations:
void
+#ifdef __GXX_EXPERIMENTAL_CXX0X__
+ splice(iterator __position, list&& __x)
+#else
splice(iterator __position, list& __x)
+#endif
{
_GLIBCXX_DEBUG_VERIFY(&__x != this,
_M_message(__gnu_debug::__msg_self_splice)
._M_sequence(*this, "this"));
- this->splice(__position, __x, __x.begin(), __x.end());
+ this->_M_transfer_from_if(__x, _Not_equal(__x._M_base().end()));
+ _Base::splice(__position.base(), _GLIBCXX_MOVE(__x._M_base()));
}
+#ifdef __GXX_EXPERIMENTAL_CXX0X__
void
+ splice(iterator __position, list& __x)
+ { splice(__position, std::move(__x)); }
+#endif
+
+ void
+#ifdef __GXX_EXPERIMENTAL_CXX0X__
+ splice(iterator __position, list&& __x, iterator __i)
+#else
splice(iterator __position, list& __x, iterator __i)
+#endif
{
__glibcxx_check_insert(__position);
- _GLIBCXX_DEBUG_VERIFY(__x.get_allocator() == this->get_allocator(),
- _M_message(__gnu_debug::__msg_splice_alloc)
- ._M_sequence(*this)._M_sequence(__x, "__x"));
+
+ // We used to perform the splice_alloc check: not anymore, redundant
+ // after implementing the relevant bits of N1599.
+
_GLIBCXX_DEBUG_VERIFY(__i._M_dereferenceable(),
_M_message(__gnu_debug::__msg_splice_bad)
._M_iterator(__i, "__i"));
// _GLIBCXX_RESOLVE_LIB_DEFECTS
// 250. splicing invalidates iterators
- this->_M_transfer_iter(__i);
- _Base::splice(__position.base(), __x._M_base(), __i.base());
+ this->_M_transfer_from_if(__x, _Equal(__i.base()));
+ _Base::splice(__position.base(), _GLIBCXX_MOVE(__x._M_base()),
+ __i.base());
}
+#ifdef __GXX_EXPERIMENTAL_CXX0X__
void
- splice(iterator __position, list& __x, iterator __first, iterator __last)
+ splice(iterator __position, list& __x, iterator __i)
+ { splice(__position, std::move(__x), __i); }
+#endif
+
+ void
+#ifdef __GXX_EXPERIMENTAL_CXX0X__
+ splice(iterator __position, list&& __x, iterator __first,
+ iterator __last)
+#else
+ splice(iterator __position, list& __x, iterator __first,
+ iterator __last)
+#endif
{
__glibcxx_check_insert(__position);
__glibcxx_check_valid_range(__first, __last);
_M_message(__gnu_debug::__msg_splice_other)
._M_sequence(__x, "x")
._M_iterator(__first, "first"));
- _GLIBCXX_DEBUG_VERIFY(__x.get_allocator() == this->get_allocator(),
- _M_message(__gnu_debug::__msg_splice_alloc)
- ._M_sequence(*this)._M_sequence(__x));
- for (iterator __tmp = __first; __tmp != __last; )
+ // We used to perform the splice_alloc check: not anymore, redundant
+ // after implementing the relevant bits of N1599.
+
+ for (_Base_iterator __tmp = __first.base();
+ __tmp != __last.base(); ++__tmp)
{
+ _GLIBCXX_DEBUG_VERIFY(__tmp != _Base::end(),
+ _M_message(__gnu_debug::__msg_valid_range)
+ ._M_iterator(__first, "first")
+ ._M_iterator(__last, "last"));
_GLIBCXX_DEBUG_VERIFY(&__x != this || __tmp != __position,
_M_message(__gnu_debug::__msg_splice_overlap)
._M_iterator(__tmp, "position")
._M_iterator(__first, "first")
._M_iterator(__last, "last"));
- iterator __victim = __tmp++;
// _GLIBCXX_RESOLVE_LIB_DEFECTS
// 250. splicing invalidates iterators
- this->_M_transfer_iter(__victim);
+ this->_M_transfer_from_if(__x, _Equal(__tmp));
}
- _Base::splice(__position.base(), __x._M_base(), __first.base(),
- __last.base());
+ _Base::splice(__position.base(), _GLIBCXX_MOVE(__x._M_base()),
+ __first.base(), __last.base());
}
+#ifdef __GXX_EXPERIMENTAL_CXX0X__
+ void
+ splice(iterator __position, list& __x, iterator __first, iterator __last)
+ { splice(__position, std::move(__x), __first, __last); }
+#endif
+
void
remove(const _Tp& __value)
{
- for (iterator __x = begin(); __x.base() != _Base::end(); )
+ for (_Base_iterator __x = _Base::begin(); __x != _Base::end(); )
{
if (*__x == __value)
- __x = erase(__x);
+ __x = _M_erase(__x);
else
++__x;
}
void
remove_if(_Predicate __pred)
{
- for (iterator __x = begin(); __x.base() != _Base::end(); )
+ for (_Base_iterator __x = _Base::begin(); __x != _Base::end(); )
{
if (__pred(*__x))
- __x = erase(__x);
+ __x = _M_erase(__x);
else
++__x;
}
void
unique()
{
- iterator __first = begin();
- iterator __last = end();
+ _Base_iterator __first = _Base::begin();
+ _Base_iterator __last = _Base::end();
if (__first == __last)
return;
- iterator __next = __first;
- while (++__next != __last)
+ _Base_iterator __next = __first; ++__next;
+ while (__next != __last)
{
if (*__first == *__next)
- erase(__next);
+ __next = _M_erase(__next);
else
- __first = __next;
- __next = __first;
+ __first = __next++;
}
}
void
unique(_BinaryPredicate __binary_pred)
{
- iterator __first = begin();
- iterator __last = end();
+ _Base_iterator __first = _Base::begin();
+ _Base_iterator __last = _Base::end();
if (__first == __last)
return;
- iterator __next = __first;
- while (++__next != __last)
+ _Base_iterator __next = __first; ++__next;
+ while (__next != __last)
{
if (__binary_pred(*__first, *__next))
- erase(__next);
+ __next = _M_erase(__next);
else
- __first = __next;
- __next = __first;
+ __first = __next++;
}
}
void
+#ifdef __GXX_EXPERIMENTAL_CXX0X__
+ merge(list&& __x)
+#else
merge(list& __x)
+#endif
{
- __glibcxx_check_sorted(_Base::begin(), _Base::end());
- __glibcxx_check_sorted(__x.begin().base(), __x.end().base());
- for (iterator __tmp = __x.begin(); __tmp != __x.end(); )
+ // _GLIBCXX_RESOLVE_LIB_DEFECTS
+ // 300. list::merge() specification incomplete
+ if (this != &__x)
{
- iterator __victim = __tmp++;
- __victim._M_attach(&__x);
+ __glibcxx_check_sorted(_Base::begin(), _Base::end());
+ __glibcxx_check_sorted(__x.begin().base(), __x.end().base());
+ this->_M_transfer_from_if(__x, _Not_equal(__x._M_base().end()));
+ _Base::merge(_GLIBCXX_MOVE(__x._M_base()));
}
- _Base::merge(__x._M_base());
}
+#ifdef __GXX_EXPERIMENTAL_CXX0X__
+ void
+ merge(list& __x)
+ { merge(std::move(__x)); }
+#endif
+
template<class _Compare>
void
+#ifdef __GXX_EXPERIMENTAL_CXX0X__
+ merge(list&& __x, _Compare __comp)
+#else
merge(list& __x, _Compare __comp)
+#endif
{
- __glibcxx_check_sorted_pred(_Base::begin(), _Base::end(), __comp);
- __glibcxx_check_sorted_pred(__x.begin().base(), __x.end().base(),
- __comp);
- for (iterator __tmp = __x.begin(); __tmp != __x.end(); )
+ // _GLIBCXX_RESOLVE_LIB_DEFECTS
+ // 300. list::merge() specification incomplete
+ if (this != &__x)
{
- iterator __victim = __tmp++;
- __victim._M_attach(&__x);
+ __glibcxx_check_sorted_pred(_Base::begin(), _Base::end(),
+ __comp);
+ __glibcxx_check_sorted_pred(__x.begin().base(), __x.end().base(),
+ __comp);
+ this->_M_transfer_from_if(__x, _Not_equal(__x._M_base().end()));
+ _Base::merge(_GLIBCXX_MOVE(__x._M_base()), __comp);
}
- _Base::merge(__x._M_base(), __comp);
}
+#ifdef __GXX_EXPERIMENTAL_CXX0X__
+ template<typename _Compare>
+ void
+ merge(list& __x, _Compare __comp)
+ { merge(std::move(__x), __comp); }
+#endif
+
void
sort() { _Base::sort(); }
void
_M_invalidate_all()
{
- typedef typename _Base::const_iterator _Base_const_iterator;
- typedef __gnu_debug::_Not_equal_to<_Base_const_iterator> _Not_equal;
- this->_M_invalidate_if(_Not_equal(_M_base().end()));
+ this->_M_invalidate_if(_Not_equal(_Base::end()));
}
};
template<typename _Tp, typename _Alloc>
inline bool
- operator==(const list<_Tp, _Alloc>& __lhs, const list<_Tp, _Alloc>& __rhs)
+ operator==(const list<_Tp, _Alloc>& __lhs,
+ const list<_Tp, _Alloc>& __rhs)
{ return __lhs._M_base() == __rhs._M_base(); }
template<typename _Tp, typename _Alloc>
inline bool
- operator!=(const list<_Tp, _Alloc>& __lhs, const list<_Tp, _Alloc>& __rhs)
+ operator!=(const list<_Tp, _Alloc>& __lhs,
+ const list<_Tp, _Alloc>& __rhs)
{ return __lhs._M_base() != __rhs._M_base(); }
template<typename _Tp, typename _Alloc>
inline bool
- operator<(const list<_Tp, _Alloc>& __lhs, const list<_Tp, _Alloc>& __rhs)
+ operator<(const list<_Tp, _Alloc>& __lhs,
+ const list<_Tp, _Alloc>& __rhs)
{ return __lhs._M_base() < __rhs._M_base(); }
template<typename _Tp, typename _Alloc>
inline bool
- operator<=(const list<_Tp, _Alloc>& __lhs, const list<_Tp, _Alloc>& __rhs)
+ operator<=(const list<_Tp, _Alloc>& __lhs,
+ const list<_Tp, _Alloc>& __rhs)
{ return __lhs._M_base() <= __rhs._M_base(); }
template<typename _Tp, typename _Alloc>
inline bool
- operator>=(const list<_Tp, _Alloc>& __lhs, const list<_Tp, _Alloc>& __rhs)
+ operator>=(const list<_Tp, _Alloc>& __lhs,
+ const list<_Tp, _Alloc>& __rhs)
{ return __lhs._M_base() >= __rhs._M_base(); }
template<typename _Tp, typename _Alloc>
inline bool
- operator>(const list<_Tp, _Alloc>& __lhs, const list<_Tp, _Alloc>& __rhs)
+ operator>(const list<_Tp, _Alloc>& __lhs,
+ const list<_Tp, _Alloc>& __rhs)
{ return __lhs._M_base() > __rhs._M_base(); }
template<typename _Tp, typename _Alloc>
inline void
swap(list<_Tp, _Alloc>& __lhs, list<_Tp, _Alloc>& __rhs)
{ __lhs.swap(__rhs); }
-} // namespace __gnu_debug_def
+
+} // namespace __debug
} // namespace std
#endif
OSDN Git Service
