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