1.1 --- a/epoc32/include/stdapis/stlport/stl/_deque.c Tue Nov 24 13:55:44 2009 +0000
1.2 +++ b/epoc32/include/stdapis/stlport/stl/_deque.c Tue Mar 16 16:12:26 2010 +0000
1.3 @@ -1,1 +1,691 @@
1.4 -_deque.c
1.5 +/*
1.6 + *
1.7 + *
1.8 + * Copyright (c) 1994
1.9 + * Hewlett-Packard Company
1.10 + *
1.11 + * Copyright (c) 1996,1997
1.12 + * Silicon Graphics Computer Systems, Inc.
1.13 + *
1.14 + * Copyright (c) 1997
1.15 + * Moscow Center for SPARC Technology
1.16 + *
1.17 + * Copyright (c) 1999
1.18 + * Boris Fomitchev
1.19 + *
1.20 + * This material is provided "as is", with absolutely no warranty expressed
1.21 + * or implied. Any use is at your own risk.
1.22 + *
1.23 + * Permission to use or copy this software for any purpose is hereby granted
1.24 + * without fee, provided the above notices are retained on all copies.
1.25 + * Permission to modify the code and to distribute modified code is granted,
1.26 + * provided the above notices are retained, and a notice that the code was
1.27 + * modified is included with the above copyright notice.
1.28 + *
1.29 + */
1.30 +#ifndef _STLP_DEQUE_C
1.31 +# define _STLP_DEQUE_C
1.32 +
1.33 +# ifndef _STLP_INTERNAL_DEQUE_H
1.34 +# include <stl/_deque.h>
1.35 +# endif
1.36 +
1.37 +_STLP_BEGIN_NAMESPACE
1.38 +
1.39 +// Non-inline member functions from _Deque_base.
1.40 +
1.41 +template <class _Tp, class _Alloc >
1.42 +_Deque_base<_Tp,_Alloc >::~_Deque_base() {
1.43 + if (_M_map._M_data) {
1.44 + if (_M_start._M_node) {
1.45 + _M_destroy_nodes(_M_start._M_node, this->_M_finish._M_node + 1);
1.46 + }
1.47 + _M_map.deallocate(_M_map._M_data, _M_map_size._M_data);
1.48 + }
1.49 +}
1.50 +
1.51 +template <class _Tp, class _Alloc >
1.52 +void
1.53 +_Deque_base<_Tp,_Alloc>::_M_initialize_map(size_t __num_elements)
1.54 +{
1.55 + size_t __num_nodes =
1.56 + __num_elements / this->buffer_size() + 1 ;
1.57 +
1.58 + _M_map_size._M_data = (max)((size_t) _S_initial_map_size, __num_nodes + 2);
1.59 + _M_map._M_data = _M_map.allocate(_M_map_size._M_data);
1.60 +
1.61 + _Tp** __nstart = _M_map._M_data + (_M_map_size._M_data - __num_nodes) / 2;
1.62 + _Tp** __nfinish = __nstart + __num_nodes;
1.63 +
1.64 + _STLP_TRY {
1.65 + _M_create_nodes(__nstart, __nfinish);
1.66 + }
1.67 + _STLP_UNWIND((_M_map.deallocate(_M_map._M_data, _M_map_size._M_data),
1.68 + _M_map._M_data = 0, _M_map_size._M_data = 0));
1.69 + _M_start._M_set_node(__nstart);
1.70 + this->_M_finish._M_set_node(__nfinish - 1);
1.71 + _M_start._M_cur = _M_start._M_first;
1.72 + this->_M_finish._M_cur = this->_M_finish._M_first +
1.73 + __num_elements % this->buffer_size();
1.74 +}
1.75 +
1.76 +template <class _Tp, class _Alloc >
1.77 +void
1.78 +_Deque_base<_Tp,_Alloc>::_M_create_nodes(_Tp** __nstart,
1.79 + _Tp** __nfinish)
1.80 +{
1.81 + _Tp** _STLP_LEAVE_VOLATILE __cur = 0;
1.82 + _STLP_TRY {
1.83 + for (__cur = __nstart; __cur < __nfinish; ++__cur)
1.84 + *__cur = _M_map_size.allocate(this->buffer_size());
1.85 + }
1.86 + _STLP_UNWIND(_M_destroy_nodes(__nstart, __cur));
1.87 +}
1.88 +
1.89 +template <class _Tp, class _Alloc >
1.90 +void
1.91 +_Deque_base<_Tp,_Alloc>::_M_destroy_nodes(_Tp** __nstart,
1.92 + _Tp** __nfinish)
1.93 +{
1.94 + for (_Tp** __n = __nstart; __n < __nfinish; ++__n)
1.95 + _M_map_size.deallocate(*__n, this->buffer_size());
1.96 +}
1.97 +
1.98 +
1.99 +
1.100 +// Non-inline member functions
1.101 +
1.102 +# if defined ( _STLP_NESTED_TYPE_PARAM_BUG )
1.103 +// qualified references
1.104 +# define __iterator__ _Deque_iterator<_Tp, _Nonconst_traits<_Tp> >
1.105 +# define const_iterator _Deque_iterator<_Tp, _Const_traits<_Tp> >
1.106 +# define iterator __iterator__
1.107 +# define size_type size_t
1.108 +# define value_type _Tp
1.109 +# else
1.110 +# define __iterator__ _STLP_TYPENAME_ON_RETURN_TYPE __deque__<_Tp, _Alloc>::iterator
1.111 +# endif
1.112 +
1.113 +template <class _Tp, class _Alloc >
1.114 +__deque__<_Tp, _Alloc >&
1.115 +__deque__<_Tp, _Alloc >::operator= (const __deque__<_Tp, _Alloc >& __x) {
1.116 + const size_type __len = size();
1.117 + if (&__x != this) {
1.118 + if (__len >= __x.size())
1.119 + erase(copy(__x.begin(), __x.end(), this->_M_start), this->_M_finish);
1.120 + else {
1.121 + const_iterator __mid = __x.begin() + difference_type(__len);
1.122 + copy(__x.begin(), __mid, this->_M_start);
1.123 + insert(this->_M_finish, __mid, __x.end());
1.124 + }
1.125 + }
1.126 + return *this;
1.127 +}
1.128 +
1.129 +template <class _Tp, class _Alloc >
1.130 +void
1.131 +__deque__<_Tp, _Alloc >::_M_fill_insert(iterator __pos,
1.132 + size_type __n, const value_type& __x)
1.133 +{
1.134 + if (__pos._M_cur == this->_M_start._M_cur) {
1.135 + iterator __new_start = _M_reserve_elements_at_front(__n);
1.136 + _STLP_TRY {
1.137 + uninitialized_fill(__new_start, this->_M_start, __x);
1.138 + }
1.139 + _STLP_UNWIND(this->_M_destroy_nodes(__new_start._M_node, this->_M_start._M_node));
1.140 + this->_M_start = __new_start;
1.141 + }
1.142 + else if (__pos._M_cur == this->_M_finish._M_cur) {
1.143 + iterator __new_finish = _M_reserve_elements_at_back(__n);
1.144 + _STLP_TRY {
1.145 + uninitialized_fill(this->_M_finish, __new_finish, __x);
1.146 + }
1.147 + _STLP_UNWIND(this->_M_destroy_nodes(this->_M_finish._M_node+1, __new_finish._M_node+1));
1.148 + this->_M_finish = __new_finish;
1.149 + }
1.150 + else
1.151 + _M_insert_aux(__pos, __n, __x);
1.152 +}
1.153 +
1.154 +#ifndef _STLP_MEMBER_TEMPLATES
1.155 +
1.156 +template <class _Tp, class _Alloc >
1.157 +void __deque__<_Tp, _Alloc>::insert(iterator __pos,
1.158 + const value_type* __first,
1.159 + const value_type* __last) {
1.160 + size_type __n = __last - __first;
1.161 + if (__pos._M_cur == this->_M_start._M_cur) {
1.162 + iterator __new_start = _M_reserve_elements_at_front(__n);
1.163 + _STLP_TRY {
1.164 + uninitialized_copy(__first, __last, __new_start);
1.165 + }
1.166 + _STLP_UNWIND(this->_M_destroy_nodes(__new_start._M_node, this->_M_start._M_node));
1.167 + this->_M_start = __new_start;
1.168 + }
1.169 + else if (__pos._M_cur == this->_M_finish._M_cur) {
1.170 + iterator __new_finish = _M_reserve_elements_at_back(__n);
1.171 + _STLP_TRY {
1.172 + uninitialized_copy(__first, __last, this->_M_finish);
1.173 + }
1.174 + _STLP_UNWIND(this->_M_destroy_nodes(this->_M_finish._M_node + 1,
1.175 + __new_finish._M_node + 1));
1.176 + this->_M_finish = __new_finish;
1.177 + }
1.178 + else
1.179 + _M_insert_aux(__pos, __first, __last, __n);
1.180 +}
1.181 +
1.182 +template <class _Tp, class _Alloc >
1.183 +void __deque__<_Tp,_Alloc>::insert(iterator __pos,
1.184 + const_iterator __first,
1.185 + const_iterator __last)
1.186 +{
1.187 + size_type __n = __last - __first;
1.188 + if (__pos._M_cur == this->_M_start._M_cur) {
1.189 + iterator __new_start = _M_reserve_elements_at_front(__n);
1.190 + _STLP_TRY {
1.191 + uninitialized_copy(__first, __last, __new_start);
1.192 + }
1.193 + _STLP_UNWIND(this->_M_destroy_nodes(__new_start._M_node, this->_M_start._M_node));
1.194 + this->_M_start = __new_start;
1.195 + }
1.196 + else if (__pos._M_cur == this->_M_finish._M_cur) {
1.197 + iterator __new_finish = _M_reserve_elements_at_back(__n);
1.198 + _STLP_TRY {
1.199 + uninitialized_copy(__first, __last, this->_M_finish);
1.200 + }
1.201 + _STLP_UNWIND(this->_M_destroy_nodes(this->_M_finish._M_node + 1,__new_finish._M_node + 1));
1.202 + this->_M_finish = __new_finish;
1.203 + }
1.204 + else
1.205 + _M_insert_aux(__pos, __first, __last, __n);
1.206 +}
1.207 +
1.208 +#endif /* _STLP_MEMBER_TEMPLATES */
1.209 +
1.210 +template <class _Tp, class _Alloc >
1.211 +__iterator__
1.212 +__deque__<_Tp,_Alloc>::erase(iterator __first, iterator __last)
1.213 +{
1.214 + if (__first == this->_M_start && __last == this->_M_finish) {
1.215 + clear();
1.216 + return this->_M_finish;
1.217 + }
1.218 + else {
1.219 + difference_type __n = __last - __first;
1.220 + difference_type __elems_before = __first - this->_M_start;
1.221 + if (__elems_before < difference_type(this->size() - __n) / 2) {
1.222 + copy_backward(this->_M_start, __first, __last);
1.223 + iterator __new_start = this->_M_start + __n;
1.224 + _STLP_STD::_Destroy(this->_M_start, __new_start);
1.225 + this->_M_destroy_nodes(this->_M_start._M_node, __new_start._M_node);
1.226 + this->_M_start = __new_start;
1.227 + }
1.228 + else {
1.229 + copy(__last, this->_M_finish, __first);
1.230 + iterator __new_finish = this->_M_finish - __n;
1.231 + _STLP_STD::_Destroy(__new_finish, this->_M_finish);
1.232 + this->_M_destroy_nodes(__new_finish._M_node + 1, this->_M_finish._M_node + 1);
1.233 + this->_M_finish = __new_finish;
1.234 + }
1.235 + return this->_M_start + __elems_before;
1.236 + }
1.237 +}
1.238 +
1.239 +template <class _Tp, class _Alloc >
1.240 +void __deque__<_Tp,_Alloc>::clear()
1.241 +{
1.242 + for (_Map_pointer __node = this->_M_start._M_node + 1;
1.243 + __node < this->_M_finish._M_node;
1.244 + ++__node) {
1.245 + _STLP_STD::_Destroy(*__node, *__node + this->buffer_size());
1.246 + this->_M_map_size.deallocate(*__node, this->buffer_size());
1.247 + }
1.248 +
1.249 + if (this->_M_start._M_node != this->_M_finish._M_node) {
1.250 + _STLP_STD::_Destroy(this->_M_start._M_cur, this->_M_start._M_last);
1.251 + _STLP_STD::_Destroy(this->_M_finish._M_first, this->_M_finish._M_cur);
1.252 + this->_M_map_size.deallocate(this->_M_finish._M_first, this->buffer_size());
1.253 + }
1.254 + else
1.255 + _STLP_STD::_Destroy(this->_M_start._M_cur, this->_M_finish._M_cur);
1.256 +
1.257 + this->_M_finish = this->_M_start;
1.258 +}
1.259 +
1.260 +// Precondition: this->_M_start and this->_M_finish have already been initialized,
1.261 +// but none of the deque's elements have yet been constructed.
1.262 +template <class _Tp, class _Alloc >
1.263 +void
1.264 +__deque__<_Tp,_Alloc>::_M_fill_initialize(const value_type& __val) {
1.265 + _STLP_LEAVE_VOLATILE _Map_pointer __cur = 0;
1.266 + _STLP_TRY {
1.267 + for (__cur = this->_M_start._M_node; __cur < this->_M_finish._M_node; ++__cur)
1.268 + uninitialized_fill(*__cur, *__cur + this->buffer_size(), __val);
1.269 + uninitialized_fill(this->_M_finish._M_first, this->_M_finish._M_cur, __val);
1.270 + }
1.271 + _STLP_UNWIND(_STLP_STD::_Destroy(this->_M_start, iterator(*__cur, __cur)));
1.272 +}
1.273 +
1.274 +
1.275 +// Called only if this->_M_finish._M_cur == this->_M_finish._M_last - 1.
1.276 +template <class _Tp, class _Alloc >
1.277 +void
1.278 +__deque__<_Tp,_Alloc>::_M_push_back_aux_v(const value_type& __t)
1.279 +{
1.280 + value_type __t_copy = __t;
1.281 + _STLP_PUSH_CLEANUP_ITEM(value_type, &__t_copy);
1.282 + _M_reserve_map_at_back();
1.283 + *(this->_M_finish._M_node + 1) = this->_M_map_size.allocate(this->buffer_size());
1.284 + _STLP_TRY {
1.285 + _Construct(this->_M_finish._M_cur, __t_copy);
1.286 + this->_M_finish._M_set_node(this->_M_finish._M_node + 1);
1.287 + this->_M_finish._M_cur = this->_M_finish._M_first;
1.288 + }
1.289 + _STLP_UNWIND(this->_M_map_size.deallocate(*(this->_M_finish._M_node + 1),
1.290 + this->buffer_size()));
1.291 +#ifdef _STLP_USE_TRAP_LEAVE
1.292 + CleanupStack::Pop();
1.293 +#endif
1.294 +}
1.295 +
1.296 +# ifndef _STLP_NO_ANACHRONISMS
1.297 +// Called only if this->_M_finish._M_cur == this->_M_finish._M_last - 1.
1.298 +template <class _Tp, class _Alloc >
1.299 +void
1.300 +__deque__<_Tp,_Alloc>::_M_push_back_aux()
1.301 +{
1.302 + _M_reserve_map_at_back();
1.303 + *(this->_M_finish._M_node + 1) = this->_M_map_size.allocate(this->buffer_size());
1.304 + _STLP_TRY {
1.305 + _Construct(this->_M_finish._M_cur);
1.306 + this->_M_finish._M_set_node(this->_M_finish._M_node + 1);
1.307 + this->_M_finish._M_cur = this->_M_finish._M_first;
1.308 + }
1.309 + _STLP_UNWIND(this->_M_map_size.deallocate(*(this->_M_finish._M_node + 1),
1.310 + this->buffer_size()));
1.311 +}
1.312 +# endif
1.313 +
1.314 +// Called only if this->_M_start._M_cur == this->_M_start._M_first.
1.315 +template <class _Tp, class _Alloc >
1.316 +void
1.317 +__deque__<_Tp,_Alloc>::_M_push_front_aux_v(const value_type& __t)
1.318 +{
1.319 + value_type __t_copy = __t;
1.320 + _STLP_PUSH_CLEANUP_ITEM(value_type, &__t_copy);
1.321 + _M_reserve_map_at_front();
1.322 + *(this->_M_start._M_node - 1) = this->_M_map_size.allocate(this->buffer_size());
1.323 + _STLP_TRY {
1.324 + this->_M_start._M_set_node(this->_M_start._M_node - 1);
1.325 + this->_M_start._M_cur = this->_M_start._M_last - 1;
1.326 + _Construct(this->_M_start._M_cur, __t_copy);
1.327 + }
1.328 + _STLP_UNWIND((++this->_M_start,
1.329 + this->_M_map_size.deallocate(*(this->_M_start._M_node - 1), this->buffer_size())));
1.330 +#ifdef _STLP_USE_TRAP_LEAVE
1.331 + CleanupStack::Pop();
1.332 +#endif
1.333 +}
1.334 +
1.335 +
1.336 +# ifndef _STLP_NO_ANACHRONISMS
1.337 +// Called only if this->_M_start._M_cur == this->_M_start._M_first.
1.338 +template <class _Tp, class _Alloc >
1.339 +void
1.340 +__deque__<_Tp,_Alloc>::_M_push_front_aux()
1.341 +{
1.342 + _M_reserve_map_at_front();
1.343 + *(this->_M_start._M_node - 1) = this->_M_map_size.allocate(this->buffer_size());
1.344 + _STLP_TRY {
1.345 + this->_M_start._M_set_node(this->_M_start._M_node - 1);
1.346 + this->_M_start._M_cur = this->_M_start._M_last - 1;
1.347 + _Construct(this->_M_start._M_cur);
1.348 + }
1.349 + _STLP_UNWIND((++this->_M_start, this->_M_map_size.deallocate(*(this->_M_start._M_node - 1),
1.350 + this->buffer_size() )));
1.351 +}
1.352 +# endif
1.353 +
1.354 +// Called only if this->_M_finish._M_cur == this->_M_finish._M_first.
1.355 +template <class _Tp, class _Alloc >
1.356 +void
1.357 +__deque__<_Tp,_Alloc>::_M_pop_back_aux()
1.358 +{
1.359 + this->_M_map_size.deallocate(this->_M_finish._M_first, this->buffer_size());
1.360 + this->_M_finish._M_set_node(this->_M_finish._M_node - 1);
1.361 + this->_M_finish._M_cur = this->_M_finish._M_last - 1;
1.362 + _STLP_STD::_Destroy(this->_M_finish._M_cur);
1.363 +}
1.364 +
1.365 +// Called only if this->_M_start._M_cur == this->_M_start._M_last - 1. Note that
1.366 +// if the deque has at least one element (a precondition for this member
1.367 +// function), and if this->_M_start._M_cur == this->_M_start._M_last, then the deque
1.368 +// must have at least two nodes.
1.369 +template <class _Tp, class _Alloc >
1.370 +void
1.371 +__deque__<_Tp,_Alloc>::_M_pop_front_aux()
1.372 +{
1.373 + _STLP_STD::_Destroy(this->_M_start._M_cur);
1.374 + this->_M_map_size.deallocate(this->_M_start._M_first, this->buffer_size());
1.375 + this->_M_start._M_set_node(this->_M_start._M_node + 1);
1.376 + this->_M_start._M_cur = this->_M_start._M_first;
1.377 +}
1.378 +
1.379 +
1.380 +
1.381 +template <class _Tp, class _Alloc >
1.382 +__iterator__
1.383 +__deque__<_Tp,_Alloc>::_M_insert_aux_prepare(iterator __pos) {
1.384 + difference_type __index = __pos - this->_M_start;
1.385 + if (__index < difference_type(size() / 2)) {
1.386 + push_front(front());
1.387 + iterator __front1 = this->_M_start;
1.388 + ++__front1;
1.389 + iterator __front2 = __front1;
1.390 + ++__front2;
1.391 + __pos = this->_M_start + __index;
1.392 + iterator __pos1 = __pos;
1.393 + ++__pos1;
1.394 + copy(__front2, __pos1, __front1);
1.395 + }
1.396 + else {
1.397 + push_back(back());
1.398 + iterator __back1 = this->_M_finish;
1.399 + --__back1;
1.400 + iterator __back2 = __back1;
1.401 + --__back2;
1.402 + __pos = this->_M_start + __index;
1.403 + copy_backward(__pos, __back2, __back1);
1.404 + }
1.405 + return __pos;
1.406 +}
1.407 +
1.408 +template <class _Tp, class _Alloc >
1.409 +__iterator__
1.410 +__deque__<_Tp,_Alloc>::_M_insert_aux(iterator __pos,
1.411 + const value_type& __x) {
1.412 + value_type __x_copy = __x;
1.413 + _STLP_PUSH_CLEANUP_ITEM(value_type, &__x_copy);
1.414 + _STLP_MPWFIX_TRY //*TY 06/01/2000 - mpw forget to call dtor on __x_copy without this try block
1.415 + __pos = _M_insert_aux_prepare(__pos);
1.416 + *__pos = __x_copy;
1.417 +#ifdef _STLP_USE_TRAP_LEAVE
1.418 + CleanupStack::Pop();
1.419 +#endif
1.420 + return __pos;
1.421 + _STLP_MPWFIX_CATCH //*TY 06/01/2000 -
1.422 +}
1.423 +
1.424 +template <class _Tp, class _Alloc >
1.425 +__iterator__
1.426 +__deque__<_Tp,_Alloc>::_M_insert_aux(iterator __pos)
1.427 +{
1.428 + __pos = _M_insert_aux_prepare(__pos);
1.429 + *__pos = value_type();
1.430 + return __pos;
1.431 +}
1.432 +
1.433 +template <class _Tp, class _Alloc >
1.434 +void
1.435 +__deque__<_Tp,_Alloc>::_M_insert_aux(iterator __pos,
1.436 + size_type __n,
1.437 + const value_type& __x)
1.438 +{
1.439 + const difference_type __elems_before = __pos - this->_M_start;
1.440 + size_type __length = this->size();
1.441 + value_type __x_copy = __x;
1.442 + _STLP_PUSH_CLEANUP_ITEM(value_type, &__x_copy);
1.443 +
1.444 + if (__elems_before < difference_type(__length / 2)) {
1.445 + iterator __new_start = _M_reserve_elements_at_front(__n);
1.446 + iterator __old_start = this->_M_start;
1.447 + __pos = this->_M_start + __elems_before;
1.448 + _STLP_TRY {
1.449 + if (__elems_before >= difference_type(__n)) {
1.450 + iterator __start_n = this->_M_start + difference_type(__n);
1.451 + uninitialized_copy(this->_M_start, __start_n, __new_start);
1.452 + this->_M_start = __new_start;
1.453 + copy(__start_n, __pos, __old_start);
1.454 + fill(__pos - difference_type(__n), __pos, __x_copy);
1.455 + }
1.456 + else {
1.457 + __uninitialized_copy_fill(this->_M_start, __pos, __new_start,
1.458 + this->_M_start, __x_copy);
1.459 + this->_M_start = __new_start;
1.460 + fill(__old_start, __pos, __x_copy);
1.461 + }
1.462 + }
1.463 + _STLP_UNWIND(this->_M_destroy_nodes(__new_start._M_node, this->_M_start._M_node));
1.464 + }
1.465 + else {
1.466 + iterator __new_finish = _M_reserve_elements_at_back(__n);
1.467 + iterator __old_finish = this->_M_finish;
1.468 + const difference_type __elems_after =
1.469 + difference_type(__length) - __elems_before;
1.470 + __pos = this->_M_finish - __elems_after;
1.471 + _STLP_TRY {
1.472 + if (__elems_after > difference_type(__n)) {
1.473 + iterator __finish_n = this->_M_finish - difference_type(__n);
1.474 + uninitialized_copy(__finish_n, this->_M_finish, this->_M_finish);
1.475 + this->_M_finish = __new_finish;
1.476 + copy_backward(__pos, __finish_n, __old_finish);
1.477 + fill(__pos, __pos + difference_type(__n), __x_copy);
1.478 + }
1.479 + else {
1.480 + __uninitialized_fill_copy(this->_M_finish, __pos + difference_type(__n),
1.481 + __x_copy, __pos, this->_M_finish);
1.482 + this->_M_finish = __new_finish;
1.483 + fill(__pos, __old_finish, __x_copy);
1.484 + }
1.485 + }
1.486 + _STLP_UNWIND(this->_M_destroy_nodes(this->_M_finish._M_node + 1, __new_finish._M_node + 1));
1.487 + }
1.488 +#ifdef _STLP_USE_TRAP_LEAVE
1.489 + CleanupStack::Pop();
1.490 +#endif
1.491 +}
1.492 +
1.493 +#ifndef _STLP_MEMBER_TEMPLATES
1.494 +template <class _Tp, class _Alloc >
1.495 +void
1.496 +__deque__<_Tp,_Alloc>::_M_insert_aux(iterator __pos,
1.497 + const value_type* __first,
1.498 + const value_type* __last,
1.499 + size_type __n)
1.500 +{
1.501 +
1.502 + const difference_type __elemsbefore = __pos - this->_M_start;
1.503 + size_type __length = size();
1.504 + if (__elemsbefore < difference_type(__length / 2)) {
1.505 + iterator __new_start = _M_reserve_elements_at_front(__n);
1.506 + iterator __old_start = this->_M_start;
1.507 + __pos = this->_M_start + __elemsbefore;
1.508 + _STLP_TRY {
1.509 + if (__elemsbefore >= difference_type(__n)) {
1.510 + iterator __start_n = this->_M_start + difference_type(__n);
1.511 + uninitialized_copy(this->_M_start, __start_n, __new_start);
1.512 + this->_M_start = __new_start;
1.513 + copy(__start_n, __pos, __old_start);
1.514 + copy(__first, __last, __pos - difference_type(__n));
1.515 + }
1.516 + else {
1.517 + const value_type* __mid =
1.518 + __first + (difference_type(__n) - __elemsbefore);
1.519 + __uninitialized_copy_copy(this->_M_start, __pos, __first, __mid,
1.520 + __new_start, _IsPODType());
1.521 + this->_M_start = __new_start;
1.522 + copy(__mid, __last, __old_start);
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 __elemsafter =
1.531 + difference_type(__length) - __elemsbefore;
1.532 + __pos = this->_M_finish - __elemsafter;
1.533 + _STLP_TRY {
1.534 + if (__elemsafter > difference_type(__n)) {
1.535 + iterator __finish_n = this->_M_finish - difference_type(__n);
1.536 + uninitialized_copy(__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 + copy(__first, __last, __pos);
1.540 + }
1.541 + else {
1.542 + const value_type* __mid = __first + __elemsafter;
1.543 + __uninitialized_copy_copy(__mid, __last, __pos, this->_M_finish, this->_M_finish, _IsPODType());
1.544 + this->_M_finish = __new_finish;
1.545 + copy(__first, __mid, __pos);
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 +}
1.551 +
1.552 +template <class _Tp, class _Alloc >
1.553 +void
1.554 +__deque__<_Tp,_Alloc>::_M_insert_aux(iterator __pos,
1.555 + const_iterator __first,
1.556 + const_iterator __last,
1.557 + size_type __n)
1.558 +{
1.559 + const difference_type __elemsbefore = __pos - this->_M_start;
1.560 + size_type __length = size();
1.561 + if (__elemsbefore < difference_type(__length / 2)) {
1.562 + iterator __new_start = _M_reserve_elements_at_front(__n);
1.563 + iterator __old_start = this->_M_start;
1.564 + __pos = this->_M_start + __elemsbefore;
1.565 + _STLP_TRY {
1.566 + if (__elemsbefore >= difference_type(__n)) {
1.567 + iterator __start_n = this->_M_start + __n;
1.568 + uninitialized_copy(this->_M_start, __start_n, __new_start);
1.569 + this->_M_start = __new_start;
1.570 + copy(__start_n, __pos, __old_start);
1.571 + copy(__first, __last, __pos - difference_type(__n));
1.572 + }
1.573 + else {
1.574 + const_iterator __mid = __first + (__n - __elemsbefore);
1.575 + __uninitialized_copy_copy(this->_M_start, __pos, __first, __mid,
1.576 + __new_start, _IsPODType());
1.577 + this->_M_start = __new_start;
1.578 + copy(__mid, __last, __old_start);
1.579 + }
1.580 + }
1.581 + _STLP_UNWIND(this->_M_destroy_nodes(__new_start._M_node, this->_M_start._M_node));
1.582 + }
1.583 + else {
1.584 + iterator __new_finish = _M_reserve_elements_at_back(__n);
1.585 + iterator __old_finish = this->_M_finish;
1.586 + const difference_type __elemsafter = __length - __elemsbefore;
1.587 + __pos = this->_M_finish - __elemsafter;
1.588 + _STLP_TRY {
1.589 + if (__elemsafter > difference_type(__n)) {
1.590 + iterator __finish_n = this->_M_finish - difference_type(__n);
1.591 + uninitialized_copy(__finish_n, this->_M_finish, this->_M_finish);
1.592 + this->_M_finish = __new_finish;
1.593 + copy_backward(__pos, __finish_n, __old_finish);
1.594 + copy(__first, __last, __pos);
1.595 + }
1.596 + else {
1.597 + const_iterator __mid = __first + __elemsafter;
1.598 + __uninitialized_copy_copy(__mid, __last, __pos, this->_M_finish, this->_M_finish, _IsPODType());
1.599 + this->_M_finish = __new_finish;
1.600 + copy(__first, __mid, __pos);
1.601 + }
1.602 + }
1.603 + _STLP_UNWIND(this->_M_destroy_nodes(this->_M_finish._M_node + 1, __new_finish._M_node + 1));
1.604 + }
1.605 +}
1.606 +
1.607 +#endif /* _STLP_MEMBER_TEMPLATES */
1.608 +
1.609 +template <class _Tp, class _Alloc >
1.610 +void
1.611 +__deque__<_Tp,_Alloc>::_M_new_elements_at_front(size_type __new_elems)
1.612 +{
1.613 + size_type __new_nodes
1.614 + = (__new_elems + this->buffer_size() - 1) / this->buffer_size();
1.615 + _M_reserve_map_at_front(__new_nodes);
1.616 + size_type __i =1;
1.617 + _STLP_TRY {
1.618 + for (; __i <= __new_nodes; ++__i)
1.619 + *(this->_M_start._M_node - __i) = this->_M_map_size.allocate(this->buffer_size());
1.620 + }
1.621 + _STLP_CATCH_ALL {
1.622 + for (size_type __j = 1; __j < __i; ++__j)
1.623 + this->_M_map_size.deallocate(*(this->_M_start._M_node - __j), this->buffer_size());
1.624 + _STLP_RETHROW;
1.625 + }
1.626 +}
1.627 +
1.628 +template <class _Tp, class _Alloc >
1.629 +void
1.630 +__deque__<_Tp,_Alloc>::_M_new_elements_at_back(size_type __new_elems)
1.631 +{
1.632 + size_type __new_nodes
1.633 + = (__new_elems + this->buffer_size() - 1) / this->buffer_size();
1.634 + _M_reserve_map_at_back(__new_nodes);
1.635 + size_type __i = 1;
1.636 + _STLP_TRY {
1.637 + for (; __i <= __new_nodes; ++__i)
1.638 + *(this->_M_finish._M_node + __i) = this->_M_map_size.allocate(this->buffer_size());
1.639 + }
1.640 + _STLP_CATCH_ALL {
1.641 + for (size_type __j = 1; __j < __i; ++__j)
1.642 + this->_M_map_size.deallocate(*(this->_M_finish._M_node + __j), this->buffer_size());
1.643 + _STLP_RETHROW;
1.644 + }
1.645 +}
1.646 +
1.647 +template <class _Tp, class _Alloc >
1.648 +void
1.649 +__deque__<_Tp,_Alloc>::_M_reallocate_map(size_type __nodes_to_add,
1.650 + bool __add_at_front)
1.651 +{
1.652 + size_type __old_num_nodes = this->_M_finish._M_node - this->_M_start._M_node + 1;
1.653 + size_type __new_num_nodes = __old_num_nodes + __nodes_to_add;
1.654 +
1.655 + _Map_pointer __new_nstart;
1.656 + if (this->_M_map_size._M_data > 2 * __new_num_nodes) {
1.657 + __new_nstart = this->_M_map._M_data + (this->_M_map_size._M_data - __new_num_nodes) / 2
1.658 + + (__add_at_front ? __nodes_to_add : 0);
1.659 + if (__new_nstart < this->_M_start._M_node)
1.660 + copy(this->_M_start._M_node, this->_M_finish._M_node + 1, __new_nstart);
1.661 + else
1.662 + copy_backward(this->_M_start._M_node, this->_M_finish._M_node + 1,
1.663 + __new_nstart + __old_num_nodes);
1.664 + }
1.665 + else {
1.666 + size_type __new_map_size =
1.667 + this->_M_map_size._M_data + (max)((size_t)this->_M_map_size._M_data, __nodes_to_add) + 2;
1.668 +
1.669 + _Map_pointer __new_map = this->_M_map.allocate(__new_map_size);
1.670 + __new_nstart = __new_map + (__new_map_size - __new_num_nodes) / 2
1.671 + + (__add_at_front ? __nodes_to_add : 0);
1.672 + copy(this->_M_start._M_node, this->_M_finish._M_node + 1, __new_nstart);
1.673 + this->_M_map.deallocate(this->_M_map._M_data, this->_M_map_size._M_data);
1.674 +
1.675 + this->_M_map._M_data = __new_map;
1.676 + this->_M_map_size._M_data = __new_map_size;
1.677 + }
1.678 +
1.679 + this->_M_start._M_set_node(__new_nstart);
1.680 + this->_M_finish._M_set_node(__new_nstart + __old_num_nodes - 1);
1.681 +}
1.682 +
1.683 +_STLP_END_NAMESPACE
1.684 +
1.685 +# undef __iterator__
1.686 +# undef iterator
1.687 +# undef const_iterator
1.688 +# undef size_type
1.689 +# undef value_type
1.690 +
1.691 +#endif /* _STLP_DEQUE_C */
1.692 +
1.693 +// Local Variables:
1.694 +// mode:C++
1.695 +// End: