home *** CD-ROM | disk | FTP | other *** search
/ OS/2 Shareware BBS: 10 Tools / 10-Tools.zip / stlpt453.zip / STLport-4.5.3 / stlport / stl / _deque.c < prev    next >
C/C++ Source or Header  |  2002-02-02  |  24KB  |  677 lines
  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. // Non-inline member functions from _Deque_base.
  36.  
  37. template <class _Tp, class _Alloc >
  38. _Deque_base<_Tp,_Alloc >::~_Deque_base() {
  39.   if (_M_map._M_data) {
  40.     _M_destroy_nodes(_M_start._M_node, this->_M_finish._M_node + 1);
  41.     _M_map.deallocate(_M_map._M_data, _M_map_size._M_data);
  42.   }
  43. }
  44.  
  45. template <class _Tp, class _Alloc >
  46. void
  47. _Deque_base<_Tp,_Alloc>::_M_initialize_map(size_t __num_elements)
  48. {
  49.   size_t __num_nodes = 
  50.     __num_elements / this->buffer_size() + 1 ;
  51.  
  52.   _M_map_size._M_data = (max)((size_t) _S_initial_map_size, __num_nodes + 2);
  53.   _M_map._M_data = _M_map.allocate(_M_map_size._M_data);
  54.  
  55.   _Tp** __nstart = _M_map._M_data + (_M_map_size._M_data - __num_nodes) / 2;
  56.   _Tp** __nfinish = __nstart + __num_nodes;
  57.     
  58.   _STLP_TRY {
  59.     _M_create_nodes(__nstart, __nfinish);
  60.   }
  61.   _STLP_UNWIND((_M_map.deallocate(_M_map._M_data, _M_map_size._M_data), 
  62.                 _M_map._M_data = 0, _M_map_size._M_data = 0));
  63.   _M_start._M_set_node(__nstart);
  64.   this->_M_finish._M_set_node(__nfinish - 1);
  65.   _M_start._M_cur = _M_start._M_first;
  66.   this->_M_finish._M_cur = this->_M_finish._M_first +
  67.                __num_elements % this->buffer_size();
  68. }
  69.  
  70. template <class _Tp, class _Alloc >
  71. void
  72. _Deque_base<_Tp,_Alloc>::_M_create_nodes(_Tp** __nstart,
  73.                                                   _Tp** __nfinish)
  74. {
  75.   _Tp** __cur;
  76.   _STLP_TRY {
  77.     for (__cur = __nstart; __cur < __nfinish; ++__cur)
  78.       *__cur = _M_map_size.allocate(this->buffer_size());
  79.   }
  80.   _STLP_UNWIND(_M_destroy_nodes(__nstart, __cur));
  81. }
  82.  
  83. template <class _Tp, class _Alloc >
  84. void 
  85. _Deque_base<_Tp,_Alloc>::_M_destroy_nodes(_Tp** __nstart,
  86.                                                    _Tp** __nfinish)
  87. {
  88.   for (_Tp** __n = __nstart; __n < __nfinish; ++__n)
  89.     _M_map_size.deallocate(*__n, this->buffer_size());
  90. }
  91.  
  92.  
  93.  
  94. // Non-inline member functions
  95.  
  96. # if defined ( _STLP_NESTED_TYPE_PARAM_BUG )
  97. // qualified references 
  98. #   define __iterator__           _Deque_iterator<_Tp, _Nonconst_traits<_Tp> >
  99. #   define const_iterator         _Deque_iterator<_Tp, _Const_traits<_Tp>  > 
  100. #   define iterator               __iterator__
  101. #   define size_type              size_t
  102. #   define value_type             _Tp
  103. # else
  104. #  define __iterator__           _STLP_TYPENAME_ON_RETURN_TYPE __deque__<_Tp, _Alloc>::iterator
  105. # endif
  106.  
  107. template <class _Tp, class _Alloc >
  108. __deque__<_Tp, _Alloc >&  
  109. __deque__<_Tp, _Alloc >::operator= (const __deque__<_Tp, _Alloc >& __x) {
  110.   const size_type __len = size();
  111.   if (&__x != this) {
  112.     if (__len >= __x.size())
  113.       erase(copy(__x.begin(), __x.end(), this->_M_start), this->_M_finish);
  114.     else {
  115.       const_iterator __mid = __x.begin() + difference_type(__len);
  116.       copy(__x.begin(), __mid, this->_M_start);
  117.       insert(this->_M_finish, __mid, __x.end());
  118.     }
  119.   }
  120.   return *this;
  121. }        
  122.  
  123. template <class _Tp, class _Alloc >
  124. void 
  125. __deque__<_Tp, _Alloc >::_M_fill_insert(iterator __pos,
  126.                          size_type __n, const value_type& __x)
  127. {
  128.   if (__pos._M_cur == this->_M_start._M_cur) {
  129.     iterator __new_start = _M_reserve_elements_at_front(__n);
  130.     _STLP_TRY {
  131.       uninitialized_fill(__new_start, this->_M_start, __x);
  132.     }
  133.     _STLP_UNWIND(this->_M_destroy_nodes(__new_start._M_node, this->_M_start._M_node));
  134.     this->_M_start = __new_start;
  135.   }
  136.   else if (__pos._M_cur == this->_M_finish._M_cur) {
  137.     iterator __new_finish = _M_reserve_elements_at_back(__n);
  138.     _STLP_TRY {
  139.       uninitialized_fill(this->_M_finish, __new_finish, __x);
  140.     }
  141.     _STLP_UNWIND(this->_M_destroy_nodes(this->_M_finish._M_node+1, __new_finish._M_node+1));
  142.     this->_M_finish = __new_finish;
  143.   }
  144.   else 
  145.     _M_insert_aux(__pos, __n, __x);
  146. }
  147.  
  148. #ifndef _STLP_MEMBER_TEMPLATES  
  149.  
  150. template <class _Tp, class _Alloc >
  151. void __deque__<_Tp, _Alloc>::insert(iterator __pos,
  152.                                            const value_type* __first,
  153.                                            const value_type* __last) {
  154.   size_type __n = __last - __first;
  155.   if (__pos._M_cur == this->_M_start._M_cur) {
  156.     iterator __new_start = _M_reserve_elements_at_front(__n);
  157.     _STLP_TRY {
  158.       uninitialized_copy(__first, __last, __new_start);
  159.     }
  160.     _STLP_UNWIND(this->_M_destroy_nodes(__new_start._M_node, this->_M_start._M_node));
  161.     this->_M_start = __new_start;
  162.   }
  163.   else if (__pos._M_cur == this->_M_finish._M_cur) {
  164.     iterator __new_finish = _M_reserve_elements_at_back(__n);
  165.     _STLP_TRY {
  166.       uninitialized_copy(__first, __last, this->_M_finish);
  167.     }
  168.     _STLP_UNWIND(this->_M_destroy_nodes(this->_M_finish._M_node + 1, 
  169.                                   __new_finish._M_node + 1));
  170.     this->_M_finish = __new_finish;
  171.   }
  172.   else
  173.     _M_insert_aux(__pos, __first, __last, __n);
  174. }
  175.  
  176. template <class _Tp, class _Alloc >
  177. void __deque__<_Tp,_Alloc>::insert(iterator __pos,
  178.                                          const_iterator __first,
  179.                                          const_iterator __last)
  180. {
  181.   size_type __n = __last - __first;
  182.   if (__pos._M_cur == this->_M_start._M_cur) {
  183.     iterator __new_start = _M_reserve_elements_at_front(__n);
  184.     _STLP_TRY {
  185.       uninitialized_copy(__first, __last, __new_start);
  186.     }
  187.     _STLP_UNWIND(this->_M_destroy_nodes(__new_start._M_node, this->_M_start._M_node));
  188.     this->_M_start = __new_start;
  189.   }
  190.   else if (__pos._M_cur == this->_M_finish._M_cur) {
  191.     iterator __new_finish = _M_reserve_elements_at_back(__n);
  192.     _STLP_TRY {
  193.       uninitialized_copy(__first, __last, this->_M_finish);
  194.     }
  195.     _STLP_UNWIND(this->_M_destroy_nodes(this->_M_finish._M_node + 1,__new_finish._M_node + 1));
  196.     this->_M_finish = __new_finish;
  197.   }
  198.   else
  199.     _M_insert_aux(__pos, __first, __last, __n);
  200. }
  201.  
  202. #endif /* _STLP_MEMBER_TEMPLATES */
  203.  
  204. template <class _Tp, class _Alloc >
  205. __iterator__ 
  206. __deque__<_Tp,_Alloc>::erase(iterator __first, iterator __last)
  207. {
  208.   if (__first == this->_M_start && __last == this->_M_finish) {
  209.     clear();
  210.     return this->_M_finish;
  211.   }
  212.   else {
  213.     difference_type __n = __last - __first;
  214.     difference_type __elems_before = __first - this->_M_start;
  215.     if (__elems_before < difference_type(this->size() - __n) / 2) {
  216.       copy_backward(this->_M_start, __first, __last);
  217.       iterator __new_start = this->_M_start + __n;
  218.       _Destroy(this->_M_start, __new_start);
  219.       this->_M_destroy_nodes(this->_M_start._M_node, __new_start._M_node);
  220.       this->_M_start = __new_start;
  221.     }
  222.     else {
  223.       copy(__last, this->_M_finish, __first);
  224.       iterator __new_finish = this->_M_finish - __n;
  225.       _Destroy(__new_finish, this->_M_finish);
  226.       this->_M_destroy_nodes(__new_finish._M_node + 1, this->_M_finish._M_node + 1);
  227.       this->_M_finish = __new_finish;
  228.     }
  229.     return this->_M_start + __elems_before;
  230.   }
  231. }
  232.  
  233. template <class _Tp, class _Alloc >
  234. void __deque__<_Tp,_Alloc>::clear()
  235. {
  236.   for (_Map_pointer __node = this->_M_start._M_node + 1;
  237.        __node < this->_M_finish._M_node;
  238.        ++__node) {
  239.     _Destroy(*__node, *__node + this->buffer_size());
  240.     this->_M_map_size.deallocate(*__node, this->buffer_size());
  241.   }
  242.  
  243.   if (this->_M_start._M_node != this->_M_finish._M_node) {
  244.     _Destroy(this->_M_start._M_cur, this->_M_start._M_last);
  245.     _Destroy(this->_M_finish._M_first, this->_M_finish._M_cur);
  246.     this->_M_map_size.deallocate(this->_M_finish._M_first, this->buffer_size());
  247.   }
  248.   else
  249.     _Destroy(this->_M_start._M_cur, this->_M_finish._M_cur);
  250.  
  251.   this->_M_finish = this->_M_start;
  252. }
  253.  
  254. // Precondition: this->_M_start and this->_M_finish have already been initialized,
  255. // but none of the deque's elements have yet been constructed.
  256. template <class _Tp, class _Alloc >
  257. void 
  258. __deque__<_Tp,_Alloc>::_M_fill_initialize(const value_type& __val) {
  259.   _Map_pointer __cur;
  260.   _STLP_TRY {
  261.     for (__cur = this->_M_start._M_node; __cur < this->_M_finish._M_node; ++__cur)
  262.       uninitialized_fill(*__cur, *__cur + this->buffer_size(), __val);
  263.     uninitialized_fill(this->_M_finish._M_first, this->_M_finish._M_cur, __val);
  264.   }
  265.   _STLP_UNWIND(_Destroy(this->_M_start, iterator(*__cur, __cur)));
  266. }
  267.  
  268.  
  269. // Called only if this->_M_finish._M_cur == this->_M_finish._M_last - 1.
  270. template <class _Tp, class _Alloc >
  271. void
  272. __deque__<_Tp,_Alloc>::_M_push_back_aux_v(const value_type& __t)
  273. {
  274.   value_type __t_copy = __t;
  275.   _M_reserve_map_at_back();
  276.   *(this->_M_finish._M_node + 1) = this->_M_map_size.allocate(this->buffer_size());
  277.   _STLP_TRY {
  278.     _Construct(this->_M_finish._M_cur, __t_copy);
  279.     this->_M_finish._M_set_node(this->_M_finish._M_node + 1);
  280.     this->_M_finish._M_cur = this->_M_finish._M_first;
  281.   }
  282.   _STLP_UNWIND(this->_M_map_size.deallocate(*(this->_M_finish._M_node + 1), 
  283.                       this->buffer_size()));
  284. }
  285.  
  286. # ifndef _STLP_NO_ANACHRONISMS
  287. // Called only if this->_M_finish._M_cur == this->_M_finish._M_last - 1.
  288. template <class _Tp, class _Alloc >
  289. void
  290. __deque__<_Tp,_Alloc>::_M_push_back_aux()
  291. {
  292.   _M_reserve_map_at_back();
  293.   *(this->_M_finish._M_node + 1) = this->_M_map_size.allocate(this->buffer_size());
  294.   _STLP_TRY {
  295.     _Construct(this->_M_finish._M_cur);
  296.     this->_M_finish._M_set_node(this->_M_finish._M_node + 1);
  297.     this->_M_finish._M_cur = this->_M_finish._M_first;
  298.   }
  299.   _STLP_UNWIND(this->_M_map_size.deallocate(*(this->_M_finish._M_node + 1), 
  300.                       this->buffer_size()));
  301. }
  302. # endif
  303.  
  304. // Called only if this->_M_start._M_cur == this->_M_start._M_first.
  305. template <class _Tp, class _Alloc >
  306. void 
  307. __deque__<_Tp,_Alloc>::_M_push_front_aux_v(const value_type& __t)
  308. {
  309.   value_type __t_copy = __t;
  310.   _M_reserve_map_at_front();
  311.   *(this->_M_start._M_node - 1) = this->_M_map_size.allocate(this->buffer_size());
  312.   _STLP_TRY {
  313.     this->_M_start._M_set_node(this->_M_start._M_node - 1);
  314.     this->_M_start._M_cur = this->_M_start._M_last - 1;
  315.     _Construct(this->_M_start._M_cur, __t_copy);
  316.   }
  317.   _STLP_UNWIND((++this->_M_start, 
  318.         this->_M_map_size.deallocate(*(this->_M_start._M_node - 1), this->buffer_size())));
  319. } 
  320.  
  321.  
  322. # ifndef _STLP_NO_ANACHRONISMS
  323. // Called only if this->_M_start._M_cur == this->_M_start._M_first.
  324. template <class _Tp, class _Alloc >
  325. void 
  326. __deque__<_Tp,_Alloc>::_M_push_front_aux()
  327. {
  328.   _M_reserve_map_at_front();
  329.   *(this->_M_start._M_node - 1) = this->_M_map_size.allocate(this->buffer_size());
  330.   _STLP_TRY {
  331.     this->_M_start._M_set_node(this->_M_start._M_node - 1);
  332.     this->_M_start._M_cur = this->_M_start._M_last - 1;
  333.     _Construct(this->_M_start._M_cur);
  334.   }
  335.   _STLP_UNWIND((++this->_M_start, this->_M_map_size.deallocate(*(this->_M_start._M_node - 1), 
  336.                            this->buffer_size() )));
  337. } 
  338. # endif
  339.  
  340. // Called only if this->_M_finish._M_cur == this->_M_finish._M_first.
  341. template <class _Tp, class _Alloc >
  342. void 
  343. __deque__<_Tp,_Alloc>::_M_pop_back_aux()
  344. {
  345.   this->_M_map_size.deallocate(this->_M_finish._M_first, this->buffer_size());
  346.   this->_M_finish._M_set_node(this->_M_finish._M_node - 1);
  347.   this->_M_finish._M_cur = this->_M_finish._M_last - 1;
  348.   _Destroy(this->_M_finish._M_cur);
  349. }
  350.  
  351. // Called only if this->_M_start._M_cur == this->_M_start._M_last - 1.  Note that 
  352. // if the deque has at least one element (a precondition for this member 
  353. // function), and if this->_M_start._M_cur == this->_M_start._M_last, then the deque 
  354. // must have at least two nodes.
  355. template <class _Tp, class _Alloc >
  356. void 
  357. __deque__<_Tp,_Alloc>::_M_pop_front_aux()
  358. {
  359.   _Destroy(this->_M_start._M_cur);
  360.   this->_M_map_size.deallocate(this->_M_start._M_first, this->buffer_size());
  361.   this->_M_start._M_set_node(this->_M_start._M_node + 1);
  362.   this->_M_start._M_cur = this->_M_start._M_first;
  363. }      
  364.  
  365.  
  366.  
  367. template <class _Tp, class _Alloc >
  368. __iterator__
  369. __deque__<_Tp,_Alloc>::_M_insert_aux_prepare(iterator __pos) {
  370.   difference_type __index = __pos - this->_M_start;
  371.   if (__index < difference_type(size() / 2)) {
  372.     push_front(front());
  373.     iterator __front1 = this->_M_start;
  374.     ++__front1;
  375.     iterator __front2 = __front1;
  376.     ++__front2;
  377.     __pos = this->_M_start + __index;
  378.     iterator __pos1 = __pos;
  379.     ++__pos1;
  380.     copy(__front2, __pos1, __front1);
  381.   }
  382.   else {
  383.     push_back(back());
  384.     iterator __back1 = this->_M_finish;
  385.     --__back1;
  386.     iterator __back2 = __back1;
  387.     --__back2;
  388.     __pos = this->_M_start + __index;
  389.     copy_backward(__pos, __back2, __back1);
  390.   }
  391.   return __pos;
  392. }
  393.  
  394. template <class _Tp, class _Alloc >
  395. __iterator__
  396. __deque__<_Tp,_Alloc>::_M_insert_aux(iterator __pos,
  397.                      const value_type& __x) {
  398.   value_type __x_copy = __x;
  399.   _STLP_MPWFIX_TRY        //*TY 06/01/2000 - mpw forget to call dtor on __x_copy without this try block
  400.   __pos = _M_insert_aux_prepare(__pos);
  401.   *__pos = __x_copy;
  402.   return __pos;
  403.   _STLP_MPWFIX_CATCH        //*TY 06/01/2000 - 
  404. }
  405.  
  406. template <class _Tp, class _Alloc >
  407. __iterator__
  408. __deque__<_Tp,_Alloc>::_M_insert_aux(iterator __pos)
  409. {
  410.   __pos = _M_insert_aux_prepare(__pos);
  411.   *__pos = value_type();
  412.   return __pos;
  413. }
  414.  
  415. template <class _Tp, class _Alloc >
  416. void
  417. __deque__<_Tp,_Alloc>::_M_insert_aux(iterator __pos,
  418.                                            size_type __n,
  419.                                            const value_type& __x)
  420. {
  421.   const difference_type __elems_before = __pos - this->_M_start;
  422.   size_type __length = this->size();
  423.   value_type __x_copy = __x;
  424.   if (__elems_before < difference_type(__length / 2)) {
  425.     iterator __new_start = _M_reserve_elements_at_front(__n);
  426.     iterator __old_start = this->_M_start;
  427.     __pos = this->_M_start + __elems_before;
  428.     _STLP_TRY {
  429.       if (__elems_before >= difference_type(__n)) {
  430.         iterator __start_n = this->_M_start + difference_type(__n);
  431.         uninitialized_copy(this->_M_start, __start_n, __new_start);
  432.         this->_M_start = __new_start;
  433.         copy(__start_n, __pos, __old_start);
  434.         fill(__pos - difference_type(__n), __pos, __x_copy);
  435.       }
  436.       else {
  437.         __uninitialized_copy_fill(this->_M_start, __pos, __new_start, 
  438.                               this->_M_start, __x_copy);
  439.         this->_M_start = __new_start;
  440.         fill(__old_start, __pos, __x_copy);
  441.       }
  442.     }
  443.     _STLP_UNWIND(this->_M_destroy_nodes(__new_start._M_node, this->_M_start._M_node));
  444.   }
  445.   else {
  446.     iterator __new_finish = _M_reserve_elements_at_back(__n);
  447.     iterator __old_finish = this->_M_finish;
  448.     const difference_type __elems_after = 
  449.       difference_type(__length) - __elems_before;
  450.     __pos = this->_M_finish - __elems_after;
  451.     _STLP_TRY {
  452.       if (__elems_after > difference_type(__n)) {
  453.         iterator __finish_n = this->_M_finish - difference_type(__n);
  454.         uninitialized_copy(__finish_n, this->_M_finish, this->_M_finish);
  455.         this->_M_finish = __new_finish;
  456.         copy_backward(__pos, __finish_n, __old_finish);
  457.         fill(__pos, __pos + difference_type(__n), __x_copy);
  458.       }
  459.       else {
  460.         __uninitialized_fill_copy(this->_M_finish, __pos + difference_type(__n),
  461.                                   __x_copy, __pos, this->_M_finish);
  462.         this->_M_finish = __new_finish;
  463.         fill(__pos, __old_finish, __x_copy);
  464.       }
  465.     }
  466.     _STLP_UNWIND(this->_M_destroy_nodes(this->_M_finish._M_node + 1, __new_finish._M_node + 1));
  467.   }
  468. }
  469.  
  470. #ifndef _STLP_MEMBER_TEMPLATES 
  471. template <class _Tp, class _Alloc >
  472. void 
  473. __deque__<_Tp,_Alloc>::_M_insert_aux(iterator __pos,
  474.                                            const value_type* __first,
  475.                                            const value_type* __last,
  476.                                            size_type __n)
  477. {
  478.  
  479.   const difference_type __elemsbefore = __pos - this->_M_start;
  480.   size_type __length = size();
  481.   if (__elemsbefore < difference_type(__length / 2)) {
  482.     iterator __new_start = _M_reserve_elements_at_front(__n);
  483.     iterator __old_start = this->_M_start;
  484.     __pos = this->_M_start + __elemsbefore;
  485.     _STLP_TRY {
  486.       if (__elemsbefore >= difference_type(__n)) {
  487.         iterator __start_n = this->_M_start + difference_type(__n);
  488.         uninitialized_copy(this->_M_start, __start_n, __new_start);
  489.         this->_M_start = __new_start;
  490.         copy(__start_n, __pos, __old_start);
  491.         copy(__first, __last, __pos - difference_type(__n));
  492.       }
  493.       else {
  494.         const value_type* __mid = 
  495.       __first + (difference_type(__n) - __elemsbefore);
  496.         __uninitialized_copy_copy(this->_M_start, __pos, __first, __mid,
  497.                                   __new_start, _IsPODType());
  498.         this->_M_start = __new_start;
  499.         copy(__mid, __last, __old_start);
  500.       }
  501.     }
  502.     _STLP_UNWIND(this->_M_destroy_nodes(__new_start._M_node, this->_M_start._M_node));
  503.   }
  504.   else {
  505.     iterator __new_finish = _M_reserve_elements_at_back(__n);
  506.     iterator __old_finish = this->_M_finish;
  507.     const difference_type __elemsafter = 
  508.       difference_type(__length) - __elemsbefore;
  509.     __pos = this->_M_finish - __elemsafter;
  510.     _STLP_TRY {
  511.       if (__elemsafter > difference_type(__n)) {
  512.         iterator __finish_n = this->_M_finish - difference_type(__n);
  513.         uninitialized_copy(__finish_n, this->_M_finish, this->_M_finish);
  514.         this->_M_finish = __new_finish;
  515.         copy_backward(__pos, __finish_n, __old_finish);
  516.         copy(__first, __last, __pos);
  517.       }
  518.       else {
  519.         const value_type* __mid = __first + __elemsafter;
  520.         __uninitialized_copy_copy(__mid, __last, __pos, this->_M_finish, this->_M_finish, _IsPODType());
  521.         this->_M_finish = __new_finish;
  522.         copy(__first, __mid, __pos);
  523.       }
  524.     }
  525.     _STLP_UNWIND(this->_M_destroy_nodes(this->_M_finish._M_node + 1, __new_finish._M_node + 1));
  526.   }
  527. }
  528.  
  529. template <class _Tp, class _Alloc >
  530. void
  531. __deque__<_Tp,_Alloc>::_M_insert_aux(iterator __pos,
  532.                                            const_iterator __first,
  533.                                            const_iterator __last,
  534.                                            size_type __n)
  535. {
  536.   const difference_type __elemsbefore = __pos - this->_M_start;
  537.   size_type __length = size();
  538.   if (__elemsbefore < difference_type(__length / 2)) {
  539.     iterator __new_start = _M_reserve_elements_at_front(__n);
  540.     iterator __old_start = this->_M_start;
  541.     __pos = this->_M_start + __elemsbefore;
  542.     _STLP_TRY {
  543.       if (__elemsbefore >= difference_type(__n)) {
  544.         iterator __start_n = this->_M_start + __n;
  545.         uninitialized_copy(this->_M_start, __start_n, __new_start);
  546.         this->_M_start = __new_start;
  547.         copy(__start_n, __pos, __old_start);
  548.         copy(__first, __last, __pos - difference_type(__n));
  549.       }
  550.       else {
  551.         const_iterator __mid = __first + (__n - __elemsbefore);
  552.         __uninitialized_copy_copy(this->_M_start, __pos, __first, __mid,
  553.                                   __new_start, _IsPODType());
  554.         this->_M_start = __new_start;
  555.         copy(__mid, __last, __old_start);
  556.       }
  557.     }
  558.     _STLP_UNWIND(this->_M_destroy_nodes(__new_start._M_node, this->_M_start._M_node));
  559.   }
  560.   else {
  561.     iterator __new_finish = _M_reserve_elements_at_back(__n);
  562.     iterator __old_finish = this->_M_finish;
  563.     const difference_type __elemsafter = __length - __elemsbefore;
  564.     __pos = this->_M_finish - __elemsafter;
  565.     _STLP_TRY {
  566.       if (__elemsafter > difference_type(__n)) {
  567.         iterator __finish_n = this->_M_finish - difference_type(__n);
  568.         uninitialized_copy(__finish_n, this->_M_finish, this->_M_finish);
  569.         this->_M_finish = __new_finish;
  570.         copy_backward(__pos, __finish_n, __old_finish);
  571.         copy(__first, __last, __pos);
  572.       }
  573.       else {
  574.         const_iterator __mid = __first + __elemsafter;
  575.         __uninitialized_copy_copy(__mid, __last, __pos, this->_M_finish, this->_M_finish, _IsPODType());
  576.         this->_M_finish = __new_finish;
  577.         copy(__first, __mid, __pos);
  578.       }
  579.     }
  580.     _STLP_UNWIND(this->_M_destroy_nodes(this->_M_finish._M_node + 1, __new_finish._M_node + 1));
  581.   }
  582. }
  583.  
  584. #endif /* _STLP_MEMBER_TEMPLATES */
  585.  
  586. template <class _Tp, class _Alloc >
  587. void 
  588. __deque__<_Tp,_Alloc>::_M_new_elements_at_front(size_type __new_elems)
  589. {
  590.   size_type __new_nodes
  591.       = (__new_elems + this->buffer_size() - 1) / this->buffer_size();
  592.   _M_reserve_map_at_front(__new_nodes);
  593.   size_type __i =1;
  594.   _STLP_TRY {
  595.     for (; __i <= __new_nodes; ++__i)
  596.       *(this->_M_start._M_node - __i) = this->_M_map_size.allocate(this->buffer_size());
  597.   }
  598. #       ifdef _STLP_USE_EXCEPTIONS
  599.   catch(...) {
  600.     for (size_type __j = 1; __j < __i; ++__j)
  601.       this->_M_map_size.deallocate(*(this->_M_start._M_node - __j), this->buffer_size());
  602.     throw;
  603.   }
  604. #       endif /* _STLP_USE_EXCEPTIONS */
  605. }
  606.  
  607. template <class _Tp, class _Alloc >
  608. void 
  609. __deque__<_Tp,_Alloc>::_M_new_elements_at_back(size_type __new_elems)
  610. {
  611.   size_type __new_nodes
  612.       = (__new_elems + this->buffer_size() - 1) / this->buffer_size();
  613.   _M_reserve_map_at_back(__new_nodes);
  614.   size_type __i = 1;
  615.   _STLP_TRY {
  616.     for (; __i <= __new_nodes; ++__i)
  617.       *(this->_M_finish._M_node + __i) = this->_M_map_size.allocate(this->buffer_size());
  618.   }
  619. #       ifdef _STLP_USE_EXCEPTIONS
  620.   catch(...) {
  621.     for (size_type __j = 1; __j < __i; ++__j)
  622.       this->_M_map_size.deallocate(*(this->_M_finish._M_node + __j), this->buffer_size());
  623.     throw;
  624.   }
  625. #       endif /* _STLP_USE_EXCEPTIONS */
  626. }
  627.  
  628. template <class _Tp, class _Alloc >
  629. void 
  630. __deque__<_Tp,_Alloc>::_M_reallocate_map(size_type __nodes_to_add,
  631.                                               bool __add_at_front)
  632. {
  633.   size_type __old_num_nodes = this->_M_finish._M_node - this->_M_start._M_node + 1;
  634.   size_type __new_num_nodes = __old_num_nodes + __nodes_to_add;
  635.  
  636.   _Map_pointer __new_nstart;
  637.   if (this->_M_map_size._M_data > 2 * __new_num_nodes) {
  638.     __new_nstart = this->_M_map._M_data + (this->_M_map_size._M_data - __new_num_nodes) / 2 
  639.                      + (__add_at_front ? __nodes_to_add : 0);
  640.     if (__new_nstart < this->_M_start._M_node)
  641.       copy(this->_M_start._M_node, this->_M_finish._M_node + 1, __new_nstart);
  642.     else
  643.       copy_backward(this->_M_start._M_node, this->_M_finish._M_node + 1, 
  644.                     __new_nstart + __old_num_nodes);
  645.   }
  646.   else {
  647.     size_type __new_map_size = 
  648.       this->_M_map_size._M_data + (max)((size_t)this->_M_map_size._M_data, __nodes_to_add) + 2;
  649.  
  650.     _Map_pointer __new_map = this->_M_map.allocate(__new_map_size);
  651.     __new_nstart = __new_map + (__new_map_size - __new_num_nodes) / 2
  652.                          + (__add_at_front ? __nodes_to_add : 0);
  653.     copy(this->_M_start._M_node, this->_M_finish._M_node + 1, __new_nstart);
  654.     this->_M_map.deallocate(this->_M_map._M_data, this->_M_map_size._M_data);
  655.  
  656.     this->_M_map._M_data = __new_map;
  657.     this->_M_map_size._M_data = __new_map_size;
  658.   }
  659.  
  660.   this->_M_start._M_set_node(__new_nstart);
  661.   this->_M_finish._M_set_node(__new_nstart + __old_num_nodes - 1);
  662. }
  663.  
  664. _STLP_END_NAMESPACE
  665.  
  666. # undef __iterator__
  667. # undef iterator
  668. # undef const_iterator
  669. # undef size_type
  670. # undef value_type
  671.  
  672. #endif /*  _STLP_DEQUE_C */
  673.  
  674. // Local Variables:
  675. // mode:C++
  676. // End:
  677.