include/c++/stl/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(copy(__x.begin(), __x.end(), this->_M_start), this->_M_finish);
 112     else {
 113       const_iterator __mid = __x.begin() + difference_type(__len);
 114       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 (__pos._M_cur == this->_M_start._M_cur) {
 125     iterator __new_start = _M_reserve_elements_at_front(__n);
 126     _STLP_TRY {
 127       uninitialized_fill(__new_start, this->_M_start, __x);
 128     }
 129     _STLP_UNWIND(this->_M_destroy_nodes(__new_start._M_node, this->_M_start._M_node))
 130     this->_M_start = __new_start;
 131   }
 132   else if (__pos._M_cur == this->_M_finish._M_cur) {
 133     iterator __new_finish = _M_reserve_elements_at_back(__n);
 134     _STLP_TRY {
 135       uninitialized_fill(this->_M_finish, __new_finish, __x);
 136     }
 137     _STLP_UNWIND(this->_M_destroy_nodes(this->_M_finish._M_node+1, __new_finish._M_node+1))
 138     this->_M_finish = __new_finish;
 139   }
 140   else
 141     _M_fill_insert_aux(__pos, __n, __x, _Movable());
 142 }
 143
 144 #if !defined (_STLP_MEMBER_TEMPLATES)
 145
 146 template <class _Tp, class _Alloc >
 147 void deque<_Tp, _Alloc>::insert(iterator __pos,
 148                                 const value_type* __first, const value_type* __last) {
 149   size_type __n = __last - __first;
 150   if (__pos._M_cur == this->_M_start._M_cur) {
 151     iterator __new_start = _M_reserve_elements_at_front(__n);
 152     _STLP_TRY {
 153       _STLP_PRIV __ucopy(__first, __last, __new_start);
 154     }
 155     _STLP_UNWIND(this->_M_destroy_nodes(__new_start._M_node, this->_M_start._M_node))
 156     this->_M_start = __new_start;
 157   }
 158   else if (__pos._M_cur == this->_M_finish._M_cur) {
 159     iterator __new_finish = _M_reserve_elements_at_back(__n);
 160     _STLP_TRY {
 161       _STLP_PRIV __ucopy(__first, __last, this->_M_finish);
 162     }
 163     _STLP_UNWIND(this->_M_destroy_nodes(this->_M_finish._M_node + 1,
 164                                         __new_finish._M_node + 1))
 165     this->_M_finish = __new_finish;
 166   }
 167   else
 168     _M_insert_range_aux(__pos, __first, __last, __n, _Movable());
 169 }
 170
 171 template <class _Tp, class _Alloc >
 172 void deque<_Tp,_Alloc>::insert(iterator __pos,
 173                                const_iterator __first, const_iterator __last) {
 174   size_type __n = __last - __first;
 175   if (__pos._M_cur == this->_M_start._M_cur) {
 176     iterator __new_start = _M_reserve_elements_at_front(__n);
 177     _STLP_TRY {
 178       _STLP_PRIV __ucopy(__first, __last, __new_start);
 179     }
 180     _STLP_UNWIND(this->_M_destroy_nodes(__new_start._M_node, this->_M_start._M_node))
 181     this->_M_start = __new_start;
 182   }
 183   else if (__pos._M_cur == this->_M_finish._M_cur) {
 184     iterator __new_finish = _M_reserve_elements_at_back(__n);
 185     _STLP_TRY {
 186       _STLP_PRIV __ucopy(__first, __last, this->_M_finish);
 187     }
 188     _STLP_UNWIND(this->_M_destroy_nodes(this->_M_finish._M_node + 1,
 189                                         __new_finish._M_node + 1))
 190     this->_M_finish = __new_finish;
 191   }
 192   else
 193     _M_insert_range_aux(__pos, __first, __last, __n, _Movable());
 194 }
 195
 196 #endif /* _STLP_MEMBER_TEMPLATES */
 197
 198 template <class _Tp, class _Alloc >
 199 __iterator__ deque<_Tp,_Alloc>::_M_erase(iterator __pos,
 200                                          const __true_type& /*_Movable*/) {
 201   difference_type __index = __pos - this->_M_start;
 202   if (size_type(__index) < this->size() >> 1) {
 203     //We move the start of the deque one position to the right
 204     //starting from the rightmost element to move.
 205     iterator __src = __pos, __dst = __pos;
 206     _STLP_STD::_Destroy(&(*__dst));
 207     if (__src != this->_M_start) {
 208       for (--__src; __dst != this->_M_start; --__src, --__dst) {
 209         _STLP_STD::_Move_Construct(&(*__dst), *__src);
 210         _STLP_STD::_Destroy_Moved(&(*__src));
 211       }
 212     }
 213     _M_pop_front_aux();
 214   }
 215   else {
 216     iterator __src = __pos, __dst = __pos;
 217     _STLP_STD::_Destroy(&(*__dst));
 218     for (++__src; __src != this->_M_finish; ++__src, ++__dst) {
 219       _STLP_STD::_Move_Construct(&(*__dst), *__src);
 220       _STLP_STD::_Destroy_Moved(&(*__src));
 221     }
 222     //Duplication of the pop_back code without the destroy which has already been done:
 223     if (this->_M_finish._M_cur != this->_M_finish._M_first) {
 224       --this->_M_finish._M_cur;
 225     }
 226     else {
 227       _M_pop_back_aux();
 228     }
 229   }
 230   return this->_M_start + __index;
 231 }
 232
 233 template <class _Tp, class _Alloc >
 234 __iterator__ deque<_Tp,_Alloc>::_M_erase(iterator __pos,
 235                                          const __false_type& /*_Movable*/) {
 236   iterator __next = __pos;
 237   ++__next;
 238   difference_type __index = __pos - this->_M_start;
 239   if (size_type(__index) < this->size() >> 1) {
 240     copy_backward(this->_M_start, __pos, __next);
 241     pop_front();
 242   }
 243   else {
 244     copy(__next, this->_M_finish, __pos);
 245     pop_back();
 246   }
 247   return this->_M_start + __index;
 248 }
 249
 250 template <class _Tp, class _Alloc >
 251 __iterator__ deque<_Tp,_Alloc>::_M_erase(iterator __first, iterator __last,
 252                                          const __true_type& /*_Movable*/) {
 253   difference_type __n = __last - __first;
 254   difference_type __elems_before = __first - this->_M_start;
 255   if (__elems_before <= difference_type(this->size() - __n) / 2) {
 256     iterator __src = __first, __dst = __last;
 257     if (__src != this->_M_start) {
 258       for (--__src, --__dst; (__src >= this->_M_start) && (__dst >= __first); --__src, --__dst) {
 259         _STLP_STD::_Destroy(&(*__dst));
 260         _STLP_STD::_Move_Construct(&(*__dst), *__src);
 261       }
 262       if (__dst >= __first) {
 263         //There are more elements to erase than elements to move
 264         _STLP_STD::_Destroy_Range(__first, ++__dst);
 265         _STLP_STD::_Destroy_Moved_Range(this->_M_start, __first);
 266       }
 267       else {
 268         //There are more elements to move than elements to erase
 269         for (; __src >= this->_M_start; --__src, --__dst) {
 270           _STLP_STD::_Destroy_Moved(&(*__dst));
 271           _STLP_STD::_Move_Construct(&(*__dst), *__src);
 272         }
 273         _STLP_STD::_Destroy_Moved_Range(this->_M_start, ++__dst);
 274       }
 275     }
 276     else {
 277       _STLP_STD::_Destroy_Range(this->_M_start, __last);
 278     }
 279     iterator __new_start = this->_M_start + __n;
 280     this->_M_destroy_nodes(this->_M_start._M_node, __new_start._M_node);
 281     this->_M_start = __new_start;
 282   }
 283   else {
 284     if (__last != this->_M_finish) {
 285       iterator __src = __last, __dst = __first;
 286       for (; (__src != this->_M_finish) && (__dst != __last); ++__src, ++__dst) {
 287         _STLP_STD::_Destroy(&(*__dst));
 288         _STLP_STD::_Move_Construct(&(*__dst), *__src);
 289       }
 290       if (__dst != __last) {
 291         //There are more elements to erase than elements to move
 292         _STLP_STD::_Destroy_Range(__dst, __last);
 293         _STLP_STD::_Destroy_Moved_Range(__last, this->_M_finish);
 294       }
 295       else {
 296         //There are more elements to move than elements to erase
 297         for (; __src != this->_M_finish; ++__src, ++__dst) {
 298           _STLP_STD::_Destroy_Moved(&(*__dst));
 299           _STLP_STD::_Move_Construct(&(*__dst), *__src);
 300         }
 301         _STLP_STD::_Destroy_Moved_Range(__dst, this->_M_finish);
 302       }
 303     }
 304     else {
 305       _STLP_STD::_Destroy_Range(__first, this->_M_finish);
 306     }
 307     iterator __new_finish = this->_M_finish - __n;
 308     this->_M_destroy_nodes(__new_finish._M_node + 1, this->_M_finish._M_node + 1);
 309     this->_M_finish = __new_finish;
 310   }
 311   return this->_M_start + __elems_before;
 312 }
 313
 314 template <class _Tp, class _Alloc >
 315 __iterator__ deque<_Tp,_Alloc>::_M_erase(iterator __first, iterator __last,
 316                                          const __false_type& /*_Movable*/) {
 317   difference_type __n = __last - __first;
 318   difference_type __elems_before = __first - this->_M_start;
 319   if (__elems_before <= difference_type(this->size() - __n) / 2) {
 320     copy_backward(this->_M_start, __first, __last);
 321     iterator __new_start = this->_M_start + __n;
 322     _STLP_STD::_Destroy_Range(this->_M_start, __new_start);
 323     this->_M_destroy_nodes(this->_M_start._M_node, __new_start._M_node);
 324     this->_M_start = __new_start;
 325   }
 326   else {
 327     copy(__last, this->_M_finish, __first);
 328     iterator __new_finish = this->_M_finish - __n;
 329     _STLP_STD::_Destroy_Range(__new_finish, this->_M_finish);
 330     this->_M_destroy_nodes(__new_finish._M_node + 1, this->_M_finish._M_node + 1);
 331     this->_M_finish = __new_finish;
 332   }
 333   return this->_M_start + __elems_before;
 334 }
 335
 336 template <class _Tp, class _Alloc >
 337 void deque<_Tp,_Alloc>::clear() {
 338   for (_Map_pointer __node = this->_M_start._M_node + 1;
 339        __node < this->_M_finish._M_node;
 340        ++__node) {
 341     _STLP_STD::_Destroy_Range(*__node, *__node + this->buffer_size());
 342     this->_M_map_size.deallocate(*__node, this->buffer_size());
 343   }
 344
 345   if (this->_M_start._M_node != this->_M_finish._M_node) {
 346     _STLP_STD::_Destroy_Range(this->_M_start._M_cur, this->_M_start._M_last);
 347     _STLP_STD::_Destroy_Range(this->_M_finish._M_first, this->_M_finish._M_cur);
 348     this->_M_map_size.deallocate(this->_M_finish._M_first, this->buffer_size());
 349   }
 350   else
 351     _STLP_STD::_Destroy_Range(this->_M_start._M_cur, this->_M_finish._M_cur);
 352
 353   this->_M_finish = this->_M_start;
 354 }
 355
 356 // Precondition: this->_M_start and this->_M_finish have already been initialized,
 357 // but none of the deque's elements have yet been constructed.
 358 template <class _Tp, class _Alloc >
 359 void deque<_Tp,_Alloc>::_M_fill_initialize(const value_type& __val,
 360                                            const __false_type& /*_TrivialInit*/) {
 361   _Map_pointer __cur = this->_M_start._M_node;
 362   _STLP_TRY {
 363     for (; __cur < this->_M_finish._M_node; ++__cur)
 364       uninitialized_fill(*__cur, *__cur + this->buffer_size(), __val);
 365     uninitialized_fill(this->_M_finish._M_first, this->_M_finish._M_cur, __val);
 366   }
 367   _STLP_UNWIND(_STLP_STD::_Destroy_Range(this->_M_start, iterator(*__cur, __cur)))
 368 }
 369
 370
 371 // Called only if this->_M_finish._M_cur == this->_M_finish._M_last - 1.
 372 template <class _Tp, class _Alloc >
 373 void deque<_Tp,_Alloc>::_M_push_back_aux_v(const value_type& __t) {
 374   _M_reserve_map_at_back();
 375   *(this->_M_finish._M_node + 1) = this->_M_map_size.allocate(this->buffer_size());
 376   _STLP_TRY {
 377     _Copy_Construct(this->_M_finish._M_cur, __t);
 378     this->_M_finish._M_set_node(this->_M_finish._M_node + 1);
 379     this->_M_finish._M_cur = this->_M_finish._M_first;
 380   }
 381   _STLP_UNWIND(this->_M_map_size.deallocate(*(this->_M_finish._M_node + 1),
 382                                             this->buffer_size()))
 383 }
 384
 385 #if defined(_STLP_DONT_SUP_DFLT_PARAM) && !defined(_STLP_NO_ANACHRONISMS)
 386 // Called only if this->_M_finish._M_cur == this->_M_finish._M_last - 1.
 387 template <class _Tp, class _Alloc >
 388 void deque<_Tp,_Alloc>::_M_push_back_aux() {
 389   _M_reserve_map_at_back();
 390   *(this->_M_finish._M_node + 1) = this->_M_map_size.allocate(this->buffer_size());
 391   _STLP_TRY {
 392     _STLP_STD::_Construct(this->_M_finish._M_cur);
 393     this->_M_finish._M_set_node(this->_M_finish._M_node + 1);
 394     this->_M_finish._M_cur = this->_M_finish._M_first;
 395   }
 396   _STLP_UNWIND(this->_M_map_size.deallocate(*(this->_M_finish._M_node + 1),
 397                                             this->buffer_size()))
 398 }
 399 #endif /*_STLP_DONT_SUP_DFLT_PARAM && !_STLP_NO_ANACHRONISMS*/
 400
 401 // Called only if this->_M_start._M_cur == this->_M_start._M_first.
 402 template <class _Tp, class _Alloc >
 403 void deque<_Tp,_Alloc>::_M_push_front_aux_v(const value_type& __t) {
 404   _M_reserve_map_at_front();
 405   *(this->_M_start._M_node - 1) = this->_M_map_size.allocate(this->buffer_size());
 406   _STLP_TRY {
 407     this->_M_start._M_set_node(this->_M_start._M_node - 1);
 408     this->_M_start._M_cur = this->_M_start._M_last - 1;
 409     _Copy_Construct(this->_M_start._M_cur, __t);
 410   }
 411   _STLP_UNWIND((++this->_M_start,
 412                 this->_M_map_size.deallocate(*(this->_M_start._M_node - 1), this->buffer_size())))
 413 }
 414
 415
 416 #if defined (_STLP_DONT_SUP_DFLT_PARAM) && !defined (_STLP_NO_ANACHRONISMS)
 417 // Called only if this->_M_start._M_cur == this->_M_start._M_first.
 418 template <class _Tp, class _Alloc >
 419 void deque<_Tp,_Alloc>::_M_push_front_aux() {
 420   _M_reserve_map_at_front();
 421   *(this->_M_start._M_node - 1) = this->_M_map_size.allocate(this->buffer_size());
 422   _STLP_TRY {
 423     this->_M_start._M_set_node(this->_M_start._M_node - 1);
 424     this->_M_start._M_cur = this->_M_start._M_last - 1;
 425     _STLP_STD::_Construct(this->_M_start._M_cur);
 426   }
 427   _STLP_UNWIND((++this->_M_start, this->_M_map_size.deallocate(*(this->_M_start._M_node - 1),
 428                                                                this->buffer_size())))
 429 }
 430 #endif /*_STLP_DONT_SUP_DFLT_PARAM && !_STLP_NO_ANACHRONISMS*/
 431
 432 // Called only if this->_M_finish._M_cur == this->_M_finish._M_first.
 433 template <class _Tp, class _Alloc >
 434 void deque<_Tp,_Alloc>::_M_pop_back_aux() {
 435   this->_M_map_size.deallocate(this->_M_finish._M_first, this->buffer_size());
 436   this->_M_finish._M_set_node(this->_M_finish._M_node - 1);
 437   this->_M_finish._M_cur = this->_M_finish._M_last - 1;
 438 }
 439
 440 // Note that if the deque has at least one element (a precondition for this member
 441 // function), and if this->_M_start._M_cur == this->_M_start._M_last, then the deque
 442 // must have at least two nodes.
 443 template <class _Tp, class _Alloc >
 444 void deque<_Tp,_Alloc>::_M_pop_front_aux() {
 445   if (this->_M_start._M_cur != this->_M_start._M_last - 1)
 446     ++this->_M_start._M_cur;
 447   else {
 448     this->_M_map_size.deallocate(this->_M_start._M_first, this->buffer_size());
 449     this->_M_start._M_set_node(this->_M_start._M_node + 1);
 450     this->_M_start._M_cur = this->_M_start._M_first;
 451   }
 452 }
 453
 454 template <class _Tp, class _Alloc >
 455 __iterator__ deque<_Tp,_Alloc>::_M_fill_insert_aux(iterator __pos, size_type __n,
 456                                                    const value_type& __x,
 457                                                    const __true_type& /*_Movable*/) {
 458   const difference_type __elems_before = __pos - this->_M_start;
 459   size_type __length = this->size();
 460   value_type __x_copy = __x;
 461   if (__elems_before <= difference_type(__length / 2)) {
 462     iterator __new_start = _M_reserve_elements_at_front(__n);
 463     __pos = this->_M_start + __elems_before;
 464     _STLP_TRY {
 465       iterator __dst = __new_start;
 466       iterator __src = this->_M_start;
 467       for (; __src != __pos; ++__dst, ++__src) {
 468         _STLP_STD::_Move_Construct(&(*__dst), *__src);
 469         _STLP_STD::_Destroy_Moved(&(*__src));
 470       }
 471       this->_M_start = __new_start;
 472       uninitialized_fill(__dst, __src, __x_copy);
 473       __pos = __dst;
 474     }
 475     _STLP_UNWIND(this->_M_destroy_nodes(__new_start._M_node, this->_M_start._M_node))
 476   }
 477   else {
 478     iterator __new_finish = _M_reserve_elements_at_back(__n);
 479     const difference_type __elems_after = difference_type(__length) - __elems_before;
 480     __pos = this->_M_finish - __elems_after;
 481     _STLP_TRY {
 482       iterator __dst = __new_finish;
 483       iterator __src = this->_M_finish;
 484       for (--__src, --__dst; __src >= __pos; --__src, --__dst) {
 485         _STLP_STD::_Move_Construct(&(*__dst), *__src);
 486         _STLP_STD::_Destroy_Moved(&(*__src));
 487       }
 488       this->_M_finish = __new_finish;
 489       uninitialized_fill(__pos, __pos + __n, __x_copy);
 490     }
 491     _STLP_UNWIND(this->_M_destroy_nodes(this->_M_finish._M_node + 1, __new_finish._M_node + 1))
 492   }
 493   return __pos;
 494 }
 495
 496 template <class _Tp, class _Alloc >
 497 __iterator__ deque<_Tp,_Alloc>::_M_fill_insert_aux(iterator __pos, size_type __n,
 498                                                    const value_type& __x,
 499                                                    const __false_type& /*_Movable*/) {
 500   const difference_type __elems_before = __pos - this->_M_start;
 501   size_type __length = this->size();
 502   value_type __x_copy = __x;
 503   if (__elems_before <= difference_type(__length / 2)) {
 504     iterator __new_start = _M_reserve_elements_at_front(__n);
 505     iterator __old_start = this->_M_start;
 506     __pos = this->_M_start + __elems_before;
 507     _STLP_TRY {
 508       if (__elems_before >= difference_type(__n)) {
 509         iterator __start_n = this->_M_start + difference_type(__n);
 510         _STLP_PRIV __ucopy(this->_M_start, __start_n, __new_start);
 511         this->_M_start = __new_start;
 512         copy(__start_n, __pos, __old_start);
 513         fill(__pos - difference_type(__n), __pos, __x_copy);
 514         __pos -= difference_type(__n);
 515       }
 516       else {
 517         _STLP_PRIV __uninitialized_copy_fill(this->_M_start, __pos, __new_start,
 518                                              this->_M_start, __x_copy);
 519         this->_M_start = __new_start;
 520         fill(__old_start, __pos, __x_copy);
 521       }
 522     }
 523     _STLP_UNWIND(this->_M_destroy_nodes(__new_start._M_node, this->_M_start._M_node))
 524   }
 525   else {
 526     iterator __new_finish = _M_reserve_elements_at_back(__n);
 527     iterator __old_finish = this->_M_finish;
 528     const difference_type __elems_after =
 529       difference_type(__length) - __elems_before;
 530     __pos = this->_M_finish - __elems_after;
 531     _STLP_TRY {
 532       if (__elems_after > difference_type(__n)) {
 533         iterator __finish_n = this->_M_finish - difference_type(__n);
 534         _STLP_PRIV __ucopy(__finish_n, this->_M_finish, this->_M_finish);
 535         this->_M_finish = __new_finish;
 536         copy_backward(__pos, __finish_n, __old_finish);
 537         fill(__pos, __pos + difference_type(__n), __x_copy);
 538       }
 539       else {
 540         _STLP_PRIV __uninitialized_fill_copy(this->_M_finish, __pos + difference_type(__n),
 541                                              __x_copy, __pos, this->_M_finish);
 542         this->_M_finish = __new_finish;
 543         fill(__pos, __old_finish, __x_copy);
 544       }
 545     }
 546     _STLP_UNWIND(this->_M_destroy_nodes(this->_M_finish._M_node + 1, __new_finish._M_node + 1))
 547   }
 548   return __pos;
 549 }
 550
 551 #if !defined (_STLP_MEMBER_TEMPLATES)
 552 template <class _Tp, class _Alloc >
 553 void deque<_Tp,_Alloc>::_M_insert_range_aux(iterator __pos,
 554                                             const value_type* __first, const value_type* __last,
 555                                             size_type __n, const __true_type& /*_Movable*/) {
 556   const difference_type __elems_before = __pos - this->_M_start;
 557   size_type __length = size();
 558   if (__elems_before <= difference_type(__length / 2)) {
 559     iterator __new_start = _M_reserve_elements_at_front(__n);
 560     __pos = this->_M_start + __elems_before;
 561     _STLP_TRY {
 562       iterator __dst = __new_start;
 563       iterator __src = this->_M_start;
 564       for (; __src != __pos; ++__dst, ++__src) {
 565         _STLP_STD::_Move_Construct(&(*__dst), *__src);
 566         _STLP_STD::_Destroy_Moved(&(*__src));
 567       }
 568       this->_M_start = __new_start;
 569       _STLP_PRIV __ucopy(__first, __last, __dst);
 570     }
 571     _STLP_UNWIND(this->_M_destroy_nodes(__new_start._M_node, this->_M_start._M_node))
 572   }
 573   else {
 574     iterator __new_finish = _M_reserve_elements_at_back(__n);
 575     const difference_type __elems_after = difference_type(__length) - __elems_before;
 576     __pos = this->_M_finish - __elems_after;
 577     _STLP_TRY {
 578       iterator __dst = __new_finish;
 579       iterator __src = this->_M_finish;
 580       for (--__src, --__dst; __src >= __pos; --__src, --__dst) {
 581         _STLP_STD::_Move_Construct(&(*__dst), *__src);
 582         _STLP_STD::_Destroy_Moved(&(*__src));
 583       }
 584       this->_M_finish = __new_finish;
 585       _STLP_PRIV __ucopy(__first, __last, __pos);
 586     }
 587     _STLP_UNWIND(this->_M_destroy_nodes(this->_M_finish._M_node + 1, __new_finish._M_node + 1))
 588   }
 589 }
 590
 591 template <class _Tp, class _Alloc >
 592 void deque<_Tp,_Alloc>::_M_insert_range_aux(iterator __pos,
 593                                             const value_type* __first, const value_type* __last,
 594                                             size_type __n, const __false_type& /*_Movable*/) {
 595   const difference_type __elems_before = __pos - this->_M_start;
 596   size_type __length = size();
 597   if (__elems_before <= difference_type(__length / 2)) {
 598     iterator __new_start = _M_reserve_elements_at_front(__n);
 599     iterator __old_start = this->_M_start;
 600     __pos = this->_M_start + __elems_before;
 601     _STLP_TRY {
 602       if (__elems_before >= difference_type(__n)) {
 603         iterator __start_n = this->_M_start + difference_type(__n);
 604         _STLP_PRIV __ucopy(this->_M_start, __start_n, __new_start);
 605         this->_M_start = __new_start;
 606         copy(__start_n, __pos, __old_start);
 607         copy(__first, __last, __pos - difference_type(__n));
 608       }
 609       else {
 610         const value_type* __mid = __first + (difference_type(__n) - __elems_before);
 611         __uninitialized_copy_copy(this->_M_start, __pos, __first, __mid, __new_start);
 612         this->_M_start = __new_start;
 613         copy(__mid, __last, __old_start);
 614       }
 615     }
 616     _STLP_UNWIND(this->_M_destroy_nodes(__new_start._M_node, this->_M_start._M_node))
 617   }
 618   else {
 619     iterator __new_finish = _M_reserve_elements_at_back(__n);
 620     iterator __old_finish = this->_M_finish;
 621     const difference_type __elems_after =
 622       difference_type(__length) - __elems_before;
 623     __pos = this->_M_finish - __elems_after;
 624     _STLP_TRY {
 625
 626       if (__elems_after > difference_type(__n)) {
 627         iterator __finish_n = this->_M_finish - difference_type(__n);
 628         _STLP_PRIV __ucopy(__finish_n, this->_M_finish, this->_M_finish);
 629         this->_M_finish = __new_finish;
 630         copy_backward(__pos, __finish_n, __old_finish);
 631         copy(__first, __last, __pos);
 632       }
 633       else {
 634         const value_type* __mid = __first + __elems_after;
 635         __uninitialized_copy_copy(__mid, __last, __pos, this->_M_finish, this->_M_finish);
 636         this->_M_finish = __new_finish;
 637         copy(__first, __mid, __pos);
 638       }
 639     }
 640     _STLP_UNWIND(this->_M_destroy_nodes(this->_M_finish._M_node + 1, __new_finish._M_node + 1))
 641   }
 642 }
 643
 644 template <class _Tp, class _Alloc >
 645 void deque<_Tp,_Alloc>::_M_insert_range_aux(iterator __pos,
 646                                             const_iterator __first, const_iterator __last,
 647                                             size_type __n, const __true_type& /*_Movable*/) {
 648   const difference_type __elems_before = __pos - this->_M_start;
 649   size_type __length = size();
 650   if (__elems_before <= difference_type(__length / 2)) {
 651     iterator __new_start = _M_reserve_elements_at_front(__n);
 652     __pos = this->_M_start + __elems_before;
 653     _STLP_TRY {
 654       iterator __dst = __new_start;
 655       iterator __src = this->_M_start;
 656       for (; __src != __pos; ++__dst, ++__src) {
 657         _STLP_STD::_Move_Construct(&(*__dst), *__src);
 658         _STLP_STD::_Destroy_Moved(&(*__src));
 659       }
 660       this->_M_start = __new_start;
 661       _STLP_PRIV __ucopy(__first, __last, __dst);
 662     }
 663     _STLP_UNWIND(this->_M_destroy_nodes(__new_start._M_node, this->_M_start._M_node))
 664   }
 665   else {
 666     iterator __new_finish = _M_reserve_elements_at_back(__n);
 667     const difference_type __elems_after = difference_type(__length) - __elems_before;
 668     __pos = this->_M_finish - __elems_after;
 669     _STLP_TRY {
 670       iterator __dst = __new_finish;
 671       iterator __src = this->_M_finish;
 672       for (--__src, --__dst; __src >= __pos; --__src, --__dst) {
 673         _STLP_STD::_Move_Construct(&(*__dst), *__src);
 674         _STLP_STD::_Destroy_Moved(&(*__src));
 675       }
 676       this->_M_finish = __new_finish;
 677       _STLP_PRIV __ucopy(__first, __last, __pos);
 678     }
 679     _STLP_UNWIND(this->_M_destroy_nodes(this->_M_finish._M_node + 1, __new_finish._M_node + 1))
 680   }
 681 }
 682
 683 template <class _Tp, class _Alloc >
 684 void deque<_Tp,_Alloc>::_M_insert_range_aux(iterator __pos,
 685                                             const_iterator __first, const_iterator __last,
 686                                             size_type __n, const __false_type& /*_Movable*/) {
 687   const difference_type __elems_before = __pos - this->_M_start;
 688   size_type __length = size();
 689   if (__elems_before < difference_type(__length / 2)) {
 690     iterator __new_start = _M_reserve_elements_at_front(__n);
 691     iterator __old_start = this->_M_start;
 692     __pos = this->_M_start + __elems_before;
 693     _STLP_TRY {
 694       if (__elems_before >= difference_type(__n)) {
 695         iterator __start_n = this->_M_start + __n;
 696         _STLP_PRIV __ucopy(this->_M_start, __start_n, __new_start);
 697         this->_M_start = __new_start;
 698         copy(__start_n, __pos, __old_start);
 699         copy(__first, __last, __pos - difference_type(__n));
 700       }
 701       else {
 702         const_iterator __mid = __first + (__n - __elems_before);
 703         __uninitialized_copy_copy(this->_M_start, __pos, __first, __mid, __new_start);
 704         this->_M_start = __new_start;
 705         copy(__mid, __last, __old_start);
 706       }
 707     }
 708     _STLP_UNWIND(this->_M_destroy_nodes(__new_start._M_node, this->_M_start._M_node))
 709   }
 710   else {
 711     iterator __new_finish = _M_reserve_elements_at_back(__n);
 712     iterator __old_finish = this->_M_finish;
 713     const difference_type __elems_after = __length - __elems_before;
 714     __pos = this->_M_finish - __elems_after;
 715     _STLP_TRY {
 716       if (__elems_after > difference_type(__n)) {
 717         iterator __finish_n = this->_M_finish - difference_type(__n);
 718         _STLP_PRIV __ucopy(__finish_n, this->_M_finish, this->_M_finish);
 719         this->_M_finish = __new_finish;
 720         copy_backward(__pos, __finish_n, __old_finish);
 721         copy(__first, __last, __pos);
 722       }
 723       else {
 724         const_iterator __mid = __first + __elems_after;
 725         __uninitialized_copy_copy(__mid, __last, __pos, this->_M_finish, this->_M_finish);
 726         this->_M_finish = __new_finish;
 727         copy(__first, __mid, __pos);
 728       }
 729     }
 730     _STLP_UNWIND(this->_M_destroy_nodes(this->_M_finish._M_node + 1, __new_finish._M_node + 1))
 731   }
 732 }
 733 #endif /* _STLP_MEMBER_TEMPLATES */
 734
 735 template <class _Tp, class _Alloc >
 736 void deque<_Tp,_Alloc>::_M_new_elements_at_front(size_type __new_elems) {
 737   size_type __new_nodes
 738       = (__new_elems + this->buffer_size() - 1) / this->buffer_size();
 739   _M_reserve_map_at_front(__new_nodes);
 740   size_type __i = 1;
 741   _STLP_TRY {
 742     for (; __i <= __new_nodes; ++__i)
 743       *(this->_M_start._M_node - __i) = this->_M_map_size.allocate(this->buffer_size());
 744   }
 745   _STLP_UNWIND(for (size_type __j = 1; __j < __i; ++__j)
 746                  this->_M_map_size.deallocate(*(this->_M_start._M_node - __j), this->buffer_size()))
 747 }
 748
 749 template <class _Tp, class _Alloc >
 750 void deque<_Tp,_Alloc>::_M_new_elements_at_back(size_type __new_elems) {
 751   size_type __new_nodes
 752       = (__new_elems + this->buffer_size() - 1) / this->buffer_size();
 753   _M_reserve_map_at_back(__new_nodes);
 754   size_type __i = 1;
 755   _STLP_TRY {
 756     for (; __i <= __new_nodes; ++__i)
 757       *(this->_M_finish._M_node + __i) = this->_M_map_size.allocate(this->buffer_size());
 758   }
 759   _STLP_UNWIND(for (size_type __j = 1; __j < __i; ++__j)
 760                  this->_M_map_size.deallocate(*(this->_M_finish._M_node + __j), this->buffer_size()))
 761 }
 762
 763 template <class _Tp, class _Alloc >
 764 void deque<_Tp,_Alloc>::_M_reallocate_map(size_type __nodes_to_add,
 765                                           bool __add_at_front) {
 766   size_type __old_num_nodes = this->_M_finish._M_node - this->_M_start._M_node + 1;
 767   size_type __new_num_nodes = __old_num_nodes + __nodes_to_add;
 768
 769   _Map_pointer __new_nstart;
 770   if (this->_M_map_size._M_data > 2 * __new_num_nodes) {
 771     __new_nstart = this->_M_map._M_data + (this->_M_map_size._M_data - __new_num_nodes) / 2
 772                      + (__add_at_front ? __nodes_to_add : 0);
 773     if (__new_nstart < this->_M_start._M_node)
 774       copy(this->_M_start._M_node, this->_M_finish._M_node + 1, __new_nstart);
 775     else
 776       copy_backward(this->_M_start._M_node, this->_M_finish._M_node + 1,
 777                     __new_nstart + __old_num_nodes);
 778   }
 779   else {
 780     size_type __new_map_size =
 781       this->_M_map_size._M_data + (max)((size_t)this->_M_map_size._M_data, __nodes_to_add) + 2;
 782
 783     _Map_pointer __new_map = this->_M_map.allocate(__new_map_size);
 784     __new_nstart = __new_map + (__new_map_size - __new_num_nodes) / 2
 785                          + (__add_at_front ? __nodes_to_add : 0);
 786     copy(this->_M_start._M_node, this->_M_finish._M_node + 1, __new_nstart);
 787     this->_M_map.deallocate(this->_M_map._M_data, this->_M_map_size._M_data);
 788
 789     this->_M_map._M_data = __new_map;
 790     this->_M_map_size._M_data = __new_map_size;
 791   }
 792
 793   this->_M_start._M_set_node(__new_nstart);
 794   this->_M_finish._M_set_node(__new_nstart + __old_num_nodes - 1);
 795 }
 796
 797 #if defined (deque)
 798 #  undef deque
 799 _STLP_MOVE_TO_STD_NAMESPACE
 800 #endif
 801
 802 _STLP_END_NAMESPACE
 803
 804 #undef __iterator__
 805 #undef iterator
 806 #undef const_iterator
 807 #undef size_type
 808 #undef value_type
 809
 810 #endif /*  _STLP_DEQUE_C */
 811
 812 // Local Variables:
 813 // mode:C++
 814 // End: