williamr@2: /* williamr@2: * williamr@2: * williamr@2: * Copyright (c) 1994 williamr@2: * Hewlett-Packard Company williamr@2: * williamr@2: * Copyright (c) 1996,1997 williamr@2: * Silicon Graphics Computer Systems, Inc. williamr@2: * williamr@2: * Copyright (c) 1997 williamr@2: * Moscow Center for SPARC Technology williamr@2: * williamr@4: * 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@4: * 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_LIST_C williamr@2: #define _STLP_LIST_C williamr@2: williamr@2: #ifndef _STLP_INTERNAL_LIST_H williamr@4: # include williamr@2: #endif williamr@2: williamr@4: #ifndef _STLP_CARRAY_H williamr@4: # include williamr@2: #endif williamr@2: williamr@4: #ifndef _STLP_RANGE_ERRORS_H williamr@4: # include williamr@4: #endif williamr@2: williamr@2: _STLP_BEGIN_NAMESPACE williamr@2: williamr@4: _STLP_MOVE_TO_PRIV_NAMESPACE williamr@2: williamr@4: #if defined (_STLP_EXPOSE_GLOBALS_IMPLEMENTATION) williamr@2: template williamr@2: void _STLP_CALL williamr@4: _List_global<_Dummy>::_Transfer(_List_node_base* __position, williamr@4: _List_node_base* __first, _List_node_base* __last) { williamr@2: if (__position != __last) { williamr@2: // Remove [first, last) from its old position. williamr@4: __last->_M_prev->_M_next = __position; williamr@4: __first->_M_prev->_M_next = __last; williamr@4: __position->_M_prev->_M_next = __first; williamr@4: williamr@2: // Splice [first, last) into its new position. williamr@4: _Node_base* __tmp = __position->_M_prev; williamr@2: __position->_M_prev = __last->_M_prev; williamr@4: __last->_M_prev = __first->_M_prev; williamr@2: __first->_M_prev = __tmp; williamr@2: } williamr@2: } williamr@4: #endif /* _STLP_EXPOSE_GLOBALS_IMPLEMENTATION */ williamr@2: williamr@2: template williamr@4: void _List_base<_Tp,_Alloc>::clear() { williamr@4: _Node* __cur = __STATIC_CAST(_Node*, _M_node._M_data._M_next); williamr@4: while (__cur != &(_M_node._M_data)) { williamr@4: _Node* __tmp = __cur; williamr@4: __cur = __STATIC_CAST(_Node*, __cur->_M_next); williamr@2: _STLP_STD::_Destroy(&__tmp->_M_data); williamr@2: this->_M_node.deallocate(__tmp, 1); williamr@2: } williamr@4: _M_node._M_data._M_next = &_M_node._M_data; williamr@4: _M_node._M_data._M_prev = &_M_node._M_data; williamr@2: } williamr@2: williamr@4: #if defined (_STLP_NESTED_TYPE_PARAM_BUG) williamr@4: # define size_type size_t williamr@4: #endif williamr@4: williamr@4: #if defined (_STLP_USE_PTR_SPECIALIZATIONS) williamr@4: # define list _STLP_PTR_IMPL_NAME(list) williamr@4: #elif defined (_STLP_DEBUG) williamr@4: # define list _STLP_NON_DBG_NAME(list) williamr@4: #else williamr@4: _STLP_MOVE_TO_STD_NAMESPACE williamr@4: #endif williamr@2: williamr@2: template williamr@4: void list<_Tp, _Alloc>::resize(size_type __new_size, const _Tp& __x) { williamr@2: iterator __i = begin(); williamr@2: size_type __len = 0; williamr@2: for ( ; __i != end() && __len < __new_size; ++__i, ++__len); williamr@2: williamr@2: if (__len == __new_size) williamr@2: erase(__i, end()); williamr@4: else // __i == end() williamr@2: insert(end(), __new_size - __len, __x); williamr@2: } williamr@2: williamr@2: template williamr@4: list<_Tp, _Alloc>& list<_Tp, _Alloc>::operator=(const list<_Tp, _Alloc>& __x) { williamr@2: if (this != &__x) { williamr@2: iterator __first1 = begin(); williamr@2: iterator __last1 = end(); williamr@2: const_iterator __first2 = __x.begin(); williamr@2: const_iterator __last2 = __x.end(); williamr@4: while (__first1 != __last1 && __first2 != __last2) williamr@2: *__first1++ = *__first2++; williamr@2: if (__first2 == __last2) williamr@2: erase(__first1, __last1); williamr@2: else williamr@2: insert(__last1, __first2, __last2); williamr@2: } williamr@2: return *this; williamr@2: } williamr@2: williamr@2: template williamr@2: void list<_Tp, _Alloc>::_M_fill_assign(size_type __n, const _Tp& __val) { williamr@2: iterator __i = begin(); williamr@2: for ( ; __i != end() && __n > 0; ++__i, --__n) williamr@2: *__i = __val; williamr@2: if (__n > 0) williamr@2: insert(end(), __n, __val); williamr@2: else williamr@2: erase(__i, end()); williamr@2: } williamr@2: williamr@4: #if !defined (list) williamr@4: _STLP_MOVE_TO_PRIV_NAMESPACE williamr@4: #endif williamr@4: williamr@4: template williamr@2: void _S_remove_if(list<_Tp, _Alloc>& __that, _Predicate __pred) { williamr@4: typedef typename list<_Tp, _Alloc>::iterator _Literator; williamr@4: _Literator __first = __that.begin(); williamr@4: _Literator __last = __that.end(); williamr@2: while (__first != __last) { williamr@4: _Literator __next = __first; williamr@2: ++__next; williamr@2: if (__pred(*__first)) __that.erase(__first); williamr@2: __first = __next; williamr@2: } williamr@2: } williamr@2: williamr@2: template williamr@2: void _S_unique(list<_Tp, _Alloc>& __that, _BinaryPredicate __binary_pred) { williamr@4: typedef typename list<_Tp, _Alloc>::iterator _Literator; williamr@4: _Literator __first = __that.begin(); williamr@4: _Literator __last = __that.end(); williamr@2: if (__first == __last) return; williamr@4: _Literator __next = __first; williamr@2: while (++__next != __last) { williamr@2: if (__binary_pred(*__first, *__next)) williamr@2: __that.erase(__next); williamr@2: else williamr@2: __first = __next; williamr@2: __next = __first; williamr@2: } williamr@2: } williamr@2: williamr@2: template williamr@2: void _S_merge(list<_Tp, _Alloc>& __that, list<_Tp, _Alloc>& __x, williamr@4: _StrictWeakOrdering __comp) { williamr@2: typedef typename list<_Tp, _Alloc>::iterator _Literator; williamr@2: _Literator __first1 = __that.begin(); williamr@2: _Literator __last1 = __that.end(); williamr@2: _Literator __first2 = __x.begin(); williamr@2: _Literator __last2 = __x.end(); williamr@4: if (__that.get_allocator() == __x.get_allocator()) { williamr@4: while (__first1 != __last1 && __first2 != __last2) { williamr@4: if (__comp(*__first2, *__first1)) { williamr@4: _STLP_VERBOSE_ASSERT(!__comp(*__first1, *__first2), _StlMsg_INVALID_STRICT_WEAK_PREDICATE) williamr@4: _Literator __next = __first2; williamr@4: _List_global_inst::_Transfer(__first1._M_node, __first2._M_node, (++__next)._M_node); williamr@4: __first2 = __next; williamr@4: } williamr@4: else williamr@4: ++__first1; williamr@2: } williamr@4: if (__first2 != __last2) williamr@4: _List_global_inst::_Transfer(__last1._M_node, __first2._M_node, __last2._M_node); williamr@4: } williamr@4: else { williamr@4: while (__first1 != __last1 && __first2 != __last2) { williamr@4: if (__comp(*__first2, *__first1)) { williamr@4: _STLP_VERBOSE_ASSERT(!__comp(*__first1, *__first2), _StlMsg_INVALID_STRICT_WEAK_PREDICATE) williamr@4: __first1 = __that.insert(__first1, *__first2); williamr@4: } williamr@4: else williamr@4: ++__first1; williamr@4: } williamr@4: if (__first2 != __last2) { williamr@4: __that.insert(__first1, __first2, __last2); williamr@4: } williamr@4: __x.clear(); williamr@4: } williamr@2: } williamr@2: williamr@2: template williamr@2: void _S_sort(list<_Tp, _Alloc>& __that, _StrictWeakOrdering __comp) { williamr@2: // Do nothing if the list has length 0 or 1. williamr@4: if (__that._M_node._M_data._M_next == &__that._M_node._M_data || williamr@4: __that._M_node._M_data._M_next->_M_next == &__that._M_node._M_data) williamr@4: return; williamr@2: williamr@4: list<_Tp, _Alloc> __carry(__that.get_allocator()); williamr@4: const int NB = 64; williamr@4: _STLP_PRIV _CArray, NB> __counter(__carry); williamr@4: int __fill = 0; williamr@4: while (!__that.empty()) { williamr@4: __carry.splice(__carry.begin(), __that, __that.begin()); williamr@4: int __i = 0; williamr@4: while (__i < __fill && !__counter[__i].empty()) { williamr@4: _S_merge(__counter[__i], __carry, __comp); williamr@4: __carry.swap(__counter[__i++]); williamr@2: } williamr@4: __carry.swap(__counter[__i]); williamr@4: if (__i == __fill) { williamr@4: ++__fill; williamr@4: if (__fill >= NB) { williamr@4: //Looks like the list has too many elements to be sorted with this algorithm: williamr@4: __stl_throw_overflow_error("list::sort"); williamr@4: } williamr@4: } williamr@4: } williamr@2: williamr@4: for (int __i = 1; __i < __fill; ++__i) williamr@4: _S_merge(__counter[__i], __counter[__i - 1], __comp); williamr@4: __that.swap(__counter[__fill - 1]); williamr@2: } williamr@2: williamr@4: #if defined (list) williamr@4: # undef list williamr@4: #endif williamr@4: williamr@4: _STLP_MOVE_TO_STD_NAMESPACE williamr@2: williamr@2: _STLP_END_NAMESPACE williamr@2: williamr@2: #endif /* _STLP_LIST_C */ williamr@2: williamr@2: // Local Variables: williamr@2: // mode:C++ williamr@2: // End: