Branch data Line data Source code
1 : : // Deque implementation (out of line) -*- C++ -*-
2 : :
3 : : // Copyright (C) 2001, 2002, 2003, 2004, 2005, 2006, 2007, 2008,
4 : : // 2009, 2010, 2011, 2012
5 : : // Free Software Foundation, Inc.
6 : : //
7 : : // This file is part of the GNU ISO C++ Library. This library is free
8 : : // software; you can redistribute it and/or modify it under the
9 : : // terms of the GNU General Public License as published by the
10 : : // Free Software Foundation; either version 3, or (at your option)
11 : : // any later version.
12 : :
13 : : // This library is distributed in the hope that it will be useful,
14 : : // but WITHOUT ANY WARRANTY; without even the implied warranty of
15 : : // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
16 : : // GNU General Public License for more details.
17 : :
18 : : // Under Section 7 of GPL version 3, you are granted additional
19 : : // permissions described in the GCC Runtime Library Exception, version
20 : : // 3.1, as published by the Free Software Foundation.
21 : :
22 : : // You should have received a copy of the GNU General Public License and
23 : : // a copy of the GCC Runtime Library Exception along with this program;
24 : : // see the files COPYING3 and COPYING.RUNTIME respectively. If not, see
25 : : // <http://www.gnu.org/licenses/>.
26 : :
27 : : /*
28 : : *
29 : : * Copyright (c) 1994
30 : : * Hewlett-Packard Company
31 : : *
32 : : * Permission to use, copy, modify, distribute and sell this software
33 : : * and its documentation for any purpose is hereby granted without fee,
34 : : * provided that the above copyright notice appear in all copies and
35 : : * that both that copyright notice and this permission notice appear
36 : : * in supporting documentation. Hewlett-Packard Company makes no
37 : : * representations about the suitability of this software for any
38 : : * purpose. It is provided "as is" without express or implied warranty.
39 : : *
40 : : *
41 : : * Copyright (c) 1997
42 : : * Silicon Graphics Computer Systems, Inc.
43 : : *
44 : : * Permission to use, copy, modify, distribute and sell this software
45 : : * and its documentation for any purpose is hereby granted without fee,
46 : : * provided that the above copyright notice appear in all copies and
47 : : * that both that copyright notice and this permission notice appear
48 : : * in supporting documentation. Silicon Graphics makes no
49 : : * representations about the suitability of this software for any
50 : : * purpose. It is provided "as is" without express or implied warranty.
51 : : */
52 : :
53 : : /** @file bits/deque.tcc
54 : : * This is an internal header file, included by other library headers.
55 : : * Do not attempt to use it directly. @headername{deque}
56 : : */
57 : :
58 : : #ifndef _DEQUE_TCC
59 : : #define _DEQUE_TCC 1
60 : :
61 : : namespace std _GLIBCXX_VISIBILITY(default)
62 : : {
63 : : _GLIBCXX_BEGIN_NAMESPACE_CONTAINER
64 : :
65 : : #ifdef __GXX_EXPERIMENTAL_CXX0X__
66 : : template <typename _Tp, typename _Alloc>
67 : : void
68 : : deque<_Tp, _Alloc>::
69 : : _M_default_initialize()
70 : : {
71 : : _Map_pointer __cur;
72 : : __try
73 : : {
74 : : for (__cur = this->_M_impl._M_start._M_node;
75 : : __cur < this->_M_impl._M_finish._M_node;
76 : : ++__cur)
77 : : std::__uninitialized_default_a(*__cur, *__cur + _S_buffer_size(),
78 : : _M_get_Tp_allocator());
79 : : std::__uninitialized_default_a(this->_M_impl._M_finish._M_first,
80 : : this->_M_impl._M_finish._M_cur,
81 : : _M_get_Tp_allocator());
82 : : }
83 : : __catch(...)
84 : : {
85 : : std::_Destroy(this->_M_impl._M_start, iterator(*__cur, __cur),
86 : : _M_get_Tp_allocator());
87 : : __throw_exception_again;
88 : : }
89 : : }
90 : : #endif
91 : :
92 : : template <typename _Tp, typename _Alloc>
93 : : deque<_Tp, _Alloc>&
94 : : deque<_Tp, _Alloc>::
95 : : operator=(const deque& __x)
96 : : {
97 : : const size_type __len = size();
98 : : if (&__x != this)
99 : : {
100 : : if (__len >= __x.size())
101 : : _M_erase_at_end(std::copy(__x.begin(), __x.end(),
102 : : this->_M_impl._M_start));
103 : : else
104 : : {
105 : : const_iterator __mid = __x.begin() + difference_type(__len);
106 : : std::copy(__x.begin(), __mid, this->_M_impl._M_start);
107 : : insert(this->_M_impl._M_finish, __mid, __x.end());
108 : : }
109 : : }
110 : : return *this;
111 : : }
112 : :
113 : : #ifdef __GXX_EXPERIMENTAL_CXX0X__
114 : : template<typename _Tp, typename _Alloc>
115 : : template<typename... _Args>
116 : : void
117 : : deque<_Tp, _Alloc>::
118 : : emplace_front(_Args&&... __args)
119 : : {
120 : : if (this->_M_impl._M_start._M_cur != this->_M_impl._M_start._M_first)
121 : : {
122 : : this->_M_impl.construct(this->_M_impl._M_start._M_cur - 1,
123 : : std::forward<_Args>(__args)...);
124 : : --this->_M_impl._M_start._M_cur;
125 : : }
126 : : else
127 : : _M_push_front_aux(std::forward<_Args>(__args)...);
128 : : }
129 : :
130 : : template<typename _Tp, typename _Alloc>
131 : : template<typename... _Args>
132 : : void
133 : : deque<_Tp, _Alloc>::
134 : : emplace_back(_Args&&... __args)
135 : : {
136 : : if (this->_M_impl._M_finish._M_cur
137 : : != this->_M_impl._M_finish._M_last - 1)
138 : : {
139 : : this->_M_impl.construct(this->_M_impl._M_finish._M_cur,
140 : : std::forward<_Args>(__args)...);
141 : : ++this->_M_impl._M_finish._M_cur;
142 : : }
143 : : else
144 : : _M_push_back_aux(std::forward<_Args>(__args)...);
145 : : }
146 : : #endif
147 : :
148 : : template <typename _Tp, typename _Alloc>
149 : : typename deque<_Tp, _Alloc>::iterator
150 : : deque<_Tp, _Alloc>::
151 : : insert(iterator __position, const value_type& __x)
152 : : {
153 : : if (__position._M_cur == this->_M_impl._M_start._M_cur)
154 : : {
155 : : push_front(__x);
156 : : return this->_M_impl._M_start;
157 : : }
158 : : else if (__position._M_cur == this->_M_impl._M_finish._M_cur)
159 : : {
160 : : push_back(__x);
161 : : iterator __tmp = this->_M_impl._M_finish;
162 : : --__tmp;
163 : : return __tmp;
164 : : }
165 : : else
166 : : return _M_insert_aux(__position, __x);
167 : : }
168 : :
169 : : #ifdef __GXX_EXPERIMENTAL_CXX0X__
170 : : template<typename _Tp, typename _Alloc>
171 : : template<typename... _Args>
172 : : typename deque<_Tp, _Alloc>::iterator
173 : : deque<_Tp, _Alloc>::
174 : : emplace(iterator __position, _Args&&... __args)
175 : : {
176 : : if (__position._M_cur == this->_M_impl._M_start._M_cur)
177 : : {
178 : : emplace_front(std::forward<_Args>(__args)...);
179 : : return this->_M_impl._M_start;
180 : : }
181 : : else if (__position._M_cur == this->_M_impl._M_finish._M_cur)
182 : : {
183 : : emplace_back(std::forward<_Args>(__args)...);
184 : : iterator __tmp = this->_M_impl._M_finish;
185 : : --__tmp;
186 : : return __tmp;
187 : : }
188 : : else
189 : : return _M_insert_aux(__position, std::forward<_Args>(__args)...);
190 : : }
191 : : #endif
192 : :
193 : : template <typename _Tp, typename _Alloc>
194 : : typename deque<_Tp, _Alloc>::iterator
195 : : deque<_Tp, _Alloc>::
196 : : erase(iterator __position)
197 : : {
198 : : iterator __next = __position;
199 : : ++__next;
200 : : const difference_type __index = __position - begin();
201 : : if (static_cast<size_type>(__index) < (size() >> 1))
202 : : {
203 : : if (__position != begin())
204 : : _GLIBCXX_MOVE_BACKWARD3(begin(), __position, __next);
205 : : pop_front();
206 : : }
207 : : else
208 : : {
209 : : if (__next != end())
210 : : _GLIBCXX_MOVE3(__next, end(), __position);
211 : : pop_back();
212 : : }
213 : : return begin() + __index;
214 : : }
215 : :
216 : : template <typename _Tp, typename _Alloc>
217 : : typename deque<_Tp, _Alloc>::iterator
218 : : deque<_Tp, _Alloc>::
219 : : erase(iterator __first, iterator __last)
220 : : {
221 : : if (__first == __last)
222 : : return __first;
223 : : else if (__first == begin() && __last == end())
224 : : {
225 : : clear();
226 : : return end();
227 : : }
228 : : else
229 : : {
230 : : const difference_type __n = __last - __first;
231 : : const difference_type __elems_before = __first - begin();
232 : : if (static_cast<size_type>(__elems_before) <= (size() - __n) / 2)
233 : : {
234 : : if (__first != begin())
235 : : _GLIBCXX_MOVE_BACKWARD3(begin(), __first, __last);
236 : : _M_erase_at_begin(begin() + __n);
237 : : }
238 : : else
239 : : {
240 : : if (__last != end())
241 : : _GLIBCXX_MOVE3(__last, end(), __first);
242 : : _M_erase_at_end(end() - __n);
243 : : }
244 : : return begin() + __elems_before;
245 : : }
246 : : }
247 : :
248 : : template <typename _Tp, class _Alloc>
249 : : template <typename _InputIterator>
250 : : void
251 : : deque<_Tp, _Alloc>::
252 : : _M_assign_aux(_InputIterator __first, _InputIterator __last,
253 : : std::input_iterator_tag)
254 : : {
255 : : iterator __cur = begin();
256 : : for (; __first != __last && __cur != end(); ++__cur, ++__first)
257 : : *__cur = *__first;
258 : : if (__first == __last)
259 : : _M_erase_at_end(__cur);
260 : : else
261 : : insert(end(), __first, __last);
262 : : }
263 : :
264 : : template <typename _Tp, typename _Alloc>
265 : : void
266 : : deque<_Tp, _Alloc>::
267 : : _M_fill_insert(iterator __pos, size_type __n, const value_type& __x)
268 : : {
269 : : if (__pos._M_cur == this->_M_impl._M_start._M_cur)
270 : : {
271 : : iterator __new_start = _M_reserve_elements_at_front(__n);
272 : : __try
273 : : {
274 : : std::__uninitialized_fill_a(__new_start, this->_M_impl._M_start,
275 : : __x, _M_get_Tp_allocator());
276 : : this->_M_impl._M_start = __new_start;
277 : : }
278 : : __catch(...)
279 : : {
280 : : _M_destroy_nodes(__new_start._M_node,
281 : : this->_M_impl._M_start._M_node);
282 : : __throw_exception_again;
283 : : }
284 : : }
285 : : else if (__pos._M_cur == this->_M_impl._M_finish._M_cur)
286 : : {
287 : : iterator __new_finish = _M_reserve_elements_at_back(__n);
288 : : __try
289 : : {
290 : : std::__uninitialized_fill_a(this->_M_impl._M_finish,
291 : : __new_finish, __x,
292 : : _M_get_Tp_allocator());
293 : : this->_M_impl._M_finish = __new_finish;
294 : : }
295 : : __catch(...)
296 : : {
297 : : _M_destroy_nodes(this->_M_impl._M_finish._M_node + 1,
298 : : __new_finish._M_node + 1);
299 : : __throw_exception_again;
300 : : }
301 : : }
302 : : else
303 : : _M_insert_aux(__pos, __n, __x);
304 : : }
305 : :
306 : : #ifdef __GXX_EXPERIMENTAL_CXX0X__
307 : : template <typename _Tp, typename _Alloc>
308 : : void
309 : : deque<_Tp, _Alloc>::
310 : : _M_default_append(size_type __n)
311 : : {
312 : : if (__n)
313 : : {
314 : : iterator __new_finish = _M_reserve_elements_at_back(__n);
315 : : __try
316 : : {
317 : : std::__uninitialized_default_a(this->_M_impl._M_finish,
318 : : __new_finish,
319 : : _M_get_Tp_allocator());
320 : : this->_M_impl._M_finish = __new_finish;
321 : : }
322 : : __catch(...)
323 : : {
324 : : _M_destroy_nodes(this->_M_impl._M_finish._M_node + 1,
325 : : __new_finish._M_node + 1);
326 : : __throw_exception_again;
327 : : }
328 : : }
329 : : }
330 : :
331 : : template <typename _Tp, typename _Alloc>
332 : : bool
333 : : deque<_Tp, _Alloc>::
334 : : _M_shrink_to_fit()
335 : : {
336 : : const difference_type __front_capacity
337 : : = (this->_M_impl._M_start._M_cur - this->_M_impl._M_start._M_first);
338 : : if (__front_capacity == 0)
339 : : return false;
340 : :
341 : : const difference_type __back_capacity
342 : : = (this->_M_impl._M_finish._M_last - this->_M_impl._M_finish._M_cur);
343 : : if (__front_capacity + __back_capacity < _S_buffer_size())
344 : : return false;
345 : :
346 : : return std::__shrink_to_fit_aux<deque>::_S_do_it(*this);
347 : : }
348 : : #endif
349 : :
350 : : template <typename _Tp, typename _Alloc>
351 : : void
352 : 101007 : deque<_Tp, _Alloc>::
353 : : _M_fill_initialize(const value_type& __value)
354 : : {
355 : : _Map_pointer __cur;
356 : : __try
357 : : {
358 [ - + ]: 101007 : for (__cur = this->_M_impl._M_start._M_node;
359 : : __cur < this->_M_impl._M_finish._M_node;
360 : : ++__cur)
361 [ # # ]: 0 : std::__uninitialized_fill_a(*__cur, *__cur + _S_buffer_size(),
362 : : __value, _M_get_Tp_allocator());
363 [ + - ]: 101007 : std::__uninitialized_fill_a(this->_M_impl._M_finish._M_first,
364 : : this->_M_impl._M_finish._M_cur,
365 : : __value, _M_get_Tp_allocator());
366 : : }
367 : : __catch(...)
368 : : {
369 [ # # # # ]: : std::_Destroy(this->_M_impl._M_start, iterator(*__cur, __cur),
370 : : _M_get_Tp_allocator());
371 : : __throw_exception_again;
372 : : }
373 : 101007 : }
374 : :
375 : : template <typename _Tp, typename _Alloc>
376 : : template <typename _InputIterator>
377 : : void
378 : : deque<_Tp, _Alloc>::
379 : : _M_range_initialize(_InputIterator __first, _InputIterator __last,
380 : : std::input_iterator_tag)
381 : : {
382 : : this->_M_initialize_map(0);
383 : : __try
384 : : {
385 : : for (; __first != __last; ++__first)
386 : : push_back(*__first);
387 : : }
388 : : __catch(...)
389 : : {
390 : : clear();
391 : : __throw_exception_again;
392 : : }
393 : : }
394 : :
395 : : template <typename _Tp, typename _Alloc>
396 : : template <typename _ForwardIterator>
397 : : void
398 : : deque<_Tp, _Alloc>::
399 : : _M_range_initialize(_ForwardIterator __first, _ForwardIterator __last,
400 : : std::forward_iterator_tag)
401 : : {
402 : : const size_type __n = std::distance(__first, __last);
403 : : this->_M_initialize_map(__n);
404 : :
405 : : _Map_pointer __cur_node;
406 : : __try
407 : : {
408 : : for (__cur_node = this->_M_impl._M_start._M_node;
409 : : __cur_node < this->_M_impl._M_finish._M_node;
410 : : ++__cur_node)
411 : : {
412 : : _ForwardIterator __mid = __first;
413 : : std::advance(__mid, _S_buffer_size());
414 : : std::__uninitialized_copy_a(__first, __mid, *__cur_node,
415 : : _M_get_Tp_allocator());
416 : : __first = __mid;
417 : : }
418 : : std::__uninitialized_copy_a(__first, __last,
419 : : this->_M_impl._M_finish._M_first,
420 : : _M_get_Tp_allocator());
421 : : }
422 : : __catch(...)
423 : : {
424 : : std::_Destroy(this->_M_impl._M_start,
425 : : iterator(*__cur_node, __cur_node),
426 : : _M_get_Tp_allocator());
427 : : __throw_exception_again;
428 : : }
429 : : }
430 : :
431 : : // Called only if _M_impl._M_finish._M_cur == _M_impl._M_finish._M_last - 1.
432 : : template<typename _Tp, typename _Alloc>
433 : : #ifdef __GXX_EXPERIMENTAL_CXX0X__
434 : : template<typename... _Args>
435 : : void
436 : : deque<_Tp, _Alloc>::
437 : : _M_push_back_aux(_Args&&... __args)
438 : : #else
439 : : void
440 : 0 : deque<_Tp, _Alloc>::
441 : : _M_push_back_aux(const value_type& __t)
442 : : #endif
443 : : {
444 : 0 : _M_reserve_map_at_back();
445 : 0 : *(this->_M_impl._M_finish._M_node + 1) = this->_M_allocate_node();
446 : : __try
447 : : {
448 : : #ifdef __GXX_EXPERIMENTAL_CXX0X__
449 : : this->_M_impl.construct(this->_M_impl._M_finish._M_cur,
450 : : std::forward<_Args>(__args)...);
451 : : #else
452 : 0 : this->_M_impl.construct(this->_M_impl._M_finish._M_cur, __t);
453 : : #endif
454 [ # # # # : 0 : this->_M_impl._M_finish._M_set_node(this->_M_impl._M_finish._M_node
# # # # ]
455 : : + 1);
456 : 0 : this->_M_impl._M_finish._M_cur = this->_M_impl._M_finish._M_first;
457 : : }
458 : : __catch(...)
459 : : {
460 [ # # # # : : _M_deallocate_node(*(this->_M_impl._M_finish._M_node + 1));
# # # # ]
461 : : __throw_exception_again;
462 : : }
463 : 0 : }
464 : :
465 : : // Called only if _M_impl._M_start._M_cur == _M_impl._M_start._M_first.
466 : : template<typename _Tp, typename _Alloc>
467 : : #ifdef __GXX_EXPERIMENTAL_CXX0X__
468 : : template<typename... _Args>
469 : : void
470 : : deque<_Tp, _Alloc>::
471 : : _M_push_front_aux(_Args&&... __args)
472 : : #else
473 : : void
474 : : deque<_Tp, _Alloc>::
475 : : _M_push_front_aux(const value_type& __t)
476 : : #endif
477 : : {
478 : : _M_reserve_map_at_front();
479 : : *(this->_M_impl._M_start._M_node - 1) = this->_M_allocate_node();
480 : : __try
481 : : {
482 : : this->_M_impl._M_start._M_set_node(this->_M_impl._M_start._M_node
483 : : - 1);
484 : : this->_M_impl._M_start._M_cur = this->_M_impl._M_start._M_last - 1;
485 : : #ifdef __GXX_EXPERIMENTAL_CXX0X__
486 : : this->_M_impl.construct(this->_M_impl._M_start._M_cur,
487 : : std::forward<_Args>(__args)...);
488 : : #else
489 : : this->_M_impl.construct(this->_M_impl._M_start._M_cur, __t);
490 : : #endif
491 : : }
492 : : __catch(...)
493 : : {
494 : : ++this->_M_impl._M_start;
495 : : _M_deallocate_node(*(this->_M_impl._M_start._M_node - 1));
496 : : __throw_exception_again;
497 : : }
498 : : }
499 : :
500 : : // Called only if _M_impl._M_finish._M_cur == _M_impl._M_finish._M_first.
501 : : template <typename _Tp, typename _Alloc>
502 : 0 : void deque<_Tp, _Alloc>::
503 : : _M_pop_back_aux()
504 : : {
505 : 0 : _M_deallocate_node(this->_M_impl._M_finish._M_first);
506 : 0 : this->_M_impl._M_finish._M_set_node(this->_M_impl._M_finish._M_node - 1);
507 : 0 : this->_M_impl._M_finish._M_cur = this->_M_impl._M_finish._M_last - 1;
508 : 0 : this->_M_impl.destroy(this->_M_impl._M_finish._M_cur);
509 : 0 : }
510 : :
511 : : // Called only if _M_impl._M_start._M_cur == _M_impl._M_start._M_last - 1.
512 : : // Note that if the deque has at least one element (a precondition for this
513 : : // member function), and if
514 : : // _M_impl._M_start._M_cur == _M_impl._M_start._M_last,
515 : : // then the deque must have at least two nodes.
516 : : template <typename _Tp, typename _Alloc>
517 : 0 : void deque<_Tp, _Alloc>::
518 : : _M_pop_front_aux()
519 : : {
520 : 0 : this->_M_impl.destroy(this->_M_impl._M_start._M_cur);
521 : 0 : _M_deallocate_node(this->_M_impl._M_start._M_first);
522 : 0 : this->_M_impl._M_start._M_set_node(this->_M_impl._M_start._M_node + 1);
523 : 0 : this->_M_impl._M_start._M_cur = this->_M_impl._M_start._M_first;
524 : 0 : }
525 : :
526 : : template <typename _Tp, typename _Alloc>
527 : : template <typename _InputIterator>
528 : : void
529 : : deque<_Tp, _Alloc>::
530 : : _M_range_insert_aux(iterator __pos,
531 : : _InputIterator __first, _InputIterator __last,
532 : : std::input_iterator_tag)
533 : : { std::copy(__first, __last, std::inserter(*this, __pos)); }
534 : :
535 : : template <typename _Tp, typename _Alloc>
536 : : template <typename _ForwardIterator>
537 : : void
538 : : deque<_Tp, _Alloc>::
539 : : _M_range_insert_aux(iterator __pos,
540 : : _ForwardIterator __first, _ForwardIterator __last,
541 : : std::forward_iterator_tag)
542 : : {
543 : : const size_type __n = std::distance(__first, __last);
544 : : if (__pos._M_cur == this->_M_impl._M_start._M_cur)
545 : : {
546 : : iterator __new_start = _M_reserve_elements_at_front(__n);
547 : : __try
548 : : {
549 : : std::__uninitialized_copy_a(__first, __last, __new_start,
550 : : _M_get_Tp_allocator());
551 : : this->_M_impl._M_start = __new_start;
552 : : }
553 : : __catch(...)
554 : : {
555 : : _M_destroy_nodes(__new_start._M_node,
556 : : this->_M_impl._M_start._M_node);
557 : : __throw_exception_again;
558 : : }
559 : : }
560 : : else if (__pos._M_cur == this->_M_impl._M_finish._M_cur)
561 : : {
562 : : iterator __new_finish = _M_reserve_elements_at_back(__n);
563 : : __try
564 : : {
565 : : std::__uninitialized_copy_a(__first, __last,
566 : : this->_M_impl._M_finish,
567 : : _M_get_Tp_allocator());
568 : : this->_M_impl._M_finish = __new_finish;
569 : : }
570 : : __catch(...)
571 : : {
572 : : _M_destroy_nodes(this->_M_impl._M_finish._M_node + 1,
573 : : __new_finish._M_node + 1);
574 : : __throw_exception_again;
575 : : }
576 : : }
577 : : else
578 : : _M_insert_aux(__pos, __first, __last, __n);
579 : : }
580 : :
581 : : template<typename _Tp, typename _Alloc>
582 : : #ifdef __GXX_EXPERIMENTAL_CXX0X__
583 : : template<typename... _Args>
584 : : typename deque<_Tp, _Alloc>::iterator
585 : : deque<_Tp, _Alloc>::
586 : : _M_insert_aux(iterator __pos, _Args&&... __args)
587 : : {
588 : : value_type __x_copy(std::forward<_Args>(__args)...); // XXX copy
589 : : #else
590 : : typename deque<_Tp, _Alloc>::iterator
591 : : deque<_Tp, _Alloc>::
592 : : _M_insert_aux(iterator __pos, const value_type& __x)
593 : : {
594 : : value_type __x_copy = __x; // XXX copy
595 : : #endif
596 : : difference_type __index = __pos - this->_M_impl._M_start;
597 : : if (static_cast<size_type>(__index) < size() / 2)
598 : : {
599 : : push_front(_GLIBCXX_MOVE(front()));
600 : : iterator __front1 = this->_M_impl._M_start;
601 : : ++__front1;
602 : : iterator __front2 = __front1;
603 : : ++__front2;
604 : : __pos = this->_M_impl._M_start + __index;
605 : : iterator __pos1 = __pos;
606 : : ++__pos1;
607 : : _GLIBCXX_MOVE3(__front2, __pos1, __front1);
608 : : }
609 : : else
610 : : {
611 : : push_back(_GLIBCXX_MOVE(back()));
612 : : iterator __back1 = this->_M_impl._M_finish;
613 : : --__back1;
614 : : iterator __back2 = __back1;
615 : : --__back2;
616 : : __pos = this->_M_impl._M_start + __index;
617 : : _GLIBCXX_MOVE_BACKWARD3(__pos, __back2, __back1);
618 : : }
619 : : *__pos = _GLIBCXX_MOVE(__x_copy);
620 : : return __pos;
621 : : }
622 : :
623 : : template <typename _Tp, typename _Alloc>
624 : : void
625 : : deque<_Tp, _Alloc>::
626 : : _M_insert_aux(iterator __pos, size_type __n, const value_type& __x)
627 : : {
628 : : const difference_type __elems_before = __pos - this->_M_impl._M_start;
629 : : const size_type __length = this->size();
630 : : value_type __x_copy = __x;
631 : : if (__elems_before < difference_type(__length / 2))
632 : : {
633 : : iterator __new_start = _M_reserve_elements_at_front(__n);
634 : : iterator __old_start = this->_M_impl._M_start;
635 : : __pos = this->_M_impl._M_start + __elems_before;
636 : : __try
637 : : {
638 : : if (__elems_before >= difference_type(__n))
639 : : {
640 : : iterator __start_n = (this->_M_impl._M_start
641 : : + difference_type(__n));
642 : : std::__uninitialized_move_a(this->_M_impl._M_start,
643 : : __start_n, __new_start,
644 : : _M_get_Tp_allocator());
645 : : this->_M_impl._M_start = __new_start;
646 : : _GLIBCXX_MOVE3(__start_n, __pos, __old_start);
647 : : std::fill(__pos - difference_type(__n), __pos, __x_copy);
648 : : }
649 : : else
650 : : {
651 : : std::__uninitialized_move_fill(this->_M_impl._M_start,
652 : : __pos, __new_start,
653 : : this->_M_impl._M_start,
654 : : __x_copy,
655 : : _M_get_Tp_allocator());
656 : : this->_M_impl._M_start = __new_start;
657 : : std::fill(__old_start, __pos, __x_copy);
658 : : }
659 : : }
660 : : __catch(...)
661 : : {
662 : : _M_destroy_nodes(__new_start._M_node,
663 : : this->_M_impl._M_start._M_node);
664 : : __throw_exception_again;
665 : : }
666 : : }
667 : : else
668 : : {
669 : : iterator __new_finish = _M_reserve_elements_at_back(__n);
670 : : iterator __old_finish = this->_M_impl._M_finish;
671 : : const difference_type __elems_after =
672 : : difference_type(__length) - __elems_before;
673 : : __pos = this->_M_impl._M_finish - __elems_after;
674 : : __try
675 : : {
676 : : if (__elems_after > difference_type(__n))
677 : : {
678 : : iterator __finish_n = (this->_M_impl._M_finish
679 : : - difference_type(__n));
680 : : std::__uninitialized_move_a(__finish_n,
681 : : this->_M_impl._M_finish,
682 : : this->_M_impl._M_finish,
683 : : _M_get_Tp_allocator());
684 : : this->_M_impl._M_finish = __new_finish;
685 : : _GLIBCXX_MOVE_BACKWARD3(__pos, __finish_n, __old_finish);
686 : : std::fill(__pos, __pos + difference_type(__n), __x_copy);
687 : : }
688 : : else
689 : : {
690 : : std::__uninitialized_fill_move(this->_M_impl._M_finish,
691 : : __pos + difference_type(__n),
692 : : __x_copy, __pos,
693 : : this->_M_impl._M_finish,
694 : : _M_get_Tp_allocator());
695 : : this->_M_impl._M_finish = __new_finish;
696 : : std::fill(__pos, __old_finish, __x_copy);
697 : : }
698 : : }
699 : : __catch(...)
700 : : {
701 : : _M_destroy_nodes(this->_M_impl._M_finish._M_node + 1,
702 : : __new_finish._M_node + 1);
703 : : __throw_exception_again;
704 : : }
705 : : }
706 : : }
707 : :
708 : : template <typename _Tp, typename _Alloc>
709 : : template <typename _ForwardIterator>
710 : : void
711 : : deque<_Tp, _Alloc>::
712 : : _M_insert_aux(iterator __pos,
713 : : _ForwardIterator __first, _ForwardIterator __last,
714 : : size_type __n)
715 : : {
716 : : const difference_type __elemsbefore = __pos - this->_M_impl._M_start;
717 : : const size_type __length = size();
718 : : if (static_cast<size_type>(__elemsbefore) < __length / 2)
719 : : {
720 : : iterator __new_start = _M_reserve_elements_at_front(__n);
721 : : iterator __old_start = this->_M_impl._M_start;
722 : : __pos = this->_M_impl._M_start + __elemsbefore;
723 : : __try
724 : : {
725 : : if (__elemsbefore >= difference_type(__n))
726 : : {
727 : : iterator __start_n = (this->_M_impl._M_start
728 : : + difference_type(__n));
729 : : std::__uninitialized_move_a(this->_M_impl._M_start,
730 : : __start_n, __new_start,
731 : : _M_get_Tp_allocator());
732 : : this->_M_impl._M_start = __new_start;
733 : : _GLIBCXX_MOVE3(__start_n, __pos, __old_start);
734 : : std::copy(__first, __last, __pos - difference_type(__n));
735 : : }
736 : : else
737 : : {
738 : : _ForwardIterator __mid = __first;
739 : : std::advance(__mid, difference_type(__n) - __elemsbefore);
740 : : std::__uninitialized_move_copy(this->_M_impl._M_start,
741 : : __pos, __first, __mid,
742 : : __new_start,
743 : : _M_get_Tp_allocator());
744 : : this->_M_impl._M_start = __new_start;
745 : : std::copy(__mid, __last, __old_start);
746 : : }
747 : : }
748 : : __catch(...)
749 : : {
750 : : _M_destroy_nodes(__new_start._M_node,
751 : : this->_M_impl._M_start._M_node);
752 : : __throw_exception_again;
753 : : }
754 : : }
755 : : else
756 : : {
757 : : iterator __new_finish = _M_reserve_elements_at_back(__n);
758 : : iterator __old_finish = this->_M_impl._M_finish;
759 : : const difference_type __elemsafter =
760 : : difference_type(__length) - __elemsbefore;
761 : : __pos = this->_M_impl._M_finish - __elemsafter;
762 : : __try
763 : : {
764 : : if (__elemsafter > difference_type(__n))
765 : : {
766 : : iterator __finish_n = (this->_M_impl._M_finish
767 : : - difference_type(__n));
768 : : std::__uninitialized_move_a(__finish_n,
769 : : this->_M_impl._M_finish,
770 : : this->_M_impl._M_finish,
771 : : _M_get_Tp_allocator());
772 : : this->_M_impl._M_finish = __new_finish;
773 : : _GLIBCXX_MOVE_BACKWARD3(__pos, __finish_n, __old_finish);
774 : : std::copy(__first, __last, __pos);
775 : : }
776 : : else
777 : : {
778 : : _ForwardIterator __mid = __first;
779 : : std::advance(__mid, __elemsafter);
780 : : std::__uninitialized_copy_move(__mid, __last, __pos,
781 : : this->_M_impl._M_finish,
782 : : this->_M_impl._M_finish,
783 : : _M_get_Tp_allocator());
784 : : this->_M_impl._M_finish = __new_finish;
785 : : std::copy(__first, __mid, __pos);
786 : : }
787 : : }
788 : : __catch(...)
789 : : {
790 : : _M_destroy_nodes(this->_M_impl._M_finish._M_node + 1,
791 : : __new_finish._M_node + 1);
792 : : __throw_exception_again;
793 : : }
794 : : }
795 : : }
796 : :
797 : : template<typename _Tp, typename _Alloc>
798 : : void
799 : : deque<_Tp, _Alloc>::
800 : : _M_destroy_data_aux(iterator __first, iterator __last)
801 : : {
802 : : for (_Map_pointer __node = __first._M_node + 1;
803 : : __node < __last._M_node; ++__node)
804 : : std::_Destroy(*__node, *__node + _S_buffer_size(),
805 : : _M_get_Tp_allocator());
806 : :
807 : : if (__first._M_node != __last._M_node)
808 : : {
809 : : std::_Destroy(__first._M_cur, __first._M_last,
810 : : _M_get_Tp_allocator());
811 : : std::_Destroy(__last._M_first, __last._M_cur,
812 : : _M_get_Tp_allocator());
813 : : }
814 : : else
815 : : std::_Destroy(__first._M_cur, __last._M_cur,
816 : : _M_get_Tp_allocator());
817 : : }
818 : :
819 : : template <typename _Tp, typename _Alloc>
820 : : void
821 : : deque<_Tp, _Alloc>::
822 : : _M_new_elements_at_front(size_type __new_elems)
823 : : {
824 : : if (this->max_size() - this->size() < __new_elems)
825 : : __throw_length_error(__N("deque::_M_new_elements_at_front"));
826 : :
827 : : const size_type __new_nodes = ((__new_elems + _S_buffer_size() - 1)
828 : : / _S_buffer_size());
829 : : _M_reserve_map_at_front(__new_nodes);
830 : : size_type __i;
831 : : __try
832 : : {
833 : : for (__i = 1; __i <= __new_nodes; ++__i)
834 : : *(this->_M_impl._M_start._M_node - __i) = this->_M_allocate_node();
835 : : }
836 : : __catch(...)
837 : : {
838 : : for (size_type __j = 1; __j < __i; ++__j)
839 : : _M_deallocate_node(*(this->_M_impl._M_start._M_node - __j));
840 : : __throw_exception_again;
841 : : }
842 : : }
843 : :
844 : : template <typename _Tp, typename _Alloc>
845 : : void
846 : : deque<_Tp, _Alloc>::
847 : : _M_new_elements_at_back(size_type __new_elems)
848 : : {
849 : : if (this->max_size() - this->size() < __new_elems)
850 : : __throw_length_error(__N("deque::_M_new_elements_at_back"));
851 : :
852 : : const size_type __new_nodes = ((__new_elems + _S_buffer_size() - 1)
853 : : / _S_buffer_size());
854 : : _M_reserve_map_at_back(__new_nodes);
855 : : size_type __i;
856 : : __try
857 : : {
858 : : for (__i = 1; __i <= __new_nodes; ++__i)
859 : : *(this->_M_impl._M_finish._M_node + __i) = this->_M_allocate_node();
860 : : }
861 : : __catch(...)
862 : : {
863 : : for (size_type __j = 1; __j < __i; ++__j)
864 : : _M_deallocate_node(*(this->_M_impl._M_finish._M_node + __j));
865 : : __throw_exception_again;
866 : : }
867 : : }
868 : :
869 : : template <typename _Tp, typename _Alloc>
870 : : void
871 : 0 : deque<_Tp, _Alloc>::
872 : : _M_reallocate_map(size_type __nodes_to_add, bool __add_at_front)
873 : : {
874 : : const size_type __old_num_nodes
875 : 0 : = this->_M_impl._M_finish._M_node - this->_M_impl._M_start._M_node + 1;
876 : 0 : const size_type __new_num_nodes = __old_num_nodes + __nodes_to_add;
877 : :
878 : : _Map_pointer __new_nstart;
879 [ # # ][ # # ]: 0 : if (this->_M_impl._M_map_size > 2 * __new_num_nodes)
[ # # ][ # # ]
880 : : {
881 [ # # ][ # # ]: 0 : __new_nstart = this->_M_impl._M_map + (this->_M_impl._M_map_size
[ # # ][ # # ]
882 : : - __new_num_nodes) / 2
883 : : + (__add_at_front ? __nodes_to_add : 0);
884 [ # # ][ # # ]: 0 : if (__new_nstart < this->_M_impl._M_start._M_node)
[ # # ][ # # ]
885 : 0 : std::copy(this->_M_impl._M_start._M_node,
886 : : this->_M_impl._M_finish._M_node + 1,
887 : : __new_nstart);
888 : : else
889 : 0 : std::copy_backward(this->_M_impl._M_start._M_node,
890 : : this->_M_impl._M_finish._M_node + 1,
891 : : __new_nstart + __old_num_nodes);
892 : : }
893 : : else
894 : : {
895 : : size_type __new_map_size = this->_M_impl._M_map_size
896 : : + std::max(this->_M_impl._M_map_size,
897 : 0 : __nodes_to_add) + 2;
898 : :
899 : 0 : _Map_pointer __new_map = this->_M_allocate_map(__new_map_size);
900 [ # # ][ # # ]: 0 : __new_nstart = __new_map + (__new_map_size - __new_num_nodes) / 2
[ # # ][ # # ]
901 : : + (__add_at_front ? __nodes_to_add : 0);
902 : 0 : std::copy(this->_M_impl._M_start._M_node,
903 : : this->_M_impl._M_finish._M_node + 1,
904 : : __new_nstart);
905 : 0 : _M_deallocate_map(this->_M_impl._M_map, this->_M_impl._M_map_size);
906 : :
907 : 0 : this->_M_impl._M_map = __new_map;
908 : 0 : this->_M_impl._M_map_size = __new_map_size;
909 : : }
910 : :
911 : 0 : this->_M_impl._M_start._M_set_node(__new_nstart);
912 : 0 : this->_M_impl._M_finish._M_set_node(__new_nstart + __old_num_nodes - 1);
913 : 0 : }
914 : :
915 : : // Overload for deque::iterators, exploiting the "segmented-iterator
916 : : // optimization".
917 : : template<typename _Tp>
918 : : void
919 : : fill(const _Deque_iterator<_Tp, _Tp&, _Tp*>& __first,
920 : : const _Deque_iterator<_Tp, _Tp&, _Tp*>& __last, const _Tp& __value)
921 : : {
922 : : typedef typename _Deque_iterator<_Tp, _Tp&, _Tp*>::_Self _Self;
923 : :
924 : : for (typename _Self::_Map_pointer __node = __first._M_node + 1;
925 : : __node < __last._M_node; ++__node)
926 : : std::fill(*__node, *__node + _Self::_S_buffer_size(), __value);
927 : :
928 : : if (__first._M_node != __last._M_node)
929 : : {
930 : : std::fill(__first._M_cur, __first._M_last, __value);
931 : : std::fill(__last._M_first, __last._M_cur, __value);
932 : : }
933 : : else
934 : : std::fill(__first._M_cur, __last._M_cur, __value);
935 : : }
936 : :
937 : : template<typename _Tp>
938 : : _Deque_iterator<_Tp, _Tp&, _Tp*>
939 : : copy(_Deque_iterator<_Tp, const _Tp&, const _Tp*> __first,
940 : : _Deque_iterator<_Tp, const _Tp&, const _Tp*> __last,
941 : : _Deque_iterator<_Tp, _Tp&, _Tp*> __result)
942 : : {
943 : : typedef typename _Deque_iterator<_Tp, _Tp&, _Tp*>::_Self _Self;
944 : : typedef typename _Self::difference_type difference_type;
945 : :
946 : : difference_type __len = __last - __first;
947 : : while (__len > 0)
948 : : {
949 : : const difference_type __clen
950 : : = std::min(__len, std::min(__first._M_last - __first._M_cur,
951 : : __result._M_last - __result._M_cur));
952 : : std::copy(__first._M_cur, __first._M_cur + __clen, __result._M_cur);
953 : : __first += __clen;
954 : : __result += __clen;
955 : : __len -= __clen;
956 : : }
957 : : return __result;
958 : : }
959 : :
960 : : template<typename _Tp>
961 : : _Deque_iterator<_Tp, _Tp&, _Tp*>
962 : : copy_backward(_Deque_iterator<_Tp, const _Tp&, const _Tp*> __first,
963 : : _Deque_iterator<_Tp, const _Tp&, const _Tp*> __last,
964 : : _Deque_iterator<_Tp, _Tp&, _Tp*> __result)
965 : : {
966 : : typedef typename _Deque_iterator<_Tp, _Tp&, _Tp*>::_Self _Self;
967 : : typedef typename _Self::difference_type difference_type;
968 : :
969 : : difference_type __len = __last - __first;
970 : : while (__len > 0)
971 : : {
972 : : difference_type __llen = __last._M_cur - __last._M_first;
973 : : _Tp* __lend = __last._M_cur;
974 : :
975 : : difference_type __rlen = __result._M_cur - __result._M_first;
976 : : _Tp* __rend = __result._M_cur;
977 : :
978 : : if (!__llen)
979 : : {
980 : : __llen = _Self::_S_buffer_size();
981 : : __lend = *(__last._M_node - 1) + __llen;
982 : : }
983 : : if (!__rlen)
984 : : {
985 : : __rlen = _Self::_S_buffer_size();
986 : : __rend = *(__result._M_node - 1) + __rlen;
987 : : }
988 : :
989 : : const difference_type __clen = std::min(__len,
990 : : std::min(__llen, __rlen));
991 : : std::copy_backward(__lend - __clen, __lend, __rend);
992 : : __last -= __clen;
993 : : __result -= __clen;
994 : : __len -= __clen;
995 : : }
996 : : return __result;
997 : : }
998 : :
999 : : #ifdef __GXX_EXPERIMENTAL_CXX0X__
1000 : : template<typename _Tp>
1001 : : _Deque_iterator<_Tp, _Tp&, _Tp*>
1002 : : move(_Deque_iterator<_Tp, const _Tp&, const _Tp*> __first,
1003 : : _Deque_iterator<_Tp, const _Tp&, const _Tp*> __last,
1004 : : _Deque_iterator<_Tp, _Tp&, _Tp*> __result)
1005 : : {
1006 : : typedef typename _Deque_iterator<_Tp, _Tp&, _Tp*>::_Self _Self;
1007 : : typedef typename _Self::difference_type difference_type;
1008 : :
1009 : : difference_type __len = __last - __first;
1010 : : while (__len > 0)
1011 : : {
1012 : : const difference_type __clen
1013 : : = std::min(__len, std::min(__first._M_last - __first._M_cur,
1014 : : __result._M_last - __result._M_cur));
1015 : : std::move(__first._M_cur, __first._M_cur + __clen, __result._M_cur);
1016 : : __first += __clen;
1017 : : __result += __clen;
1018 : : __len -= __clen;
1019 : : }
1020 : : return __result;
1021 : : }
1022 : :
1023 : : template<typename _Tp>
1024 : : _Deque_iterator<_Tp, _Tp&, _Tp*>
1025 : : move_backward(_Deque_iterator<_Tp, const _Tp&, const _Tp*> __first,
1026 : : _Deque_iterator<_Tp, const _Tp&, const _Tp*> __last,
1027 : : _Deque_iterator<_Tp, _Tp&, _Tp*> __result)
1028 : : {
1029 : : typedef typename _Deque_iterator<_Tp, _Tp&, _Tp*>::_Self _Self;
1030 : : typedef typename _Self::difference_type difference_type;
1031 : :
1032 : : difference_type __len = __last - __first;
1033 : : while (__len > 0)
1034 : : {
1035 : : difference_type __llen = __last._M_cur - __last._M_first;
1036 : : _Tp* __lend = __last._M_cur;
1037 : :
1038 : : difference_type __rlen = __result._M_cur - __result._M_first;
1039 : : _Tp* __rend = __result._M_cur;
1040 : :
1041 : : if (!__llen)
1042 : : {
1043 : : __llen = _Self::_S_buffer_size();
1044 : : __lend = *(__last._M_node - 1) + __llen;
1045 : : }
1046 : : if (!__rlen)
1047 : : {
1048 : : __rlen = _Self::_S_buffer_size();
1049 : : __rend = *(__result._M_node - 1) + __rlen;
1050 : : }
1051 : :
1052 : : const difference_type __clen = std::min(__len,
1053 : : std::min(__llen, __rlen));
1054 : : std::move_backward(__lend - __clen, __lend, __rend);
1055 : : __last -= __clen;
1056 : : __result -= __clen;
1057 : : __len -= __clen;
1058 : : }
1059 : : return __result;
1060 : : }
1061 : : #endif
1062 : :
1063 : : _GLIBCXX_END_NAMESPACE_CONTAINER
1064 : : } // namespace std
1065 : :
1066 : : #endif
|
