deque.tcc

Go to the documentation of this file.
00001 // Deque implementation (out of line) -*- C++ -*-
00002 
00003 // Copyright (C) 2001, 2002 Free Software Foundation, Inc.
00004 //
00005 // This file is part of the GNU ISO C++ Library.  This library is free
00006 // software; you can redistribute it and/or modify it under the
00007 // terms of the GNU General Public License as published by the
00008 // Free Software Foundation; either version 2, or (at your option)
00009 // any later version.
00010 
00011 // This library is distributed in the hope that it will be useful,
00012 // but WITHOUT ANY WARRANTY; without even the implied warranty of
00013 // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
00014 // GNU General Public License for more details.
00015 
00016 // You should have received a copy of the GNU General Public License along
00017 // with this library; see the file COPYING.  If not, write to the Free
00018 // Software Foundation, 59 Temple Place - Suite 330, Boston, MA 02111-1307,
00019 // USA.
00020 
00021 // As a special exception, you may use this file as part of a free software
00022 // library without restriction.  Specifically, if other files instantiate
00023 // templates or use macros or inline functions from this file, or you compile
00024 // this file and link it with other files to produce an executable, this
00025 // file does not by itself cause the resulting executable to be covered by
00026 // the GNU General Public License.  This exception does not however
00027 // invalidate any other reasons why the executable file might be covered by
00028 // the GNU General Public License.
00029 
00030 /*
00031  *
00032  * Copyright (c) 1994
00033  * Hewlett-Packard Company
00034  *
00035  * Permission to use, copy, modify, distribute and sell this software
00036  * and its documentation for any purpose is hereby granted without fee,
00037  * provided that the above copyright notice appear in all copies and
00038  * that both that copyright notice and this permission notice appear
00039  * in supporting documentation.  Hewlett-Packard Company makes no
00040  * representations about the suitability of this software for any
00041  * purpose.  It is provided "as is" without express or implied warranty.
00042  *
00043  *
00044  * Copyright (c) 1997
00045  * Silicon Graphics Computer Systems, Inc.
00046  *
00047  * Permission to use, copy, modify, distribute and sell this software
00048  * and its documentation for any purpose is hereby granted without fee,
00049  * provided that the above copyright notice appear in all copies and
00050  * that both that copyright notice and this permission notice appear
00051  * in supporting documentation.  Silicon Graphics makes no
00052  * representations about the suitability of this software for any
00053  * purpose.  It is provided "as is" without express or implied warranty.
00054  */
00055 
00056 /** @file deque.tcc
00057  *  This is an internal header file, included by other library headers.
00058  *  You should not attempt to use it directly.
00059  */
00060 
00061 #ifndef __GLIBCPP_INTERNAL_DEQUE_TCC
00062 #define __GLIBCPP_INTERNAL_DEQUE_TCC
00063 
00064 namespace std
00065 { 
00066   template <typename _Tp, typename _Alloc>
00067     deque<_Tp,_Alloc>&
00068     deque<_Tp,_Alloc>::
00069     operator=(const deque& __x)
00070     {
00071       const size_type __len = size();
00072       if (&__x != this)
00073       {
00074         if (__len >= __x.size())
00075           erase(copy(__x.begin(), __x.end(), _M_start), _M_finish);
00076         else
00077         {
00078           const_iterator __mid = __x.begin() + difference_type(__len);
00079           copy(__x.begin(), __mid, _M_start);
00080           insert(_M_finish, __mid, __x.end());
00081         }
00082       }
00083       return *this;
00084     }        
00085   
00086   template <typename _Tp, typename _Alloc>
00087     typename deque<_Tp,_Alloc>::iterator 
00088     deque<_Tp,_Alloc>::
00089     insert(iterator position, const value_type& __x)
00090     {
00091       if (position._M_cur == _M_start._M_cur)
00092       {
00093         push_front(__x);
00094         return _M_start;
00095       }
00096       else if (position._M_cur == _M_finish._M_cur)
00097       {
00098         push_back(__x);
00099         iterator __tmp = _M_finish;
00100         --__tmp;
00101         return __tmp;
00102       }
00103       else
00104         return _M_insert_aux(position, __x);
00105     }
00106   
00107   template <typename _Tp, typename _Alloc>
00108     typename deque<_Tp,_Alloc>::iterator 
00109     deque<_Tp,_Alloc>::
00110     erase(iterator __position)
00111     {
00112       iterator __next = __position;
00113       ++__next;
00114       size_type __index = __position - _M_start;
00115       if (__index < (size() >> 1))
00116       {
00117         copy_backward(_M_start, __position, __next);
00118         pop_front();
00119       }
00120       else
00121       {
00122         copy(__next, _M_finish, __position);
00123         pop_back();
00124       }
00125       return _M_start + __index;
00126     }
00127   
00128   template <typename _Tp, typename _Alloc>
00129     typename deque<_Tp,_Alloc>::iterator 
00130     deque<_Tp,_Alloc>::
00131     erase(iterator __first, iterator __last)
00132     {
00133       if (__first == _M_start && __last == _M_finish)
00134       {
00135         clear();
00136         return _M_finish;
00137       }
00138       else
00139       {
00140         difference_type __n = __last - __first;
00141         difference_type __elems_before = __first - _M_start;
00142         if (static_cast<size_type>(__elems_before) < (size() - __n) / 2)
00143         {
00144           copy_backward(_M_start, __first, __last);
00145           iterator __new_start = _M_start + __n;
00146           _Destroy(_M_start, __new_start);
00147           _M_destroy_nodes(_M_start._M_node, __new_start._M_node);
00148           _M_start = __new_start;
00149         }
00150         else
00151         {
00152           copy(__last, _M_finish, __first);
00153           iterator __new_finish = _M_finish - __n;
00154           _Destroy(__new_finish, _M_finish);
00155           _M_destroy_nodes(__new_finish._M_node + 1, _M_finish._M_node + 1);
00156           _M_finish = __new_finish;
00157         }
00158         return _M_start + __elems_before;
00159       }
00160     }
00161     
00162   template <typename _Tp, typename _Alloc> 
00163     void
00164     deque<_Tp,_Alloc>::
00165     clear()
00166     {
00167       for (_Map_pointer __node = _M_start._M_node + 1;
00168            __node < _M_finish._M_node;
00169            ++__node)
00170       {
00171         _Destroy(*__node, *__node + _S_buffer_size());
00172         _M_deallocate_node(*__node);
00173       }
00174     
00175       if (_M_start._M_node != _M_finish._M_node)
00176       {
00177         _Destroy(_M_start._M_cur, _M_start._M_last);
00178         _Destroy(_M_finish._M_first, _M_finish._M_cur);
00179         _M_deallocate_node(_M_finish._M_first);
00180       }
00181       else
00182         _Destroy(_M_start._M_cur, _M_finish._M_cur);
00183     
00184       _M_finish = _M_start;
00185     }
00186     
00187   template <typename _Tp, class _Alloc>
00188     template <typename _InputIter>
00189       void
00190       deque<_Tp,_Alloc>
00191       ::_M_assign_aux(_InputIter __first, _InputIter __last, input_iterator_tag)
00192       {
00193         iterator __cur = begin();
00194         for ( ; __first != __last && __cur != end(); ++__cur, ++__first)
00195           *__cur = *__first;
00196         if (__first == __last)
00197           erase(__cur, end());
00198         else
00199           insert(end(), __first, __last);
00200       }
00201     
00202   template <typename _Tp, typename _Alloc>
00203     void
00204     deque<_Tp,_Alloc>::
00205     _M_fill_insert(iterator __pos, size_type __n, const value_type& __x)
00206     {
00207       if (__pos._M_cur == _M_start._M_cur)
00208       {
00209         iterator __new_start = _M_reserve_elements_at_front(__n);
00210         try
00211           {
00212             uninitialized_fill(__new_start, _M_start, __x);
00213             _M_start = __new_start;
00214           }
00215         catch(...)
00216           {
00217             _M_destroy_nodes(__new_start._M_node, _M_start._M_node);
00218             __throw_exception_again;
00219           }
00220       }
00221       else if (__pos._M_cur == _M_finish._M_cur)
00222       {
00223         iterator __new_finish = _M_reserve_elements_at_back(__n);
00224         try
00225           {
00226             uninitialized_fill(_M_finish, __new_finish, __x);
00227             _M_finish = __new_finish;
00228           }
00229         catch(...)
00230           {
00231             _M_destroy_nodes(_M_finish._M_node + 1, __new_finish._M_node + 1);    
00232             __throw_exception_again;
00233           }
00234       }
00235       else 
00236         _M_insert_aux(__pos, __n, __x);
00237     }
00238     
00239   template <typename _Tp, typename _Alloc>
00240     void
00241     deque<_Tp,_Alloc>::
00242     _M_fill_initialize(const value_type& __value)
00243     {
00244       _Map_pointer __cur;
00245       try
00246         {
00247           for (__cur = _M_start._M_node; __cur < _M_finish._M_node; ++__cur)
00248             uninitialized_fill(*__cur, *__cur + _S_buffer_size(), __value);
00249           uninitialized_fill(_M_finish._M_first, _M_finish._M_cur, __value);
00250         }
00251       catch(...)
00252         {
00253           _Destroy(_M_start, iterator(*__cur, __cur));
00254           __throw_exception_again;
00255         }
00256     }
00257     
00258   template <typename _Tp, typename _Alloc>
00259     template <typename _InputIterator>
00260       void
00261       deque<_Tp,_Alloc>::
00262       _M_range_initialize(_InputIterator __first, _InputIterator __last,
00263                           input_iterator_tag)
00264       {
00265         _M_initialize_map(0);
00266         try
00267           {
00268             for ( ; __first != __last; ++__first)
00269               push_back(*__first);
00270           }
00271         catch(...)
00272           {
00273             clear();
00274             __throw_exception_again;
00275           }
00276       }
00277     
00278   template <typename _Tp, typename _Alloc>
00279     template <typename _ForwardIterator>
00280       void
00281       deque<_Tp,_Alloc>::
00282       _M_range_initialize(_ForwardIterator __first, _ForwardIterator __last,
00283                           forward_iterator_tag)
00284       {
00285         size_type __n = distance(__first, __last);
00286         _M_initialize_map(__n);
00287       
00288         _Map_pointer __cur_node;
00289         try
00290           {
00291             for (__cur_node = _M_start._M_node; 
00292                  __cur_node < _M_finish._M_node; 
00293                  ++__cur_node)
00294             {
00295               _ForwardIterator __mid = __first;
00296               advance(__mid, _S_buffer_size());
00297               uninitialized_copy(__first, __mid, *__cur_node);
00298               __first = __mid;
00299             }
00300             uninitialized_copy(__first, __last, _M_finish._M_first);
00301           }
00302         catch(...)
00303           {
00304             _Destroy(_M_start, iterator(*__cur_node, __cur_node));
00305             __throw_exception_again;
00306           }
00307       }
00308     
00309   // Called only if _M_finish._M_cur == _M_finish._M_last - 1.
00310   template <typename _Tp, typename _Alloc>
00311     void
00312     deque<_Tp,_Alloc>::
00313     _M_push_back_aux(const value_type& __t)
00314     {
00315       value_type __t_copy = __t;
00316       _M_reserve_map_at_back();
00317       *(_M_finish._M_node + 1) = _M_allocate_node();
00318       try
00319         {
00320           _Construct(_M_finish._M_cur, __t_copy);
00321           _M_finish._M_set_node(_M_finish._M_node + 1);
00322           _M_finish._M_cur = _M_finish._M_first;
00323         }
00324       catch(...)
00325         {
00326           _M_deallocate_node(*(_M_finish._M_node + 1));
00327           __throw_exception_again;
00328         }
00329     }
00330     
00331   #ifdef _GLIBCPP_DEPRECATED
00332   // Called only if _M_finish._M_cur == _M_finish._M_last - 1.
00333   template <typename _Tp, typename _Alloc>
00334     void
00335     deque<_Tp,_Alloc>::
00336     _M_push_back_aux()
00337     {
00338       _M_reserve_map_at_back();
00339       *(_M_finish._M_node + 1) = _M_allocate_node();
00340       try
00341         {
00342           _Construct(_M_finish._M_cur);
00343           _M_finish._M_set_node(_M_finish._M_node + 1);
00344           _M_finish._M_cur = _M_finish._M_first;
00345         }
00346       catch(...)
00347         {
00348           _M_deallocate_node(*(_M_finish._M_node + 1));
00349           __throw_exception_again;
00350         }
00351     }
00352   #endif
00353     
00354   // Called only if _M_start._M_cur == _M_start._M_first.
00355   template <typename _Tp, typename _Alloc>
00356     void
00357     deque<_Tp,_Alloc>::
00358     _M_push_front_aux(const value_type& __t)
00359     {
00360       value_type __t_copy = __t;
00361       _M_reserve_map_at_front();
00362       *(_M_start._M_node - 1) = _M_allocate_node();
00363       try
00364         {
00365           _M_start._M_set_node(_M_start._M_node - 1);
00366           _M_start._M_cur = _M_start._M_last - 1;
00367           _Construct(_M_start._M_cur, __t_copy);
00368         }
00369       catch(...)
00370         {
00371           ++_M_start;
00372           _M_deallocate_node(*(_M_start._M_node - 1));
00373           __throw_exception_again;
00374         }
00375     } 
00376     
00377   #ifdef _GLIBCPP_DEPRECATED
00378   // Called only if _M_start._M_cur == _M_start._M_first.
00379   template <typename _Tp, typename _Alloc>
00380     void
00381     deque<_Tp,_Alloc>::
00382     _M_push_front_aux()
00383     {
00384       _M_reserve_map_at_front();
00385       *(_M_start._M_node - 1) = _M_allocate_node();
00386       try
00387         {
00388           _M_start._M_set_node(_M_start._M_node - 1);
00389           _M_start._M_cur = _M_start._M_last - 1;
00390           _Construct(_M_start._M_cur);
00391         }
00392       catch(...)
00393         {
00394           ++_M_start;
00395           _M_deallocate_node(*(_M_start._M_node - 1));
00396           __throw_exception_again;
00397         }
00398     } 
00399   #endif
00400     
00401   // Called only if _M_finish._M_cur == _M_finish._M_first.
00402   template <typename _Tp, typename _Alloc>
00403     void deque<_Tp,_Alloc>::
00404     _M_pop_back_aux()
00405     {
00406       _M_deallocate_node(_M_finish._M_first);
00407       _M_finish._M_set_node(_M_finish._M_node - 1);
00408       _M_finish._M_cur = _M_finish._M_last - 1;
00409       _Destroy(_M_finish._M_cur);
00410     }
00411     
00412   // Called only if _M_start._M_cur == _M_start._M_last - 1.  Note that 
00413   // if the deque has at least one element (a precondition for this member 
00414   // function), and if _M_start._M_cur == _M_start._M_last, then the deque 
00415   // must have at least two nodes.
00416   template <typename _Tp, typename _Alloc>
00417     void deque<_Tp,_Alloc>::
00418     _M_pop_front_aux()
00419     {
00420       _Destroy(_M_start._M_cur);
00421       _M_deallocate_node(_M_start._M_first);
00422       _M_start._M_set_node(_M_start._M_node + 1);
00423       _M_start._M_cur = _M_start._M_first;
00424     }      
00425     
00426   template <typename _Tp, typename _Alloc>
00427     template <typename _InputIterator>
00428       void
00429       deque<_Tp,_Alloc>::
00430       _M_range_insert_aux(iterator __pos,
00431                           _InputIterator __first, _InputIterator __last,
00432                           input_iterator_tag)
00433       {
00434         copy(__first, __last, inserter(*this, __pos));
00435       }
00436     
00437   template <typename _Tp, typename _Alloc>
00438     template <typename _ForwardIterator>
00439       void
00440       deque<_Tp,_Alloc>::
00441       _M_range_insert_aux(iterator __pos,
00442                           _ForwardIterator __first, _ForwardIterator __last,
00443                           forward_iterator_tag)
00444       {
00445         size_type __n = distance(__first, __last);
00446         if (__pos._M_cur == _M_start._M_cur)
00447         {
00448           iterator __new_start = _M_reserve_elements_at_front(__n);
00449           try
00450             {
00451               uninitialized_copy(__first, __last, __new_start);
00452               _M_start = __new_start;
00453             }
00454           catch(...)
00455             {
00456               _M_destroy_nodes(__new_start._M_node, _M_start._M_node);
00457               __throw_exception_again;
00458             }
00459         }
00460         else if (__pos._M_cur == _M_finish._M_cur)
00461         {
00462           iterator __new_finish = _M_reserve_elements_at_back(__n);
00463           try
00464             {
00465               uninitialized_copy(__first, __last, _M_finish);
00466               _M_finish = __new_finish;
00467             }
00468           catch(...)
00469             {
00470               _M_destroy_nodes(_M_finish._M_node + 1, __new_finish._M_node + 1);
00471               __throw_exception_again;
00472             }
00473         }
00474         else
00475           _M_insert_aux(__pos, __first, __last, __n);
00476       }
00477     
00478   template <typename _Tp, typename _Alloc>
00479     typename deque<_Tp, _Alloc>::iterator
00480     deque<_Tp,_Alloc>::
00481     _M_insert_aux(iterator __pos, const value_type& __x)
00482     {
00483       difference_type __index = __pos - _M_start;
00484       value_type __x_copy = __x; // XXX copy
00485       if (static_cast<size_type>(__index) < size() / 2)
00486       {
00487         push_front(front());
00488         iterator __front1 = _M_start;
00489         ++__front1;
00490         iterator __front2 = __front1;
00491         ++__front2;
00492         __pos = _M_start + __index;
00493         iterator __pos1 = __pos;
00494         ++__pos1;
00495         copy(__front2, __pos1, __front1);
00496       }
00497       else
00498       {
00499         push_back(back());
00500         iterator __back1 = _M_finish;
00501         --__back1;
00502         iterator __back2 = __back1;
00503         --__back2;
00504         __pos = _M_start + __index;
00505         copy_backward(__pos, __back2, __back1);
00506       }
00507       *__pos = __x_copy;
00508       return __pos;
00509     }
00510     
00511   #ifdef _GLIBCPP_DEPRECATED
00512   // Nothing seems to actually use this.  According to the pattern followed by
00513   // the rest of the SGI code, it would be called by the deprecated insert(pos)
00514   // function, but that has been replaced.  We'll take our time removing this
00515   // anyhow; mark for 3.4.  -pme
00516   template <typename _Tp, typename _Alloc>
00517     typename deque<_Tp,_Alloc>::iterator 
00518     deque<_Tp,_Alloc>::
00519     _M_insert_aux(iterator __pos)
00520     {
00521       difference_type __index = __pos - _M_start;
00522       if (static_cast<size_type>(__index) < size() / 2)
00523       {
00524         push_front(front());
00525         iterator __front1 = _M_start;
00526         ++__front1;
00527         iterator __front2 = __front1;
00528         ++__front2;
00529         __pos = _M_start + __index;
00530         iterator __pos1 = __pos;
00531         ++__pos1;
00532         copy(__front2, __pos1, __front1);
00533       }
00534       else
00535       {
00536         push_back(back());
00537         iterator __back1 = _M_finish;
00538         --__back1;
00539         iterator __back2 = __back1;
00540         --__back2;
00541         __pos = _M_start + __index;
00542         copy_backward(__pos, __back2, __back1);
00543       }
00544       *__pos = value_type();
00545       return __pos;
00546     }
00547   #endif
00548     
00549   template <typename _Tp, typename _Alloc>
00550     void
00551     deque<_Tp,_Alloc>::
00552     _M_insert_aux(iterator __pos, size_type __n, const value_type& __x)
00553     {
00554       const difference_type __elems_before = __pos - _M_start;
00555       size_type __length = this->size();
00556       value_type __x_copy = __x;
00557       if (__elems_before < difference_type(__length / 2))
00558       {
00559         iterator __new_start = _M_reserve_elements_at_front(__n);
00560         iterator __old_start = _M_start;
00561         __pos = _M_start + __elems_before;
00562         try
00563           {
00564             if (__elems_before >= difference_type(__n))
00565             {
00566               iterator __start_n = _M_start + difference_type(__n);
00567               uninitialized_copy(_M_start, __start_n, __new_start);
00568               _M_start = __new_start;
00569               copy(__start_n, __pos, __old_start);
00570               fill(__pos - difference_type(__n), __pos, __x_copy);
00571             }
00572             else
00573             {
00574               __uninitialized_copy_fill(_M_start, __pos, __new_start, 
00575                                         _M_start, __x_copy);
00576               _M_start = __new_start;
00577               fill(__old_start, __pos, __x_copy);
00578             }
00579           }
00580         catch(...)
00581           { 
00582             _M_destroy_nodes(__new_start._M_node, _M_start._M_node);
00583             __throw_exception_again;
00584           }
00585       }
00586       else
00587       {
00588         iterator __new_finish = _M_reserve_elements_at_back(__n);
00589         iterator __old_finish = _M_finish;
00590         const difference_type __elems_after = 
00591           difference_type(__length) - __elems_before;
00592         __pos = _M_finish - __elems_after;
00593         try
00594           {
00595             if (__elems_after > difference_type(__n))
00596             {
00597               iterator __finish_n = _M_finish - difference_type(__n);
00598               uninitialized_copy(__finish_n, _M_finish, _M_finish);
00599               _M_finish = __new_finish;
00600               copy_backward(__pos, __finish_n, __old_finish);
00601               fill(__pos, __pos + difference_type(__n), __x_copy);
00602             }
00603             else
00604             {
00605               __uninitialized_fill_copy(_M_finish, __pos + difference_type(__n),
00606                                         __x_copy, __pos, _M_finish);
00607               _M_finish = __new_finish;
00608               fill(__pos, __old_finish, __x_copy);
00609             }
00610           }
00611         catch(...)
00612           { 
00613             _M_destroy_nodes(_M_finish._M_node + 1, __new_finish._M_node + 1);
00614             __throw_exception_again;
00615           }
00616       }
00617     }
00618     
00619   template <typename _Tp, typename _Alloc>
00620     template <typename _ForwardIterator>
00621       void
00622       deque<_Tp,_Alloc>::
00623       _M_insert_aux(iterator __pos,
00624                     _ForwardIterator __first, _ForwardIterator __last,
00625                     size_type __n)
00626       {
00627         const difference_type __elemsbefore = __pos - _M_start;
00628         size_type __length = size();
00629         if (static_cast<size_type>(__elemsbefore) < __length / 2)
00630         {
00631           iterator __new_start = _M_reserve_elements_at_front(__n);
00632           iterator __old_start = _M_start;
00633           __pos = _M_start + __elemsbefore;
00634           try
00635             {
00636               if (__elemsbefore >= difference_type(__n))
00637               {
00638                 iterator __start_n = _M_start + difference_type(__n); 
00639                 uninitialized_copy(_M_start, __start_n, __new_start);
00640                 _M_start = __new_start;
00641                 copy(__start_n, __pos, __old_start);
00642                 copy(__first, __last, __pos - difference_type(__n));
00643               }
00644               else
00645               {
00646                 _ForwardIterator __mid = __first;
00647                 advance(__mid, difference_type(__n) - __elemsbefore);
00648                 __uninitialized_copy_copy(_M_start, __pos, __first, __mid,
00649                                           __new_start);
00650                 _M_start = __new_start;
00651                 copy(__mid, __last, __old_start);
00652               }
00653             }
00654           catch(...)
00655             {
00656               _M_destroy_nodes(__new_start._M_node, _M_start._M_node);
00657               __throw_exception_again;
00658             }
00659         }
00660         else
00661         {
00662           iterator __new_finish = _M_reserve_elements_at_back(__n);
00663           iterator __old_finish = _M_finish;
00664           const difference_type __elemsafter = 
00665             difference_type(__length) - __elemsbefore;
00666           __pos = _M_finish - __elemsafter;
00667           try
00668             {
00669               if (__elemsafter > difference_type(__n))
00670               {
00671                 iterator __finish_n = _M_finish - difference_type(__n);
00672                 uninitialized_copy(__finish_n, _M_finish, _M_finish);
00673                 _M_finish = __new_finish;
00674                 copy_backward(__pos, __finish_n, __old_finish);
00675                 copy(__first, __last, __pos);
00676               }
00677               else
00678               {
00679                 _ForwardIterator __mid = __first;
00680                 advance(__mid, __elemsafter);
00681                 __uninitialized_copy_copy(__mid, __last, __pos,
00682                                           _M_finish, _M_finish);
00683                 _M_finish = __new_finish;
00684                 copy(__first, __mid, __pos);
00685               }
00686             }
00687           catch(...)
00688             {
00689               _M_destroy_nodes(_M_finish._M_node + 1, __new_finish._M_node + 1);
00690               __throw_exception_again;
00691             }
00692         }
00693       }
00694     
00695   template <typename _Tp, typename _Alloc>
00696     void
00697     deque<_Tp,_Alloc>::
00698     _M_new_elements_at_front(size_type __new_elems)
00699     {
00700       size_type __new_nodes
00701           = (__new_elems + _S_buffer_size() - 1) / _S_buffer_size();
00702       _M_reserve_map_at_front(__new_nodes);
00703       size_type __i;
00704       try
00705         {
00706           for (__i = 1; __i <= __new_nodes; ++__i)
00707             *(_M_start._M_node - __i) = _M_allocate_node();
00708         }
00709       catch(...)
00710         {
00711           for (size_type __j = 1; __j < __i; ++__j)
00712             _M_deallocate_node(*(_M_start._M_node - __j));      
00713           __throw_exception_again;
00714         }
00715     }
00716     
00717   template <typename _Tp, typename _Alloc>
00718     void
00719     deque<_Tp,_Alloc>::
00720     _M_new_elements_at_back(size_type __new_elems)
00721     {
00722       size_type __new_nodes
00723           = (__new_elems + _S_buffer_size() - 1) / _S_buffer_size();
00724       _M_reserve_map_at_back(__new_nodes);
00725       size_type __i;
00726       try
00727         {
00728           for (__i = 1; __i <= __new_nodes; ++__i)
00729             *(_M_finish._M_node + __i) = _M_allocate_node();
00730         }
00731       catch(...)
00732         {
00733           for (size_type __j = 1; __j < __i; ++__j)
00734             _M_deallocate_node(*(_M_finish._M_node + __j));      
00735           __throw_exception_again;
00736         }
00737     }
00738     
00739   template <typename _Tp, typename _Alloc>
00740     void
00741     deque<_Tp,_Alloc>::
00742     _M_reallocate_map(size_type __nodes_to_add, bool __add_at_front)
00743     {
00744       size_type __old_num_nodes = _M_finish._M_node - _M_start._M_node + 1;
00745       size_type __new_num_nodes = __old_num_nodes + __nodes_to_add;
00746     
00747       _Map_pointer __new_nstart;
00748       if (_M_map_size > 2 * __new_num_nodes)
00749       {
00750         __new_nstart = _M_map + (_M_map_size - __new_num_nodes) / 2 
00751                          + (__add_at_front ? __nodes_to_add : 0);
00752         if (__new_nstart < _M_start._M_node)
00753           copy(_M_start._M_node, _M_finish._M_node + 1, __new_nstart);
00754         else
00755           copy_backward(_M_start._M_node, _M_finish._M_node + 1, 
00756                         __new_nstart + __old_num_nodes);
00757       }
00758       else
00759       {
00760         size_type __new_map_size = 
00761           _M_map_size + max(_M_map_size, __nodes_to_add) + 2;
00762     
00763         _Map_pointer __new_map = _M_allocate_map(__new_map_size);
00764         __new_nstart = __new_map + (__new_map_size - __new_num_nodes) / 2
00765                              + (__add_at_front ? __nodes_to_add : 0);
00766         copy(_M_start._M_node, _M_finish._M_node + 1, __new_nstart);
00767         _M_deallocate_map(_M_map, _M_map_size);
00768     
00769         _M_map = __new_map;
00770         _M_map_size = __new_map_size;
00771       }
00772     
00773       _M_start._M_set_node(__new_nstart);
00774       _M_finish._M_set_node(__new_nstart + __old_num_nodes - 1);
00775     }
00776 } // namespace std 
00777   
00778 #endif /* __GLIBCPP_INTERNAL_DEQUE_TCC */
00779 

Generated on Thu Feb 10 23:22:54 2005 for libstdc++-v3 Source by  doxygen 1.4.0