| blob | 7172223896468326a8b4a307153f72154eab518d |
1 // Deque implementation (out of line) -*- C++ -*-
3 // Copyright (C) 2001, 2002, 2003, 2004, 2005 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.
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.
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, 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301,
19 // USA.
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.
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 */
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 */
61 #ifndef _DEQUE_TCC
62 #define _DEQUE_TCC 1
64 namespace _GLIBCXX_STD
65 {
66 template <typename _Tp, typename _Alloc>
67 deque<_Tp, _Alloc>&
68 deque<_Tp, _Alloc>::
69 operator=(const deque& __x)
70 {
71 const size_type __len = size();
72 if (&__x != this)
73 {
74 if (__len >= __x.size())
75 erase(std::copy(__x.begin(), __x.end(), this->_M_impl._M_start),
76 this->_M_impl._M_finish);
77 else
78 {
79 const_iterator __mid = __x.begin() + difference_type(__len);
80 std::copy(__x.begin(), __mid, this->_M_impl._M_start);
81 insert(this->_M_impl._M_finish, __mid, __x.end());
82 }
83 }
84 return *this;
85 }
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 }
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 const 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 }
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
135 && __last == this->_M_impl._M_finish)
136 {
137 clear();
138 return this->_M_impl._M_finish;
139 }
140 else
141 {
142 const difference_type __n = __last - __first;
143 const difference_type __elems_before = (__first
144 - this->_M_impl._M_start);
145 if (static_cast<size_type>(__elems_before) < (size() - __n) / 2)
146 {
147 std::copy_backward(this->_M_impl._M_start, __first, __last);
148 iterator __new_start = this->_M_impl._M_start + __n;
149 std::_Destroy(this->_M_impl._M_start, __new_start,
150 _M_get_Tp_allocator());
151 _M_destroy_nodes(this->_M_impl._M_start._M_node,
152 __new_start._M_node);
153 this->_M_impl._M_start = __new_start;
154 }
155 else
156 {
157 std::copy(__last, this->_M_impl._M_finish, __first);
158 iterator __new_finish = this->_M_impl._M_finish - __n;
159 std::_Destroy(__new_finish, this->_M_impl._M_finish,
160 _M_get_Tp_allocator());
161 _M_destroy_nodes(__new_finish._M_node + 1,
162 this->_M_impl._M_finish._M_node + 1);
163 this->_M_impl._M_finish = __new_finish;
164 }
165 return this->_M_impl._M_start + __elems_before;
166 }
167 }
169 template <typename _Tp, typename _Alloc>
170 void
171 deque<_Tp, _Alloc>::
172 clear()
173 {
174 for (_Map_pointer __node = this->_M_impl._M_start._M_node + 1;
175 __node < this->_M_impl._M_finish._M_node;
176 ++__node)
177 {
178 std::_Destroy(*__node, *__node + _S_buffer_size(),
179 _M_get_Tp_allocator());
180 _M_deallocate_node(*__node);
181 }
183 if (this->_M_impl._M_start._M_node != this->_M_impl._M_finish._M_node)
184 {
185 std::_Destroy(this->_M_impl._M_start._M_cur,
186 this->_M_impl._M_start._M_last,
187 _M_get_Tp_allocator());
188 std::_Destroy(this->_M_impl._M_finish._M_first,
189 this->_M_impl._M_finish._M_cur,
190 _M_get_Tp_allocator());
191 _M_deallocate_node(this->_M_impl._M_finish._M_first);
192 }
193 else
194 std::_Destroy(this->_M_impl._M_start._M_cur,
195 this->_M_impl._M_finish._M_cur,
196 _M_get_Tp_allocator());
198 this->_M_impl._M_finish = this->_M_impl._M_start;
199 }
201 template <typename _Tp, class _Alloc>
202 template <typename _InputIterator>
203 void
204 deque<_Tp, _Alloc>::
205 _M_assign_aux(_InputIterator __first, _InputIterator __last,
206 std::input_iterator_tag)
207 {
208 iterator __cur = begin();
209 for (; __first != __last && __cur != end(); ++__cur, ++__first)
210 *__cur = *__first;
211 if (__first == __last)
212 erase(__cur, end());
213 else
214 insert(end(), __first, __last);
215 }
217 template <typename _Tp, typename _Alloc>
218 void
219 deque<_Tp, _Alloc>::
220 _M_fill_insert(iterator __pos, size_type __n, const value_type& __x)
221 {
222 if (__pos._M_cur == this->_M_impl._M_start._M_cur)
223 {
224 iterator __new_start = _M_reserve_elements_at_front(__n);
225 try
226 {
227 std::__uninitialized_fill_a(__new_start, this->_M_impl._M_start,
228 __x,
229 _M_get_Tp_allocator());
230 this->_M_impl._M_start = __new_start;
231 }
232 catch(...)
233 {
234 _M_destroy_nodes(__new_start._M_node,
235 this->_M_impl._M_start._M_node);
236 __throw_exception_again;
237 }
238 }
239 else if (__pos._M_cur == this->_M_impl._M_finish._M_cur)
240 {
241 iterator __new_finish = _M_reserve_elements_at_back(__n);
242 try
243 {
244 std::__uninitialized_fill_a(this->_M_impl._M_finish,
245 __new_finish, __x,
246 _M_get_Tp_allocator());
247 this->_M_impl._M_finish = __new_finish;
248 }
249 catch(...)
250 {
251 _M_destroy_nodes(this->_M_impl._M_finish._M_node + 1,
252 __new_finish._M_node + 1);
253 __throw_exception_again;
254 }
255 }
256 else
257 _M_insert_aux(__pos, __n, __x);
258 }
260 template <typename _Tp, typename _Alloc>
261 void
262 deque<_Tp, _Alloc>::
263 _M_fill_initialize(const value_type& __value)
264 {
265 _Map_pointer __cur;
266 try
267 {
268 for (__cur = this->_M_impl._M_start._M_node;
269 __cur < this->_M_impl._M_finish._M_node;
270 ++__cur)
271 std::__uninitialized_fill_a(*__cur, *__cur + _S_buffer_size(),
272 __value, _M_get_Tp_allocator());
273 std::__uninitialized_fill_a(this->_M_impl._M_finish._M_first,
274 this->_M_impl._M_finish._M_cur,
275 __value, _M_get_Tp_allocator());
276 }
277 catch(...)
278 {
279 std::_Destroy(this->_M_impl._M_start, iterator(*__cur, __cur),
280 _M_get_Tp_allocator());
281 __throw_exception_again;
282 }
283 }
285 template <typename _Tp, typename _Alloc>
286 template <typename _InputIterator>
287 void
288 deque<_Tp, _Alloc>::
289 _M_range_initialize(_InputIterator __first, _InputIterator __last,
290 std::input_iterator_tag)
291 {
292 this->_M_initialize_map(0);
293 try
294 {
295 for (; __first != __last; ++__first)
296 push_back(*__first);
297 }
298 catch(...)
299 {
300 clear();
301 __throw_exception_again;
302 }
303 }
305 template <typename _Tp, typename _Alloc>
306 template <typename _ForwardIterator>
307 void
308 deque<_Tp, _Alloc>::
309 _M_range_initialize(_ForwardIterator __first, _ForwardIterator __last,
310 std::forward_iterator_tag)
311 {
312 const size_type __n = std::distance(__first, __last);
313 this->_M_initialize_map(__n);
315 _Map_pointer __cur_node;
316 try
317 {
318 for (__cur_node = this->_M_impl._M_start._M_node;
319 __cur_node < this->_M_impl._M_finish._M_node;
320 ++__cur_node)
321 {
322 _ForwardIterator __mid = __first;
323 std::advance(__mid, _S_buffer_size());
324 std::__uninitialized_copy_a(__first, __mid, *__cur_node,
325 _M_get_Tp_allocator());
326 __first = __mid;
327 }
328 std::__uninitialized_copy_a(__first, __last,
329 this->_M_impl._M_finish._M_first,
330 _M_get_Tp_allocator());
331 }
332 catch(...)
333 {
334 std::_Destroy(this->_M_impl._M_start,
335 iterator(*__cur_node, __cur_node),
336 _M_get_Tp_allocator());
337 __throw_exception_again;
338 }
339 }
341 // Called only if _M_impl._M_finish._M_cur == _M_impl._M_finish._M_last - 1.
342 template <typename _Tp, typename _Alloc>
343 void
344 deque<_Tp, _Alloc>::
345 _M_push_back_aux(const value_type& __t)
346 {
347 value_type __t_copy = __t;
348 _M_reserve_map_at_back();
349 *(this->_M_impl._M_finish._M_node + 1) = this->_M_allocate_node();
350 try
351 {
352 this->_M_impl.construct(this->_M_impl._M_finish._M_cur, __t_copy);
353 this->_M_impl._M_finish._M_set_node(this->_M_impl._M_finish._M_node
354 + 1);
355 this->_M_impl._M_finish._M_cur = this->_M_impl._M_finish._M_first;
356 }
357 catch(...)
358 {
359 _M_deallocate_node(*(this->_M_impl._M_finish._M_node + 1));
360 __throw_exception_again;
361 }
362 }
364 // Called only if _M_impl._M_start._M_cur == _M_impl._M_start._M_first.
365 template <typename _Tp, typename _Alloc>
366 void
367 deque<_Tp, _Alloc>::
368 _M_push_front_aux(const value_type& __t)
369 {
370 value_type __t_copy = __t;
371 _M_reserve_map_at_front();
372 *(this->_M_impl._M_start._M_node - 1) = this->_M_allocate_node();
373 try
374 {
375 this->_M_impl._M_start._M_set_node(this->_M_impl._M_start._M_node
376 - 1);
377 this->_M_impl._M_start._M_cur = this->_M_impl._M_start._M_last - 1;
378 this->_M_impl.construct(this->_M_impl._M_start._M_cur, __t_copy);
379 }
380 catch(...)
381 {
382 ++this->_M_impl._M_start;
383 _M_deallocate_node(*(this->_M_impl._M_start._M_node - 1));
384 __throw_exception_again;
385 }
386 }
388 // Called only if _M_impl._M_finish._M_cur == _M_impl._M_finish._M_first.
389 template <typename _Tp, typename _Alloc>
390 void deque<_Tp, _Alloc>::
391 _M_pop_back_aux()
392 {
393 _M_deallocate_node(this->_M_impl._M_finish._M_first);
394 this->_M_impl._M_finish._M_set_node(this->_M_impl._M_finish._M_node - 1);
395 this->_M_impl._M_finish._M_cur = this->_M_impl._M_finish._M_last - 1;
396 this->_M_impl.destroy(this->_M_impl._M_finish._M_cur);
397 }
399 // Called only if _M_impl._M_start._M_cur == _M_impl._M_start._M_last - 1.
400 // Note that if the deque has at least one element (a precondition for this
401 // member function), and if
402 // _M_impl._M_start._M_cur == _M_impl._M_start._M_last,
403 // then the deque must have at least two nodes.
404 template <typename _Tp, typename _Alloc>
405 void deque<_Tp, _Alloc>::
406 _M_pop_front_aux()
407 {
408 this->_M_impl.destroy(this->_M_impl._M_start._M_cur);
409 _M_deallocate_node(this->_M_impl._M_start._M_first);
410 this->_M_impl._M_start._M_set_node(this->_M_impl._M_start._M_node + 1);
411 this->_M_impl._M_start._M_cur = this->_M_impl._M_start._M_first;
412 }
414 template <typename _Tp, typename _Alloc>
415 template <typename _InputIterator>
416 void
417 deque<_Tp, _Alloc>::
418 _M_range_insert_aux(iterator __pos,
419 _InputIterator __first, _InputIterator __last,
420 std::input_iterator_tag)
421 { std::copy(__first, __last, std::inserter(*this, __pos)); }
423 template <typename _Tp, typename _Alloc>
424 template <typename _ForwardIterator>
425 void
426 deque<_Tp, _Alloc>::
427 _M_range_insert_aux(iterator __pos,
428 _ForwardIterator __first, _ForwardIterator __last,
429 std::forward_iterator_tag)
430 {
431 const size_type __n = std::distance(__first, __last);
432 if (__pos._M_cur == this->_M_impl._M_start._M_cur)
433 {
434 iterator __new_start = _M_reserve_elements_at_front(__n);
435 try
436 {
437 std::__uninitialized_copy_a(__first, __last, __new_start,
438 _M_get_Tp_allocator());
439 this->_M_impl._M_start = __new_start;
440 }
441 catch(...)
442 {
443 _M_destroy_nodes(__new_start._M_node,
444 this->_M_impl._M_start._M_node);
445 __throw_exception_again;
446 }
447 }
448 else if (__pos._M_cur == this->_M_impl._M_finish._M_cur)
449 {
450 iterator __new_finish = _M_reserve_elements_at_back(__n);
451 try
452 {
453 std::__uninitialized_copy_a(__first, __last,
454 this->_M_impl._M_finish,
455 _M_get_Tp_allocator());
456 this->_M_impl._M_finish = __new_finish;
457 }
458 catch(...)
459 {
460 _M_destroy_nodes(this->_M_impl._M_finish._M_node + 1,
461 __new_finish._M_node + 1);
462 __throw_exception_again;
463 }
464 }
465 else
466 _M_insert_aux(__pos, __first, __last, __n);
467 }
469 template <typename _Tp, typename _Alloc>
470 typename deque<_Tp, _Alloc>::iterator
471 deque<_Tp, _Alloc>::
472 _M_insert_aux(iterator __pos, const value_type& __x)
473 {
474 difference_type __index = __pos - this->_M_impl._M_start;
475 value_type __x_copy = __x; // XXX copy
476 if (static_cast<size_type>(__index) < size() / 2)
477 {
478 push_front(front());
479 iterator __front1 = this->_M_impl._M_start;
480 ++__front1;
481 iterator __front2 = __front1;
482 ++__front2;
483 __pos = this->_M_impl._M_start + __index;
484 iterator __pos1 = __pos;
485 ++__pos1;
486 std::copy(__front2, __pos1, __front1);
487 }
488 else
489 {
490 push_back(back());
491 iterator __back1 = this->_M_impl._M_finish;
492 --__back1;
493 iterator __back2 = __back1;
494 --__back2;
495 __pos = this->_M_impl._M_start + __index;
496 std::copy_backward(__pos, __back2, __back1);
497 }
498 *__pos = __x_copy;
499 return __pos;
500 }
502 template <typename _Tp, typename _Alloc>
503 void
504 deque<_Tp, _Alloc>::
505 _M_insert_aux(iterator __pos, size_type __n, const value_type& __x)
506 {
507 const difference_type __elems_before = __pos - this->_M_impl._M_start;
508 const size_type __length = this->size();
509 value_type __x_copy = __x;
510 if (__elems_before < difference_type(__length / 2))
511 {
512 iterator __new_start = _M_reserve_elements_at_front(__n);
513 iterator __old_start = this->_M_impl._M_start;
514 __pos = this->_M_impl._M_start + __elems_before;
515 try
516 {
517 if (__elems_before >= difference_type(__n))
518 {
519 iterator __start_n = (this->_M_impl._M_start
520 + difference_type(__n));
521 std::__uninitialized_copy_a(this->_M_impl._M_start,
522 __start_n, __new_start,
523 _M_get_Tp_allocator());
524 this->_M_impl._M_start = __new_start;
525 std::copy(__start_n, __pos, __old_start);
526 fill(__pos - difference_type(__n), __pos, __x_copy);
527 }
528 else
529 {
530 std::__uninitialized_copy_fill(this->_M_impl._M_start,
531 __pos, __new_start,
532 this->_M_impl._M_start,
533 __x_copy,
534 _M_get_Tp_allocator());
535 this->_M_impl._M_start = __new_start;
536 std::fill(__old_start, __pos, __x_copy);
537 }
538 }
539 catch(...)
540 {
541 _M_destroy_nodes(__new_start._M_node,
542 this->_M_impl._M_start._M_node);
543 __throw_exception_again;
544 }
545 }
546 else
547 {
548 iterator __new_finish = _M_reserve_elements_at_back(__n);
549 iterator __old_finish = this->_M_impl._M_finish;
550 const difference_type __elems_after =
551 difference_type(__length) - __elems_before;
552 __pos = this->_M_impl._M_finish - __elems_after;
553 try
554 {
555 if (__elems_after > difference_type(__n))
556 {
557 iterator __finish_n = (this->_M_impl._M_finish
558 - difference_type(__n));
559 std::__uninitialized_copy_a(__finish_n,
560 this->_M_impl._M_finish,
561 this->_M_impl._M_finish,
562 _M_get_Tp_allocator());
563 this->_M_impl._M_finish = __new_finish;
564 std::copy_backward(__pos, __finish_n, __old_finish);
565 std::fill(__pos, __pos + difference_type(__n), __x_copy);
566 }
567 else
568 {
569 std::__uninitialized_fill_copy(this->_M_impl._M_finish,
570 __pos + difference_type(__n),
571 __x_copy, __pos,
572 this->_M_impl._M_finish,
573 _M_get_Tp_allocator());
574 this->_M_impl._M_finish = __new_finish;
575 std::fill(__pos, __old_finish, __x_copy);
576 }
577 }
578 catch(...)
579 {
580 _M_destroy_nodes(this->_M_impl._M_finish._M_node + 1,
581 __new_finish._M_node + 1);
582 __throw_exception_again;
583 }
584 }
585 }
587 template <typename _Tp, typename _Alloc>
588 template <typename _ForwardIterator>
589 void
590 deque<_Tp, _Alloc>::
591 _M_insert_aux(iterator __pos,
592 _ForwardIterator __first, _ForwardIterator __last,
593 size_type __n)
594 {
595 const difference_type __elemsbefore = __pos - this->_M_impl._M_start;
596 const size_type __length = size();
597 if (static_cast<size_type>(__elemsbefore) < __length / 2)
598 {
599 iterator __new_start = _M_reserve_elements_at_front(__n);
600 iterator __old_start = this->_M_impl._M_start;
601 __pos = this->_M_impl._M_start + __elemsbefore;
602 try
603 {
604 if (__elemsbefore >= difference_type(__n))
605 {
606 iterator __start_n = (this->_M_impl._M_start
607 + difference_type(__n));
608 std::__uninitialized_copy_a(this->_M_impl._M_start,
609 __start_n, __new_start,
610 _M_get_Tp_allocator());
611 this->_M_impl._M_start = __new_start;
612 std::copy(__start_n, __pos, __old_start);
613 std::copy(__first, __last, __pos - difference_type(__n));
614 }
615 else
616 {
617 _ForwardIterator __mid = __first;
618 std::advance(__mid, difference_type(__n) - __elemsbefore);
619 std::__uninitialized_copy_copy(this->_M_impl._M_start,
620 __pos, __first, __mid,
621 __new_start,
622 _M_get_Tp_allocator());
623 this->_M_impl._M_start = __new_start;
624 std::copy(__mid, __last, __old_start);
625 }
626 }
627 catch(...)
628 {
629 _M_destroy_nodes(__new_start._M_node,
630 this->_M_impl._M_start._M_node);
631 __throw_exception_again;
632 }
633 }
634 else
635 {
636 iterator __new_finish = _M_reserve_elements_at_back(__n);
637 iterator __old_finish = this->_M_impl._M_finish;
638 const difference_type __elemsafter =
639 difference_type(__length) - __elemsbefore;
640 __pos = this->_M_impl._M_finish - __elemsafter;
641 try
642 {
643 if (__elemsafter > difference_type(__n))
644 {
645 iterator __finish_n = (this->_M_impl._M_finish
646 - difference_type(__n));
647 std::__uninitialized_copy_a(__finish_n,
648 this->_M_impl._M_finish,
649 this->_M_impl._M_finish,
650 _M_get_Tp_allocator());
651 this->_M_impl._M_finish = __new_finish;
652 std::copy_backward(__pos, __finish_n, __old_finish);
653 std::copy(__first, __last, __pos);
654 }
655 else
656 {
657 _ForwardIterator __mid = __first;
658 std::advance(__mid, __elemsafter);
659 std::__uninitialized_copy_copy(__mid, __last, __pos,
660 this->_M_impl._M_finish,
661 this->_M_impl._M_finish,
662 _M_get_Tp_allocator());
663 this->_M_impl._M_finish = __new_finish;
664 std::copy(__first, __mid, __pos);
665 }
666 }
667 catch(...)
668 {
669 _M_destroy_nodes(this->_M_impl._M_finish._M_node + 1,
670 __new_finish._M_node + 1);
671 __throw_exception_again;
672 }
673 }
674 }
676 template <typename _Tp, typename _Alloc>
677 void
678 deque<_Tp, _Alloc>::
679 _M_new_elements_at_front(size_type __new_elems)
680 {
681 const size_type __new_nodes
682 = (__new_elems + _S_buffer_size() - 1) / _S_buffer_size();
683 _M_reserve_map_at_front(__new_nodes);
684 size_type __i;
685 try
686 {
687 for (__i = 1; __i <= __new_nodes; ++__i)
688 *(this->_M_impl._M_start._M_node - __i) = this->_M_allocate_node();
689 }
690 catch(...)
691 {
692 for (size_type __j = 1; __j < __i; ++__j)
693 _M_deallocate_node(*(this->_M_impl._M_start._M_node - __j));
694 __throw_exception_again;
695 }
696 }
698 template <typename _Tp, typename _Alloc>
699 void
700 deque<_Tp, _Alloc>::
701 _M_new_elements_at_back(size_type __new_elems)
702 {
703 const size_type __new_nodes
704 = (__new_elems + _S_buffer_size() - 1) / _S_buffer_size();
705 _M_reserve_map_at_back(__new_nodes);
706 size_type __i;
707 try
708 {
709 for (__i = 1; __i <= __new_nodes; ++__i)
710 *(this->_M_impl._M_finish._M_node + __i) = this->_M_allocate_node();
711 }
712 catch(...)
713 {
714 for (size_type __j = 1; __j < __i; ++__j)
715 _M_deallocate_node(*(this->_M_impl._M_finish._M_node + __j));
716 __throw_exception_again;
717 }
718 }
720 template <typename _Tp, typename _Alloc>
721 void
722 deque<_Tp, _Alloc>::
723 _M_reallocate_map(size_type __nodes_to_add, bool __add_at_front)
724 {
725 const size_type __old_num_nodes
726 = this->_M_impl._M_finish._M_node - this->_M_impl._M_start._M_node + 1;
727 const size_type __new_num_nodes = __old_num_nodes + __nodes_to_add;
729 _Map_pointer __new_nstart;
730 if (this->_M_impl._M_map_size > 2 * __new_num_nodes)
731 {
732 __new_nstart = this->_M_impl._M_map + (this->_M_impl._M_map_size
733 - __new_num_nodes) / 2
734 + (__add_at_front ? __nodes_to_add : 0);
735 if (__new_nstart < this->_M_impl._M_start._M_node)
736 std::copy(this->_M_impl._M_start._M_node,
737 this->_M_impl._M_finish._M_node + 1,
738 __new_nstart);
739 else
740 std::copy_backward(this->_M_impl._M_start._M_node,
741 this->_M_impl._M_finish._M_node + 1,
742 __new_nstart + __old_num_nodes);
743 }
744 else
745 {
746 size_type __new_map_size = this->_M_impl._M_map_size
747 + std::max(this->_M_impl._M_map_size,
748 __nodes_to_add) + 2;
750 _Map_pointer __new_map = this->_M_allocate_map(__new_map_size);
751 __new_nstart = __new_map + (__new_map_size - __new_num_nodes) / 2
752 + (__add_at_front ? __nodes_to_add : 0);
753 std::copy(this->_M_impl._M_start._M_node,
754 this->_M_impl._M_finish._M_node + 1,
755 __new_nstart);
756 _M_deallocate_map(this->_M_impl._M_map, this->_M_impl._M_map_size);
758 this->_M_impl._M_map = __new_map;
759 this->_M_impl._M_map_size = __new_map_size;
760 }
762 this->_M_impl._M_start._M_set_node(__new_nstart);
763 this->_M_impl._M_finish._M_set_node(__new_nstart + __old_num_nodes - 1);
764 }
765 } // namespace std
767 #endif