diff options
Diffstat (limited to 'libstdc++-v3/include/ext/slist')
-rw-r--r-- | libstdc++-v3/include/ext/slist | 198 |
1 files changed, 41 insertions, 157 deletions
diff --git a/libstdc++-v3/include/ext/slist b/libstdc++-v3/include/ext/slist index ef0906279a9..0c114e9e947 100644 --- a/libstdc++-v3/include/ext/slist +++ b/libstdc++-v3/include/ext/slist @@ -1,3 +1,32 @@ +// Singly-linked list implementation -*- C++ -*- + +// 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. + +// 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. + /* * Copyright (c) 1997 * Silicon Graphics Computer Systems, Inc. @@ -19,14 +48,14 @@ #ifndef __SGI_STL_INTERNAL_SLIST_H #define __SGI_STL_INTERNAL_SLIST_H -#include <bits/concept_checks.h> - -__STL_BEGIN_NAMESPACE +#include <bits/stl_algobase.h> +#include <bits/stl_alloc.h> +#include <bits/stl_construct.h> +#include <bits/stl_uninitialized.h> +#include <bits/concept_check.h> -#if defined(__sgi) && !defined(__GNUC__) && (_MIPS_SIM != _MIPS_SIM_ABI32) -#pragma set woff 1174 -#pragma set woff 1375 -#endif +namespace std +{ struct _Slist_node_base { @@ -149,9 +178,7 @@ struct _Slist_iterator : public _Slist_iterator_base _Slist_iterator(const iterator& __x) : _Slist_iterator_base(__x._M_node) {} reference operator*() const { return ((_Node*) _M_node)->_M_data; } -#ifndef __SGI_STL_NO_ARROW_OPERATOR pointer operator->() const { return &(operator*()); } -#endif /* __SGI_STL_NO_ARROW_OPERATOR */ _Self& operator++() { @@ -166,22 +193,6 @@ struct _Slist_iterator : public _Slist_iterator_base } }; -#ifndef __STL_CLASS_PARTIAL_SPECIALIZATION - -inline ptrdiff_t* distance_type(const _Slist_iterator_base&) { - return 0; -} - -inline forward_iterator_tag iterator_category(const _Slist_iterator_base&) { - return forward_iterator_tag(); -} - -template <class _Tp, class _Ref, class _Ptr> -inline _Tp* value_type(const _Slist_iterator<_Tp, _Ref, _Ptr>&) { - return 0; -} - -#endif /* __STL_CLASS_PARTIAL_SPECIALIZATION */ // Base class that encapsulates details of allocators. Three cases: // an ordinary standard-conforming allocator, a standard-conforming @@ -190,8 +201,6 @@ inline _Tp* value_type(const _Slist_iterator<_Tp, _Ref, _Ptr>&) { // compatibility and because we want to avoid wasting storage on an // allocator instance if it isn't necessary. -#ifdef __STL_USE_STD_ALLOCATORS - // Base for general standard-conforming allocators. template <class _Tp, class _Allocator, bool _IsStatic> class _Slist_alloc_base { @@ -263,38 +272,6 @@ protected: _Slist_node_base* _M_erase_after(_Slist_node_base*, _Slist_node_base*); }; -#else /* __STL_USE_STD_ALLOCATORS */ - -template <class _Tp, class _Alloc> -struct _Slist_base { - typedef _Alloc allocator_type; - allocator_type get_allocator() const { return allocator_type(); } - - _Slist_base(const allocator_type&) { _M_head._M_next = 0; } - ~_Slist_base() { _M_erase_after(&_M_head, 0); } - -protected: - typedef simple_alloc<_Slist_node<_Tp>, _Alloc> _Alloc_type; - _Slist_node<_Tp>* _M_get_node() { return _Alloc_type::allocate(1); } - void _M_put_node(_Slist_node<_Tp>* __p) { _Alloc_type::deallocate(__p, 1); } - - _Slist_node_base* _M_erase_after(_Slist_node_base* __pos) - { - _Slist_node<_Tp>* __next = (_Slist_node<_Tp>*) (__pos->_M_next); - _Slist_node_base* __next_next = __next->_M_next; - __pos->_M_next = __next_next; - destroy(&__next->_M_data); - _M_put_node(__next); - return __next_next; - } - _Slist_node_base* _M_erase_after(_Slist_node_base*, _Slist_node_base*); - -protected: - _Slist_node_base _M_head; -}; - -#endif /* __STL_USE_STD_ALLOCATORS */ - template <class _Tp, class _Alloc> _Slist_node_base* _Slist_base<_Tp,_Alloc>::_M_erase_after(_Slist_node_base* __before_first, @@ -310,12 +287,11 @@ _Slist_base<_Tp,_Alloc>::_M_erase_after(_Slist_node_base* __before_first, return __last_node; } -template <class _Tp, class _Alloc = __STL_DEFAULT_ALLOCATOR(_Tp) > +template <class _Tp, class _Alloc = allocator<_Tp> > class slist : private _Slist_base<_Tp,_Alloc> { - // requirements: - - __STL_CLASS_REQUIRES(_Tp, _Assignable); + // concept requirements + __glibcpp_class_requires(_Tp, _SGIAssignableConcept); private: typedef _Slist_base<_Tp,_Alloc> _Base; @@ -369,7 +345,6 @@ public: explicit slist(size_type __n) : _Base(allocator_type()) { _M_insert_after_fill(&this->_M_head, __n, value_type()); } -#ifdef __STL_MEMBER_TEMPLATES // We don't need any dispatching tricks here, because _M_insert_after_range // already does them. template <class _InputIterator> @@ -377,15 +352,6 @@ public: const allocator_type& __a = allocator_type()) : _Base(__a) { _M_insert_after_range(&this->_M_head, __first, __last); } -#else /* __STL_MEMBER_TEMPLATES */ - slist(const_iterator __first, const_iterator __last, - const allocator_type& __a = allocator_type()) : _Base(__a) - { _M_insert_after_range(&this->_M_head, __first, __last); } - slist(const value_type* __first, const value_type* __last, - const allocator_type& __a = allocator_type()) : _Base(__a) - { _M_insert_after_range(&this->_M_head, __first, __last); } -#endif /* __STL_MEMBER_TEMPLATES */ - slist(const slist& __x) : _Base(__x.get_allocator()) { _M_insert_after_range(&this->_M_head, __x.begin(), __x.end()); } @@ -404,9 +370,6 @@ public: void _M_fill_assign(size_type __n, const _Tp& __val); - -#ifdef __STL_MEMBER_TEMPLATES - template <class _InputIterator> void assign(_InputIterator __first, _InputIterator __last) { typedef typename _Is_integer<_InputIterator>::_Integral _Integral; @@ -421,8 +384,6 @@ public: void _M_assign_dispatch(_InputIterator __first, _InputIterator __last, __false_type); -#endif /* __STL_MEMBER_TEMPLATES */ - public: iterator begin() { return iterator((_Node*)this->_M_head._M_next); } @@ -450,7 +411,7 @@ public: bool empty() const { return this->_M_head._M_next == 0; } void swap(slist& __x) - { __STD::swap(this->_M_head._M_next, __x._M_head._M_next); } + { std::swap(this->_M_head._M_next, __x._M_head._M_next); } public: @@ -491,8 +452,6 @@ private: __pos = __slist_make_link(__pos, _M_create_node(__x)); } -#ifdef __STL_MEMBER_TEMPLATES - // Check whether it's an integral type. If so, it's not an iterator. template <class _InIter> void _M_insert_after_range(_Node_base* __pos, @@ -517,26 +476,6 @@ private: } } -#else /* __STL_MEMBER_TEMPLATES */ - - void _M_insert_after_range(_Node_base* __pos, - const_iterator __first, const_iterator __last) { - while (__first != __last) { - __pos = __slist_make_link(__pos, _M_create_node(*__first)); - ++__first; - } - } - void _M_insert_after_range(_Node_base* __pos, - const value_type* __first, - const value_type* __last) { - while (__first != __last) { - __pos = __slist_make_link(__pos, _M_create_node(*__first)); - ++__first; - } - } - -#endif /* __STL_MEMBER_TEMPLATES */ - public: iterator insert_after(iterator __pos, const value_type& __x) { @@ -551,8 +490,6 @@ public: _M_insert_after_fill(__pos._M_node, __n, __x); } -#ifdef __STL_MEMBER_TEMPLATES - // We don't need any dispatching tricks here, because _M_insert_after_range // already does them. template <class _InIter> @@ -560,19 +497,6 @@ public: _M_insert_after_range(__pos._M_node, __first, __last); } -#else /* __STL_MEMBER_TEMPLATES */ - - void insert_after(iterator __pos, - const_iterator __first, const_iterator __last) { - _M_insert_after_range(__pos._M_node, __first, __last); - } - void insert_after(iterator __pos, - const value_type* __first, const value_type* __last) { - _M_insert_after_range(__pos._M_node, __first, __last); - } - -#endif /* __STL_MEMBER_TEMPLATES */ - iterator insert(iterator __pos, const value_type& __x) { return iterator(_M_insert_after(__slist_previous(&this->_M_head, __pos._M_node), @@ -590,8 +514,6 @@ public: __n, __x); } -#ifdef __STL_MEMBER_TEMPLATES - // We don't need any dispatching tricks here, because _M_insert_after_range // already does them. template <class _InIter> @@ -600,21 +522,6 @@ public: __first, __last); } -#else /* __STL_MEMBER_TEMPLATES */ - - void insert(iterator __pos, const_iterator __first, const_iterator __last) { - _M_insert_after_range(__slist_previous(&this->_M_head, __pos._M_node), - __first, __last); - } - void insert(iterator __pos, const value_type* __first, - const value_type* __last) { - _M_insert_after_range(__slist_previous(&this->_M_head, __pos._M_node), - __first, __last); - } - -#endif /* __STL_MEMBER_TEMPLATES */ - - public: iterator erase_after(iterator __pos) { return iterator((_Node*) this->_M_erase_after(__pos._M_node)); @@ -700,7 +607,6 @@ public: void merge(slist& __x); void sort(); -#ifdef __STL_MEMBER_TEMPLATES template <class _Predicate> void remove_if(_Predicate __pred); @@ -712,7 +618,6 @@ public: template <class _StrictWeakOrdering> void sort(_StrictWeakOrdering __comp); -#endif /* __STL_MEMBER_TEMPLATES */ }; template <class _Tp, class _Alloc> @@ -752,8 +657,6 @@ void slist<_Tp, _Alloc>::_M_fill_assign(size_type __n, const _Tp& __val) { this->_M_erase_after(__prev, 0); } -#ifdef __STL_MEMBER_TEMPLATES - template <class _Tp, class _Alloc> template <class _InputIter> void slist<_Tp, _Alloc>::_M_assign_dispatch(_InputIter __first, _InputIter __last, @@ -773,8 +676,6 @@ slist<_Tp, _Alloc>::_M_assign_dispatch(_InputIter __first, _InputIter __last, this->_M_erase_after(__prev, 0); } -#endif /* __STL_MEMBER_TEMPLATES */ - template <class _Tp, class _Alloc> inline bool operator==(const slist<_Tp,_Alloc>& _SL1, const slist<_Tp,_Alloc>& _SL2) @@ -801,8 +702,6 @@ operator<(const slist<_Tp,_Alloc>& _SL1, const slist<_Tp,_Alloc>& _SL2) _SL2.begin(), _SL2.end()); } -#ifdef __STL_FUNCTION_TMPL_PARTIAL_ORDER - template <class _Tp, class _Alloc> inline bool operator!=(const slist<_Tp,_Alloc>& _SL1, const slist<_Tp,_Alloc>& _SL2) { @@ -832,8 +731,6 @@ inline void swap(slist<_Tp,_Alloc>& __x, slist<_Tp,_Alloc>& __y) { __x.swap(__y); } -#endif /* __STL_FUNCTION_TMPL_PARTIAL_ORDER */ - template <class _Tp, class _Alloc> void slist<_Tp,_Alloc>::resize(size_type __len, const _Tp& __x) @@ -919,8 +816,6 @@ void slist<_Tp,_Alloc>::sort() } } -#ifdef __STL_MEMBER_TEMPLATES - template <class _Tp, class _Alloc> template <class _Predicate> void slist<_Tp,_Alloc>::remove_if(_Predicate __pred) @@ -993,13 +888,9 @@ void slist<_Tp,_Alloc>::sort(_StrictWeakOrdering __comp) } } -#endif /* __STL_MEMBER_TEMPLATES */ - // Specialization of insert_iterator so that insertions will be constant // time rather than linear time. -#ifdef __STL_CLASS_PARTIAL_SPECIALIZATION - template <class _Tp, class _Alloc> class insert_iterator<slist<_Tp, _Alloc> > { protected: @@ -1032,14 +923,7 @@ public: insert_iterator<_Container>& operator++(int) { return *this; } }; -#endif /* __STL_CLASS_PARTIAL_SPECIALIZATION */ - -#if defined(__sgi) && !defined(__GNUC__) && (_MIPS_SIM != _MIPS_SIM_ABI32) -#pragma reset woff 1174 -#pragma reset woff 1375 -#endif - -__STL_END_NAMESPACE +} // namespace std #endif /* __SGI_STL_INTERNAL_SLIST_H */ |