Line data Source code
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 :
59 : namespace 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 5767 : deque<_Tp, _Alloc>::
163 : emplace_back(_Args&&... __args)
164 : {
165 5767 : if (this->_M_impl._M_finish._M_cur
166 5767 : != this->_M_impl._M_finish._M_last - 1)
167 : {
168 5767 : _Alloc_traits::construct(this->_M_impl,
169 : this->_M_impl._M_finish._M_cur,
170 : std::forward<_Args>(__args)...);
171 5767 : ++this->_M_impl._M_finish._M_cur;
172 : }
173 : else
174 0 : _M_push_back_aux(std::forward<_Args>(__args)...);
175 : #if __cplusplus > 201402L
176 : return back();
177 : #endif
178 5730 : }
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 0 : 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 0 : if (size() == max_size())
488 0 : __throw_length_error(
489 : __N("cannot create std::deque larger than max_size()"));
490 :
491 0 : _M_reserve_map_at_back();
492 0 : *(this->_M_impl._M_finish._M_node + 1) = this->_M_allocate_node();
493 : __try
494 : {
495 : #if __cplusplus >= 201103L
496 0 : _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 0 : this->_M_impl._M_finish._M_set_node(this->_M_impl._M_finish._M_node
503 : + 1);
504 0 : this->_M_impl._M_finish._M_cur = this->_M_impl._M_finish._M_first;
505 : }
506 0 : __catch(...)
507 : {
508 0 : _M_deallocate_node(*(this->_M_impl._M_finish._M_node + 1));
509 0 : __throw_exception_again;
510 : }
511 0 : }
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 0 : void deque<_Tp, _Alloc>::
556 : _M_pop_back_aux()
557 : {
558 0 : _M_deallocate_node(this->_M_impl._M_finish._M_first);
559 0 : this->_M_impl._M_finish._M_set_node(this->_M_impl._M_finish._M_node - 1);
560 0 : this->_M_impl._M_finish._M_cur = this->_M_impl._M_finish._M_last - 1;
561 0 : _Alloc_traits::destroy(_M_get_Tp_allocator(),
562 : this->_M_impl._M_finish._M_cur);
563 0 : }
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 0 : void deque<_Tp, _Alloc>::
572 : _M_pop_front_aux()
573 : {
574 0 : _Alloc_traits::destroy(_M_get_Tp_allocator(),
575 : this->_M_impl._M_start._M_cur);
576 0 : _M_deallocate_node(this->_M_impl._M_start._M_first);
577 0 : this->_M_impl._M_start._M_set_node(this->_M_impl._M_start._M_node + 1);
578 0 : this->_M_impl._M_start._M_cur = this->_M_impl._M_start._M_first;
579 0 : }
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 0 : deque<_Tp, _Alloc>::
594 : _M_range_insert_aux(iterator __pos,
595 : _ForwardIterator __first, _ForwardIterator __last,
596 : std::forward_iterator_tag)
597 : {
598 0 : const size_type __n = std::distance(__first, __last);
599 0 : if (__pos._M_cur == this->_M_impl._M_start._M_cur)
600 : {
601 0 : iterator __new_start = _M_reserve_elements_at_front(__n);
602 : __try
603 : {
604 0 : std::__uninitialized_copy_a(__first, __last, __new_start,
605 0 : _M_get_Tp_allocator());
606 0 : 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 0 : else if (__pos._M_cur == this->_M_impl._M_finish._M_cur)
616 : {
617 0 : iterator __new_finish = _M_reserve_elements_at_back(__n);
618 : __try
619 : {
620 0 : std::__uninitialized_copy_a(__first, __last,
621 0 : this->_M_impl._M_finish,
622 0 : _M_get_Tp_allocator());
623 0 : 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 0 : _M_insert_aux(__pos, __first, __last, __n);
634 0 : }
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 0 : deque<_Tp, _Alloc>::
767 : _M_insert_aux(iterator __pos,
768 : _ForwardIterator __first, _ForwardIterator __last,
769 : size_type __n)
770 : {
771 0 : const difference_type __elemsbefore = __pos - this->_M_impl._M_start;
772 0 : const size_type __length = size();
773 0 : if (static_cast<size_type>(__elemsbefore) < __length / 2)
774 : {
775 0 : iterator __new_start = _M_reserve_elements_at_front(__n);
776 0 : iterator __old_start = this->_M_impl._M_start;
777 0 : __pos = this->_M_impl._M_start + __elemsbefore;
778 : __try
779 : {
780 0 : if (__elemsbefore >= difference_type(__n))
781 : {
782 0 : iterator __start_n = (this->_M_impl._M_start
783 : + difference_type(__n));
784 0 : std::__uninitialized_move_a(this->_M_impl._M_start,
785 : __start_n, __new_start,
786 0 : _M_get_Tp_allocator());
787 0 : this->_M_impl._M_start = __new_start;
788 0 : _GLIBCXX_MOVE3(__start_n, __pos, __old_start);
789 0 : std::copy(__first, __last, __pos - difference_type(__n));
790 : }
791 : else
792 : {
793 0 : _ForwardIterator __mid = __first;
794 0 : std::advance(__mid, difference_type(__n) - __elemsbefore);
795 0 : std::__uninitialized_move_copy(this->_M_impl._M_start,
796 : __pos, __first, __mid,
797 : __new_start,
798 0 : _M_get_Tp_allocator());
799 0 : this->_M_impl._M_start = __new_start;
800 0 : 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 0 : iterator __new_finish = _M_reserve_elements_at_back(__n);
813 0 : iterator __old_finish = this->_M_impl._M_finish;
814 0 : const difference_type __elemsafter =
815 : difference_type(__length) - __elemsbefore;
816 0 : __pos = this->_M_impl._M_finish - __elemsafter;
817 : __try
818 : {
819 0 : if (__elemsafter > difference_type(__n))
820 : {
821 0 : iterator __finish_n = (this->_M_impl._M_finish
822 : - difference_type(__n));
823 0 : std::__uninitialized_move_a(__finish_n,
824 0 : this->_M_impl._M_finish,
825 0 : this->_M_impl._M_finish,
826 0 : _M_get_Tp_allocator());
827 0 : this->_M_impl._M_finish = __new_finish;
828 0 : _GLIBCXX_MOVE_BACKWARD3(__pos, __finish_n, __old_finish);
829 0 : std::copy(__first, __last, __pos);
830 : }
831 : else
832 : {
833 0 : _ForwardIterator __mid = __first;
834 0 : std::advance(__mid, __elemsafter);
835 0 : std::__uninitialized_copy_move(__mid, __last, __pos,
836 0 : this->_M_impl._M_finish,
837 0 : this->_M_impl._M_finish,
838 0 : _M_get_Tp_allocator());
839 0 : this->_M_impl._M_finish = __new_finish;
840 0 : 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 0 : }
851 :
852 : template<typename _Tp, typename _Alloc>
853 : void
854 0 : deque<_Tp, _Alloc>::
855 : _M_destroy_data_aux(iterator __first, iterator __last)
856 : {
857 0 : for (_Map_pointer __node = __first._M_node + 1;
858 0 : __node < __last._M_node; ++__node)
859 0 : std::_Destroy(*__node, *__node + _S_buffer_size(),
860 0 : _M_get_Tp_allocator());
861 :
862 0 : if (__first._M_node != __last._M_node)
863 : {
864 0 : std::_Destroy(__first._M_cur, __first._M_last,
865 0 : _M_get_Tp_allocator());
866 0 : std::_Destroy(__last._M_first, __last._M_cur,
867 0 : _M_get_Tp_allocator());
868 : }
869 : else
870 0 : std::_Destroy(__first._M_cur, __last._M_cur,
871 0 : _M_get_Tp_allocator());
872 0 : }
873 :
874 : template <typename _Tp, typename _Alloc>
875 : void
876 0 : deque<_Tp, _Alloc>::
877 : _M_new_elements_at_front(size_type __new_elems)
878 : {
879 0 : if (this->max_size() - this->size() < __new_elems)
880 0 : __throw_length_error(__N("deque::_M_new_elements_at_front"));
881 :
882 0 : const size_type __new_nodes = ((__new_elems + _S_buffer_size() - 1)
883 : / _S_buffer_size());
884 0 : _M_reserve_map_at_front(__new_nodes);
885 : size_type __i;
886 : __try
887 : {
888 0 : for (__i = 1; __i <= __new_nodes; ++__i)
889 0 : *(this->_M_impl._M_start._M_node - __i) = this->_M_allocate_node();
890 : }
891 0 : __catch(...)
892 : {
893 0 : for (size_type __j = 1; __j < __i; ++__j)
894 0 : _M_deallocate_node(*(this->_M_impl._M_start._M_node - __j));
895 0 : __throw_exception_again;
896 : }
897 0 : }
898 :
899 : template <typename _Tp, typename _Alloc>
900 : void
901 0 : deque<_Tp, _Alloc>::
902 : _M_new_elements_at_back(size_type __new_elems)
903 : {
904 0 : if (this->max_size() - this->size() < __new_elems)
905 0 : __throw_length_error(__N("deque::_M_new_elements_at_back"));
906 :
907 0 : const size_type __new_nodes = ((__new_elems + _S_buffer_size() - 1)
908 : / _S_buffer_size());
909 0 : _M_reserve_map_at_back(__new_nodes);
910 : size_type __i;
911 : __try
912 : {
913 0 : for (__i = 1; __i <= __new_nodes; ++__i)
914 0 : *(this->_M_impl._M_finish._M_node + __i) = this->_M_allocate_node();
915 : }
916 0 : __catch(...)
917 : {
918 0 : for (size_type __j = 1; __j < __i; ++__j)
919 0 : _M_deallocate_node(*(this->_M_impl._M_finish._M_node + __j));
920 0 : __throw_exception_again;
921 : }
922 0 : }
923 :
924 : template <typename _Tp, typename _Alloc>
925 : void
926 0 : deque<_Tp, _Alloc>::
927 : _M_reallocate_map(size_type __nodes_to_add, bool __add_at_front)
928 : {
929 0 : const size_type __old_num_nodes
930 0 : = this->_M_impl._M_finish._M_node - this->_M_impl._M_start._M_node + 1;
931 0 : const size_type __new_num_nodes = __old_num_nodes + __nodes_to_add;
932 :
933 : _Map_pointer __new_nstart;
934 0 : if (this->_M_impl._M_map_size > 2 * __new_num_nodes)
935 : {
936 0 : __new_nstart = this->_M_impl._M_map + (this->_M_impl._M_map_size
937 0 : - __new_num_nodes) / 2
938 0 : + (__add_at_front ? __nodes_to_add : 0);
939 0 : if (__new_nstart < this->_M_impl._M_start._M_node)
940 0 : std::copy(this->_M_impl._M_start._M_node,
941 : this->_M_impl._M_finish._M_node + 1,
942 : __new_nstart);
943 : else
944 0 : 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 0 : size_type __new_map_size = this->_M_impl._M_map_size
951 0 : + std::max(this->_M_impl._M_map_size,
952 : __nodes_to_add) + 2;
953 :
954 0 : _Map_pointer __new_map = this->_M_allocate_map(__new_map_size);
955 0 : __new_nstart = __new_map + (__new_map_size - __new_num_nodes) / 2
956 0 : + (__add_at_front ? __nodes_to_add : 0);
957 0 : std::copy(this->_M_impl._M_start._M_node,
958 0 : this->_M_impl._M_finish._M_node + 1,
959 : __new_nstart);
960 0 : _M_deallocate_map(this->_M_impl._M_map, this->_M_impl._M_map_size);
961 :
962 0 : this->_M_impl._M_map = __new_map;
963 0 : this->_M_impl._M_map_size = __new_map_size;
964 : }
965 :
966 0 : this->_M_impl._M_start._M_set_node(__new_nstart);
967 0 : this->_M_impl._M_finish._M_set_node(__new_nstart + __old_num_nodes - 1);
968 0 : }
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 0 : 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 0 : difference_type __len = __last - __first;
1065 0 : while (__len > 0)
1066 : {
1067 0 : const difference_type __clen
1068 0 : = std::min(__len, std::min(__first._M_last - __first._M_cur,
1069 0 : __result._M_last - __result._M_cur));
1070 0 : std::move(__first._M_cur, __first._M_cur + __clen, __result._M_cur);
1071 0 : __first += __clen;
1072 0 : __result += __clen;
1073 0 : __len -= __clen;
1074 : }
1075 0 : return __result;
1076 : }
1077 :
1078 : template<typename _Tp>
1079 : _Deque_iterator<_Tp, _Tp&, _Tp*>
1080 0 : 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 0 : difference_type __len = __last - __first;
1088 0 : while (__len > 0)
1089 : {
1090 0 : difference_type __llen = __last._M_cur - __last._M_first;
1091 0 : _Tp* __lend = __last._M_cur;
1092 :
1093 0 : difference_type __rlen = __result._M_cur - __result._M_first;
1094 0 : _Tp* __rend = __result._M_cur;
1095 :
1096 0 : if (!__llen)
1097 : {
1098 0 : __llen = _Self::_S_buffer_size();
1099 0 : __lend = *(__last._M_node - 1) + __llen;
1100 : }
1101 0 : if (!__rlen)
1102 : {
1103 0 : __rlen = _Self::_S_buffer_size();
1104 0 : __rend = *(__result._M_node - 1) + __rlen;
1105 : }
1106 :
1107 0 : const difference_type __clen = std::min(__len,
1108 : std::min(__llen, __rlen));
1109 0 : std::move_backward(__lend - __clen, __lend, __rend);
1110 0 : __last -= __clen;
1111 0 : __result -= __clen;
1112 0 : __len -= __clen;
1113 : }
1114 0 : return __result;
1115 : }
1116 : #endif
1117 :
1118 : _GLIBCXX_END_NAMESPACE_CONTAINER
1119 : _GLIBCXX_END_NAMESPACE_VERSION
1120 : } // namespace std
1121 :
1122 : #endif
|
