// List implementation -*- C++ -*-
-// Copyright (C) 2001-2013 Free Software Foundation, Inc.
+// Copyright (C) 2001-2014 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
/// See bits/stl_deque.h's _Deque_base for an explanation.
template<typename _Tp, typename _Alloc>
- class _List_base
+ class _GLIBCXX_DEFAULT_ABI_TAG _List_base
{
protected:
// NOTA BENE
typedef typename _Alloc::template rebind<_Tp>::other _Tp_alloc_type;
+ static size_t
+ _S_distance(const __detail::_List_node_base* __first,
+ const __detail::_List_node_base* __last)
+ {
+ size_t __n = 0;
+ while (__first != __last)
+ {
+ __first = __first->_M_next;
+ ++__n;
+ }
+ return __n;
+ }
+
struct _List_impl
: public _Node_alloc_type
{
+#if _GLIBCXX_USE_CXX11_ABI
+ _List_node<size_t> _M_node;
+#else
__detail::_List_node_base _M_node;
+#endif
_List_impl()
: _Node_alloc_type(), _M_node()
_List_impl _M_impl;
+#if _GLIBCXX_USE_CXX11_ABI
+ size_t _M_get_size() const { return _M_impl._M_node._M_data; }
+
+ void _M_set_size(size_t __n) { _M_impl._M_node._M_data = __n; }
+
+ void _M_inc_size(size_t __n) { _M_impl._M_node._M_data += __n; }
+
+ void _M_dec_size(size_t __n) { _M_impl._M_node._M_data -= __n; }
+
+ size_t
+ _M_distance(const __detail::_List_node_base* __first,
+ const __detail::_List_node_base* __last) const
+ { return _S_distance(__first, __last); }
+
+ // return the stored size
+ size_t _M_node_count() const { return _M_impl._M_node._M_data; }
+#else
+ // dummy implementations used when the size is not stored
+ size_t _M_get_size() const { return 0; }
+ void _M_set_size(size_t) { }
+ void _M_inc_size(size_t) { }
+ void _M_dec_size(size_t) { }
+ size_t _M_distance(const void*, const void*) const { return 0; }
+
+ // count the number of nodes
+ size_t _M_node_count() const
+ {
+ return _S_distance(_M_impl._M_node._M_next,
+ std::__addressof(_M_impl._M_node));
+ }
+#endif
+
_List_node<_Tp>*
_M_get_node()
{ return _M_impl._Node_alloc_type::allocate(1); }
_List_base(_List_base&& __x) noexcept
: _M_impl(std::move(__x._M_get_Node_allocator()))
{
- _M_init();
- __detail::_List_node_base::swap(_M_impl._M_node, __x._M_impl._M_node);
+ auto* const __xnode = std::__addressof(__x._M_impl._M_node);
+ if (__xnode->_M_next == __xnode)
+ _M_init();
+ else
+ {
+ auto* const __node = std::__addressof(_M_impl._M_node);
+ __node->_M_next = __xnode->_M_next;
+ __node->_M_prev = __xnode->_M_prev;
+ __node->_M_next->_M_prev = __node->_M_prev->_M_next = __node;
+ _M_set_size(__x._M_get_size());
+ __x._M_init();
+ }
}
#endif
{
this->_M_impl._M_node._M_next = &this->_M_impl._M_node;
this->_M_impl._M_node._M_prev = &this->_M_impl._M_node;
+ _M_set_size(0);
}
};
* %empty.
*/
template<typename _Tp, typename _Alloc = std::allocator<_Tp> >
- class list : protected _List_base<_Tp, _Alloc>
+ class _GLIBCXX_DEFAULT_ABI_TAG list : protected _List_base<_Tp, _Alloc>
{
// concept requirements
typedef typename _Alloc::value_type _Alloc_value_type;
public:
// [23.2.2.1] construct/copy/destroy
// (assign() and get_allocator() are also listed in this section)
+
+ /**
+ * @brief Creates a %list with no elements.
+ */
+ list()
+#if __cplusplus >= 201103L
+ noexcept(is_nothrow_default_constructible<_Node_alloc_type>::value)
+#endif
+ : _Base() { }
+
/**
* @brief Creates a %list with no elements.
* @param __a An allocator object.
*/
explicit
- list(const allocator_type& __a = allocator_type()) _GLIBCXX_NOEXCEPT
+ list(const allocator_type& __a) _GLIBCXX_NOEXCEPT
: _Base(_Node_alloc_type(__a)) { }
#if __cplusplus >= 201103L
/** Returns the number of elements in the %list. */
size_type
size() const _GLIBCXX_NOEXCEPT
- { return std::distance(begin(), end()); }
+ { return this->_M_node_count(); }
/** Returns the size() of the largest possible %list. */
size_type
__detail::_List_node_base::swap(this->_M_impl._M_node,
__x._M_impl._M_node);
+ size_t __xsize = __x._M_get_size();
+ __x._M_set_size(this->_M_get_size());
+ this->_M_set_size(__xsize);
+
// _GLIBCXX_RESOLVE_LIB_DEFECTS
// 431. Swapping containers with unequal allocators.
std::__alloc_swap<typename _Base::_Node_alloc_type>::
*/
void
#if __cplusplus >= 201103L
- splice(const_iterator __position, list&& __x)
+ splice(const_iterator __position, list&& __x) noexcept
#else
splice(iterator __position, list& __x)
#endif
this->_M_transfer(__position._M_const_cast(),
__x.begin(), __x.end());
+
+ this->_M_inc_size(__x._M_get_size());
+ __x._M_set_size(0);
}
}
#if __cplusplus >= 201103L
void
- splice(const_iterator __position, list& __x)
+ splice(const_iterator __position, list& __x) noexcept
{ splice(__position, std::move(__x)); }
#endif
* inserts it into the current list before @a __position.
*/
void
- splice(const_iterator __position, list&& __x, const_iterator __i)
+ splice(const_iterator __position, list&& __x, const_iterator __i) noexcept
#else
/**
* @brief Insert element from another %list.
this->_M_transfer(__position._M_const_cast(),
__i._M_const_cast(), __j);
+
+ this->_M_inc_size(1);
+ __x._M_dec_size(1);
}
#if __cplusplus >= 201103L
* inserts it into the current list before @a __position.
*/
void
- splice(const_iterator __position, list& __x, const_iterator __i)
+ splice(const_iterator __position, list& __x, const_iterator __i) noexcept
{ splice(__position, std::move(__x), __i); }
#endif
*/
void
splice(const_iterator __position, list&& __x, const_iterator __first,
- const_iterator __last)
+ const_iterator __last) noexcept
#else
/**
* @brief Insert range from another %list.
if (this != &__x)
_M_check_equal_allocators(__x);
+ size_t __n = this->_M_distance(__first._M_node, __last._M_node);
+ this->_M_inc_size(__n);
+ __x._M_dec_size(__n);
+
this->_M_transfer(__position._M_const_cast(),
__first._M_const_cast(),
__last._M_const_cast());
*/
void
splice(const_iterator __position, list& __x, const_iterator __first,
- const_iterator __last)
+ const_iterator __last) noexcept
{ splice(__position, std::move(__x), __first, __last); }
#endif
{
_Node* __tmp = _M_create_node(__x);
__tmp->_M_hook(__position._M_node);
+ this->_M_inc_size(1);
}
#else
template<typename... _Args>
{
_Node* __tmp = _M_create_node(std::forward<_Args>(__args)...);
__tmp->_M_hook(__position._M_node);
+ this->_M_inc_size(1);
}
#endif
void
_M_erase(iterator __position) _GLIBCXX_NOEXCEPT
{
+ this->_M_dec_size(1);
__position._M_node->_M_unhook();
_Node* __n = static_cast<_Node*>(__position._M_node);
#if __cplusplus >= 201103L
// To implement the splice (and merge) bits of N1599.
void
- _M_check_equal_allocators(list& __x)
+ _M_check_equal_allocators(list& __x) _GLIBCXX_NOEXCEPT
{
if (std::__alloc_neq<typename _Base::_Node_alloc_type>::
_S_do_it(_M_get_Node_allocator(), __x._M_get_Node_allocator()))
- __throw_runtime_error(__N("list::_M_check_equal_allocators"));
+ __builtin_abort();
}
};
projects / gcc.git / blobdiff