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