177dc872c5c4ae67e051d1bf7edf96ce36c7b9be2David 'Digit' Turner/* 277dc872c5c4ae67e051d1bf7edf96ce36c7b9be2David 'Digit' Turner * 377dc872c5c4ae67e051d1bf7edf96ce36c7b9be2David 'Digit' Turner * 477dc872c5c4ae67e051d1bf7edf96ce36c7b9be2David 'Digit' Turner * Copyright (c) 1994 577dc872c5c4ae67e051d1bf7edf96ce36c7b9be2David 'Digit' Turner * Hewlett-Packard Company 677dc872c5c4ae67e051d1bf7edf96ce36c7b9be2David 'Digit' Turner * 777dc872c5c4ae67e051d1bf7edf96ce36c7b9be2David 'Digit' Turner * Copyright (c) 1996,1997 877dc872c5c4ae67e051d1bf7edf96ce36c7b9be2David 'Digit' Turner * Silicon Graphics Computer Systems, Inc. 977dc872c5c4ae67e051d1bf7edf96ce36c7b9be2David 'Digit' Turner * 1077dc872c5c4ae67e051d1bf7edf96ce36c7b9be2David 'Digit' Turner * Copyright (c) 1997 1177dc872c5c4ae67e051d1bf7edf96ce36c7b9be2David 'Digit' Turner * Moscow Center for SPARC Technology 1277dc872c5c4ae67e051d1bf7edf96ce36c7b9be2David 'Digit' Turner * 1377dc872c5c4ae67e051d1bf7edf96ce36c7b9be2David 'Digit' Turner * Copyright (c) 1999 1477dc872c5c4ae67e051d1bf7edf96ce36c7b9be2David 'Digit' Turner * Boris Fomitchev 1577dc872c5c4ae67e051d1bf7edf96ce36c7b9be2David 'Digit' Turner * 1677dc872c5c4ae67e051d1bf7edf96ce36c7b9be2David 'Digit' Turner * This material is provided "as is", with absolutely no warranty expressed 1777dc872c5c4ae67e051d1bf7edf96ce36c7b9be2David 'Digit' Turner * or implied. Any use is at your own risk. 1877dc872c5c4ae67e051d1bf7edf96ce36c7b9be2David 'Digit' Turner * 1977dc872c5c4ae67e051d1bf7edf96ce36c7b9be2David 'Digit' Turner * Permission to use or copy this software for any purpose is hereby granted 2077dc872c5c4ae67e051d1bf7edf96ce36c7b9be2David 'Digit' Turner * without fee, provided the above notices are retained on all copies. 2177dc872c5c4ae67e051d1bf7edf96ce36c7b9be2David 'Digit' Turner * Permission to modify the code and to distribute modified code is granted, 2277dc872c5c4ae67e051d1bf7edf96ce36c7b9be2David 'Digit' Turner * provided the above notices are retained, and a notice that the code was 2377dc872c5c4ae67e051d1bf7edf96ce36c7b9be2David 'Digit' Turner * modified is included with the above copyright notice. 2477dc872c5c4ae67e051d1bf7edf96ce36c7b9be2David 'Digit' Turner * 2577dc872c5c4ae67e051d1bf7edf96ce36c7b9be2David 'Digit' Turner */ 2677dc872c5c4ae67e051d1bf7edf96ce36c7b9be2David 'Digit' Turner#ifndef _STLP_LIST_C 2777dc872c5c4ae67e051d1bf7edf96ce36c7b9be2David 'Digit' Turner#define _STLP_LIST_C 2877dc872c5c4ae67e051d1bf7edf96ce36c7b9be2David 'Digit' Turner 2977dc872c5c4ae67e051d1bf7edf96ce36c7b9be2David 'Digit' Turner#ifndef _STLP_INTERNAL_LIST_H 3077dc872c5c4ae67e051d1bf7edf96ce36c7b9be2David 'Digit' Turner# include <stl/_list.h> 3177dc872c5c4ae67e051d1bf7edf96ce36c7b9be2David 'Digit' Turner#endif 3277dc872c5c4ae67e051d1bf7edf96ce36c7b9be2David 'Digit' Turner 3377dc872c5c4ae67e051d1bf7edf96ce36c7b9be2David 'Digit' Turner#ifndef _STLP_CARRAY_H 3477dc872c5c4ae67e051d1bf7edf96ce36c7b9be2David 'Digit' Turner# include <stl/_carray.h> 3577dc872c5c4ae67e051d1bf7edf96ce36c7b9be2David 'Digit' Turner#endif 3677dc872c5c4ae67e051d1bf7edf96ce36c7b9be2David 'Digit' Turner 3777dc872c5c4ae67e051d1bf7edf96ce36c7b9be2David 'Digit' Turner#ifndef _STLP_RANGE_ERRORS_H 3877dc872c5c4ae67e051d1bf7edf96ce36c7b9be2David 'Digit' Turner# include <stl/_range_errors.h> 3977dc872c5c4ae67e051d1bf7edf96ce36c7b9be2David 'Digit' Turner#endif 4077dc872c5c4ae67e051d1bf7edf96ce36c7b9be2David 'Digit' Turner 4177dc872c5c4ae67e051d1bf7edf96ce36c7b9be2David 'Digit' Turner_STLP_BEGIN_NAMESPACE 4277dc872c5c4ae67e051d1bf7edf96ce36c7b9be2David 'Digit' Turner 4377dc872c5c4ae67e051d1bf7edf96ce36c7b9be2David 'Digit' Turner_STLP_MOVE_TO_PRIV_NAMESPACE 4477dc872c5c4ae67e051d1bf7edf96ce36c7b9be2David 'Digit' Turner 4577dc872c5c4ae67e051d1bf7edf96ce36c7b9be2David 'Digit' Turner#if defined (_STLP_EXPOSE_GLOBALS_IMPLEMENTATION) 4677dc872c5c4ae67e051d1bf7edf96ce36c7b9be2David 'Digit' Turnertemplate <class _Dummy> 4777dc872c5c4ae67e051d1bf7edf96ce36c7b9be2David 'Digit' Turnervoid _STLP_CALL 4877dc872c5c4ae67e051d1bf7edf96ce36c7b9be2David 'Digit' Turner_List_global<_Dummy>::_Transfer(_List_node_base* __position, 4977dc872c5c4ae67e051d1bf7edf96ce36c7b9be2David 'Digit' Turner _List_node_base* __first, _List_node_base* __last) { 5077dc872c5c4ae67e051d1bf7edf96ce36c7b9be2David 'Digit' Turner if (__position != __last) { 5177dc872c5c4ae67e051d1bf7edf96ce36c7b9be2David 'Digit' Turner // Remove [first, last) from its old position. 5277dc872c5c4ae67e051d1bf7edf96ce36c7b9be2David 'Digit' Turner __last->_M_prev->_M_next = __position; 5377dc872c5c4ae67e051d1bf7edf96ce36c7b9be2David 'Digit' Turner __first->_M_prev->_M_next = __last; 5477dc872c5c4ae67e051d1bf7edf96ce36c7b9be2David 'Digit' Turner __position->_M_prev->_M_next = __first; 5577dc872c5c4ae67e051d1bf7edf96ce36c7b9be2David 'Digit' Turner 5677dc872c5c4ae67e051d1bf7edf96ce36c7b9be2David 'Digit' Turner // Splice [first, last) into its new position. 5777dc872c5c4ae67e051d1bf7edf96ce36c7b9be2David 'Digit' Turner _Node_base* __tmp = __position->_M_prev; 5877dc872c5c4ae67e051d1bf7edf96ce36c7b9be2David 'Digit' Turner __position->_M_prev = __last->_M_prev; 5977dc872c5c4ae67e051d1bf7edf96ce36c7b9be2David 'Digit' Turner __last->_M_prev = __first->_M_prev; 6077dc872c5c4ae67e051d1bf7edf96ce36c7b9be2David 'Digit' Turner __first->_M_prev = __tmp; 6177dc872c5c4ae67e051d1bf7edf96ce36c7b9be2David 'Digit' Turner } 6277dc872c5c4ae67e051d1bf7edf96ce36c7b9be2David 'Digit' Turner} 6377dc872c5c4ae67e051d1bf7edf96ce36c7b9be2David 'Digit' Turner#endif /* _STLP_EXPOSE_GLOBALS_IMPLEMENTATION */ 6477dc872c5c4ae67e051d1bf7edf96ce36c7b9be2David 'Digit' Turner 6577dc872c5c4ae67e051d1bf7edf96ce36c7b9be2David 'Digit' Turnertemplate <class _Tp, class _Alloc> 6677dc872c5c4ae67e051d1bf7edf96ce36c7b9be2David 'Digit' Turnervoid _List_base<_Tp,_Alloc>::clear() { 6777dc872c5c4ae67e051d1bf7edf96ce36c7b9be2David 'Digit' Turner _Node* __cur = __STATIC_CAST(_Node*, _M_node._M_data._M_next); 6877dc872c5c4ae67e051d1bf7edf96ce36c7b9be2David 'Digit' Turner while ( 6977dc872c5c4ae67e051d1bf7edf96ce36c7b9be2David 'Digit' Turner#if defined (__BORLANDC__) // runtime error 7077dc872c5c4ae67e051d1bf7edf96ce36c7b9be2David 'Digit' Turner __cur && 7177dc872c5c4ae67e051d1bf7edf96ce36c7b9be2David 'Digit' Turner#endif 7277dc872c5c4ae67e051d1bf7edf96ce36c7b9be2David 'Digit' Turner __cur != &(_M_node._M_data)) { 7377dc872c5c4ae67e051d1bf7edf96ce36c7b9be2David 'Digit' Turner _Node* __tmp = __cur; 7477dc872c5c4ae67e051d1bf7edf96ce36c7b9be2David 'Digit' Turner __cur = __STATIC_CAST(_Node*, __cur->_M_next); 7577dc872c5c4ae67e051d1bf7edf96ce36c7b9be2David 'Digit' Turner _STLP_STD::_Destroy(&__tmp->_M_data); 7677dc872c5c4ae67e051d1bf7edf96ce36c7b9be2David 'Digit' Turner this->_M_node.deallocate(__tmp, 1); 7777dc872c5c4ae67e051d1bf7edf96ce36c7b9be2David 'Digit' Turner } 7877dc872c5c4ae67e051d1bf7edf96ce36c7b9be2David 'Digit' Turner _M_node._M_data._M_next = &_M_node._M_data; 7977dc872c5c4ae67e051d1bf7edf96ce36c7b9be2David 'Digit' Turner _M_node._M_data._M_prev = &_M_node._M_data; 8077dc872c5c4ae67e051d1bf7edf96ce36c7b9be2David 'Digit' Turner} 8177dc872c5c4ae67e051d1bf7edf96ce36c7b9be2David 'Digit' Turner 8277dc872c5c4ae67e051d1bf7edf96ce36c7b9be2David 'Digit' Turner#if defined (_STLP_NESTED_TYPE_PARAM_BUG) 8377dc872c5c4ae67e051d1bf7edf96ce36c7b9be2David 'Digit' Turner# define size_type size_t 8477dc872c5c4ae67e051d1bf7edf96ce36c7b9be2David 'Digit' Turner#endif 8577dc872c5c4ae67e051d1bf7edf96ce36c7b9be2David 'Digit' Turner 8677dc872c5c4ae67e051d1bf7edf96ce36c7b9be2David 'Digit' Turner#if defined (_STLP_USE_PTR_SPECIALIZATIONS) 8777dc872c5c4ae67e051d1bf7edf96ce36c7b9be2David 'Digit' Turner# define list _STLP_PTR_IMPL_NAME(list) 8877dc872c5c4ae67e051d1bf7edf96ce36c7b9be2David 'Digit' Turner#elif defined (_STLP_DEBUG) 8977dc872c5c4ae67e051d1bf7edf96ce36c7b9be2David 'Digit' Turner# define list _STLP_NON_DBG_NAME(list) 9077dc872c5c4ae67e051d1bf7edf96ce36c7b9be2David 'Digit' Turner#else 9177dc872c5c4ae67e051d1bf7edf96ce36c7b9be2David 'Digit' Turner_STLP_MOVE_TO_STD_NAMESPACE 9277dc872c5c4ae67e051d1bf7edf96ce36c7b9be2David 'Digit' Turner#endif 9377dc872c5c4ae67e051d1bf7edf96ce36c7b9be2David 'Digit' Turner 9477dc872c5c4ae67e051d1bf7edf96ce36c7b9be2David 'Digit' Turnertemplate <class _Tp, class _Alloc> 9577dc872c5c4ae67e051d1bf7edf96ce36c7b9be2David 'Digit' Turnervoid list<_Tp, _Alloc>::resize(size_type __new_size, const _Tp& __x) { 9677dc872c5c4ae67e051d1bf7edf96ce36c7b9be2David 'Digit' Turner iterator __i = begin(); 9777dc872c5c4ae67e051d1bf7edf96ce36c7b9be2David 'Digit' Turner size_type __len = 0; 9877dc872c5c4ae67e051d1bf7edf96ce36c7b9be2David 'Digit' Turner for ( ; __i != end() && __len < __new_size; ++__i, ++__len); 9977dc872c5c4ae67e051d1bf7edf96ce36c7b9be2David 'Digit' Turner 10077dc872c5c4ae67e051d1bf7edf96ce36c7b9be2David 'Digit' Turner if (__len == __new_size) 10177dc872c5c4ae67e051d1bf7edf96ce36c7b9be2David 'Digit' Turner erase(__i, end()); 10277dc872c5c4ae67e051d1bf7edf96ce36c7b9be2David 'Digit' Turner else // __i == end() 10377dc872c5c4ae67e051d1bf7edf96ce36c7b9be2David 'Digit' Turner insert(end(), __new_size - __len, __x); 10477dc872c5c4ae67e051d1bf7edf96ce36c7b9be2David 'Digit' Turner} 10577dc872c5c4ae67e051d1bf7edf96ce36c7b9be2David 'Digit' Turner 10677dc872c5c4ae67e051d1bf7edf96ce36c7b9be2David 'Digit' Turnertemplate <class _Tp, class _Alloc> 10777dc872c5c4ae67e051d1bf7edf96ce36c7b9be2David 'Digit' Turnerlist<_Tp, _Alloc>& list<_Tp, _Alloc>::operator=(const list<_Tp, _Alloc>& __x) { 10877dc872c5c4ae67e051d1bf7edf96ce36c7b9be2David 'Digit' Turner if (this != &__x) { 10977dc872c5c4ae67e051d1bf7edf96ce36c7b9be2David 'Digit' Turner iterator __first1 = begin(); 11077dc872c5c4ae67e051d1bf7edf96ce36c7b9be2David 'Digit' Turner iterator __last1 = end(); 11177dc872c5c4ae67e051d1bf7edf96ce36c7b9be2David 'Digit' Turner const_iterator __first2 = __x.begin(); 11277dc872c5c4ae67e051d1bf7edf96ce36c7b9be2David 'Digit' Turner const_iterator __last2 = __x.end(); 11377dc872c5c4ae67e051d1bf7edf96ce36c7b9be2David 'Digit' Turner while (__first1 != __last1 && __first2 != __last2) 11477dc872c5c4ae67e051d1bf7edf96ce36c7b9be2David 'Digit' Turner *__first1++ = *__first2++; 11577dc872c5c4ae67e051d1bf7edf96ce36c7b9be2David 'Digit' Turner if (__first2 == __last2) 11677dc872c5c4ae67e051d1bf7edf96ce36c7b9be2David 'Digit' Turner erase(__first1, __last1); 11777dc872c5c4ae67e051d1bf7edf96ce36c7b9be2David 'Digit' Turner else 11877dc872c5c4ae67e051d1bf7edf96ce36c7b9be2David 'Digit' Turner insert(__last1, __first2, __last2); 11977dc872c5c4ae67e051d1bf7edf96ce36c7b9be2David 'Digit' Turner } 12077dc872c5c4ae67e051d1bf7edf96ce36c7b9be2David 'Digit' Turner return *this; 12177dc872c5c4ae67e051d1bf7edf96ce36c7b9be2David 'Digit' Turner} 12277dc872c5c4ae67e051d1bf7edf96ce36c7b9be2David 'Digit' Turner 12377dc872c5c4ae67e051d1bf7edf96ce36c7b9be2David 'Digit' Turnertemplate <class _Tp, class _Alloc> 12477dc872c5c4ae67e051d1bf7edf96ce36c7b9be2David 'Digit' Turnervoid list<_Tp, _Alloc>::_M_fill_assign(size_type __n, const _Tp& __val) { 12577dc872c5c4ae67e051d1bf7edf96ce36c7b9be2David 'Digit' Turner iterator __i = begin(); 12677dc872c5c4ae67e051d1bf7edf96ce36c7b9be2David 'Digit' Turner for ( ; __i != end() && __n > 0; ++__i, --__n) 12777dc872c5c4ae67e051d1bf7edf96ce36c7b9be2David 'Digit' Turner *__i = __val; 12877dc872c5c4ae67e051d1bf7edf96ce36c7b9be2David 'Digit' Turner if (__n > 0) 12977dc872c5c4ae67e051d1bf7edf96ce36c7b9be2David 'Digit' Turner insert(end(), __n, __val); 13077dc872c5c4ae67e051d1bf7edf96ce36c7b9be2David 'Digit' Turner else 13177dc872c5c4ae67e051d1bf7edf96ce36c7b9be2David 'Digit' Turner erase(__i, end()); 13277dc872c5c4ae67e051d1bf7edf96ce36c7b9be2David 'Digit' Turner} 13377dc872c5c4ae67e051d1bf7edf96ce36c7b9be2David 'Digit' Turner 13477dc872c5c4ae67e051d1bf7edf96ce36c7b9be2David 'Digit' Turner#if !defined (list) 13577dc872c5c4ae67e051d1bf7edf96ce36c7b9be2David 'Digit' Turner_STLP_MOVE_TO_PRIV_NAMESPACE 13677dc872c5c4ae67e051d1bf7edf96ce36c7b9be2David 'Digit' Turner#endif 13777dc872c5c4ae67e051d1bf7edf96ce36c7b9be2David 'Digit' Turner 13877dc872c5c4ae67e051d1bf7edf96ce36c7b9be2David 'Digit' Turnertemplate <class _Tp, class _Alloc, class _Predicate> 13977dc872c5c4ae67e051d1bf7edf96ce36c7b9be2David 'Digit' Turnervoid _S_remove_if(list<_Tp, _Alloc>& __that, _Predicate __pred) { 14077dc872c5c4ae67e051d1bf7edf96ce36c7b9be2David 'Digit' Turner typedef typename list<_Tp, _Alloc>::iterator _Literator; 14177dc872c5c4ae67e051d1bf7edf96ce36c7b9be2David 'Digit' Turner _Literator __first = __that.begin(); 14277dc872c5c4ae67e051d1bf7edf96ce36c7b9be2David 'Digit' Turner _Literator __last = __that.end(); 14377dc872c5c4ae67e051d1bf7edf96ce36c7b9be2David 'Digit' Turner while (__first != __last) { 14477dc872c5c4ae67e051d1bf7edf96ce36c7b9be2David 'Digit' Turner _Literator __next = __first; 14577dc872c5c4ae67e051d1bf7edf96ce36c7b9be2David 'Digit' Turner ++__next; 14677dc872c5c4ae67e051d1bf7edf96ce36c7b9be2David 'Digit' Turner if (__pred(*__first)) __that.erase(__first); 14777dc872c5c4ae67e051d1bf7edf96ce36c7b9be2David 'Digit' Turner __first = __next; 14877dc872c5c4ae67e051d1bf7edf96ce36c7b9be2David 'Digit' Turner } 14977dc872c5c4ae67e051d1bf7edf96ce36c7b9be2David 'Digit' Turner} 15077dc872c5c4ae67e051d1bf7edf96ce36c7b9be2David 'Digit' Turner 15177dc872c5c4ae67e051d1bf7edf96ce36c7b9be2David 'Digit' Turnertemplate <class _Tp, class _Alloc, class _BinaryPredicate> 15277dc872c5c4ae67e051d1bf7edf96ce36c7b9be2David 'Digit' Turnervoid _S_unique(list<_Tp, _Alloc>& __that, _BinaryPredicate __binary_pred) { 15377dc872c5c4ae67e051d1bf7edf96ce36c7b9be2David 'Digit' Turner typedef typename list<_Tp, _Alloc>::iterator _Literator; 15477dc872c5c4ae67e051d1bf7edf96ce36c7b9be2David 'Digit' Turner _Literator __first = __that.begin(); 15577dc872c5c4ae67e051d1bf7edf96ce36c7b9be2David 'Digit' Turner _Literator __last = __that.end(); 15677dc872c5c4ae67e051d1bf7edf96ce36c7b9be2David 'Digit' Turner if (__first == __last) return; 15777dc872c5c4ae67e051d1bf7edf96ce36c7b9be2David 'Digit' Turner _Literator __next = __first; 15877dc872c5c4ae67e051d1bf7edf96ce36c7b9be2David 'Digit' Turner while (++__next != __last) { 15977dc872c5c4ae67e051d1bf7edf96ce36c7b9be2David 'Digit' Turner if (__binary_pred(*__first, *__next)) 16077dc872c5c4ae67e051d1bf7edf96ce36c7b9be2David 'Digit' Turner __that.erase(__next); 16177dc872c5c4ae67e051d1bf7edf96ce36c7b9be2David 'Digit' Turner else 16277dc872c5c4ae67e051d1bf7edf96ce36c7b9be2David 'Digit' Turner __first = __next; 16377dc872c5c4ae67e051d1bf7edf96ce36c7b9be2David 'Digit' Turner __next = __first; 16477dc872c5c4ae67e051d1bf7edf96ce36c7b9be2David 'Digit' Turner } 16577dc872c5c4ae67e051d1bf7edf96ce36c7b9be2David 'Digit' Turner} 16677dc872c5c4ae67e051d1bf7edf96ce36c7b9be2David 'Digit' Turner 16777dc872c5c4ae67e051d1bf7edf96ce36c7b9be2David 'Digit' Turnertemplate <class _Tp, class _Alloc, class _StrictWeakOrdering> 16877dc872c5c4ae67e051d1bf7edf96ce36c7b9be2David 'Digit' Turnervoid _S_merge(list<_Tp, _Alloc>& __that, list<_Tp, _Alloc>& __x, 16977dc872c5c4ae67e051d1bf7edf96ce36c7b9be2David 'Digit' Turner _StrictWeakOrdering __comp) { 17077dc872c5c4ae67e051d1bf7edf96ce36c7b9be2David 'Digit' Turner typedef typename list<_Tp, _Alloc>::iterator _Literator; 17177dc872c5c4ae67e051d1bf7edf96ce36c7b9be2David 'Digit' Turner _Literator __first1 = __that.begin(); 17277dc872c5c4ae67e051d1bf7edf96ce36c7b9be2David 'Digit' Turner _Literator __last1 = __that.end(); 17377dc872c5c4ae67e051d1bf7edf96ce36c7b9be2David 'Digit' Turner _Literator __first2 = __x.begin(); 17477dc872c5c4ae67e051d1bf7edf96ce36c7b9be2David 'Digit' Turner _Literator __last2 = __x.end(); 17577dc872c5c4ae67e051d1bf7edf96ce36c7b9be2David 'Digit' Turner if (__that.get_allocator() == __x.get_allocator()) { 17677dc872c5c4ae67e051d1bf7edf96ce36c7b9be2David 'Digit' Turner while (__first1 != __last1 && __first2 != __last2) { 17777dc872c5c4ae67e051d1bf7edf96ce36c7b9be2David 'Digit' Turner if (__comp(*__first2, *__first1)) { 17877dc872c5c4ae67e051d1bf7edf96ce36c7b9be2David 'Digit' Turner _STLP_VERBOSE_ASSERT(!__comp(*__first1, *__first2), _StlMsg_INVALID_STRICT_WEAK_PREDICATE) 17977dc872c5c4ae67e051d1bf7edf96ce36c7b9be2David 'Digit' Turner _Literator __next = __first2; 18077dc872c5c4ae67e051d1bf7edf96ce36c7b9be2David 'Digit' Turner _List_global_inst::_Transfer(__first1._M_node, __first2._M_node, (++__next)._M_node); 18177dc872c5c4ae67e051d1bf7edf96ce36c7b9be2David 'Digit' Turner __first2 = __next; 18277dc872c5c4ae67e051d1bf7edf96ce36c7b9be2David 'Digit' Turner } 18377dc872c5c4ae67e051d1bf7edf96ce36c7b9be2David 'Digit' Turner else 18477dc872c5c4ae67e051d1bf7edf96ce36c7b9be2David 'Digit' Turner ++__first1; 18577dc872c5c4ae67e051d1bf7edf96ce36c7b9be2David 'Digit' Turner } 18677dc872c5c4ae67e051d1bf7edf96ce36c7b9be2David 'Digit' Turner if (__first2 != __last2) 18777dc872c5c4ae67e051d1bf7edf96ce36c7b9be2David 'Digit' Turner _List_global_inst::_Transfer(__last1._M_node, __first2._M_node, __last2._M_node); 18877dc872c5c4ae67e051d1bf7edf96ce36c7b9be2David 'Digit' Turner } 18977dc872c5c4ae67e051d1bf7edf96ce36c7b9be2David 'Digit' Turner else { 19077dc872c5c4ae67e051d1bf7edf96ce36c7b9be2David 'Digit' Turner while (__first1 != __last1 && __first2 != __last2) { 19177dc872c5c4ae67e051d1bf7edf96ce36c7b9be2David 'Digit' Turner if (__comp(*__first2, *__first1)) { 19277dc872c5c4ae67e051d1bf7edf96ce36c7b9be2David 'Digit' Turner _STLP_VERBOSE_ASSERT(!__comp(*__first1, *__first2), _StlMsg_INVALID_STRICT_WEAK_PREDICATE) 19377dc872c5c4ae67e051d1bf7edf96ce36c7b9be2David 'Digit' Turner __first1 = __that.insert(__first1, *__first2); 19477dc872c5c4ae67e051d1bf7edf96ce36c7b9be2David 'Digit' Turner } 19577dc872c5c4ae67e051d1bf7edf96ce36c7b9be2David 'Digit' Turner else 19677dc872c5c4ae67e051d1bf7edf96ce36c7b9be2David 'Digit' Turner ++__first1; 19777dc872c5c4ae67e051d1bf7edf96ce36c7b9be2David 'Digit' Turner } 19877dc872c5c4ae67e051d1bf7edf96ce36c7b9be2David 'Digit' Turner if (__first2 != __last2) { 19977dc872c5c4ae67e051d1bf7edf96ce36c7b9be2David 'Digit' Turner __that.insert(__first1, __first2, __last2); 20077dc872c5c4ae67e051d1bf7edf96ce36c7b9be2David 'Digit' Turner } 20177dc872c5c4ae67e051d1bf7edf96ce36c7b9be2David 'Digit' Turner __x.clear(); 20277dc872c5c4ae67e051d1bf7edf96ce36c7b9be2David 'Digit' Turner } 20377dc872c5c4ae67e051d1bf7edf96ce36c7b9be2David 'Digit' Turner} 20477dc872c5c4ae67e051d1bf7edf96ce36c7b9be2David 'Digit' Turner 20577dc872c5c4ae67e051d1bf7edf96ce36c7b9be2David 'Digit' Turnertemplate <class _Tp, class _Alloc, class _StrictWeakOrdering> 20677dc872c5c4ae67e051d1bf7edf96ce36c7b9be2David 'Digit' Turnervoid _S_sort(list<_Tp, _Alloc>& __that, _StrictWeakOrdering __comp) { 20777dc872c5c4ae67e051d1bf7edf96ce36c7b9be2David 'Digit' Turner // Do nothing if the list has length 0 or 1. 20877dc872c5c4ae67e051d1bf7edf96ce36c7b9be2David 'Digit' Turner if (__that._M_node._M_data._M_next == &__that._M_node._M_data || 20977dc872c5c4ae67e051d1bf7edf96ce36c7b9be2David 'Digit' Turner __that._M_node._M_data._M_next->_M_next == &__that._M_node._M_data) 21077dc872c5c4ae67e051d1bf7edf96ce36c7b9be2David 'Digit' Turner return; 21177dc872c5c4ae67e051d1bf7edf96ce36c7b9be2David 'Digit' Turner 21277dc872c5c4ae67e051d1bf7edf96ce36c7b9be2David 'Digit' Turner list<_Tp, _Alloc> __carry(__that.get_allocator()); 21377dc872c5c4ae67e051d1bf7edf96ce36c7b9be2David 'Digit' Turner const int NB = 64; 21477dc872c5c4ae67e051d1bf7edf96ce36c7b9be2David 'Digit' Turner _STLP_PRIV _CArray<list<_Tp, _Alloc>, NB> __counter(__carry); 21577dc872c5c4ae67e051d1bf7edf96ce36c7b9be2David 'Digit' Turner int __fill = 0; 21677dc872c5c4ae67e051d1bf7edf96ce36c7b9be2David 'Digit' Turner while (!__that.empty()) { 21777dc872c5c4ae67e051d1bf7edf96ce36c7b9be2David 'Digit' Turner __carry.splice(__carry.begin(), __that, __that.begin()); 21877dc872c5c4ae67e051d1bf7edf96ce36c7b9be2David 'Digit' Turner int __i = 0; 21977dc872c5c4ae67e051d1bf7edf96ce36c7b9be2David 'Digit' Turner while (__i < __fill && !__counter[__i].empty()) { 22077dc872c5c4ae67e051d1bf7edf96ce36c7b9be2David 'Digit' Turner _S_merge(__counter[__i], __carry, __comp); 22177dc872c5c4ae67e051d1bf7edf96ce36c7b9be2David 'Digit' Turner __carry.swap(__counter[__i++]); 22277dc872c5c4ae67e051d1bf7edf96ce36c7b9be2David 'Digit' Turner } 22377dc872c5c4ae67e051d1bf7edf96ce36c7b9be2David 'Digit' Turner __carry.swap(__counter[__i]); 22477dc872c5c4ae67e051d1bf7edf96ce36c7b9be2David 'Digit' Turner if (__i == __fill) { 22577dc872c5c4ae67e051d1bf7edf96ce36c7b9be2David 'Digit' Turner ++__fill; 22677dc872c5c4ae67e051d1bf7edf96ce36c7b9be2David 'Digit' Turner if (__fill >= NB) { 22777dc872c5c4ae67e051d1bf7edf96ce36c7b9be2David 'Digit' Turner //Looks like the list has too many elements to be sorted with this algorithm: 22877dc872c5c4ae67e051d1bf7edf96ce36c7b9be2David 'Digit' Turner __stl_throw_overflow_error("list::sort"); 22977dc872c5c4ae67e051d1bf7edf96ce36c7b9be2David 'Digit' Turner } 23077dc872c5c4ae67e051d1bf7edf96ce36c7b9be2David 'Digit' Turner } 23177dc872c5c4ae67e051d1bf7edf96ce36c7b9be2David 'Digit' Turner } 23277dc872c5c4ae67e051d1bf7edf96ce36c7b9be2David 'Digit' Turner 23377dc872c5c4ae67e051d1bf7edf96ce36c7b9be2David 'Digit' Turner for (int __i = 1; __i < __fill; ++__i) 23477dc872c5c4ae67e051d1bf7edf96ce36c7b9be2David 'Digit' Turner _S_merge(__counter[__i], __counter[__i - 1], __comp); 23577dc872c5c4ae67e051d1bf7edf96ce36c7b9be2David 'Digit' Turner __that.swap(__counter[__fill - 1]); 23677dc872c5c4ae67e051d1bf7edf96ce36c7b9be2David 'Digit' Turner} 23777dc872c5c4ae67e051d1bf7edf96ce36c7b9be2David 'Digit' Turner 23877dc872c5c4ae67e051d1bf7edf96ce36c7b9be2David 'Digit' Turner#if defined (list) 23977dc872c5c4ae67e051d1bf7edf96ce36c7b9be2David 'Digit' Turner# undef list 24077dc872c5c4ae67e051d1bf7edf96ce36c7b9be2David 'Digit' Turner#endif 24177dc872c5c4ae67e051d1bf7edf96ce36c7b9be2David 'Digit' Turner 24277dc872c5c4ae67e051d1bf7edf96ce36c7b9be2David 'Digit' Turner_STLP_MOVE_TO_STD_NAMESPACE 24377dc872c5c4ae67e051d1bf7edf96ce36c7b9be2David 'Digit' Turner 24477dc872c5c4ae67e051d1bf7edf96ce36c7b9be2David 'Digit' Turner_STLP_END_NAMESPACE 24577dc872c5c4ae67e051d1bf7edf96ce36c7b9be2David 'Digit' Turner 24677dc872c5c4ae67e051d1bf7edf96ce36c7b9be2David 'Digit' Turner#endif /* _STLP_LIST_C */ 24777dc872c5c4ae67e051d1bf7edf96ce36c7b9be2David 'Digit' Turner 24877dc872c5c4ae67e051d1bf7edf96ce36c7b9be2David 'Digit' Turner// Local Variables: 24977dc872c5c4ae67e051d1bf7edf96ce36c7b9be2David 'Digit' Turner// mode:C++ 25077dc872c5c4ae67e051d1bf7edf96ce36c7b9be2David 'Digit' Turner// End: 251