1.1 --- a/epoc32/include/stdapis/stlport/stl/_deque.c Tue Mar 16 16:12:26 2010 +0000
1.2 +++ /dev/null Thu Jan 01 00:00:00 1970 +0000
1.3 @@ -1,691 +0,0 @@
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: