From e3d51be28110e27f893dda4867542958706db1d6 Mon Sep 17 00:00:00 2001 From: Gawain Bolton Date: Sun, 6 Jul 2003 00:58:52 +0000 Subject: [PATCH] stl_list.h: Performance and memory usage improvements. 2003-07-05 Gawain Bolton * include/bits/stl_list.h: Performance and memory usage improvements. * include/bits/list.tcc: Likewise. From-SVN: r68987 --- libstdc++-v3/ChangeLog | 6 ++++ libstdc++-v3/include/bits/list.tcc | 49 +++++++++++++++++++++++----- libstdc++-v3/include/bits/stl_list.h | 33 +++++++++---------- 3 files changed, 62 insertions(+), 26 deletions(-) diff --git a/libstdc++-v3/ChangeLog b/libstdc++-v3/ChangeLog index c55d7840101..7d1d6262861 100644 --- a/libstdc++-v3/ChangeLog +++ b/libstdc++-v3/ChangeLog @@ -1,3 +1,9 @@ +2003-07-05 Gawain Bolton + + * include/bits/stl_list.h: Performance and memory usage + improvements. + * include/bits/list.tcc: Likewise. + 2003-07-05 Paolo Carlini * include/std/std_complex.h: Fully qualify standard diff --git a/libstdc++-v3/include/bits/list.tcc b/libstdc++-v3/include/bits/list.tcc index 428dc90e2e1..2afde96995a 100644 --- a/libstdc++-v3/include/bits/list.tcc +++ b/libstdc++-v3/include/bits/list.tcc @@ -69,18 +69,51 @@ namespace std __clear() { typedef _List_node<_Tp> _Node; - _Node* __cur = static_cast<_Node*>(this->_M_node->_M_next); - while (__cur != this->_M_node) + _Node* __cur = static_cast<_Node*>(this->_M_node._M_next); + while (__cur != &this->_M_node) { _Node* __tmp = __cur; __cur = static_cast<_Node*>(__cur->_M_next); std::_Destroy(&__tmp->_M_data); _M_put_node(__tmp); } - this->_M_node->_M_next = this->_M_node; - this->_M_node->_M_prev = this->_M_node; + this->_M_node._M_next = &this->_M_node; + this->_M_node._M_prev = &this->_M_node; } + template + void list<_Tp, _Alloc>:: + swap(list<_Tp, _Alloc>& __x) + { + if ( this->_M_node._M_next == &this->_M_node ) + { + if ( __x._M_node._M_next != &__x._M_node ) + { + this->_M_node._M_next = __x._M_node._M_next; + this->_M_node._M_prev = __x._M_node._M_prev; + + this->_M_node._M_next->_M_prev = this->_M_node._M_prev->_M_next = &this->_M_node; + __x._M_node._M_next = __x._M_node._M_prev = &__x._M_node; + } + } + else if ( __x._M_node._M_next == &__x._M_node ) + { + __x._M_node._M_next = this->_M_node._M_next; + __x._M_node._M_prev = this->_M_node._M_prev; + + __x._M_node._M_next->_M_prev = __x._M_node._M_prev->_M_next = &__x._M_node; + this->_M_node._M_next = this->_M_node._M_prev = &this->_M_node; + } + else + { + std::swap(this->_M_node._M_next,__x._M_node._M_next); + std::swap(this->_M_node._M_prev,__x._M_node._M_prev); + + this->_M_node._M_next->_M_prev = this->_M_node._M_prev->_M_next = &this->_M_node; + __x._M_node._M_next->_M_prev = __x._M_node._M_prev->_M_next = &__x._M_node; + } + } + template typename list<_Tp,_Alloc>::iterator list<_Tp,_Alloc>:: @@ -250,8 +283,8 @@ namespace std sort() { // Do nothing if the list has length 0 or 1. - if (this->_M_node->_M_next != this->_M_node - && this->_M_node->_M_next->_M_next != this->_M_node) + if (this->_M_node._M_next != &this->_M_node + && this->_M_node._M_next->_M_next != &this->_M_node) { list __carry; list __counter[64]; @@ -341,8 +374,8 @@ namespace std sort(_StrictWeakOrdering __comp) { // Do nothing if the list has length 0 or 1. - if (this->_M_node->_M_next != this->_M_node && - this->_M_node->_M_next->_M_next != this->_M_node) + if (this->_M_node._M_next != &this->_M_node && + this->_M_node._M_next->_M_next != &this->_M_node) { list __carry; list __counter[64]; diff --git a/libstdc++-v3/include/bits/stl_list.h b/libstdc++-v3/include/bits/stl_list.h index 95fd78e07ea..6f5579e3770 100644 --- a/libstdc++-v3/include/bits/stl_list.h +++ b/libstdc++-v3/include/bits/stl_list.h @@ -247,7 +247,7 @@ namespace std typename _Alloc_traits<_List_node<_Tp>, _Allocator>::allocator_type _M_node_allocator; - _List_node<_Tp>* _M_node; + _List_node_base _M_node; }; /// @if maint Specialization for instanceless allocators. @endif @@ -278,7 +278,7 @@ namespace std _M_put_node(_List_node<_Tp>* __p) { _Alloc_type::deallocate(__p, 1); } - _List_node<_Tp>* _M_node; + _List_node_base _M_node; }; @@ -301,16 +301,14 @@ namespace std _List_base(const allocator_type& __a) : _Base(__a) { - this->_M_node = _M_get_node(); - this->_M_node->_M_next = this->_M_node; - this->_M_node->_M_prev = this->_M_node; + this->_M_node._M_next = &this->_M_node; + this->_M_node._M_prev = &this->_M_node; } // This is what actually destroys the list. ~_List_base() { __clear(); - _M_put_node(this->_M_node); } void @@ -376,8 +374,8 @@ namespace std typedef const value_type* const_pointer; typedef _List_iterator<_Tp,_Tp&,_Tp*> iterator; typedef _List_iterator<_Tp,const _Tp&,const _Tp*> const_iterator; - typedef std::reverse_iterator const_reverse_iterator; - typedef std::reverse_iterator reverse_iterator; + typedef std::reverse_iterator const_reverse_iterator; + typedef std::reverse_iterator reverse_iterator; typedef value_type& reference; typedef const value_type& const_reference; typedef size_t size_type; @@ -506,11 +504,11 @@ namespace std { this->insert(begin(), __first, __last); } /** - * The dtor only erases the elements, and note that if the elements + * No explicit dtor needed as the _Base dtor takes care of things. + * The _Base dtor only erases the elements, and note that if the elements * themselves are pointers, the pointed-to memory is not touched in any * way. Managing the pointer is the user's responsibilty. */ - ~list() { } /** * @brief %List assignment operator. @@ -566,28 +564,28 @@ namespace std * %list. Iteration is done in ordinary element order. */ iterator - begin() { return static_cast<_Node*>(this->_M_node->_M_next); } + begin() { return static_cast<_Node*>(this->_M_node._M_next); } /** * Returns a read-only (constant) iterator that points to the first element * in the %list. Iteration is done in ordinary element order. */ const_iterator - begin() const { return static_cast<_Node*>(this->_M_node->_M_next); } + begin() const { return static_cast<_Node*>(this->_M_node._M_next); } /** * Returns a read/write iterator that points one past the last element in * the %list. Iteration is done in ordinary element order. */ iterator - end() { return this->_M_node; } + end() { return static_cast<_Node*>(&this->_M_node); } /** * Returns a read-only (constant) iterator that points one past the last * element in the %list. Iteration is done in ordinary element order. */ const_iterator - end() const { return this->_M_node; } + end() const { return const_cast<_Node *>(static_cast(&this->_M_node)); } /** * Returns a read/write reverse iterator that points to the last element in @@ -625,7 +623,7 @@ namespace std * Returns true if the %list is empty. (Thus begin() would equal end().) */ bool - empty() const { return this->_M_node->_M_next == this->_M_node; } + empty() const { return this->_M_node._M_next == &this->_M_node; } /** Returns the number of elements in the %list. */ size_type @@ -848,12 +846,11 @@ namespace std * @param x A %list of the same element and allocator types. * * This exchanges the elements between two lists in constant time. - * (It is only swapping a single pointer, so it should be quite fast.) * Note that the global std::swap() function is specialized such that * std::swap(l1,l2) will feed to this function. */ void - swap(list& __x) { std::swap(this->_M_node, __x._M_node); } + swap(list& __x); /** * Erases all the elements. Note that this function only erases the @@ -940,7 +937,7 @@ namespace std * @doctodo */ void - reverse() { __List_base_reverse(this->_M_node); } + reverse() { __List_base_reverse(&this->_M_node); } /** * @doctodo -- 2.30.2