epoc32/include/stdapis/stlport/stl/_deque.c
branchSymbian2
changeset 2 2fe1408b6811
parent 0 061f57f2323e
     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: