diff -r e1b950c65cb4 -r 837f303aceeb epoc32/include/stdapis/stlportv5/stl/_deque.c --- a/epoc32/include/stdapis/stlportv5/stl/_deque.c Wed Mar 31 12:27:01 2010 +0100 +++ b/epoc32/include/stdapis/stlportv5/stl/_deque.c Wed Mar 31 12:33:34 2010 +0100 @@ -10,13 +10,13 @@ * Copyright (c) 1997 * Moscow Center for SPARC Technology * - * Copyright (c) 1999 + * Copyright (c) 1999 * Boris Fomitchev * * This material is provided "as is", with absolutely no warranty expressed * or implied. Any use is at your own risk. * - * Permission to use or copy this software for any purpose is hereby granted + * Permission to use or copy this software for any purpose is hereby granted * without fee, provided the above notices are retained on all copies. * Permission to modify the code and to distribute modified code is granted, * provided the above notices are retained, and a notice that the code was @@ -24,91 +24,87 @@ * */ #ifndef _STLP_DEQUE_C -# define _STLP_DEQUE_C +#define _STLP_DEQUE_C -# ifndef _STLP_INTERNAL_DEQUE_H +#ifndef _STLP_INTERNAL_DEQUE_H # include -# endif +#endif _STLP_BEGIN_NAMESPACE +_STLP_MOVE_TO_PRIV_NAMESPACE + // Non-inline member functions from _Deque_base. template _Deque_base<_Tp,_Alloc >::~_Deque_base() { if (_M_map._M_data) { - if (_M_start._M_node) { - _M_destroy_nodes(_M_start._M_node, this->_M_finish._M_node + 1); - } + _M_destroy_nodes(_M_start._M_node, this->_M_finish._M_node + 1); _M_map.deallocate(_M_map._M_data, _M_map_size._M_data); } } template -void -_Deque_base<_Tp,_Alloc>::_M_initialize_map(size_t __num_elements) -{ - size_t __num_nodes = - __num_elements / this->buffer_size() + 1 ; +void _Deque_base<_Tp,_Alloc>::_M_initialize_map(size_t __num_elements) { + size_t __num_nodes = __num_elements / this->buffer_size() + 1 ; _M_map_size._M_data = (max)((size_t) _S_initial_map_size, __num_nodes + 2); _M_map._M_data = _M_map.allocate(_M_map_size._M_data); _Tp** __nstart = _M_map._M_data + (_M_map_size._M_data - __num_nodes) / 2; _Tp** __nfinish = __nstart + __num_nodes; - + _STLP_TRY { _M_create_nodes(__nstart, __nfinish); } - _STLP_UNWIND((_M_map.deallocate(_M_map._M_data, _M_map_size._M_data), - _M_map._M_data = 0, _M_map_size._M_data = 0)); + _STLP_UNWIND((_M_map.deallocate(_M_map._M_data, _M_map_size._M_data), + _M_map._M_data = 0, _M_map_size._M_data = 0)) _M_start._M_set_node(__nstart); this->_M_finish._M_set_node(__nfinish - 1); _M_start._M_cur = _M_start._M_first; - this->_M_finish._M_cur = this->_M_finish._M_first + - __num_elements % this->buffer_size(); + this->_M_finish._M_cur = this->_M_finish._M_first + __num_elements % this->buffer_size(); } template -void -_Deque_base<_Tp,_Alloc>::_M_create_nodes(_Tp** __nstart, - _Tp** __nfinish) -{ - _Tp** _STLP_LEAVE_VOLATILE __cur = 0; +void _Deque_base<_Tp,_Alloc>::_M_create_nodes(_Tp** __nstart, + _Tp** __nfinish) { + _Tp** __cur = __nstart; _STLP_TRY { - for (__cur = __nstart; __cur < __nfinish; ++__cur) + for (; __cur < __nfinish; ++__cur) *__cur = _M_map_size.allocate(this->buffer_size()); } - _STLP_UNWIND(_M_destroy_nodes(__nstart, __cur)); + _STLP_UNWIND(_M_destroy_nodes(__nstart, __cur)) } template -void -_Deque_base<_Tp,_Alloc>::_M_destroy_nodes(_Tp** __nstart, - _Tp** __nfinish) -{ +void _Deque_base<_Tp,_Alloc>::_M_destroy_nodes(_Tp** __nstart, + _Tp** __nfinish) { for (_Tp** __n = __nstart; __n < __nfinish; ++__n) _M_map_size.deallocate(*__n, this->buffer_size()); } +#if defined (_STLP_USE_PTR_SPECIALIZATIONS) +# define deque _STLP_PTR_IMPL_NAME(deque) +#elif defined (_STLP_DEBUG) +# define deque _STLP_NON_DBG_NAME(deque) +#else +_STLP_MOVE_TO_STD_NAMESPACE +#endif - -// Non-inline member functions - -# if defined ( _STLP_NESTED_TYPE_PARAM_BUG ) -// qualified references -# define __iterator__ _Deque_iterator<_Tp, _Nonconst_traits<_Tp> > -# define const_iterator _Deque_iterator<_Tp, _Const_traits<_Tp> > -# define iterator __iterator__ -# define size_type size_t -# define value_type _Tp -# else -# define __iterator__ _STLP_TYPENAME_ON_RETURN_TYPE __deque__<_Tp, _Alloc>::iterator -# endif +#if defined (_STLP_NESTED_TYPE_PARAM_BUG) +// qualified references +# define __iterator__ _Deque_iterator<_Tp, _Nonconst_traits<_Tp> > +# define const_iterator _Deque_iterator<_Tp, _Const_traits<_Tp> > +# define iterator __iterator__ +# define size_type size_t +# define value_type _Tp +#else +# define __iterator__ _STLP_TYPENAME_ON_RETURN_TYPE deque<_Tp, _Alloc>::iterator +#endif template -__deque__<_Tp, _Alloc >& -__deque__<_Tp, _Alloc >::operator= (const __deque__<_Tp, _Alloc >& __x) { +deque<_Tp, _Alloc >& +deque<_Tp, _Alloc >::operator= (const deque<_Tp, _Alloc >& __x) { const size_type __len = size(); if (&__x != this) { if (__len >= __x.size()) @@ -120,19 +116,17 @@ } } return *this; -} +} template -void -__deque__<_Tp, _Alloc >::_M_fill_insert(iterator __pos, - size_type __n, const value_type& __x) -{ +void deque<_Tp, _Alloc >::_M_fill_insert(iterator __pos, + size_type __n, const value_type& __x) { if (__pos._M_cur == this->_M_start._M_cur) { iterator __new_start = _M_reserve_elements_at_front(__n); _STLP_TRY { uninitialized_fill(__new_start, this->_M_start, __x); } - _STLP_UNWIND(this->_M_destroy_nodes(__new_start._M_node, this->_M_start._M_node)); + _STLP_UNWIND(this->_M_destroy_nodes(__new_start._M_node, this->_M_start._M_node)) this->_M_start = __new_start; } else if (__pos._M_cur == this->_M_finish._M_cur) { @@ -140,115 +134,221 @@ _STLP_TRY { uninitialized_fill(this->_M_finish, __new_finish, __x); } - _STLP_UNWIND(this->_M_destroy_nodes(this->_M_finish._M_node+1, __new_finish._M_node+1)); + _STLP_UNWIND(this->_M_destroy_nodes(this->_M_finish._M_node+1, __new_finish._M_node+1)) this->_M_finish = __new_finish; } - else - _M_insert_aux(__pos, __n, __x); + else + _M_fill_insert_aux(__pos, __n, __x, _Movable()); } -#ifndef _STLP_MEMBER_TEMPLATES +#if !defined (_STLP_MEMBER_TEMPLATES) template -void __deque__<_Tp, _Alloc>::insert(iterator __pos, - const value_type* __first, - const value_type* __last) { +void deque<_Tp, _Alloc>::insert(iterator __pos, + const value_type* __first, const value_type* __last) { size_type __n = __last - __first; if (__pos._M_cur == this->_M_start._M_cur) { iterator __new_start = _M_reserve_elements_at_front(__n); _STLP_TRY { - uninitialized_copy(__first, __last, __new_start); + _STLP_PRIV __ucopy(__first, __last, __new_start); } - _STLP_UNWIND(this->_M_destroy_nodes(__new_start._M_node, this->_M_start._M_node)); + _STLP_UNWIND(this->_M_destroy_nodes(__new_start._M_node, this->_M_start._M_node)) this->_M_start = __new_start; } else if (__pos._M_cur == this->_M_finish._M_cur) { iterator __new_finish = _M_reserve_elements_at_back(__n); _STLP_TRY { - uninitialized_copy(__first, __last, this->_M_finish); + _STLP_PRIV __ucopy(__first, __last, this->_M_finish); } - _STLP_UNWIND(this->_M_destroy_nodes(this->_M_finish._M_node + 1, - __new_finish._M_node + 1)); + _STLP_UNWIND(this->_M_destroy_nodes(this->_M_finish._M_node + 1, + __new_finish._M_node + 1)) this->_M_finish = __new_finish; } else - _M_insert_aux(__pos, __first, __last, __n); + _M_insert_range_aux(__pos, __first, __last, __n, _Movable()); } template -void __deque__<_Tp,_Alloc>::insert(iterator __pos, - const_iterator __first, - const_iterator __last) -{ +void deque<_Tp,_Alloc>::insert(iterator __pos, + const_iterator __first, const_iterator __last) { size_type __n = __last - __first; if (__pos._M_cur == this->_M_start._M_cur) { iterator __new_start = _M_reserve_elements_at_front(__n); _STLP_TRY { - uninitialized_copy(__first, __last, __new_start); + _STLP_PRIV __ucopy(__first, __last, __new_start); } - _STLP_UNWIND(this->_M_destroy_nodes(__new_start._M_node, this->_M_start._M_node)); + _STLP_UNWIND(this->_M_destroy_nodes(__new_start._M_node, this->_M_start._M_node)) this->_M_start = __new_start; } else if (__pos._M_cur == this->_M_finish._M_cur) { iterator __new_finish = _M_reserve_elements_at_back(__n); _STLP_TRY { - uninitialized_copy(__first, __last, this->_M_finish); + _STLP_PRIV __ucopy(__first, __last, this->_M_finish); } - _STLP_UNWIND(this->_M_destroy_nodes(this->_M_finish._M_node + 1,__new_finish._M_node + 1)); + _STLP_UNWIND(this->_M_destroy_nodes(this->_M_finish._M_node + 1, + __new_finish._M_node + 1)) this->_M_finish = __new_finish; } else - _M_insert_aux(__pos, __first, __last, __n); + _M_insert_range_aux(__pos, __first, __last, __n, _Movable()); } #endif /* _STLP_MEMBER_TEMPLATES */ template -__iterator__ -__deque__<_Tp,_Alloc>::erase(iterator __first, iterator __last) -{ - if (__first == this->_M_start && __last == this->_M_finish) { - clear(); - return this->_M_finish; +__iterator__ deque<_Tp,_Alloc>::_M_erase(iterator __pos, + const __true_type& /*_Movable*/) { + difference_type __index = __pos - this->_M_start; + if (size_type(__index) < this->size() >> 1) { + //We move the start of the deque one position to the right + //starting from the rightmost element to move. + iterator __src = __pos, __dst = __pos; + _STLP_STD::_Destroy(&(*__dst)); + if (__src != this->_M_start) { + for (--__src; __dst != this->_M_start; --__src, --__dst) { + _STLP_STD::_Move_Construct(&(*__dst), *__src); + _STLP_STD::_Destroy_Moved(&(*__src)); + } + } + _M_pop_front_aux(); } else { - difference_type __n = __last - __first; - difference_type __elems_before = __first - this->_M_start; - if (__elems_before < difference_type(this->size() - __n) / 2) { - copy_backward(this->_M_start, __first, __last); - iterator __new_start = this->_M_start + __n; - _STLP_STD::_Destroy(this->_M_start, __new_start); - this->_M_destroy_nodes(this->_M_start._M_node, __new_start._M_node); - this->_M_start = __new_start; + iterator __src = __pos, __dst = __pos; + _STLP_STD::_Destroy(&(*__dst)); + for (++__src; __src != this->_M_finish; ++__src, ++__dst) { + _STLP_STD::_Move_Construct(&(*__dst), *__src); + _STLP_STD::_Destroy_Moved(&(*__src)); + } + //Duplication of the pop_back code without the destroy which has already been done: + if (this->_M_finish._M_cur != this->_M_finish._M_first) { + --this->_M_finish._M_cur; } else { - copy(__last, this->_M_finish, __first); - iterator __new_finish = this->_M_finish - __n; - _STLP_STD::_Destroy(__new_finish, this->_M_finish); - this->_M_destroy_nodes(__new_finish._M_node + 1, this->_M_finish._M_node + 1); - this->_M_finish = __new_finish; + _M_pop_back_aux(); } - return this->_M_start + __elems_before; } + return this->_M_start + __index; } template -void __deque__<_Tp,_Alloc>::clear() -{ +__iterator__ deque<_Tp,_Alloc>::_M_erase(iterator __pos, + const __false_type& /*_Movable*/) { + iterator __next = __pos; + ++__next; + difference_type __index = __pos - this->_M_start; + if (size_type(__index) < this->size() >> 1) { + copy_backward(this->_M_start, __pos, __next); + pop_front(); + } + else { + copy(__next, this->_M_finish, __pos); + pop_back(); + } + return this->_M_start + __index; +} + +template +__iterator__ deque<_Tp,_Alloc>::_M_erase(iterator __first, iterator __last, + const __true_type& /*_Movable*/) { + difference_type __n = __last - __first; + difference_type __elems_before = __first - this->_M_start; + if (__elems_before <= difference_type(this->size() - __n) / 2) { + iterator __src = __first, __dst = __last; + if (__src != this->_M_start) { + for (--__src, --__dst; (__src >= this->_M_start) && (__dst >= __first); --__src, --__dst) { + _STLP_STD::_Destroy(&(*__dst)); + _STLP_STD::_Move_Construct(&(*__dst), *__src); + } + if (__dst >= __first) { + //There are more elements to erase than elements to move + _STLP_STD::_Destroy_Range(__first, ++__dst); + _STLP_STD::_Destroy_Moved_Range(this->_M_start, __first); + } + else { + //There are more elements to move than elements to erase + for (; __src >= this->_M_start; --__src, --__dst) { + _STLP_STD::_Destroy_Moved(&(*__dst)); + _STLP_STD::_Move_Construct(&(*__dst), *__src); + } + _STLP_STD::_Destroy_Moved_Range(this->_M_start, ++__dst); + } + } + else { + _STLP_STD::_Destroy_Range(this->_M_start, __last); + } + iterator __new_start = this->_M_start + __n; + this->_M_destroy_nodes(this->_M_start._M_node, __new_start._M_node); + this->_M_start = __new_start; + } + else { + if (__last != this->_M_finish) { + iterator __src = __last, __dst = __first; + for (; (__src != this->_M_finish) && (__dst != __last); ++__src, ++__dst) { + _STLP_STD::_Destroy(&(*__dst)); + _STLP_STD::_Move_Construct(&(*__dst), *__src); + } + if (__dst != __last) { + //There are more elements to erase than elements to move + _STLP_STD::_Destroy_Range(__dst, __last); + _STLP_STD::_Destroy_Moved_Range(__last, this->_M_finish); + } + else { + //There are more elements to move than elements to erase + for (; __src != this->_M_finish; ++__src, ++__dst) { + _STLP_STD::_Destroy_Moved(&(*__dst)); + _STLP_STD::_Move_Construct(&(*__dst), *__src); + } + _STLP_STD::_Destroy_Moved_Range(__dst, this->_M_finish); + } + } + else { + _STLP_STD::_Destroy_Range(__first, this->_M_finish); + } + iterator __new_finish = this->_M_finish - __n; + this->_M_destroy_nodes(__new_finish._M_node + 1, this->_M_finish._M_node + 1); + this->_M_finish = __new_finish; + } + return this->_M_start + __elems_before; +} + +template +__iterator__ deque<_Tp,_Alloc>::_M_erase(iterator __first, iterator __last, + const __false_type& /*_Movable*/) { + difference_type __n = __last - __first; + difference_type __elems_before = __first - this->_M_start; + if (__elems_before <= difference_type(this->size() - __n) / 2) { + copy_backward(this->_M_start, __first, __last); + iterator __new_start = this->_M_start + __n; + _STLP_STD::_Destroy_Range(this->_M_start, __new_start); + this->_M_destroy_nodes(this->_M_start._M_node, __new_start._M_node); + this->_M_start = __new_start; + } + else { + copy(__last, this->_M_finish, __first); + iterator __new_finish = this->_M_finish - __n; + _STLP_STD::_Destroy_Range(__new_finish, this->_M_finish); + this->_M_destroy_nodes(__new_finish._M_node + 1, this->_M_finish._M_node + 1); + this->_M_finish = __new_finish; + } + return this->_M_start + __elems_before; +} + +template +void deque<_Tp,_Alloc>::clear() { for (_Map_pointer __node = this->_M_start._M_node + 1; __node < this->_M_finish._M_node; ++__node) { - _STLP_STD::_Destroy(*__node, *__node + this->buffer_size()); + _STLP_STD::_Destroy_Range(*__node, *__node + this->buffer_size()); this->_M_map_size.deallocate(*__node, this->buffer_size()); } if (this->_M_start._M_node != this->_M_finish._M_node) { - _STLP_STD::_Destroy(this->_M_start._M_cur, this->_M_start._M_last); - _STLP_STD::_Destroy(this->_M_finish._M_first, this->_M_finish._M_cur); + _STLP_STD::_Destroy_Range(this->_M_start._M_cur, this->_M_start._M_last); + _STLP_STD::_Destroy_Range(this->_M_finish._M_first, this->_M_finish._M_cur); this->_M_map_size.deallocate(this->_M_finish._M_first, this->buffer_size()); } else - _STLP_STD::_Destroy(this->_M_start._M_cur, this->_M_finish._M_cur); + _STLP_STD::_Destroy_Range(this->_M_start._M_cur, this->_M_finish._M_cur); this->_M_finish = this->_M_start; } @@ -256,375 +356,398 @@ // Precondition: this->_M_start and this->_M_finish have already been initialized, // but none of the deque's elements have yet been constructed. template -void -__deque__<_Tp,_Alloc>::_M_fill_initialize(const value_type& __val) { - _STLP_LEAVE_VOLATILE _Map_pointer __cur = 0; +void deque<_Tp,_Alloc>::_M_fill_initialize(const value_type& __val, + const __false_type& /*_TrivialInit*/) { + _Map_pointer __cur = this->_M_start._M_node; _STLP_TRY { - for (__cur = this->_M_start._M_node; __cur < this->_M_finish._M_node; ++__cur) + for (; __cur < this->_M_finish._M_node; ++__cur) uninitialized_fill(*__cur, *__cur + this->buffer_size(), __val); uninitialized_fill(this->_M_finish._M_first, this->_M_finish._M_cur, __val); } - _STLP_UNWIND(_STLP_STD::_Destroy(this->_M_start, iterator(*__cur, __cur))); + _STLP_UNWIND(_STLP_STD::_Destroy_Range(this->_M_start, iterator(*__cur, __cur))) } // Called only if this->_M_finish._M_cur == this->_M_finish._M_last - 1. template -void -__deque__<_Tp,_Alloc>::_M_push_back_aux_v(const value_type& __t) -{ - value_type __t_copy = __t; - _STLP_PUSH_CLEANUP_ITEM(value_type, &__t_copy); +void deque<_Tp,_Alloc>::_M_push_back_aux_v(const value_type& __t) { _M_reserve_map_at_back(); *(this->_M_finish._M_node + 1) = this->_M_map_size.allocate(this->buffer_size()); _STLP_TRY { - _Construct(this->_M_finish._M_cur, __t_copy); + _Copy_Construct(this->_M_finish._M_cur, __t); this->_M_finish._M_set_node(this->_M_finish._M_node + 1); this->_M_finish._M_cur = this->_M_finish._M_first; } - _STLP_UNWIND(this->_M_map_size.deallocate(*(this->_M_finish._M_node + 1), - this->buffer_size())); -#ifdef _STLP_USE_TRAP_LEAVE - CleanupStack::Pop(); -#endif + _STLP_UNWIND(this->_M_map_size.deallocate(*(this->_M_finish._M_node + 1), + this->buffer_size())) } -# ifndef _STLP_NO_ANACHRONISMS +#if defined(_STLP_DONT_SUP_DFLT_PARAM) && !defined(_STLP_NO_ANACHRONISMS) // Called only if this->_M_finish._M_cur == this->_M_finish._M_last - 1. template -void -__deque__<_Tp,_Alloc>::_M_push_back_aux() -{ +void deque<_Tp,_Alloc>::_M_push_back_aux() { _M_reserve_map_at_back(); *(this->_M_finish._M_node + 1) = this->_M_map_size.allocate(this->buffer_size()); _STLP_TRY { - _Construct(this->_M_finish._M_cur); + _STLP_STD::_Construct(this->_M_finish._M_cur); this->_M_finish._M_set_node(this->_M_finish._M_node + 1); this->_M_finish._M_cur = this->_M_finish._M_first; } - _STLP_UNWIND(this->_M_map_size.deallocate(*(this->_M_finish._M_node + 1), - this->buffer_size())); + _STLP_UNWIND(this->_M_map_size.deallocate(*(this->_M_finish._M_node + 1), + this->buffer_size())) } -# endif +#endif /*_STLP_DONT_SUP_DFLT_PARAM && !_STLP_NO_ANACHRONISMS*/ // Called only if this->_M_start._M_cur == this->_M_start._M_first. template -void -__deque__<_Tp,_Alloc>::_M_push_front_aux_v(const value_type& __t) -{ - value_type __t_copy = __t; - _STLP_PUSH_CLEANUP_ITEM(value_type, &__t_copy); +void deque<_Tp,_Alloc>::_M_push_front_aux_v(const value_type& __t) { _M_reserve_map_at_front(); *(this->_M_start._M_node - 1) = this->_M_map_size.allocate(this->buffer_size()); _STLP_TRY { this->_M_start._M_set_node(this->_M_start._M_node - 1); this->_M_start._M_cur = this->_M_start._M_last - 1; - _Construct(this->_M_start._M_cur, __t_copy); + _Copy_Construct(this->_M_start._M_cur, __t); } - _STLP_UNWIND((++this->_M_start, - this->_M_map_size.deallocate(*(this->_M_start._M_node - 1), this->buffer_size()))); -#ifdef _STLP_USE_TRAP_LEAVE - CleanupStack::Pop(); -#endif -} + _STLP_UNWIND((++this->_M_start, + this->_M_map_size.deallocate(*(this->_M_start._M_node - 1), this->buffer_size()))) +} -# ifndef _STLP_NO_ANACHRONISMS +#if defined (_STLP_DONT_SUP_DFLT_PARAM) && !defined (_STLP_NO_ANACHRONISMS) // Called only if this->_M_start._M_cur == this->_M_start._M_first. template -void -__deque__<_Tp,_Alloc>::_M_push_front_aux() -{ +void deque<_Tp,_Alloc>::_M_push_front_aux() { _M_reserve_map_at_front(); *(this->_M_start._M_node - 1) = this->_M_map_size.allocate(this->buffer_size()); _STLP_TRY { this->_M_start._M_set_node(this->_M_start._M_node - 1); this->_M_start._M_cur = this->_M_start._M_last - 1; - _Construct(this->_M_start._M_cur); + _STLP_STD::_Construct(this->_M_start._M_cur); } - _STLP_UNWIND((++this->_M_start, this->_M_map_size.deallocate(*(this->_M_start._M_node - 1), - this->buffer_size() ))); -} -# endif + _STLP_UNWIND((++this->_M_start, this->_M_map_size.deallocate(*(this->_M_start._M_node - 1), + this->buffer_size()))) +} +#endif /*_STLP_DONT_SUP_DFLT_PARAM && !_STLP_NO_ANACHRONISMS*/ // Called only if this->_M_finish._M_cur == this->_M_finish._M_first. template -void -__deque__<_Tp,_Alloc>::_M_pop_back_aux() -{ +void deque<_Tp,_Alloc>::_M_pop_back_aux() { this->_M_map_size.deallocate(this->_M_finish._M_first, this->buffer_size()); this->_M_finish._M_set_node(this->_M_finish._M_node - 1); this->_M_finish._M_cur = this->_M_finish._M_last - 1; - _STLP_STD::_Destroy(this->_M_finish._M_cur); } -// Called only if this->_M_start._M_cur == this->_M_start._M_last - 1. Note that -// if the deque has at least one element (a precondition for this member -// function), and if this->_M_start._M_cur == this->_M_start._M_last, then the deque +// Note that if the deque has at least one element (a precondition for this member +// function), and if this->_M_start._M_cur == this->_M_start._M_last, then the deque // must have at least two nodes. template -void -__deque__<_Tp,_Alloc>::_M_pop_front_aux() -{ - _STLP_STD::_Destroy(this->_M_start._M_cur); - this->_M_map_size.deallocate(this->_M_start._M_first, this->buffer_size()); - this->_M_start._M_set_node(this->_M_start._M_node + 1); - this->_M_start._M_cur = this->_M_start._M_first; -} - - +void deque<_Tp,_Alloc>::_M_pop_front_aux() { + if (this->_M_start._M_cur != this->_M_start._M_last - 1) + ++this->_M_start._M_cur; + else { + this->_M_map_size.deallocate(this->_M_start._M_first, this->buffer_size()); + this->_M_start._M_set_node(this->_M_start._M_node + 1); + this->_M_start._M_cur = this->_M_start._M_first; + } +} template -__iterator__ -__deque__<_Tp,_Alloc>::_M_insert_aux_prepare(iterator __pos) { - difference_type __index = __pos - this->_M_start; - if (__index < difference_type(size() / 2)) { - push_front(front()); - iterator __front1 = this->_M_start; - ++__front1; - iterator __front2 = __front1; - ++__front2; - __pos = this->_M_start + __index; - iterator __pos1 = __pos; - ++__pos1; - copy(__front2, __pos1, __front1); +__iterator__ deque<_Tp,_Alloc>::_M_fill_insert_aux(iterator __pos, size_type __n, + const value_type& __x, + const __true_type& /*_Movable*/) { + const difference_type __elems_before = __pos - this->_M_start; + size_type __length = this->size(); + value_type __x_copy = __x; + if (__elems_before <= difference_type(__length / 2)) { + iterator __new_start = _M_reserve_elements_at_front(__n); + __pos = this->_M_start + __elems_before; + _STLP_TRY { + iterator __dst = __new_start; + iterator __src = this->_M_start; + for (; __src != __pos; ++__dst, ++__src) { + _STLP_STD::_Move_Construct(&(*__dst), *__src); + _STLP_STD::_Destroy_Moved(&(*__src)); + } + this->_M_start = __new_start; + uninitialized_fill(__dst, __src, __x_copy); + __pos = __dst; + } + _STLP_UNWIND(this->_M_destroy_nodes(__new_start._M_node, this->_M_start._M_node)) } else { - push_back(back()); - iterator __back1 = this->_M_finish; - --__back1; - iterator __back2 = __back1; - --__back2; - __pos = this->_M_start + __index; - copy_backward(__pos, __back2, __back1); + iterator __new_finish = _M_reserve_elements_at_back(__n); + const difference_type __elems_after = difference_type(__length) - __elems_before; + __pos = this->_M_finish - __elems_after; + _STLP_TRY { + iterator __dst = __new_finish; + iterator __src = this->_M_finish; + for (--__src, --__dst; __src >= __pos; --__src, --__dst) { + _STLP_STD::_Move_Construct(&(*__dst), *__src); + _STLP_STD::_Destroy_Moved(&(*__src)); + } + this->_M_finish = __new_finish; + uninitialized_fill(__pos, __pos + __n, __x_copy); + } + _STLP_UNWIND(this->_M_destroy_nodes(this->_M_finish._M_node + 1, __new_finish._M_node + 1)) } return __pos; } template -__iterator__ -__deque__<_Tp,_Alloc>::_M_insert_aux(iterator __pos, - const value_type& __x) { +__iterator__ deque<_Tp,_Alloc>::_M_fill_insert_aux(iterator __pos, size_type __n, + const value_type& __x, + const __false_type& /*_Movable*/) { + const difference_type __elems_before = __pos - this->_M_start; + size_type __length = this->size(); value_type __x_copy = __x; - _STLP_PUSH_CLEANUP_ITEM(value_type, &__x_copy); - _STLP_MPWFIX_TRY //*TY 06/01/2000 - mpw forget to call dtor on __x_copy without this try block - __pos = _M_insert_aux_prepare(__pos); - *__pos = __x_copy; -#ifdef _STLP_USE_TRAP_LEAVE - CleanupStack::Pop(); -#endif + if (__elems_before <= difference_type(__length / 2)) { + iterator __new_start = _M_reserve_elements_at_front(__n); + iterator __old_start = this->_M_start; + __pos = this->_M_start + __elems_before; + _STLP_TRY { + if (__elems_before >= difference_type(__n)) { + iterator __start_n = this->_M_start + difference_type(__n); + _STLP_PRIV __ucopy(this->_M_start, __start_n, __new_start); + this->_M_start = __new_start; + copy(__start_n, __pos, __old_start); + fill(__pos - difference_type(__n), __pos, __x_copy); + __pos -= difference_type(__n); + } + else { + _STLP_PRIV __uninitialized_copy_fill(this->_M_start, __pos, __new_start, + this->_M_start, __x_copy); + this->_M_start = __new_start; + fill(__old_start, __pos, __x_copy); + } + } + _STLP_UNWIND(this->_M_destroy_nodes(__new_start._M_node, this->_M_start._M_node)) + } + else { + iterator __new_finish = _M_reserve_elements_at_back(__n); + iterator __old_finish = this->_M_finish; + const difference_type __elems_after = + difference_type(__length) - __elems_before; + __pos = this->_M_finish - __elems_after; + _STLP_TRY { + if (__elems_after > difference_type(__n)) { + iterator __finish_n = this->_M_finish - difference_type(__n); + _STLP_PRIV __ucopy(__finish_n, this->_M_finish, this->_M_finish); + this->_M_finish = __new_finish; + copy_backward(__pos, __finish_n, __old_finish); + fill(__pos, __pos + difference_type(__n), __x_copy); + } + else { + _STLP_PRIV __uninitialized_fill_copy(this->_M_finish, __pos + difference_type(__n), + __x_copy, __pos, this->_M_finish); + this->_M_finish = __new_finish; + fill(__pos, __old_finish, __x_copy); + } + } + _STLP_UNWIND(this->_M_destroy_nodes(this->_M_finish._M_node + 1, __new_finish._M_node + 1)) + } return __pos; - _STLP_MPWFIX_CATCH //*TY 06/01/2000 - +} + +#if !defined (_STLP_MEMBER_TEMPLATES) +template +void deque<_Tp,_Alloc>::_M_insert_range_aux(iterator __pos, + const value_type* __first, const value_type* __last, + size_type __n, const __true_type& /*_Movable*/) { + const difference_type __elems_before = __pos - this->_M_start; + size_type __length = size(); + if (__elems_before <= difference_type(__length / 2)) { + iterator __new_start = _M_reserve_elements_at_front(__n); + __pos = this->_M_start + __elems_before; + _STLP_TRY { + iterator __dst = __new_start; + iterator __src = this->_M_start; + for (; __src != __pos; ++__dst, ++__src) { + _STLP_STD::_Move_Construct(&(*__dst), *__src); + _STLP_STD::_Destroy_Moved(&(*__src)); + } + this->_M_start = __new_start; + _STLP_PRIV __ucopy(__first, __last, __dst); + } + _STLP_UNWIND(this->_M_destroy_nodes(__new_start._M_node, this->_M_start._M_node)) + } + else { + iterator __new_finish = _M_reserve_elements_at_back(__n); + const difference_type __elems_after = difference_type(__length) - __elems_before; + __pos = this->_M_finish - __elems_after; + _STLP_TRY { + iterator __dst = __new_finish; + iterator __src = this->_M_finish; + for (--__src, --__dst; __src >= __pos; --__src, --__dst) { + _STLP_STD::_Move_Construct(&(*__dst), *__src); + _STLP_STD::_Destroy_Moved(&(*__src)); + } + this->_M_finish = __new_finish; + _STLP_PRIV __ucopy(__first, __last, __pos); + } + _STLP_UNWIND(this->_M_destroy_nodes(this->_M_finish._M_node + 1, __new_finish._M_node + 1)) + } } template -__iterator__ -__deque__<_Tp,_Alloc>::_M_insert_aux(iterator __pos) -{ - __pos = _M_insert_aux_prepare(__pos); - *__pos = value_type(); - return __pos; +void deque<_Tp,_Alloc>::_M_insert_range_aux(iterator __pos, + const value_type* __first, const value_type* __last, + size_type __n, const __false_type& /*_Movable*/) { + const difference_type __elems_before = __pos - this->_M_start; + size_type __length = size(); + if (__elems_before <= difference_type(__length / 2)) { + iterator __new_start = _M_reserve_elements_at_front(__n); + iterator __old_start = this->_M_start; + __pos = this->_M_start + __elems_before; + _STLP_TRY { + if (__elems_before >= difference_type(__n)) { + iterator __start_n = this->_M_start + difference_type(__n); + _STLP_PRIV __ucopy(this->_M_start, __start_n, __new_start); + this->_M_start = __new_start; + copy(__start_n, __pos, __old_start); + copy(__first, __last, __pos - difference_type(__n)); + } + else { + const value_type* __mid = __first + (difference_type(__n) - __elems_before); + __uninitialized_copy_copy(this->_M_start, __pos, __first, __mid, __new_start); + this->_M_start = __new_start; + copy(__mid, __last, __old_start); + } + } + _STLP_UNWIND(this->_M_destroy_nodes(__new_start._M_node, this->_M_start._M_node)) + } + else { + iterator __new_finish = _M_reserve_elements_at_back(__n); + iterator __old_finish = this->_M_finish; + const difference_type __elems_after = + difference_type(__length) - __elems_before; + __pos = this->_M_finish - __elems_after; + _STLP_TRY { + + if (__elems_after > difference_type(__n)) { + iterator __finish_n = this->_M_finish - difference_type(__n); + _STLP_PRIV __ucopy(__finish_n, this->_M_finish, this->_M_finish); + this->_M_finish = __new_finish; + copy_backward(__pos, __finish_n, __old_finish); + copy(__first, __last, __pos); + } + else { + const value_type* __mid = __first + __elems_after; + __uninitialized_copy_copy(__mid, __last, __pos, this->_M_finish, this->_M_finish); + this->_M_finish = __new_finish; + copy(__first, __mid, __pos); + } + } + _STLP_UNWIND(this->_M_destroy_nodes(this->_M_finish._M_node + 1, __new_finish._M_node + 1)) + } } template -void -__deque__<_Tp,_Alloc>::_M_insert_aux(iterator __pos, - size_type __n, - const value_type& __x) -{ +void deque<_Tp,_Alloc>::_M_insert_range_aux(iterator __pos, + const_iterator __first, const_iterator __last, + size_type __n, const __true_type& /*_Movable*/) { const difference_type __elems_before = __pos - this->_M_start; - size_type __length = this->size(); - value_type __x_copy = __x; - _STLP_PUSH_CLEANUP_ITEM(value_type, &__x_copy); + size_type __length = size(); + if (__elems_before <= difference_type(__length / 2)) { + iterator __new_start = _M_reserve_elements_at_front(__n); + __pos = this->_M_start + __elems_before; + _STLP_TRY { + iterator __dst = __new_start; + iterator __src = this->_M_start; + for (; __src != __pos; ++__dst, ++__src) { + _STLP_STD::_Move_Construct(&(*__dst), *__src); + _STLP_STD::_Destroy_Moved(&(*__src)); + } + this->_M_start = __new_start; + _STLP_PRIV __ucopy(__first, __last, __dst); + } + _STLP_UNWIND(this->_M_destroy_nodes(__new_start._M_node, this->_M_start._M_node)) + } + else { + iterator __new_finish = _M_reserve_elements_at_back(__n); + const difference_type __elems_after = difference_type(__length) - __elems_before; + __pos = this->_M_finish - __elems_after; + _STLP_TRY { + iterator __dst = __new_finish; + iterator __src = this->_M_finish; + for (--__src, --__dst; __src >= __pos; --__src, --__dst) { + _STLP_STD::_Move_Construct(&(*__dst), *__src); + _STLP_STD::_Destroy_Moved(&(*__src)); + } + this->_M_finish = __new_finish; + _STLP_PRIV __ucopy(__first, __last, __pos); + } + _STLP_UNWIND(this->_M_destroy_nodes(this->_M_finish._M_node + 1, __new_finish._M_node + 1)) + } +} +template +void deque<_Tp,_Alloc>::_M_insert_range_aux(iterator __pos, + const_iterator __first, const_iterator __last, + size_type __n, const __false_type& /*_Movable*/) { + const difference_type __elems_before = __pos - this->_M_start; + size_type __length = size(); if (__elems_before < difference_type(__length / 2)) { iterator __new_start = _M_reserve_elements_at_front(__n); iterator __old_start = this->_M_start; __pos = this->_M_start + __elems_before; _STLP_TRY { if (__elems_before >= difference_type(__n)) { - iterator __start_n = this->_M_start + difference_type(__n); - uninitialized_copy(this->_M_start, __start_n, __new_start); - this->_M_start = __new_start; - copy(__start_n, __pos, __old_start); - fill(__pos - difference_type(__n), __pos, __x_copy); - } - else { - __uninitialized_copy_fill(this->_M_start, __pos, __new_start, - this->_M_start, __x_copy); - this->_M_start = __new_start; - fill(__old_start, __pos, __x_copy); - } - } - _STLP_UNWIND(this->_M_destroy_nodes(__new_start._M_node, this->_M_start._M_node)); - } - else { - iterator __new_finish = _M_reserve_elements_at_back(__n); - iterator __old_finish = this->_M_finish; - const difference_type __elems_after = - difference_type(__length) - __elems_before; - __pos = this->_M_finish - __elems_after; - _STLP_TRY { - if (__elems_after > difference_type(__n)) { - iterator __finish_n = this->_M_finish - difference_type(__n); - uninitialized_copy(__finish_n, this->_M_finish, this->_M_finish); - this->_M_finish = __new_finish; - copy_backward(__pos, __finish_n, __old_finish); - fill(__pos, __pos + difference_type(__n), __x_copy); - } - else { - __uninitialized_fill_copy(this->_M_finish, __pos + difference_type(__n), - __x_copy, __pos, this->_M_finish); - this->_M_finish = __new_finish; - fill(__pos, __old_finish, __x_copy); - } - } - _STLP_UNWIND(this->_M_destroy_nodes(this->_M_finish._M_node + 1, __new_finish._M_node + 1)); - } -#ifdef _STLP_USE_TRAP_LEAVE - CleanupStack::Pop(); -#endif -} - -#ifndef _STLP_MEMBER_TEMPLATES -template -void -__deque__<_Tp,_Alloc>::_M_insert_aux(iterator __pos, - const value_type* __first, - const value_type* __last, - size_type __n) -{ - - const difference_type __elemsbefore = __pos - this->_M_start; - size_type __length = size(); - if (__elemsbefore < difference_type(__length / 2)) { - iterator __new_start = _M_reserve_elements_at_front(__n); - iterator __old_start = this->_M_start; - __pos = this->_M_start + __elemsbefore; - _STLP_TRY { - if (__elemsbefore >= difference_type(__n)) { - iterator __start_n = this->_M_start + difference_type(__n); - uninitialized_copy(this->_M_start, __start_n, __new_start); + iterator __start_n = this->_M_start + __n; + _STLP_PRIV __ucopy(this->_M_start, __start_n, __new_start); this->_M_start = __new_start; copy(__start_n, __pos, __old_start); copy(__first, __last, __pos - difference_type(__n)); } else { - const value_type* __mid = - __first + (difference_type(__n) - __elemsbefore); - __uninitialized_copy_copy(this->_M_start, __pos, __first, __mid, - __new_start, _IsPODType()); + const_iterator __mid = __first + (__n - __elems_before); + __uninitialized_copy_copy(this->_M_start, __pos, __first, __mid, __new_start); this->_M_start = __new_start; copy(__mid, __last, __old_start); } } - _STLP_UNWIND(this->_M_destroy_nodes(__new_start._M_node, this->_M_start._M_node)); + _STLP_UNWIND(this->_M_destroy_nodes(__new_start._M_node, this->_M_start._M_node)) } else { iterator __new_finish = _M_reserve_elements_at_back(__n); iterator __old_finish = this->_M_finish; - const difference_type __elemsafter = - difference_type(__length) - __elemsbefore; - __pos = this->_M_finish - __elemsafter; + const difference_type __elems_after = __length - __elems_before; + __pos = this->_M_finish - __elems_after; _STLP_TRY { - if (__elemsafter > difference_type(__n)) { + if (__elems_after > difference_type(__n)) { iterator __finish_n = this->_M_finish - difference_type(__n); - uninitialized_copy(__finish_n, this->_M_finish, this->_M_finish); + _STLP_PRIV __ucopy(__finish_n, this->_M_finish, this->_M_finish); this->_M_finish = __new_finish; copy_backward(__pos, __finish_n, __old_finish); copy(__first, __last, __pos); } else { - const value_type* __mid = __first + __elemsafter; - __uninitialized_copy_copy(__mid, __last, __pos, this->_M_finish, this->_M_finish, _IsPODType()); + const_iterator __mid = __first + __elems_after; + __uninitialized_copy_copy(__mid, __last, __pos, this->_M_finish, this->_M_finish); this->_M_finish = __new_finish; copy(__first, __mid, __pos); } } - _STLP_UNWIND(this->_M_destroy_nodes(this->_M_finish._M_node + 1, __new_finish._M_node + 1)); + _STLP_UNWIND(this->_M_destroy_nodes(this->_M_finish._M_node + 1, __new_finish._M_node + 1)) } } - -template -void -__deque__<_Tp,_Alloc>::_M_insert_aux(iterator __pos, - const_iterator __first, - const_iterator __last, - size_type __n) -{ - const difference_type __elemsbefore = __pos - this->_M_start; - size_type __length = size(); - if (__elemsbefore < difference_type(__length / 2)) { - iterator __new_start = _M_reserve_elements_at_front(__n); - iterator __old_start = this->_M_start; - __pos = this->_M_start + __elemsbefore; - _STLP_TRY { - if (__elemsbefore >= difference_type(__n)) { - iterator __start_n = this->_M_start + __n; - uninitialized_copy(this->_M_start, __start_n, __new_start); - this->_M_start = __new_start; - copy(__start_n, __pos, __old_start); - copy(__first, __last, __pos - difference_type(__n)); - } - else { - const_iterator __mid = __first + (__n - __elemsbefore); - __uninitialized_copy_copy(this->_M_start, __pos, __first, __mid, - __new_start, _IsPODType()); - this->_M_start = __new_start; - copy(__mid, __last, __old_start); - } - } - _STLP_UNWIND(this->_M_destroy_nodes(__new_start._M_node, this->_M_start._M_node)); - } - else { - iterator __new_finish = _M_reserve_elements_at_back(__n); - iterator __old_finish = this->_M_finish; - const difference_type __elemsafter = __length - __elemsbefore; - __pos = this->_M_finish - __elemsafter; - _STLP_TRY { - if (__elemsafter > difference_type(__n)) { - iterator __finish_n = this->_M_finish - difference_type(__n); - uninitialized_copy(__finish_n, this->_M_finish, this->_M_finish); - this->_M_finish = __new_finish; - copy_backward(__pos, __finish_n, __old_finish); - copy(__first, __last, __pos); - } - else { - const_iterator __mid = __first + __elemsafter; - __uninitialized_copy_copy(__mid, __last, __pos, this->_M_finish, this->_M_finish, _IsPODType()); - this->_M_finish = __new_finish; - copy(__first, __mid, __pos); - } - } - _STLP_UNWIND(this->_M_destroy_nodes(this->_M_finish._M_node + 1, __new_finish._M_node + 1)); - } -} - #endif /* _STLP_MEMBER_TEMPLATES */ template -void -__deque__<_Tp,_Alloc>::_M_new_elements_at_front(size_type __new_elems) -{ +void deque<_Tp,_Alloc>::_M_new_elements_at_front(size_type __new_elems) { size_type __new_nodes = (__new_elems + this->buffer_size() - 1) / this->buffer_size(); _M_reserve_map_at_front(__new_nodes); - size_type __i =1; + size_type __i = 1; _STLP_TRY { for (; __i <= __new_nodes; ++__i) *(this->_M_start._M_node - __i) = this->_M_map_size.allocate(this->buffer_size()); } - _STLP_CATCH_ALL { - for (size_type __j = 1; __j < __i; ++__j) - this->_M_map_size.deallocate(*(this->_M_start._M_node - __j), this->buffer_size()); - _STLP_RETHROW; - } + _STLP_UNWIND(for (size_type __j = 1; __j < __i; ++__j) + this->_M_map_size.deallocate(*(this->_M_start._M_node - __j), this->buffer_size())) } template -void -__deque__<_Tp,_Alloc>::_M_new_elements_at_back(size_type __new_elems) -{ +void deque<_Tp,_Alloc>::_M_new_elements_at_back(size_type __new_elems) { size_type __new_nodes = (__new_elems + this->buffer_size() - 1) / this->buffer_size(); _M_reserve_map_at_back(__new_nodes); @@ -633,33 +756,28 @@ for (; __i <= __new_nodes; ++__i) *(this->_M_finish._M_node + __i) = this->_M_map_size.allocate(this->buffer_size()); } - _STLP_CATCH_ALL { - for (size_type __j = 1; __j < __i; ++__j) - this->_M_map_size.deallocate(*(this->_M_finish._M_node + __j), this->buffer_size()); - _STLP_RETHROW; - } + _STLP_UNWIND(for (size_type __j = 1; __j < __i; ++__j) + this->_M_map_size.deallocate(*(this->_M_finish._M_node + __j), this->buffer_size())) } template -void -__deque__<_Tp,_Alloc>::_M_reallocate_map(size_type __nodes_to_add, - bool __add_at_front) -{ +void deque<_Tp,_Alloc>::_M_reallocate_map(size_type __nodes_to_add, + bool __add_at_front) { size_type __old_num_nodes = this->_M_finish._M_node - this->_M_start._M_node + 1; size_type __new_num_nodes = __old_num_nodes + __nodes_to_add; _Map_pointer __new_nstart; if (this->_M_map_size._M_data > 2 * __new_num_nodes) { - __new_nstart = this->_M_map._M_data + (this->_M_map_size._M_data - __new_num_nodes) / 2 + __new_nstart = this->_M_map._M_data + (this->_M_map_size._M_data - __new_num_nodes) / 2 + (__add_at_front ? __nodes_to_add : 0); if (__new_nstart < this->_M_start._M_node) copy(this->_M_start._M_node, this->_M_finish._M_node + 1, __new_nstart); else - copy_backward(this->_M_start._M_node, this->_M_finish._M_node + 1, + copy_backward(this->_M_start._M_node, this->_M_finish._M_node + 1, __new_nstart + __old_num_nodes); } else { - size_type __new_map_size = + size_type __new_map_size = this->_M_map_size._M_data + (max)((size_t)this->_M_map_size._M_data, __nodes_to_add) + 2; _Map_pointer __new_map = this->_M_map.allocate(__new_map_size); @@ -676,13 +794,18 @@ this->_M_finish._M_set_node(__new_nstart + __old_num_nodes - 1); } +#if defined (deque) +# undef deque +_STLP_MOVE_TO_STD_NAMESPACE +#endif + _STLP_END_NAMESPACE -# undef __iterator__ -# undef iterator -# undef const_iterator -# undef size_type -# undef value_type +#undef __iterator__ +#undef iterator +#undef const_iterator +#undef size_type +#undef value_type #endif /* _STLP_DEQUE_C */