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 == begin() && __last == end())
 222         {
 223           clear();
 224           return end();
 225         }
 226       else
 227         {
 228           const difference_type __n = __last - __first;
 229           const difference_type __elems_before = __first - begin();
 230           if (static_cast<size_type>(__elems_before) <= (size() - __n) / 2)
 231             {
 232               if (__first != begin())
 233                 _GLIBCXX_MOVE_BACKWARD3(begin(), __first, __last);
 234               _M_erase_at_begin(begin() + __n);
 235             }
 236           else
 237             {
 238               if (__last != end())
 239                 _GLIBCXX_MOVE3(__last, end(), __first);
 240               _M_erase_at_end(end() - __n);
 241             }
 242           return begin() + __elems_before;
 243         }
 244     }
 245
 246   template <typename _Tp, class _Alloc>
 247     template <typename _InputIterator>
 248       void
 249       deque<_Tp, _Alloc>::
 250       _M_assign_aux(_InputIterator __first, _InputIterator __last,
 251                     std::input_iterator_tag)
 252       {
 253         iterator __cur = begin();
 254         for (; __first != __last && __cur != end(); ++__cur, ++__first)
 255           *__cur = *__first;
 256         if (__first == __last)
 257           _M_erase_at_end(__cur);
 258         else
 259           insert(end(), __first, __last);
 260       }
 261
 262   template <typename _Tp, typename _Alloc>
 263     void
 264     deque<_Tp, _Alloc>::
 265     _M_fill_insert(iterator __pos, size_type __n, const value_type& __x)
 266     {
 267       if (__pos._M_cur == this->_M_impl._M_start._M_cur)
 268         {
 269           iterator __new_start = _M_reserve_elements_at_front(__n);
 270           __try
 271             {
 272               std::__uninitialized_fill_a(__new_start, this->_M_impl._M_start,
 273                                           __x, _M_get_Tp_allocator());
 274               this->_M_impl._M_start = __new_start;
 275             }
 276           __catch(...)
 277             {
 278               _M_destroy_nodes(__new_start._M_node,
 279                                this->_M_impl._M_start._M_node);
 280               __throw_exception_again;
 281             }
 282         }
 283       else if (__pos._M_cur == this->_M_impl._M_finish._M_cur)
 284         {
 285           iterator __new_finish = _M_reserve_elements_at_back(__n);
 286           __try
 287             {
 288               std::__uninitialized_fill_a(this->_M_impl._M_finish,
 289                                           __new_finish, __x,
 290                                           _M_get_Tp_allocator());
 291               this->_M_impl._M_finish = __new_finish;
 292             }
 293           __catch(...)
 294             {
 295               _M_destroy_nodes(this->_M_impl._M_finish._M_node + 1,
 296                                __new_finish._M_node + 1);
 297               __throw_exception_again;
 298             }
 299         }
 300       else
 301         _M_insert_aux(__pos, __n, __x);
 302     }
 303
 304 #ifdef __GXX_EXPERIMENTAL_CXX0X__
 305   template <typename _Tp, typename _Alloc>
 306     void
 307     deque<_Tp, _Alloc>::
 308     _M_default_append(size_type __n)
 309     {
 310       if (__n)
 311         {
 312           iterator __new_finish = _M_reserve_elements_at_back(__n);
 313           __try
 314             {
 315               std::__uninitialized_default_a(this->_M_impl._M_finish,
 316                                              __new_finish,
 317                                              _M_get_Tp_allocator());
 318               this->_M_impl._M_finish = __new_finish;
 319             }
 320           __catch(...)
 321             {
 322               _M_destroy_nodes(this->_M_impl._M_finish._M_node + 1,
 323                                __new_finish._M_node + 1);
 324               __throw_exception_again;
 325             }
 326         }
 327     }
 328 #endif
 329
 330   template <typename _Tp, typename _Alloc>
 331     void
 332     deque<_Tp, _Alloc>::
 333     _M_fill_initialize(const value_type& __value)
 334     {
 335       _Map_pointer __cur;
 336       __try
 337         {
 338           for (__cur = this->_M_impl._M_start._M_node;
 339                __cur < this->_M_impl._M_finish._M_node;
 340                ++__cur)
 341             std::__uninitialized_fill_a(*__cur, *__cur + _S_buffer_size(),
 342                                         __value, _M_get_Tp_allocator());
 343           std::__uninitialized_fill_a(this->_M_impl._M_finish._M_first,
 344                                       this->_M_impl._M_finish._M_cur,
 345                                       __value, _M_get_Tp_allocator());
 346         }
 347       __catch(...)
 348         {
 349           std::_Destroy(this->_M_impl._M_start, iterator(*__cur, __cur),
 350                         _M_get_Tp_allocator());
 351           __throw_exception_again;
 352         }
 353     }
 354
 355   template <typename _Tp, typename _Alloc>
 356     template <typename _InputIterator>
 357       void
 358       deque<_Tp, _Alloc>::
 359       _M_range_initialize(_InputIterator __first, _InputIterator __last,
 360                           std::input_iterator_tag)
 361       {
 362         this->_M_initialize_map(0);
 363         __try
 364           {
 365             for (; __first != __last; ++__first)
 366               push_back(*__first);
 367           }
 368         __catch(...)
 369           {
 370             clear();
 371             __throw_exception_again;
 372           }
 373       }
 374
 375   template <typename _Tp, typename _Alloc>
 376     template <typename _ForwardIterator>
 377       void
 378       deque<_Tp, _Alloc>::
 379       _M_range_initialize(_ForwardIterator __first, _ForwardIterator __last,
 380                           std::forward_iterator_tag)
 381       {
 382         const size_type __n = std::distance(__first, __last);
 383         this->_M_initialize_map(__n);
 384
 385         _Map_pointer __cur_node;
 386         __try
 387           {
 388             for (__cur_node = this->_M_impl._M_start._M_node;
 389                  __cur_node < this->_M_impl._M_finish._M_node;
 390                  ++__cur_node)
 391               {
 392                 _ForwardIterator __mid = __first;
 393                 std::advance(__mid, _S_buffer_size());
 394                 std::__uninitialized_copy_a(__first, __mid, *__cur_node,
 395                                             _M_get_Tp_allocator());
 396                 __first = __mid;
 397               }
 398             std::__uninitialized_copy_a(__first, __last,
 399                                         this->_M_impl._M_finish._M_first,
 400                                         _M_get_Tp_allocator());
 401           }
 402         __catch(...)
 403           {
 404             std::_Destroy(this->_M_impl._M_start,
 405                           iterator(*__cur_node, __cur_node),
 406                           _M_get_Tp_allocator());
 407             __throw_exception_again;
 408           }
 409       }
 410
 411   // Called only if _M_impl._M_finish._M_cur == _M_impl._M_finish._M_last - 1.
 412   template<typename _Tp, typename _Alloc>
 413 #ifdef __GXX_EXPERIMENTAL_CXX0X__
 414     template<typename... _Args>
 415       void
 416       deque<_Tp, _Alloc>::
 417       _M_push_back_aux(_Args&&... __args)
 418 #else
 419       void
 420       deque<_Tp, _Alloc>::
 421       _M_push_back_aux(const value_type& __t)
 422 #endif
 423       {
 424         _M_reserve_map_at_back();
 425         *(this->_M_impl._M_finish._M_node + 1) = this->_M_allocate_node();
 426         __try
 427           {
 428 #ifdef __GXX_EXPERIMENTAL_CXX0X__
 429             this->_M_impl.construct(this->_M_impl._M_finish._M_cur,
 430                                     std::forward<_Args>(__args)...);
 431 #else
 432             this->_M_impl.construct(this->_M_impl._M_finish._M_cur, __t);
 433 #endif
 434             this->_M_impl._M_finish._M_set_node(this->_M_impl._M_finish._M_node
 435                                                 + 1);
 436             this->_M_impl._M_finish._M_cur = this->_M_impl._M_finish._M_first;
 437           }
 438         __catch(...)
 439           {
 440             _M_deallocate_node(*(this->_M_impl._M_finish._M_node + 1));
 441             __throw_exception_again;
 442           }
 443       }
 444
 445   // Called only if _M_impl._M_start._M_cur == _M_impl._M_start._M_first.
 446   template<typename _Tp, typename _Alloc>
 447 #ifdef __GXX_EXPERIMENTAL_CXX0X__
 448     template<typename... _Args>
 449       void
 450       deque<_Tp, _Alloc>::
 451       _M_push_front_aux(_Args&&... __args)
 452 #else
 453       void
 454       deque<_Tp, _Alloc>::
 455       _M_push_front_aux(const value_type& __t)
 456 #endif
 457       {
 458         _M_reserve_map_at_front();
 459         *(this->_M_impl._M_start._M_node - 1) = this->_M_allocate_node();
 460         __try
 461           {
 462             this->_M_impl._M_start._M_set_node(this->_M_impl._M_start._M_node
 463                                                - 1);
 464             this->_M_impl._M_start._M_cur = this->_M_impl._M_start._M_last - 1;
 465 #ifdef __GXX_EXPERIMENTAL_CXX0X__
 466             this->_M_impl.construct(this->_M_impl._M_start._M_cur,
 467                                     std::forward<_Args>(__args)...);
 468 #else
 469             this->_M_impl.construct(this->_M_impl._M_start._M_cur, __t);
 470 #endif
 471           }
 472         __catch(...)
 473           {
 474             ++this->_M_impl._M_start;
 475             _M_deallocate_node(*(this->_M_impl._M_start._M_node - 1));
 476             __throw_exception_again;
 477           }
 478       }
 479
 480   // Called only if _M_impl._M_finish._M_cur == _M_impl._M_finish._M_first.
 481   template <typename _Tp, typename _Alloc>
 482     void deque<_Tp, _Alloc>::
 483     _M_pop_back_aux()
 484     {
 485       _M_deallocate_node(this->_M_impl._M_finish._M_first);
 486       this->_M_impl._M_finish._M_set_node(this->_M_impl._M_finish._M_node - 1);
 487       this->_M_impl._M_finish._M_cur = this->_M_impl._M_finish._M_last - 1;
 488       this->_M_impl.destroy(this->_M_impl._M_finish._M_cur);
 489     }
 490
 491   // Called only if _M_impl._M_start._M_cur == _M_impl._M_start._M_last - 1.
 492   // Note that if the deque has at least one element (a precondition for this
 493   // member function), and if
 494   //   _M_impl._M_start._M_cur == _M_impl._M_start._M_last,
 495   // then the deque must have at least two nodes.
 496   template <typename _Tp, typename _Alloc>
 497     void deque<_Tp, _Alloc>::
 498     _M_pop_front_aux()
 499     {
 500       this->_M_impl.destroy(this->_M_impl._M_start._M_cur);
 501       _M_deallocate_node(this->_M_impl._M_start._M_first);
 502       this->_M_impl._M_start._M_set_node(this->_M_impl._M_start._M_node + 1);
 503       this->_M_impl._M_start._M_cur = this->_M_impl._M_start._M_first;
 504     }
 505
 506   template <typename _Tp, typename _Alloc>
 507     template <typename _InputIterator>
 508       void
 509       deque<_Tp, _Alloc>::
 510       _M_range_insert_aux(iterator __pos,
 511                           _InputIterator __first, _InputIterator __last,
 512                           std::input_iterator_tag)
 513       { std::copy(__first, __last, std::inserter(*this, __pos)); }
 514
 515   template <typename _Tp, typename _Alloc>
 516     template <typename _ForwardIterator>
 517       void
 518       deque<_Tp, _Alloc>::
 519       _M_range_insert_aux(iterator __pos,
 520                           _ForwardIterator __first, _ForwardIterator __last,
 521                           std::forward_iterator_tag)
 522       {
 523         const size_type __n = std::distance(__first, __last);
 524         if (__pos._M_cur == this->_M_impl._M_start._M_cur)
 525           {
 526             iterator __new_start = _M_reserve_elements_at_front(__n);
 527             __try
 528               {
 529                 std::__uninitialized_copy_a(__first, __last, __new_start,
 530                                             _M_get_Tp_allocator());
 531                 this->_M_impl._M_start = __new_start;
 532               }
 533             __catch(...)
 534               {
 535                 _M_destroy_nodes(__new_start._M_node,
 536                                  this->_M_impl._M_start._M_node);
 537                 __throw_exception_again;
 538               }
 539           }
 540         else if (__pos._M_cur == this->_M_impl._M_finish._M_cur)
 541           {
 542             iterator __new_finish = _M_reserve_elements_at_back(__n);
 543             __try
 544               {
 545                 std::__uninitialized_copy_a(__first, __last,
 546                                             this->_M_impl._M_finish,
 547                                             _M_get_Tp_allocator());
 548                 this->_M_impl._M_finish = __new_finish;
 549               }
 550             __catch(...)
 551               {
 552                 _M_destroy_nodes(this->_M_impl._M_finish._M_node + 1,
 553                                  __new_finish._M_node + 1);
 554                 __throw_exception_again;
 555               }
 556           }
 557         else
 558           _M_insert_aux(__pos, __first, __last, __n);
 559       }
 560
 561   template<typename _Tp, typename _Alloc>
 562 #ifdef __GXX_EXPERIMENTAL_CXX0X__
 563     template<typename... _Args>
 564       typename deque<_Tp, _Alloc>::iterator
 565       deque<_Tp, _Alloc>::
 566       _M_insert_aux(iterator __pos, _Args&&... __args)
 567       {
 568         value_type __x_copy(std::forward<_Args>(__args)...); // XXX copy
 569 #else
 570     typename deque<_Tp, _Alloc>::iterator
 571       deque<_Tp, _Alloc>::
 572       _M_insert_aux(iterator __pos, const value_type& __x)
 573       {
 574         value_type __x_copy = __x; // XXX copy
 575 #endif
 576         difference_type __index = __pos - this->_M_impl._M_start;
 577         if (static_cast<size_type>(__index) < size() / 2)
 578           {
 579             push_front(_GLIBCXX_MOVE(front()));
 580             iterator __front1 = this->_M_impl._M_start;
 581             ++__front1;
 582             iterator __front2 = __front1;
 583             ++__front2;
 584             __pos = this->_M_impl._M_start + __index;
 585             iterator __pos1 = __pos;
 586             ++__pos1;
 587             _GLIBCXX_MOVE3(__front2, __pos1, __front1);
 588           }
 589         else
 590           {
 591             push_back(_GLIBCXX_MOVE(back()));
 592             iterator __back1 = this->_M_impl._M_finish;
 593             --__back1;
 594             iterator __back2 = __back1;
 595             --__back2;
 596             __pos = this->_M_impl._M_start + __index;
 597             _GLIBCXX_MOVE_BACKWARD3(__pos, __back2, __back1);
 598           }
 599         *__pos = _GLIBCXX_MOVE(__x_copy);
 600         return __pos;
 601       }
 602
 603   template <typename _Tp, typename _Alloc>
 604     void
 605     deque<_Tp, _Alloc>::
 606     _M_insert_aux(iterator __pos, size_type __n, const value_type& __x)
 607     {
 608       const difference_type __elems_before = __pos - this->_M_impl._M_start;
 609       const size_type __length = this->size();
 610       value_type __x_copy = __x;
 611       if (__elems_before < difference_type(__length / 2))
 612         {
 613           iterator __new_start = _M_reserve_elements_at_front(__n);
 614           iterator __old_start = this->_M_impl._M_start;
 615           __pos = this->_M_impl._M_start + __elems_before;
 616           __try
 617             {
 618               if (__elems_before >= difference_type(__n))
 619                 {
 620                   iterator __start_n = (this->_M_impl._M_start
 621                                         + difference_type(__n));
 622                   std::__uninitialized_move_a(this->_M_impl._M_start,
 623                                               __start_n, __new_start,
 624                                               _M_get_Tp_allocator());
 625                   this->_M_impl._M_start = __new_start;
 626                   _GLIBCXX_MOVE3(__start_n, __pos, __old_start);
 627                   std::fill(__pos - difference_type(__n), __pos, __x_copy);
 628                 }
 629               else
 630                 {
 631                   std::__uninitialized_move_fill(this->_M_impl._M_start,
 632                                                  __pos, __new_start,
 633                                                  this->_M_impl._M_start,
 634                                                  __x_copy,
 635                                                  _M_get_Tp_allocator());
 636                   this->_M_impl._M_start = __new_start;
 637                   std::fill(__old_start, __pos, __x_copy);
 638                 }
 639             }
 640           __catch(...)
 641             {
 642               _M_destroy_nodes(__new_start._M_node,
 643                                this->_M_impl._M_start._M_node);
 644               __throw_exception_again;
 645             }
 646         }
 647       else
 648         {
 649           iterator __new_finish = _M_reserve_elements_at_back(__n);
 650           iterator __old_finish = this->_M_impl._M_finish;
 651           const difference_type __elems_after =
 652             difference_type(__length) - __elems_before;
 653           __pos = this->_M_impl._M_finish - __elems_after;
 654           __try
 655             {
 656               if (__elems_after > difference_type(__n))
 657                 {
 658                   iterator __finish_n = (this->_M_impl._M_finish
 659                                          - difference_type(__n));
 660                   std::__uninitialized_move_a(__finish_n,
 661                                               this->_M_impl._M_finish,
 662                                               this->_M_impl._M_finish,
 663                                               _M_get_Tp_allocator());
 664                   this->_M_impl._M_finish = __new_finish;
 665                   _GLIBCXX_MOVE_BACKWARD3(__pos, __finish_n, __old_finish);
 666                   std::fill(__pos, __pos + difference_type(__n), __x_copy);
 667                 }
 668               else
 669                 {
 670                   std::__uninitialized_fill_move(this->_M_impl._M_finish,
 671                                                  __pos + difference_type(__n),
 672                                                  __x_copy, __pos,
 673                                                  this->_M_impl._M_finish,
 674                                                  _M_get_Tp_allocator());
 675                   this->_M_impl._M_finish = __new_finish;
 676                   std::fill(__pos, __old_finish, __x_copy);
 677                 }
 678             }
 679           __catch(...)
 680             {
 681               _M_destroy_nodes(this->_M_impl._M_finish._M_node + 1,
 682                                __new_finish._M_node + 1);
 683               __throw_exception_again;
 684             }
 685         }
 686     }
 687
 688   template <typename _Tp, typename _Alloc>
 689     template <typename _ForwardIterator>
 690       void
 691       deque<_Tp, _Alloc>::
 692       _M_insert_aux(iterator __pos,
 693                     _ForwardIterator __first, _ForwardIterator __last,
 694                     size_type __n)
 695       {
 696         const difference_type __elemsbefore = __pos - this->_M_impl._M_start;
 697         const size_type __length = size();
 698         if (static_cast<size_type>(__elemsbefore) < __length / 2)
 699           {
 700             iterator __new_start = _M_reserve_elements_at_front(__n);
 701             iterator __old_start = this->_M_impl._M_start;
 702             __pos = this->_M_impl._M_start + __elemsbefore;
 703             __try
 704               {
 705                 if (__elemsbefore >= difference_type(__n))
 706                   {
 707                     iterator __start_n = (this->_M_impl._M_start
 708                                           + difference_type(__n));
 709                     std::__uninitialized_move_a(this->_M_impl._M_start,
 710                                                 __start_n, __new_start,
 711                                                 _M_get_Tp_allocator());
 712                     this->_M_impl._M_start = __new_start;
 713                     _GLIBCXX_MOVE3(__start_n, __pos, __old_start);
 714                     std::copy(__first, __last, __pos - difference_type(__n));
 715                   }
 716                 else
 717                   {
 718                     _ForwardIterator __mid = __first;
 719                     std::advance(__mid, difference_type(__n) - __elemsbefore);
 720                     std::__uninitialized_move_copy(this->_M_impl._M_start,
 721                                                    __pos, __first, __mid,
 722                                                    __new_start,
 723                                                    _M_get_Tp_allocator());
 724                     this->_M_impl._M_start = __new_start;
 725                     std::copy(__mid, __last, __old_start);
 726                   }
 727               }
 728             __catch(...)
 729               {
 730                 _M_destroy_nodes(__new_start._M_node,
 731                                  this->_M_impl._M_start._M_node);
 732                 __throw_exception_again;
 733               }
 734           }
 735         else
 736         {
 737           iterator __new_finish = _M_reserve_elements_at_back(__n);
 738           iterator __old_finish = this->_M_impl._M_finish;
 739           const difference_type __elemsafter =
 740             difference_type(__length) - __elemsbefore;
 741           __pos = this->_M_impl._M_finish - __elemsafter;
 742           __try
 743             {
 744               if (__elemsafter > difference_type(__n))
 745                 {
 746                   iterator __finish_n = (this->_M_impl._M_finish
 747                                          - difference_type(__n));
 748                   std::__uninitialized_move_a(__finish_n,
 749                                               this->_M_impl._M_finish,
 750                                               this->_M_impl._M_finish,
 751                                               _M_get_Tp_allocator());
 752                   this->_M_impl._M_finish = __new_finish;
 753                   _GLIBCXX_MOVE_BACKWARD3(__pos, __finish_n, __old_finish);
 754                   std::copy(__first, __last, __pos);
 755                 }
 756               else
 757                 {
 758                   _ForwardIterator __mid = __first;
 759                   std::advance(__mid, __elemsafter);
 760                   std::__uninitialized_copy_move(__mid, __last, __pos,
 761                                                  this->_M_impl._M_finish,
 762                                                  this->_M_impl._M_finish,
 763                                                  _M_get_Tp_allocator());
 764                   this->_M_impl._M_finish = __new_finish;
 765                   std::copy(__first, __mid, __pos);
 766                 }
 767             }
 768           __catch(...)
 769             {
 770               _M_destroy_nodes(this->_M_impl._M_finish._M_node + 1,
 771                                __new_finish._M_node + 1);
 772               __throw_exception_again;
 773             }
 774         }
 775       }
 776
 777    template<typename _Tp, typename _Alloc>
 778      void
 779      deque<_Tp, _Alloc>::
 780      _M_destroy_data_aux(iterator __first, iterator __last)
 781      {
 782        for (_Map_pointer __node = __first._M_node + 1;
 783             __node < __last._M_node; ++__node)
 784          std::_Destroy(*__node, *__node + _S_buffer_size(),
 785                        _M_get_Tp_allocator());
 786
 787        if (__first._M_node != __last._M_node)
 788          {
 789            std::_Destroy(__first._M_cur, __first._M_last,
 790                          _M_get_Tp_allocator());
 791            std::_Destroy(__last._M_first, __last._M_cur,
 792                          _M_get_Tp_allocator());
 793          }
 794        else
 795          std::_Destroy(__first._M_cur, __last._M_cur,
 796                        _M_get_Tp_allocator());
 797      }
 798
 799   template <typename _Tp, typename _Alloc>
 800     void
 801     deque<_Tp, _Alloc>::
 802     _M_new_elements_at_front(size_type __new_elems)
 803     {
 804       if (this->max_size() - this->size() < __new_elems)
 805         __throw_length_error(__N("deque::_M_new_elements_at_front"));
 806
 807       const size_type __new_nodes = ((__new_elems + _S_buffer_size() - 1)
 808                                      / _S_buffer_size());
 809       _M_reserve_map_at_front(__new_nodes);
 810       size_type __i;
 811       __try
 812         {
 813           for (__i = 1; __i <= __new_nodes; ++__i)
 814             *(this->_M_impl._M_start._M_node - __i) = this->_M_allocate_node();
 815         }
 816       __catch(...)
 817         {
 818           for (size_type __j = 1; __j < __i; ++__j)
 819             _M_deallocate_node(*(this->_M_impl._M_start._M_node - __j));
 820           __throw_exception_again;
 821         }
 822     }
 823
 824   template <typename _Tp, typename _Alloc>
 825     void
 826     deque<_Tp, _Alloc>::
 827     _M_new_elements_at_back(size_type __new_elems)
 828     {
 829       if (this->max_size() - this->size() < __new_elems)
 830         __throw_length_error(__N("deque::_M_new_elements_at_back"));
 831
 832       const size_type __new_nodes = ((__new_elems + _S_buffer_size() - 1)
 833                                      / _S_buffer_size());
 834       _M_reserve_map_at_back(__new_nodes);
 835       size_type __i;
 836       __try
 837         {
 838           for (__i = 1; __i <= __new_nodes; ++__i)
 839             *(this->_M_impl._M_finish._M_node + __i) = this->_M_allocate_node();
 840         }
 841       __catch(...)
 842         {
 843           for (size_type __j = 1; __j < __i; ++__j)
 844             _M_deallocate_node(*(this->_M_impl._M_finish._M_node + __j));
 845           __throw_exception_again;
 846         }
 847     }
 848
 849   template <typename _Tp, typename _Alloc>
 850     void
 851     deque<_Tp, _Alloc>::
 852     _M_reallocate_map(size_type __nodes_to_add, bool __add_at_front)
 853     {
 854       const size_type __old_num_nodes
 855         = this->_M_impl._M_finish._M_node - this->_M_impl._M_start._M_node + 1;
 856       const size_type __new_num_nodes = __old_num_nodes + __nodes_to_add;
 857
 858       _Map_pointer __new_nstart;
 859       if (this->_M_impl._M_map_size > 2 * __new_num_nodes)
 860         {
 861           __new_nstart = this->_M_impl._M_map + (this->_M_impl._M_map_size
 862                                          - __new_num_nodes) / 2
 863                          + (__add_at_front ? __nodes_to_add : 0);
 864           if (__new_nstart < this->_M_impl._M_start._M_node)
 865             std::copy(this->_M_impl._M_start._M_node,
 866                       this->_M_impl._M_finish._M_node + 1,
 867                       __new_nstart);
 868           else
 869             std::copy_backward(this->_M_impl._M_start._M_node,
 870                                this->_M_impl._M_finish._M_node + 1,
 871                                __new_nstart + __old_num_nodes);
 872         }
 873       else
 874         {
 875           size_type __new_map_size = this->_M_impl._M_map_size
 876                                      + std::max(this->_M_impl._M_map_size,
 877                                                 __nodes_to_add) + 2;
 878
 879           _Map_pointer __new_map = this->_M_allocate_map(__new_map_size);
 880           __new_nstart = __new_map + (__new_map_size - __new_num_nodes) / 2
 881                          + (__add_at_front ? __nodes_to_add : 0);
 882           std::copy(this->_M_impl._M_start._M_node,
 883                     this->_M_impl._M_finish._M_node + 1,
 884                     __new_nstart);
 885           _M_deallocate_map(this->_M_impl._M_map, this->_M_impl._M_map_size);
 886
 887           this->_M_impl._M_map = __new_map;
 888           this->_M_impl._M_map_size = __new_map_size;
 889         }
 890
 891       this->_M_impl._M_start._M_set_node(__new_nstart);
 892       this->_M_impl._M_finish._M_set_node(__new_nstart + __old_num_nodes - 1);
 893     }
 894
 895   // Overload for deque::iterators, exploiting the "segmented-iterator
 896   // optimization".
 897   template<typename _Tp>
 898     void
 899     fill(const _Deque_iterator<_Tp, _Tp&, _Tp*>& __first,
 900          const _Deque_iterator<_Tp, _Tp&, _Tp*>& __last, const _Tp& __value)
 901     {
 902       typedef typename _Deque_iterator<_Tp, _Tp&, _Tp*>::_Self _Self;
 903
 904       for (typename _Self::_Map_pointer __node = __first._M_node + 1;
 905            __node < __last._M_node; ++__node)
 906         std::fill(*__node, *__node + _Self::_S_buffer_size(), __value);
 907
 908       if (__first._M_node != __last._M_node)
 909         {
 910           std::fill(__first._M_cur, __first._M_last, __value);
 911           std::fill(__last._M_first, __last._M_cur, __value);
 912         }
 913       else
 914         std::fill(__first._M_cur, __last._M_cur, __value);
 915     }
 916
 917   template<typename _Tp>
 918     _Deque_iterator<_Tp, _Tp&, _Tp*>
 919     copy(_Deque_iterator<_Tp, const _Tp&, const _Tp*> __first,
 920          _Deque_iterator<_Tp, const _Tp&, const _Tp*> __last,
 921          _Deque_iterator<_Tp, _Tp&, _Tp*> __result)
 922     {
 923       typedef typename _Deque_iterator<_Tp, _Tp&, _Tp*>::_Self _Self;
 924       typedef typename _Self::difference_type difference_type;
 925
 926       difference_type __len = __last - __first;
 927       while (__len > 0)
 928         {
 929           const difference_type __clen
 930             = std::min(__len, std::min(__first._M_last - __first._M_cur,
 931                                        __result._M_last - __result._M_cur));
 932           std::copy(__first._M_cur, __first._M_cur + __clen, __result._M_cur);
 933           __first += __clen;
 934           __result += __clen;
 935           __len -= __clen;
 936         }
 937       return __result;
 938     }
 939
 940   template<typename _Tp>
 941     _Deque_iterator<_Tp, _Tp&, _Tp*>
 942     copy_backward(_Deque_iterator<_Tp, const _Tp&, const _Tp*> __first,
 943                   _Deque_iterator<_Tp, const _Tp&, const _Tp*> __last,
 944                   _Deque_iterator<_Tp, _Tp&, _Tp*> __result)
 945     {
 946       typedef typename _Deque_iterator<_Tp, _Tp&, _Tp*>::_Self _Self;
 947       typedef typename _Self::difference_type difference_type;
 948
 949       difference_type __len = __last - __first;
 950       while (__len > 0)
 951         {
 952           difference_type __llen = __last._M_cur - __last._M_first;
 953           _Tp* __lend = __last._M_cur;
 954
 955           difference_type __rlen = __result._M_cur - __result._M_first;
 956           _Tp* __rend = __result._M_cur;
 957
 958           if (!__llen)
 959             {
 960               __llen = _Self::_S_buffer_size();
 961               __lend = *(__last._M_node - 1) + __llen;
 962             }
 963           if (!__rlen)
 964             {
 965               __rlen = _Self::_S_buffer_size();
 966               __rend = *(__result._M_node - 1) + __rlen;
 967             }
 968
 969           const difference_type __clen = std::min(__len,
 970                                                   std::min(__llen, __rlen));
 971           std::copy_backward(__lend - __clen, __lend, __rend);
 972           __last -= __clen;
 973           __result -= __clen;
 974           __len -= __clen;
 975         }
 976       return __result;
 977     }
 978
 979 #ifdef __GXX_EXPERIMENTAL_CXX0X__
 980   template<typename _Tp>
 981     _Deque_iterator<_Tp, _Tp&, _Tp*>
 982     move(_Deque_iterator<_Tp, const _Tp&, const _Tp*> __first,
 983          _Deque_iterator<_Tp, const _Tp&, const _Tp*> __last,
 984          _Deque_iterator<_Tp, _Tp&, _Tp*> __result)
 985     {
 986       typedef typename _Deque_iterator<_Tp, _Tp&, _Tp*>::_Self _Self;
 987       typedef typename _Self::difference_type difference_type;
 988
 989       difference_type __len = __last - __first;
 990       while (__len > 0)
 991         {
 992           const difference_type __clen
 993             = std::min(__len, std::min(__first._M_last - __first._M_cur,
 994                                        __result._M_last - __result._M_cur));
 995           std::move(__first._M_cur, __first._M_cur + __clen, __result._M_cur);
 996           __first += __clen;
 997           __result += __clen;
 998           __len -= __clen;
 999         }
1000       return __result;
1001     }
1002
1003   template<typename _Tp>
1004     _Deque_iterator<_Tp, _Tp&, _Tp*>
1005     move_backward(_Deque_iterator<_Tp, const _Tp&, const _Tp*> __first,
1006                   _Deque_iterator<_Tp, const _Tp&, const _Tp*> __last,
1007                   _Deque_iterator<_Tp, _Tp&, _Tp*> __result)
1008     {
1009       typedef typename _Deque_iterator<_Tp, _Tp&, _Tp*>::_Self _Self;
1010       typedef typename _Self::difference_type difference_type;
1011
1012       difference_type __len = __last - __first;
1013       while (__len > 0)
1014         {
1015           difference_type __llen = __last._M_cur - __last._M_first;
1016           _Tp* __lend = __last._M_cur;
1017
1018           difference_type __rlen = __result._M_cur - __result._M_first;
1019           _Tp* __rend = __result._M_cur;
1020
1021           if (!__llen)
1022             {
1023               __llen = _Self::_S_buffer_size();
1024               __lend = *(__last._M_node - 1) + __llen;
1025             }
1026           if (!__rlen)
1027             {
1028               __rlen = _Self::_S_buffer_size();
1029               __rend = *(__result._M_node - 1) + __rlen;
1030             }
1031
1032           const difference_type __clen = std::min(__len,
1033                                                   std::min(__llen, __rlen));
1034           std::move_backward(__lend - __clen, __lend, __rend);
1035           __last -= __clen;
1036           __result -= __clen;
1037           __len -= __clen;
1038         }
1039       return __result;
1040     }
1041 #endif
1042
1043 _GLIBCXX_END_NAMESPACE_CONTAINER
1044 } // namespace std
1045
1046 #endif