From 1fc610939a651cf4a5f8138b7a35abd8cf62497e Mon Sep 17 00:00:00 2001 From: "Stephen M. Webb" Date: Thu, 22 Nov 2001 19:19:23 +0000 Subject: [PATCH] list_capacity.cc: New file. 2001-11-22 Stephen M. Webb * testsuite/23_containers/list_capacity.cc: New file. * testsuite/23_containers/list_ctor.cc: New file. * testsuite/23_containers/list_modifiers.cc: New file. * testsuite/23_containers/list_operators.cc: New file. 2001-11-22 Stephen M. Webb * include/bits/stl_list.h: Reformatted according to C++STYLE rules. (size): Replaced nonstandard distance() call with the standard one. (transfer): Uglified to _M_transfer. From-SVN: r47277 --- libstdc++-v3/ChangeLog | 13 + libstdc++-v3/include/bits/stl_list.h | 1502 ++++++++++------- .../testsuite/23_containers/list_capacity.cc | 70 + .../testsuite/23_containers/list_ctor.cc | 332 ++++ .../testsuite/23_containers/list_modifiers.cc | 325 ++++ .../testsuite/23_containers/list_operators.cc | 211 +++ 6 files changed, 1799 insertions(+), 654 deletions(-) create mode 100644 libstdc++-v3/testsuite/23_containers/list_capacity.cc create mode 100644 libstdc++-v3/testsuite/23_containers/list_ctor.cc create mode 100644 libstdc++-v3/testsuite/23_containers/list_modifiers.cc create mode 100644 libstdc++-v3/testsuite/23_containers/list_operators.cc diff --git a/libstdc++-v3/ChangeLog b/libstdc++-v3/ChangeLog index deb1321957e..802b0bb2ffe 100644 --- a/libstdc++-v3/ChangeLog +++ b/libstdc++-v3/ChangeLog @@ -1,3 +1,16 @@ +2001-11-22 Stephen M. Webb + + * testsuite/23_containers/list_capacity.cc: New file. + * testsuite/23_containers/list_ctor.cc: New file. + * testsuite/23_containers/list_modifiers.cc: New file. + * testsuite/23_containers/list_operators.cc: New file. + +2001-11-22 Stephen M. Webb + + * include/bits/stl_list.h: Reformatted according to C++STYLE rules. + (size): Replaced nonstandard distance() call with the standard one. + (transfer): Uglified to _M_transfer. + 2001-11-21 Paolo Carlini PR libstdc++/4548 diff --git a/libstdc++-v3/include/bits/stl_list.h b/libstdc++-v3/include/bits/stl_list.h index 4feaa7157bb..3d787a0d5c0 100644 --- a/libstdc++-v3/include/bits/stl_list.h +++ b/libstdc++-v3/include/bits/stl_list.h @@ -66,718 +66,912 @@ namespace std { -struct _List_node_base { - _List_node_base* _M_next; - _List_node_base* _M_prev; -}; + struct _List_node_base + { + _List_node_base* _M_next; + _List_node_base* _M_prev; + }; -template -struct _List_node : public _List_node_base { - _Tp _M_data; -}; + template + struct _List_node : public _List_node_base + { + _Tp _M_data; + }; -struct _List_iterator_base { - typedef size_t size_type; - typedef ptrdiff_t difference_type; - typedef bidirectional_iterator_tag iterator_category; + struct _List_iterator_base + { + typedef size_t size_type; + typedef ptrdiff_t difference_type; + typedef bidirectional_iterator_tag iterator_category; - _List_node_base* _M_node; + _List_node_base* _M_node; - _List_iterator_base(_List_node_base* __x) : _M_node(__x) {} - _List_iterator_base() {} + _List_iterator_base(_List_node_base* __x) + : _M_node(__x) + { } - void _M_incr() { _M_node = _M_node->_M_next; } - void _M_decr() { _M_node = _M_node->_M_prev; } + _List_iterator_base() + { } - bool operator==(const _List_iterator_base& __x) const { - return _M_node == __x._M_node; - } - bool operator!=(const _List_iterator_base& __x) const { - return _M_node != __x._M_node; - } -}; + void + _M_incr() + { _M_node = _M_node->_M_next; } -template -struct _List_iterator : public _List_iterator_base { - typedef _List_iterator<_Tp,_Tp&,_Tp*> iterator; - typedef _List_iterator<_Tp,const _Tp&,const _Tp*> const_iterator; - typedef _List_iterator<_Tp,_Ref,_Ptr> _Self; + void + _M_decr() + { _M_node = _M_node->_M_prev; } - typedef _Tp value_type; - typedef _Ptr pointer; - typedef _Ref reference; - typedef _List_node<_Tp> _Node; + bool + operator==(const _List_iterator_base& __x) const + { return _M_node == __x._M_node; } - _List_iterator(_Node* __x) : _List_iterator_base(__x) {} - _List_iterator() {} - _List_iterator(const iterator& __x) : _List_iterator_base(__x._M_node) {} + bool + operator!=(const _List_iterator_base& __x) const + { return _M_node != __x._M_node; } + }; - reference operator*() const { return ((_Node*) _M_node)->_M_data; } - pointer operator->() const { return &(operator*()); } + template + struct _List_iterator : public _List_iterator_base + { + typedef _List_iterator<_Tp,_Tp&,_Tp*> iterator; + typedef _List_iterator<_Tp,const _Tp&,const _Tp*> const_iterator; + typedef _List_iterator<_Tp,_Ref,_Ptr> _Self; - _Self& operator++() { - this->_M_incr(); - return *this; - } - _Self operator++(int) { - _Self __tmp = *this; - this->_M_incr(); - return __tmp; - } - _Self& operator--() { - this->_M_decr(); - return *this; - } - _Self operator--(int) { - _Self __tmp = *this; - this->_M_decr(); - return __tmp; - } -}; - - -// Base class that encapsulates details of allocators. Three cases: -// an ordinary standard-conforming allocator, a standard-conforming -// allocator with no non-static data, and an SGI-style allocator. -// This complexity is necessary only because we're worrying about backward -// compatibility and because we want to avoid wasting storage on an -// allocator instance if it isn't necessary. - - -// Base for general standard-conforming allocators. -template -class _List_alloc_base { -public: - typedef typename _Alloc_traits<_Tp, _Allocator>::allocator_type - allocator_type; - allocator_type get_allocator() const { return _Node_allocator; } - - _List_alloc_base(const allocator_type& __a) : _Node_allocator(__a) {} - -protected: - _List_node<_Tp>* _M_get_node() - { return _Node_allocator.allocate(1); } - void _M_put_node(_List_node<_Tp>* __p) - { _Node_allocator.deallocate(__p, 1); } - -protected: - typename _Alloc_traits<_List_node<_Tp>, _Allocator>::allocator_type - _Node_allocator; - _List_node<_Tp>* _M_node; -}; - -// Specialization for instanceless allocators. - -template -class _List_alloc_base<_Tp, _Allocator, true> { -public: - typedef typename _Alloc_traits<_Tp, _Allocator>::allocator_type - allocator_type; - allocator_type get_allocator() const { return allocator_type(); } - - _List_alloc_base(const allocator_type&) {} - -protected: - typedef typename _Alloc_traits<_List_node<_Tp>, _Allocator>::_Alloc_type - _Alloc_type; - _List_node<_Tp>* _M_get_node() { return _Alloc_type::allocate(1); } - void _M_put_node(_List_node<_Tp>* __p) { _Alloc_type::deallocate(__p, 1); } - -protected: - _List_node<_Tp>* _M_node; -}; - -template -class _List_base - : public _List_alloc_base<_Tp, _Alloc, - _Alloc_traits<_Tp, _Alloc>::_S_instanceless> -{ -public: - typedef _List_alloc_base<_Tp, _Alloc, - _Alloc_traits<_Tp, _Alloc>::_S_instanceless> - _Base; - typedef typename _Base::allocator_type allocator_type; - - _List_base(const allocator_type& __a) : _Base(__a) { - _M_node = _M_get_node(); - _M_node->_M_next = _M_node; - _M_node->_M_prev = _M_node; - } - ~_List_base() { - clear(); - _M_put_node(_M_node); - } + typedef _Tp value_type; + typedef _Ptr pointer; + typedef _Ref reference; + typedef _List_node<_Tp> _Node; - void clear(); -}; + _List_iterator(_Node* __x) + : _List_iterator_base(__x) + { } + _List_iterator() + { } -template -void -_List_base<_Tp,_Alloc>::clear() -{ - _List_node<_Tp>* __cur = (_List_node<_Tp>*) _M_node->_M_next; - while (__cur != _M_node) { - _List_node<_Tp>* __tmp = __cur; - __cur = (_List_node<_Tp>*) __cur->_M_next; - _Destroy(&__tmp->_M_data); - _M_put_node(__tmp); - } - _M_node->_M_next = _M_node; - _M_node->_M_prev = _M_node; -} + _List_iterator(const iterator& __x) + : _List_iterator_base(__x._M_node) + { } -template > -class list : protected _List_base<_Tp, _Alloc> -{ - // concept requirements - __glibcpp_class_requires(_Tp, _SGIAssignableConcept) - - typedef _List_base<_Tp, _Alloc> _Base; -protected: - typedef void* _Void_pointer; - -public: - typedef _Tp value_type; - typedef value_type* pointer; - typedef const value_type* const_pointer; - typedef value_type& reference; - typedef const value_type& const_reference; - typedef _List_node<_Tp> _Node; - typedef size_t size_type; - typedef ptrdiff_t difference_type; - - typedef typename _Base::allocator_type allocator_type; - allocator_type get_allocator() const { return _Base::get_allocator(); } - -public: - typedef _List_iterator<_Tp,_Tp&,_Tp*> iterator; - typedef _List_iterator<_Tp,const _Tp&,const _Tp*> const_iterator; - - typedef reverse_iterator const_reverse_iterator; - typedef reverse_iterator reverse_iterator; - -protected: - using _Base::_M_node; - using _Base::_M_put_node; - using _Base::_M_get_node; - -protected: - _Node* _M_create_node(const _Tp& __x) - { - _Node* __p = _M_get_node(); - try { - _Construct(&__p->_M_data, __x); - } - catch(...) + reference + operator*() const + { return ((_Node*) _M_node)->_M_data; } + + pointer + operator->() const + { return &(operator*()); } + + _Self& + operator++() { - _M_put_node(__p); - __throw_exception_again; + this->_M_incr(); + return *this; } - return __p; - } - _Node* _M_create_node() - { - _Node* __p = _M_get_node(); - try { - _Construct(&__p->_M_data); - } - catch(...) + _Self + operator++(int) { - _M_put_node(__p); - __throw_exception_again; + _Self __tmp = *this; + this->_M_incr(); + return __tmp; } - return __p; - } -public: - explicit list(const allocator_type& __a = allocator_type()) : _Base(__a) {} + _Self& + operator--() + { + this->_M_decr(); + return *this; + } - iterator begin() { return (_Node*)(_M_node->_M_next); } - const_iterator begin() const { return (_Node*)(_M_node->_M_next); } + _Self + operator--(int) + { + _Self __tmp = *this; + this->_M_decr(); + return __tmp; + } + }; + + + // Base class that encapsulates details of allocators. Three cases: + // an ordinary standard-conforming allocator, a standard-conforming + // allocator with no non-static data, and an SGI-style allocator. + // This complexity is necessary only because we're worrying about backward + // compatibility and because we want to avoid wasting storage on an + // allocator instance if it isn't necessary. + + + // Base for general standard-conforming allocators. + template + class _List_alloc_base + { + public: + typedef typename _Alloc_traits<_Tp, _Allocator>::allocator_type + allocator_type; + + allocator_type + get_allocator() const + { return _Node_allocator; } + + _List_alloc_base(const allocator_type& __a) + : _Node_allocator(__a) + { } + + protected: + _List_node<_Tp>* + _M_get_node() + { return _Node_allocator.allocate(1); } + + void + _M_put_node(_List_node<_Tp>* __p) + { _Node_allocator.deallocate(__p, 1); } + + protected: + typename _Alloc_traits<_List_node<_Tp>, _Allocator>::allocator_type + _Node_allocator; + + _List_node<_Tp>* _M_node; + }; + + // Specialization for instanceless allocators. + + template + class _List_alloc_base<_Tp, _Allocator, true> + { + public: + typedef typename _Alloc_traits<_Tp, _Allocator>::allocator_type + allocator_type; + + allocator_type + get_allocator() const + { return allocator_type(); } + + _List_alloc_base(const allocator_type&) + { } + + protected: + typedef typename _Alloc_traits<_List_node<_Tp>, _Allocator>::_Alloc_type + _Alloc_type; + + _List_node<_Tp>* + _M_get_node() + { return _Alloc_type::allocate(1); } + + void + _M_put_node(_List_node<_Tp>* __p) + { _Alloc_type::deallocate(__p, 1); } + + protected: + _List_node<_Tp>* _M_node; + }; + + template + class _List_base + : public _List_alloc_base<_Tp, _Alloc, + _Alloc_traits<_Tp, _Alloc>::_S_instanceless> + { + public: + typedef _List_alloc_base<_Tp, _Alloc, + _Alloc_traits<_Tp, _Alloc>::_S_instanceless> + _Base; + typedef typename _Base::allocator_type allocator_type; + + _List_base(const allocator_type& __a) + : _Base(__a) + { + _M_node = _M_get_node(); + _M_node->_M_next = _M_node; + _M_node->_M_prev = _M_node; + } - iterator end() { return _M_node; } - const_iterator end() const { return _M_node; } + ~_List_base() + { + clear(); + _M_put_node(_M_node); + } - reverse_iterator rbegin() - { return reverse_iterator(end()); } - const_reverse_iterator rbegin() const - { return const_reverse_iterator(end()); } + void clear(); + }; + + + template > + class list : protected _List_base<_Tp, _Alloc> + { + // concept requirements + __glibcpp_class_requires(_Tp, _SGIAssignableConcept) + + typedef _List_base<_Tp, _Alloc> _Base; + protected: + typedef void* _Void_pointer; + + public: + typedef _Tp value_type; + typedef value_type* pointer; + typedef const value_type* const_pointer; + typedef value_type& reference; + typedef const value_type& const_reference; + typedef _List_node<_Tp> _Node; + typedef size_t size_type; + typedef ptrdiff_t difference_type; + + typedef typename _Base::allocator_type allocator_type; + + typedef _List_iterator<_Tp,_Tp&,_Tp*> iterator; + typedef _List_iterator<_Tp,const _Tp&,const _Tp*> const_iterator; + + typedef reverse_iterator const_reverse_iterator; + typedef reverse_iterator reverse_iterator; + + protected: + using _Base::_M_node; + using _Base::_M_put_node; + using _Base::_M_get_node; + + protected: + _Node* + _M_create_node(const _Tp& __x) + { + _Node* __p = _M_get_node(); + try { + _Construct(&__p->_M_data, __x); + } + catch(...) + { + _M_put_node(__p); + __throw_exception_again; + } + return __p; + } - reverse_iterator rend() - { return reverse_iterator(begin()); } - const_reverse_iterator rend() const - { return const_reverse_iterator(begin()); } + _Node* + _M_create_node() + { + _Node* __p = _M_get_node(); + try { + _Construct(&__p->_M_data); + } + catch(...) + { + _M_put_node(__p); + __throw_exception_again; + } + return __p; + } - bool empty() const { return _M_node->_M_next == _M_node; } - size_type size() const { - size_type __result = 0; - distance(begin(), end(), __result); - return __result; - } - size_type max_size() const { return size_type(-1); } - - reference front() { return *begin(); } - const_reference front() const { return *begin(); } - reference back() { return *(--end()); } - const_reference back() const { return *(--end()); } - - void swap(list<_Tp, _Alloc>& __x) { std::swap(_M_node, __x._M_node); } - - iterator insert(iterator __position, const _Tp& __x) { - _Node* __tmp = _M_create_node(__x); - __tmp->_M_next = __position._M_node; - __tmp->_M_prev = __position._M_node->_M_prev; - __position._M_node->_M_prev->_M_next = __tmp; - __position._M_node->_M_prev = __tmp; - return __tmp; - } - iterator insert(iterator __position) { return insert(__position, _Tp()); } + public: + allocator_type + get_allocator() const + { return _Base::get_allocator(); } + + explicit + list(const allocator_type& __a = allocator_type()) + : _Base(__a) + { } + + iterator + begin() + { return static_cast<_Node*>(_M_node->_M_next); } + + const_iterator + begin() const + { return static_cast<_Node*>(_M_node->_M_next); } + + iterator + end() + { return _M_node; } + + const_iterator + end() const + { return _M_node; } + + reverse_iterator + rbegin() + { return reverse_iterator(end()); } + + const_reverse_iterator + rbegin() const + { return const_reverse_iterator(end()); } + + reverse_iterator + rend() + { return reverse_iterator(begin()); } + + const_reverse_iterator + rend() const + { return const_reverse_iterator(begin()); } + + bool + empty() const + { return _M_node->_M_next == _M_node; } + + size_type + size() const + { return distance(begin(), end()); } + + size_type + max_size() const + { return size_type(-1); } + + reference + front() + { return *begin(); } + + const_reference + front() const + { return *begin(); } + + reference + back() + { return *(--end()); } + + const_reference + back() const + { return *(--end()); } + + void + swap(list<_Tp, _Alloc>& __x) + { std::swap(_M_node, __x._M_node); } + + iterator + insert(iterator __position, const _Tp& __x) + { + _Node* __tmp = _M_create_node(__x); + __tmp->_M_next = __position._M_node; + __tmp->_M_prev = __position._M_node->_M_prev; + __position._M_node->_M_prev->_M_next = __tmp; + __position._M_node->_M_prev = __tmp; + return __tmp; + } - // Check whether it's an integral type. If so, it's not an iterator. - template - void _M_insert_dispatch(iterator __pos, _Integer __n, _Integer __x, - __true_type) { - _M_fill_insert(__pos, (size_type) __n, (_Tp) __x); - } + iterator + insert(iterator __position) + { return insert(__position, _Tp()); } + + // Check whether it's an integral type. If so, it's not an iterator. + template + void + _M_insert_dispatch(iterator __pos, _Integer __n, _Integer __x, __true_type) + { _M_fill_insert(__pos, (size_type) __n, (_Tp) __x); } + + template + void + _M_insert_dispatch(iterator __pos, + _InputIterator __first, _InputIterator __last, + __false_type); + + template + void + insert(iterator __pos, _InputIterator __first, _InputIterator __last) + { + typedef typename _Is_integer<_InputIterator>::_Integral _Integral; + _M_insert_dispatch(__pos, __first, __last, _Integral()); + } + + void + insert(iterator __pos, size_type __n, const _Tp& __x) + { _M_fill_insert(__pos, __n, __x); } + + void + _M_fill_insert(iterator __pos, size_type __n, const _Tp& __x); + + void + push_front(const _Tp& __x) + { insert(begin(), __x); } + + void + push_front() + { insert(begin()); } + + void + push_back(const _Tp& __x) + { insert(end(), __x); } + + void + push_back() + { insert(end()); } + + iterator + erase(iterator __position) + { + _List_node_base* __next_node = __position._M_node->_M_next; + _List_node_base* __prev_node = __position._M_node->_M_prev; + _Node* __n = static_cast<_Node*>(__position._M_node); + __prev_node->_M_next = __next_node; + __next_node->_M_prev = __prev_node; + _Destroy(&__n->_M_data); + _M_put_node(__n); + return iterator(static_cast<_Node*>(__next_node)); + } - template - void _M_insert_dispatch(iterator __pos, - _InputIterator __first, _InputIterator __last, - __false_type); + iterator + erase(iterator __first, iterator __last); - template - void insert(iterator __pos, _InputIterator __first, _InputIterator __last) { - typedef typename _Is_integer<_InputIterator>::_Integral _Integral; - _M_insert_dispatch(__pos, __first, __last, _Integral()); - } + void + clear() + { _Base::clear(); } - void insert(iterator __pos, size_type __n, const _Tp& __x) - { _M_fill_insert(__pos, __n, __x); } - void _M_fill_insert(iterator __pos, size_type __n, const _Tp& __x); - - void push_front(const _Tp& __x) { insert(begin(), __x); } - void push_front() {insert(begin());} - void push_back(const _Tp& __x) { insert(end(), __x); } - void push_back() {insert(end());} - - iterator erase(iterator __position) { - _List_node_base* __next_node = __position._M_node->_M_next; - _List_node_base* __prev_node = __position._M_node->_M_prev; - _Node* __n = (_Node*) __position._M_node; - __prev_node->_M_next = __next_node; - __next_node->_M_prev = __prev_node; - _Destroy(&__n->_M_data); - _M_put_node(__n); - return iterator((_Node*) __next_node); - } - iterator erase(iterator __first, iterator __last); - void clear() { _Base::clear(); } + void + resize(size_type __new_size, const _Tp& __x); + + void + resize(size_type __new_size) + { this->resize(__new_size, _Tp()); } - void resize(size_type __new_size, const _Tp& __x); - void resize(size_type __new_size) { this->resize(__new_size, _Tp()); } + void + pop_front() + { erase(begin()); } - void pop_front() { erase(begin()); } - void pop_back() { - iterator __tmp = end(); - erase(--__tmp); - } - list(size_type __n, const _Tp& __value, - const allocator_type& __a = allocator_type()) - : _Base(__a) - { insert(begin(), __n, __value); } - explicit list(size_type __n) - : _Base(allocator_type()) - { insert(begin(), __n, _Tp()); } - - // We don't need any dispatching tricks here, because insert does all of - // that anyway. - template - list(_InputIterator __first, _InputIterator __last, - const allocator_type& __a = allocator_type()) - : _Base(__a) - { insert(begin(), __first, __last); } - - list(const list<_Tp, _Alloc>& __x) : _Base(__x.get_allocator()) - { insert(begin(), __x.begin(), __x.end()); } - - ~list() { } - - list<_Tp, _Alloc>& operator=(const list<_Tp, _Alloc>& __x); - -public: - // assign(), a generalized assignment member function. Two - // versions: one that takes a count, and one that takes a range. - // The range version is a member template, so we dispatch on whether - // or not the type is an integer. - - void assign(size_type __n, const _Tp& __val) { _M_fill_assign(__n, __val); } - - void _M_fill_assign(size_type __n, const _Tp& __val); - - template - void assign(_InputIterator __first, _InputIterator __last) { - typedef typename _Is_integer<_InputIterator>::_Integral _Integral; - _M_assign_dispatch(__first, __last, _Integral()); - } + void + pop_back() + { + iterator __tmp = end(); + erase(--__tmp); + } + + list(size_type __n, const _Tp& __value, + const allocator_type& __a = allocator_type()) + : _Base(__a) + { insert(begin(), __n, __value); } + + explicit + list(size_type __n) + : _Base(allocator_type()) + { insert(begin(), __n, _Tp()); } + + // We don't need any dispatching tricks here, because insert does all of + // that anyway. + template + list(_InputIterator __first, _InputIterator __last, + const allocator_type& __a = allocator_type()) + : _Base(__a) + { insert(begin(), __first, __last); } + + list(const list<_Tp, _Alloc>& __x) + : _Base(__x.get_allocator()) + { insert(begin(), __x.begin(), __x.end()); } + + ~list() + { } + + list<_Tp, _Alloc>& + operator=(const list<_Tp, _Alloc>& __x); + + public: + // assign(), a generalized assignment member function. Two + // versions: one that takes a count, and one that takes a range. + // The range version is a member template, so we dispatch on whether + // or not the type is an integer. + + void + assign(size_type __n, const _Tp& __val) + { _M_fill_assign(__n, __val); } + + void + _M_fill_assign(size_type __n, const _Tp& __val); + + template + void + assign(_InputIterator __first, _InputIterator __last) + { + typedef typename _Is_integer<_InputIterator>::_Integral _Integral; + _M_assign_dispatch(__first, __last, _Integral()); + } + + template + void + _M_assign_dispatch(_Integer __n, _Integer __val, __true_type) + { _M_fill_assign((size_type) __n, (_Tp) __val); } + + template + void + _M_assign_dispatch(_InputIterator __first, _InputIterator __last, + __false_type); + + protected: + void + _M_transfer(iterator __position, iterator __first, iterator __last) + { + if (__position != __last) { + // Remove [first, last) from its old position. + __last._M_node->_M_prev->_M_next = __position._M_node; + __first._M_node->_M_prev->_M_next = __last._M_node; + __position._M_node->_M_prev->_M_next = __first._M_node; + + // Splice [first, last) into its new position. + _List_node_base* __tmp = __position._M_node->_M_prev; + __position._M_node->_M_prev = __last._M_node->_M_prev; + __last._M_node->_M_prev = __first._M_node->_M_prev; + __first._M_node->_M_prev = __tmp; + } + } + + public: + void + splice(iterator __position, list& __x) + { + if (!__x.empty()) + this->_M_transfer(__position, __x.begin(), __x.end()); + } + + void + splice(iterator __position, list&, iterator __i) + { + iterator __j = __i; + ++__j; + if (__position == __i || __position == __j) return; + this->_M_transfer(__position, __i, __j); + } + + void + splice(iterator __position, list&, iterator __first, iterator __last) + { + if (__first != __last) + this->_M_transfer(__position, __first, __last); + } + + void + remove(const _Tp& __value); + + void + unique(); + + void + merge(list& __x); + + void + reverse(); + + void + sort(); + + template + void + remove_if(_Predicate); + + template + void + unique(_BinaryPredicate); + + template + void + merge(list&, _StrictWeakOrdering); - template - void _M_assign_dispatch(_Integer __n, _Integer __val, __true_type) - { _M_fill_assign((size_type) __n, (_Tp) __val); } - - template - void _M_assign_dispatch(_InputIterator __first, _InputIterator __last, - __false_type); - -protected: - void transfer(iterator __position, iterator __first, iterator __last) { - if (__position != __last) { - // Remove [first, last) from its old position. - __last._M_node->_M_prev->_M_next = __position._M_node; - __first._M_node->_M_prev->_M_next = __last._M_node; - __position._M_node->_M_prev->_M_next = __first._M_node; - - // Splice [first, last) into its new position. - _List_node_base* __tmp = __position._M_node->_M_prev; - __position._M_node->_M_prev = __last._M_node->_M_prev; - __last._M_node->_M_prev = __first._M_node->_M_prev; - __first._M_node->_M_prev = __tmp; + template + void + sort(_StrictWeakOrdering); + }; + + template + inline bool + operator==(const list<_Tp,_Alloc>& __x, const list<_Tp,_Alloc>& __y) + { + typedef typename list<_Tp,_Alloc>::const_iterator const_iterator; + const_iterator __end1 = __x.end(); + const_iterator __end2 = __y.end(); + + const_iterator __i1 = __x.begin(); + const_iterator __i2 = __y.begin(); + while (__i1 != __end1 && __i2 != __end2 && *__i1 == *__i2) { + ++__i1; + ++__i2; + } + return __i1 == __end1 && __i2 == __end2; } - } -public: - void splice(iterator __position, list& __x) { - if (!__x.empty()) - this->transfer(__position, __x.begin(), __x.end()); - } - void splice(iterator __position, list&, iterator __i) { - iterator __j = __i; - ++__j; - if (__position == __i || __position == __j) return; - this->transfer(__position, __i, __j); - } - void splice(iterator __position, list&, iterator __first, iterator __last) { - if (__first != __last) - this->transfer(__position, __first, __last); - } - void remove(const _Tp& __value); - void unique(); - void merge(list& __x); - void reverse(); - void sort(); - - template void remove_if(_Predicate); - template void unique(_BinaryPredicate); - template void merge(list&, _StrictWeakOrdering); - template void sort(_StrictWeakOrdering); -}; - -template -inline bool -operator==(const list<_Tp,_Alloc>& __x, const list<_Tp,_Alloc>& __y) -{ - typedef typename list<_Tp,_Alloc>::const_iterator const_iterator; - const_iterator __end1 = __x.end(); - const_iterator __end2 = __y.end(); - - const_iterator __i1 = __x.begin(); - const_iterator __i2 = __y.begin(); - while (__i1 != __end1 && __i2 != __end2 && *__i1 == *__i2) { - ++__i1; - ++__i2; - } - return __i1 == __end1 && __i2 == __end2; -} + template + inline bool + operator<(const list<_Tp,_Alloc>& __x, const list<_Tp,_Alloc>& __y) + { + return lexicographical_compare(__x.begin(), __x.end(), + __y.begin(), __y.end()); + } -template -inline bool operator<(const list<_Tp,_Alloc>& __x, - const list<_Tp,_Alloc>& __y) -{ - return lexicographical_compare(__x.begin(), __x.end(), - __y.begin(), __y.end()); -} - -template -inline bool operator!=(const list<_Tp,_Alloc>& __x, - const list<_Tp,_Alloc>& __y) { - return !(__x == __y); -} - -template -inline bool operator>(const list<_Tp,_Alloc>& __x, - const list<_Tp,_Alloc>& __y) { - return __y < __x; -} - -template -inline bool operator<=(const list<_Tp,_Alloc>& __x, - const list<_Tp,_Alloc>& __y) { - return !(__y < __x); -} - -template -inline bool operator>=(const list<_Tp,_Alloc>& __x, - const list<_Tp,_Alloc>& __y) { - return !(__x < __y); -} - -template -inline void -swap(list<_Tp, _Alloc>& __x, list<_Tp, _Alloc>& __y) -{ - __x.swap(__y); -} - -template template -void -list<_Tp, _Alloc>::_M_insert_dispatch(iterator __position, - _InputIter __first, _InputIter __last, - __false_type) -{ - for ( ; __first != __last; ++__first) - insert(__position, *__first); -} - -template -void -list<_Tp, _Alloc>::_M_fill_insert(iterator __position, - size_type __n, const _Tp& __x) -{ - for ( ; __n > 0; --__n) - insert(__position, __x); -} + template + inline bool + operator!=(const list<_Tp,_Alloc>& __x, const list<_Tp,_Alloc>& __y) + { return !(__x == __y); } + + template + inline bool + operator>(const list<_Tp,_Alloc>& __x, const list<_Tp,_Alloc>& __y) + { return __y < __x; } + + template + inline bool + operator<=(const list<_Tp,_Alloc>& __x, const list<_Tp,_Alloc>& __y) + { return !(__y < __x); } + + template + inline bool + operator>=(const list<_Tp,_Alloc>& __x, const list<_Tp,_Alloc>& __y) + { return !(__x < __y); } + + template + inline void + swap(list<_Tp, _Alloc>& __x, list<_Tp, _Alloc>& __y) + { __x.swap(__y); } + + // move these to stl_list.tcc + + template + void _List_base<_Tp,_Alloc>:: + clear() + { + _List_node<_Tp>* __cur = static_cast<_List_node<_Tp>*>(_M_node->_M_next); + while (__cur != _M_node) { + _List_node<_Tp>* __tmp = __cur; + __cur = static_cast<_List_node<_Tp>*>(__cur->_M_next); + _Destroy(&__tmp->_M_data); + _M_put_node(__tmp); + } + _M_node->_M_next = _M_node; + _M_node->_M_prev = _M_node; + } -template -typename list<_Tp,_Alloc>::iterator list<_Tp, _Alloc>::erase(iterator __first, - iterator __last) -{ - while (__first != __last) - erase(__first++); - return __last; -} + template + template + void list<_Tp, _Alloc>:: + _M_insert_dispatch(iterator __position, _InputIter __first, _InputIter __last, + __false_type) + { + for ( ; __first != __last; ++__first) + insert(__position, *__first); + + } -template -void list<_Tp, _Alloc>::resize(size_type __new_size, const _Tp& __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); -} - -template -list<_Tp, _Alloc>& list<_Tp, _Alloc>::operator=(const list<_Tp, _Alloc>& __x) -{ - if (this != &__x) { - iterator __first1 = begin(); - iterator __last1 = end(); - const_iterator __first2 = __x.begin(); - const_iterator __last2 = __x.end(); - while (__first1 != __last1 && __first2 != __last2) - *__first1++ = *__first2++; - if (__first2 == __last2) - erase(__first1, __last1); - else - insert(__last1, __first2, __last2); - } - return *this; -} - -template -void list<_Tp, _Alloc>::_M_fill_assign(size_type __n, const _Tp& __val) { - iterator __i = begin(); - for ( ; __i != end() && __n > 0; ++__i, --__n) - *__i = __val; - if (__n > 0) - insert(end(), __n, __val); - else - erase(__i, end()); -} - -template template -void -list<_Tp, _Alloc>::_M_assign_dispatch(_InputIter __first2, _InputIter __last2, - __false_type) -{ - iterator __first1 = begin(); - iterator __last1 = end(); - for ( ; __first1 != __last1 && __first2 != __last2; ++__first1, ++__first2) - *__first1 = *__first2; - if (__first2 == __last2) - erase(__first1, __last1); - else - insert(__last1, __first2, __last2); -} - -template -void list<_Tp, _Alloc>::remove(const _Tp& __value) -{ - iterator __first = begin(); - iterator __last = end(); - while (__first != __last) { - iterator __next = __first; - ++__next; - if (*__first == __value) erase(__first); - __first = __next; - } -} + template + void list<_Tp, _Alloc>:: + _M_fill_insert(iterator __position, size_type __n, const _Tp& __x) + { + for ( ; __n > 0; --__n) + insert(__position, __x); + } -template -void list<_Tp, _Alloc>::unique() -{ - iterator __first = begin(); - iterator __last = end(); - if (__first == __last) return; - iterator __next = __first; - while (++__next != __last) { - if (*__first == *__next) - erase(__next); - else - __first = __next; - __next = __first; - } -} + template + typename list<_Tp,_Alloc>::iterator list<_Tp, _Alloc>:: + erase(iterator __first, iterator __last) + { + while (__first != __last) + erase(__first++); + return __last; + } -template -void list<_Tp, _Alloc>::merge(list<_Tp, _Alloc>& __x) -{ - iterator __first1 = begin(); - iterator __last1 = end(); - iterator __first2 = __x.begin(); - iterator __last2 = __x.end(); - while (__first1 != __last1 && __first2 != __last2) - if (*__first2 < *__first1) { - iterator __next = __first2; - transfer(__first1, __first2, ++__next); - __first2 = __next; + template + void list<_Tp, _Alloc>:: + resize(size_type __new_size, const _Tp& __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); } - else - ++__first1; - if (__first2 != __last2) transfer(__last1, __first2, __last2); -} -inline void __List_base_reverse(_List_node_base* __p) -{ - _List_node_base* __tmp = __p; - do { - std::swap(__tmp->_M_next, __tmp->_M_prev); - __tmp = __tmp->_M_prev; // Old next node is now prev. - } while (__tmp != __p); -} - -template -inline void list<_Tp, _Alloc>::reverse() -{ - __List_base_reverse(this->_M_node); -} + template + list<_Tp, _Alloc>& list<_Tp, _Alloc>:: + operator=(const list<_Tp, _Alloc>& __x) + { + if (this != &__x) { + iterator __first1 = begin(); + iterator __last1 = end(); + const_iterator __first2 = __x.begin(); + const_iterator __last2 = __x.end(); + while (__first1 != __last1 && __first2 != __last2) + *__first1++ = *__first2++; + if (__first2 == __last2) + erase(__first1, __last1); + else + insert(__last1, __first2, __last2); + } + return *this; + } -template -void list<_Tp, _Alloc>::sort() -{ - // Do nothing if the list has length 0 or 1. - if (_M_node->_M_next != _M_node && _M_node->_M_next->_M_next != _M_node) { - list<_Tp, _Alloc> __carry; - list<_Tp, _Alloc> __counter[64]; - int __fill = 0; - while (!empty()) { - __carry.splice(__carry.begin(), *this, begin()); - int __i = 0; - while(__i < __fill && !__counter[__i].empty()) { - __counter[__i].merge(__carry); - __carry.swap(__counter[__i++]); + template + void list<_Tp, _Alloc>:: + _M_fill_assign(size_type __n, const _Tp& __val) { + iterator __i = begin(); + for ( ; __i != end() && __n > 0; ++__i, --__n) + *__i = __val; + if (__n > 0) + insert(end(), __n, __val); + else + erase(__i, end()); + } + + template + template + void list<_Tp, _Alloc>:: + _M_assign_dispatch(_InputIter __first2, _InputIter __last2, __false_type) + { + iterator __first1 = begin(); + iterator __last1 = end(); + for ( ; __first1 != __last1 && __first2 != __last2; ++__first1, ++__first2) + *__first1 = *__first2; + if (__first2 == __last2) + erase(__first1, __last1); + else + insert(__last1, __first2, __last2); } - __carry.swap(__counter[__i]); - if (__i == __fill) ++__fill; - } - for (int __i = 1; __i < __fill; ++__i) - __counter[__i].merge(__counter[__i-1]); - swap(__counter[__fill-1]); - } -} + template + void list<_Tp, _Alloc>:: + remove(const _Tp& __value) + { + iterator __first = begin(); + iterator __last = end(); + while (__first != __last) { + iterator __next = __first; + ++__next; + if (*__first == __value) erase(__first); + __first = __next; + } + } -template template -void list<_Tp, _Alloc>::remove_if(_Predicate __pred) -{ - iterator __first = begin(); - iterator __last = end(); - while (__first != __last) { - iterator __next = __first; - ++__next; - if (__pred(*__first)) erase(__first); - __first = __next; - } -} + template + void list<_Tp, _Alloc>:: + unique() + { + iterator __first = begin(); + iterator __last = end(); + if (__first == __last) return; + iterator __next = __first; + while (++__next != __last) { + if (*__first == *__next) + erase(__next); + else + __first = __next; + __next = __first; + } + } -template template -void list<_Tp, _Alloc>::unique(_BinaryPredicate __binary_pred) -{ - iterator __first = begin(); - iterator __last = end(); - if (__first == __last) return; - iterator __next = __first; - while (++__next != __last) { - if (__binary_pred(*__first, *__next)) - erase(__next); - else - __first = __next; - __next = __first; + template + void list<_Tp, _Alloc>:: + merge(list<_Tp, _Alloc>& __x) + { + iterator __first1 = begin(); + iterator __last1 = end(); + iterator __first2 = __x.begin(); + iterator __last2 = __x.end(); + while (__first1 != __last1 && __first2 != __last2) + if (*__first2 < *__first1) { + iterator __next = __first2; + _M_transfer(__first1, __first2, ++__next); + __first2 = __next; + } + else + ++__first1; + if (__first2 != __last2) _M_transfer(__last1, __first2, __last2); + } + + inline void + __List_base_reverse(_List_node_base* __p) + { + _List_node_base* __tmp = __p; + do { + std::swap(__tmp->_M_next, __tmp->_M_prev); + __tmp = __tmp->_M_prev; // Old next node is now prev. + } while (__tmp != __p); } -} -template template -void list<_Tp, _Alloc>::merge(list<_Tp, _Alloc>& __x, - _StrictWeakOrdering __comp) -{ - iterator __first1 = begin(); - iterator __last1 = end(); - iterator __first2 = __x.begin(); - iterator __last2 = __x.end(); - while (__first1 != __last1 && __first2 != __last2) - if (__comp(*__first2, *__first1)) { - iterator __next = __first2; - transfer(__first1, __first2, ++__next); - __first2 = __next; + template + inline void list<_Tp, _Alloc>:: + reverse() + { __List_base_reverse(this->_M_node); } + + template + void list<_Tp, _Alloc>:: + sort() + { + // Do nothing if the list has length 0 or 1. + if (_M_node->_M_next != _M_node && _M_node->_M_next->_M_next != _M_node) { + list<_Tp, _Alloc> __carry; + list<_Tp, _Alloc> __counter[64]; + int __fill = 0; + while (!empty()) { + __carry.splice(__carry.begin(), *this, begin()); + int __i = 0; + while(__i < __fill && !__counter[__i].empty()) { + __counter[__i].merge(__carry); + __carry.swap(__counter[__i++]); + } + __carry.swap(__counter[__i]); + if (__i == __fill) ++__fill; + } + + for (int __i = 1; __i < __fill; ++__i) + __counter[__i].merge(__counter[__i-1]); + swap(__counter[__fill-1]); + } } - else - ++__first1; - if (__first2 != __last2) transfer(__last1, __first2, __last2); -} -template template -void list<_Tp, _Alloc>::sort(_StrictWeakOrdering __comp) -{ - // Do nothing if the list has length 0 or 1. - if (_M_node->_M_next != _M_node && _M_node->_M_next->_M_next != _M_node) { - list<_Tp, _Alloc> __carry; - list<_Tp, _Alloc> __counter[64]; - int __fill = 0; - while (!empty()) { - __carry.splice(__carry.begin(), *this, begin()); - int __i = 0; - while(__i < __fill && !__counter[__i].empty()) { - __counter[__i].merge(__carry, __comp); - __carry.swap(__counter[__i++]); + template + template + void list<_Tp, _Alloc>:: + remove_if(_Predicate __pred) + { + iterator __first = begin(); + iterator __last = end(); + while (__first != __last) { + iterator __next = __first; + ++__next; + if (__pred(*__first)) erase(__first); + __first = __next; + } } - __carry.swap(__counter[__i]); - if (__i == __fill) ++__fill; - } - for (int __i = 1; __i < __fill; ++__i) - __counter[__i].merge(__counter[__i-1], __comp); - swap(__counter[__fill-1]); - } -} + template + template + void list<_Tp, _Alloc>:: + unique(_BinaryPredicate __binary_pred) + { + iterator __first = begin(); + iterator __last = end(); + if (__first == __last) return; + iterator __next = __first; + while (++__next != __last) { + if (__binary_pred(*__first, *__next)) + erase(__next); + else + __first = __next; + __next = __first; + } + } + + template + template + void list<_Tp, _Alloc>:: + merge(list<_Tp, _Alloc>& __x, _StrictWeakOrdering __comp) + { + iterator __first1 = begin(); + iterator __last1 = end(); + iterator __first2 = __x.begin(); + iterator __last2 = __x.end(); + while (__first1 != __last1 && __first2 != __last2) + if (__comp(*__first2, *__first1)) { + iterator __next = __first2; + _M_transfer(__first1, __first2, ++__next); + __first2 = __next; + } + else + ++__first1; + if (__first2 != __last2) _M_transfer(__last1, __first2, __last2); + } + + template + template + void list<_Tp, _Alloc>:: + sort(_StrictWeakOrdering __comp) + { + // Do nothing if the list has length 0 or 1. + if (_M_node->_M_next != _M_node && _M_node->_M_next->_M_next != _M_node) { + list<_Tp, _Alloc> __carry; + list<_Tp, _Alloc> __counter[64]; + int __fill = 0; + while (!empty()) { + __carry.splice(__carry.begin(), *this, begin()); + int __i = 0; + while(__i < __fill && !__counter[__i].empty()) { + __counter[__i].merge(__carry, __comp); + __carry.swap(__counter[__i++]); + } + __carry.swap(__counter[__i]); + if (__i == __fill) ++__fill; + } + + for (int __i = 1; __i < __fill; ++__i) + __counter[__i].merge(__counter[__i-1], __comp); + swap(__counter[__fill-1]); + } + } } // namespace std #endif /* __SGI_STL_INTERNAL_LIST_H */ +// vi:set ts=2 sw=2: // Local Variables: // mode:C++ // End: diff --git a/libstdc++-v3/testsuite/23_containers/list_capacity.cc b/libstdc++-v3/testsuite/23_containers/list_capacity.cc new file mode 100644 index 00000000000..133fecd5423 --- /dev/null +++ b/libstdc++-v3/testsuite/23_containers/list_capacity.cc @@ -0,0 +1,70 @@ +// Copyright (C) 2001 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) +// any later version. + +// This library is distributed in the hope that it will be useful, +// but WITHOUT ANY WARRANTY; without Pred the implied warranty of +// 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, 59 Temple Place - Suite 330, Boston, MA 02111-1307, +// USA. + +// 23.2.2.2 list capacity [lib.list.capacity] + +#include +#include + +bool test = true; + +// This test verifies the following. +// +// 23.2.2 bool empty() const +// 23.2.2 size_type size() const +// 23.2.2 iterator begin() +// 23.2.2 iterator end() +// 23.2.2.3 void push_back(const T&) +// 23.2.2 size_type max_size() const +// 23.2.2.2 void resize(size_type s, T c = T()) +// +void +test01() +{ + std::list list0101; + VERIFY(list0101.empty()); + VERIFY(list0101.size() == 0); + + list0101.push_back(1); + VERIFY(!list0101.empty()); + VERIFY(list0101.size() == 1); + + list0101.resize(3, 2); + VERIFY(!list0101.empty()); + VERIFY(list0101.size() == 3); + + std::list::iterator i = list0101.begin(); + VERIFY(*i == 1); ++i; + VERIFY(*i == 2); ++i; + VERIFY(*i == 2); ++i; + VERIFY(i == list0101.end()); + + list0101.resize(0); + VERIFY(list0101.empty()); + VERIFY(list0101.size() == 0); +} + +int +main(int argc, char* argv[]) +{ + test01(); + + return !test; +} + +// vi:set sw=2 ts=2: diff --git a/libstdc++-v3/testsuite/23_containers/list_ctor.cc b/libstdc++-v3/testsuite/23_containers/list_ctor.cc new file mode 100644 index 00000000000..e358e7a9fe4 --- /dev/null +++ b/libstdc++-v3/testsuite/23_containers/list_ctor.cc @@ -0,0 +1,332 @@ +// Copyright (C) 2001 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) +// any later version. + +// This library is distributed in the hope that it will be useful, +// but WITHOUT ANY WARRANTY; without even the implied warranty of +// 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, 59 Temple Place - Suite 330, Boston, MA 02111-1307, +// USA. + +// 23.2.2.1 list constructors, copy, and assignment + +#include +#include + +bool test = true; + +// A nontrivial type. +template + struct A { }; + +// Another nontrivial type +struct B { }; + +// A nontrivial type convertible from an int +struct C { + C(int i) : i_(i) { } + bool operator==(const C& rhs) { return i_ == rhs.i_; } + int i_; +}; + +// Default constructor, basic properties +// +// This test verifies the following. +// 23.2.2.1 explicit list(const a& = Allocator()) +// 23.1 (7) iterator behaviour of empty containers +// 23.2.2 iterator begin() +// 23.2.2 iterator end() +// 23.2.2 size_type size() const +// 23.2.2 existence of required typedefs +// +void +test01() +{ + std::list< A > list0101; + VERIFY(list0101.begin() == list0101.end()); + VERIFY(list0101.size() == 0); + + // check type definitions -- will fail compile if missing + typedef std::list< A >::reference reference; + typedef std::list< A >::const_reference const_reference; + typedef std::list< A >::iterator iterator; + typedef std::list< A >::const_iterator const_iterator; + typedef std::list< A >::size_type size_type; + typedef std::list< A >::difference_type difference_type; + typedef std::list< A >::value_type value_type; + typedef std::list< A >::allocator_type allocator_type; + typedef std::list< A >::pointer pointer; + typedef std::list< A >::const_pointer const_pointer; + typedef std::list< A >::reverse_iterator reverse_iterator; + typedef std::list< A >::const_reverse_iterator const_reverse_iterator; + + // allocator checks? +} + +// Fill constructor +// +// This test verifies the following. +// 23.2.2.1 explicit list(size_type n, const T& v = T(), const a& = Allocator()) +// 23.2.2 const_iterator begin() const +// 23.2.2 const_iterator end() const +// 23.2.2 size_type size() const +// +void +test02() +{ + const int LIST_SIZE = 5; + const int INIT_VALUE = 7; + int count; + std::list::const_iterator i; + + // nontrivial value_type + std::list< A > list0201(LIST_SIZE); + + // default value + std::list list0202(LIST_SIZE); + for (i = list0202.begin(), count = 0; + i != list0202.end(); + ++i, ++count) + VERIFY(*i == 0); + VERIFY(count == LIST_SIZE); + VERIFY(list0202.size() == LIST_SIZE); + + // explicit value + std::list list0203(LIST_SIZE, INIT_VALUE); + for (i = list0203.begin(), count = 0; + i != list0203.end(); + ++i, ++count) + VERIFY(*i == INIT_VALUE); + VERIFY(count == LIST_SIZE); + VERIFY(list0203.size() == LIST_SIZE); +} + +// Fill constructor disguised as a range constructor +void +test02D() +{ + const int LIST_SIZE = 5; + const int INIT_VALUE = 7; + int count = 0; + std::list list0204(LIST_SIZE, INIT_VALUE); + std::list::iterator i = list0204.begin(); + for (; i != list0204.end(); ++i, ++count) + VERIFY(*i == INIT_VALUE); + VERIFY(count == LIST_SIZE); + VERIFY(list0204.size() == LIST_SIZE); +} + +// Range constructor +// +// This test verifies the following. +// 23.2.2.1 template list(InputIterator f, InputIterator l, const Allocator& a = Allocator()) +// 23.2.2 const_iterator begin() const +// 23.2.2 const_iterator end() const +// 23.2.2 size_type size() const +// +void +test03() +{ + const int A[] = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17}; + const int N = sizeof(A) / sizeof(int); + int count; + std::list::const_iterator i; + + // construct from a dissimilar range + std::list list0301(A, A + N); + for (i = list0301.begin(), count = 0; + i != list0301.end(); + ++i, ++count) + VERIFY(*i == A[count]); + VERIFY(count == N); + VERIFY(list0301.size() == N); + + // construct from a similar range + std::list list0302(list0301.begin(), list0301.end()); + for (i = list0302.begin(), count = 0; + i != list0302.end(); + ++i, ++count) + VERIFY(*i == A[count]); + VERIFY(count == N); + VERIFY(list0302.size() == N); +} + +// Copy constructor +// +// This test verifies the following. +// 23.2.2.1 list(const list& x) +// 23.2.2 reverse_iterator rbegin() +// 23.2.2 reverse_iterator rend() +// 23.2.2 size_type size() const +// +void +test04() +{ + const int A[] = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17}; + const int N = sizeof(A) / sizeof(int); + int count; + std::list::reverse_iterator i; + std::list list0401(A, A + N); + + std::list list0402(list0401); + for (i = list0401.rbegin(), count = N - 1; + i != list0401.rend(); + ++i, --count) + VERIFY(*i == A[count]); + VERIFY(count == -1); + VERIFY(list0401.size() == N); +} + +// Range assign +// +// This test verifies the following. +// 23.2.2.1 void assign(InputIterator f, InputIterator l) +// 23.2.2 const_iterator begin() const +// 23.2.2 const_iterator end() const +// 23.2.2 size_type size() const +// +void +test05() +{ + const int A[] = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17}; + const int B[] = {101, 102, 103, 104, 105}; + const int N = sizeof(A) / sizeof(int); + const int M = sizeof(B) / sizeof(int); + int count; + std::list::const_iterator i; + + std::list list0501; + + // make it bigger + list0501.assign(A, A + N); + for (i = list0501.begin(), count = 0; + i != list0501.end(); + ++i, ++count) + VERIFY(*i == A[count]); + VERIFY(count == N); + VERIFY(list0501.size() == N); + + // make it smaller + list0501.assign(B, B + M); + for (i = list0501.begin(), count = 0; + i != list0501.end(); + ++i, ++count) + VERIFY(*i == B[count]); + VERIFY(count == M); + VERIFY(list0501.size() == M); +} + +// Fill assign +// +// This test verifies the following. +// 23.2.2.1 void assign(size_type n, const T& v) +// 23.2.2 const_iterator begin() const +// 23.2.2 const_iterator end() const +// 23.2.2 size_type size() const +// +void +test06() +{ + const int BIG_LIST_SIZE = 11; + const int BIG_INIT_VALUE = 7; + const int SMALL_LIST_SIZE = 5; + const int SMALL_INIT_VALUE = 17; + int count; + std::list::const_iterator i; + + std::list list0601; + VERIFY(list0601.size() == 0); + + // make it bigger + list0601.assign(BIG_LIST_SIZE, BIG_INIT_VALUE); + for (i = list0601.begin(), count = 0; + i != list0601.end(); + ++i, ++count) + VERIFY(*i == BIG_INIT_VALUE); + VERIFY(count == BIG_LIST_SIZE); + VERIFY(list0601.size() == BIG_LIST_SIZE); + + // make it shrink + list0601.assign(SMALL_LIST_SIZE, SMALL_INIT_VALUE); + for (i = list0601.begin(), count = 0; + i != list0601.end(); + ++i, ++count) + VERIFY(*i == SMALL_INIT_VALUE); + VERIFY(count == SMALL_LIST_SIZE); + VERIFY(list0601.size() == SMALL_LIST_SIZE); +} + +// Fill Assignment disguised as a Range Assignment +void +test06D() +{ + const int LIST_SIZE = 5; + const int INIT_VALUE = 7; + int count = 0; + std::list list0604; + VERIFY(list0604.size() == 0); + + list0604.assign(LIST_SIZE, INIT_VALUE); + std::list::iterator i = list0604.begin(); + for (; i != list0604.end(); ++i, ++count) + VERIFY(*i == INIT_VALUE); + VERIFY(count == LIST_SIZE); + VERIFY(list0604.size() == LIST_SIZE); +} + +// Assignment operator +// +// This test verifies the following. +// 23.2.2 operator=(const list& x) +// 23.2.2 iterator begin() +// 23.2.2 iterator end() +// 23.2.2 size_type size() const +// 23.2.2 bool operator==(const list& x, const list& y) +// +void +test07() +{ + const int A[] = {701, 702, 703, 704, 705}; + const int N = sizeof(A) / sizeof(int); + int count; + std::list::iterator i; + + std::list list0701(A, A + N); + VERIFY(list0701.size() == N); + + std::list list0702; + VERIFY(list0702.size() == 0); + + list0702 = list0701; + VERIFY(list0702.size() == N); + for (i = list0702.begin(), count = 0; + i != list0702.end(); + ++i, ++count) + VERIFY(*i == A[count]); + VERIFY(count == N); + VERIFY(list0702 == list0701); +} + +int main() +{ + test01(); + test02(); + test02D(); + test03(); + test04(); + test05(); + test06(); + test06D(); + test07(); + + return !test; +} +// vi:set sw=2 ts=2: diff --git a/libstdc++-v3/testsuite/23_containers/list_modifiers.cc b/libstdc++-v3/testsuite/23_containers/list_modifiers.cc new file mode 100644 index 00000000000..9ce078143ad --- /dev/null +++ b/libstdc++-v3/testsuite/23_containers/list_modifiers.cc @@ -0,0 +1,325 @@ +// Copyright (C) 2001 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) +// any later version. + +// This library is distributed in the hope that it will be useful, +// but WITHOUT ANY WARRANTY; without Pred the implied warranty of +// 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, 59 Temple Place - Suite 330, Boston, MA 02111-1307, +// USA. + +// 23.2.2.3 list modifiers [lib.list.modifiers] + +#include +#include + +bool test = true; + +// Here's a class with nontrivial ctor/dtor that provides +// the ability to track the number of copy ctors and dtors +// and will throw on demand during copy. +class T +{ +public: + // default constructor + T(int anId, bool throwOnDemand = false) + : itsId(anId), willThrow(throwOnDemand) + { } + + // copy constructor + T(const T& rhs) + : itsId(rhs.id()), willThrow(rhs.willThrow) + { + ++itsCopyCount; + if (willThrow) + throw "exception"; + } + + ~T() + { ++itsDtorCount; } + + int + id() const + { return itsId; } + +private: + const int itsId; + const bool willThrow; + +public: + static void + reset() + { itsCopyCount = 0; itsDtorCount = 0; } + + static int + copyCount() + { return itsCopyCount; } + + static int + dtorCount() + { return itsDtorCount; } + +private: + static int itsCopyCount; + static int itsDtorCount; +}; + +int T::itsCopyCount = 0; +int T::itsDtorCount = 0; + + +// This test verifies the following. +// +// 23.2.2.3 void push_front(const T& x) +// 23.2.2.3 void push_back(const T& x) +// 23.2.2.3 (1) iterator and reference non-invalidation +// 23.2.2.3 (1) exception effects +// 23.2.2.3 (2) complexity requirements +// +// 23.2.2.3 void pop_front() +// 23.2.2.3 void pop_back() +// 23.2.2.3 (3) iterator and reference non-invalidation +// 23.2.2.3 (5) complexity requirements +// +// 23.2.2 const_iterator begin() const +// 23.2.2 iterator end() +// 23.2.2 const_reverse_iterator rbegin() const +// 23.2.2 _reference front() +// 23.2.2 const_reference front() const +// 23.2.2 reference back() +// 23.2.2 const_reference back() const +// +void +test01() +{ + std::list list0101; + std::list::const_iterator i; + std::list::const_reverse_iterator j; + std::list::iterator k; + T::reset(); + + list0101.push_back(T(1)); // list should be [1] + VERIFY(list0101.size() == 1); + VERIFY(T::copyCount() == 1); + + k = list0101.end(); + --k; + VERIFY(k->id() == 1); + VERIFY(k->id() == list0101.front().id()); + VERIFY(k->id() == list0101.back().id()); + + list0101.push_front(T(2)); // list should be [2 1] + VERIFY(list0101.size() == 2); + VERIFY(T::copyCount() == 2); + VERIFY(k->id() == 1); + + list0101.push_back(T(3)); // list should be [2 1 3] + VERIFY(list0101.size() == 3); + VERIFY(T::copyCount() == 3); + VERIFY(k->id() == 1); + + try + { + list0101.push_back(T(4, true)); + VERIFY(("no exception thrown", false)); + } + catch (...) + { + VERIFY(list0101.size() == 3); + VERIFY(T::copyCount() == 4); + } + + i = list0101.begin(); + VERIFY(i->id() == 2); + VERIFY(i->id() == list0101.front().id()); + + j = list0101.rbegin(); + VERIFY(j->id() == 3); + VERIFY(j->id() == list0101.back().id()); + + ++i; + VERIFY(i->id() == 1); + + ++j; + VERIFY(j->id() == 1); + + T::reset(); + + list0101.pop_back(); // list should be [2 1] + VERIFY(list0101.size() == 2); + VERIFY(T::dtorCount() == 1); + VERIFY(i->id() == 1); + VERIFY(j->id() == 1); + VERIFY(k->id() == 1); + + list0101.pop_front(); // list should be [1] + VERIFY(list0101.size() == 1); + VERIFY(T::dtorCount() == 2); + VERIFY(i->id() == 1); + VERIFY(j->id() == 1); + VERIFY(k->id() == 1); +} + +// general single insert/erase + swap +void +test02() +{ + std::list list0201; + T::reset(); + + list0201.insert(list0201.begin(), T(1)); // list should be [1] + VERIFY(list0201.size() == 1); + VERIFY(T::copyCount() == 1); + + list0201.insert(list0201.end(), T(2)); // list should be [1 2] + VERIFY(list0201.size() == 2); + VERIFY(T::copyCount() == 2); + + std::list::iterator i = list0201.begin(); + std::list::const_iterator j = i; + VERIFY(i->id() == 1); ++i; + VERIFY(i->id() == 2); + + list0201.insert(i, T(3)); // list should be [1 3 2] + VERIFY(list0201.size() == 3); + VERIFY(T::copyCount() == 3); + + std::list::const_iterator k = i; + VERIFY(i->id() == 2); --i; + VERIFY(i->id() == 3); --i; + VERIFY(i->id() == 1); + VERIFY(j->id() == 1); + + ++i; // will point to '3' + T::reset(); + list0201.erase(i); // should be [1 2] + VERIFY(list0201.size() == 2); + VERIFY(T::dtorCount() == 1); + VERIFY(k->id() == 2); + VERIFY(j->id() == 1); + + std::list list0202; + T::reset(); + VERIFY(list0202.size() == 0); + VERIFY(T::copyCount() == 0); + VERIFY(T::dtorCount() == 0); + + // member swap + list0202.swap(list0201); + VERIFY(list0201.size() == 0); + VERIFY(list0202.size() == 2); + VERIFY(T::copyCount() == 0); + VERIFY(T::dtorCount() == 0); + + // specialized swap + swap(list0201, list0202); + VERIFY(list0201.size() == 2); + VERIFY(list0202.size() == 0); + VERIFY(T::copyCount() == 0); + VERIFY(T::dtorCount() == 0); +} + +// range and fill insert/erase + clear +// missing: o fill insert disguised as a range insert in all its variants +// o exception effects +void +test03() +{ + std::list list0301; + T::reset(); + + // fill insert at beginning of list / empty list + list0301.insert(list0301.begin(), 3, T(11)); // should be [11 11 11] + VERIFY(list0301.size() == 3); + VERIFY(T::copyCount() == 3); + + // save iterators to verify post-insert validity + std::list::iterator b = list0301.begin(); + std::list::iterator m = list0301.end(); --m; + std::list::iterator e = list0301.end(); + + // fill insert at end of list + T::reset(); + list0301.insert(list0301.end(), 3, T(13)); // should be [11 11 11 13 13 13] + VERIFY(list0301.size() == 6); + VERIFY(T::copyCount() == 3); + VERIFY(b == list0301.begin() && b->id() == 11); + VERIFY(e == list0301.end()); + VERIFY(m->id() == 11); + + // fill insert in the middle of list + ++m; + T::reset(); + list0301.insert(m, 3, T(12)); // should be [11 11 11 12 12 12 13 13 13] + VERIFY(list0301.size() == 9); + VERIFY(T::copyCount() == 3); + VERIFY(b == list0301.begin() && b->id() == 11); + VERIFY(e == list0301.end()); + VERIFY(m->id() == 13); + + // single erase + T::reset(); + m = list0301.erase(m); // should be [11 11 11 12 12 12 13 13] + VERIFY(list0301.size() == 8); + VERIFY(T::dtorCount() == 1); + VERIFY(b == list0301.begin() && b->id() == 11); + VERIFY(e == list0301.end()); + VERIFY(m->id() == 13); + + // range erase + T::reset(); + m = list0301.erase(list0301.begin(), m); // should be [13 13] + VERIFY(list0301.size() == 2); + VERIFY(T::dtorCount() == 6); + VERIFY(m->id() == 13); + + // range fill at beginning + const int A[] = {321, 322, 333}; + const int N = sizeof(A) / sizeof(int); + T::reset(); + b = list0301.begin(); + list0301.insert(b, A, A + N); // should be [321 322 333 13 13] + VERIFY(list0301.size() == 5); + VERIFY(T::copyCount() == 3); + VERIFY(m->id() == 13); + + // range fill at end + T::reset(); + list0301.insert(e, A, A + N); // should be [321 322 333 13 13 321 322 333] + VERIFY(list0301.size() == 8); + VERIFY(T::copyCount() == 3); + VERIFY(e == list0301.end()); + VERIFY(m->id() == 13); + + // range fill in middle + T::reset(); + list0301.insert(m, A, A + N); + VERIFY(list0301.size() == 11); + VERIFY(T::copyCount() == 3); + VERIFY(e == list0301.end()); + VERIFY(m->id() == 13); + + T::reset(); + list0301.clear(); + VERIFY(list0301.size() == 0); + VERIFY(T::dtorCount() == 11); + VERIFY(e == list0301.end()); +} + +main(int argc, char* argv[]) +{ + test01(); + test02(); + test03(); + + return !test; +} +// vi:set sw=2 ts=2: diff --git a/libstdc++-v3/testsuite/23_containers/list_operators.cc b/libstdc++-v3/testsuite/23_containers/list_operators.cc new file mode 100644 index 00000000000..69a59943e1e --- /dev/null +++ b/libstdc++-v3/testsuite/23_containers/list_operators.cc @@ -0,0 +1,211 @@ +// Copyright (C) 2001 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) +// any later version. + +// This library is distributed in the hope that it will be useful, +// but WITHOUT ANY WARRANTY; without Pred the implied warranty of +// 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, 59 Temple Place - Suite 330, Boston, MA 02111-1307, +// USA. + +// 23.2.2.4 list operations [lib.list.ops] + +#include +#include + +bool test = true; + +// splice(p, x) + remove + reverse +void +test01() +{ + const int K = 417; + const int A[] = {1, 2, 3, 4, 5}; + const int B[] = {K, K, K, K, K}; + const int N = sizeof(A) / sizeof(int); + const int M = sizeof(B) / sizeof(int); + + std::list list0101(A, A + N); + std::list list0102(B, B + M); + std::list::iterator p = list0101.begin(); + + VERIFY(list0101.size() == N); + VERIFY(list0102.size() == M); + + ++p; + list0101.splice(p, list0102); // [1 K K K K K 2 3 4 5] + VERIFY(list0101.size() == N + M); + VERIFY(list0102.size() == 0); + + // remove range from middle + list0101.remove(K); + VERIFY(list0101.size() == N); + + // remove first element + list0101.remove(1); + VERIFY(list0101.size() == N - 1); + + // remove last element + list0101.remove(5); + VERIFY(list0101.size() == N - 2); + + // reverse + list0101.reverse(); + p = list0101.begin(); + VERIFY(*p == 4); ++p; + VERIFY(*p == 3); ++p; + VERIFY(*p == 2); ++p; + VERIFY(p == list0101.end()); +} + +// splice(p, x, i) + remove_if + operator== +void +test02() +{ + const int A[] = {1, 2, 3, 4, 5}; + const int B[] = {2, 1, 3, 4, 5}; + const int C[] = {1, 3, 4, 5, 2}; + const int N = sizeof(A) / sizeof(int); + std::list list0201(A, A + N); + std::list list0202(A, A + N); + std::list list0203(B, B + N); + std::list list0204(C, C + N); + std::list::iterator i = list0201.begin(); + + // result should be unchanged + list0201.splice(list0201.begin(), list0201, i); + VERIFY(list0201 == list0202); + + // result should be [2 1 3 4 5] + ++i; + list0201.splice(list0201.begin(), list0201, i); + VERIFY(list0201 != list0202); + VERIFY(list0201 == list0203); + + // result should be [1 3 4 5 2] + list0201.splice(list0201.end(), list0201, i); + VERIFY(list0201 == list0204); +} + +// splice(p, x, f, l) + sort + merge + unique +void +test03() +{ + const int A[] = {103, 203, 603, 303, 403, 503}; + const int B[] = {417, 417, 417, 417, 417}; + const int E[] = {103, 417, 417, 203, 603, 303, 403, 503}; + const int F[] = {103, 203, 303, 403, 417, 417, 503, 603}; + const int C[] = {103, 203, 303, 403, 417, 417, 417, 417, 417, 503, 603}; + const int D[] = {103, 203, 303, 403, 417, 503, 603}; + const int N = sizeof(A) / sizeof(int); + const int M = sizeof(B) / sizeof(int); + const int P = sizeof(C) / sizeof(int); + const int Q = sizeof(D) / sizeof(int); + const int R = sizeof(E) / sizeof(int); + + std::list list0301(A, A + N); + std::list list0302(B, B + M); + std::list list0303(C, C + P); + std::list list0304(D, D + Q); + std::list list0305(E, E + R); + std::list list0306(F, F + R); + std::list::iterator p = list0301.begin(); + std::list::iterator q = list0302.begin(); + + ++p; ++q; ++q; + list0301.splice(p, list0302, list0302.begin(), q); + VERIFY(list0301 == list0305); + VERIFY(list0301.size() == N + 2); + VERIFY(list0302.size() == M - 2); + + list0301.sort(); + VERIFY(list0301 == list0306); + + list0301.merge(list0302); + VERIFY(list0301.size() == N + M); + VERIFY(list0302.size() == 0); + VERIFY(list0301 == list0303); + + list0301.unique(); + VERIFY(list0301 == list0304); +} + +// A comparison predicate to order by rightmost digit. Tracks call counts for +// performance checks. +struct CompLastLt +{ + bool operator()(const int x, const int y) { ++itsCount; return x % 10 < y % 10; } + static int count() { return itsCount; } + static void reset() { itsCount = 0; } + static int itsCount; +}; + +int CompLastLt::itsCount; + +struct CompLastEq +{ + bool operator()(const int x, const int y) { ++itsCount; return x % 10 == y % 10; } + static int count() { return itsCount; } + static void reset() { itsCount = 0; } + static int itsCount; +}; + +int CompLastEq::itsCount; + +// sort(pred) + merge(pred) + unique(pred) +// also checks performance requirements +void +test04() +{ + const int A[] = {1, 2, 3, 4, 5, 6}; + const int B[] = {12, 15, 13, 14, 11}; + const int C[] = {11, 12, 13, 14, 15}; + const int D[] = {1, 11, 2, 12, 3, 13, 4, 14, 5, 15, 6}; + const int N = sizeof(A) / sizeof(int); + const int M = sizeof(B) / sizeof(int); + const int Q = sizeof(D) / sizeof(int); + + std::list list0401(A, A + N); + std::list list0402(B, B + M); + std::list list0403(C, C + M); + std::list list0404(D, D + Q); + std::list list0405(A, A + N); + + // sort B + CompLastLt lt; + + CompLastLt::reset(); + list0402.sort(lt); + VERIFY(list0402 == list0403); + + CompLastLt::reset(); + list0401.merge(list0402, lt); + VERIFY(list0401 == list0404); + VERIFY(lt.count() <= (N + M - 1)); + + CompLastEq eq; + + CompLastEq::reset(); + list0401.unique(eq); + VERIFY(list0401 == list0405); + VERIFY(eq.count() == (N + M - 1)); +} + +main(int argc, char* argv[]) +{ + test01(); + test02(); + test03(); + test04(); + + return !test; +} +// vi:set sw=2 ts=2: -- 2.30.2