source: branches/libc-0.6/src/gcc/libstdc++-v3/include/bits/deque.tcc@ 2537

Last change on this file since 2537 was 1389, checked in by bird, 22 years ago

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