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