diff options
Diffstat (limited to 'contrib/libstdc++/stl/stl_slist.h')
-rw-r--r-- | contrib/libstdc++/stl/stl_slist.h | 945 |
1 files changed, 0 insertions, 945 deletions
diff --git a/contrib/libstdc++/stl/stl_slist.h b/contrib/libstdc++/stl/stl_slist.h deleted file mode 100644 index 6da234d92c2c..000000000000 --- a/contrib/libstdc++/stl/stl_slist.h +++ /dev/null @@ -1,945 +0,0 @@ -/* - * Copyright (c) 1997 - * Silicon Graphics Computer Systems, Inc. - * - * Permission to use, copy, modify, distribute and sell this software - * and its documentation for any purpose is hereby granted without fee, - * provided that the above copyright notice appear in all copies and - * that both that copyright notice and this permission notice appear - * in supporting documentation. Silicon Graphics makes no - * representations about the suitability of this software for any - * purpose. It is provided "as is" without express or implied warranty. - * - */ - -/* NOTE: This is an internal header file, included by other STL headers. - * You should not attempt to use it directly. - */ - -#ifndef __SGI_STL_INTERNAL_SLIST_H -#define __SGI_STL_INTERNAL_SLIST_H - - -__STL_BEGIN_NAMESPACE - -#if defined(__sgi) && !defined(__GNUC__) && (_MIPS_SIM != _MIPS_SIM_ABI32) -#pragma set woff 1174 -#pragma set woff 1375 -#endif - -struct _Slist_node_base -{ - _Slist_node_base* _M_next; -}; - -inline _Slist_node_base* -__slist_make_link(_Slist_node_base* __prev_node, - _Slist_node_base* __new_node) -{ - __new_node->_M_next = __prev_node->_M_next; - __prev_node->_M_next = __new_node; - return __new_node; -} - -inline _Slist_node_base* -__slist_previous(_Slist_node_base* __head, - const _Slist_node_base* __node) -{ - while (__head && __head->_M_next != __node) - __head = __head->_M_next; - return __head; -} - -inline const _Slist_node_base* -__slist_previous(const _Slist_node_base* __head, - const _Slist_node_base* __node) -{ - while (__head && __head->_M_next != __node) - __head = __head->_M_next; - return __head; -} - -inline void __slist_splice_after(_Slist_node_base* __pos, - _Slist_node_base* __before_first, - _Slist_node_base* __before_last) -{ - if (__pos != __before_first && __pos != __before_last) { - _Slist_node_base* __first = __before_first->_M_next; - _Slist_node_base* __after = __pos->_M_next; - __before_first->_M_next = __before_last->_M_next; - __pos->_M_next = __first; - __before_last->_M_next = __after; - } -} - -inline _Slist_node_base* __slist_reverse(_Slist_node_base* __node) -{ - _Slist_node_base* __result = __node; - __node = __node->_M_next; - __result->_M_next = 0; - while(__node) { - _Slist_node_base* __next = __node->_M_next; - __node->_M_next = __result; - __result = __node; - __node = __next; - } - return __result; -} - -inline size_t __slist_size(_Slist_node_base* __node) -{ - size_t __result = 0; - for ( ; __node != 0; __node = __node->_M_next) - ++__result; - return __result; -} - -template <class _Tp> -struct _Slist_node : public _Slist_node_base -{ - _Tp _M_data; -}; - -struct _Slist_iterator_base -{ - typedef size_t size_type; - typedef ptrdiff_t difference_type; - typedef forward_iterator_tag iterator_category; - - _Slist_node_base* _M_node; - - _Slist_iterator_base(_Slist_node_base* __x) : _M_node(__x) {} - void _M_incr() { _M_node = _M_node->_M_next; } - - bool operator==(const _Slist_iterator_base& __x) const { - return _M_node == __x._M_node; - } - bool operator!=(const _Slist_iterator_base& __x) const { - return _M_node != __x._M_node; - } -}; - -template <class _Tp, class _Ref, class _Ptr> -struct _Slist_iterator : public _Slist_iterator_base -{ - typedef _Slist_iterator<_Tp, _Tp&, _Tp*> iterator; - typedef _Slist_iterator<_Tp, const _Tp&, const _Tp*> const_iterator; - typedef _Slist_iterator<_Tp, _Ref, _Ptr> _Self; - - typedef _Tp value_type; - typedef _Ptr pointer; - typedef _Ref reference; - typedef _Slist_node<_Tp> _Node; - - _Slist_iterator(_Node* __x) : _Slist_iterator_base(__x) {} - _Slist_iterator() : _Slist_iterator_base(0) {} - _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++() - { - _M_incr(); - return *this; - } - _Self operator++(int) - { - _Self __tmp = *this; - _M_incr(); - return __tmp; - } -}; - -#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 -// 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. - -#ifdef __STL_USE_STD_ALLOCATORS - -// Base for general standard-conforming allocators. -template <class _Tp, class _Allocator, bool _IsStatic> -class _Slist_alloc_base { -public: - typedef typename _Alloc_traits<_Tp,_Allocator>::allocator_type - allocator_type; - allocator_type get_allocator() const { return _M_node_allocator; } - - _Slist_alloc_base(const allocator_type& __a) : _M_node_allocator(__a) {} - -protected: - _Slist_node<_Tp>* _M_get_node() - { return _M_node_allocator.allocate(1); } - void _M_put_node(_Slist_node<_Tp>* __p) - { _M_node_allocator.deallocate(__p, 1); } - -protected: - typename _Alloc_traits<_Slist_node<_Tp>,_Allocator>::allocator_type - _M_node_allocator; - _Slist_node_base _M_head; -}; - -// Specialization for instanceless allocators. -template <class _Tp, class _Allocator> -class _Slist_alloc_base<_Tp,_Allocator, true> { -public: - typedef typename _Alloc_traits<_Tp,_Allocator>::allocator_type - allocator_type; - allocator_type get_allocator() const { return allocator_type(); } - - _Slist_alloc_base(const allocator_type&) {} - -protected: - typedef typename _Alloc_traits<_Slist_node<_Tp>, _Allocator>::_Alloc_type - _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); } - -protected: - _Slist_node_base _M_head; -}; - - -template <class _Tp, class _Alloc> -struct _Slist_base - : public _Slist_alloc_base<_Tp, _Alloc, - _Alloc_traits<_Tp, _Alloc>::_S_instanceless> -{ - typedef _Slist_alloc_base<_Tp, _Alloc, - _Alloc_traits<_Tp, _Alloc>::_S_instanceless> - _Base; - typedef typename _Base::allocator_type allocator_type; - - _Slist_base(const allocator_type& __a) : _Base(__a) { _M_head._M_next = 0; } - ~_Slist_base() { _M_erase_after(&_M_head, 0); } - -protected: - - _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*); -}; - -#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, - _Slist_node_base* __last_node) { - _Slist_node<_Tp>* __cur = (_Slist_node<_Tp>*) (__before_first->_M_next); - while (__cur != __last_node) { - _Slist_node<_Tp>* __tmp = __cur; - __cur = (_Slist_node<_Tp>*) __cur->_M_next; - destroy(&__tmp->_M_data); - _M_put_node(__tmp); - } - __before_first->_M_next = __last_node; - return __last_node; -} - -template <class _Tp, class _Alloc = __STL_DEFAULT_ALLOCATOR(_Tp) > -class slist : private _Slist_base<_Tp,_Alloc> -{ -private: - typedef _Slist_base<_Tp,_Alloc> _Base; -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 size_t size_type; - typedef ptrdiff_t difference_type; - - typedef _Slist_iterator<_Tp, _Tp&, _Tp*> iterator; - typedef _Slist_iterator<_Tp, const _Tp&, const _Tp*> const_iterator; - - typedef typename _Base::allocator_type allocator_type; - allocator_type get_allocator() const { return _Base::get_allocator(); } - -private: - typedef _Slist_node<_Tp> _Node; - typedef _Slist_node_base _Node_base; - typedef _Slist_iterator_base _Iterator_base; - - _Node* _M_create_node(const value_type& __x) { - _Node* __node = _M_get_node(); - __STL_TRY { - construct(&__node->_M_data, __x); - __node->_M_next = 0; - } - __STL_UNWIND(_M_put_node(__node)); - return __node; - } - - _Node* _M_create_node() { - _Node* __node = _M_get_node(); - __STL_TRY { - construct(&__node->_M_data); - __node->_M_next = 0; - } - __STL_UNWIND(_M_put_node(__node)); - return __node; - } - -private: -#ifdef __STL_USE_NAMESPACES - using _Base::_M_get_node; - using _Base::_M_put_node; - using _Base::_M_erase_after; - using _Base::_M_head; -#endif /* __STL_USE_NAMESPACES */ - -public: - explicit slist(const allocator_type& __a = allocator_type()) : _Base(__a) {} - - slist(size_type __n, const value_type& __x, - const allocator_type& __a = allocator_type()) : _Base(__a) - { _M_insert_after_fill(&_M_head, __n, __x); } - - explicit slist(size_type __n) : _Base(allocator_type()) - { _M_insert_after_fill(&_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> - slist(_InputIterator __first, _InputIterator __last, - const allocator_type& __a = allocator_type()) : _Base(__a) - { _M_insert_after_range(&_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(&_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(&_M_head, __first, __last); } -#endif /* __STL_MEMBER_TEMPLATES */ - - slist(const slist& __x) : _Base(__x.get_allocator()) - { _M_insert_after_range(&_M_head, __x.begin(), __x.end()); } - - slist& operator= (const slist& __x); - - ~slist() {} - -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); - -#ifdef __STL_MEMBER_TEMPLATES - - template <class _InputIterator> - void assign(_InputIterator __first, _InputIterator __last) { - typedef typename _Is_integer<_InputIterator>::_Integral _Integral; - _M_assign_dispatch(__first, __last, _Integral()); - } - - template <class _Integer> - void _M_assign_dispatch(_Integer __n, _Integer __val, __true_type) - { assign((size_type) __n, (_Tp) __val); } - - template <class _InputIterator> - void _M_assign_dispatch(_InputIterator __first, _InputIterator __last, - __false_type); - -#endif /* __STL_MEMBER_TEMPLATES */ - -public: - - iterator begin() { return iterator((_Node*)_M_head._M_next); } - const_iterator begin() const - { return const_iterator((_Node*)_M_head._M_next);} - - iterator end() { return iterator(0); } - const_iterator end() const { return const_iterator(0); } - - size_type size() const { return __slist_size(_M_head._M_next); } - - size_type max_size() const { return size_type(-1); } - - bool empty() const { return _M_head._M_next == 0; } - - void swap(slist& __x) { __STD::swap(_M_head._M_next, __x._M_head._M_next); } - -public: - friend bool operator== __STL_NULL_TMPL_ARGS (const slist<_Tp,_Alloc>& _SL1, - const slist<_Tp,_Alloc>& _SL2); - -public: - - reference front() { return ((_Node*) _M_head._M_next)->_M_data; } - const_reference front() const - { return ((_Node*) _M_head._M_next)->_M_data; } - void push_front(const value_type& __x) { - __slist_make_link(&_M_head, _M_create_node(__x)); - } - void push_front() { __slist_make_link(&_M_head, _M_create_node());} - void pop_front() { - _Node* __node = (_Node*) _M_head._M_next; - _M_head._M_next = __node->_M_next; - destroy(&__node->_M_data); - _M_put_node(__node); - } - - iterator previous(const_iterator __pos) { - return iterator((_Node*) __slist_previous(&_M_head, __pos._M_node)); - } - const_iterator previous(const_iterator __pos) const { - return const_iterator((_Node*) __slist_previous(&_M_head, __pos._M_node)); - } - -private: - _Node* _M_insert_after(_Node_base* __pos, const value_type& __x) { - return (_Node*) (__slist_make_link(__pos, _M_create_node(__x))); - } - - _Node* _M_insert_after(_Node_base* __pos) { - return (_Node*) (__slist_make_link(__pos, _M_create_node())); - } - - void _M_insert_after_fill(_Node_base* __pos, - size_type __n, const value_type& __x) { - for (size_type __i = 0; __i < __n; ++__i) - __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, - _InIter __first, _InIter __last) { - typedef typename _Is_integer<_InIter>::_Integral _Integral; - _M_insert_after_range(__pos, __first, __last, _Integral()); - } - - template <class _Integer> - void _M_insert_after_range(_Node_base* __pos, _Integer __n, _Integer __x, - __true_type) { - _M_insert_after_fill(__pos, __n, __x); - } - - template <class _InIter> - void _M_insert_after_range(_Node_base* __pos, - _InIter __first, _InIter __last, - __false_type) { - while (__first != __last) { - __pos = __slist_make_link(__pos, _M_create_node(*__first)); - ++__first; - } - } - -#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) { - return iterator(_M_insert_after(__pos._M_node, __x)); - } - - iterator insert_after(iterator __pos) { - return insert_after(__pos, value_type()); - } - - void insert_after(iterator __pos, size_type __n, const value_type& __x) { - _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> - void insert_after(iterator __pos, _InIter __first, _InIter __last) { - _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(&_M_head, __pos._M_node), - __x)); - } - - iterator insert(iterator __pos) { - return iterator(_M_insert_after(__slist_previous(&_M_head, __pos._M_node), - value_type())); - } - - void insert(iterator __pos, size_type __n, const value_type& __x) { - _M_insert_after_fill(__slist_previous(&_M_head, __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> - void insert(iterator __pos, _InIter __first, _InIter __last) { - _M_insert_after_range(__slist_previous(&_M_head, __pos._M_node), - __first, __last); - } - -#else /* __STL_MEMBER_TEMPLATES */ - - void insert(iterator __pos, const_iterator __first, const_iterator __last) { - _M_insert_after_range(__slist_previous(&_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(&_M_head, __pos._M_node), - __first, __last); - } - -#endif /* __STL_MEMBER_TEMPLATES */ - - -public: - iterator erase_after(iterator __pos) { - return iterator((_Node*) _M_erase_after(__pos._M_node)); - } - iterator erase_after(iterator __before_first, iterator __last) { - return iterator((_Node*) _M_erase_after(__before_first._M_node, - __last._M_node)); - } - - iterator erase(iterator __pos) { - return (_Node*) _M_erase_after(__slist_previous(&_M_head, - __pos._M_node)); - } - iterator erase(iterator __first, iterator __last) { - return (_Node*) _M_erase_after( - __slist_previous(&_M_head, __first._M_node), __last._M_node); - } - - void resize(size_type new_size, const _Tp& __x); - void resize(size_type new_size) { resize(new_size, _Tp()); } - void clear() { _M_erase_after(&_M_head, 0); } - -public: - // Moves the range [__before_first + 1, __before_last + 1) to *this, - // inserting it immediately after __pos. This is constant time. - void splice_after(iterator __pos, - iterator __before_first, iterator __before_last) - { - if (__before_first != __before_last) - __slist_splice_after(__pos._M_node, __before_first._M_node, - __before_last._M_node); - } - - // Moves the element that follows __prev to *this, inserting it immediately - // after __pos. This is constant time. - void splice_after(iterator __pos, iterator __prev) - { - __slist_splice_after(__pos._M_node, - __prev._M_node, __prev._M_node->_M_next); - } - - - // Linear in distance(begin(), __pos), and linear in __x.size(). - void splice(iterator __pos, slist& __x) { - if (__x._M_head._M_next) - __slist_splice_after(__slist_previous(&_M_head, __pos._M_node), - &__x._M_head, __slist_previous(&__x._M_head, 0)); - } - - // Linear in distance(begin(), __pos), and in distance(__x.begin(), __i). - void splice(iterator __pos, slist& __x, iterator __i) { - __slist_splice_after(__slist_previous(&_M_head, __pos._M_node), - __slist_previous(&__x._M_head, __i._M_node), - __i._M_node); - } - - // Linear in distance(begin(), __pos), in distance(__x.begin(), __first), - // and in distance(__first, __last). - void splice(iterator __pos, slist& __x, iterator __first, iterator __last) - { - if (__first != __last) - __slist_splice_after(__slist_previous(&_M_head, __pos._M_node), - __slist_previous(&__x._M_head, __first._M_node), - __slist_previous(__first._M_node, __last._M_node)); - } - -public: - void reverse() { - if (_M_head._M_next) - _M_head._M_next = __slist_reverse(_M_head._M_next); - } - - void remove(const _Tp& __val); - void unique(); - void merge(slist& __x); - void sort(); - -#ifdef __STL_MEMBER_TEMPLATES - template <class _Predicate> - void remove_if(_Predicate __pred); - - template <class _BinaryPredicate> - void unique(_BinaryPredicate __pred); - - template <class _StrictWeakOrdering> - void merge(slist&, _StrictWeakOrdering); - - template <class _StrictWeakOrdering> - void sort(_StrictWeakOrdering __comp); -#endif /* __STL_MEMBER_TEMPLATES */ -}; - -template <class _Tp, class _Alloc> -slist<_Tp,_Alloc>& slist<_Tp,_Alloc>::operator=(const slist<_Tp,_Alloc>& __x) -{ - if (&__x != this) { - _Node_base* __p1 = &_M_head; - _Node* __n1 = (_Node*) _M_head._M_next; - const _Node* __n2 = (const _Node*) __x._M_head._M_next; - while (__n1 && __n2) { - __n1->_M_data = __n2->_M_data; - __p1 = __n1; - __n1 = (_Node*) __n1->_M_next; - __n2 = (const _Node*) __n2->_M_next; - } - if (__n2 == 0) - _M_erase_after(__p1, 0); - else - _M_insert_after_range(__p1, const_iterator((_Node*)__n2), - const_iterator(0)); - } - return *this; -} - -template <class _Tp, class _Alloc> -void slist<_Tp, _Alloc>::assign(size_type __n, const _Tp& __val) { - _Node_base* __prev = &_M_head; - _Node* __node = (_Node*) _M_head._M_next; - for ( ; __node != 0 && __n > 0 ; --__n) { - __node->_M_data = __val; - __prev = __node; - __node = (_Node*) __node->_M_next; - } - if (__n > 0) - _M_insert_after_fill(__prev, __n, __val); - else - _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, - __false_type) -{ - _Node_base* __prev = &_M_head; - _Node* __node = (_Node*) _M_head._M_next; - while (__node != 0 && __first != __last) { - __node->_M_data = *__first; - __prev = __node; - __node = (_Node*) __node->_M_next; - ++__first; - } - if (__first != __last) - _M_insert_after_range(__prev, __first, __last); - else - _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) -{ - typedef typename slist<_Tp,_Alloc>::_Node _Node; - _Node* __n1 = (_Node*) _SL1._M_head._M_next; - _Node* __n2 = (_Node*) _SL2._M_head._M_next; - while (__n1 && __n2 && __n1->_M_data == __n2->_M_data) { - __n1 = (_Node*) __n1->_M_next; - __n2 = (_Node*) __n2->_M_next; - } - return __n1 == 0 && __n2 == 0; -} - -template <class _Tp, class _Alloc> -inline bool operator<(const slist<_Tp,_Alloc>& _SL1, - const slist<_Tp,_Alloc>& _SL2) -{ - return lexicographical_compare(_SL1.begin(), _SL1.end(), - _SL2.begin(), _SL2.end()); -} - -#ifdef __STL_FUNCTION_TMPL_PARTIAL_ORDER - -template <class _Tp, class _Alloc> -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) -{ - _Node_base* __cur = &_M_head; - while (__cur->_M_next != 0 && __len > 0) { - --__len; - __cur = __cur->_M_next; - } - if (__cur->_M_next) - _M_erase_after(__cur, 0); - else - _M_insert_after_fill(__cur, __len, __x); -} - -template <class _Tp, class _Alloc> -void slist<_Tp,_Alloc>::remove(const _Tp& __val) -{ - _Node_base* __cur = &_M_head; - while (__cur && __cur->_M_next) { - if (((_Node*) __cur->_M_next)->_M_data == __val) - _M_erase_after(__cur); - else - __cur = __cur->_M_next; - } -} - -template <class _Tp, class _Alloc> -void slist<_Tp,_Alloc>::unique() -{ - _Node_base* __cur = _M_head._M_next; - if (__cur) { - while (__cur->_M_next) { - if (((_Node*)__cur)->_M_data == - ((_Node*)(__cur->_M_next))->_M_data) - _M_erase_after(__cur); - else - __cur = __cur->_M_next; - } - } -} - -template <class _Tp, class _Alloc> -void slist<_Tp,_Alloc>::merge(slist<_Tp,_Alloc>& __x) -{ - _Node_base* __n1 = &_M_head; - while (__n1->_M_next && __x._M_head._M_next) { - if (((_Node*) __x._M_head._M_next)->_M_data < - ((_Node*) __n1->_M_next)->_M_data) - __slist_splice_after(__n1, &__x._M_head, __x._M_head._M_next); - __n1 = __n1->_M_next; - } - if (__x._M_head._M_next) { - __n1->_M_next = __x._M_head._M_next; - __x._M_head._M_next = 0; - } -} - -template <class _Tp, class _Alloc> -void slist<_Tp,_Alloc>::sort() -{ - if (_M_head._M_next && _M_head._M_next->_M_next) { - slist __carry; - slist __counter[64]; - int __fill = 0; - while (!empty()) { - __slist_splice_after(&__carry._M_head, &_M_head, _M_head._M_next); - int __i = 0; - while (__i < __fill && !__counter[__i].empty()) { - __counter[__i].merge(__carry); - __carry.swap(__counter[__i]); - ++__i; - } - __carry.swap(__counter[__i]); - if (__i == __fill) - ++__fill; - } - - for (int __i = 1; __i < __fill; ++__i) - __counter[__i].merge(__counter[__i-1]); - this->swap(__counter[__fill-1]); - } -} - -#ifdef __STL_MEMBER_TEMPLATES - -template <class _Tp, class _Alloc> -template <class _Predicate> -void slist<_Tp,_Alloc>::remove_if(_Predicate __pred) -{ - _Node_base* __cur = &_M_head; - while (__cur->_M_next) { - if (__pred(((_Node*) __cur->_M_next)->_M_data)) - _M_erase_after(__cur); - else - __cur = __cur->_M_next; - } -} - -template <class _Tp, class _Alloc> template <class _BinaryPredicate> -void slist<_Tp,_Alloc>::unique(_BinaryPredicate __pred) -{ - _Node* __cur = (_Node*) _M_head._M_next; - if (__cur) { - while (__cur->_M_next) { - if (__pred(((_Node*)__cur)->_M_data, - ((_Node*)(__cur->_M_next))->_M_data)) - _M_erase_after(__cur); - else - __cur = (_Node*) __cur->_M_next; - } - } -} - -template <class _Tp, class _Alloc> template <class _StrictWeakOrdering> -void slist<_Tp,_Alloc>::merge(slist<_Tp,_Alloc>& __x, - _StrictWeakOrdering __comp) -{ - _Node_base* __n1 = &_M_head; - while (__n1->_M_next && __x._M_head._M_next) { - if (__comp(((_Node*) __x._M_head._M_next)->_M_data, - ((_Node*) __n1->_M_next)->_M_data)) - __slist_splice_after(__n1, &__x._M_head, __x._M_head._M_next); - __n1 = __n1->_M_next; - } - if (__x._M_head._M_next) { - __n1->_M_next = __x._M_head._M_next; - __x._M_head._M_next = 0; - } -} - -template <class _Tp, class _Alloc> template <class _StrictWeakOrdering> -void slist<_Tp,_Alloc>::sort(_StrictWeakOrdering __comp) -{ - if (_M_head._M_next && _M_head._M_next->_M_next) { - slist __carry; - slist __counter[64]; - int __fill = 0; - while (!empty()) { - __slist_splice_after(&__carry._M_head, &_M_head, _M_head._M_next); - int __i = 0; - while (__i < __fill && !__counter[__i].empty()) { - __counter[__i].merge(__carry, __comp); - __carry.swap(__counter[__i]); - ++__i; - } - __carry.swap(__counter[__i]); - if (__i == __fill) - ++__fill; - } - - for (int __i = 1; __i < __fill; ++__i) - __counter[__i].merge(__counter[__i-1], __comp); - this->swap(__counter[__fill-1]); - } -} - -#endif /* __STL_MEMBER_TEMPLATES */ - -#if defined(__sgi) && !defined(__GNUC__) && (_MIPS_SIM != _MIPS_SIM_ABI32) -#pragma reset woff 1174 -#pragma reset woff 1375 -#endif - -__STL_END_NAMESPACE - -#endif /* __SGI_STL_INTERNAL_SLIST_H */ - -// Local Variables: -// mode:C++ -// End: |