l4/pkg/libstdc++-v3/contrib/libstdc++-v3-4.6/include/bits/deque.tcc

   1 // Deque implementation (out of line) -*- C++ -*-
   2
   3 // Copyright (C) 2001, 2002, 2003, 2004, 2005, 2006, 2007, 2008,
   4 // 2009, 2010, 2011
   5 // Free Software Foundation, Inc.
   6 //
   7 // This file is part of the GNU ISO C++ Library.  This library is free
   8 // software; you can redistribute it and/or modify it under the
   9 // terms of the GNU General Public License as published by the
  10 // Free Software Foundation; either version 3, or (at your option)
  11 // any later version.
  12
  13 // This library is distributed in the hope that it will be useful,
  14 // but WITHOUT ANY WARRANTY; without even the implied warranty of
  15 // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  16 // GNU General Public License for more details.
  17
  18 // Under Section 7 of GPL version 3, you are granted additional
  19 // permissions described in the GCC Runtime Library Exception, version
  20 // 3.1, as published by the Free Software Foundation.
  21
  22 // You should have received a copy of the GNU General Public License and
  23 // a copy of the GCC Runtime Library Exception along with this program;
  24 // see the files COPYING3 and COPYING.RUNTIME respectively.  If not, see
  25 // <http://www.gnu.org/licenses/>.
  26
  27 /*
  28  *
  29  * Copyright (c) 1994
  30  * Hewlett-Packard Company
  31  *
  32  * Permission to use, copy, modify, distribute and sell this software
  33  * and its documentation for any purpose is hereby granted without fee,
  34  * provided that the above copyright notice appear in all copies and
  35  * that both that copyright notice and this permission notice appear
  36  * in supporting documentation.  Hewlett-Packard Company makes no
  37  * representations about the suitability of this software for any
  38  * purpose.  It is provided "as is" without express or implied warranty.
  39  *
  40  *
  41  * Copyright (c) 1997
  42  * Silicon Graphics Computer Systems, Inc.
  43  *
  44  * Permission to use, copy, modify, distribute and sell this software
  45  * and its documentation for any purpose is hereby granted without fee,
  46  * provided that the above copyright notice appear in all copies and
  47  * that both that copyright notice and this permission notice appear
  48  * in supporting documentation.  Silicon Graphics makes no
  49  * representations about the suitability of this software for any
  50  * purpose.  It is provided "as is" without express or implied warranty.
  51  */
  52
  53 /** @file bits/deque.tcc
  54  *  This is an internal header file, included by other library headers.
  55  *  Do not attempt to use it directly. @headername{deque}
  56  */
  57
  58 #ifndef _DEQUE_TCC
  59 #define _DEQUE_TCC 1
  60
  61 namespace std _GLIBCXX_VISIBILITY(default)
  62 {
  63 _GLIBCXX_BEGIN_NAMESPACE_CONTAINER
  64
  65 #ifdef __GXX_EXPERIMENTAL_CXX0X__
  66   template <typename _Tp, typename _Alloc>
  67     void
  68     deque<_Tp, _Alloc>::
  69     _M_default_initialize()
  70     {
  71       _Map_pointer __cur;
  72       __try
  73         {
  74           for (__cur = this->_M_impl._M_start._M_node;
  75                __cur < this->_M_impl._M_finish._M_node;
  76                ++__cur)
  77             std::__uninitialized_default_a(*__cur, *__cur + _S_buffer_size(),
  78                                            _M_get_Tp_allocator());
  79           std::__uninitialized_default_a(this->_M_impl._M_finish._M_first,
  80                                          this->_M_impl._M_finish._M_cur,
  81                                          _M_get_Tp_allocator());
  82         }
  83       __catch(...)
  84         {
  85           std::_Destroy(this->_M_impl._M_start, iterator(*__cur, __cur),
  86                         _M_get_Tp_allocator());
  87           __throw_exception_again;
  88         }
  89     }
  90 #endif
  91
  92   template <typename _Tp, typename _Alloc>
  93     deque<_Tp, _Alloc>&
  94     deque<_Tp, _Alloc>::
  95     operator=(const deque& __x)
  96     {
  97       const size_type __len = size();
  98       if (&__x != this)
  99         {
 100           if (__len >= __x.size())
 101             _M_erase_at_end(std::copy(__x.begin(), __x.end(),
 102                                       this->_M_impl._M_start));
 103           else
 104             {
 105               const_iterator __mid = __x.begin() + difference_type(__len);
 106               std::copy(__x.begin(), __mid, this->_M_impl._M_start);
 107               insert(this->_M_impl._M_finish, __mid, __x.end());
 108             }
 109         }
 110       return *this;
 111     }
 112
 113 #ifdef __GXX_EXPERIMENTAL_CXX0X__
 114   template<typename _Tp, typename _Alloc>
 115     template<typename... _Args>
 116       void
 117       deque<_Tp, _Alloc>::
 118       emplace_front(_Args&&... __args)
 119       {
 120         if (this->_M_impl._M_start._M_cur != this->_M_impl._M_start._M_first)
 121           {
 122             this->_M_impl.construct(this->_M_impl._M_start._M_cur - 1,
 123                                     std::forward<_Args>(__args)...);
 124             --this->_M_impl._M_start._M_cur;
 125           }
 126         else
 127           _M_push_front_aux(std::forward<_Args>(__args)...);
 128       }
 129
 130   template<typename _Tp, typename _Alloc>
 131     template<typename... _Args>
 132       void
 133       deque<_Tp, _Alloc>::
 134       emplace_back(_Args&&... __args)
 135       {
 136         if (this->_M_impl._M_finish._M_cur
 137             != this->_M_impl._M_finish._M_last - 1)
 138           {
 139             this->_M_impl.construct(this->_M_impl._M_finish._M_cur,
 140                                     std::forward<_Args>(__args)...);
 141             ++this->_M_impl._M_finish._M_cur;
 142           }
 143         else
 144           _M_push_back_aux(std::forward<_Args>(__args)...);
 145       }
 146 #endif
 147
 148   template <typename _Tp, typename _Alloc>
 149     typename deque<_Tp, _Alloc>::iterator
 150     deque<_Tp, _Alloc>::
 151     insert(iterator __position, const value_type& __x)
 152     {
 153       if (__position._M_cur == this->_M_impl._M_start._M_cur)
 154         {
 155           push_front(__x);
 156           return this->_M_impl._M_start;
 157         }
 158       else if (__position._M_cur == this->_M_impl._M_finish._M_cur)
 159         {
 160           push_back(__x);
 161           iterator __tmp = this->_M_impl._M_finish;
 162           --__tmp;
 163           return __tmp;
 164         }
 165       else
 166         return _M_insert_aux(__position, __x);
 167     }
 168
 169 #ifdef __GXX_EXPERIMENTAL_CXX0X__
 170   template<typename _Tp, typename _Alloc>
 171     template<typename... _Args>
 172       typename deque<_Tp, _Alloc>::iterator
 173       deque<_Tp, _Alloc>::
 174       emplace(iterator __position, _Args&&... __args)
 175       {
 176         if (__position._M_cur == this->_M_impl._M_start._M_cur)
 177           {
 178             push_front(std::forward<_Args>(__args)...);
 179             return this->_M_impl._M_start;
 180           }
 181         else if (__position._M_cur == this->_M_impl._M_finish._M_cur)
 182           {
 183             push_back(std::forward<_Args>(__args)...);
 184             iterator __tmp = this->_M_impl._M_finish;
 185             --__tmp;
 186             return __tmp;
 187           }
 188         else
 189           return _M_insert_aux(__position, std::forward<_Args>(__args)...);
 190       }
 191 #endif
 192
 193   template <typename _Tp, typename _Alloc>
 194     typename deque<_Tp, _Alloc>::iterator
 195     deque<_Tp, _Alloc>::
 196     erase(iterator __position)
 197     {
 198       iterator __next = __position;
 199       ++__next;
 200       const difference_type __index = __position - begin();
 201       if (static_cast<size_type>(__index) < (size() >> 1))
 202         {
 203           if (__position != begin())
 204             _GLIBCXX_MOVE_BACKWARD3(begin(), __position, __next);
 205           pop_front();
 206         }
 207       else
 208         {
 209           if (__next != end())
 210             _GLIBCXX_MOVE3(__next, end(), __position);
 211           pop_back();
 212         }
 213       return begin() + __index;
 214     }
 215
 216   template <typename _Tp, typename _Alloc>
 217     typename deque<_Tp, _Alloc>::iterator
 218     deque<_Tp, _Alloc>::
 219     erase(iterator __first, iterator __last)
 220     {
 221       if (__first == __last)
 222         return __first;
 223       else if (__first == begin() && __last == end())
 224         {
 225           clear();
 226           return end();
 227         }
 228       else
 229         {
 230           const difference_type __n = __last - __first;
 231           const difference_type __elems_before = __first - begin();
 232           if (static_cast<size_type>(__elems_before) <= (size() - __n) / 2)
 233             {
 234               if (__first != begin())
 235                 _GLIBCXX_MOVE_BACKWARD3(begin(), __first, __last);
 236               _M_erase_at_begin(begin() + __n);
 237             }
 238           else
 239             {
 240               if (__last != end())
 241                 _GLIBCXX_MOVE3(__last, end(), __first);
 242               _M_erase_at_end(end() - __n);
 243             }
 244           return begin() + __elems_before;
 245         }
 246     }
 247
 248   template <typename _Tp, class _Alloc>
 249     template <typename _InputIterator>
 250       void
 251       deque<_Tp, _Alloc>::
 252       _M_assign_aux(_InputIterator __first, _InputIterator __last,
 253                     std::input_iterator_tag)
 254       {
 255         iterator __cur = begin();
 256         for (; __first != __last && __cur != end(); ++__cur, ++__first)
 257           *__cur = *__first;
 258         if (__first == __last)
 259           _M_erase_at_end(__cur);
 260         else
 261           insert(end(), __first, __last);
 262       }
 263
 264   template <typename _Tp, typename _Alloc>
 265     void
 266     deque<_Tp, _Alloc>::
 267     _M_fill_insert(iterator __pos, size_type __n, const value_type& __x)
 268     {
 269       if (__pos._M_cur == this->_M_impl._M_start._M_cur)
 270         {
 271           iterator __new_start = _M_reserve_elements_at_front(__n);
 272           __try
 273             {
 274               std::__uninitialized_fill_a(__new_start, this->_M_impl._M_start,
 275                                           __x, _M_get_Tp_allocator());
 276               this->_M_impl._M_start = __new_start;
 277             }
 278           __catch(...)
 279             {
 280               _M_destroy_nodes(__new_start._M_node,
 281                                this->_M_impl._M_start._M_node);
 282               __throw_exception_again;
 283             }
 284         }
 285       else if (__pos._M_cur == this->_M_impl._M_finish._M_cur)
 286         {
 287           iterator __new_finish = _M_reserve_elements_at_back(__n);
 288           __try
 289             {
 290               std::__uninitialized_fill_a(this->_M_impl._M_finish,
 291                                           __new_finish, __x,
 292                                           _M_get_Tp_allocator());
 293               this->_M_impl._M_finish = __new_finish;
 294             }
 295           __catch(...)
 296             {
 297               _M_destroy_nodes(this->_M_impl._M_finish._M_node + 1,
 298                                __new_finish._M_node + 1);
 299               __throw_exception_again;
 300             }
 301         }
 302       else
 303         _M_insert_aux(__pos, __n, __x);
 304     }
 305
 306 #ifdef __GXX_EXPERIMENTAL_CXX0X__
 307   template <typename _Tp, typename _Alloc>
 308     void
 309     deque<_Tp, _Alloc>::
 310     _M_default_append(size_type __n)
 311     {
 312       if (__n)
 313         {
 314           iterator __new_finish = _M_reserve_elements_at_back(__n);
 315           __try
 316             {
 317               std::__uninitialized_default_a(this->_M_impl._M_finish,
 318                                              __new_finish,
 319                                              _M_get_Tp_allocator());
 320               this->_M_impl._M_finish = __new_finish;
 321             }
 322           __catch(...)
 323             {
 324               _M_destroy_nodes(this->_M_impl._M_finish._M_node + 1,
 325                                __new_finish._M_node + 1);
 326               __throw_exception_again;
 327             }
 328         }
 329     }
 330 #endif
 331
 332   template <typename _Tp, typename _Alloc>
 333     void
 334     deque<_Tp, _Alloc>::
 335     _M_fill_initialize(const value_type& __value)
 336     {
 337       _Map_pointer __cur;
 338       __try
 339         {
 340           for (__cur = this->_M_impl._M_start._M_node;
 341                __cur < this->_M_impl._M_finish._M_node;
 342                ++__cur)
 343             std::__uninitialized_fill_a(*__cur, *__cur + _S_buffer_size(),
 344                                         __value, _M_get_Tp_allocator());
 345           std::__uninitialized_fill_a(this->_M_impl._M_finish._M_first,
 346                                       this->_M_impl._M_finish._M_cur,
 347                                       __value, _M_get_Tp_allocator());
 348         }
 349       __catch(...)
 350         {
 351           std::_Destroy(this->_M_impl._M_start, iterator(*__cur, __cur),
 352                         _M_get_Tp_allocator());
 353           __throw_exception_again;
 354         }
 355     }
 356
 357   template <typename _Tp, typename _Alloc>
 358     template <typename _InputIterator>
 359       void
 360       deque<_Tp, _Alloc>::
 361       _M_range_initialize(_InputIterator __first, _InputIterator __last,
 362                           std::input_iterator_tag)
 363       {
 364         this->_M_initialize_map(0);
 365         __try
 366           {
 367             for (; __first != __last; ++__first)
 368               push_back(*__first);
 369           }
 370         __catch(...)
 371           {
 372             clear();
 373             __throw_exception_again;
 374           }
 375       }
 376
 377   template <typename _Tp, typename _Alloc>
 378     template <typename _ForwardIterator>
 379       void
 380       deque<_Tp, _Alloc>::
 381       _M_range_initialize(_ForwardIterator __first, _ForwardIterator __last,
 382                           std::forward_iterator_tag)
 383       {
 384         const size_type __n = std::distance(__first, __last);
 385         this->_M_initialize_map(__n);
 386
 387         _Map_pointer __cur_node;
 388         __try
 389           {
 390             for (__cur_node = this->_M_impl._M_start._M_node;
 391                  __cur_node < this->_M_impl._M_finish._M_node;
 392                  ++__cur_node)
 393               {
 394                 _ForwardIterator __mid = __first;
 395                 std::advance(__mid, _S_buffer_size());
 396                 std::__uninitialized_copy_a(__first, __mid, *__cur_node,
 397                                             _M_get_Tp_allocator());
 398                 __first = __mid;
 399               }
 400             std::__uninitialized_copy_a(__first, __last,
 401                                         this->_M_impl._M_finish._M_first,
 402                                         _M_get_Tp_allocator());
 403           }
 404         __catch(...)
 405           {
 406             std::_Destroy(this->_M_impl._M_start,
 407                           iterator(*__cur_node, __cur_node),
 408                           _M_get_Tp_allocator());
 409             __throw_exception_again;
 410           }
 411       }
 412
 413   // Called only if _M_impl._M_finish._M_cur == _M_impl._M_finish._M_last - 1.
 414   template<typename _Tp, typename _Alloc>
 415 #ifdef __GXX_EXPERIMENTAL_CXX0X__
 416     template<typename... _Args>
 417       void
 418       deque<_Tp, _Alloc>::
 419       _M_push_back_aux(_Args&&... __args)
 420 #else
 421       void
 422       deque<_Tp, _Alloc>::
 423       _M_push_back_aux(const value_type& __t)
 424 #endif
 425       {
 426         _M_reserve_map_at_back();
 427         *(this->_M_impl._M_finish._M_node + 1) = this->_M_allocate_node();
 428         __try
 429           {
 430 #ifdef __GXX_EXPERIMENTAL_CXX0X__
 431             this->_M_impl.construct(this->_M_impl._M_finish._M_cur,
 432                                     std::forward<_Args>(__args)...);
 433 #else
 434             this->_M_impl.construct(this->_M_impl._M_finish._M_cur, __t);
 435 #endif
 436             this->_M_impl._M_finish._M_set_node(this->_M_impl._M_finish._M_node
 437                                                 + 1);
 438             this->_M_impl._M_finish._M_cur = this->_M_impl._M_finish._M_first;
 439           }
 440         __catch(...)
 441           {
 442             _M_deallocate_node(*(this->_M_impl._M_finish._M_node + 1));
 443             __throw_exception_again;
 444           }
 445       }
 446
 447   // Called only if _M_impl._M_start._M_cur == _M_impl._M_start._M_first.
 448   template<typename _Tp, typename _Alloc>
 449 #ifdef __GXX_EXPERIMENTAL_CXX0X__
 450     template<typename... _Args>
 451       void
 452       deque<_Tp, _Alloc>::
 453       _M_push_front_aux(_Args&&... __args)
 454 #else
 455       void
 456       deque<_Tp, _Alloc>::
 457       _M_push_front_aux(const value_type& __t)
 458 #endif
 459       {
 460         _M_reserve_map_at_front();
 461         *(this->_M_impl._M_start._M_node - 1) = this->_M_allocate_node();
 462         __try
 463           {
 464             this->_M_impl._M_start._M_set_node(this->_M_impl._M_start._M_node
 465                                                - 1);
 466             this->_M_impl._M_start._M_cur = this->_M_impl._M_start._M_last - 1;
 467 #ifdef __GXX_EXPERIMENTAL_CXX0X__
 468             this->_M_impl.construct(this->_M_impl._M_start._M_cur,
 469                                     std::forward<_Args>(__args)...);
 470 #else
 471             this->_M_impl.construct(this->_M_impl._M_start._M_cur, __t);
 472 #endif
 473           }
 474         __catch(...)
 475           {
 476             ++this->_M_impl._M_start;
 477             _M_deallocate_node(*(this->_M_impl._M_start._M_node - 1));
 478             __throw_exception_again;
 479           }
 480       }
 481
 482   // Called only if _M_impl._M_finish._M_cur == _M_impl._M_finish._M_first.
 483   template <typename _Tp, typename _Alloc>
 484     void deque<_Tp, _Alloc>::
 485     _M_pop_back_aux()
 486     {
 487       _M_deallocate_node(this->_M_impl._M_finish._M_first);
 488       this->_M_impl._M_finish._M_set_node(this->_M_impl._M_finish._M_node - 1);
 489       this->_M_impl._M_finish._M_cur = this->_M_impl._M_finish._M_last - 1;
 490       this->_M_impl.destroy(this->_M_impl._M_finish._M_cur);
 491     }
 492
 493   // Called only if _M_impl._M_start._M_cur == _M_impl._M_start._M_last - 1.
 494   // Note that if the deque has at least one element (a precondition for this
 495   // member function), and if
 496   //   _M_impl._M_start._M_cur == _M_impl._M_start._M_last,
 497   // then the deque must have at least two nodes.
 498   template <typename _Tp, typename _Alloc>
 499     void deque<_Tp, _Alloc>::
 500     _M_pop_front_aux()
 501     {
 502       this->_M_impl.destroy(this->_M_impl._M_start._M_cur);
 503       _M_deallocate_node(this->_M_impl._M_start._M_first);
 504       this->_M_impl._M_start._M_set_node(this->_M_impl._M_start._M_node + 1);
 505       this->_M_impl._M_start._M_cur = this->_M_impl._M_start._M_first;
 506     }
 507
 508   template <typename _Tp, typename _Alloc>
 509     template <typename _InputIterator>
 510       void
 511       deque<_Tp, _Alloc>::
 512       _M_range_insert_aux(iterator __pos,
 513                           _InputIterator __first, _InputIterator __last,
 514                           std::input_iterator_tag)
 515       { std::copy(__first, __last, std::inserter(*this, __pos)); }
 516
 517   template <typename _Tp, typename _Alloc>
 518     template <typename _ForwardIterator>
 519       void
 520       deque<_Tp, _Alloc>::
 521       _M_range_insert_aux(iterator __pos,
 522                           _ForwardIterator __first, _ForwardIterator __last,
 523                           std::forward_iterator_tag)
 524       {
 525         const size_type __n = std::distance(__first, __last);
 526         if (__pos._M_cur == this->_M_impl._M_start._M_cur)
 527           {
 528             iterator __new_start = _M_reserve_elements_at_front(__n);
 529             __try
 530               {
 531                 std::__uninitialized_copy_a(__first, __last, __new_start,
 532                                             _M_get_Tp_allocator());
 533                 this->_M_impl._M_start = __new_start;
 534               }
 535             __catch(...)
 536               {
 537                 _M_destroy_nodes(__new_start._M_node,
 538                                  this->_M_impl._M_start._M_node);
 539                 __throw_exception_again;
 540               }
 541           }
 542         else if (__pos._M_cur == this->_M_impl._M_finish._M_cur)
 543           {
 544             iterator __new_finish = _M_reserve_elements_at_back(__n);
 545             __try
 546               {
 547                 std::__uninitialized_copy_a(__first, __last,
 548                                             this->_M_impl._M_finish,
 549                                             _M_get_Tp_allocator());
 550                 this->_M_impl._M_finish = __new_finish;
 551               }
 552             __catch(...)
 553               {
 554                 _M_destroy_nodes(this->_M_impl._M_finish._M_node + 1,
 555                                  __new_finish._M_node + 1);
 556                 __throw_exception_again;
 557               }
 558           }
 559         else
 560           _M_insert_aux(__pos, __first, __last, __n);
 561       }
 562
 563   template<typename _Tp, typename _Alloc>
 564 #ifdef __GXX_EXPERIMENTAL_CXX0X__
 565     template<typename... _Args>
 566       typename deque<_Tp, _Alloc>::iterator
 567       deque<_Tp, _Alloc>::
 568       _M_insert_aux(iterator __pos, _Args&&... __args)
 569       {
 570         value_type __x_copy(std::forward<_Args>(__args)...); // XXX copy
 571 #else
 572     typename deque<_Tp, _Alloc>::iterator
 573       deque<_Tp, _Alloc>::
 574       _M_insert_aux(iterator __pos, const value_type& __x)
 575       {
 576         value_type __x_copy = __x; // XXX copy
 577 #endif
 578         difference_type __index = __pos - this->_M_impl._M_start;
 579         if (static_cast<size_type>(__index) < size() / 2)
 580           {
 581             push_front(_GLIBCXX_MOVE(front()));
 582             iterator __front1 = this->_M_impl._M_start;
 583             ++__front1;
 584             iterator __front2 = __front1;
 585             ++__front2;
 586             __pos = this->_M_impl._M_start + __index;
 587             iterator __pos1 = __pos;
 588             ++__pos1;
 589             _GLIBCXX_MOVE3(__front2, __pos1, __front1);
 590           }
 591         else
 592           {
 593             push_back(_GLIBCXX_MOVE(back()));
 594             iterator __back1 = this->_M_impl._M_finish;
 595             --__back1;
 596             iterator __back2 = __back1;
 597             --__back2;
 598             __pos = this->_M_impl._M_start + __index;
 599             _GLIBCXX_MOVE_BACKWARD3(__pos, __back2, __back1);
 600           }
 601         *__pos = _GLIBCXX_MOVE(__x_copy);
 602         return __pos;
 603       }
 604
 605   template <typename _Tp, typename _Alloc>
 606     void
 607     deque<_Tp, _Alloc>::
 608     _M_insert_aux(iterator __pos, size_type __n, const value_type& __x)
 609     {
 610       const difference_type __elems_before = __pos - this->_M_impl._M_start;
 611       const size_type __length = this->size();
 612       value_type __x_copy = __x;
 613       if (__elems_before < difference_type(__length / 2))
 614         {
 615           iterator __new_start = _M_reserve_elements_at_front(__n);
 616           iterator __old_start = this->_M_impl._M_start;
 617           __pos = this->_M_impl._M_start + __elems_before;
 618           __try
 619             {
 620               if (__elems_before >= difference_type(__n))
 621                 {
 622                   iterator __start_n = (this->_M_impl._M_start
 623                                         + difference_type(__n));
 624                   std::__uninitialized_move_a(this->_M_impl._M_start,
 625                                               __start_n, __new_start,
 626                                               _M_get_Tp_allocator());
 627                   this->_M_impl._M_start = __new_start;
 628                   _GLIBCXX_MOVE3(__start_n, __pos, __old_start);
 629                   std::fill(__pos - difference_type(__n), __pos, __x_copy);
 630                 }
 631               else
 632                 {
 633                   std::__uninitialized_move_fill(this->_M_impl._M_start,
 634                                                  __pos, __new_start,
 635                                                  this->_M_impl._M_start,
 636                                                  __x_copy,
 637                                                  _M_get_Tp_allocator());
 638                   this->_M_impl._M_start = __new_start;
 639                   std::fill(__old_start, __pos, __x_copy);
 640                 }
 641             }
 642           __catch(...)
 643             {
 644               _M_destroy_nodes(__new_start._M_node,
 645                                this->_M_impl._M_start._M_node);
 646               __throw_exception_again;
 647             }
 648         }
 649       else
 650         {
 651           iterator __new_finish = _M_reserve_elements_at_back(__n);
 652           iterator __old_finish = this->_M_impl._M_finish;
 653           const difference_type __elems_after =
 654             difference_type(__length) - __elems_before;
 655           __pos = this->_M_impl._M_finish - __elems_after;
 656           __try
 657             {
 658               if (__elems_after > difference_type(__n))
 659                 {
 660                   iterator __finish_n = (this->_M_impl._M_finish
 661                                          - difference_type(__n));
 662                   std::__uninitialized_move_a(__finish_n,
 663                                               this->_M_impl._M_finish,
 664                                               this->_M_impl._M_finish,
 665                                               _M_get_Tp_allocator());
 666                   this->_M_impl._M_finish = __new_finish;
 667                   _GLIBCXX_MOVE_BACKWARD3(__pos, __finish_n, __old_finish);
 668                   std::fill(__pos, __pos + difference_type(__n), __x_copy);
 669                 }
 670               else
 671                 {
 672                   std::__uninitialized_fill_move(this->_M_impl._M_finish,
 673                                                  __pos + difference_type(__n),
 674                                                  __x_copy, __pos,
 675                                                  this->_M_impl._M_finish,
 676                                                  _M_get_Tp_allocator());
 677                   this->_M_impl._M_finish = __new_finish;
 678                   std::fill(__pos, __old_finish, __x_copy);
 679                 }
 680             }
 681           __catch(...)
 682             {
 683               _M_destroy_nodes(this->_M_impl._M_finish._M_node + 1,
 684                                __new_finish._M_node + 1);
 685               __throw_exception_again;
 686             }
 687         }
 688     }
 689
 690   template <typename _Tp, typename _Alloc>
 691     template <typename _ForwardIterator>
 692       void
 693       deque<_Tp, _Alloc>::
 694       _M_insert_aux(iterator __pos,
 695                     _ForwardIterator __first, _ForwardIterator __last,
 696                     size_type __n)
 697       {
 698         const difference_type __elemsbefore = __pos - this->_M_impl._M_start;
 699         const size_type __length = size();
 700         if (static_cast<size_type>(__elemsbefore) < __length / 2)
 701           {
 702             iterator __new_start = _M_reserve_elements_at_front(__n);
 703             iterator __old_start = this->_M_impl._M_start;
 704             __pos = this->_M_impl._M_start + __elemsbefore;
 705             __try
 706               {
 707                 if (__elemsbefore >= difference_type(__n))
 708                   {
 709                     iterator __start_n = (this->_M_impl._M_start
 710                                           + difference_type(__n));
 711                     std::__uninitialized_move_a(this->_M_impl._M_start,
 712                                                 __start_n, __new_start,
 713                                                 _M_get_Tp_allocator());
 714                     this->_M_impl._M_start = __new_start;
 715                     _GLIBCXX_MOVE3(__start_n, __pos, __old_start);
 716                     std::copy(__first, __last, __pos - difference_type(__n));
 717                   }
 718                 else
 719                   {
 720                     _ForwardIterator __mid = __first;
 721                     std::advance(__mid, difference_type(__n) - __elemsbefore);
 722                     std::__uninitialized_move_copy(this->_M_impl._M_start,
 723                                                    __pos, __first, __mid,
 724                                                    __new_start,
 725                                                    _M_get_Tp_allocator());
 726                     this->_M_impl._M_start = __new_start;
 727                     std::copy(__mid, __last, __old_start);
 728                   }
 729               }
 730             __catch(...)
 731               {
 732                 _M_destroy_nodes(__new_start._M_node,
 733                                  this->_M_impl._M_start._M_node);
 734                 __throw_exception_again;
 735               }
 736           }
 737         else
 738         {
 739           iterator __new_finish = _M_reserve_elements_at_back(__n);
 740           iterator __old_finish = this->_M_impl._M_finish;
 741           const difference_type __elemsafter =
 742             difference_type(__length) - __elemsbefore;
 743           __pos = this->_M_impl._M_finish - __elemsafter;
 744           __try
 745             {
 746               if (__elemsafter > difference_type(__n))
 747                 {
 748                   iterator __finish_n = (this->_M_impl._M_finish
 749                                          - difference_type(__n));
 750                   std::__uninitialized_move_a(__finish_n,
 751                                               this->_M_impl._M_finish,
 752                                               this->_M_impl._M_finish,
 753                                               _M_get_Tp_allocator());
 754                   this->_M_impl._M_finish = __new_finish;
 755                   _GLIBCXX_MOVE_BACKWARD3(__pos, __finish_n, __old_finish);
 756                   std::copy(__first, __last, __pos);
 757                 }
 758               else
 759                 {
 760                   _ForwardIterator __mid = __first;
 761                   std::advance(__mid, __elemsafter);
 762                   std::__uninitialized_copy_move(__mid, __last, __pos,
 763                                                  this->_M_impl._M_finish,
 764                                                  this->_M_impl._M_finish,
 765                                                  _M_get_Tp_allocator());
 766                   this->_M_impl._M_finish = __new_finish;
 767                   std::copy(__first, __mid, __pos);
 768                 }
 769             }
 770           __catch(...)
 771             {
 772               _M_destroy_nodes(this->_M_impl._M_finish._M_node + 1,
 773                                __new_finish._M_node + 1);
 774               __throw_exception_again;
 775             }
 776         }
 777       }
 778
 779    template<typename _Tp, typename _Alloc>
 780      void
 781      deque<_Tp, _Alloc>::
 782      _M_destroy_data_aux(iterator __first, iterator __last)
 783      {
 784        for (_Map_pointer __node = __first._M_node + 1;
 785             __node < __last._M_node; ++__node)
 786          std::_Destroy(*__node, *__node + _S_buffer_size(),
 787                        _M_get_Tp_allocator());
 788
 789        if (__first._M_node != __last._M_node)
 790          {
 791            std::_Destroy(__first._M_cur, __first._M_last,
 792                          _M_get_Tp_allocator());
 793            std::_Destroy(__last._M_first, __last._M_cur,
 794                          _M_get_Tp_allocator());
 795          }
 796        else
 797          std::_Destroy(__first._M_cur, __last._M_cur,
 798                        _M_get_Tp_allocator());
 799      }
 800
 801   template <typename _Tp, typename _Alloc>
 802     void
 803     deque<_Tp, _Alloc>::
 804     _M_new_elements_at_front(size_type __new_elems)
 805     {
 806       if (this->max_size() - this->size() < __new_elems)
 807         __throw_length_error(__N("deque::_M_new_elements_at_front"));
 808
 809       const size_type __new_nodes = ((__new_elems + _S_buffer_size() - 1)
 810                                      / _S_buffer_size());
 811       _M_reserve_map_at_front(__new_nodes);
 812       size_type __i;
 813       __try
 814         {
 815           for (__i = 1; __i <= __new_nodes; ++__i)
 816             *(this->_M_impl._M_start._M_node - __i) = this->_M_allocate_node();
 817         }
 818       __catch(...)
 819         {
 820           for (size_type __j = 1; __j < __i; ++__j)
 821             _M_deallocate_node(*(this->_M_impl._M_start._M_node - __j));
 822           __throw_exception_again;
 823         }
 824     }
 825
 826   template <typename _Tp, typename _Alloc>
 827     void
 828     deque<_Tp, _Alloc>::
 829     _M_new_elements_at_back(size_type __new_elems)
 830     {
 831       if (this->max_size() - this->size() < __new_elems)
 832         __throw_length_error(__N("deque::_M_new_elements_at_back"));
 833
 834       const size_type __new_nodes = ((__new_elems + _S_buffer_size() - 1)
 835                                      / _S_buffer_size());
 836       _M_reserve_map_at_back(__new_nodes);
 837       size_type __i;
 838       __try
 839         {
 840           for (__i = 1; __i <= __new_nodes; ++__i)
 841             *(this->_M_impl._M_finish._M_node + __i) = this->_M_allocate_node();
 842         }
 843       __catch(...)
 844         {
 845           for (size_type __j = 1; __j < __i; ++__j)
 846             _M_deallocate_node(*(this->_M_impl._M_finish._M_node + __j));
 847           __throw_exception_again;
 848         }
 849     }
 850
 851   template <typename _Tp, typename _Alloc>
 852     void
 853     deque<_Tp, _Alloc>::
 854     _M_reallocate_map(size_type __nodes_to_add, bool __add_at_front)
 855     {
 856       const size_type __old_num_nodes
 857         = this->_M_impl._M_finish._M_node - this->_M_impl._M_start._M_node + 1;
 858       const size_type __new_num_nodes = __old_num_nodes + __nodes_to_add;
 859
 860       _Map_pointer __new_nstart;
 861       if (this->_M_impl._M_map_size > 2 * __new_num_nodes)
 862         {
 863           __new_nstart = this->_M_impl._M_map + (this->_M_impl._M_map_size
 864                                          - __new_num_nodes) / 2
 865                          + (__add_at_front ? __nodes_to_add : 0);
 866           if (__new_nstart < this->_M_impl._M_start._M_node)
 867             std::copy(this->_M_impl._M_start._M_node,
 868                       this->_M_impl._M_finish._M_node + 1,
 869                       __new_nstart);
 870           else
 871             std::copy_backward(this->_M_impl._M_start._M_node,
 872                                this->_M_impl._M_finish._M_node + 1,
 873                                __new_nstart + __old_num_nodes);
 874         }
 875       else
 876         {
 877           size_type __new_map_size = this->_M_impl._M_map_size
 878                                      + std::max(this->_M_impl._M_map_size,
 879                                                 __nodes_to_add) + 2;
 880
 881           _Map_pointer __new_map = this->_M_allocate_map(__new_map_size);
 882           __new_nstart = __new_map + (__new_map_size - __new_num_nodes) / 2
 883                          + (__add_at_front ? __nodes_to_add : 0);
 884           std::copy(this->_M_impl._M_start._M_node,
 885                     this->_M_impl._M_finish._M_node + 1,
 886                     __new_nstart);
 887           _M_deallocate_map(this->_M_impl._M_map, this->_M_impl._M_map_size);
 888
 889           this->_M_impl._M_map = __new_map;
 890           this->_M_impl._M_map_size = __new_map_size;
 891         }
 892
 893       this->_M_impl._M_start._M_set_node(__new_nstart);
 894       this->_M_impl._M_finish._M_set_node(__new_nstart + __old_num_nodes - 1);
 895     }
 896
 897   // Overload for deque::iterators, exploiting the "segmented-iterator
 898   // optimization".
 899   template<typename _Tp>
 900     void
 901     fill(const _Deque_iterator<_Tp, _Tp&, _Tp*>& __first,
 902          const _Deque_iterator<_Tp, _Tp&, _Tp*>& __last, const _Tp& __value)
 903     {
 904       typedef typename _Deque_iterator<_Tp, _Tp&, _Tp*>::_Self _Self;
 905
 906       for (typename _Self::_Map_pointer __node = __first._M_node + 1;
 907            __node < __last._M_node; ++__node)
 908         std::fill(*__node, *__node + _Self::_S_buffer_size(), __value);
 909
 910       if (__first._M_node != __last._M_node)
 911         {
 912           std::fill(__first._M_cur, __first._M_last, __value);
 913           std::fill(__last._M_first, __last._M_cur, __value);
 914         }
 915       else
 916         std::fill(__first._M_cur, __last._M_cur, __value);
 917     }
 918
 919   template<typename _Tp>
 920     _Deque_iterator<_Tp, _Tp&, _Tp*>
 921     copy(_Deque_iterator<_Tp, const _Tp&, const _Tp*> __first,
 922          _Deque_iterator<_Tp, const _Tp&, const _Tp*> __last,
 923          _Deque_iterator<_Tp, _Tp&, _Tp*> __result)
 924     {
 925       typedef typename _Deque_iterator<_Tp, _Tp&, _Tp*>::_Self _Self;
 926       typedef typename _Self::difference_type difference_type;
 927
 928       difference_type __len = __last - __first;
 929       while (__len > 0)
 930         {
 931           const difference_type __clen
 932             = std::min(__len, std::min(__first._M_last - __first._M_cur,
 933                                        __result._M_last - __result._M_cur));
 934           std::copy(__first._M_cur, __first._M_cur + __clen, __result._M_cur);
 935           __first += __clen;
 936           __result += __clen;
 937           __len -= __clen;
 938         }
 939       return __result;
 940     }
 941
 942   template<typename _Tp>
 943     _Deque_iterator<_Tp, _Tp&, _Tp*>
 944     copy_backward(_Deque_iterator<_Tp, const _Tp&, const _Tp*> __first,
 945                   _Deque_iterator<_Tp, const _Tp&, const _Tp*> __last,
 946                   _Deque_iterator<_Tp, _Tp&, _Tp*> __result)
 947     {
 948       typedef typename _Deque_iterator<_Tp, _Tp&, _Tp*>::_Self _Self;
 949       typedef typename _Self::difference_type difference_type;
 950
 951       difference_type __len = __last - __first;
 952       while (__len > 0)
 953         {
 954           difference_type __llen = __last._M_cur - __last._M_first;
 955           _Tp* __lend = __last._M_cur;
 956
 957           difference_type __rlen = __result._M_cur - __result._M_first;
 958           _Tp* __rend = __result._M_cur;
 959
 960           if (!__llen)
 961             {
 962               __llen = _Self::_S_buffer_size();
 963               __lend = *(__last._M_node - 1) + __llen;
 964             }
 965           if (!__rlen)
 966             {
 967               __rlen = _Self::_S_buffer_size();
 968               __rend = *(__result._M_node - 1) + __rlen;
 969             }
 970
 971           const difference_type __clen = std::min(__len,
 972                                                   std::min(__llen, __rlen));
 973           std::copy_backward(__lend - __clen, __lend, __rend);
 974           __last -= __clen;
 975           __result -= __clen;
 976           __len -= __clen;
 977         }
 978       return __result;
 979     }
 980
 981 #ifdef __GXX_EXPERIMENTAL_CXX0X__
 982   template<typename _Tp>
 983     _Deque_iterator<_Tp, _Tp&, _Tp*>
 984     move(_Deque_iterator<_Tp, const _Tp&, const _Tp*> __first,
 985          _Deque_iterator<_Tp, const _Tp&, const _Tp*> __last,
 986          _Deque_iterator<_Tp, _Tp&, _Tp*> __result)
 987     {
 988       typedef typename _Deque_iterator<_Tp, _Tp&, _Tp*>::_Self _Self;
 989       typedef typename _Self::difference_type difference_type;
 990
 991       difference_type __len = __last - __first;
 992       while (__len > 0)
 993         {
 994           const difference_type __clen
 995             = std::min(__len, std::min(__first._M_last - __first._M_cur,
 996                                        __result._M_last - __result._M_cur));
 997           std::move(__first._M_cur, __first._M_cur + __clen, __result._M_cur);
 998           __first += __clen;
 999           __result += __clen;
1000           __len -= __clen;
1001         }
1002       return __result;
1003     }
1004
1005   template<typename _Tp>
1006     _Deque_iterator<_Tp, _Tp&, _Tp*>
1007     move_backward(_Deque_iterator<_Tp, const _Tp&, const _Tp*> __first,
1008                   _Deque_iterator<_Tp, const _Tp&, const _Tp*> __last,
1009                   _Deque_iterator<_Tp, _Tp&, _Tp*> __result)
1010     {
1011       typedef typename _Deque_iterator<_Tp, _Tp&, _Tp*>::_Self _Self;
1012       typedef typename _Self::difference_type difference_type;
1013
1014       difference_type __len = __last - __first;
1015       while (__len > 0)
1016         {
1017           difference_type __llen = __last._M_cur - __last._M_first;
1018           _Tp* __lend = __last._M_cur;
1019
1020           difference_type __rlen = __result._M_cur - __result._M_first;
1021           _Tp* __rend = __result._M_cur;
1022
1023           if (!__llen)
1024             {
1025               __llen = _Self::_S_buffer_size();
1026               __lend = *(__last._M_node - 1) + __llen;
1027             }
1028           if (!__rlen)
1029             {
1030               __rlen = _Self::_S_buffer_size();
1031               __rend = *(__result._M_node - 1) + __rlen;
1032             }
1033
1034           const difference_type __clen = std::min(__len,
1035                                                   std::min(__llen, __rlen));
1036           std::move_backward(__lend - __clen, __lend, __rend);
1037           __last -= __clen;
1038           __result -= __clen;
1039           __len -= __clen;
1040         }
1041       return __result;
1042     }
1043 #endif
1044
1045 _GLIBCXX_END_NAMESPACE_CONTAINER
1046 } // namespace std
1047
1048 #endif