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