1.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000
1.2 +++ b/epoc32/include/tools/stlport/stl/_deque.c Wed Mar 31 12:33:34 2010 +0100
1.3 @@ -0,0 +1,813 @@
1.4 +/*
1.5 + *
1.6 + *
1.7 + * Copyright (c) 1994
1.8 + * Hewlett-Packard Company
1.9 + *
1.10 + * Copyright (c) 1996,1997
1.11 + * Silicon Graphics Computer Systems, Inc.
1.12 + *
1.13 + * Copyright (c) 1997
1.14 + * Moscow Center for SPARC Technology
1.15 + *
1.16 + * Copyright (c) 1999
1.17 + * Boris Fomitchev
1.18 + *
1.19 + * This material is provided "as is", with absolutely no warranty expressed
1.20 + * or implied. Any use is at your own risk.
1.21 + *
1.22 + * Permission to use or copy this software for any purpose is hereby granted
1.23 + * without fee, provided the above notices are retained on all copies.
1.24 + * Permission to modify the code and to distribute modified code is granted,
1.25 + * provided the above notices are retained, and a notice that the code was
1.26 + * modified is included with the above copyright notice.
1.27 + *
1.28 + */
1.29 +#ifndef _STLP_DEQUE_C
1.30 +#define _STLP_DEQUE_C
1.31 +
1.32 +#ifndef _STLP_INTERNAL_DEQUE_H
1.33 +# include <stl/_deque.h>
1.34 +#endif
1.35 +
1.36 +_STLP_BEGIN_NAMESPACE
1.37 +
1.38 +_STLP_MOVE_TO_PRIV_NAMESPACE
1.39 +
1.40 +// Non-inline member functions from _Deque_base.
1.41 +
1.42 +template <class _Tp, class _Alloc >
1.43 +_Deque_base<_Tp,_Alloc >::~_Deque_base() {
1.44 + if (_M_map._M_data) {
1.45 + _M_destroy_nodes(_M_start._M_node, this->_M_finish._M_node + 1);
1.46 + _M_map.deallocate(_M_map._M_data, _M_map_size._M_data);
1.47 + }
1.48 +}
1.49 +
1.50 +template <class _Tp, class _Alloc >
1.51 +void _Deque_base<_Tp,_Alloc>::_M_initialize_map(size_t __num_elements) {
1.52 + size_t __num_nodes = __num_elements / this->buffer_size() + 1 ;
1.53 +
1.54 + _M_map_size._M_data = (max)((size_t) _S_initial_map_size, __num_nodes + 2);
1.55 + _M_map._M_data = _M_map.allocate(_M_map_size._M_data);
1.56 +
1.57 + _Tp** __nstart = _M_map._M_data + (_M_map_size._M_data - __num_nodes) / 2;
1.58 + _Tp** __nfinish = __nstart + __num_nodes;
1.59 +
1.60 + _STLP_TRY {
1.61 + _M_create_nodes(__nstart, __nfinish);
1.62 + }
1.63 + _STLP_UNWIND((_M_map.deallocate(_M_map._M_data, _M_map_size._M_data),
1.64 + _M_map._M_data = 0, _M_map_size._M_data = 0))
1.65 + _M_start._M_set_node(__nstart);
1.66 + this->_M_finish._M_set_node(__nfinish - 1);
1.67 + _M_start._M_cur = _M_start._M_first;
1.68 + this->_M_finish._M_cur = this->_M_finish._M_first + __num_elements % this->buffer_size();
1.69 +}
1.70 +
1.71 +template <class _Tp, class _Alloc >
1.72 +void _Deque_base<_Tp,_Alloc>::_M_create_nodes(_Tp** __nstart,
1.73 + _Tp** __nfinish) {
1.74 + _Tp** __cur = __nstart;
1.75 + _STLP_TRY {
1.76 + for (; __cur < __nfinish; ++__cur)
1.77 + *__cur = _M_map_size.allocate(this->buffer_size());
1.78 + }
1.79 + _STLP_UNWIND(_M_destroy_nodes(__nstart, __cur))
1.80 +}
1.81 +
1.82 +template <class _Tp, class _Alloc >
1.83 +void _Deque_base<_Tp,_Alloc>::_M_destroy_nodes(_Tp** __nstart,
1.84 + _Tp** __nfinish) {
1.85 + for (_Tp** __n = __nstart; __n < __nfinish; ++__n)
1.86 + _M_map_size.deallocate(*__n, this->buffer_size());
1.87 +}
1.88 +
1.89 +#if defined (_STLP_USE_PTR_SPECIALIZATIONS)
1.90 +# define deque _STLP_PTR_IMPL_NAME(deque)
1.91 +#elif defined (_STLP_DEBUG)
1.92 +# define deque _STLP_NON_DBG_NAME(deque)
1.93 +#else
1.94 +_STLP_MOVE_TO_STD_NAMESPACE
1.95 +#endif
1.96 +
1.97 +#if defined (_STLP_NESTED_TYPE_PARAM_BUG)
1.98 +// qualified references
1.99 +# define __iterator__ _Deque_iterator<_Tp, _Nonconst_traits<_Tp> >
1.100 +# define const_iterator _Deque_iterator<_Tp, _Const_traits<_Tp> >
1.101 +# define iterator __iterator__
1.102 +# define size_type size_t
1.103 +# define value_type _Tp
1.104 +#else
1.105 +# define __iterator__ _STLP_TYPENAME_ON_RETURN_TYPE deque<_Tp, _Alloc>::iterator
1.106 +#endif
1.107 +
1.108 +template <class _Tp, class _Alloc >
1.109 +deque<_Tp, _Alloc >&
1.110 +deque<_Tp, _Alloc >::operator= (const deque<_Tp, _Alloc >& __x) {
1.111 + const size_type __len = size();
1.112 + if (&__x != this) {
1.113 + if (__len >= __x.size())
1.114 + erase(copy(__x.begin(), __x.end(), this->_M_start), this->_M_finish);
1.115 + else {
1.116 + const_iterator __mid = __x.begin() + difference_type(__len);
1.117 + copy(__x.begin(), __mid, this->_M_start);
1.118 + insert(this->_M_finish, __mid, __x.end());
1.119 + }
1.120 + }
1.121 + return *this;
1.122 +}
1.123 +
1.124 +template <class _Tp, class _Alloc >
1.125 +void deque<_Tp, _Alloc >::_M_fill_insert(iterator __pos,
1.126 + size_type __n, const value_type& __x) {
1.127 + if (__pos._M_cur == this->_M_start._M_cur) {
1.128 + iterator __new_start = _M_reserve_elements_at_front(__n);
1.129 + _STLP_TRY {
1.130 + uninitialized_fill(__new_start, this->_M_start, __x);
1.131 + }
1.132 + _STLP_UNWIND(this->_M_destroy_nodes(__new_start._M_node, this->_M_start._M_node))
1.133 + this->_M_start = __new_start;
1.134 + }
1.135 + else if (__pos._M_cur == this->_M_finish._M_cur) {
1.136 + iterator __new_finish = _M_reserve_elements_at_back(__n);
1.137 + _STLP_TRY {
1.138 + uninitialized_fill(this->_M_finish, __new_finish, __x);
1.139 + }
1.140 + _STLP_UNWIND(this->_M_destroy_nodes(this->_M_finish._M_node+1, __new_finish._M_node+1))
1.141 + this->_M_finish = __new_finish;
1.142 + }
1.143 + else
1.144 + _M_fill_insert_aux(__pos, __n, __x, _Movable());
1.145 +}
1.146 +
1.147 +#if !defined (_STLP_MEMBER_TEMPLATES)
1.148 +
1.149 +template <class _Tp, class _Alloc >
1.150 +void deque<_Tp, _Alloc>::insert(iterator __pos,
1.151 + const value_type* __first, const value_type* __last) {
1.152 + size_type __n = __last - __first;
1.153 + if (__pos._M_cur == this->_M_start._M_cur) {
1.154 + iterator __new_start = _M_reserve_elements_at_front(__n);
1.155 + _STLP_TRY {
1.156 + _STLP_PRIV __ucopy(__first, __last, __new_start);
1.157 + }
1.158 + _STLP_UNWIND(this->_M_destroy_nodes(__new_start._M_node, this->_M_start._M_node))
1.159 + this->_M_start = __new_start;
1.160 + }
1.161 + else if (__pos._M_cur == this->_M_finish._M_cur) {
1.162 + iterator __new_finish = _M_reserve_elements_at_back(__n);
1.163 + _STLP_TRY {
1.164 + _STLP_PRIV __ucopy(__first, __last, this->_M_finish);
1.165 + }
1.166 + _STLP_UNWIND(this->_M_destroy_nodes(this->_M_finish._M_node + 1,
1.167 + __new_finish._M_node + 1))
1.168 + this->_M_finish = __new_finish;
1.169 + }
1.170 + else
1.171 + _M_insert_range_aux(__pos, __first, __last, __n, _Movable());
1.172 +}
1.173 +
1.174 +template <class _Tp, class _Alloc >
1.175 +void deque<_Tp,_Alloc>::insert(iterator __pos,
1.176 + const_iterator __first, const_iterator __last) {
1.177 + size_type __n = __last - __first;
1.178 + if (__pos._M_cur == this->_M_start._M_cur) {
1.179 + iterator __new_start = _M_reserve_elements_at_front(__n);
1.180 + _STLP_TRY {
1.181 + _STLP_PRIV __ucopy(__first, __last, __new_start);
1.182 + }
1.183 + _STLP_UNWIND(this->_M_destroy_nodes(__new_start._M_node, this->_M_start._M_node))
1.184 + this->_M_start = __new_start;
1.185 + }
1.186 + else if (__pos._M_cur == this->_M_finish._M_cur) {
1.187 + iterator __new_finish = _M_reserve_elements_at_back(__n);
1.188 + _STLP_TRY {
1.189 + _STLP_PRIV __ucopy(__first, __last, this->_M_finish);
1.190 + }
1.191 + _STLP_UNWIND(this->_M_destroy_nodes(this->_M_finish._M_node + 1,
1.192 + __new_finish._M_node + 1))
1.193 + this->_M_finish = __new_finish;
1.194 + }
1.195 + else
1.196 + _M_insert_range_aux(__pos, __first, __last, __n, _Movable());
1.197 +}
1.198 +
1.199 +#endif /* _STLP_MEMBER_TEMPLATES */
1.200 +
1.201 +template <class _Tp, class _Alloc >
1.202 +__iterator__ deque<_Tp,_Alloc>::_M_erase(iterator __pos,
1.203 + const __true_type& /*_Movable*/) {
1.204 + difference_type __index = __pos - this->_M_start;
1.205 + if (size_type(__index) < this->size() >> 1) {
1.206 + //We move the start of the deque one position to the right
1.207 + //starting from the rightmost element to move.
1.208 + iterator __src = __pos, __dst = __pos;
1.209 + _STLP_STD::_Destroy(&(*__dst));
1.210 + if (__src != this->_M_start) {
1.211 + for (--__src; __dst != this->_M_start; --__src, --__dst) {
1.212 + _STLP_STD::_Move_Construct(&(*__dst), *__src);
1.213 + _STLP_STD::_Destroy_Moved(&(*__src));
1.214 + }
1.215 + }
1.216 + _M_pop_front_aux();
1.217 + }
1.218 + else {
1.219 + iterator __src = __pos, __dst = __pos;
1.220 + _STLP_STD::_Destroy(&(*__dst));
1.221 + for (++__src; __src != this->_M_finish; ++__src, ++__dst) {
1.222 + _STLP_STD::_Move_Construct(&(*__dst), *__src);
1.223 + _STLP_STD::_Destroy_Moved(&(*__src));
1.224 + }
1.225 + //Duplication of the pop_back code without the destroy which has already been done:
1.226 + if (this->_M_finish._M_cur != this->_M_finish._M_first) {
1.227 + --this->_M_finish._M_cur;
1.228 + }
1.229 + else {
1.230 + _M_pop_back_aux();
1.231 + }
1.232 + }
1.233 + return this->_M_start + __index;
1.234 +}
1.235 +
1.236 +template <class _Tp, class _Alloc >
1.237 +__iterator__ deque<_Tp,_Alloc>::_M_erase(iterator __pos,
1.238 + const __false_type& /*_Movable*/) {
1.239 + iterator __next = __pos;
1.240 + ++__next;
1.241 + difference_type __index = __pos - this->_M_start;
1.242 + if (size_type(__index) < this->size() >> 1) {
1.243 + copy_backward(this->_M_start, __pos, __next);
1.244 + pop_front();
1.245 + }
1.246 + else {
1.247 + copy(__next, this->_M_finish, __pos);
1.248 + pop_back();
1.249 + }
1.250 + return this->_M_start + __index;
1.251 +}
1.252 +
1.253 +template <class _Tp, class _Alloc >
1.254 +__iterator__ deque<_Tp,_Alloc>::_M_erase(iterator __first, iterator __last,
1.255 + const __true_type& /*_Movable*/) {
1.256 + difference_type __n = __last - __first;
1.257 + difference_type __elems_before = __first - this->_M_start;
1.258 + if (__elems_before <= difference_type(this->size() - __n) / 2) {
1.259 + iterator __src = __first, __dst = __last;
1.260 + if (__src != this->_M_start) {
1.261 + for (--__src, --__dst; (__src >= this->_M_start) && (__dst >= __first); --__src, --__dst) {
1.262 + _STLP_STD::_Destroy(&(*__dst));
1.263 + _STLP_STD::_Move_Construct(&(*__dst), *__src);
1.264 + }
1.265 + if (__dst >= __first) {
1.266 + //There are more elements to erase than elements to move
1.267 + _STLP_STD::_Destroy_Range(__first, ++__dst);
1.268 + _STLP_STD::_Destroy_Moved_Range(this->_M_start, __first);
1.269 + }
1.270 + else {
1.271 + //There are more elements to move than elements to erase
1.272 + for (; __src >= this->_M_start; --__src, --__dst) {
1.273 + _STLP_STD::_Destroy_Moved(&(*__dst));
1.274 + _STLP_STD::_Move_Construct(&(*__dst), *__src);
1.275 + }
1.276 + _STLP_STD::_Destroy_Moved_Range(this->_M_start, ++__dst);
1.277 + }
1.278 + }
1.279 + else {
1.280 + _STLP_STD::_Destroy_Range(this->_M_start, __last);
1.281 + }
1.282 + iterator __new_start = this->_M_start + __n;
1.283 + this->_M_destroy_nodes(this->_M_start._M_node, __new_start._M_node);
1.284 + this->_M_start = __new_start;
1.285 + }
1.286 + else {
1.287 + if (__last != this->_M_finish) {
1.288 + iterator __src = __last, __dst = __first;
1.289 + for (; (__src != this->_M_finish) && (__dst != __last); ++__src, ++__dst) {
1.290 + _STLP_STD::_Destroy(&(*__dst));
1.291 + _STLP_STD::_Move_Construct(&(*__dst), *__src);
1.292 + }
1.293 + if (__dst != __last) {
1.294 + //There are more elements to erase than elements to move
1.295 + _STLP_STD::_Destroy_Range(__dst, __last);
1.296 + _STLP_STD::_Destroy_Moved_Range(__last, this->_M_finish);
1.297 + }
1.298 + else {
1.299 + //There are more elements to move than elements to erase
1.300 + for (; __src != this->_M_finish; ++__src, ++__dst) {
1.301 + _STLP_STD::_Destroy_Moved(&(*__dst));
1.302 + _STLP_STD::_Move_Construct(&(*__dst), *__src);
1.303 + }
1.304 + _STLP_STD::_Destroy_Moved_Range(__dst, this->_M_finish);
1.305 + }
1.306 + }
1.307 + else {
1.308 + _STLP_STD::_Destroy_Range(__first, this->_M_finish);
1.309 + }
1.310 + iterator __new_finish = this->_M_finish - __n;
1.311 + this->_M_destroy_nodes(__new_finish._M_node + 1, this->_M_finish._M_node + 1);
1.312 + this->_M_finish = __new_finish;
1.313 + }
1.314 + return this->_M_start + __elems_before;
1.315 +}
1.316 +
1.317 +template <class _Tp, class _Alloc >
1.318 +__iterator__ deque<_Tp,_Alloc>::_M_erase(iterator __first, iterator __last,
1.319 + const __false_type& /*_Movable*/) {
1.320 + difference_type __n = __last - __first;
1.321 + difference_type __elems_before = __first - this->_M_start;
1.322 + if (__elems_before <= difference_type(this->size() - __n) / 2) {
1.323 + copy_backward(this->_M_start, __first, __last);
1.324 + iterator __new_start = this->_M_start + __n;
1.325 + _STLP_STD::_Destroy_Range(this->_M_start, __new_start);
1.326 + this->_M_destroy_nodes(this->_M_start._M_node, __new_start._M_node);
1.327 + this->_M_start = __new_start;
1.328 + }
1.329 + else {
1.330 + copy(__last, this->_M_finish, __first);
1.331 + iterator __new_finish = this->_M_finish - __n;
1.332 + _STLP_STD::_Destroy_Range(__new_finish, this->_M_finish);
1.333 + this->_M_destroy_nodes(__new_finish._M_node + 1, this->_M_finish._M_node + 1);
1.334 + this->_M_finish = __new_finish;
1.335 + }
1.336 + return this->_M_start + __elems_before;
1.337 +}
1.338 +
1.339 +template <class _Tp, class _Alloc >
1.340 +void deque<_Tp,_Alloc>::clear() {
1.341 + for (_Map_pointer __node = this->_M_start._M_node + 1;
1.342 + __node < this->_M_finish._M_node;
1.343 + ++__node) {
1.344 + _STLP_STD::_Destroy_Range(*__node, *__node + this->buffer_size());
1.345 + this->_M_map_size.deallocate(*__node, this->buffer_size());
1.346 + }
1.347 +
1.348 + if (this->_M_start._M_node != this->_M_finish._M_node) {
1.349 + _STLP_STD::_Destroy_Range(this->_M_start._M_cur, this->_M_start._M_last);
1.350 + _STLP_STD::_Destroy_Range(this->_M_finish._M_first, this->_M_finish._M_cur);
1.351 + this->_M_map_size.deallocate(this->_M_finish._M_first, this->buffer_size());
1.352 + }
1.353 + else
1.354 + _STLP_STD::_Destroy_Range(this->_M_start._M_cur, this->_M_finish._M_cur);
1.355 +
1.356 + this->_M_finish = this->_M_start;
1.357 +}
1.358 +
1.359 +// Precondition: this->_M_start and this->_M_finish have already been initialized,
1.360 +// but none of the deque's elements have yet been constructed.
1.361 +template <class _Tp, class _Alloc >
1.362 +void deque<_Tp,_Alloc>::_M_fill_initialize(const value_type& __val,
1.363 + const __false_type& /*_TrivialInit*/) {
1.364 + _Map_pointer __cur = this->_M_start._M_node;
1.365 + _STLP_TRY {
1.366 + for (; __cur < this->_M_finish._M_node; ++__cur)
1.367 + uninitialized_fill(*__cur, *__cur + this->buffer_size(), __val);
1.368 + uninitialized_fill(this->_M_finish._M_first, this->_M_finish._M_cur, __val);
1.369 + }
1.370 + _STLP_UNWIND(_STLP_STD::_Destroy_Range(this->_M_start, iterator(*__cur, __cur)))
1.371 +}
1.372 +
1.373 +
1.374 +// Called only if this->_M_finish._M_cur == this->_M_finish._M_last - 1.
1.375 +template <class _Tp, class _Alloc >
1.376 +void deque<_Tp,_Alloc>::_M_push_back_aux_v(const value_type& __t) {
1.377 + _M_reserve_map_at_back();
1.378 + *(this->_M_finish._M_node + 1) = this->_M_map_size.allocate(this->buffer_size());
1.379 + _STLP_TRY {
1.380 + _Copy_Construct(this->_M_finish._M_cur, __t);
1.381 + this->_M_finish._M_set_node(this->_M_finish._M_node + 1);
1.382 + this->_M_finish._M_cur = this->_M_finish._M_first;
1.383 + }
1.384 + _STLP_UNWIND(this->_M_map_size.deallocate(*(this->_M_finish._M_node + 1),
1.385 + this->buffer_size()))
1.386 +}
1.387 +
1.388 +#if defined(_STLP_DONT_SUP_DFLT_PARAM) && !defined(_STLP_NO_ANACHRONISMS)
1.389 +// Called only if this->_M_finish._M_cur == this->_M_finish._M_last - 1.
1.390 +template <class _Tp, class _Alloc >
1.391 +void deque<_Tp,_Alloc>::_M_push_back_aux() {
1.392 + _M_reserve_map_at_back();
1.393 + *(this->_M_finish._M_node + 1) = this->_M_map_size.allocate(this->buffer_size());
1.394 + _STLP_TRY {
1.395 + _STLP_STD::_Construct(this->_M_finish._M_cur);
1.396 + this->_M_finish._M_set_node(this->_M_finish._M_node + 1);
1.397 + this->_M_finish._M_cur = this->_M_finish._M_first;
1.398 + }
1.399 + _STLP_UNWIND(this->_M_map_size.deallocate(*(this->_M_finish._M_node + 1),
1.400 + this->buffer_size()))
1.401 +}
1.402 +#endif /*_STLP_DONT_SUP_DFLT_PARAM && !_STLP_NO_ANACHRONISMS*/
1.403 +
1.404 +// Called only if this->_M_start._M_cur == this->_M_start._M_first.
1.405 +template <class _Tp, class _Alloc >
1.406 +void deque<_Tp,_Alloc>::_M_push_front_aux_v(const value_type& __t) {
1.407 + _M_reserve_map_at_front();
1.408 + *(this->_M_start._M_node - 1) = this->_M_map_size.allocate(this->buffer_size());
1.409 + _STLP_TRY {
1.410 + this->_M_start._M_set_node(this->_M_start._M_node - 1);
1.411 + this->_M_start._M_cur = this->_M_start._M_last - 1;
1.412 + _Copy_Construct(this->_M_start._M_cur, __t);
1.413 + }
1.414 + _STLP_UNWIND((++this->_M_start,
1.415 + this->_M_map_size.deallocate(*(this->_M_start._M_node - 1), this->buffer_size())))
1.416 +}
1.417 +
1.418 +
1.419 +#if defined (_STLP_DONT_SUP_DFLT_PARAM) && !defined (_STLP_NO_ANACHRONISMS)
1.420 +// Called only if this->_M_start._M_cur == this->_M_start._M_first.
1.421 +template <class _Tp, class _Alloc >
1.422 +void deque<_Tp,_Alloc>::_M_push_front_aux() {
1.423 + _M_reserve_map_at_front();
1.424 + *(this->_M_start._M_node - 1) = this->_M_map_size.allocate(this->buffer_size());
1.425 + _STLP_TRY {
1.426 + this->_M_start._M_set_node(this->_M_start._M_node - 1);
1.427 + this->_M_start._M_cur = this->_M_start._M_last - 1;
1.428 + _STLP_STD::_Construct(this->_M_start._M_cur);
1.429 + }
1.430 + _STLP_UNWIND((++this->_M_start, this->_M_map_size.deallocate(*(this->_M_start._M_node - 1),
1.431 + this->buffer_size())))
1.432 +}
1.433 +#endif /*_STLP_DONT_SUP_DFLT_PARAM && !_STLP_NO_ANACHRONISMS*/
1.434 +
1.435 +// Called only if this->_M_finish._M_cur == this->_M_finish._M_first.
1.436 +template <class _Tp, class _Alloc >
1.437 +void deque<_Tp,_Alloc>::_M_pop_back_aux() {
1.438 + this->_M_map_size.deallocate(this->_M_finish._M_first, this->buffer_size());
1.439 + this->_M_finish._M_set_node(this->_M_finish._M_node - 1);
1.440 + this->_M_finish._M_cur = this->_M_finish._M_last - 1;
1.441 +}
1.442 +
1.443 +// Note that if the deque has at least one element (a precondition for this member
1.444 +// function), and if this->_M_start._M_cur == this->_M_start._M_last, then the deque
1.445 +// must have at least two nodes.
1.446 +template <class _Tp, class _Alloc >
1.447 +void deque<_Tp,_Alloc>::_M_pop_front_aux() {
1.448 + if (this->_M_start._M_cur != this->_M_start._M_last - 1)
1.449 + ++this->_M_start._M_cur;
1.450 + else {
1.451 + this->_M_map_size.deallocate(this->_M_start._M_first, this->buffer_size());
1.452 + this->_M_start._M_set_node(this->_M_start._M_node + 1);
1.453 + this->_M_start._M_cur = this->_M_start._M_first;
1.454 + }
1.455 +}
1.456 +
1.457 +template <class _Tp, class _Alloc >
1.458 +__iterator__ deque<_Tp,_Alloc>::_M_fill_insert_aux(iterator __pos, size_type __n,
1.459 + const value_type& __t,
1.460 + const __true_type& /*_Movable*/) {
1.461 + const difference_type __elems_before = __pos - this->_M_start;
1.462 + size_type __length = this->size();
1.463 + value_type __x_copy = __t;
1.464 + if (__elems_before <= difference_type(__length / 2)) {
1.465 + iterator __new_start = _M_reserve_elements_at_front(__n);
1.466 + __pos = this->_M_start + __elems_before;
1.467 + _STLP_TRY {
1.468 + iterator __dst = __new_start;
1.469 + iterator __src = this->_M_start;
1.470 + for (; __src != __pos; ++__dst, ++__src) {
1.471 + _STLP_STD::_Move_Construct(&(*__dst), *__src);
1.472 + _STLP_STD::_Destroy_Moved(&(*__src));
1.473 + }
1.474 + this->_M_start = __new_start;
1.475 + uninitialized_fill(__dst, __src, __x_copy);
1.476 + __pos = __dst;
1.477 + }
1.478 + _STLP_UNWIND(this->_M_destroy_nodes(__new_start._M_node, this->_M_start._M_node))
1.479 + }
1.480 + else {
1.481 + iterator __new_finish = _M_reserve_elements_at_back(__n);
1.482 + const difference_type __elems_after = difference_type(__length) - __elems_before;
1.483 + __pos = this->_M_finish - __elems_after;
1.484 + _STLP_TRY {
1.485 + iterator __dst = __new_finish;
1.486 + iterator __src = this->_M_finish;
1.487 + for (--__src, --__dst; __src >= __pos; --__src, --__dst) {
1.488 + _STLP_STD::_Move_Construct(&(*__dst), *__src);
1.489 + _STLP_STD::_Destroy_Moved(&(*__src));
1.490 + }
1.491 + this->_M_finish = __new_finish;
1.492 + uninitialized_fill(__pos, __pos + __n, __x_copy);
1.493 + }
1.494 + _STLP_UNWIND(this->_M_destroy_nodes(this->_M_finish._M_node + 1, __new_finish._M_node + 1))
1.495 + }
1.496 + return __pos;
1.497 +}
1.498 +
1.499 +template <class _Tp, class _Alloc >
1.500 +__iterator__ deque<_Tp,_Alloc>::_M_fill_insert_aux(iterator __pos, size_type __n,
1.501 + const value_type& __t,
1.502 + const __false_type& /*_Movable*/) {
1.503 + const difference_type __elems_before = __pos - this->_M_start;
1.504 + size_type __length = this->size();
1.505 + value_type __x_copy = __t;
1.506 + if (__elems_before <= difference_type(__length / 2)) {
1.507 + iterator __new_start = _M_reserve_elements_at_front(__n);
1.508 + iterator __old_start = this->_M_start;
1.509 + __pos = this->_M_start + __elems_before;
1.510 + _STLP_TRY {
1.511 + if (__elems_before >= difference_type(__n)) {
1.512 + iterator __start_n = this->_M_start + difference_type(__n);
1.513 + _STLP_PRIV __ucopy(this->_M_start, __start_n, __new_start);
1.514 + this->_M_start = __new_start;
1.515 + copy(__start_n, __pos, __old_start);
1.516 + fill(__pos - difference_type(__n), __pos, __x_copy);
1.517 + }
1.518 + else {
1.519 + _STLP_PRIV __uninitialized_copy_fill(this->_M_start, __pos, __new_start,
1.520 + this->_M_start, __x_copy);
1.521 + this->_M_start = __new_start;
1.522 + fill(__old_start, __pos, __x_copy);
1.523 + }
1.524 + }
1.525 + _STLP_UNWIND(this->_M_destroy_nodes(__new_start._M_node, this->_M_start._M_node))
1.526 + }
1.527 + else {
1.528 + iterator __new_finish = _M_reserve_elements_at_back(__n);
1.529 + iterator __old_finish = this->_M_finish;
1.530 + const difference_type __elems_after =
1.531 + difference_type(__length) - __elems_before;
1.532 + __pos = this->_M_finish - __elems_after;
1.533 + _STLP_TRY {
1.534 + if (__elems_after > difference_type(__n)) {
1.535 + iterator __finish_n = this->_M_finish - difference_type(__n);
1.536 + _STLP_PRIV __ucopy(__finish_n, this->_M_finish, this->_M_finish);
1.537 + this->_M_finish = __new_finish;
1.538 + copy_backward(__pos, __finish_n, __old_finish);
1.539 + fill(__pos, __pos + difference_type(__n), __x_copy);
1.540 + }
1.541 + else {
1.542 + _STLP_PRIV __uninitialized_fill_copy(this->_M_finish, __pos + difference_type(__n),
1.543 + __x_copy, __pos, this->_M_finish);
1.544 + this->_M_finish = __new_finish;
1.545 + fill(__pos, __old_finish, __x_copy);
1.546 + }
1.547 + }
1.548 + _STLP_UNWIND(this->_M_destroy_nodes(this->_M_finish._M_node + 1, __new_finish._M_node + 1))
1.549 + }
1.550 + return __pos;
1.551 +}
1.552 +
1.553 +#if !defined (_STLP_MEMBER_TEMPLATES)
1.554 +template <class _Tp, class _Alloc >
1.555 +void deque<_Tp,_Alloc>::_M_insert_range_aux(iterator __pos,
1.556 + const value_type* __first, const value_type* __last,
1.557 + size_type __n, const __true_type& /*_Movable*/) {
1.558 + const difference_type __elems_before = __pos - this->_M_start;
1.559 + size_type __length = size();
1.560 + if (__elems_before <= difference_type(__length / 2)) {
1.561 + iterator __new_start = _M_reserve_elements_at_front(__n);
1.562 + __pos = this->_M_start + __elems_before;
1.563 + _STLP_TRY {
1.564 + iterator __dst = __new_start;
1.565 + iterator __src = this->_M_start;
1.566 + for (; __src != __pos; ++__dst, ++__src) {
1.567 + _STLP_STD::_Move_Construct(&(*__dst), *__src);
1.568 + _STLP_STD::_Destroy_Moved(&(*__src));
1.569 + }
1.570 + this->_M_start = __new_start;
1.571 + _STLP_PRIV __ucopy(__first, __last, __dst);
1.572 + }
1.573 + _STLP_UNWIND(this->_M_destroy_nodes(__new_start._M_node, this->_M_start._M_node))
1.574 + }
1.575 + else {
1.576 + iterator __new_finish = _M_reserve_elements_at_back(__n);
1.577 + const difference_type __elems_after = difference_type(__length) - __elems_before;
1.578 + __pos = this->_M_finish - __elems_after;
1.579 + _STLP_TRY {
1.580 + iterator __dst = __new_finish;
1.581 + iterator __src = this->_M_finish;
1.582 + for (--__src, --__dst; __src >= __pos; --__src, --__dst) {
1.583 + _STLP_STD::_Move_Construct(&(*__dst), *__src);
1.584 + _STLP_STD::_Destroy_Moved(&(*__src));
1.585 + }
1.586 + this->_M_finish = __new_finish;
1.587 + _STLP_PRIV __ucopy(__first, __last, __pos);
1.588 + }
1.589 + _STLP_UNWIND(this->_M_destroy_nodes(this->_M_finish._M_node + 1, __new_finish._M_node + 1))
1.590 + }
1.591 +}
1.592 +
1.593 +template <class _Tp, class _Alloc >
1.594 +void deque<_Tp,_Alloc>::_M_insert_range_aux(iterator __pos,
1.595 + const value_type* __first, const value_type* __last,
1.596 + size_type __n, const __false_type& /*_Movable*/) {
1.597 + const difference_type __elems_before = __pos - this->_M_start;
1.598 + size_type __length = size();
1.599 + if (__elems_before <= difference_type(__length / 2)) {
1.600 + iterator __new_start = _M_reserve_elements_at_front(__n);
1.601 + iterator __old_start = this->_M_start;
1.602 + __pos = this->_M_start + __elems_before;
1.603 + _STLP_TRY {
1.604 + if (__elems_before >= difference_type(__n)) {
1.605 + iterator __start_n = this->_M_start + difference_type(__n);
1.606 + _STLP_PRIV __ucopy(this->_M_start, __start_n, __new_start);
1.607 + this->_M_start = __new_start;
1.608 + copy(__start_n, __pos, __old_start);
1.609 + copy(__first, __last, __pos - difference_type(__n));
1.610 + }
1.611 + else {
1.612 + const value_type* __mid = __first + (difference_type(__n) - __elems_before);
1.613 + __uninitialized_copy_copy(this->_M_start, __pos, __first, __mid, __new_start);
1.614 + this->_M_start = __new_start;
1.615 + copy(__mid, __last, __old_start);
1.616 + }
1.617 + }
1.618 + _STLP_UNWIND(this->_M_destroy_nodes(__new_start._M_node, this->_M_start._M_node))
1.619 + }
1.620 + else {
1.621 + iterator __new_finish = _M_reserve_elements_at_back(__n);
1.622 + iterator __old_finish = this->_M_finish;
1.623 + const difference_type __elems_after =
1.624 + difference_type(__length) - __elems_before;
1.625 + __pos = this->_M_finish - __elems_after;
1.626 + _STLP_TRY {
1.627 +
1.628 + if (__elems_after > difference_type(__n)) {
1.629 + iterator __finish_n = this->_M_finish - difference_type(__n);
1.630 + _STLP_PRIV __ucopy(__finish_n, this->_M_finish, this->_M_finish);
1.631 + this->_M_finish = __new_finish;
1.632 + copy_backward(__pos, __finish_n, __old_finish);
1.633 + copy(__first, __last, __pos);
1.634 + }
1.635 + else {
1.636 + const value_type* __mid = __first + __elems_after;
1.637 + __uninitialized_copy_copy(__mid, __last, __pos, this->_M_finish, this->_M_finish);
1.638 + this->_M_finish = __new_finish;
1.639 + copy(__first, __mid, __pos);
1.640 + }
1.641 + }
1.642 + _STLP_UNWIND(this->_M_destroy_nodes(this->_M_finish._M_node + 1, __new_finish._M_node + 1))
1.643 + }
1.644 +}
1.645 +
1.646 +template <class _Tp, class _Alloc >
1.647 +void deque<_Tp,_Alloc>::_M_insert_range_aux(iterator __pos,
1.648 + const_iterator __first, const_iterator __last,
1.649 + size_type __n, const __true_type& /*_Movable*/) {
1.650 + const difference_type __elems_before = __pos - this->_M_start;
1.651 + size_type __length = size();
1.652 + if (__elems_before <= difference_type(__length / 2)) {
1.653 + iterator __new_start = _M_reserve_elements_at_front(__n);
1.654 + __pos = this->_M_start + __elems_before;
1.655 + _STLP_TRY {
1.656 + iterator __dst = __new_start;
1.657 + iterator __src = this->_M_start;
1.658 + for (; __src != __pos; ++__dst, ++__src) {
1.659 + _STLP_STD::_Move_Construct(&(*__dst), *__src);
1.660 + _STLP_STD::_Destroy_Moved(&(*__src));
1.661 + }
1.662 + this->_M_start = __new_start;
1.663 + _STLP_PRIV __ucopy(__first, __last, __dst);
1.664 + }
1.665 + _STLP_UNWIND(this->_M_destroy_nodes(__new_start._M_node, this->_M_start._M_node))
1.666 + }
1.667 + else {
1.668 + iterator __new_finish = _M_reserve_elements_at_back(__n);
1.669 + const difference_type __elems_after = difference_type(__length) - __elems_before;
1.670 + __pos = this->_M_finish - __elems_after;
1.671 + _STLP_TRY {
1.672 + iterator __dst = __new_finish;
1.673 + iterator __src = this->_M_finish;
1.674 + for (--__src, --__dst; __src >= __pos; --__src, --__dst) {
1.675 + _STLP_STD::_Move_Construct(&(*__dst), *__src);
1.676 + _STLP_STD::_Destroy_Moved(&(*__src));
1.677 + }
1.678 + this->_M_finish = __new_finish;
1.679 + _STLP_PRIV __ucopy(__first, __last, __pos);
1.680 + }
1.681 + _STLP_UNWIND(this->_M_destroy_nodes(this->_M_finish._M_node + 1, __new_finish._M_node + 1))
1.682 + }
1.683 +}
1.684 +
1.685 +template <class _Tp, class _Alloc >
1.686 +void deque<_Tp,_Alloc>::_M_insert_range_aux(iterator __pos,
1.687 + const_iterator __first, const_iterator __last,
1.688 + size_type __n, const __false_type& /*_Movable*/) {
1.689 + const difference_type __elems_before = __pos - this->_M_start;
1.690 + size_type __length = size();
1.691 + if (__elems_before < difference_type(__length / 2)) {
1.692 + iterator __new_start = _M_reserve_elements_at_front(__n);
1.693 + iterator __old_start = this->_M_start;
1.694 + __pos = this->_M_start + __elems_before;
1.695 + _STLP_TRY {
1.696 + if (__elems_before >= difference_type(__n)) {
1.697 + iterator __start_n = this->_M_start + __n;
1.698 + _STLP_PRIV __ucopy(this->_M_start, __start_n, __new_start);
1.699 + this->_M_start = __new_start;
1.700 + copy(__start_n, __pos, __old_start);
1.701 + copy(__first, __last, __pos - difference_type(__n));
1.702 + }
1.703 + else {
1.704 + const_iterator __mid = __first + (__n - __elems_before);
1.705 + __uninitialized_copy_copy(this->_M_start, __pos, __first, __mid, __new_start);
1.706 + this->_M_start = __new_start;
1.707 + copy(__mid, __last, __old_start);
1.708 + }
1.709 + }
1.710 + _STLP_UNWIND(this->_M_destroy_nodes(__new_start._M_node, this->_M_start._M_node))
1.711 + }
1.712 + else {
1.713 + iterator __new_finish = _M_reserve_elements_at_back(__n);
1.714 + iterator __old_finish = this->_M_finish;
1.715 + const difference_type __elems_after = __length - __elems_before;
1.716 + __pos = this->_M_finish - __elems_after;
1.717 + _STLP_TRY {
1.718 + if (__elems_after > difference_type(__n)) {
1.719 + iterator __finish_n = this->_M_finish - difference_type(__n);
1.720 + _STLP_PRIV __ucopy(__finish_n, this->_M_finish, this->_M_finish);
1.721 + this->_M_finish = __new_finish;
1.722 + copy_backward(__pos, __finish_n, __old_finish);
1.723 + copy(__first, __last, __pos);
1.724 + }
1.725 + else {
1.726 + const_iterator __mid = __first + __elems_after;
1.727 + __uninitialized_copy_copy(__mid, __last, __pos, this->_M_finish, this->_M_finish);
1.728 + this->_M_finish = __new_finish;
1.729 + copy(__first, __mid, __pos);
1.730 + }
1.731 + }
1.732 + _STLP_UNWIND(this->_M_destroy_nodes(this->_M_finish._M_node + 1, __new_finish._M_node + 1))
1.733 + }
1.734 +}
1.735 +#endif /* _STLP_MEMBER_TEMPLATES */
1.736 +
1.737 +template <class _Tp, class _Alloc >
1.738 +void deque<_Tp,_Alloc>::_M_new_elements_at_front(size_type __new_elems) {
1.739 + size_type __new_nodes
1.740 + = (__new_elems + this->buffer_size() - 1) / this->buffer_size();
1.741 + _M_reserve_map_at_front(__new_nodes);
1.742 + size_type __i = 1;
1.743 + _STLP_TRY {
1.744 + for (; __i <= __new_nodes; ++__i)
1.745 + *(this->_M_start._M_node - __i) = this->_M_map_size.allocate(this->buffer_size());
1.746 + }
1.747 + _STLP_UNWIND(for (size_type __j = 1; __j < __i; ++__j)
1.748 + this->_M_map_size.deallocate(*(this->_M_start._M_node - __j), this->buffer_size()))
1.749 +}
1.750 +
1.751 +template <class _Tp, class _Alloc >
1.752 +void deque<_Tp,_Alloc>::_M_new_elements_at_back(size_type __new_elems) {
1.753 + size_type __new_nodes
1.754 + = (__new_elems + this->buffer_size() - 1) / this->buffer_size();
1.755 + _M_reserve_map_at_back(__new_nodes);
1.756 + size_type __i = 1;
1.757 + _STLP_TRY {
1.758 + for (; __i <= __new_nodes; ++__i)
1.759 + *(this->_M_finish._M_node + __i) = this->_M_map_size.allocate(this->buffer_size());
1.760 + }
1.761 + _STLP_UNWIND(for (size_type __j = 1; __j < __i; ++__j)
1.762 + this->_M_map_size.deallocate(*(this->_M_finish._M_node + __j), this->buffer_size()))
1.763 +}
1.764 +
1.765 +template <class _Tp, class _Alloc >
1.766 +void deque<_Tp,_Alloc>::_M_reallocate_map(size_type __nodes_to_add,
1.767 + bool __add_at_front) {
1.768 + size_type __old_num_nodes = this->_M_finish._M_node - this->_M_start._M_node + 1;
1.769 + size_type __new_num_nodes = __old_num_nodes + __nodes_to_add;
1.770 +
1.771 + _Map_pointer __new_nstart;
1.772 + if (this->_M_map_size._M_data > 2 * __new_num_nodes) {
1.773 + __new_nstart = this->_M_map._M_data + (this->_M_map_size._M_data - __new_num_nodes) / 2
1.774 + + (__add_at_front ? __nodes_to_add : 0);
1.775 + if (__new_nstart < this->_M_start._M_node)
1.776 + copy(this->_M_start._M_node, this->_M_finish._M_node + 1, __new_nstart);
1.777 + else
1.778 + copy_backward(this->_M_start._M_node, this->_M_finish._M_node + 1,
1.779 + __new_nstart + __old_num_nodes);
1.780 + }
1.781 + else {
1.782 + size_type __new_map_size =
1.783 + this->_M_map_size._M_data + (max)((size_t)this->_M_map_size._M_data, __nodes_to_add) + 2;
1.784 +
1.785 + _Map_pointer __new_map = this->_M_map.allocate(__new_map_size);
1.786 + __new_nstart = __new_map + (__new_map_size - __new_num_nodes) / 2
1.787 + + (__add_at_front ? __nodes_to_add : 0);
1.788 + copy(this->_M_start._M_node, this->_M_finish._M_node + 1, __new_nstart);
1.789 + this->_M_map.deallocate(this->_M_map._M_data, this->_M_map_size._M_data);
1.790 +
1.791 + this->_M_map._M_data = __new_map;
1.792 + this->_M_map_size._M_data = __new_map_size;
1.793 + }
1.794 +
1.795 + this->_M_start._M_set_node(__new_nstart);
1.796 + this->_M_finish._M_set_node(__new_nstart + __old_num_nodes - 1);
1.797 +}
1.798 +
1.799 +#if defined (deque)
1.800 +# undef deque
1.801 +_STLP_MOVE_TO_STD_NAMESPACE
1.802 +#endif
1.803 +
1.804 +_STLP_END_NAMESPACE
1.805 +
1.806 +#undef __iterator__
1.807 +#undef iterator
1.808 +#undef const_iterator
1.809 +#undef size_type
1.810 +#undef value_type
1.811 +
1.812 +#endif /* _STLP_DEQUE_C */
1.813 +
1.814 +// Local Variables:
1.815 +// mode:C++
1.816 +// End: