include/stlport/stl/_deque.c

   1 /*
   2  *
   3  *
   4  * Copyright (c) 1994
   5  * Hewlett-Packard Company
   6  *
   7  * Copyright (c) 1996,1997
   8  * Silicon Graphics Computer Systems, Inc.
   9  *
  10  * Copyright (c) 1997
  11  * Moscow Center for SPARC Technology
  12  *
  13  * Copyright (c) 1999
  14  * Boris Fomitchev
  15  *
  16  * This material is provided "as is", with absolutely no warranty expressed
  17  * or implied. Any use is at your own risk.
  18  *
  19  * Permission to use or copy this software for any purpose is hereby granted
  20  * without fee, provided the above notices are retained on all copies.
  21  * Permission to modify the code and to distribute modified code is granted,
  22  * provided the above notices are retained, and a notice that the code was
  23  * modified is included with the above copyright notice.
  24  *
  25  */
  26 #ifndef _STLP_DEQUE_C
  27 #define _STLP_DEQUE_C
  28
  29 #ifndef _STLP_INTERNAL_DEQUE_H
  30 #  include <stl/_deque.h>
  31 #endif
  32
  33 _STLP_BEGIN_NAMESPACE
  34
  35 _STLP_MOVE_TO_PRIV_NAMESPACE
  36
  37 // Non-inline member functions from _Deque_base.
  38
  39 template <class _Tp, class _Alloc >
  40 _Deque_base<_Tp,_Alloc >::~_Deque_base() {
  41   if (_M_map._M_data) {
  42     _M_destroy_nodes(_M_start._M_node, this->_M_finish._M_node + 1);
  43     _M_map.deallocate(_M_map._M_data, _M_map_size._M_data);
  44   }
  45 }
  46
  47 template <class _Tp, class _Alloc >
  48 void _Deque_base<_Tp,_Alloc>::_M_initialize_map(size_t __num_elements) {
  49   size_t __num_nodes = __num_elements / this->buffer_size() + 1 ;
  50
  51   _M_map_size._M_data = (max)((size_t) _S_initial_map_size, __num_nodes + 2);
  52   _M_map._M_data = _M_map.allocate(_M_map_size._M_data);
  53
  54   _Tp** __nstart = _M_map._M_data + (_M_map_size._M_data - __num_nodes) / 2;
  55   _Tp** __nfinish = __nstart + __num_nodes;
  56
  57   _STLP_TRY {
  58     _M_create_nodes(__nstart, __nfinish);
  59   }
  60   _STLP_UNWIND((_M_map.deallocate(_M_map._M_data, _M_map_size._M_data),
  61                 _M_map._M_data = 0, _M_map_size._M_data = 0))
  62   _M_start._M_set_node(__nstart);
  63   this->_M_finish._M_set_node(__nfinish - 1);
  64   _M_start._M_cur = _M_start._M_first;
  65   this->_M_finish._M_cur = this->_M_finish._M_first + __num_elements % this->buffer_size();
  66 }
  67
  68 template <class _Tp, class _Alloc >
  69 void _Deque_base<_Tp,_Alloc>::_M_create_nodes(_Tp** __nstart,
  70                                               _Tp** __nfinish) {
  71   _Tp** __cur = __nstart;
  72   _STLP_TRY {
  73     for (; __cur < __nfinish; ++__cur)
  74       *__cur = _M_map_size.allocate(this->buffer_size());
  75   }
  76   _STLP_UNWIND(_M_destroy_nodes(__nstart, __cur))
  77 }
  78
  79 template <class _Tp, class _Alloc >
  80 void _Deque_base<_Tp,_Alloc>::_M_destroy_nodes(_Tp** __nstart,
  81                                                _Tp** __nfinish) {
  82   for (_Tp** __n = __nstart; __n < __nfinish; ++__n)
  83     _M_map_size.deallocate(*__n, this->buffer_size());
  84 }
  85
  86 #if defined (_STLP_USE_PTR_SPECIALIZATIONS)
  87 #  define deque _STLP_PTR_IMPL_NAME(deque)
  88 #elif defined (_STLP_DEBUG)
  89 #  define deque _STLP_NON_DBG_NAME(deque)
  90 #else
  91 _STLP_MOVE_TO_STD_NAMESPACE
  92 #endif
  93
  94 #if defined (_STLP_NESTED_TYPE_PARAM_BUG)
  95 // qualified references
  96 #  define __iterator__   _Deque_iterator<_Tp, _Nonconst_traits<_Tp> >
  97 #  define const_iterator _Deque_iterator<_Tp, _Const_traits<_Tp>  >
  98 #  define iterator       __iterator__
  99 #  define size_type      size_t
 100 #  define value_type     _Tp
 101 #else
 102 #  define __iterator__   _STLP_TYPENAME_ON_RETURN_TYPE deque<_Tp, _Alloc>::iterator
 103 #endif
 104
 105 template <class _Tp, class _Alloc >
 106 deque<_Tp, _Alloc >&
 107 deque<_Tp, _Alloc >::operator= (const deque<_Tp, _Alloc >& __x) {
 108   const size_type __len = size();
 109   if (&__x != this) {
 110     if (__len >= __x.size())
 111       erase(_STLP_STD::copy(__x.begin(), __x.end(), this->_M_start), this->_M_finish);
 112     else {
 113       const_iterator __mid = __x.begin() + difference_type(__len);
 114       _STLP_STD::copy(__x.begin(), __mid, this->_M_start);
 115       insert(this->_M_finish, __mid, __x.end());
 116     }
 117   }
 118   return *this;
 119 }
 120
 121 template <class _Tp, class _Alloc >
 122 void deque<_Tp, _Alloc >::_M_fill_insert(iterator __pos,
 123                                          size_type __n, const value_type& __x) {
 124 #if !defined (_STLP_NO_MOVE_SEMANTIC)
 125   typedef typename __move_traits<_Tp>::implemented _Movable;
 126 #endif
 127   if (__pos._M_cur == this->_M_start._M_cur) {
 128     iterator __new_start = _M_reserve_elements_at_front(__n);
 129     _STLP_TRY {
 130       uninitialized_fill(__new_start, this->_M_start, __x);
 131     }
 132     _STLP_UNWIND(this->_M_destroy_nodes(__new_start._M_node, this->_M_start._M_node))
 133     this->_M_start = __new_start;
 134   }
 135   else if (__pos._M_cur == this->_M_finish._M_cur) {
 136     iterator __new_finish = _M_reserve_elements_at_back(__n);
 137     _STLP_TRY {
 138       uninitialized_fill(this->_M_finish, __new_finish, __x);
 139     }
 140     _STLP_UNWIND(this->_M_destroy_nodes(this->_M_finish._M_node+1, __new_finish._M_node+1))
 141     this->_M_finish = __new_finish;
 142   }
 143   else
 144     _M_fill_insert_aux(__pos, __n, __x, _Movable());
 145 }
 146
 147 #if !defined (_STLP_MEMBER_TEMPLATES)
 148
 149 template <class _Tp, class _Alloc >
 150 void deque<_Tp, _Alloc>::insert(iterator __pos,
 151                                 const value_type* __first, const value_type* __last) {
 152 #if !defined (_STLP_NO_MOVE_SEMANTIC)
 153   typedef typename __move_traits<_Tp>::implemented _Movable;
 154 #endif
 155   size_type __n = __last - __first;
 156   if (__pos._M_cur == this->_M_start._M_cur) {
 157     iterator __new_start = _M_reserve_elements_at_front(__n);
 158     _STLP_TRY {
 159       _STLP_PRIV __ucopy(__first, __last, __new_start);
 160     }
 161     _STLP_UNWIND(this->_M_destroy_nodes(__new_start._M_node, this->_M_start._M_node))
 162     this->_M_start = __new_start;
 163   }
 164   else if (__pos._M_cur == this->_M_finish._M_cur) {
 165     iterator __new_finish = _M_reserve_elements_at_back(__n);
 166     _STLP_TRY {
 167       _STLP_PRIV __ucopy(__first, __last, this->_M_finish);
 168     }
 169     _STLP_UNWIND(this->_M_destroy_nodes(this->_M_finish._M_node + 1,
 170                                         __new_finish._M_node + 1))
 171     this->_M_finish = __new_finish;
 172   }
 173   else
 174     _M_insert_range_aux(__pos, __first, __last, __n, _Movable());
 175 }
 176
 177 template <class _Tp, class _Alloc >
 178 void deque<_Tp,_Alloc>::insert(iterator __pos,
 179                                const_iterator __first, const_iterator __last) {
 180 #if !defined (_STLP_NO_MOVE_SEMANTIC)
 181   typedef typename __move_traits<_Tp>::implemented _Movable;
 182 #endif
 183   size_type __n = __last - __first;
 184   if (__pos._M_cur == this->_M_start._M_cur) {
 185     iterator __new_start = _M_reserve_elements_at_front(__n);
 186     _STLP_TRY {
 187       _STLP_PRIV __ucopy(__first, __last, __new_start);
 188     }
 189     _STLP_UNWIND(this->_M_destroy_nodes(__new_start._M_node, this->_M_start._M_node))
 190     this->_M_start = __new_start;
 191   }
 192   else if (__pos._M_cur == this->_M_finish._M_cur) {
 193     iterator __new_finish = _M_reserve_elements_at_back(__n);
 194     _STLP_TRY {
 195       _STLP_PRIV __ucopy(__first, __last, this->_M_finish);
 196     }
 197     _STLP_UNWIND(this->_M_destroy_nodes(this->_M_finish._M_node + 1,
 198                                         __new_finish._M_node + 1))
 199     this->_M_finish = __new_finish;
 200   }
 201   else
 202     _M_insert_range_aux(__pos, __first, __last, __n, _Movable());
 203 }
 204
 205 #endif /* _STLP_MEMBER_TEMPLATES */
 206
 207 template <class _Tp, class _Alloc >
 208 __iterator__ deque<_Tp,_Alloc>::_M_erase(iterator __pos,
 209                                          const __true_type& /*_Movable*/) {
 210   difference_type __index = __pos - this->_M_start;
 211   if (size_type(__index) < this->size() >> 1) {
 212     //We move the start of the deque one position to the right
 213     //starting from the rightmost element to move.
 214     iterator __src = __pos, __dst = __pos;
 215     _STLP_STD::_Destroy(&(*__dst));
 216     if (__src != this->_M_start) {
 217       for (--__src; __dst != this->_M_start; --__src, --__dst) {
 218         _STLP_STD::_Move_Construct(&(*__dst), *__src);
 219         _STLP_STD::_Destroy_Moved(&(*__src));
 220       }
 221     }
 222     _M_pop_front_aux();
 223   }
 224   else {
 225     iterator __src = __pos, __dst = __pos;
 226     _STLP_STD::_Destroy(&(*__dst));
 227     for (++__src; __src != this->_M_finish; ++__src, ++__dst) {
 228       _STLP_STD::_Move_Construct(&(*__dst), *__src);
 229       _STLP_STD::_Destroy_Moved(&(*__src));
 230     }
 231     //Duplication of the pop_back code without the destroy which has already been done:
 232     if (this->_M_finish._M_cur != this->_M_finish._M_first) {
 233       --this->_M_finish._M_cur;
 234     }
 235     else {
 236       _M_pop_back_aux();
 237     }
 238   }
 239   return this->_M_start + __index;
 240 }
 241
 242 template <class _Tp, class _Alloc >
 243 __iterator__ deque<_Tp,_Alloc>::_M_erase(iterator __pos,
 244                                          const __false_type& /*_Movable*/) {
 245   iterator __next = __pos;
 246   ++__next;
 247   difference_type __index = __pos - this->_M_start;
 248   if (size_type(__index) < this->size() >> 1) {
 249     copy_backward(this->_M_start, __pos, __next);
 250     pop_front();
 251   }
 252   else {
 253     _STLP_STD::copy(__next, this->_M_finish, __pos);
 254     pop_back();
 255   }
 256   return this->_M_start + __index;
 257 }
 258
 259 template <class _Tp, class _Alloc >
 260 __iterator__ deque<_Tp,_Alloc>::_M_erase(iterator __first, iterator __last,
 261                                          const __true_type& /*_Movable*/) {
 262   difference_type __n = __last - __first;
 263   difference_type __elems_before = __first - this->_M_start;
 264   if (__elems_before <= difference_type(this->size() - __n) / 2) {
 265     iterator __src = __first, __dst = __last;
 266     if (__src != this->_M_start) {
 267       for (--__src, --__dst; (__src >= this->_M_start) && (__dst >= __first); --__src, --__dst) {
 268         _STLP_STD::_Destroy(&(*__dst));
 269         _STLP_STD::_Move_Construct(&(*__dst), *__src);
 270       }
 271       if (__dst >= __first) {
 272         //There are more elements to erase than elements to move
 273         _STLP_STD::_Destroy_Range(__first, ++__dst);
 274         _STLP_STD::_Destroy_Moved_Range(this->_M_start, __first);
 275       }
 276       else {
 277         //There are more elements to move than elements to erase
 278         for (; __src >= this->_M_start; --__src, --__dst) {
 279           _STLP_STD::_Destroy_Moved(&(*__dst));
 280           _STLP_STD::_Move_Construct(&(*__dst), *__src);
 281         }
 282         _STLP_STD::_Destroy_Moved_Range(this->_M_start, ++__dst);
 283       }
 284     }
 285     else {
 286       _STLP_STD::_Destroy_Range(this->_M_start, __last);
 287     }
 288     iterator __new_start = this->_M_start + __n;
 289     this->_M_destroy_nodes(this->_M_start._M_node, __new_start._M_node);
 290     this->_M_start = __new_start;
 291   }
 292   else {
 293     if (__last != this->_M_finish) {
 294       iterator __src = __last, __dst = __first;
 295       for (; (__src != this->_M_finish) && (__dst != __last); ++__src, ++__dst) {
 296         _STLP_STD::_Destroy(&(*__dst));
 297         _STLP_STD::_Move_Construct(&(*__dst), *__src);
 298       }
 299       if (__dst != __last) {
 300         //There are more elements to erase than elements to move
 301         _STLP_STD::_Destroy_Range(__dst, __last);
 302         _STLP_STD::_Destroy_Moved_Range(__last, this->_M_finish);
 303       }
 304       else {
 305         //There are more elements to move than elements to erase
 306         for (; __src != this->_M_finish; ++__src, ++__dst) {
 307           _STLP_STD::_Destroy_Moved(&(*__dst));
 308           _STLP_STD::_Move_Construct(&(*__dst), *__src);
 309         }
 310         _STLP_STD::_Destroy_Moved_Range(__dst, this->_M_finish);
 311       }
 312     }
 313     else {
 314       _STLP_STD::_Destroy_Range(__first, this->_M_finish);
 315     }
 316     iterator __new_finish = this->_M_finish - __n;
 317     this->_M_destroy_nodes(__new_finish._M_node + 1, this->_M_finish._M_node + 1);
 318     this->_M_finish = __new_finish;
 319   }
 320   return this->_M_start + __elems_before;
 321 }
 322
 323 template <class _Tp, class _Alloc >
 324 __iterator__ deque<_Tp,_Alloc>::_M_erase(iterator __first, iterator __last,
 325                                          const __false_type& /*_Movable*/) {
 326   difference_type __n = __last - __first;
 327   difference_type __elems_before = __first - this->_M_start;
 328   if (__elems_before <= difference_type(this->size() - __n) / 2) {
 329     copy_backward(this->_M_start, __first, __last);
 330     iterator __new_start = this->_M_start + __n;
 331     _STLP_STD::_Destroy_Range(this->_M_start, __new_start);
 332     this->_M_destroy_nodes(this->_M_start._M_node, __new_start._M_node);
 333     this->_M_start = __new_start;
 334   }
 335   else {
 336     _STLP_STD::copy(__last, this->_M_finish, __first);
 337     iterator __new_finish = this->_M_finish - __n;
 338     _STLP_STD::_Destroy_Range(__new_finish, this->_M_finish);
 339     this->_M_destroy_nodes(__new_finish._M_node + 1, this->_M_finish._M_node + 1);
 340     this->_M_finish = __new_finish;
 341   }
 342   return this->_M_start + __elems_before;
 343 }
 344
 345 template <class _Tp, class _Alloc >
 346 void deque<_Tp,_Alloc>::clear() {
 347   for (_Map_pointer __node = this->_M_start._M_node + 1;
 348        __node < this->_M_finish._M_node;
 349        ++__node) {
 350     _STLP_STD::_Destroy_Range(*__node, *__node + this->buffer_size());
 351     this->_M_map_size.deallocate(*__node, this->buffer_size());
 352   }
 353
 354   if (this->_M_start._M_node != this->_M_finish._M_node) {
 355     _STLP_STD::_Destroy_Range(this->_M_start._M_cur, this->_M_start._M_last);
 356     _STLP_STD::_Destroy_Range(this->_M_finish._M_first, this->_M_finish._M_cur);
 357     this->_M_map_size.deallocate(this->_M_finish._M_first, this->buffer_size());
 358   }
 359   else
 360     _STLP_STD::_Destroy_Range(this->_M_start._M_cur, this->_M_finish._M_cur);
 361
 362   this->_M_finish = this->_M_start;
 363 }
 364
 365 // Precondition: this->_M_start and this->_M_finish have already been initialized,
 366 // but none of the deque's elements have yet been constructed.
 367 template <class _Tp, class _Alloc >
 368 void deque<_Tp,_Alloc>::_M_fill_initialize(const value_type& __val,
 369                                            const __false_type& /*_TrivialInit*/) {
 370   _Map_pointer __cur = this->_M_start._M_node;
 371   _STLP_TRY {
 372     for (; __cur < this->_M_finish._M_node; ++__cur)
 373       uninitialized_fill(*__cur, *__cur + this->buffer_size(), __val);
 374     uninitialized_fill(this->_M_finish._M_first, this->_M_finish._M_cur, __val);
 375   }
 376   _STLP_UNWIND(_STLP_STD::_Destroy_Range(this->_M_start, iterator(*__cur, __cur)))
 377 }
 378
 379
 380 // Called only if this->_M_finish._M_cur == this->_M_finish._M_last - 1.
 381 template <class _Tp, class _Alloc >
 382 void deque<_Tp,_Alloc>::_M_push_back_aux_v(const value_type& __t) {
 383   _M_reserve_map_at_back();
 384   *(this->_M_finish._M_node + 1) = this->_M_map_size.allocate(this->buffer_size());
 385   _STLP_TRY {
 386     _Copy_Construct(this->_M_finish._M_cur, __t);
 387     this->_M_finish._M_set_node(this->_M_finish._M_node + 1);
 388     this->_M_finish._M_cur = this->_M_finish._M_first;
 389   }
 390   _STLP_UNWIND(this->_M_map_size.deallocate(*(this->_M_finish._M_node + 1),
 391                                             this->buffer_size()))
 392 }
 393
 394 #if defined(_STLP_DONT_SUP_DFLT_PARAM) && !defined(_STLP_NO_ANACHRONISMS)
 395 // Called only if this->_M_finish._M_cur == this->_M_finish._M_last - 1.
 396 template <class _Tp, class _Alloc >
 397 void deque<_Tp,_Alloc>::_M_push_back_aux() {
 398   _M_reserve_map_at_back();
 399   *(this->_M_finish._M_node + 1) = this->_M_map_size.allocate(this->buffer_size());
 400   _STLP_TRY {
 401     _STLP_STD::_Construct(this->_M_finish._M_cur);
 402     this->_M_finish._M_set_node(this->_M_finish._M_node + 1);
 403     this->_M_finish._M_cur = this->_M_finish._M_first;
 404   }
 405   _STLP_UNWIND(this->_M_map_size.deallocate(*(this->_M_finish._M_node + 1),
 406                                             this->buffer_size()))
 407 }
 408 #endif /*_STLP_DONT_SUP_DFLT_PARAM && !_STLP_NO_ANACHRONISMS*/
 409
 410 // Called only if this->_M_start._M_cur == this->_M_start._M_first.
 411 template <class _Tp, class _Alloc >
 412 void deque<_Tp,_Alloc>::_M_push_front_aux_v(const value_type& __t) {
 413   _M_reserve_map_at_front();
 414   *(this->_M_start._M_node - 1) = this->_M_map_size.allocate(this->buffer_size());
 415   _STLP_TRY {
 416     this->_M_start._M_set_node(this->_M_start._M_node - 1);
 417     this->_M_start._M_cur = this->_M_start._M_last - 1;
 418     _Copy_Construct(this->_M_start._M_cur, __t);
 419   }
 420   _STLP_UNWIND((++this->_M_start,
 421                 this->_M_map_size.deallocate(*(this->_M_start._M_node - 1), this->buffer_size())))
 422 }
 423
 424
 425 #if defined (_STLP_DONT_SUP_DFLT_PARAM) && !defined (_STLP_NO_ANACHRONISMS)
 426 // Called only if this->_M_start._M_cur == this->_M_start._M_first.
 427 template <class _Tp, class _Alloc >
 428 void deque<_Tp,_Alloc>::_M_push_front_aux() {
 429   _M_reserve_map_at_front();
 430   *(this->_M_start._M_node - 1) = this->_M_map_size.allocate(this->buffer_size());
 431   _STLP_TRY {
 432     this->_M_start._M_set_node(this->_M_start._M_node - 1);
 433     this->_M_start._M_cur = this->_M_start._M_last - 1;
 434     _STLP_STD::_Construct(this->_M_start._M_cur);
 435   }
 436   _STLP_UNWIND((++this->_M_start, this->_M_map_size.deallocate(*(this->_M_start._M_node - 1),
 437                                                                this->buffer_size())))
 438 }
 439 #endif /*_STLP_DONT_SUP_DFLT_PARAM && !_STLP_NO_ANACHRONISMS*/
 440
 441 // Called only if this->_M_finish._M_cur == this->_M_finish._M_first.
 442 template <class _Tp, class _Alloc >
 443 void deque<_Tp,_Alloc>::_M_pop_back_aux() {
 444   this->_M_map_size.deallocate(this->_M_finish._M_first, this->buffer_size());
 445   this->_M_finish._M_set_node(this->_M_finish._M_node - 1);
 446   this->_M_finish._M_cur = this->_M_finish._M_last - 1;
 447 }
 448
 449 // Note that if the deque has at least one element (a precondition for this member
 450 // function), and if this->_M_start._M_cur == this->_M_start._M_last, then the deque
 451 // must have at least two nodes.
 452 template <class _Tp, class _Alloc >
 453 void deque<_Tp,_Alloc>::_M_pop_front_aux() {
 454   if (this->_M_start._M_cur != this->_M_start._M_last - 1)
 455     ++this->_M_start._M_cur;
 456   else {
 457     this->_M_map_size.deallocate(this->_M_start._M_first, this->buffer_size());
 458     this->_M_start._M_set_node(this->_M_start._M_node + 1);
 459     this->_M_start._M_cur = this->_M_start._M_first;
 460   }
 461 }
 462
 463 template <class _Tp, class _Alloc >
 464 __iterator__ deque<_Tp,_Alloc>::_M_fill_insert_aux(iterator __pos, size_type __n,
 465                                                    const value_type& __x,
 466                                                    const __true_type& /*_Movable*/) {
 467   const difference_type __elems_before = __pos - this->_M_start;
 468   size_type __length = this->size();
 469   value_type __x_copy = __x;
 470   if (__elems_before <= difference_type(__length / 2)) {
 471     iterator __new_start = _M_reserve_elements_at_front(__n);
 472     __pos = this->_M_start + __elems_before;
 473     _STLP_TRY {
 474       iterator __dst = __new_start;
 475       iterator __src = this->_M_start;
 476       for (; __src != __pos; ++__dst, ++__src) {
 477         _STLP_STD::_Move_Construct(&(*__dst), *__src);
 478         _STLP_STD::_Destroy_Moved(&(*__src));
 479       }
 480       this->_M_start = __new_start;
 481       uninitialized_fill(__dst, __src, __x_copy);
 482       __pos = __dst;
 483     }
 484     _STLP_UNWIND(this->_M_destroy_nodes(__new_start._M_node, this->_M_start._M_node))
 485   }
 486   else {
 487     iterator __new_finish = _M_reserve_elements_at_back(__n);
 488     const difference_type __elems_after = difference_type(__length) - __elems_before;
 489     __pos = this->_M_finish - __elems_after;
 490     _STLP_TRY {
 491       iterator __dst = __new_finish;
 492       iterator __src = this->_M_finish;
 493       for (--__src, --__dst; __src >= __pos; --__src, --__dst) {
 494         _STLP_STD::_Move_Construct(&(*__dst), *__src);
 495         _STLP_STD::_Destroy_Moved(&(*__src));
 496       }
 497       this->_M_finish = __new_finish;
 498       uninitialized_fill(__pos, __pos + __n, __x_copy);
 499     }
 500     _STLP_UNWIND(this->_M_destroy_nodes(this->_M_finish._M_node + 1, __new_finish._M_node + 1))
 501   }
 502   return __pos;
 503 }
 504
 505 template <class _Tp, class _Alloc >
 506 __iterator__ deque<_Tp,_Alloc>::_M_fill_insert_aux(iterator __pos, size_type __n,
 507                                                    const value_type& __x,
 508                                                    const __false_type& /*_Movable*/) {
 509   const difference_type __elems_before = __pos - this->_M_start;
 510   size_type __length = this->size();
 511   value_type __x_copy = __x;
 512   if (__elems_before <= difference_type(__length / 2)) {
 513     iterator __new_start = _M_reserve_elements_at_front(__n);
 514     iterator __old_start = this->_M_start;
 515     __pos = this->_M_start + __elems_before;
 516     _STLP_TRY {
 517       if (__elems_before >= difference_type(__n)) {
 518         iterator __start_n = this->_M_start + difference_type(__n);
 519         _STLP_PRIV __ucopy(this->_M_start, __start_n, __new_start);
 520         this->_M_start = __new_start;
 521         _STLP_STD::copy(__start_n, __pos, __old_start);
 522         _STLP_STD::fill(__pos - difference_type(__n), __pos, __x_copy);
 523         __pos -= difference_type(__n);
 524       }
 525       else {
 526         _STLP_PRIV __uninitialized_copy_fill(this->_M_start, __pos, __new_start,
 527                                              this->_M_start, __x_copy);
 528         this->_M_start = __new_start;
 529         fill(__old_start, __pos, __x_copy);
 530       }
 531     }
 532     _STLP_UNWIND(this->_M_destroy_nodes(__new_start._M_node, this->_M_start._M_node))
 533   }
 534   else {
 535     iterator __new_finish = _M_reserve_elements_at_back(__n);
 536     iterator __old_finish = this->_M_finish;
 537     const difference_type __elems_after =
 538       difference_type(__length) - __elems_before;
 539     __pos = this->_M_finish - __elems_after;
 540     _STLP_TRY {
 541       if (__elems_after > difference_type(__n)) {
 542         iterator __finish_n = this->_M_finish - difference_type(__n);
 543         _STLP_PRIV __ucopy(__finish_n, this->_M_finish, this->_M_finish);
 544         this->_M_finish = __new_finish;
 545         copy_backward(__pos, __finish_n, __old_finish);
 546         fill(__pos, __pos + difference_type(__n), __x_copy);
 547       }
 548       else {
 549         _STLP_PRIV __uninitialized_fill_copy(this->_M_finish, __pos + difference_type(__n),
 550                                              __x_copy, __pos, this->_M_finish);
 551         this->_M_finish = __new_finish;
 552         fill(__pos, __old_finish, __x_copy);
 553       }
 554     }
 555     _STLP_UNWIND(this->_M_destroy_nodes(this->_M_finish._M_node + 1, __new_finish._M_node + 1))
 556   }
 557   return __pos;
 558 }
 559
 560 #if !defined (_STLP_MEMBER_TEMPLATES)
 561 template <class _Tp, class _Alloc >
 562 void deque<_Tp,_Alloc>::_M_insert_range_aux(iterator __pos,
 563                                             const value_type* __first, const value_type* __last,
 564                                             size_type __n, const __true_type& /*_Movable*/) {
 565   const difference_type __elems_before = __pos - this->_M_start;
 566   size_type __length = size();
 567   if (__elems_before <= difference_type(__length / 2)) {
 568     iterator __new_start = _M_reserve_elements_at_front(__n);
 569     __pos = this->_M_start + __elems_before;
 570     _STLP_TRY {
 571       iterator __dst = __new_start;
 572       iterator __src = this->_M_start;
 573       for (; __src != __pos; ++__dst, ++__src) {
 574         _STLP_STD::_Move_Construct(&(*__dst), *__src);
 575         _STLP_STD::_Destroy_Moved(&(*__src));
 576       }
 577       this->_M_start = __new_start;
 578       _STLP_PRIV __ucopy(__first, __last, __dst);
 579     }
 580     _STLP_UNWIND(this->_M_destroy_nodes(__new_start._M_node, this->_M_start._M_node))
 581   }
 582   else {
 583     iterator __new_finish = _M_reserve_elements_at_back(__n);
 584     const difference_type __elems_after = difference_type(__length) - __elems_before;
 585     __pos = this->_M_finish - __elems_after;
 586     _STLP_TRY {
 587       iterator __dst = __new_finish;
 588       iterator __src = this->_M_finish;
 589       for (--__src, --__dst; __src >= __pos; --__src, --__dst) {
 590         _STLP_STD::_Move_Construct(&(*__dst), *__src);
 591         _STLP_STD::_Destroy_Moved(&(*__src));
 592       }
 593       this->_M_finish = __new_finish;
 594       _STLP_PRIV __ucopy(__first, __last, __pos);
 595     }
 596     _STLP_UNWIND(this->_M_destroy_nodes(this->_M_finish._M_node + 1, __new_finish._M_node + 1))
 597   }
 598 }
 599
 600 template <class _Tp, class _Alloc >
 601 void deque<_Tp,_Alloc>::_M_insert_range_aux(iterator __pos,
 602                                             const value_type* __first, const value_type* __last,
 603                                             size_type __n, const __false_type& /*_Movable*/) {
 604   const difference_type __elems_before = __pos - this->_M_start;
 605   size_type __length = size();
 606   if (__elems_before <= difference_type(__length / 2)) {
 607     iterator __new_start = _M_reserve_elements_at_front(__n);
 608     iterator __old_start = this->_M_start;
 609     __pos = this->_M_start + __elems_before;
 610     _STLP_TRY {
 611       if (__elems_before >= difference_type(__n)) {
 612         iterator __start_n = this->_M_start + difference_type(__n);
 613         _STLP_PRIV __ucopy(this->_M_start, __start_n, __new_start);
 614         this->_M_start = __new_start;
 615         _STLP_STD::copy(__start_n, __pos, __old_start);
 616         _STLP_STD::copy(__first, __last, __pos - difference_type(__n));
 617       }
 618       else {
 619         const value_type* __mid = __first + (difference_type(__n) - __elems_before);
 620         _STLP_PRIV __uninitialized_copy_copy(this->_M_start, __pos, __first, __mid, __new_start);
 621         this->_M_start = __new_start;
 622         _STLP_STD::copy(__mid, __last, __old_start);
 623       }
 624     }
 625     _STLP_UNWIND(this->_M_destroy_nodes(__new_start._M_node, this->_M_start._M_node))
 626   }
 627   else {
 628     iterator __new_finish = _M_reserve_elements_at_back(__n);
 629     iterator __old_finish = this->_M_finish;
 630     const difference_type __elems_after =
 631       difference_type(__length) - __elems_before;
 632     __pos = this->_M_finish - __elems_after;
 633     _STLP_TRY {
 634
 635       if (__elems_after > difference_type(__n)) {
 636         iterator __finish_n = this->_M_finish - difference_type(__n);
 637         _STLP_PRIV __ucopy(__finish_n, this->_M_finish, this->_M_finish);
 638         this->_M_finish = __new_finish;
 639         _STLP_STD::copy_backward(__pos, __finish_n, __old_finish);
 640         _STLP_STD::copy(__first, __last, __pos);
 641       }
 642       else {
 643         const value_type* __mid = __first + __elems_after;
 644         _STLP_PRIV __uninitialized_copy_copy(__mid, __last, __pos, this->_M_finish, this->_M_finish);
 645         this->_M_finish = __new_finish;
 646         _STLP_STD::copy(__first, __mid, __pos);
 647       }
 648     }
 649     _STLP_UNWIND(this->_M_destroy_nodes(this->_M_finish._M_node + 1, __new_finish._M_node + 1))
 650   }
 651 }
 652
 653 template <class _Tp, class _Alloc >
 654 void deque<_Tp,_Alloc>::_M_insert_range_aux(iterator __pos,
 655                                             const_iterator __first, const_iterator __last,
 656                                             size_type __n, const __true_type& /*_Movable*/) {
 657   const difference_type __elems_before = __pos - this->_M_start;
 658   size_type __length = size();
 659   if (__elems_before <= difference_type(__length / 2)) {
 660     iterator __new_start = _M_reserve_elements_at_front(__n);
 661     __pos = this->_M_start + __elems_before;
 662     _STLP_TRY {
 663       iterator __dst = __new_start;
 664       iterator __src = this->_M_start;
 665       for (; __src != __pos; ++__dst, ++__src) {
 666         _STLP_STD::_Move_Construct(&(*__dst), *__src);
 667         _STLP_STD::_Destroy_Moved(&(*__src));
 668       }
 669       this->_M_start = __new_start;
 670       _STLP_PRIV __ucopy(__first, __last, __dst);
 671     }
 672     _STLP_UNWIND(this->_M_destroy_nodes(__new_start._M_node, this->_M_start._M_node))
 673   }
 674   else {
 675     iterator __new_finish = _M_reserve_elements_at_back(__n);
 676     const difference_type __elems_after = difference_type(__length) - __elems_before;
 677     __pos = this->_M_finish - __elems_after;
 678     _STLP_TRY {
 679       iterator __dst = __new_finish;
 680       iterator __src = this->_M_finish;
 681       for (--__src, --__dst; __src >= __pos; --__src, --__dst) {
 682         _STLP_STD::_Move_Construct(&(*__dst), *__src);
 683         _STLP_STD::_Destroy_Moved(&(*__src));
 684       }
 685       this->_M_finish = __new_finish;
 686       _STLP_PRIV __ucopy(__first, __last, __pos);
 687     }
 688     _STLP_UNWIND(this->_M_destroy_nodes(this->_M_finish._M_node + 1, __new_finish._M_node + 1))
 689   }
 690 }
 691
 692 template <class _Tp, class _Alloc >
 693 void deque<_Tp,_Alloc>::_M_insert_range_aux(iterator __pos,
 694                                             const_iterator __first, const_iterator __last,
 695                                             size_type __n, const __false_type& /*_Movable*/) {
 696   const difference_type __elems_before = __pos - this->_M_start;
 697   size_type __length = size();
 698   if (__elems_before < difference_type(__length / 2)) {
 699     iterator __new_start = _M_reserve_elements_at_front(__n);
 700     iterator __old_start = this->_M_start;
 701     __pos = this->_M_start + __elems_before;
 702     _STLP_TRY {
 703       if (__elems_before >= difference_type(__n)) {
 704         iterator __start_n = this->_M_start + __n;
 705         _STLP_PRIV __ucopy(this->_M_start, __start_n, __new_start);
 706         this->_M_start = __new_start;
 707         _STLP_STD::copy(__start_n, __pos, __old_start);
 708         _STLP_STD::copy(__first, __last, __pos - difference_type(__n));
 709       }
 710       else {
 711         const_iterator __mid = __first + (__n - __elems_before);
 712         _STLP_PRIV __uninitialized_copy_copy(this->_M_start, __pos, __first, __mid, __new_start);
 713         this->_M_start = __new_start;
 714         _STLP_STD::copy(__mid, __last, __old_start);
 715       }
 716     }
 717     _STLP_UNWIND(this->_M_destroy_nodes(__new_start._M_node, this->_M_start._M_node))
 718   }
 719   else {
 720     iterator __new_finish = _M_reserve_elements_at_back(__n);
 721     iterator __old_finish = this->_M_finish;
 722     const difference_type __elems_after = __length - __elems_before;
 723     __pos = this->_M_finish - __elems_after;
 724     _STLP_TRY {
 725       if (__elems_after > difference_type(__n)) {
 726         iterator __finish_n = this->_M_finish - difference_type(__n);
 727         _STLP_PRIV __ucopy(__finish_n, this->_M_finish, this->_M_finish);
 728         this->_M_finish = __new_finish;
 729         _STLP_STD::copy_backward(__pos, __finish_n, __old_finish);
 730         _STLP_STD::copy(__first, __last, __pos);
 731       }
 732       else {
 733         const_iterator __mid = __first + __elems_after;
 734         _STLP_PRIV __uninitialized_copy_copy(__mid, __last, __pos, this->_M_finish, this->_M_finish);
 735         this->_M_finish = __new_finish;
 736         _STLP_STD::copy(__first, __mid, __pos);
 737       }
 738     }
 739     _STLP_UNWIND(this->_M_destroy_nodes(this->_M_finish._M_node + 1, __new_finish._M_node + 1))
 740   }
 741 }
 742 #endif /* _STLP_MEMBER_TEMPLATES */
 743
 744 template <class _Tp, class _Alloc >
 745 void deque<_Tp,_Alloc>::_M_new_elements_at_front(size_type __new_elems) {
 746   size_type __new_nodes
 747       = (__new_elems + this->buffer_size() - 1) / this->buffer_size();
 748   _M_reserve_map_at_front(__new_nodes);
 749   size_type __i = 1;
 750   _STLP_TRY {
 751     for (; __i <= __new_nodes; ++__i)
 752       *(this->_M_start._M_node - __i) = this->_M_map_size.allocate(this->buffer_size());
 753   }
 754   _STLP_UNWIND(for (size_type __j = 1; __j < __i; ++__j)
 755                  this->_M_map_size.deallocate(*(this->_M_start._M_node - __j), this->buffer_size()))
 756 }
 757
 758 template <class _Tp, class _Alloc >
 759 void deque<_Tp,_Alloc>::_M_new_elements_at_back(size_type __new_elems) {
 760   size_type __new_nodes
 761       = (__new_elems + this->buffer_size() - 1) / this->buffer_size();
 762   _M_reserve_map_at_back(__new_nodes);
 763   size_type __i = 1;
 764   _STLP_TRY {
 765     for (; __i <= __new_nodes; ++__i)
 766       *(this->_M_finish._M_node + __i) = this->_M_map_size.allocate(this->buffer_size());
 767   }
 768   _STLP_UNWIND(for (size_type __j = 1; __j < __i; ++__j)
 769                  this->_M_map_size.deallocate(*(this->_M_finish._M_node + __j), this->buffer_size()))
 770 }
 771
 772 template <class _Tp, class _Alloc >
 773 void deque<_Tp,_Alloc>::_M_reallocate_map(size_type __nodes_to_add,
 774                                           bool __add_at_front) {
 775   size_type __old_num_nodes = this->_M_finish._M_node - this->_M_start._M_node + 1;
 776   size_type __new_num_nodes = __old_num_nodes + __nodes_to_add;
 777
 778   _Map_pointer __new_nstart;
 779   if (this->_M_map_size._M_data > 2 * __new_num_nodes) {
 780     __new_nstart = this->_M_map._M_data + (this->_M_map_size._M_data - __new_num_nodes) / 2
 781                      + (__add_at_front ? __nodes_to_add : 0);
 782     if (__new_nstart < this->_M_start._M_node)
 783       _STLP_STD::copy(this->_M_start._M_node, this->_M_finish._M_node + 1, __new_nstart);
 784     else
 785       _STLP_STD::copy_backward(this->_M_start._M_node, this->_M_finish._M_node + 1,
 786                                __new_nstart + __old_num_nodes);
 787   }
 788   else {
 789     size_type __new_map_size =
 790       this->_M_map_size._M_data + (max)((size_t)this->_M_map_size._M_data, __nodes_to_add) + 2;
 791
 792     _Map_pointer __new_map = this->_M_map.allocate(__new_map_size);
 793     __new_nstart = __new_map + (__new_map_size - __new_num_nodes) / 2
 794                              + (__add_at_front ? __nodes_to_add : 0);
 795     _STLP_STD::copy(this->_M_start._M_node, this->_M_finish._M_node + 1, __new_nstart);
 796     this->_M_map.deallocate(this->_M_map._M_data, this->_M_map_size._M_data);
 797
 798     this->_M_map._M_data = __new_map;
 799     this->_M_map_size._M_data = __new_map_size;
 800   }
 801
 802   this->_M_start._M_set_node(__new_nstart);
 803   this->_M_finish._M_set_node(__new_nstart + __old_num_nodes - 1);
 804 }
 805
 806 #if defined (deque)
 807 #  undef deque
 808 _STLP_MOVE_TO_STD_NAMESPACE
 809 #endif
 810
 811 _STLP_END_NAMESPACE
 812
 813 #undef __iterator__
 814 #undef iterator
 815 #undef const_iterator
 816 #undef size_type
 817 #undef value_type
 818
 819 #endif /*  _STLP_DEQUE_C */
 820
 821 // Local Variables:
 822 // mode:C++
 823 // End: