1// Deque implementation (out of line) -*- C++ -*-
2
3// Copyright (C) 2001-2017 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 3, 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// Under Section 7 of GPL version 3, you are granted additional
17// permissions described in the GCC Runtime Library Exception, version
18// 3.1, as published by the Free Software Foundation.
19
20// You should have received a copy of the GNU General Public License and
21// a copy of the GCC Runtime Library Exception along with this program;
22// see the files COPYING3 and COPYING.RUNTIME respectively. If not, see
23// <http://www.gnu.org/licenses/>.
24
25/*
26 *
27 * Copyright (c) 1994
28 * Hewlett-Packard Company
29 *
30 * Permission to use, copy, modify, distribute and sell this software
31 * and its documentation for any purpose is hereby granted without fee,
32 * provided that the above copyright notice appear in all copies and
33 * that both that copyright notice and this permission notice appear
34 * in supporting documentation. Hewlett-Packard Company makes no
35 * representations about the suitability of this software for any
36 * purpose. It is provided "as is" without express or implied warranty.
37 *
38 *
39 * Copyright (c) 1997
40 * Silicon Graphics Computer Systems, Inc.
41 *
42 * Permission to use, copy, modify, distribute and sell this software
43 * and its documentation for any purpose is hereby granted without fee,
44 * provided that the above copyright notice appear in all copies and
45 * that both that copyright notice and this permission notice appear
46 * in supporting documentation. Silicon Graphics makes no
47 * representations about the suitability of this software for any
48 * purpose. It is provided "as is" without express or implied warranty.
49 */
50
51/** @file bits/deque.tcc
52 * This is an internal header file, included by other library headers.
53 * Do not attempt to use it directly. @headername{deque}
54 */
55
56#ifndef _DEQUE_TCC
57#define _DEQUE_TCC 1
58
59namespace std _GLIBCXX_VISIBILITY(default)
60{
61_GLIBCXX_BEGIN_NAMESPACE_CONTAINER
62
63#if __cplusplus >= 201103L
64 template <typename _Tp, typename _Alloc>
65 void
66 deque<_Tp, _Alloc>::
67 _M_default_initialize()
68 {
69 _Map_pointer __cur;
70 __try
71 {
72 for (__cur = this->_M_impl._M_start._M_node;
73 __cur < this->_M_impl._M_finish._M_node;
74 ++__cur)
75 std::__uninitialized_default_a(*__cur, *__cur + _S_buffer_size(),
76 _M_get_Tp_allocator());
77 std::__uninitialized_default_a(this->_M_impl._M_finish._M_first,
78 this->_M_impl._M_finish._M_cur,
79 _M_get_Tp_allocator());
80 }
81 __catch(...)
82 {
83 std::_Destroy(this->_M_impl._M_start, iterator(*__cur, __cur),
84 _M_get_Tp_allocator());
85 __throw_exception_again;
86 }
87 }
88#endif
89
90 template <typename _Tp, typename _Alloc>
91 deque<_Tp, _Alloc>&
92 deque<_Tp, _Alloc>::
93 operator=(const deque& __x)
94 {
95 if (&__x != this)
96 {
97#if __cplusplus >= 201103L
98 if (_Alloc_traits::_S_propagate_on_copy_assign())
99 {
100 if (!_Alloc_traits::_S_always_equal()
101 && _M_get_Tp_allocator() != __x._M_get_Tp_allocator())
102 {
103 // Replacement allocator cannot free existing storage,
104 // so deallocate everything and take copy of __x's data.
105 _M_replace_map(__x, __x.get_allocator());
106 std::__alloc_on_copy(_M_get_Tp_allocator(),
107 __x._M_get_Tp_allocator());
108 return *this;
109 }
110 std::__alloc_on_copy(_M_get_Tp_allocator(),
111 __x._M_get_Tp_allocator());
112 }
113#endif
114 const size_type __len = size();
115 if (__len >= __x.size())
116 _M_erase_at_end(std::copy(__x.begin(), __x.end(),
117 this->_M_impl._M_start));
118 else
119 {
120 const_iterator __mid = __x.begin() + difference_type(__len);
121 std::copy(__x.begin(), __mid, this->_M_impl._M_start);
122 _M_range_insert_aux(this->_M_impl._M_finish, __mid, __x.end(),
123 std::random_access_iterator_tag());
124 }
125 }
126 return *this;
127 }
128
129#if __cplusplus >= 201103L
130 template<typename _Tp, typename _Alloc>
131 template<typename... _Args>
132#if __cplusplus > 201402L
133 typename deque<_Tp, _Alloc>::reference
134#else
135 void
136#endif
137 deque<_Tp, _Alloc>::
138 emplace_front(_Args&&... __args)
139 {
140 if (this->_M_impl._M_start._M_cur != this->_M_impl._M_start._M_first)
141 {
142 _Alloc_traits::construct(this->_M_impl,
143 this->_M_impl._M_start._M_cur - 1,
144 std::forward<_Args>(__args)...);
145 --this->_M_impl._M_start._M_cur;
146 }
147 else
148 _M_push_front_aux(std::forward<_Args>(__args)...);
149#if __cplusplus > 201402L
150 return front();
151#endif
152 }
153
154 template<typename _Tp, typename _Alloc>
155 template<typename... _Args>
156#if __cplusplus > 201402L
157 typename deque<_Tp, _Alloc>::reference
158#else
159 void
160#endif
161 deque<_Tp, _Alloc>::
162 emplace_back(_Args&&... __args)
163 {
164 if (this->_M_impl._M_finish._M_cur
165 != this->_M_impl._M_finish._M_last - 1)
166 {
167 _Alloc_traits::construct(this->_M_impl,
168 this->_M_impl._M_finish._M_cur,
169 std::forward<_Args>(__args)...);
170 ++this->_M_impl._M_finish._M_cur;
171 }
172 else
173 _M_push_back_aux(std::forward<_Args>(__args)...);
174#if __cplusplus > 201402L
175 return back();
176#endif
177 }
178#endif
179
180#if __cplusplus >= 201103L
181 template<typename _Tp, typename _Alloc>
182 template<typename... _Args>
183 typename deque<_Tp, _Alloc>::iterator
184 deque<_Tp, _Alloc>::
185 emplace(const_iterator __position, _Args&&... __args)
186 {
187 if (__position._M_cur == this->_M_impl._M_start._M_cur)
188 {
189 emplace_front(std::forward<_Args>(__args)...);
190 return this->_M_impl._M_start;
191 }
192 else if (__position._M_cur == this->_M_impl._M_finish._M_cur)
193 {
194 emplace_back(std::forward<_Args>(__args)...);
195 iterator __tmp = this->_M_impl._M_finish;
196 --__tmp;
197 return __tmp;
198 }
199 else
200 return _M_insert_aux(__position._M_const_cast(),
201 std::forward<_Args>(__args)...);
202 }
203#endif
204
205 template <typename _Tp, typename _Alloc>
206 typename deque<_Tp, _Alloc>::iterator
207 deque<_Tp, _Alloc>::
208#if __cplusplus >= 201103L
209 insert(const_iterator __position, const value_type& __x)
210#else
211 insert(iterator __position, const value_type& __x)
212#endif
213 {
214 if (__position._M_cur == this->_M_impl._M_start._M_cur)
215 {
216 push_front(__x);
217 return this->_M_impl._M_start;
218 }
219 else if (__position._M_cur == this->_M_impl._M_finish._M_cur)
220 {
221 push_back(__x);
222 iterator __tmp = this->_M_impl._M_finish;
223 --__tmp;
224 return __tmp;
225 }
226 else
227 return _M_insert_aux(__position._M_const_cast(), __x);
228 }
229
230 template <typename _Tp, typename _Alloc>
231 typename deque<_Tp, _Alloc>::iterator
232 deque<_Tp, _Alloc>::
233 _M_erase(iterator __position)
234 {
235 iterator __next = __position;
236 ++__next;
237 const difference_type __index = __position - begin();
238 if (static_cast<size_type>(__index) < (size() >> 1))
239 {
240 if (__position != begin())
241 _GLIBCXX_MOVE_BACKWARD3(begin(), __position, __next);
242 pop_front();
243 }
244 else
245 {
246 if (__next != end())
247 _GLIBCXX_MOVE3(__next, end(), __position);
248 pop_back();
249 }
250 return begin() + __index;
251 }
252
253 template <typename _Tp, typename _Alloc>
254 typename deque<_Tp, _Alloc>::iterator
255 deque<_Tp, _Alloc>::
256 _M_erase(iterator __first, iterator __last)
257 {
258 if (__first == __last)
259 return __first;
260 else if (__first == begin() && __last == end())
261 {
262 clear();
263 return end();
264 }
265 else
266 {
267 const difference_type __n = __last - __first;
268 const difference_type __elems_before = __first - begin();
269 if (static_cast<size_type>(__elems_before) <= (size() - __n) / 2)
270 {
271 if (__first != begin())
272 _GLIBCXX_MOVE_BACKWARD3(begin(), __first, __last);
273 _M_erase_at_begin(begin() + __n);
274 }
275 else
276 {
277 if (__last != end())
278 _GLIBCXX_MOVE3(__last, end(), __first);
279 _M_erase_at_end(end() - __n);
280 }
281 return begin() + __elems_before;
282 }
283 }
284
285 template <typename _Tp, class _Alloc>
286 template <typename _InputIterator>
287 void
288 deque<_Tp, _Alloc>::
289 _M_assign_aux(_InputIterator __first, _InputIterator __last,
290 std::input_iterator_tag)
291 {
292 iterator __cur = begin();
293 for (; __first != __last && __cur != end(); ++__cur, ++__first)
294 *__cur = *__first;
295 if (__first == __last)
296 _M_erase_at_end(__cur);
297 else
298 _M_range_insert_aux(end(), __first, __last,
299 std::__iterator_category(__first));
300 }
301
302 template <typename _Tp, typename _Alloc>
303 void
304 deque<_Tp, _Alloc>::
305 _M_fill_insert(iterator __pos, size_type __n, const value_type& __x)
306 {
307 if (__pos._M_cur == this->_M_impl._M_start._M_cur)
308 {
309 iterator __new_start = _M_reserve_elements_at_front(__n);
310 __try
311 {
312 std::__uninitialized_fill_a(__new_start, this->_M_impl._M_start,
313 __x, _M_get_Tp_allocator());
314 this->_M_impl._M_start = __new_start;
315 }
316 __catch(...)
317 {
318 _M_destroy_nodes(__new_start._M_node,
319 this->_M_impl._M_start._M_node);
320 __throw_exception_again;
321 }
322 }
323 else if (__pos._M_cur == this->_M_impl._M_finish._M_cur)
324 {
325 iterator __new_finish = _M_reserve_elements_at_back(__n);
326 __try
327 {
328 std::__uninitialized_fill_a(this->_M_impl._M_finish,
329 __new_finish, __x,
330 _M_get_Tp_allocator());
331 this->_M_impl._M_finish = __new_finish;
332 }
333 __catch(...)
334 {
335 _M_destroy_nodes(this->_M_impl._M_finish._M_node + 1,
336 __new_finish._M_node + 1);
337 __throw_exception_again;
338 }
339 }
340 else
341 _M_insert_aux(__pos, __n, __x);
342 }
343
344#if __cplusplus >= 201103L
345 template <typename _Tp, typename _Alloc>
346 void
347 deque<_Tp, _Alloc>::
348 _M_default_append(size_type __n)
349 {
350 if (__n)
351 {
352 iterator __new_finish = _M_reserve_elements_at_back(__n);
353 __try
354 {
355 std::__uninitialized_default_a(this->_M_impl._M_finish,
356 __new_finish,
357 _M_get_Tp_allocator());
358 this->_M_impl._M_finish = __new_finish;
359 }
360 __catch(...)
361 {
362 _M_destroy_nodes(this->_M_impl._M_finish._M_node + 1,
363 __new_finish._M_node + 1);
364 __throw_exception_again;
365 }
366 }
367 }
368
369 template <typename _Tp, typename _Alloc>
370 bool
371 deque<_Tp, _Alloc>::
372 _M_shrink_to_fit()
373 {
374 const difference_type __front_capacity
375 = (this->_M_impl._M_start._M_cur - this->_M_impl._M_start._M_first);
376 if (__front_capacity == 0)
377 return false;
378
379 const difference_type __back_capacity
380 = (this->_M_impl._M_finish._M_last - this->_M_impl._M_finish._M_cur);
381 if (__front_capacity + __back_capacity < _S_buffer_size())
382 return false;
383
384 return std::__shrink_to_fit_aux<deque>::_S_do_it(*this);
385 }
386#endif
387
388 template <typename _Tp, typename _Alloc>
389 void
390 deque<_Tp, _Alloc>::
391 _M_fill_initialize(const value_type& __value)
392 {
393 _Map_pointer __cur;
394 __try
395 {
396 for (__cur = this->_M_impl._M_start._M_node;
397 __cur < this->_M_impl._M_finish._M_node;
398 ++__cur)
399 std::__uninitialized_fill_a(*__cur, *__cur + _S_buffer_size(),
400 __value, _M_get_Tp_allocator());
401 std::__uninitialized_fill_a(this->_M_impl._M_finish._M_first,
402 this->_M_impl._M_finish._M_cur,
403 __value, _M_get_Tp_allocator());
404 }
405 __catch(...)
406 {
407 std::_Destroy(this->_M_impl._M_start, iterator(*__cur, __cur),
408 _M_get_Tp_allocator());
409 __throw_exception_again;
410 }
411 }
412
413 template <typename _Tp, typename _Alloc>
414 template <typename _InputIterator>
415 void
416 deque<_Tp, _Alloc>::
417 _M_range_initialize(_InputIterator __first, _InputIterator __last,
418 std::input_iterator_tag)
419 {
420 this->_M_initialize_map(0);
421 __try
422 {
423 for (; __first != __last; ++__first)
424#if __cplusplus >= 201103L
425 emplace_back(*__first);
426#else
427 push_back(*__first);
428#endif
429 }
430 __catch(...)
431 {
432 clear();
433 __throw_exception_again;
434 }
435 }
436
437 template <typename _Tp, typename _Alloc>
438 template <typename _ForwardIterator>
439 void
440 deque<_Tp, _Alloc>::
441 _M_range_initialize(_ForwardIterator __first, _ForwardIterator __last,
442 std::forward_iterator_tag)
443 {
444 const size_type __n = std::distance(__first, __last);
445 this->_M_initialize_map(__n);
446
447 _Map_pointer __cur_node;
448 __try
449 {
450 for (__cur_node = this->_M_impl._M_start._M_node;
451 __cur_node < this->_M_impl._M_finish._M_node;
452 ++__cur_node)
453 {
454 _ForwardIterator __mid = __first;
455 std::advance(__mid, _S_buffer_size());
456 std::__uninitialized_copy_a(__first, __mid, *__cur_node,
457 _M_get_Tp_allocator());
458 __first = __mid;
459 }
460 std::__uninitialized_copy_a(__first, __last,
461 this->_M_impl._M_finish._M_first,
462 _M_get_Tp_allocator());
463 }
464 __catch(...)
465 {
466 std::_Destroy(this->_M_impl._M_start,
467 iterator(*__cur_node, __cur_node),
468 _M_get_Tp_allocator());
469 __throw_exception_again;
470 }
471 }
472
473 // Called only if _M_impl._M_finish._M_cur == _M_impl._M_finish._M_last - 1.
474 template<typename _Tp, typename _Alloc>
475#if __cplusplus >= 201103L
476 template<typename... _Args>
477 void
478 deque<_Tp, _Alloc>::
479 _M_push_back_aux(_Args&&... __args)
480#else
481 void
482 deque<_Tp, _Alloc>::
483 _M_push_back_aux(const value_type& __t)
484#endif
485 {
486 _M_reserve_map_at_back();
487 *(this->_M_impl._M_finish._M_node + 1) = this->_M_allocate_node();
488 __try
489 {
490#if __cplusplus >= 201103L
491 _Alloc_traits::construct(this->_M_impl,
492 this->_M_impl._M_finish._M_cur,
493 std::forward<_Args>(__args)...);
494#else
495 this->_M_impl.construct(this->_M_impl._M_finish._M_cur, __t);
496#endif
497 this->_M_impl._M_finish._M_set_node(this->_M_impl._M_finish._M_node
498 + 1);
499 this->_M_impl._M_finish._M_cur = this->_M_impl._M_finish._M_first;
500 }
501 __catch(...)
502 {
503 _M_deallocate_node(*(this->_M_impl._M_finish._M_node + 1));
504 __throw_exception_again;
505 }
506 }
507
508 // Called only if _M_impl._M_start._M_cur == _M_impl._M_start._M_first.
509 template<typename _Tp, typename _Alloc>
510#if __cplusplus >= 201103L
511 template<typename... _Args>
512 void
513 deque<_Tp, _Alloc>::
514 _M_push_front_aux(_Args&&... __args)
515#else
516 void
517 deque<_Tp, _Alloc>::
518 _M_push_front_aux(const value_type& __t)
519#endif
520 {
521 _M_reserve_map_at_front();
522 *(this->_M_impl._M_start._M_node - 1) = this->_M_allocate_node();
523 __try
524 {
525 this->_M_impl._M_start._M_set_node(this->_M_impl._M_start._M_node
526 - 1);
527 this->_M_impl._M_start._M_cur = this->_M_impl._M_start._M_last - 1;
528#if __cplusplus >= 201103L
529 _Alloc_traits::construct(this->_M_impl,
530 this->_M_impl._M_start._M_cur,
531 std::forward<_Args>(__args)...);
532#else
533 this->_M_impl.construct(this->_M_impl._M_start._M_cur, __t);
534#endif
535 }
536 __catch(...)
537 {
538 ++this->_M_impl._M_start;
539 _M_deallocate_node(*(this->_M_impl._M_start._M_node - 1));
540 __throw_exception_again;
541 }
542 }
543
544 // Called only if _M_impl._M_finish._M_cur == _M_impl._M_finish._M_first.
545 template <typename _Tp, typename _Alloc>
546 void deque<_Tp, _Alloc>::
547 _M_pop_back_aux()
548 {
549 _M_deallocate_node(this->_M_impl._M_finish._M_first);
550 this->_M_impl._M_finish._M_set_node(this->_M_impl._M_finish._M_node - 1);
551 this->_M_impl._M_finish._M_cur = this->_M_impl._M_finish._M_last - 1;
552 _Alloc_traits::destroy(_M_get_Tp_allocator(),
553 this->_M_impl._M_finish._M_cur);
554 }
555
556 // Called only if _M_impl._M_start._M_cur == _M_impl._M_start._M_last - 1.
557 // Note that if the deque has at least one element (a precondition for this
558 // member function), and if
559 // _M_impl._M_start._M_cur == _M_impl._M_start._M_last,
560 // then the deque must have at least two nodes.
561 template <typename _Tp, typename _Alloc>
562 void deque<_Tp, _Alloc>::
563 _M_pop_front_aux()
564 {
565 _Alloc_traits::destroy(_M_get_Tp_allocator(),
566 this->_M_impl._M_start._M_cur);
567 _M_deallocate_node(this->_M_impl._M_start._M_first);
568 this->_M_impl._M_start._M_set_node(this->_M_impl._M_start._M_node + 1);
569 this->_M_impl._M_start._M_cur = this->_M_impl._M_start._M_first;
570 }
571
572 template <typename _Tp, typename _Alloc>
573 template <typename _InputIterator>
574 void
575 deque<_Tp, _Alloc>::
576 _M_range_insert_aux(iterator __pos,
577 _InputIterator __first, _InputIterator __last,
578 std::input_iterator_tag)
579 { std::copy(__first, __last, std::inserter(*this, __pos)); }
580
581 template <typename _Tp, typename _Alloc>
582 template <typename _ForwardIterator>
583 void
584 deque<_Tp, _Alloc>::
585 _M_range_insert_aux(iterator __pos,
586 _ForwardIterator __first, _ForwardIterator __last,
587 std::forward_iterator_tag)
588 {
589 const size_type __n = std::distance(__first, __last);
590 if (__pos._M_cur == this->_M_impl._M_start._M_cur)
591 {
592 iterator __new_start = _M_reserve_elements_at_front(__n);
593 __try
594 {
595 std::__uninitialized_copy_a(__first, __last, __new_start,
596 _M_get_Tp_allocator());
597 this->_M_impl._M_start = __new_start;
598 }
599 __catch(...)
600 {
601 _M_destroy_nodes(__new_start._M_node,
602 this->_M_impl._M_start._M_node);
603 __throw_exception_again;
604 }
605 }
606 else if (__pos._M_cur == this->_M_impl._M_finish._M_cur)
607 {
608 iterator __new_finish = _M_reserve_elements_at_back(__n);
609 __try
610 {
611 std::__uninitialized_copy_a(__first, __last,
612 this->_M_impl._M_finish,
613 _M_get_Tp_allocator());
614 this->_M_impl._M_finish = __new_finish;
615 }
616 __catch(...)
617 {
618 _M_destroy_nodes(this->_M_impl._M_finish._M_node + 1,
619 __new_finish._M_node + 1);
620 __throw_exception_again;
621 }
622 }
623 else
624 _M_insert_aux(__pos, __first, __last, __n);
625 }
626
627 template<typename _Tp, typename _Alloc>
628#if __cplusplus >= 201103L
629 template<typename... _Args>
630 typename deque<_Tp, _Alloc>::iterator
631 deque<_Tp, _Alloc>::
632 _M_insert_aux(iterator __pos, _Args&&... __args)
633 {
634 value_type __x_copy(std::forward<_Args>(__args)...); // XXX copy
635#else
636 typename deque<_Tp, _Alloc>::iterator
637 deque<_Tp, _Alloc>::
638 _M_insert_aux(iterator __pos, const value_type& __x)
639 {
640 value_type __x_copy = __x; // XXX copy
641#endif
642 difference_type __index = __pos - this->_M_impl._M_start;
643 if (static_cast<size_type>(__index) < size() / 2)
644 {
645 push_front(_GLIBCXX_MOVE(front()));
646 iterator __front1 = this->_M_impl._M_start;
647 ++__front1;
648 iterator __front2 = __front1;
649 ++__front2;
650 __pos = this->_M_impl._M_start + __index;
651 iterator __pos1 = __pos;
652 ++__pos1;
653 _GLIBCXX_MOVE3(__front2, __pos1, __front1);
654 }
655 else
656 {
657 push_back(_GLIBCXX_MOVE(back()));
658 iterator __back1 = this->_M_impl._M_finish;
659 --__back1;
660 iterator __back2 = __back1;
661 --__back2;
662 __pos = this->_M_impl._M_start + __index;
663 _GLIBCXX_MOVE_BACKWARD3(__pos, __back2, __back1);
664 }
665 *__pos = _GLIBCXX_MOVE(__x_copy);
666 return __pos;
667 }
668
669 template <typename _Tp, typename _Alloc>
670 void
671 deque<_Tp, _Alloc>::
672 _M_insert_aux(iterator __pos, size_type __n, const value_type& __x)
673 {
674 const difference_type __elems_before = __pos - this->_M_impl._M_start;
675 const size_type __length = this->size();
676 value_type __x_copy = __x;
677 if (__elems_before < difference_type(__length / 2))
678 {
679 iterator __new_start = _M_reserve_elements_at_front(__n);
680 iterator __old_start = this->_M_impl._M_start;
681 __pos = this->_M_impl._M_start + __elems_before;
682 __try
683 {
684 if (__elems_before >= difference_type(__n))
685 {
686 iterator __start_n = (this->_M_impl._M_start
687 + difference_type(__n));
688 std::__uninitialized_move_a(this->_M_impl._M_start,
689 __start_n, __new_start,
690 _M_get_Tp_allocator());
691 this->_M_impl._M_start = __new_start;
692 _GLIBCXX_MOVE3(__start_n, __pos, __old_start);
693 std::fill(__pos - difference_type(__n), __pos, __x_copy);
694 }
695 else
696 {
697 std::__uninitialized_move_fill(this->_M_impl._M_start,
698 __pos, __new_start,
699 this->_M_impl._M_start,
700 __x_copy,
701 _M_get_Tp_allocator());
702 this->_M_impl._M_start = __new_start;
703 std::fill(__old_start, __pos, __x_copy);
704 }
705 }
706 __catch(...)
707 {
708 _M_destroy_nodes(__new_start._M_node,
709 this->_M_impl._M_start._M_node);
710 __throw_exception_again;
711 }
712 }
713 else
714 {
715 iterator __new_finish = _M_reserve_elements_at_back(__n);
716 iterator __old_finish = this->_M_impl._M_finish;
717 const difference_type __elems_after =
718 difference_type(__length) - __elems_before;
719 __pos = this->_M_impl._M_finish - __elems_after;
720 __try
721 {
722 if (__elems_after > difference_type(__n))
723 {
724 iterator __finish_n = (this->_M_impl._M_finish
725 - difference_type(__n));
726 std::__uninitialized_move_a(__finish_n,
727 this->_M_impl._M_finish,
728 this->_M_impl._M_finish,
729 _M_get_Tp_allocator());
730 this->_M_impl._M_finish = __new_finish;
731 _GLIBCXX_MOVE_BACKWARD3(__pos, __finish_n, __old_finish);
732 std::fill(__pos, __pos + difference_type(__n), __x_copy);
733 }
734 else
735 {
736 std::__uninitialized_fill_move(this->_M_impl._M_finish,
737 __pos + difference_type(__n),
738 __x_copy, __pos,
739 this->_M_impl._M_finish,
740 _M_get_Tp_allocator());
741 this->_M_impl._M_finish = __new_finish;
742 std::fill(__pos, __old_finish, __x_copy);
743 }
744 }
745 __catch(...)
746 {
747 _M_destroy_nodes(this->_M_impl._M_finish._M_node + 1,
748 __new_finish._M_node + 1);
749 __throw_exception_again;
750 }
751 }
752 }
753
754 template <typename _Tp, typename _Alloc>
755 template <typename _ForwardIterator>
756 void
757 deque<_Tp, _Alloc>::
758 _M_insert_aux(iterator __pos,
759 _ForwardIterator __first, _ForwardIterator __last,
760 size_type __n)
761 {
762 const difference_type __elemsbefore = __pos - this->_M_impl._M_start;
763 const size_type __length = size();
764 if (static_cast<size_type>(__elemsbefore) < __length / 2)
765 {
766 iterator __new_start = _M_reserve_elements_at_front(__n);
767 iterator __old_start = this->_M_impl._M_start;
768 __pos = this->_M_impl._M_start + __elemsbefore;
769 __try
770 {
771 if (__elemsbefore >= difference_type(__n))
772 {
773 iterator __start_n = (this->_M_impl._M_start
774 + difference_type(__n));
775 std::__uninitialized_move_a(this->_M_impl._M_start,
776 __start_n, __new_start,
777 _M_get_Tp_allocator());
778 this->_M_impl._M_start = __new_start;
779 _GLIBCXX_MOVE3(__start_n, __pos, __old_start);
780 std::copy(__first, __last, __pos - difference_type(__n));
781 }
782 else
783 {
784 _ForwardIterator __mid = __first;
785 std::advance(__mid, difference_type(__n) - __elemsbefore);
786 std::__uninitialized_move_copy(this->_M_impl._M_start,
787 __pos, __first, __mid,
788 __new_start,
789 _M_get_Tp_allocator());
790 this->_M_impl._M_start = __new_start;
791 std::copy(__mid, __last, __old_start);
792 }
793 }
794 __catch(...)
795 {
796 _M_destroy_nodes(__new_start._M_node,
797 this->_M_impl._M_start._M_node);
798 __throw_exception_again;
799 }
800 }
801 else
802 {
803 iterator __new_finish = _M_reserve_elements_at_back(__n);
804 iterator __old_finish = this->_M_impl._M_finish;
805 const difference_type __elemsafter =
806 difference_type(__length) - __elemsbefore;
807 __pos = this->_M_impl._M_finish - __elemsafter;
808 __try
809 {
810 if (__elemsafter > difference_type(__n))
811 {
812 iterator __finish_n = (this->_M_impl._M_finish
813 - difference_type(__n));
814 std::__uninitialized_move_a(__finish_n,
815 this->_M_impl._M_finish,
816 this->_M_impl._M_finish,
817 _M_get_Tp_allocator());
818 this->_M_impl._M_finish = __new_finish;
819 _GLIBCXX_MOVE_BACKWARD3(__pos, __finish_n, __old_finish);
820 std::copy(__first, __last, __pos);
821 }
822 else
823 {
824 _ForwardIterator __mid = __first;
825 std::advance(__mid, __elemsafter);
826 std::__uninitialized_copy_move(__mid, __last, __pos,
827 this->_M_impl._M_finish,
828 this->_M_impl._M_finish,
829 _M_get_Tp_allocator());
830 this->_M_impl._M_finish = __new_finish;
831 std::copy(__first, __mid, __pos);
832 }
833 }
834 __catch(...)
835 {
836 _M_destroy_nodes(this->_M_impl._M_finish._M_node + 1,
837 __new_finish._M_node + 1);
838 __throw_exception_again;
839 }
840 }
841 }
842
843 template<typename _Tp, typename _Alloc>
844 void
845 deque<_Tp, _Alloc>::
846 _M_destroy_data_aux(iterator __first, iterator __last)
847 {
848 for (_Map_pointer __node = __first._M_node + 1;
849 __node < __last._M_node; ++__node)
850 std::_Destroy(*__node, *__node + _S_buffer_size(),
851 _M_get_Tp_allocator());
852
853 if (__first._M_node != __last._M_node)
854 {
855 std::_Destroy(__first._M_cur, __first._M_last,
856 _M_get_Tp_allocator());
857 std::_Destroy(__last._M_first, __last._M_cur,
858 _M_get_Tp_allocator());
859 }
860 else
861 std::_Destroy(__first._M_cur, __last._M_cur,
862 _M_get_Tp_allocator());
863 }
864
865 template <typename _Tp, typename _Alloc>
866 void
867 deque<_Tp, _Alloc>::
868 _M_new_elements_at_front(size_type __new_elems)
869 {
870 if (this->max_size() - this->size() < __new_elems)
871 __throw_length_error(__N("deque::_M_new_elements_at_front"));
872
873 const size_type __new_nodes = ((__new_elems + _S_buffer_size() - 1)
874 / _S_buffer_size());
875 _M_reserve_map_at_front(__new_nodes);
876 size_type __i;
877 __try
878 {
879 for (__i = 1; __i <= __new_nodes; ++__i)
880 *(this->_M_impl._M_start._M_node - __i) = this->_M_allocate_node();
881 }
882 __catch(...)
883 {
884 for (size_type __j = 1; __j < __i; ++__j)
885 _M_deallocate_node(*(this->_M_impl._M_start._M_node - __j));
886 __throw_exception_again;
887 }
888 }
889
890 template <typename _Tp, typename _Alloc>
891 void
892 deque<_Tp, _Alloc>::
893 _M_new_elements_at_back(size_type __new_elems)
894 {
895 if (this->max_size() - this->size() < __new_elems)
896 __throw_length_error(__N("deque::_M_new_elements_at_back"));
897
898 const size_type __new_nodes = ((__new_elems + _S_buffer_size() - 1)
899 / _S_buffer_size());
900 _M_reserve_map_at_back(__new_nodes);
901 size_type __i;
902 __try
903 {
904 for (__i = 1; __i <= __new_nodes; ++__i)
905 *(this->_M_impl._M_finish._M_node + __i) = this->_M_allocate_node();
906 }
907 __catch(...)
908 {
909 for (size_type __j = 1; __j < __i; ++__j)
910 _M_deallocate_node(*(this->_M_impl._M_finish._M_node + __j));
911 __throw_exception_again;
912 }
913 }
914
915 template <typename _Tp, typename _Alloc>
916 void
917 deque<_Tp, _Alloc>::
918 _M_reallocate_map(size_type __nodes_to_add, bool __add_at_front)
919 {
920 const size_type __old_num_nodes
921 = this->_M_impl._M_finish._M_node - this->_M_impl._M_start._M_node + 1;
922 const size_type __new_num_nodes = __old_num_nodes + __nodes_to_add;
923
924 _Map_pointer __new_nstart;
925 if (this->_M_impl._M_map_size > 2 * __new_num_nodes)
926 {
927 __new_nstart = this->_M_impl._M_map + (this->_M_impl._M_map_size
928 - __new_num_nodes) / 2
929 + (__add_at_front ? __nodes_to_add : 0);
930 if (__new_nstart < this->_M_impl._M_start._M_node)
931 std::copy(this->_M_impl._M_start._M_node,
932 this->_M_impl._M_finish._M_node + 1,
933 __new_nstart);
934 else
935 std::copy_backward(this->_M_impl._M_start._M_node,
936 this->_M_impl._M_finish._M_node + 1,
937 __new_nstart + __old_num_nodes);
938 }
939 else
940 {
941 size_type __new_map_size = this->_M_impl._M_map_size
942 + std::max(this->_M_impl._M_map_size,
943 __nodes_to_add) + 2;
944
945 _Map_pointer __new_map = this->_M_allocate_map(__new_map_size);
946 __new_nstart = __new_map + (__new_map_size - __new_num_nodes) / 2
947 + (__add_at_front ? __nodes_to_add : 0);
948 std::copy(this->_M_impl._M_start._M_node,
949 this->_M_impl._M_finish._M_node + 1,
950 __new_nstart);
951 _M_deallocate_map(this->_M_impl._M_map, this->_M_impl._M_map_size);
952
953 this->_M_impl._M_map = __new_map;
954 this->_M_impl._M_map_size = __new_map_size;
955 }
956
957 this->_M_impl._M_start._M_set_node(__new_nstart);
958 this->_M_impl._M_finish._M_set_node(__new_nstart + __old_num_nodes - 1);
959 }
960
961 // Overload for deque::iterators, exploiting the "segmented-iterator
962 // optimization".
963 template<typename _Tp>
964 void
965 fill(const _Deque_iterator<_Tp, _Tp&, _Tp*>& __first,
966 const _Deque_iterator<_Tp, _Tp&, _Tp*>& __last, const _Tp& __value)
967 {
968 typedef typename _Deque_iterator<_Tp, _Tp&, _Tp*>::_Self _Self;
969
970 for (typename _Self::_Map_pointer __node = __first._M_node + 1;
971 __node < __last._M_node; ++__node)
972 std::fill(*__node, *__node + _Self::_S_buffer_size(), __value);
973
974 if (__first._M_node != __last._M_node)
975 {
976 std::fill(__first._M_cur, __first._M_last, __value);
977 std::fill(__last._M_first, __last._M_cur, __value);
978 }
979 else
980 std::fill(__first._M_cur, __last._M_cur, __value);
981 }
982
983 template<typename _Tp>
984 _Deque_iterator<_Tp, _Tp&, _Tp*>
985 copy(_Deque_iterator<_Tp, const _Tp&, const _Tp*> __first,
986 _Deque_iterator<_Tp, const _Tp&, const _Tp*> __last,
987 _Deque_iterator<_Tp, _Tp&, _Tp*> __result)
988 {
989 typedef typename _Deque_iterator<_Tp, _Tp&, _Tp*>::_Self _Self;
990 typedef typename _Self::difference_type difference_type;
991
992 difference_type __len = __last - __first;
993 while (__len > 0)
994 {
995 const difference_type __clen
996 = std::min(__len, std::min(__first._M_last - __first._M_cur,
997 __result._M_last - __result._M_cur));
998 std::copy(__first._M_cur, __first._M_cur + __clen, __result._M_cur);
999 __first += __clen;
1000 __result += __clen;
1001 __len -= __clen;
1002 }
1003 return __result;
1004 }
1005
1006 template<typename _Tp>
1007 _Deque_iterator<_Tp, _Tp&, _Tp*>
1008 copy_backward(_Deque_iterator<_Tp, const _Tp&, const _Tp*> __first,
1009 _Deque_iterator<_Tp, const _Tp&, const _Tp*> __last,
1010 _Deque_iterator<_Tp, _Tp&, _Tp*> __result)
1011 {
1012 typedef typename _Deque_iterator<_Tp, _Tp&, _Tp*>::_Self _Self;
1013 typedef typename _Self::difference_type difference_type;
1014
1015 difference_type __len = __last - __first;
1016 while (__len > 0)
1017 {
1018 difference_type __llen = __last._M_cur - __last._M_first;
1019 _Tp* __lend = __last._M_cur;
1020
1021 difference_type __rlen = __result._M_cur - __result._M_first;
1022 _Tp* __rend = __result._M_cur;
1023
1024 if (!__llen)
1025 {
1026 __llen = _Self::_S_buffer_size();
1027 __lend = *(__last._M_node - 1) + __llen;
1028 }
1029 if (!__rlen)
1030 {
1031 __rlen = _Self::_S_buffer_size();
1032 __rend = *(__result._M_node - 1) + __rlen;
1033 }
1034
1035 const difference_type __clen = std::min(__len,
1036 std::min(__llen, __rlen));
1037 std::copy_backward(__lend - __clen, __lend, __rend);
1038 __last -= __clen;
1039 __result -= __clen;
1040 __len -= __clen;
1041 }
1042 return __result;
1043 }
1044
1045#if __cplusplus >= 201103L
1046 template<typename _Tp>
1047 _Deque_iterator<_Tp, _Tp&, _Tp*>
1048 move(_Deque_iterator<_Tp, const _Tp&, const _Tp*> __first,
1049 _Deque_iterator<_Tp, const _Tp&, const _Tp*> __last,
1050 _Deque_iterator<_Tp, _Tp&, _Tp*> __result)
1051 {
1052 typedef typename _Deque_iterator<_Tp, _Tp&, _Tp*>::_Self _Self;
1053 typedef typename _Self::difference_type difference_type;
1054
1055 difference_type __len = __last - __first;
1056 while (__len > 0)
1057 {
1058 const difference_type __clen
1059 = std::min(__len, std::min(__first._M_last - __first._M_cur,
1060 __result._M_last - __result._M_cur));
1061 std::move(__first._M_cur, __first._M_cur + __clen, __result._M_cur);
1062 __first += __clen;
1063 __result += __clen;
1064 __len -= __clen;
1065 }
1066 return __result;
1067 }
1068
1069 template<typename _Tp>
1070 _Deque_iterator<_Tp, _Tp&, _Tp*>
1071 move_backward(_Deque_iterator<_Tp, const _Tp&, const _Tp*> __first,
1072 _Deque_iterator<_Tp, const _Tp&, const _Tp*> __last,
1073 _Deque_iterator<_Tp, _Tp&, _Tp*> __result)
1074 {
1075 typedef typename _Deque_iterator<_Tp, _Tp&, _Tp*>::_Self _Self;
1076 typedef typename _Self::difference_type difference_type;
1077
1078 difference_type __len = __last - __first;
1079 while (__len > 0)
1080 {
1081 difference_type __llen = __last._M_cur - __last._M_first;
1082 _Tp* __lend = __last._M_cur;
1083
1084 difference_type __rlen = __result._M_cur - __result._M_first;
1085 _Tp* __rend = __result._M_cur;
1086
1087 if (!__llen)
1088 {
1089 __llen = _Self::_S_buffer_size();
1090 __lend = *(__last._M_node - 1) + __llen;
1091 }
1092 if (!__rlen)
1093 {
1094 __rlen = _Self::_S_buffer_size();
1095 __rend = *(__result._M_node - 1) + __rlen;
1096 }
1097
1098 const difference_type __clen = std::min(__len,
1099 std::min(__llen, __rlen));
1100 std::move_backward(__lend - __clen, __lend, __rend);
1101 __last -= __clen;
1102 __result -= __clen;
1103 __len -= __clen;
1104 }
1105 return __result;
1106 }
1107#endif
1108
1109_GLIBCXX_END_NAMESPACE_CONTAINER
1110} // namespace std
1111
1112#endif
1113