contrib/gcc-3.4/libstdc++-v3/include/bits/deque.tcc

   1 // Deque implementation (out of line) -*- C++ -*-
   2
   3 // Copyright (C) 2001, 2002, 2003, 2004 Free Software Foundation, Inc.
   4 //
   5 // This file is part of the GNU ISO C++ Library.  This library is free
   6 // software; you can redistribute it and/or modify it under the
   7 // terms of the GNU General Public License as published by the
   8 // Free Software Foundation; either version 2, or (at your option)
   9 // any later version.
  10
  11 // This library is distributed in the hope that it will be useful,
  12 // but WITHOUT ANY WARRANTY; without even the implied warranty of
  13 // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  14 // GNU General Public License for more details.
  15
  16 // You should have received a copy of the GNU General Public License along
  17 // with this library; see the file COPYING.  If not, write to the Free
  18 // Software Foundation, 59 Temple Place - Suite 330, Boston, MA 02111-1307,
  19 // USA.
  20
  21 // As a special exception, you may use this file as part of a free software
  22 // library without restriction.  Specifically, if other files instantiate
  23 // templates or use macros or inline functions from this file, or you compile
  24 // this file and link it with other files to produce an executable, this
  25 // file does not by itself cause the resulting executable to be covered by
  26 // the GNU General Public License.  This exception does not however
  27 // invalidate any other reasons why the executable file might be covered by
  28 // the GNU General Public License.
  29
  30 /*
  31  *
  32  * Copyright (c) 1994
  33  * Hewlett-Packard Company
  34  *
  35  * Permission to use, copy, modify, distribute and sell this software
  36  * and its documentation for any purpose is hereby granted without fee,
  37  * provided that the above copyright notice appear in all copies and
  38  * that both that copyright notice and this permission notice appear
  39  * in supporting documentation.  Hewlett-Packard Company makes no
  40  * representations about the suitability of this software for any
  41  * purpose.  It is provided "as is" without express or implied warranty.
  42  *
  43  *
  44  * Copyright (c) 1997
  45  * Silicon Graphics Computer Systems, Inc.
  46  *
  47  * Permission to use, copy, modify, distribute and sell this software
  48  * and its documentation for any purpose is hereby granted without fee,
  49  * provided that the above copyright notice appear in all copies and
  50  * that both that copyright notice and this permission notice appear
  51  * in supporting documentation.  Silicon Graphics makes no
  52  * representations about the suitability of this software for any
  53  * purpose.  It is provided "as is" without express or implied warranty.
  54  */
  55
  56 /** @file deque.tcc
  57  *  This is an internal header file, included by other library headers.
  58  *  You should not attempt to use it directly.
  59  */
  60
  61 #ifndef _DEQUE_TCC
  62 #define _DEQUE_TCC 1
  63
  64 namespace _GLIBCXX_STD
  65 {
  66   template <typename _Tp, typename _Alloc>
  67     deque<_Tp,_Alloc>&
  68     deque<_Tp,_Alloc>::
  69     operator=(const deque& __x)
  70     {
  71       const size_type __len = size();
  72       if (&__x != this)
  73         {
  74           if (__len >= __x.size())
  75             erase(std::copy(__x.begin(), __x.end(), this->_M_impl._M_start),
  76                   this->_M_impl._M_finish);
  77           else
  78             {
  79               const_iterator __mid = __x.begin() + difference_type(__len);
  80               std::copy(__x.begin(), __mid, this->_M_impl._M_start);
  81               insert(this->_M_impl._M_finish, __mid, __x.end());
  82             }
  83         }
  84       return *this;
  85     }
  86
  87   template <typename _Tp, typename _Alloc>
  88     typename deque<_Tp,_Alloc>::iterator
  89     deque<_Tp,_Alloc>::
  90     insert(iterator position, const value_type& __x)
  91     {
  92       if (position._M_cur == this->_M_impl._M_start._M_cur)
  93         {
  94           push_front(__x);
  95           return this->_M_impl._M_start;
  96         }
  97       else if (position._M_cur == this->_M_impl._M_finish._M_cur)
  98         {
  99           push_back(__x);
 100           iterator __tmp = this->_M_impl._M_finish;
 101           --__tmp;
 102           return __tmp;
 103         }
 104       else
 105         return _M_insert_aux(position, __x);
 106     }
 107
 108   template <typename _Tp, typename _Alloc>
 109     typename deque<_Tp,_Alloc>::iterator
 110     deque<_Tp,_Alloc>::
 111     erase(iterator __position)
 112     {
 113       iterator __next = __position;
 114       ++__next;
 115       size_type __index = __position - this->_M_impl._M_start;
 116       if (__index < (size() >> 1))
 117         {
 118           std::copy_backward(this->_M_impl._M_start, __position, __next);
 119           pop_front();
 120         }
 121       else
 122         {
 123           std::copy(__next, this->_M_impl._M_finish, __position);
 124           pop_back();
 125         }
 126       return this->_M_impl._M_start + __index;
 127     }
 128
 129   template <typename _Tp, typename _Alloc>
 130     typename deque<_Tp,_Alloc>::iterator
 131     deque<_Tp,_Alloc>::
 132     erase(iterator __first, iterator __last)
 133     {
 134       if (__first == this->_M_impl._M_start && __last == this->_M_impl._M_finish)
 135         {
 136           clear();
 137           return this->_M_impl._M_finish;
 138         }
 139       else
 140         {
 141           const difference_type __n = __last - __first;
 142           const difference_type __elems_before = __first - this->_M_impl._M_start;
 143           if (static_cast<size_type>(__elems_before) < (size() - __n) / 2)
 144             {
 145               std::copy_backward(this->_M_impl._M_start, __first, __last);
 146               iterator __new_start = this->_M_impl._M_start + __n;
 147               std::_Destroy(this->_M_impl._M_start, __new_start);
 148               _M_destroy_nodes(this->_M_impl._M_start._M_node, __new_start._M_node);
 149               this->_M_impl._M_start = __new_start;
 150             }
 151           else
 152             {
 153               std::copy(__last, this->_M_impl._M_finish, __first);
 154               iterator __new_finish = this->_M_impl._M_finish - __n;
 155               std::_Destroy(__new_finish, this->_M_impl._M_finish);
 156               _M_destroy_nodes(__new_finish._M_node + 1,
 157                                this->_M_impl._M_finish._M_node + 1);
 158               this->_M_impl._M_finish = __new_finish;
 159             }
 160           return this->_M_impl._M_start + __elems_before;
 161         }
 162     }
 163
 164   template <typename _Tp, typename _Alloc>
 165     void
 166     deque<_Tp,_Alloc>::
 167     clear()
 168     {
 169       for (_Map_pointer __node = this->_M_impl._M_start._M_node + 1;
 170            __node < this->_M_impl._M_finish._M_node;
 171            ++__node)
 172         {
 173           std::_Destroy(*__node, *__node + _S_buffer_size());
 174           _M_deallocate_node(*__node);
 175         }
 176
 177       if (this->_M_impl._M_start._M_node != this->_M_impl._M_finish._M_node)
 178         {
 179           std::_Destroy(this->_M_impl._M_start._M_cur, this->_M_impl._M_start._M_last);
 180           std::_Destroy(this->_M_impl._M_finish._M_first, this->_M_impl._M_finish._M_cur);
 181           _M_deallocate_node(this->_M_impl._M_finish._M_first);
 182         }
 183       else
 184         std::_Destroy(this->_M_impl._M_start._M_cur, this->_M_impl._M_finish._M_cur);
 185
 186       this->_M_impl._M_finish = this->_M_impl._M_start;
 187     }
 188
 189   template <typename _Tp, class _Alloc>
 190     template <typename _InputIterator>
 191       void
 192       deque<_Tp,_Alloc>
 193       ::_M_assign_aux(_InputIterator __first, _InputIterator __last,
 194                       input_iterator_tag)
 195       {
 196         iterator __cur = begin();
 197         for ( ; __first != __last && __cur != end(); ++__cur, ++__first)
 198           *__cur = *__first;
 199         if (__first == __last)
 200           erase(__cur, end());
 201         else
 202           insert(end(), __first, __last);
 203       }
 204
 205   template <typename _Tp, typename _Alloc>
 206     void
 207     deque<_Tp,_Alloc>::
 208     _M_fill_insert(iterator __pos, size_type __n, const value_type& __x)
 209     {
 210       if (__pos._M_cur == this->_M_impl._M_start._M_cur)
 211         {
 212           iterator __new_start = _M_reserve_elements_at_front(__n);
 213           try
 214             {
 215               std::uninitialized_fill(__new_start, this->_M_impl._M_start, __x);
 216               this->_M_impl._M_start = __new_start;
 217             }
 218           catch(...)
 219             {
 220               _M_destroy_nodes(__new_start._M_node, this->_M_impl._M_start._M_node);
 221               __throw_exception_again;
 222             }
 223         }
 224       else if (__pos._M_cur == this->_M_impl._M_finish._M_cur)
 225         {
 226           iterator __new_finish = _M_reserve_elements_at_back(__n);
 227           try
 228             {
 229               std::uninitialized_fill(this->_M_impl._M_finish, __new_finish, __x);
 230               this->_M_impl._M_finish = __new_finish;
 231             }
 232           catch(...)
 233             {
 234               _M_destroy_nodes(this->_M_impl._M_finish._M_node + 1,
 235                                __new_finish._M_node + 1);
 236               __throw_exception_again;
 237             }
 238         }
 239       else
 240         _M_insert_aux(__pos, __n, __x);
 241     }
 242
 243   template <typename _Tp, typename _Alloc>
 244     void
 245     deque<_Tp,_Alloc>::
 246     _M_fill_initialize(const value_type& __value)
 247     {
 248       _Map_pointer __cur;
 249       try
 250         {
 251           for (__cur = this->_M_impl._M_start._M_node;
 252                __cur < this->_M_impl._M_finish._M_node;
 253                ++__cur)
 254             std::uninitialized_fill(*__cur, *__cur + _S_buffer_size(), __value);
 255           std::uninitialized_fill(this->_M_impl._M_finish._M_first,
 256                                   this->_M_impl._M_finish._M_cur,
 257                                   __value);
 258         }
 259       catch(...)
 260         {
 261           std::_Destroy(this->_M_impl._M_start, iterator(*__cur, __cur));
 262           __throw_exception_again;
 263         }
 264     }
 265
 266   template <typename _Tp, typename _Alloc>
 267     template <typename _InputIterator>
 268       void
 269       deque<_Tp,_Alloc>::
 270       _M_range_initialize(_InputIterator __first, _InputIterator __last,
 271                           input_iterator_tag)
 272       {
 273         this->_M_initialize_map(0);
 274         try
 275           {
 276             for ( ; __first != __last; ++__first)
 277               push_back(*__first);
 278           }
 279         catch(...)
 280           {
 281             clear();
 282             __throw_exception_again;
 283           }
 284       }
 285
 286   template <typename _Tp, typename _Alloc>
 287     template <typename _ForwardIterator>
 288       void
 289       deque<_Tp,_Alloc>::
 290       _M_range_initialize(_ForwardIterator __first, _ForwardIterator __last,
 291                           forward_iterator_tag)
 292       {
 293         const size_type __n = std::distance(__first, __last);
 294         this->_M_initialize_map(__n);
 295
 296         _Map_pointer __cur_node;
 297         try
 298           {
 299             for (__cur_node = this->_M_impl._M_start._M_node;
 300                  __cur_node < this->_M_impl._M_finish._M_node;
 301                  ++__cur_node)
 302             {
 303               _ForwardIterator __mid = __first;
 304               std::advance(__mid, _S_buffer_size());
 305               std::uninitialized_copy(__first, __mid, *__cur_node);
 306               __first = __mid;
 307             }
 308             std::uninitialized_copy(__first, __last, this->_M_impl._M_finish._M_first);
 309           }
 310         catch(...)
 311           {
 312             std::_Destroy(this->_M_impl._M_start, iterator(*__cur_node, __cur_node));
 313             __throw_exception_again;
 314           }
 315       }
 316
 317   // Called only if _M_impl._M_finish._M_cur == _M_impl._M_finish._M_last - 1.
 318   template <typename _Tp, typename _Alloc>
 319     void
 320     deque<_Tp,_Alloc>::
 321     _M_push_back_aux(const value_type& __t)
 322     {
 323       value_type __t_copy = __t;
 324       _M_reserve_map_at_back();
 325       *(this->_M_impl._M_finish._M_node + 1) = this->_M_allocate_node();
 326       try
 327         {
 328           std::_Construct(this->_M_impl._M_finish._M_cur, __t_copy);
 329           this->_M_impl._M_finish._M_set_node(this->_M_impl._M_finish._M_node + 1);
 330           this->_M_impl._M_finish._M_cur = this->_M_impl._M_finish._M_first;
 331         }
 332       catch(...)
 333         {
 334           _M_deallocate_node(*(this->_M_impl._M_finish._M_node + 1));
 335           __throw_exception_again;
 336         }
 337     }
 338
 339   // Called only if _M_impl._M_start._M_cur == _M_impl._M_start._M_first.
 340   template <typename _Tp, typename _Alloc>
 341     void
 342     deque<_Tp,_Alloc>::
 343     _M_push_front_aux(const value_type& __t)
 344     {
 345       value_type __t_copy = __t;
 346       _M_reserve_map_at_front();
 347       *(this->_M_impl._M_start._M_node - 1) = this->_M_allocate_node();
 348       try
 349         {
 350           this->_M_impl._M_start._M_set_node(this->_M_impl._M_start._M_node - 1);
 351           this->_M_impl._M_start._M_cur = this->_M_impl._M_start._M_last - 1;
 352           std::_Construct(this->_M_impl._M_start._M_cur, __t_copy);
 353         }
 354       catch(...)
 355         {
 356           ++this->_M_impl._M_start;
 357           _M_deallocate_node(*(this->_M_impl._M_start._M_node - 1));
 358           __throw_exception_again;
 359         }
 360     }
 361
 362   // Called only if _M_impl._M_finish._M_cur == _M_impl._M_finish._M_first.
 363   template <typename _Tp, typename _Alloc>
 364     void deque<_Tp,_Alloc>::
 365     _M_pop_back_aux()
 366     {
 367       _M_deallocate_node(this->_M_impl._M_finish._M_first);
 368       this->_M_impl._M_finish._M_set_node(this->_M_impl._M_finish._M_node - 1);
 369       this->_M_impl._M_finish._M_cur = this->_M_impl._M_finish._M_last - 1;
 370       std::_Destroy(this->_M_impl._M_finish._M_cur);
 371     }
 372
 373   // Called only if _M_impl._M_start._M_cur == _M_impl._M_start._M_last - 1.  Note that
 374   // if the deque has at least one element (a precondition for this member
 375   // function), and if _M_impl._M_start._M_cur == _M_impl._M_start._M_last, then the deque
 376   // must have at least two nodes.
 377   template <typename _Tp, typename _Alloc>
 378     void deque<_Tp,_Alloc>::
 379     _M_pop_front_aux()
 380     {
 381       std::_Destroy(this->_M_impl._M_start._M_cur);
 382       _M_deallocate_node(this->_M_impl._M_start._M_first);
 383       this->_M_impl._M_start._M_set_node(this->_M_impl._M_start._M_node + 1);
 384       this->_M_impl._M_start._M_cur = this->_M_impl._M_start._M_first;
 385     }
 386
 387   template <typename _Tp, typename _Alloc>
 388     template <typename _InputIterator>
 389       void
 390       deque<_Tp,_Alloc>::
 391       _M_range_insert_aux(iterator __pos,
 392                           _InputIterator __first, _InputIterator __last,
 393                           input_iterator_tag)
 394       { std::copy(__first, __last, std::inserter(*this, __pos)); }
 395
 396   template <typename _Tp, typename _Alloc>
 397     template <typename _ForwardIterator>
 398       void
 399       deque<_Tp,_Alloc>::
 400       _M_range_insert_aux(iterator __pos,
 401                           _ForwardIterator __first, _ForwardIterator __last,
 402                           forward_iterator_tag)
 403       {
 404         size_type __n = std::distance(__first, __last);
 405         if (__pos._M_cur == this->_M_impl._M_start._M_cur)
 406           {
 407             iterator __new_start = _M_reserve_elements_at_front(__n);
 408             try
 409               {
 410                 std::uninitialized_copy(__first, __last, __new_start);
 411                 this->_M_impl._M_start = __new_start;
 412               }
 413             catch(...)
 414               {
 415                 _M_destroy_nodes(__new_start._M_node, this->_M_impl._M_start._M_node);
 416                 __throw_exception_again;
 417               }
 418           }
 419         else if (__pos._M_cur == this->_M_impl._M_finish._M_cur)
 420           {
 421             iterator __new_finish = _M_reserve_elements_at_back(__n);
 422             try
 423               {
 424                 std::uninitialized_copy(__first, __last, this->_M_impl._M_finish);
 425                 this->_M_impl._M_finish = __new_finish;
 426               }
 427             catch(...)
 428               {
 429                 _M_destroy_nodes(this->_M_impl._M_finish._M_node + 1,
 430                                  __new_finish._M_node + 1);
 431                 __throw_exception_again;
 432               }
 433           }
 434         else
 435           _M_insert_aux(__pos, __first, __last, __n);
 436       }
 437
 438   template <typename _Tp, typename _Alloc>
 439     typename deque<_Tp, _Alloc>::iterator
 440     deque<_Tp,_Alloc>::
 441     _M_insert_aux(iterator __pos, const value_type& __x)
 442     {
 443       difference_type __index = __pos - this->_M_impl._M_start;
 444       value_type __x_copy = __x; // XXX copy
 445       if (static_cast<size_type>(__index) < size() / 2)
 446         {
 447           push_front(front());
 448           iterator __front1 = this->_M_impl._M_start;
 449           ++__front1;
 450           iterator __front2 = __front1;
 451           ++__front2;
 452           __pos = this->_M_impl._M_start + __index;
 453           iterator __pos1 = __pos;
 454           ++__pos1;
 455           std::copy(__front2, __pos1, __front1);
 456         }
 457       else
 458         {
 459           push_back(back());
 460           iterator __back1 = this->_M_impl._M_finish;
 461           --__back1;
 462           iterator __back2 = __back1;
 463           --__back2;
 464           __pos = this->_M_impl._M_start + __index;
 465           std::copy_backward(__pos, __back2, __back1);
 466         }
 467       *__pos = __x_copy;
 468       return __pos;
 469     }
 470
 471   template <typename _Tp, typename _Alloc>
 472     void
 473     deque<_Tp,_Alloc>::
 474     _M_insert_aux(iterator __pos, size_type __n, const value_type& __x)
 475     {
 476       const difference_type __elems_before = __pos - this->_M_impl._M_start;
 477       size_type __length = this->size();
 478       value_type __x_copy = __x;
 479       if (__elems_before < difference_type(__length / 2))
 480         {
 481           iterator __new_start = _M_reserve_elements_at_front(__n);
 482           iterator __old_start = this->_M_impl._M_start;
 483           __pos = this->_M_impl._M_start + __elems_before;
 484           try
 485             {
 486               if (__elems_before >= difference_type(__n))
 487                 {
 488                   iterator __start_n = this->_M_impl._M_start + difference_type(__n);
 489                   std::uninitialized_copy(this->_M_impl._M_start, __start_n,
 490                                           __new_start);
 491                   this->_M_impl._M_start = __new_start;
 492                   std::copy(__start_n, __pos, __old_start);
 493                   fill(__pos - difference_type(__n), __pos, __x_copy);
 494                 }
 495               else
 496                 {
 497                   std::__uninitialized_copy_fill(this->_M_impl._M_start, __pos,
 498                                                  __new_start,
 499                                                  this->_M_impl._M_start, __x_copy);
 500                   this->_M_impl._M_start = __new_start;
 501                   std::fill(__old_start, __pos, __x_copy);
 502                 }
 503             }
 504           catch(...)
 505             {
 506               _M_destroy_nodes(__new_start._M_node, this->_M_impl._M_start._M_node);
 507               __throw_exception_again;
 508             }
 509         }
 510       else
 511         {
 512           iterator __new_finish = _M_reserve_elements_at_back(__n);
 513           iterator __old_finish = this->_M_impl._M_finish;
 514           const difference_type __elems_after =
 515             difference_type(__length) - __elems_before;
 516           __pos = this->_M_impl._M_finish - __elems_after;
 517           try
 518             {
 519               if (__elems_after > difference_type(__n))
 520                 {
 521                   iterator __finish_n = this->_M_impl._M_finish - difference_type(__n);
 522                   std::uninitialized_copy(__finish_n, this->_M_impl._M_finish,
 523                                           this->_M_impl._M_finish);
 524                   this->_M_impl._M_finish = __new_finish;
 525                   std::copy_backward(__pos, __finish_n, __old_finish);
 526                   std::fill(__pos, __pos + difference_type(__n), __x_copy);
 527                 }
 528               else
 529                 {
 530                   std::__uninitialized_fill_copy(this->_M_impl._M_finish,
 531                                                  __pos + difference_type(__n),
 532                                                  __x_copy, __pos,
 533                                                  this->_M_impl._M_finish);
 534                   this->_M_impl._M_finish = __new_finish;
 535                   std::fill(__pos, __old_finish, __x_copy);
 536                 }
 537             }
 538           catch(...)
 539             {
 540               _M_destroy_nodes(this->_M_impl._M_finish._M_node + 1,
 541                                __new_finish._M_node + 1);
 542               __throw_exception_again;
 543             }
 544         }
 545     }
 546
 547   template <typename _Tp, typename _Alloc>
 548     template <typename _ForwardIterator>
 549       void
 550       deque<_Tp,_Alloc>::
 551       _M_insert_aux(iterator __pos,
 552                     _ForwardIterator __first, _ForwardIterator __last,
 553                     size_type __n)
 554       {
 555         const difference_type __elemsbefore = __pos - this->_M_impl._M_start;
 556         size_type __length = size();
 557         if (static_cast<size_type>(__elemsbefore) < __length / 2)
 558           {
 559             iterator __new_start = _M_reserve_elements_at_front(__n);
 560             iterator __old_start = this->_M_impl._M_start;
 561             __pos = this->_M_impl._M_start + __elemsbefore;
 562             try
 563               {
 564                 if (__elemsbefore >= difference_type(__n))
 565                   {
 566                     iterator __start_n = this->_M_impl._M_start + difference_type(__n);
 567                     std::uninitialized_copy(this->_M_impl._M_start, __start_n,
 568                                             __new_start);
 569                     this->_M_impl._M_start = __new_start;
 570                     std::copy(__start_n, __pos, __old_start);
 571                     std::copy(__first, __last, __pos - difference_type(__n));
 572                   }
 573                 else
 574                   {
 575                     _ForwardIterator __mid = __first;
 576                     std::advance(__mid, difference_type(__n) - __elemsbefore);
 577                     std::__uninitialized_copy_copy(this->_M_impl._M_start, __pos,
 578                                                    __first, __mid, __new_start);
 579                     this->_M_impl._M_start = __new_start;
 580                     std::copy(__mid, __last, __old_start);
 581                   }
 582               }
 583             catch(...)
 584               {
 585                 _M_destroy_nodes(__new_start._M_node, this->_M_impl._M_start._M_node);
 586                 __throw_exception_again;
 587               }
 588           }
 589         else
 590         {
 591           iterator __new_finish = _M_reserve_elements_at_back(__n);
 592           iterator __old_finish = this->_M_impl._M_finish;
 593           const difference_type __elemsafter =
 594             difference_type(__length) - __elemsbefore;
 595           __pos = this->_M_impl._M_finish - __elemsafter;
 596           try
 597             {
 598               if (__elemsafter > difference_type(__n))
 599                 {
 600                   iterator __finish_n = this->_M_impl._M_finish - difference_type(__n);
 601                   std::uninitialized_copy(__finish_n,
 602                                           this->_M_impl._M_finish,
 603                                           this->_M_impl._M_finish);
 604                   this->_M_impl._M_finish = __new_finish;
 605                   std::copy_backward(__pos, __finish_n, __old_finish);
 606                   std::copy(__first, __last, __pos);
 607                 }
 608               else
 609                 {
 610                   _ForwardIterator __mid = __first;
 611                   std::advance(__mid, __elemsafter);
 612                   std::__uninitialized_copy_copy(__mid, __last, __pos,
 613                                                  this->_M_impl._M_finish,
 614                                                  this->_M_impl._M_finish);
 615                   this->_M_impl._M_finish = __new_finish;
 616                   std::copy(__first, __mid, __pos);
 617                 }
 618             }
 619           catch(...)
 620             {
 621               _M_destroy_nodes(this->_M_impl._M_finish._M_node + 1,
 622                                __new_finish._M_node + 1);
 623               __throw_exception_again;
 624             }
 625         }
 626       }
 627
 628   template <typename _Tp, typename _Alloc>
 629     void
 630     deque<_Tp,_Alloc>::
 631     _M_new_elements_at_front(size_type __new_elems)
 632     {
 633       size_type __new_nodes
 634         = (__new_elems + _S_buffer_size() - 1) / _S_buffer_size();
 635       _M_reserve_map_at_front(__new_nodes);
 636       size_type __i;
 637       try
 638         {
 639           for (__i = 1; __i <= __new_nodes; ++__i)
 640             *(this->_M_impl._M_start._M_node - __i) = this->_M_allocate_node();
 641         }
 642       catch(...)
 643         {
 644           for (size_type __j = 1; __j < __i; ++__j)
 645             _M_deallocate_node(*(this->_M_impl._M_start._M_node - __j));
 646           __throw_exception_again;
 647         }
 648     }
 649
 650   template <typename _Tp, typename _Alloc>
 651     void
 652     deque<_Tp,_Alloc>::
 653     _M_new_elements_at_back(size_type __new_elems)
 654     {
 655       size_type __new_nodes
 656           = (__new_elems + _S_buffer_size() - 1) / _S_buffer_size();
 657       _M_reserve_map_at_back(__new_nodes);
 658       size_type __i;
 659       try
 660         {
 661           for (__i = 1; __i <= __new_nodes; ++__i)
 662             *(this->_M_impl._M_finish._M_node + __i) = this->_M_allocate_node();
 663         }
 664       catch(...)
 665         {
 666           for (size_type __j = 1; __j < __i; ++__j)
 667             _M_deallocate_node(*(this->_M_impl._M_finish._M_node + __j));
 668           __throw_exception_again;
 669         }
 670     }
 671
 672   template <typename _Tp, typename _Alloc>
 673     void
 674     deque<_Tp,_Alloc>::
 675     _M_reallocate_map(size_type __nodes_to_add, bool __add_at_front)
 676     {
 677       size_type __old_num_nodes
 678         = this->_M_impl._M_finish._M_node - this->_M_impl._M_start._M_node + 1;
 679       size_type __new_num_nodes = __old_num_nodes + __nodes_to_add;
 680
 681       _Map_pointer __new_nstart;
 682       if (this->_M_impl._M_map_size > 2 * __new_num_nodes)
 683         {
 684           __new_nstart = this->_M_impl._M_map + (this->_M_impl._M_map_size
 685                                          - __new_num_nodes) / 2
 686                          + (__add_at_front ? __nodes_to_add : 0);
 687           if (__new_nstart < this->_M_impl._M_start._M_node)
 688             std::copy(this->_M_impl._M_start._M_node,
 689                     this->_M_impl._M_finish._M_node + 1,
 690                     __new_nstart);
 691           else
 692             std::copy_backward(this->_M_impl._M_start._M_node,
 693                                this->_M_impl._M_finish._M_node + 1,
 694                                __new_nstart + __old_num_nodes);
 695         }
 696       else
 697         {
 698           size_type __new_map_size = this->_M_impl._M_map_size
 699                                      + std::max(this->_M_impl._M_map_size,
 700                                                 __nodes_to_add) + 2;
 701
 702           _Map_pointer __new_map = this->_M_allocate_map(__new_map_size);
 703           __new_nstart = __new_map + (__new_map_size - __new_num_nodes) / 2
 704                          + (__add_at_front ? __nodes_to_add : 0);
 705           std::copy(this->_M_impl._M_start._M_node,
 706                     this->_M_impl._M_finish._M_node + 1,
 707                     __new_nstart);
 708           _M_deallocate_map(this->_M_impl._M_map, this->_M_impl._M_map_size);
 709
 710           this->_M_impl._M_map = __new_map;
 711           this->_M_impl._M_map_size = __new_map_size;
 712         }
 713
 714       this->_M_impl._M_start._M_set_node(__new_nstart);
 715       this->_M_impl._M_finish._M_set_node(__new_nstart + __old_num_nodes - 1);
 716     }
 717 } // namespace std
 718
 719 #endif