File Coverage

/usr/include/c++/5/bits/deque.tcc
Criterion Covered Total %
statement 11 52 21.1
branch 7 64 10.9
condition n/a
subroutine n/a
pod n/a
total 18 116 15.5


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