1 : // Deque implementation (out of line) -*- C++ -*-
2 :
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.
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, 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301,
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 _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 : }
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 : 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 : }
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
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 : }
168 :
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 : }
182 :
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());
197 :
198 : this->_M_impl._M_finish = this->_M_impl._M_start;
199 : }
200 :
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 : }
216 :
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 : }
259 :
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 : }
284 :
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 : }
304 :
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);
314 :
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 : }
340 :
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 0 : _M_push_back_aux(const value_type& __t)
346 : {
347 0 : value_type __t_copy = __t;
348 0 : _M_reserve_map_at_back();
349 0 : *(this->_M_impl._M_finish._M_node + 1) = this->_M_allocate_node();
350 : try
351 : {
352 0 : this->_M_impl.construct(this->_M_impl._M_finish._M_cur, __t_copy);
353 0 : this->_M_impl._M_finish._M_set_node(this->_M_impl._M_finish._M_node
354 : + 1);
355 0 : this->_M_impl._M_finish._M_cur = this->_M_impl._M_finish._M_first;
356 : }
357 0 : catch(...)
358 : {
359 0 : _M_deallocate_node(*(this->_M_impl._M_finish._M_node + 1));
360 0 : __throw_exception_again;
361 : }
362 : }
363 :
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 : }
387 :
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 0 : _M_pop_back_aux()
392 : {
393 0 : _M_deallocate_node(this->_M_impl._M_finish._M_first);
394 0 : this->_M_impl._M_finish._M_set_node(this->_M_impl._M_finish._M_node - 1);
395 0 : this->_M_impl._M_finish._M_cur = this->_M_impl._M_finish._M_last - 1;
396 0 : this->_M_impl.destroy(this->_M_impl._M_finish._M_cur);
397 : }
398 :
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 : }
413 :
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)); }
422 :
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 : }
468 :
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 : }
501 :
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 : }
586 :
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 : }
675 :
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 : }
697 :
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 : }
719 :
720 : template <typename _Tp, typename _Alloc>
721 : void
722 : deque<_Tp, _Alloc>::
723 0 : _M_reallocate_map(size_type __nodes_to_add, bool __add_at_front)
724 : {
725 : const size_type __old_num_nodes
726 0 : = this->_M_impl._M_finish._M_node - this->_M_impl._M_start._M_node + 1;
727 0 : const size_type __new_num_nodes = __old_num_nodes + __nodes_to_add;
728 :
729 : _Map_pointer __new_nstart;
730 0 : if (this->_M_impl._M_map_size > 2 * __new_num_nodes)
731 : {
732 0 : __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 0 : if (__new_nstart < this->_M_impl._M_start._M_node)
736 0 : std::copy(this->_M_impl._M_start._M_node,
737 : this->_M_impl._M_finish._M_node + 1,
738 : __new_nstart);
739 : else
740 0 : 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 0 : __nodes_to_add) + 2;
749 :
750 0 : _Map_pointer __new_map = this->_M_allocate_map(__new_map_size);
751 0 : __new_nstart = __new_map + (__new_map_size - __new_num_nodes) / 2
752 : + (__add_at_front ? __nodes_to_add : 0);
753 0 : std::copy(this->_M_impl._M_start._M_node,
754 : this->_M_impl._M_finish._M_node + 1,
755 : __new_nstart);
756 0 : _M_deallocate_map(this->_M_impl._M_map, this->_M_impl._M_map_size);
757 :
758 0 : this->_M_impl._M_map = __new_map;
759 0 : this->_M_impl._M_map_size = __new_map_size;
760 : }
761 :
762 0 : this->_M_impl._M_start._M_set_node(__new_nstart);
763 0 : this->_M_impl._M_finish._M_set_node(__new_nstart + __old_num_nodes - 1);
764 : }
765 : } // namespace std
766 :
767 : #endif
|
