Line data Source code
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 :
59 : namespace 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 0 : deque<_Tp, _Alloc>::
162 : emplace_back(_Args&&... __args)
163 : {
164 0 : if (this->_M_impl._M_finish._M_cur
165 0 : != this->_M_impl._M_finish._M_last - 1)
166 : {
167 0 : _Alloc_traits::construct(this->_M_impl,
168 : this->_M_impl._M_finish._M_cur,
169 : std::forward<_Args>(__args)...);
170 0 : ++this->_M_impl._M_finish._M_cur;
171 : }
172 : else
173 0 : _M_push_back_aux(std::forward<_Args>(__args)...);
174 : #if __cplusplus > 201402L
175 : return back();
176 : #endif
177 0 : }
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 0 : 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 0 : _M_reserve_map_at_back();
487 0 : *(this->_M_impl._M_finish._M_node + 1) = this->_M_allocate_node();
488 : __try
489 : {
490 : #if __cplusplus >= 201103L
491 0 : _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 0 : this->_M_impl._M_finish._M_set_node(this->_M_impl._M_finish._M_node
498 : + 1);
499 0 : this->_M_impl._M_finish._M_cur = this->_M_impl._M_finish._M_first;
500 : }
501 0 : __catch(...)
502 : {
503 0 : _M_deallocate_node(*(this->_M_impl._M_finish._M_node + 1));
504 0 : __throw_exception_again;
505 : }
506 0 : }
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 0 : void deque<_Tp, _Alloc>::
563 : _M_pop_front_aux()
564 : {
565 0 : _Alloc_traits::destroy(_M_get_Tp_allocator(),
566 : this->_M_impl._M_start._M_cur);
567 0 : _M_deallocate_node(this->_M_impl._M_start._M_first);
568 0 : this->_M_impl._M_start._M_set_node(this->_M_impl._M_start._M_node + 1);
569 0 : this->_M_impl._M_start._M_cur = this->_M_impl._M_start._M_first;
570 0 : }
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 5 : deque<_Tp, _Alloc>::
846 : _M_destroy_data_aux(iterator __first, iterator __last)
847 : {
848 5 : for (_Map_pointer __node = __first._M_node + 1;
849 5 : __node < __last._M_node; ++__node)
850 0 : std::_Destroy(*__node, *__node + _S_buffer_size(),
851 0 : _M_get_Tp_allocator());
852 :
853 5 : if (__first._M_node != __last._M_node)
854 : {
855 0 : std::_Destroy(__first._M_cur, __first._M_last,
856 0 : _M_get_Tp_allocator());
857 0 : std::_Destroy(__last._M_first, __last._M_cur,
858 0 : _M_get_Tp_allocator());
859 : }
860 : else
861 5 : std::_Destroy(__first._M_cur, __last._M_cur,
862 5 : _M_get_Tp_allocator());
863 5 : }
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 0 : deque<_Tp, _Alloc>::
918 : _M_reallocate_map(size_type __nodes_to_add, bool __add_at_front)
919 : {
920 0 : const size_type __old_num_nodes
921 0 : = this->_M_impl._M_finish._M_node - this->_M_impl._M_start._M_node + 1;
922 0 : const size_type __new_num_nodes = __old_num_nodes + __nodes_to_add;
923 :
924 : _Map_pointer __new_nstart;
925 0 : if (this->_M_impl._M_map_size > 2 * __new_num_nodes)
926 : {
927 0 : __new_nstart = this->_M_impl._M_map + (this->_M_impl._M_map_size
928 0 : - __new_num_nodes) / 2
929 0 : + (__add_at_front ? __nodes_to_add : 0);
930 0 : if (__new_nstart < this->_M_impl._M_start._M_node)
931 0 : std::copy(this->_M_impl._M_start._M_node,
932 0 : this->_M_impl._M_finish._M_node + 1,
933 : __new_nstart);
934 : else
935 0 : std::copy_backward(this->_M_impl._M_start._M_node,
936 0 : this->_M_impl._M_finish._M_node + 1,
937 0 : __new_nstart + __old_num_nodes);
938 : }
939 : else
940 : {
941 0 : size_type __new_map_size = this->_M_impl._M_map_size
942 0 : + std::max(this->_M_impl._M_map_size,
943 : __nodes_to_add) + 2;
944 :
945 0 : _Map_pointer __new_map = this->_M_allocate_map(__new_map_size);
946 0 : __new_nstart = __new_map + (__new_map_size - __new_num_nodes) / 2
947 0 : + (__add_at_front ? __nodes_to_add : 0);
948 0 : std::copy(this->_M_impl._M_start._M_node,
949 0 : this->_M_impl._M_finish._M_node + 1,
950 : __new_nstart);
951 0 : _M_deallocate_map(this->_M_impl._M_map, this->_M_impl._M_map_size);
952 :
953 0 : this->_M_impl._M_map = __new_map;
954 0 : this->_M_impl._M_map_size = __new_map_size;
955 : }
956 :
957 0 : this->_M_impl._M_start._M_set_node(__new_nstart);
958 0 : this->_M_impl._M_finish._M_set_node(__new_nstart + __old_num_nodes - 1);
959 0 : }
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
|