williamr@2: /* williamr@2: * williamr@2: * Copyright (c) 1996,1997 williamr@2: * Silicon Graphics Computer Systems, Inc. williamr@2: * williamr@2: * Copyright (c) 1999 williamr@2: * Boris Fomitchev williamr@2: * williamr@2: * This material is provided "as is", with absolutely no warranty expressed williamr@2: * or implied. Any use is at your own risk. williamr@2: * williamr@2: * Permission to use or copy this software for any purpose is hereby granted williamr@2: * without fee, provided the above notices are retained on all copies. williamr@2: * Permission to modify the code and to distribute modified code is granted, williamr@2: * provided the above notices are retained, and a notice that the code was williamr@2: * modified is included with the above copyright notice. williamr@2: * williamr@2: */ williamr@2: #ifndef _STLP_SLIST_C williamr@2: #define _STLP_SLIST_C williamr@2: williamr@2: #ifndef _STLP_INTERNAL_SLIST_H williamr@2: # include williamr@2: #endif williamr@2: williamr@2: # undef slist williamr@2: # define slist __WORKAROUND_DBG_RENAME(slist) williamr@2: # if defined (_STLP_NESTED_TYPE_PARAM_BUG) williamr@2: # define size_type size_t williamr@2: # endif williamr@2: williamr@2: _STLP_BEGIN_NAMESPACE williamr@2: williamr@2: template williamr@2: _Slist_node_base* williamr@2: _Slist_base<_Tp,_Alloc>::_M_erase_after(_Slist_node_base* __before_first, williamr@2: _Slist_node_base* __last_node) { williamr@2: _Slist_node<_Tp>* __cur = (_Slist_node<_Tp>*) (__before_first->_M_next); williamr@2: while (__cur != __last_node) { williamr@2: _Slist_node<_Tp>* __tmp = __cur; williamr@2: __cur = (_Slist_node<_Tp>*) __cur->_M_next; williamr@2: _STLP_STD::_Destroy(&__tmp->_M_data); williamr@2: _M_head.deallocate(__tmp,1); williamr@2: } williamr@2: __before_first->_M_next = __last_node; williamr@2: return __last_node; williamr@2: } williamr@2: williamr@2: template williamr@2: slist<_Tp,_Alloc>& slist<_Tp,_Alloc>::operator=(const slist<_Tp,_Alloc>& __x) williamr@2: { williamr@2: if (&__x != this) { williamr@2: _Node_base* __p1 = &this->_M_head._M_data; williamr@2: _Node* __n1 = (_Node*) this->_M_head._M_data._M_next; williamr@2: const _Node* __n2 = (const _Node*) __x._M_head._M_data._M_next; williamr@2: while (__n1 && __n2) { williamr@2: __n1->_M_data = __n2->_M_data; williamr@2: __p1 = __n1; williamr@2: __n1 = (_Node*) __n1->_M_next; williamr@2: __n2 = (const _Node*) __n2->_M_next; williamr@2: } williamr@2: if (__n2 == 0) williamr@2: this->_M_erase_after(__p1, 0); williamr@2: else williamr@2: _M_insert_after_range(__p1, const_iterator((_Node*)__n2), williamr@2: const_iterator(0)); williamr@2: } williamr@2: return *this; williamr@2: } williamr@2: williamr@2: template williamr@2: void slist<_Tp, _Alloc>::_M_fill_assign(size_type __n, const _Tp& __val) { williamr@2: _Node_base* __prev = &this->_M_head._M_data; williamr@2: _Node* __node = (_Node*) this->_M_head._M_data._M_next; williamr@2: for ( ; __node != 0 && __n > 0 ; --__n) { williamr@2: __node->_M_data = __val; williamr@2: __prev = __node; williamr@2: __node = (_Node*) __node->_M_next; williamr@2: } williamr@2: if (__n > 0) williamr@2: _M_insert_after_fill(__prev, __n, __val); williamr@2: else williamr@2: this->_M_erase_after(__prev, 0); williamr@2: } williamr@2: williamr@2: williamr@2: template williamr@2: void slist<_Tp,_Alloc>::resize(size_type __len, const _Tp& __x) williamr@2: { williamr@2: _Node_base* __cur = &this->_M_head._M_data; williamr@2: while (__cur->_M_next != 0 && __len > 0) { williamr@2: --__len; williamr@2: __cur = __cur->_M_next; williamr@2: } williamr@2: if (__cur->_M_next) williamr@2: this->_M_erase_after(__cur, 0); williamr@2: else williamr@2: _M_insert_after_fill(__cur, __len, __x); williamr@2: } williamr@2: williamr@2: template williamr@2: void slist<_Tp,_Alloc>::remove(const _Tp& __val) williamr@2: { williamr@2: _Node_base* __cur = &this->_M_head._M_data; williamr@2: while (__cur && __cur->_M_next) { williamr@2: if (((_Node*) __cur->_M_next)->_M_data == __val) williamr@2: this->_M_erase_after(__cur); williamr@2: else williamr@2: __cur = __cur->_M_next; williamr@2: } williamr@2: } williamr@2: williamr@2: template williamr@2: void slist<_Tp,_Alloc>::unique() williamr@2: { williamr@2: _Node_base* __cur = this->_M_head._M_data._M_next; williamr@2: if (__cur) { williamr@2: while (__cur->_M_next) { williamr@2: if (((_Node*)__cur)->_M_data == williamr@2: ((_Node*)(__cur->_M_next))->_M_data) williamr@2: this->_M_erase_after(__cur); williamr@2: else williamr@2: __cur = __cur->_M_next; williamr@2: } williamr@2: } williamr@2: } williamr@2: williamr@2: template williamr@2: void slist<_Tp,_Alloc>::merge(slist<_Tp,_Alloc>& __x) williamr@2: { williamr@2: _Node_base* __n1 = &this->_M_head._M_data; williamr@2: while (__n1->_M_next && __x._M_head._M_data._M_next) { williamr@2: if (((_Node*) __x._M_head._M_data._M_next)->_M_data < williamr@2: ((_Node*) __n1->_M_next)->_M_data) williamr@2: _Sl_global_inst::__splice_after(__n1, &__x._M_head._M_data, __x._M_head._M_data._M_next); williamr@2: __n1 = __n1->_M_next; williamr@2: } williamr@2: if (__x._M_head._M_data._M_next) { williamr@2: __n1->_M_next = __x._M_head._M_data._M_next; williamr@2: __x._M_head._M_data._M_next = 0; williamr@2: } williamr@2: } williamr@2: williamr@2: template williamr@2: void slist<_Tp,_Alloc>::sort() williamr@2: { williamr@2: if (this->_M_head._M_data._M_next && this->_M_head._M_data._M_next->_M_next) { williamr@2: _Self __carry; williamr@2: _Self __counter[64]; williamr@2: int __fill = 0; williamr@2: while (!empty()) { williamr@2: _Sl_global_inst::__splice_after(&__carry._M_head._M_data, &this->_M_head._M_data, this->_M_head._M_data._M_next); williamr@2: int __i = 0; williamr@2: while (__i < __fill && !__counter[__i].empty()) { williamr@2: __counter[__i].merge(__carry); williamr@2: __carry.swap(__counter[__i]); williamr@2: ++__i; williamr@2: } williamr@2: __carry.swap(__counter[__i]); williamr@2: if (__i == __fill) williamr@2: ++__fill; williamr@2: } williamr@2: williamr@2: for (int __i = 1; __i < __fill; ++__i) williamr@2: __counter[__i].merge(__counter[__i-1]); williamr@2: this->swap(__counter[__fill-1]); williamr@2: } williamr@2: } williamr@2: williamr@2: # undef slist williamr@2: # undef size_type williamr@2: williamr@2: _STLP_END_NAMESPACE williamr@2: williamr@2: #endif /* _STLP_SLIST_C */ williamr@2: williamr@2: // Local Variables: williamr@2: // mode:C++ williamr@2: // End: