Hi,
this simply implements the O(1) size for the C++0x std::list. Tested
x86_64-linux multilib, etc, committed to mainline.
Thanks,
Paolo.
//////////////////////
2011-10-04 Paolo Carlini <paolo.carl...@oracle.com>
PR libstdc++/49561
* include/bits/stl_list.h (_List_base<>::_List_impl::_M_size):
Add in C++0x mode.
(_List_base<>::_List_impl, _List_base<>::_M_get_node,
_List_base<>::_M_put_node, _List_base<>::_List_base(_List_base&&),
list<>::size, list<>::swap, list<>::splice): Use it.
(operator==(const list<>&, const list<>&)): Rewrite in C++0x mode.
* include/bits/list.tcc (list<>::erase): Likewise.
(list<>::merge): Adjust in C++0x mode.
* testsuite/23_containers/list/requirements/dr438/assign_neg.cc:
Adjust dg-error line number.
* testsuite/23_containers/list/requirements/dr438/insert_neg.cc:
Likewise.
* testsuite/23_containers/list/requirements/dr438/
constructor_1_neg.cc: Likewise.
* testsuite/23_containers/list/requirements/dr438/
constructor_2_neg.cc: Likewise.
Index: include/bits/stl_list.h
===================================================================
--- include/bits/stl_list.h (revision 179522)
+++ include/bits/stl_list.h (working copy)
@@ -311,17 +311,27 @@
{
__detail::_List_node_base _M_node;
+#ifdef __GXX_EXPERIMENTAL_CXX0X__
+ size_t _M_size;
+#endif
+
_List_impl()
: _Node_alloc_type(), _M_node()
+#ifdef __GXX_EXPERIMENTAL_CXX0X__
+ , _M_size(0)
+#endif
{ }
_List_impl(const _Node_alloc_type& __a)
: _Node_alloc_type(__a), _M_node()
+#ifdef __GXX_EXPERIMENTAL_CXX0X__
+ , _M_size(0)
+#endif
{ }
#ifdef __GXX_EXPERIMENTAL_CXX0X__
_List_impl(_Node_alloc_type&& __a)
- : _Node_alloc_type(std::move(__a)), _M_node()
+ : _Node_alloc_type(std::move(__a)), _M_node(), _M_size(0)
{ }
#endif
};
@@ -330,22 +340,33 @@
_List_node<_Tp>*
_M_get_node()
- { return _M_impl._Node_alloc_type::allocate(1); }
-
+ {
+ _List_node<_Tp>* __tmp = _M_impl._Node_alloc_type::allocate(1);
+#ifdef __GXX_EXPERIMENTAL_CXX0X__
+ ++_M_impl._M_size;
+#endif
+ return __tmp;
+ }
+
void
_M_put_node(_List_node<_Tp>* __p)
- { _M_impl._Node_alloc_type::deallocate(__p, 1); }
+ {
+ _M_impl._Node_alloc_type::deallocate(__p, 1);
+#ifdef __GXX_EXPERIMENTAL_CXX0X__
+ --_M_impl._M_size;
+#endif
+ }
public:
typedef _Alloc allocator_type;
_Node_alloc_type&
_M_get_Node_allocator() _GLIBCXX_NOEXCEPT
- { return *static_cast<_Node_alloc_type*>(&this->_M_impl); }
+ { return *static_cast<_Node_alloc_type*>(&_M_impl); }
const _Node_alloc_type&
_M_get_Node_allocator() const _GLIBCXX_NOEXCEPT
- { return *static_cast<const _Node_alloc_type*>(&this->_M_impl); }
+ { return *static_cast<const _Node_alloc_type*>(&_M_impl); }
_Tp_alloc_type
_M_get_Tp_allocator() const _GLIBCXX_NOEXCEPT
@@ -368,8 +389,8 @@
: _M_impl(std::move(__x._M_get_Node_allocator()))
{
_M_init();
- __detail::_List_node_base::swap(this->_M_impl._M_node,
- __x._M_impl._M_node);
+ __detail::_List_node_base::swap(_M_impl._M_node, __x._M_impl._M_node);
+ std::swap(_M_impl._M_size, __x._M_impl._M_size);
}
#endif
@@ -851,7 +872,13 @@
/** Returns the number of elements in the %list. */
size_type
size() const _GLIBCXX_NOEXCEPT
- { return std::distance(begin(), end()); }
+ {
+#ifdef __GXX_EXPERIMENTAL_CXX0X__
+ return this->_M_impl._M_size;
+#else
+ return std::distance(begin(), end());
+#endif
+ }
/** Returns the size() of the largest possible %list. */
size_type
@@ -1186,6 +1213,9 @@
{
__detail::_List_node_base::swap(this->_M_impl._M_node,
__x._M_impl._M_node);
+#ifdef __GXX_EXPERIMENTAL_CXX0X__
+ std::swap(this->_M_impl._M_size, __x._M_impl._M_size);
+#endif
// _GLIBCXX_RESOLVE_LIB_DEFECTS
// 431. Swapping containers with unequal allocators.
@@ -1230,6 +1260,11 @@
_M_check_equal_allocators(__x);
this->_M_transfer(__position, __x.begin(), __x.end());
+
+#ifdef __GXX_EXPERIMENTAL_CXX0X__
+ this->_M_impl._M_size += __x.size();
+ __x._M_impl._M_size = 0;
+#endif
}
}
@@ -1261,8 +1296,15 @@
return;
if (this != &__x)
- _M_check_equal_allocators(__x);
+ {
+ _M_check_equal_allocators(__x);
+#ifdef __GXX_EXPERIMENTAL_CXX0X__
+ ++this->_M_impl._M_size;
+ --__x._M_impl._M_size;
+#endif
+ }
+
this->_M_transfer(__position, __i, __j);
}
@@ -1296,8 +1338,16 @@
if (__first != __last)
{
if (this != &__x)
- _M_check_equal_allocators(__x);
+ {
+ _M_check_equal_allocators(__x);
+#ifdef __GXX_EXPERIMENTAL_CXX0X__
+ const size_type __size = std::distance(__first, __last);
+ this->_M_impl._M_size += __size;
+ __x._M_impl._M_size -= __size;
+#endif
+ }
+
this->_M_transfer(__position, __first, __last);
}
}
@@ -1571,6 +1621,10 @@
inline bool
operator==(const list<_Tp, _Alloc>& __x, const list<_Tp, _Alloc>& __y)
{
+#ifdef __GXX_EXPERIMENTAL_CXX0X__
+ return (__x.size() == __y.size()
+ && std::equal(__x.begin(), __x.end(), __y.begin()));
+#else
typedef typename list<_Tp, _Alloc>::const_iterator const_iterator;
const_iterator __end1 = __x.end();
const_iterator __end2 = __y.end();
@@ -1583,6 +1637,7 @@
++__i2;
}
return __i1 == __end1 && __i2 == __end2;
+#endif
}
/**
Index: include/bits/list.tcc
===================================================================
--- include/bits/list.tcc (revision 179522)
+++ include/bits/list.tcc (working copy)
@@ -67,8 +67,8 @@
_M_clear()
{
typedef _List_node<_Tp> _Node;
- _Node* __cur = static_cast<_Node*>(this->_M_impl._M_node._M_next);
- while (__cur != &this->_M_impl._M_node)
+ _Node* __cur = static_cast<_Node*>(_M_impl._M_node._M_next);
+ while (__cur != &_M_impl._M_node)
{
_Node* __tmp = __cur;
__cur = static_cast<_Node*>(__cur->_M_next);
@@ -139,14 +139,14 @@
list<_Tp, _Alloc>::
resize(size_type __new_size)
{
- iterator __i = begin();
- size_type __len = 0;
- for (; __i != end() && __len < __new_size; ++__i, ++__len)
- ;
- if (__len == __new_size)
- erase(__i, end());
- else // __i == end()
- _M_default_append(__new_size - __len);
+ if (__new_size > size())
+ _M_default_append(__new_size - size());
+ else if (__new_size < size())
+ {
+ iterator __i = begin();
+ std::advance(__i, __new_size);
+ erase(__i, end());
+ }
}
template<typename _Tp, typename _Alloc>
@@ -154,14 +154,14 @@
list<_Tp, _Alloc>::
resize(size_type __new_size, const value_type& __x)
{
- iterator __i = begin();
- size_type __len = 0;
- for (; __i != end() && __len < __new_size; ++__i, ++__len)
- ;
- if (__len == __new_size)
- erase(__i, end());
- else // __i == end()
- insert(end(), __new_size - __len, __x);
+ if (__new_size > size())
+ insert(end(), __new_size - size(), __x);
+ else if (__new_size < size())
+ {
+ iterator __i = begin();
+ std::advance(__i, __new_size);
+ erase(__i, end());
+ }
}
#else
template<typename _Tp, typename _Alloc>
@@ -312,6 +312,11 @@
++__first1;
if (__first2 != __last2)
_M_transfer(__last1, __first2, __last2);
+
+#ifdef __GXX_EXPERIMENTAL_CXX0X__
+ this->_M_impl._M_size += __x.size();
+ __x._M_impl._M_size = 0;
+#endif
}
}
@@ -346,6 +351,11 @@
++__first1;
if (__first2 != __last2)
_M_transfer(__last1, __first2, __last2);
+
+#ifdef __GXX_EXPERIMENTAL_CXX0X__
+ this->_M_impl._M_size += __x.size();
+ __x._M_impl._M_size = 0;
+#endif
}
}
Index: testsuite/23_containers/list/requirements/dr438/assign_neg.cc
===================================================================
--- testsuite/23_containers/list/requirements/dr438/assign_neg.cc
(revision 179522)
+++ testsuite/23_containers/list/requirements/dr438/assign_neg.cc
(working copy)
@@ -18,7 +18,7 @@
// <http://www.gnu.org/licenses/>.
// { dg-do compile }
-// { dg-error "no matching" "" { target *-*-* } 1499 }
+// { dg-error "no matching" "" { target *-*-* } 1549 }
#include <list>
Index: testsuite/23_containers/list/requirements/dr438/insert_neg.cc
===================================================================
--- testsuite/23_containers/list/requirements/dr438/insert_neg.cc
(revision 179522)
+++ testsuite/23_containers/list/requirements/dr438/insert_neg.cc
(working copy)
@@ -18,7 +18,7 @@
// <http://www.gnu.org/licenses/>.
// { dg-do compile }
-// { dg-error "no matching" "" { target *-*-* } 1455 }
+// { dg-error "no matching" "" { target *-*-* } 1505 }
#include <list>
Index: testsuite/23_containers/list/requirements/dr438/constructor_1_neg.cc
===================================================================
--- testsuite/23_containers/list/requirements/dr438/constructor_1_neg.cc
(revision 179522)
+++ testsuite/23_containers/list/requirements/dr438/constructor_1_neg.cc
(working copy)
@@ -18,7 +18,7 @@
// <http://www.gnu.org/licenses/>.
// { dg-do compile }
-// { dg-error "no matching" "" { target *-*-* } 1455 }
+// { dg-error "no matching" "" { target *-*-* } 1505 }
#include <list>
Index: testsuite/23_containers/list/requirements/dr438/constructor_2_neg.cc
===================================================================
--- testsuite/23_containers/list/requirements/dr438/constructor_2_neg.cc
(revision 179522)
+++ testsuite/23_containers/list/requirements/dr438/constructor_2_neg.cc
(working copy)
@@ -18,7 +18,7 @@
// <http://www.gnu.org/licenses/>.
// { dg-do compile }
-// { dg-error "no matching" "" { target *-*-* } 1455 }
+// { dg-error "no matching" "" { target *-*-* } 1505 }
#include <list>
#include <utility>
