Line data Source code
1 : // Deque implementation (out of line) -*- C++ -*-
2 :
3 : // Copyright (C) 2001-2018 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 227 : deque<_Tp, _Alloc>::
163 : emplace_back(_Args&&... __args)
164 : {
165 454 : if (this->_M_impl._M_finish._M_cur
166 227 : != this->_M_impl._M_finish._M_last - 1)
167 : {
168 227 : _Alloc_traits::construct(this->_M_impl,
169 : this->_M_impl._M_finish._M_cur,
170 : std::forward<_Args>(__args)...);
171 227 : ++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 227 : return back();
177 : #endif
178 : }
179 : #endif
180 :
181 : #if __cplusplus >= 201103L
182 : template<typename _Tp, typename _Alloc>
183 : template<typename... _Args>
184 : typename deque<_Tp, _Alloc>::iterator
185 : deque<_Tp, _Alloc>::
186 : emplace(const_iterator __position, _Args&&... __args)
187 : {
188 : if (__position._M_cur == this->_M_impl._M_start._M_cur)
189 : {
190 : emplace_front(std::forward<_Args>(__args)...);
191 : return this->_M_impl._M_start;
192 : }
193 : else if (__position._M_cur == this->_M_impl._M_finish._M_cur)
194 : {
195 : emplace_back(std::forward<_Args>(__args)...);
196 : iterator __tmp = this->_M_impl._M_finish;
197 : --__tmp;
198 : return __tmp;
199 : }
200 : else
201 : return _M_insert_aux(__position._M_const_cast(),
202 : std::forward<_Args>(__args)...);
203 : }
204 : #endif
205 :
206 : template <typename _Tp, typename _Alloc>
207 : typename deque<_Tp, _Alloc>::iterator
208 : deque<_Tp, _Alloc>::
209 : #if __cplusplus >= 201103L
210 : insert(const_iterator __position, const value_type& __x)
211 : #else
212 : insert(iterator __position, const value_type& __x)
213 : #endif
214 : {
215 : if (__position._M_cur == this->_M_impl._M_start._M_cur)
216 : {
217 : push_front(__x);
218 : return this->_M_impl._M_start;
219 : }
220 : else if (__position._M_cur == this->_M_impl._M_finish._M_cur)
221 : {
222 : push_back(__x);
223 : iterator __tmp = this->_M_impl._M_finish;
224 : --__tmp;
225 : return __tmp;
226 : }
227 : else
228 : return _M_insert_aux(__position._M_const_cast(), __x);
229 : }
230 :
231 : template <typename _Tp, typename _Alloc>
232 : typename deque<_Tp, _Alloc>::iterator
233 : deque<_Tp, _Alloc>::
234 : _M_erase(iterator __position)
235 : {
236 : iterator __next = __position;
237 : ++__next;
238 : const difference_type __index = __position - begin();
239 : if (static_cast<size_type>(__index) < (size() >> 1))
240 : {
241 : if (__position != begin())
242 : _GLIBCXX_MOVE_BACKWARD3(begin(), __position, __next);
243 : pop_front();
244 : }
245 : else
246 : {
247 : if (__next != end())
248 : _GLIBCXX_MOVE3(__next, end(), __position);
249 : pop_back();
250 : }
251 : return begin() + __index;
252 : }
253 :
254 : template <typename _Tp, typename _Alloc>
255 : typename deque<_Tp, _Alloc>::iterator
256 : deque<_Tp, _Alloc>::
257 : _M_erase(iterator __first, iterator __last)
258 : {
259 : if (__first == __last)
260 : return __first;
261 : else if (__first == begin() && __last == end())
262 : {
263 : clear();
264 : return end();
265 : }
266 : else
267 : {
268 : const difference_type __n = __last - __first;
269 : const difference_type __elems_before = __first - begin();
270 : if (static_cast<size_type>(__elems_before) <= (size() - __n) / 2)
271 : {
272 : if (__first != begin())
273 : _GLIBCXX_MOVE_BACKWARD3(begin(), __first, __last);
274 : _M_erase_at_begin(begin() + __n);
275 : }
276 : else
277 : {
278 : if (__last != end())
279 : _GLIBCXX_MOVE3(__last, end(), __first);
280 : _M_erase_at_end(end() - __n);
281 : }
282 : return begin() + __elems_before;
283 : }
284 : }
285 :
286 : template <typename _Tp, class _Alloc>
287 : template <typename _InputIterator>
288 : void
289 : deque<_Tp, _Alloc>::
290 : _M_assign_aux(_InputIterator __first, _InputIterator __last,
291 : std::input_iterator_tag)
292 : {
293 : iterator __cur = begin();
294 : for (; __first != __last && __cur != end(); ++__cur, ++__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(__n);
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 : _M_reserve_map_at_back();
488 0 : *(this->_M_impl._M_finish._M_node + 1) = this->_M_allocate_node();
489 : __try
490 : {
491 : #if __cplusplus >= 201103L
492 0 : _Alloc_traits::construct(this->_M_impl,
493 : this->_M_impl._M_finish._M_cur,
494 : std::forward<_Args>(__args)...);
495 : #else
496 : this->_M_impl.construct(this->_M_impl._M_finish._M_cur, __t);
497 : #endif
498 0 : this->_M_impl._M_finish._M_set_node(this->_M_impl._M_finish._M_node
499 : + 1);
500 0 : this->_M_impl._M_finish._M_cur = this->_M_impl._M_finish._M_first;
501 : }
502 0 : __catch(...)
503 : {
504 0 : _M_deallocate_node(*(this->_M_impl._M_finish._M_node + 1));
505 0 : __throw_exception_again;
506 : }
507 0 : }
508 :
509 : // Called only if _M_impl._M_start._M_cur == _M_impl._M_start._M_first.
510 : template<typename _Tp, typename _Alloc>
511 : #if __cplusplus >= 201103L
512 : template<typename... _Args>
513 : void
514 : deque<_Tp, _Alloc>::
515 : _M_push_front_aux(_Args&&... __args)
516 : #else
517 : void
518 : deque<_Tp, _Alloc>::
519 : _M_push_front_aux(const value_type& __t)
520 : #endif
521 : {
522 : _M_reserve_map_at_front();
523 : *(this->_M_impl._M_start._M_node - 1) = this->_M_allocate_node();
524 : __try
525 : {
526 : this->_M_impl._M_start._M_set_node(this->_M_impl._M_start._M_node
527 : - 1);
528 : this->_M_impl._M_start._M_cur = this->_M_impl._M_start._M_last - 1;
529 : #if __cplusplus >= 201103L
530 : _Alloc_traits::construct(this->_M_impl,
531 : this->_M_impl._M_start._M_cur,
532 : std::forward<_Args>(__args)...);
533 : #else
534 : this->_M_impl.construct(this->_M_impl._M_start._M_cur, __t);
535 : #endif
536 : }
537 : __catch(...)
538 : {
539 : ++this->_M_impl._M_start;
540 : _M_deallocate_node(*(this->_M_impl._M_start._M_node - 1));
541 : __throw_exception_again;
542 : }
543 : }
544 :
545 : // Called only if _M_impl._M_finish._M_cur == _M_impl._M_finish._M_first.
546 : template <typename _Tp, typename _Alloc>
547 : void deque<_Tp, _Alloc>::
548 : _M_pop_back_aux()
549 : {
550 : _M_deallocate_node(this->_M_impl._M_finish._M_first);
551 : this->_M_impl._M_finish._M_set_node(this->_M_impl._M_finish._M_node - 1);
552 : this->_M_impl._M_finish._M_cur = this->_M_impl._M_finish._M_last - 1;
553 : _Alloc_traits::destroy(_M_get_Tp_allocator(),
554 : this->_M_impl._M_finish._M_cur);
555 : }
556 :
557 : // Called only if _M_impl._M_start._M_cur == _M_impl._M_start._M_last - 1.
558 : // Note that if the deque has at least one element (a precondition for this
559 : // member function), and if
560 : // _M_impl._M_start._M_cur == _M_impl._M_start._M_last,
561 : // then the deque must have at least two nodes.
562 : template <typename _Tp, typename _Alloc>
563 0 : void deque<_Tp, _Alloc>::
564 : _M_pop_front_aux()
565 : {
566 0 : _Alloc_traits::destroy(_M_get_Tp_allocator(),
567 : this->_M_impl._M_start._M_cur);
568 0 : _M_deallocate_node(this->_M_impl._M_start._M_first);
569 0 : this->_M_impl._M_start._M_set_node(this->_M_impl._M_start._M_node + 1);
570 0 : this->_M_impl._M_start._M_cur = this->_M_impl._M_start._M_first;
571 0 : }
572 :
573 : template <typename _Tp, typename _Alloc>
574 : template <typename _InputIterator>
575 : void
576 : deque<_Tp, _Alloc>::
577 : _M_range_insert_aux(iterator __pos,
578 : _InputIterator __first, _InputIterator __last,
579 : std::input_iterator_tag)
580 : { std::copy(__first, __last, std::inserter(*this, __pos)); }
581 :
582 : template <typename _Tp, typename _Alloc>
583 : template <typename _ForwardIterator>
584 : void
585 : deque<_Tp, _Alloc>::
586 : _M_range_insert_aux(iterator __pos,
587 : _ForwardIterator __first, _ForwardIterator __last,
588 : std::forward_iterator_tag)
589 : {
590 : const size_type __n = std::distance(__first, __last);
591 : if (__pos._M_cur == this->_M_impl._M_start._M_cur)
592 : {
593 : iterator __new_start = _M_reserve_elements_at_front(__n);
594 : __try
595 : {
596 : std::__uninitialized_copy_a(__first, __last, __new_start,
597 : _M_get_Tp_allocator());
598 : this->_M_impl._M_start = __new_start;
599 : }
600 : __catch(...)
601 : {
602 : _M_destroy_nodes(__new_start._M_node,
603 : this->_M_impl._M_start._M_node);
604 : __throw_exception_again;
605 : }
606 : }
607 : else if (__pos._M_cur == this->_M_impl._M_finish._M_cur)
608 : {
609 : iterator __new_finish = _M_reserve_elements_at_back(__n);
610 : __try
611 : {
612 : std::__uninitialized_copy_a(__first, __last,
613 : this->_M_impl._M_finish,
614 : _M_get_Tp_allocator());
615 : this->_M_impl._M_finish = __new_finish;
616 : }
617 : __catch(...)
618 : {
619 : _M_destroy_nodes(this->_M_impl._M_finish._M_node + 1,
620 : __new_finish._M_node + 1);
621 : __throw_exception_again;
622 : }
623 : }
624 : else
625 : _M_insert_aux(__pos, __first, __last, __n);
626 : }
627 :
628 : template<typename _Tp, typename _Alloc>
629 : #if __cplusplus >= 201103L
630 : template<typename... _Args>
631 : typename deque<_Tp, _Alloc>::iterator
632 : deque<_Tp, _Alloc>::
633 : _M_insert_aux(iterator __pos, _Args&&... __args)
634 : {
635 : value_type __x_copy(std::forward<_Args>(__args)...); // XXX copy
636 : #else
637 : typename deque<_Tp, _Alloc>::iterator
638 : deque<_Tp, _Alloc>::
639 : _M_insert_aux(iterator __pos, const value_type& __x)
640 : {
641 : value_type __x_copy = __x; // XXX copy
642 : #endif
643 : difference_type __index = __pos - this->_M_impl._M_start;
644 : if (static_cast<size_type>(__index) < size() / 2)
645 : {
646 : push_front(_GLIBCXX_MOVE(front()));
647 : iterator __front1 = this->_M_impl._M_start;
648 : ++__front1;
649 : iterator __front2 = __front1;
650 : ++__front2;
651 : __pos = this->_M_impl._M_start + __index;
652 : iterator __pos1 = __pos;
653 : ++__pos1;
654 : _GLIBCXX_MOVE3(__front2, __pos1, __front1);
655 : }
656 : else
657 : {
658 : push_back(_GLIBCXX_MOVE(back()));
659 : iterator __back1 = this->_M_impl._M_finish;
660 : --__back1;
661 : iterator __back2 = __back1;
662 : --__back2;
663 : __pos = this->_M_impl._M_start + __index;
664 : _GLIBCXX_MOVE_BACKWARD3(__pos, __back2, __back1);
665 : }
666 : *__pos = _GLIBCXX_MOVE(__x_copy);
667 : return __pos;
668 : }
669 :
670 : template <typename _Tp, typename _Alloc>
671 : void
672 : deque<_Tp, _Alloc>::
673 : _M_insert_aux(iterator __pos, size_type __n, const value_type& __x)
674 : {
675 : const difference_type __elems_before = __pos - this->_M_impl._M_start;
676 : const size_type __length = this->size();
677 : value_type __x_copy = __x;
678 : if (__elems_before < difference_type(__length / 2))
679 : {
680 : iterator __new_start = _M_reserve_elements_at_front(__n);
681 : iterator __old_start = this->_M_impl._M_start;
682 : __pos = this->_M_impl._M_start + __elems_before;
683 : __try
684 : {
685 : if (__elems_before >= difference_type(__n))
686 : {
687 : iterator __start_n = (this->_M_impl._M_start
688 : + difference_type(__n));
689 : std::__uninitialized_move_a(this->_M_impl._M_start,
690 : __start_n, __new_start,
691 : _M_get_Tp_allocator());
692 : this->_M_impl._M_start = __new_start;
693 : _GLIBCXX_MOVE3(__start_n, __pos, __old_start);
694 : std::fill(__pos - difference_type(__n), __pos, __x_copy);
695 : }
696 : else
697 : {
698 : std::__uninitialized_move_fill(this->_M_impl._M_start,
699 : __pos, __new_start,
700 : this->_M_impl._M_start,
701 : __x_copy,
702 : _M_get_Tp_allocator());
703 : this->_M_impl._M_start = __new_start;
704 : std::fill(__old_start, __pos, __x_copy);
705 : }
706 : }
707 : __catch(...)
708 : {
709 : _M_destroy_nodes(__new_start._M_node,
710 : this->_M_impl._M_start._M_node);
711 : __throw_exception_again;
712 : }
713 : }
714 : else
715 : {
716 : iterator __new_finish = _M_reserve_elements_at_back(__n);
717 : iterator __old_finish = this->_M_impl._M_finish;
718 : const difference_type __elems_after =
719 : difference_type(__length) - __elems_before;
720 : __pos = this->_M_impl._M_finish - __elems_after;
721 : __try
722 : {
723 : if (__elems_after > difference_type(__n))
724 : {
725 : iterator __finish_n = (this->_M_impl._M_finish
726 : - difference_type(__n));
727 : std::__uninitialized_move_a(__finish_n,
728 : this->_M_impl._M_finish,
729 : this->_M_impl._M_finish,
730 : _M_get_Tp_allocator());
731 : this->_M_impl._M_finish = __new_finish;
732 : _GLIBCXX_MOVE_BACKWARD3(__pos, __finish_n, __old_finish);
733 : std::fill(__pos, __pos + difference_type(__n), __x_copy);
734 : }
735 : else
736 : {
737 : std::__uninitialized_fill_move(this->_M_impl._M_finish,
738 : __pos + difference_type(__n),
739 : __x_copy, __pos,
740 : this->_M_impl._M_finish,
741 : _M_get_Tp_allocator());
742 : this->_M_impl._M_finish = __new_finish;
743 : std::fill(__pos, __old_finish, __x_copy);
744 : }
745 : }
746 : __catch(...)
747 : {
748 : _M_destroy_nodes(this->_M_impl._M_finish._M_node + 1,
749 : __new_finish._M_node + 1);
750 : __throw_exception_again;
751 : }
752 : }
753 : }
754 :
755 : template <typename _Tp, typename _Alloc>
756 : template <typename _ForwardIterator>
757 : void
758 : deque<_Tp, _Alloc>::
759 : _M_insert_aux(iterator __pos,
760 : _ForwardIterator __first, _ForwardIterator __last,
761 : size_type __n)
762 : {
763 : const difference_type __elemsbefore = __pos - this->_M_impl._M_start;
764 : const size_type __length = size();
765 : if (static_cast<size_type>(__elemsbefore) < __length / 2)
766 : {
767 : iterator __new_start = _M_reserve_elements_at_front(__n);
768 : iterator __old_start = this->_M_impl._M_start;
769 : __pos = this->_M_impl._M_start + __elemsbefore;
770 : __try
771 : {
772 : if (__elemsbefore >= difference_type(__n))
773 : {
774 : iterator __start_n = (this->_M_impl._M_start
775 : + difference_type(__n));
776 : std::__uninitialized_move_a(this->_M_impl._M_start,
777 : __start_n, __new_start,
778 : _M_get_Tp_allocator());
779 : this->_M_impl._M_start = __new_start;
780 : _GLIBCXX_MOVE3(__start_n, __pos, __old_start);
781 : std::copy(__first, __last, __pos - difference_type(__n));
782 : }
783 : else
784 : {
785 : _ForwardIterator __mid = __first;
786 : std::advance(__mid, difference_type(__n) - __elemsbefore);
787 : std::__uninitialized_move_copy(this->_M_impl._M_start,
788 : __pos, __first, __mid,
789 : __new_start,
790 : _M_get_Tp_allocator());
791 : this->_M_impl._M_start = __new_start;
792 : std::copy(__mid, __last, __old_start);
793 : }
794 : }
795 : __catch(...)
796 : {
797 : _M_destroy_nodes(__new_start._M_node,
798 : this->_M_impl._M_start._M_node);
799 : __throw_exception_again;
800 : }
801 : }
802 : else
803 : {
804 : iterator __new_finish = _M_reserve_elements_at_back(__n);
805 : iterator __old_finish = this->_M_impl._M_finish;
806 : const difference_type __elemsafter =
807 : difference_type(__length) - __elemsbefore;
808 : __pos = this->_M_impl._M_finish - __elemsafter;
809 : __try
810 : {
811 : if (__elemsafter > difference_type(__n))
812 : {
813 : iterator __finish_n = (this->_M_impl._M_finish
814 : - difference_type(__n));
815 : std::__uninitialized_move_a(__finish_n,
816 : this->_M_impl._M_finish,
817 : this->_M_impl._M_finish,
818 : _M_get_Tp_allocator());
819 : this->_M_impl._M_finish = __new_finish;
820 : _GLIBCXX_MOVE_BACKWARD3(__pos, __finish_n, __old_finish);
821 : std::copy(__first, __last, __pos);
822 : }
823 : else
824 : {
825 : _ForwardIterator __mid = __first;
826 : std::advance(__mid, __elemsafter);
827 : std::__uninitialized_copy_move(__mid, __last, __pos,
828 : this->_M_impl._M_finish,
829 : this->_M_impl._M_finish,
830 : _M_get_Tp_allocator());
831 : this->_M_impl._M_finish = __new_finish;
832 : std::copy(__first, __mid, __pos);
833 : }
834 : }
835 : __catch(...)
836 : {
837 : _M_destroy_nodes(this->_M_impl._M_finish._M_node + 1,
838 : __new_finish._M_node + 1);
839 : __throw_exception_again;
840 : }
841 : }
842 : }
843 :
844 : template<typename _Tp, typename _Alloc>
845 : void
846 : deque<_Tp, _Alloc>::
847 : _M_destroy_data_aux(iterator __first, iterator __last)
848 : {
849 : for (_Map_pointer __node = __first._M_node + 1;
850 : __node < __last._M_node; ++__node)
851 : std::_Destroy(*__node, *__node + _S_buffer_size(),
852 : _M_get_Tp_allocator());
853 :
854 : if (__first._M_node != __last._M_node)
855 : {
856 : std::_Destroy(__first._M_cur, __first._M_last,
857 : _M_get_Tp_allocator());
858 : std::_Destroy(__last._M_first, __last._M_cur,
859 : _M_get_Tp_allocator());
860 : }
861 : else
862 : std::_Destroy(__first._M_cur, __last._M_cur,
863 : _M_get_Tp_allocator());
864 : }
865 :
866 : template <typename _Tp, typename _Alloc>
867 : void
868 : deque<_Tp, _Alloc>::
869 : _M_new_elements_at_front(size_type __new_elems)
870 : {
871 : if (this->max_size() - this->size() < __new_elems)
872 : __throw_length_error(__N("deque::_M_new_elements_at_front"));
873 :
874 : const size_type __new_nodes = ((__new_elems + _S_buffer_size() - 1)
875 : / _S_buffer_size());
876 : _M_reserve_map_at_front(__new_nodes);
877 : size_type __i;
878 : __try
879 : {
880 : for (__i = 1; __i <= __new_nodes; ++__i)
881 : *(this->_M_impl._M_start._M_node - __i) = this->_M_allocate_node();
882 : }
883 : __catch(...)
884 : {
885 : for (size_type __j = 1; __j < __i; ++__j)
886 : _M_deallocate_node(*(this->_M_impl._M_start._M_node - __j));
887 : __throw_exception_again;
888 : }
889 : }
890 :
891 : template <typename _Tp, typename _Alloc>
892 : void
893 : deque<_Tp, _Alloc>::
894 : _M_new_elements_at_back(size_type __new_elems)
895 : {
896 : if (this->max_size() - this->size() < __new_elems)
897 : __throw_length_error(__N("deque::_M_new_elements_at_back"));
898 :
899 : const size_type __new_nodes = ((__new_elems + _S_buffer_size() - 1)
900 : / _S_buffer_size());
901 : _M_reserve_map_at_back(__new_nodes);
902 : size_type __i;
903 : __try
904 : {
905 : for (__i = 1; __i <= __new_nodes; ++__i)
906 : *(this->_M_impl._M_finish._M_node + __i) = this->_M_allocate_node();
907 : }
908 : __catch(...)
909 : {
910 : for (size_type __j = 1; __j < __i; ++__j)
911 : _M_deallocate_node(*(this->_M_impl._M_finish._M_node + __j));
912 : __throw_exception_again;
913 : }
914 : }
915 :
916 : template <typename _Tp, typename _Alloc>
917 : void
918 0 : deque<_Tp, _Alloc>::
919 : _M_reallocate_map(size_type __nodes_to_add, bool __add_at_front)
920 : {
921 0 : const size_type __old_num_nodes
922 0 : = this->_M_impl._M_finish._M_node - this->_M_impl._M_start._M_node + 1;
923 0 : const size_type __new_num_nodes = __old_num_nodes + __nodes_to_add;
924 :
925 : _Map_pointer __new_nstart;
926 0 : if (this->_M_impl._M_map_size > 2 * __new_num_nodes)
927 : {
928 0 : __new_nstart = this->_M_impl._M_map + (this->_M_impl._M_map_size
929 0 : - __new_num_nodes) / 2
930 0 : + (__add_at_front ? __nodes_to_add : 0);
931 0 : if (__new_nstart < this->_M_impl._M_start._M_node)
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 : else
936 0 : std::copy_backward(this->_M_impl._M_start._M_node,
937 0 : this->_M_impl._M_finish._M_node + 1,
938 0 : __new_nstart + __old_num_nodes);
939 : }
940 : else
941 : {
942 0 : size_type __new_map_size = this->_M_impl._M_map_size
943 0 : + std::max(this->_M_impl._M_map_size,
944 : __nodes_to_add) + 2;
945 :
946 0 : _Map_pointer __new_map = this->_M_allocate_map(__new_map_size);
947 0 : __new_nstart = __new_map + (__new_map_size - __new_num_nodes) / 2
948 0 : + (__add_at_front ? __nodes_to_add : 0);
949 0 : std::copy(this->_M_impl._M_start._M_node,
950 0 : this->_M_impl._M_finish._M_node + 1,
951 : __new_nstart);
952 0 : _M_deallocate_map(this->_M_impl._M_map, this->_M_impl._M_map_size);
953 :
954 0 : this->_M_impl._M_map = __new_map;
955 0 : this->_M_impl._M_map_size = __new_map_size;
956 : }
957 :
958 0 : this->_M_impl._M_start._M_set_node(__new_nstart);
959 0 : this->_M_impl._M_finish._M_set_node(__new_nstart + __old_num_nodes - 1);
960 0 : }
961 :
962 : // Overload for deque::iterators, exploiting the "segmented-iterator
963 : // optimization".
964 : template<typename _Tp>
965 : void
966 : fill(const _Deque_iterator<_Tp, _Tp&, _Tp*>& __first,
967 : const _Deque_iterator<_Tp, _Tp&, _Tp*>& __last, const _Tp& __value)
968 : {
969 : typedef typename _Deque_iterator<_Tp, _Tp&, _Tp*>::_Self _Self;
970 :
971 : for (typename _Self::_Map_pointer __node = __first._M_node + 1;
972 : __node < __last._M_node; ++__node)
973 : std::fill(*__node, *__node + _Self::_S_buffer_size(), __value);
974 :
975 : if (__first._M_node != __last._M_node)
976 : {
977 : std::fill(__first._M_cur, __first._M_last, __value);
978 : std::fill(__last._M_first, __last._M_cur, __value);
979 : }
980 : else
981 : std::fill(__first._M_cur, __last._M_cur, __value);
982 : }
983 :
984 : template<typename _Tp>
985 : _Deque_iterator<_Tp, _Tp&, _Tp*>
986 : copy(_Deque_iterator<_Tp, const _Tp&, const _Tp*> __first,
987 : _Deque_iterator<_Tp, const _Tp&, const _Tp*> __last,
988 : _Deque_iterator<_Tp, _Tp&, _Tp*> __result)
989 : {
990 : typedef typename _Deque_iterator<_Tp, _Tp&, _Tp*>::_Self _Self;
991 : typedef typename _Self::difference_type difference_type;
992 :
993 : difference_type __len = __last - __first;
994 : while (__len > 0)
995 : {
996 : const difference_type __clen
997 : = std::min(__len, std::min(__first._M_last - __first._M_cur,
998 : __result._M_last - __result._M_cur));
999 : std::copy(__first._M_cur, __first._M_cur + __clen, __result._M_cur);
1000 : __first += __clen;
1001 : __result += __clen;
1002 : __len -= __clen;
1003 : }
1004 : return __result;
1005 : }
1006 :
1007 : template<typename _Tp>
1008 : _Deque_iterator<_Tp, _Tp&, _Tp*>
1009 : copy_backward(_Deque_iterator<_Tp, const _Tp&, const _Tp*> __first,
1010 : _Deque_iterator<_Tp, const _Tp&, const _Tp*> __last,
1011 : _Deque_iterator<_Tp, _Tp&, _Tp*> __result)
1012 : {
1013 : typedef typename _Deque_iterator<_Tp, _Tp&, _Tp*>::_Self _Self;
1014 : typedef typename _Self::difference_type difference_type;
1015 :
1016 : difference_type __len = __last - __first;
1017 : while (__len > 0)
1018 : {
1019 : difference_type __llen = __last._M_cur - __last._M_first;
1020 : _Tp* __lend = __last._M_cur;
1021 :
1022 : difference_type __rlen = __result._M_cur - __result._M_first;
1023 : _Tp* __rend = __result._M_cur;
1024 :
1025 : if (!__llen)
1026 : {
1027 : __llen = _Self::_S_buffer_size();
1028 : __lend = *(__last._M_node - 1) + __llen;
1029 : }
1030 : if (!__rlen)
1031 : {
1032 : __rlen = _Self::_S_buffer_size();
1033 : __rend = *(__result._M_node - 1) + __rlen;
1034 : }
1035 :
1036 : const difference_type __clen = std::min(__len,
1037 : std::min(__llen, __rlen));
1038 : std::copy_backward(__lend - __clen, __lend, __rend);
1039 : __last -= __clen;
1040 : __result -= __clen;
1041 : __len -= __clen;
1042 : }
1043 : return __result;
1044 : }
1045 :
1046 : #if __cplusplus >= 201103L
1047 : template<typename _Tp>
1048 : _Deque_iterator<_Tp, _Tp&, _Tp*>
1049 : move(_Deque_iterator<_Tp, const _Tp&, const _Tp*> __first,
1050 : _Deque_iterator<_Tp, const _Tp&, const _Tp*> __last,
1051 : _Deque_iterator<_Tp, _Tp&, _Tp*> __result)
1052 : {
1053 : typedef typename _Deque_iterator<_Tp, _Tp&, _Tp*>::_Self _Self;
1054 : typedef typename _Self::difference_type difference_type;
1055 :
1056 : difference_type __len = __last - __first;
1057 : while (__len > 0)
1058 : {
1059 : const difference_type __clen
1060 : = std::min(__len, std::min(__first._M_last - __first._M_cur,
1061 : __result._M_last - __result._M_cur));
1062 : std::move(__first._M_cur, __first._M_cur + __clen, __result._M_cur);
1063 : __first += __clen;
1064 : __result += __clen;
1065 : __len -= __clen;
1066 : }
1067 : return __result;
1068 : }
1069 :
1070 : template<typename _Tp>
1071 : _Deque_iterator<_Tp, _Tp&, _Tp*>
1072 : move_backward(_Deque_iterator<_Tp, const _Tp&, const _Tp*> __first,
1073 : _Deque_iterator<_Tp, const _Tp&, const _Tp*> __last,
1074 : _Deque_iterator<_Tp, _Tp&, _Tp*> __result)
1075 : {
1076 : typedef typename _Deque_iterator<_Tp, _Tp&, _Tp*>::_Self _Self;
1077 : typedef typename _Self::difference_type difference_type;
1078 :
1079 : difference_type __len = __last - __first;
1080 : while (__len > 0)
1081 : {
1082 : difference_type __llen = __last._M_cur - __last._M_first;
1083 : _Tp* __lend = __last._M_cur;
1084 :
1085 : difference_type __rlen = __result._M_cur - __result._M_first;
1086 : _Tp* __rend = __result._M_cur;
1087 :
1088 : if (!__llen)
1089 : {
1090 : __llen = _Self::_S_buffer_size();
1091 : __lend = *(__last._M_node - 1) + __llen;
1092 : }
1093 : if (!__rlen)
1094 : {
1095 : __rlen = _Self::_S_buffer_size();
1096 : __rend = *(__result._M_node - 1) + __rlen;
1097 : }
1098 :
1099 : const difference_type __clen = std::min(__len,
1100 : std::min(__llen, __rlen));
1101 : std::move_backward(__lend - __clen, __lend, __rend);
1102 : __last -= __clen;
1103 : __result -= __clen;
1104 : __len -= __clen;
1105 : }
1106 : return __result;
1107 : }
1108 : #endif
1109 :
1110 : _GLIBCXX_END_NAMESPACE_CONTAINER
1111 : _GLIBCXX_END_NAMESPACE_VERSION
1112 : } // namespace std
1113 :
1114 : #endif
|
