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