OSDN Git Service

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