epoc32/include/stdapis/stlportv5/stl/_deque.c
author William Roberts <williamr@symbian.org>
Wed, 31 Mar 2010 12:33:34 +0100
branchSymbian3
changeset 4 837f303aceeb
parent 3 e1b950c65cb4
permissions -rw-r--r--
Current Symbian^3 public API header files (from PDK 3.0.h)
This is the epoc32/include tree with the "platform" subtrees removed, and
all but a selected few mbg and rsg files removed.
     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: